As a practice project I made a Tic-Tac-Toe game on JSFiddle (because there aren't enough already, right?) and I progressed into adding an unbeatable AI. For the most part it works, but there are some combinations (e.g. setting X into fields 5, 9, 3 or into fields 3, 7, 9) that lead to the computer not calculating the optimal move properly.
The project on JSFiddle: https://jsfiddle.net/jd8x0vjz/
And the relevant function starting at line 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
}
I think the last two if-clauses are causing these problems, since the computer does calculate the proper values (as observable in the debugger), but they're sometimes overwritten, but I am not sure if this really is the root of the problem. Any help or tips would be appreciated!
EDIT: Problem solved! Look for my answer below in case it is not the first one.
The idea of the default value of returnValue being wrong definitely sent me down the right path; it didn't make everything magically work (would've been too nice if it did), but it did give me the right nudge. Since we don't want to return any value if nothing is calculated, I adjusted the evaluateMove function as following:
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
}
Now the default is null and as such should not throw the calculations off. What it did throw off however was the first block of checks, so I adjusted it to simply return the current status should the game have ended, instead of doing any elaborate checks. However that threw off the results because I'm using inversed default values in the two methods, so I had to adjust evaluateGameStatus too. Now if the human won it returns -1 instead of 1, and if the computer won it returns 1 instead of -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
}
}
I had to do the same adjustmends for the checkGameEnd function, obviously.
You'll notice that I changed the check for draws too. That is because, for some reason, the old check for count == maxMoves did not work anymore, so I changed to a loop which simply checks whether there is any empty field at all, and to return 2 if there is, and 0 if there is not (it returns 0 here because at this point it has run through all the checks: X hasn't won, O hasn't won, and there are no open slots left, so the game must be a draw).
Working project can now be found here:
https://jsfiddle.net/h5zwzkm7/