It has four major sections. (1) We build up game positions as shown previously, through move # 3. We make sure to check that a new position is not a permutation of one already known. Also we move from the center out, so that if there are two identical positions, we keep the one in which the center was X's first move. (2) We then do move # 4, continuing as before, but also checking to be sure that if X threatens to win, we block him. (3) For moves # 5-9 we check for several things in turn:
• is the position already won
• can the player win
• can the opponent win
• can the player make a "double threat"---and win on next turn.
• can the opponent make a double threat---then we block.
The last part organizes the output. All the results from both the intermediate stages and either won or filled (drawn) boards are stored in a dictionary labeled mD, keyed by the move list for that position (1-based indexing) For example, 27853149 means X took square 2, then O took square 7, and so on. We also store the logic for the game in another dictionary labeled rD, so for each position, we can say what the reason was for us to make the last move. We filter for boards which terminate a chain by looking for those with no "daughters"---that is, there are no keys in the dictionary which begin with this key.
The positions could be analyzed in a variety of ways. Here are two:
(1) If you've played you know that it is difficult to win if you do not go first. But it is not impossible! There are six winning games for O. Here is my favorite:
We see that X took the side position, then O the corner, then X the opposing corner (273). It looks pretty good for X! O has to block on the next move. But now O threatens and X must block, and finally O has an unanswerable double threat.
The other question I looked at was: does X always win if he takes the center first? The answer is surprising. X wins only 4/10. The others are draws. Here is one of the wins:
Here is the code: