Game Tree

• A reasonable way to describe the rest of the game is a game tree.
• You start at the root (the current position), and expand all possible moves.
• Then from those, you expand all the other possible moves.
• Each level down is called a ply.
• With tic tac toe, you can expand the full tree. We could probably do it on the board.
• With chess, even with special hardware, you can't generally expand more than 18 moves ahead.
• It's exponential in the depth of the tree. The base is the number of moves.