Wednesday, December 04, 2002
( 2:35 PM ) Matt
A game is "solved" when the best play can always be determined. For example, tic-tac-toe is solved. If both players play perfectly, then it always results in a cat's game. A play is considered perfect if there is no other play which can result in a better result. The only results that matter are win, loss, or tie. The margin of victory is irrelevant.
Let's look at tic-tac-toe a little closer. What is the "perfect" first move? Is it in the centre? A corner? A side? The answer is, all of them are perfect. For any first play that X makes, there is no play that O can make which guarantees a win. Let's say that X plays in the corner. Are all of O's moves perfect? No. Because if O plays in the opposite corner, then X can play in one of the remaining corners to guarantee a win for X.
All perfect play games are cat's games, but are all cat's games perfect? No. Say X has two of the top three spaces. O needs to take the remaining space to prevent black's win, but say O plays elsewhere, and X does too on his turn. Now O takes the space, blocking X's line. If this game ends in a cat's game, it is not perfect because X had the opportunity to win, but did not take it.
How many perfect games of tic-tac-toe are there? I don't know, but it might be fun to try to figure it out. People have counted numbers of tic-tac-toe games, but I haven't seen anyone count the number of perfect games.
Okonomigo will have a feature which allows you to explore the game tree. Perhaps it would be nice to use it to explore the tic-tac-toe game tree first. No one has found a way to determine perfect play for go, but examining tic-tac-toe might give some insight into arranging branches on a level of prefectness. Maybe something akin to the probability that the sequence is perfect.# -
Comments: Post a Comment