TwiddleLab / Artificial Intelligence / Search, Games and Plans

Game Trees

Lesson 4 of 11 · 6 min · Free, no account needed

What you will learn

• A game tree shows every way a game can go: the position at the top (the root), each move a branch, each finished game an ending (a leaf).
• The number of moves from a position is the branching factor. How many moves deep the tree goes is its depth.
• Trees grow fast: about b x b x ... x b, or b^d positions after d moves.

Start the lesson

How the lesson goes

1. X to move. Three squares left. Where should X play?

   Make a bet. Tap a free square.

2. Grow every possible future.

   Tap the + under a position to see every move from it. Keep going until every game is over.

3. Colour every ending: X wins, O wins or draw.

   Tap an ending to change its colour. Look for three in a row.

   O already has top right and bottom left. Whenever the middle is still free on O's turn, O takes it and wins on that diagonal. Every other ending is a line for X.

4. Now pick X's move, reading the tree.

   Choose the branch where O can never win.

   If X takes the middle, X blocks O's diagonal and makes two threats at once, bottom middle and bottom right. O can block only one, so both endings are X wins. The other two moves leave the middle to O.

5. This picture is called a game tree.

   The position at the top is the root. Each move is a branch. A finished game is a leaf. The number of moves from a position is the branching factor, and the number of moves down is the depth.

6. How fast do trees grow? Find the fewest empty squares that give more than 1000 games.

   With n empty squares, X has n choices, then O has n - 1, then n - 2... At most n x (n - 1) x ... x 1 games. In math that is n! (n factorial).

   6! = 720 and 7! = 5,040. Each extra empty square multiplies the count. From an empty board, 9! = 362,880 is an upper bound; games that end early make the real number 255,168.

7. Chess has about 35 moves in a typical position. How many positions are 4 moves ahead?

   Put your pin on the scale. Each step to the right is 10 times bigger.

   With branching factor b and depth d, a tree has about b^d positions at the bottom. 35^4 is 1.5 million; 35^8 is already over 2 trillion.

8. Game: spot the safe move in three new positions.

   X to move each time. Tap the move with no orange ending under it. Three lives.

9. Place each game by the size of its tree.

   Roughly how many different games can be played? Drag each game onto the scale.

   These are rough sizes of the game trees: about 10^5 games for tic-tac-toe, 10^21 for Connect Four, 10^123 for chess and 10^360 for Go. A bot can read all of tic-tac-toe, but not chess or Go. That is the next problem.

Previous lesson: Heuristics: A* Finds the Way · Next lesson: Minimax · Part of the course: Search, Games and Plans

Lessons are interactive and need JavaScript. Turn it on to play them.