Chapter 5 - Tic Tac Toe - The Computer loses.

[soham23]

The page says the computer won't get anything worse than a draw. It does, though. It doesn't display "O wins" instead, it displays "Draw".

[AnimeshSinha1309]

Yeah, Replicated the result, O(2,2) - X(3,3) - O(1,1) - X(2,3) - O (1,3) - The Computer Lost, Two threats it cannot deal with - X(1,2) - O(3,1), The Human Wins, but the computer says draw.

I guess this is an issue with the evaluation function, will try to solve the issue. If someone can tell where the function that decides if a game was won, drawn or lost is placed, please do. Any help would be great.

[GaurangTandon]

Found the culprit:

https://github.com/aimacode/aima-javascript/blob/3cf3bae09563fc19f49d02a878e037e6866ac566/5-Adversarial-Search/game.js#L37

It is never checking for the case for O wins. A simple fix would be to do tree.board.gameState == 2 ? "X Wins" : tree.board.gameState == 1 ? "O wins" : "Draw".

Although this is just half the issue. I personally would have expected:

if(tree.board.gameState == 1){
    debugLog("O should not be able to win");
}

somewhere at the top of the reset function's return value.

This is just half the issue, the other half is fixing the actual tic-tac-toe machine that plays the game sub-optimally.

Old version:

Seems the file and line number that posts the message is this @AnimeshSinha1309

https://github.com/aimacode/aima-javascript/blob/master/5-Adversarial-Search/draw.js#L123

It seems board.gameState is never being set to 1. The getter for gameState is here:

https://github.com/aimacode/aima-javascript/blob/3cf3bae09563fc19f49d02a878e037e6866ac566/5-Adversarial-Search/tree.js#L35

I would expect the getter to return 1 considering that the three tiles are being checked correctly for the case case:

https://github.com/aimacode/aima-javascript/blob/3cf3bae09563fc19f49d02a878e037e6866ac566/5-Adversarial-Search/tree.js#L44

[AnimeshSinha1309]

I don't think we should do this, I agree that that would fix the issue that I says game draw. But then that should never be possible if the reset of the decision tree is working.

[GaurangTandon]

Yes, I intended the fix to be temporary only, until the decision tree is back up again. As I said above, I personally would have expected a separate error check for tree.board.gameState == 1.

[AnimeshSinha1309]

Sorry, the previous hunch seems wrong. The tree when constructed fixes its leaf node and assigns then the apt values, so its not needed again. But the lines of code that are breaking it are: https://github.com/aimacode/aima-javascript/blob/3cf3bae09563fc19f49d02a878e037e6866ac566/5-Adversarial-Search/tree.js#L142-L144. Should this not be:

if (this.board.turn == 1 && this._value >= beta) return this._value; // Human - Maximizing Agent
if (this.board.turn != 1 && this._value <= alpha) return this._value; // Computer - Minimizing Agent

In any case, removing the alpha-beta pruning segment makes the whole thing work.

[AnimeshSinha1309]

I have put together a solution. It works perfectly, please review and tell me if you can still beat the computer. Here is how the first moves of the game go now.

[soham23]

Nope, I couldn't find a way to beat this one: https://github.com/AnimeshSinha1309/AimaJavascript/tree/master/5-Adversarial-Search