Minimax in Javascript funktioniert nicht richtig

Question

Als Übungsprojekt habe ich ein Tic-Tac-Toe-Spiel auf JSFiddle gemacht (weil es nicht genug gibt, oder?) Und ich habe eine unschlagbare KI hinzugefügt. Zum größten Teil funktioniert es, aber es gibt einige Kombinationen (z. B. das Setzen von X in die Felder 5, 9, 3 oder in die Felder 3, 7, 9), die dazu führen, dass der Computer die optimale Bewegung nicht richtig berechnet.

Das Projekt auf JSFiddle: https://jsfiddle.net/jd8x0vjz/

Und die entsprechende Funktion in Zeile 63 beginnen:

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 
} 

Ich denke, die letzten beiden if-Klauseln diese Probleme verursachen, da der Computer die richtige ist zu berechnen Werte (wie im Debugger beobachtbar), aber sie sind manchmal überschrieben, aber ich bin mir nicht sicher, ob dies wirklich die Wurzel des Problems ist. Jede Hilfe oder Tipps wären willkommen!

EDIT: Problem gelöst! Suchen Sie unten nach meiner Antwort, falls es nicht die erste ist.

Answer 1

Die Idee des Default-Wertes von returnValue, der falsch ist, schickte mir definitiv den richtigen Weg; es hat nicht alles magisch funktionieren lassen (wäre zu schön gewesen, wenn es so wäre), aber es gab mir den richtigen Stupser. Da wir nichts keinen Wert zurückgeben möchten, wenn berechnet wird, eingestellt ich die evaluateMove Funktion, wie folgend:

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 
} 

Nun ist die Standard null ist und als solche sollten die Berechnungen abwerfen. Was es jedoch abwarf, war der erste Checkblock, also habe ich ihn angepasst, um einfach den aktuellen Status zurückzugeben, sollte das Spiel beendet sein, anstatt irgendwelche aufwendigen Checks zu machen. Allerdings , dass warf die Ergebnisse ab, weil ich inversed Standardwerte in den beiden Methoden verwende, so dass ich auch evaluateGameStatus anpassen musste. Nun, wenn der Mensch hat es gibt -1 statt 1, und wenn der Computer hat es gibt 1 statt -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 
} 
} 

Ich hatte den gleichen adjustmends für die checkGameEnd Funktion zu tun, natürlich.
Sie werden feststellen, dass ich auch die Prüfung für Ziehungen geändert habe. Das liegt daran, dass die alte Überprüfung für count == maxMoves aus irgendeinem Grund nicht mehr funktionierte, also wechselte ich zu einer Schleife, die einfach überprüft, ob überhaupt ein leeres Feld vorhanden ist, und 2 zurückgibt, falls vorhanden, und 0 if es gibt nicht (es gibt hier 0 zurück, weil es an dieser Stelle alle Prüfungen durchlaufen hat: X hat nicht gewonnen, O hat nicht gewonnen, und es gibt keine offenen Plätze mehr, also muss das Spiel ein Unentschieden sein).

Arbeitsprojekt kann jetzt finden Sie hier:
https://jsfiddle.net/h5zwzkm7/

Answer 2

Ich kann nicht sicher sagen, das ist die Ursache des Problems, aber es gibt definitiv einen Fehler in Ihrem Code, der seltsame Ergebnisse erzeugen wird. Die Zeile:

var returnValue = 0 //value to be returned later 

ist falsch. Abgesehen von der Tatsache, dass Sie ein Semikolon fehlen, soll der richtige Code sein:

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

Sie wollen, dass der Standardwert für den maximalen Spieler negativ zu sein, so dass er den besten Zug nimmt, und für die Minimierungs Spieler positiv, also nimmt er den schlechtesten Zug. So wie Sie es gemacht haben, wenn der maximierende Spieler nur mit Optionen konfrontiert wurde, die -1 wert waren, da -1 kleiner als 0 ist und returnValue auf 0 initialisiert wurde, würde 0 zurückgegeben, obwohl der korrekte Wert -1 ist.