Minimax en Javascript ne fonctionne pas correctement

Question

En tant que projet de pratique, j'ai fait un jeu Tic-Tac-Toe sur JSFiddle (parce qu'il n'y en a pas déjà assez, non?) Et j'ai progressé dans l'ajout d'une IA imbattable. Pour l'essentiel, cela fonctionne, mais il existe certaines combinaisons (par exemple, en définissant X dans les champs 5, 9, 3 ou dans les champs 3, 7, 9) qui conduisent l'ordinateur à ne pas calculer correctement le déplacement optimal.

Le projet sur jsFiddle: https://jsfiddle.net/jd8x0vjz/

et la fonction correspondante à partir de la ligne 63:

function evaluateMove(move, player, depth) { 
var gameStatus = evaluateGameStatus(move); //get status of current board 
if (gameStatus < 2 && player) 
    return -1; //if human won, return -1 
if (gameStatus < 2 && !player) 
    return 1; //if human lost, return 1 

var returnValue = 0 //value to be returned later 

for (var z = 0; z < 3; z++) { //loop for row 
    for (var s = 0; s < 3; s++) { //loop for column 
     if (move[z][s]) //if current slot has an x or o, 
      continue; //skip it  
     var nextMove = cloneGameStatus(move); //create temporary array with base of current grid 
     nextMove[z][s] = !player ? "x" : "o"; //assign first free field the appropriate symbol 
     var value = evaluateMove(nextMove, !player, depth+1); //recursion but with switched player, to add the correct icon afterwards 
     if ((value > returnValue) && player) 
      returnValue = value;    
     if ((value < returnValue) && !player) 
      returnValue = value;     
    } 
} 
return returnValue; //return value of current simulation 
} 

Je pense que les deux dernières si-clauses sont à l'origine de ces problèmes, puisque l'ordinateur ne calcule le bon valeurs (comme observable dans le débogueur), mais ils sont parfois remplacés, mais je ne suis pas sûr que ce soit vraiment la racine du problème. Toute aide ou conseil serait apprécié!

EDIT: Problème résolu! Recherchez ma réponse ci-dessous au cas où ce n'est pas le premier.

Answer 1

L'idée de la valeur par défaut de returnValue étant erronée m'a définitivement envoyé le bon chemin; ça ne faisait pas tout fonctionner magiquement (ça aurait été trop beau si c'était le cas), mais ça m'a donné le bon coup de pouce. Étant donné que nous ne voulons pas retourner aucune valeur si rien est calculé, je me suis ajusté la fonction evaluateMove comme suit:

function evaluateMove(move, player, depth) { 
var gameStatus = evaluateGameStatus(move); //get status of current board 
if (gameStatus != 2) 
    return gameStatus; //if the game is not running anymore, return result 

var returnValue; //value to be returned later 

for (var z = 0; z < 3; z++) { //loop for row 
    for (var s = 0; s < 3; s++) { //loop for column 
     if (move[z][s]) //if current slot has an x or o, 
      continue; //skip it  
     var nextMove = cloneGameStatus(move); //create temporary array with base of current grid 
     nextMove[z][s] = !player ? "x" : "o"; //assign first free field the appropriate symbol 
     var value = evaluateMove(nextMove, !player, depth+1); //recursion but with switched player, to add the correct icon afterwards 
     if ((value > returnValue || returnValue == null) && player) 
      returnValue = value;    
     if ((value < returnValue || returnValue == null) && !player) 
      returnValue = value;     
    } 
} 
return returnValue; //return value of current simulation 
} 

Maintenant, la valeur par défaut est nul et non en tant que telle ne devrait pas jeter les calculs hors tension. Ce qu'il a fait jaillir était cependant le premier bloc de chèques, donc je l'ai ajusté pour retourner simplement le statut actuel si le jeu était terminé, au lieu de faire des contrôles élaborés. Cependant que a jeté les résultats parce que j'utilise des valeurs par défaut inversées dans les deux méthodes, donc j'ai dû ajuster evaluateGameStatus aussi. Maintenant, si l'humain a gagné renvoie -1 au lieu de 1, et si l'ordinateur a gagné retourne 1 au lieu de -1:

function evaluateGameStatus(gameStatus) { //a clusterfuck of winning combinations 
if(
X Checks 
) 
return -1; //there's a successful combination of x's 

else if(
O Checks 
) 
return 1; //there's a successful combination of o's 

else { 
for (var z = 0; z < 3; z++) { 
    for (var s = 0; s < 3; s++) { 
     if (!gameStatus[z][s]) 
      return 2; //if there is an empty field neither has won, continue playing 
     } 
    } 

return 0; //there's no successful combination and max moves have been reached. it's a draw 
} 
} 

je devais faire les mêmes adjustmends pour la fonction checkGameEnd, évidemment.
Vous remarquerez que j'ai également changé le chèque pour les tirages. C'est parce que, pour une raison quelconque, l'ancienne vérification de count == maxMoves ne fonctionnait plus, donc je suis passé à une boucle qui vérifie simplement s'il y a un champ vide et retourne 2 s'il y en a, et 0 si il n'y en a pas (il renvoie 0 ici car à ce stade il a passé toutes les vérifications: X n'a ​​pas gagné, O n'a pas gagné, et il n'y a plus de slots ouverts, donc le jeu doit être un nul).

projet de travail peut maintenant être trouvé ici:
https://jsfiddle.net/h5zwzkm7/

Answer 2

Je ne peux pas dire avec certitude que c'est la source du problème, mais il y a certainement un bug dans votre code qui produira des résultats étranges. La ligne:

var returnValue = 0 //value to be returned later 

est incorrect. Mis à part le fait que vous manque un point-virgule, le code approprié doit être:

var returnValue = -1; 
if(!player){ 
    returnValue = 1; 
} 

Vous voulez la valeur par défaut pour le joueur maximum être négatif pour qu'il prend le meilleur coup, et pour la réduction au minimum joueur positif donc il prend le pire mouvement. La façon dont vous l'avez fait, si le joueur maximisant était confronté uniquement aux options qui valaient -1, puisque -1 est inférieur à 0 et que returnValue était initialisé à 0, 0 serait renvoyé bien que la valeur correcte à renvoyer soit -1.