This is for our Scratch Tic Tac Toe game.
If X moves in a corner:
For this we can respond with the opposite corner, a same side corner, a neighboring side, an opposite side, or the middle.
Opposite corner
X.. X.. X.. X.. X.X
... ... ... O.. O.. Forced win
... ..O X.O X.O X.OSame side corner
X.. X.O X.O X.O X.O
... ... ... .O. .O. Forced win
... ... ..X ..X X.X
Neighboring side
X.. XO. XO. XO. XO.
... ... ... O.. O.. Forced win
... ... X.. X.. X.X
Opposite side
X.. X.. X.. X.. X..
... ..O ..O O.O OXO Forced win
... ... X.. X.. X..
Middle
X.. X.. X..
... .O. .O. No way to force a win. Try it yourself
... ... ...
If X moves in the center:
With this your two choices are to respond with a side or with a corner.
Side
... .O. .O. OO. OOX
.X. .X. .X. .X. .X. Forced win
... ... ..X ..X ..X
Corner
... O.. O..
.X. .X. .X. No way to force a win. Try it yourself
... ... ...
If X moves on a side:
Your choices are to respond with a neighboring corner, a neighboring side, the center, the opposite side, or an opposite corner.
Neighboring corner
.X. OX. OX.
... ... ... No way to force a win. Try it yourself
... ... ...
Neighboring side
.X. .X. .X.
... O.. O.. No way to force a win. Try it yourself
... ... ...
Center
.X. .X. .X.
... .O. .O. No way to force a win. Try it yourself
... ... ...
Opposite side
.X. .X. .X.
... ... ... No way to force a win. Try it yourself
... .O. .O.
Opposite corner
.X. .X. XX. XXO XXO
... ... ... ... .X. Forced win
... O.. O.. O.. O..
These are for first move force-wins. Please comment if you see a mistake.
Yes, I think you're right (and my last comment was wrong.)
ReplyDeleteThere are some subtle issues with exactly how to code it in a clean way, without handling hundreds of cases separately. I'm close to getting this coded but I'll need some intelligent correctness checking. Unfortunately it is impossible to make a program to check correctness, because it is impossible to check the correctness checker.
See if you can force a win on version 6:
ReplyDeletehttp://scratch.mit.edu/projects/kramwod/954465
By the way, this branching list you've made is called a game tree:
ReplyDeletehttp://en.wikipedia.org/wiki/Game_tree
In math games, game theory and game trees don't refer to games, but often the simplest examples are isomorphic to games, hence the name.