TTT Competitor

Here's a guide for one way of creating a perfect TTT competitor...

We'll be creating a class called BoardNode, which will contain all the information about one node in the game's game-tree.

Here's the new BoardNode's __init__():

class BoardNode:
    def __init__(self,layout):
        self.layout = layout
        self.endState = None # if this is a terminal board, endState == 'x' or 'o' for wins, or 'd' for draw, else None if this board is not final
        self.children = [] # all nodes that can be reached with a single move

        self.best_move  # cell position (0-8) of the best move from this layout, or -1 if this is a final layout
        self.moves_to_end  # how many moves until the end of the game, if played perfectly.  0 if this is a final layout
        self.final_state   # expected final state ('x' if 'x' wins, 'o' if 'o' wins, else 'd' for a draw)

 

• You may add any other properties that you feel you need.

• Let's call your program file: ttt.py

• Your program will be called with two command-line arguments, a filename and a 9-character board layout:   for instance:  $ ./ttt.py  answer.txt x_ox_o___

• Your program should print, and also output to the answer file, the following answers (if the layout above is given):

6
best move is lower-left
x wins in 1 move

The first output line contains the position for the next move and the other two are for human eyes.

Basic recursive loop:

• Create a BoardNode with the initial board state given on the command-line.

• Initially, when creating a BoardNode, only its layout is known.

• Immediately, check if this is a win, loss or draw.  If so, fill in the other BoardNode properties.

• If not, enumerate all the children of this node (next immediate moves) and create those childrens' nodes (recursively).

• Then, look through your children, because they will have completed all of their other properties, so that you can then choose the best move amongst them...

Best move choice:

• If this layout is a final board, there's no choice

• else, if any of this board's children's final_state is a win for you, choose moving to the child with the smallest moves_to_end.  If more than one, choose randomly.

• else, if any child's final_state is a draw, choose one of them randomly (they will all have the same moves_to_end)

• else, choose the child with the largest moves_to_end.  If more than one, choose randomly.

Timing:  You are allowed to cheat if given an empty board and you have to make the first move (any first move will lead to a draw in 9 moves, if played perfectly by both sides).  Ther are only 3 distinctly different moves: corner, edge and center.  Choose one of the 3 types, and if choosing corner or edge, choose a random one of those. After that, however, your program should deliver an answer in under 2 seconds.

Testing: Now you can really play with tictactoe against your creation.  It should never lose.  Make it so.