Quite a while back there was a xkcd post showing the complete map of optimal tic-tac-toe moves. Ever since seeing it I've wanted to create an interactive version of this that would show a visualisation of the game tree for each possible move, and here it is! You can try it online or check out the source code repository. It runs in a web browser and the code is TypeScript.
Some notes:
- A full game tree is generated up to 5 moves ahead and then some alpha-beta pruning is applied going deeper to decrease the number of further nodes that need to be evaluated as it's difficult to draw more than 5 moves ahead on the canvas
- As the game tree is evaluated to completion, no player will ever win if you push the 'play best move' for each move as they'll both play perfectly; for this reason the 'best' move is chosen as the one that could participate in the most three-in-a-rows; a small bit of randomness is added so that it doesn't always play the same move if there are multiple moves of equal rank.
Post a comment