## Tic-tac-toe & chess

### Tic-tac-toe (or noughts & crosses)

The game starts by P1 clicking on one of the cells in the 3 × 3 grid

P1 (Human) will play as X (crosses)

P2 (Human) will play as O (noughts)

Human versus human

1. Tic-tac-toe is a 2-player sequential zero-sum game with perfect information:
1. This game is played by exactly 2 players P1 and P2 (2-player);
2. P1 and P2 take turns to move as opposed to moving simultaneously (sequential);
3. When a payoff value is assigned to each player in a game-final position (+1 for a win, -1 for a loss, and 0 for a draw), the sum of payoffs for P1 and P2 will be equal to zero (zero-sum)
4. Both P1 and P2 know the results of all previous moves by P1 and P2 (perfect information

1. A game tree is the search tree for a game
2. Each node in the game tree represents a legal position in that game
3. The root node (with no parents) represents the game-initial position and MAX (P1 or X (crosses)) moves first
4. As we expand this game tree, MAX (P1) and MIN (P2) take turns to move, until we arrive at the game-final positions
5. The leaf nodes (with no children) represent the game-final positions
6. A payoff value is assigned to each player at the game-final position: +1 for a win, −1 for a loss, 0 for a draw)

1. Tic-tac-toe is a solved game:
2. Assuming perfect play from both P1 and P2, we can correctly predict the outcome of this game (win, lose, or draw)
3. More specifically, assuming perfect play from both P1 and P2, the outcome will be a forced draw

### Chess

P1 (Human) will play as White
P1's (or White's) most recent moves are highlighted in dark red

P2 (AI) will play as Black
P2's (or Black's) most recent moves are highlighted in cornflower blue

Suggested moves will be highlighted in teal

No check, checkmate, or draw.

Human versus AI

Adapted from Zhang Zeyu's GitHub source code for chess-playing AI

1. Like tic-tac-toe, chess is a 2-player sequential zero-sum game with perfect information
2. However, chess is a more complex game than tic-tac-toe
3. Variants of chess on a smaller board and with fewer pieces have been solved
4. However, chess itself has not been solved

1. Combinatorial game theory allows for the complexity of different games to be measured:
2. State space complexity — the number of legal game positions reachable from the initial state of the game s0;
3. Game tree complexity — the number of leaf nodes in a game tree rooted at the initial state s0 as the root node;
4. Branching factor — the average number of legal moves that you can make from a given position si

Tic-tac-toe Chess
Board size 9 (3 × 3) 64 (8 × 8)
State space complexity 103 1046
Game tree complexity 105 10123
Branching factor 4 35