mpatric.com

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.

Tic-tac-toe-ception screenshot

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.
Noavatar

Posted Sat 11 Apr 2020 by Michael Patricios

Tags: Development, JavaScript, TypeScript

Post a comment