Louis Abraham's Home Page

submited by

Style Pass

2024-06-11 14:30:03

This morning, I came accross Cameron Sun’s Probabilistic Tic-Tac-Toe on HN. However, the comments were disappointing, with people proposing probabilistic models, linear programming, minimax algorithms, and heuristic evaluations to develop AI approaches for the game. In this post, I’ll present an exact solution.

You should definitely try it but as a reminder, probabilistic Tic-Tac-Toe is like tic-tac-toe but each cell is given a probability distribution. For example, if you play the center cell in the grid below, you have a 30% chance of marking it with your symbol, a 15% chance of not doing anything, and a 55% chance of marking it with the opponent’s symbol.

If one ignores the probability of not marking a cell, the game is an obvious example of dynamic programming. You have less than $3 ^ 9 = 19683$ states (the exact number is 5478) and one can compute the probability of the “cross” player winning in each state with the following pseudo-code:

The above pseudo-code is not enough to solve the game because of the possibility of doing nothing. If we were to simply add neutral(c) * value(state, turn) to the above pseudo-code, we would end up with an infinite loop.