Wednesday, June 22, 2005


Can Tic-Tac-Toe be thought of as a dynamic programming problem? I think so. Let the board be numbered from the top left corner with numbers 1-9. Let the state vector of variables be a 9x1 vector such that:

If your symbol is in square i, a 1 is in the i'th row of vector x
If no symbol is in square i, a 0 is in the i'th row of vector x
If your opponent's symbol is in square i, a -1 is in the ith row of vector x

Now, x(0) is simply <0,0....>. Let the choice vector, u, be such that if you want to put your symbol in the j'th position, there is a 1 in the j'th column of a vector of zeroes. Then the transition function is simply:

x(s+1) = x(s) + u(s) + p(s)

the p(s) is what I am not sure about. It would be your opponent's play... as a baseline, this could be just a random placement of a -1 in an open row in a vector of zeroes, so that you are playing against an opponent with no strategy.

I think this would work... but I'm not sure. And I am not even trying to come up with how to describe the function which a player would wish to optimize or how this would be done, just if the game could be thought of as a DP problem.


Post a Comment

<< Home