This is not a problem for a beginner. Here's how I would approach it.
Build a tree of positions. Each of the cells in a position has three possible values: X, O, or empty. The root position is an empty grid. If X goes first, there are 9 possible moves (I'm assuming you don't have to bother with rotations and reflections to eliminate "identical" positions).
Now we have the second level of the tree (the one below the starting position), which has 9 positions. Each of those positions has 8 moves for O, resulting in 72 positions at the third level. The fourth level will have 72x7=504 positions, and the fifth level will have 504x6=3024 positions.
Once we reach the fifth level, X will win some games. When a game has been won, you no longer generate moves from that position, which means that the ninth level of the tree will have less than 9! positions.
If you number each position, you can follow a game through the tree and display its "number" and the moves up to that point. Some positions can be reached by different move orders, so you need to record the moves to display them.
When a game has been won, record the winning move against the parent node in the tree so that you can display it if that position is reached. This gets complicated, however, because a winning line can begin on a player's
previous move. Take this position, with X to move:
XO-
O--
X--
If X plays in the center, it's a winning line, no matter what O does:
XO-
OX-
X--
In the tree, O has 4 possible moves before X wins. Sometimes the win comes from playing in the upper right, sometimes in the lower right, and on one of O's moves, X will even have a choice! But the point is that
any O move allows X to win. When this occurs, the
previous position (the first position above) should also show the winning move. This is how databases of chess endings are created, which allows a program to play perfectly once a position in the database is reached.
Submit an article or tip