5. Game Tree¶
Reference: Game playing basics
5.1. Basic concept¶
- The game tree search here focuses on two-player, perfect-information games.
- Two-players, take turns to play.
- Any player know history moves (no possibility).
- A game tree is a representation of all possible plays of a game.
- The root node represents the initial state \(s\).
- Leaf nodes represent goal states.
- Each path from the root \(s\) to a leaf nodes represents a complete game.
5.2. Game Tree¶
- A game tree is a tree whose nodes (both inner nodes and leaf nodes) are either of type “Max” or “Min”
- All nodes at the same level of a game tree are of the same type.
- Max nodes and Min nodes alternate between any two consecutive levels (One layer all OR-nodes, one layer all AND-nodes).
- Graphic notation and summary:
- □ = player 1 = Max player = own view = Max node = OR node
- O = player 2 = Min player = adversarial view = Min node = AND node
- Players play optimum.
- Use minimax algorithm to search.
5.3. Example: Tic-tac-toe¶
- Can define an evaluation function \(f\) (assume player 1 => X):
- For the current state, place all X in the spaces and count three X marks to be \(a\).
- Place all O in the spaces and count three O marks to be \(b\).
- Then \(f=a-b\)
- For OR search, choose MAX \(f\). For AND search, choose MIN \(f\).
5.4. Game Playing Introduction¶
- From any node \(s\) in tree \(T\), decide a \(T^+\) tree (subtree of \(T\)) for player Max and \(T^-\) tree for player Min.
- Two strategies \(T^+\), \(T^-\), of Max and Min respectively, share at each level either one or no edge!!!.
- The intersection of two strategies \(T^+\), \(T^-\), defines the leaf (\(T^+ \spcap T^−\)), which corresponds to the final position of the game.
- Important property
\[\min\limits_{T^-} \max\limits_{T^+}status(T^+ \cap T^-) = status(s) = \max\limits_{T^+} \min\limits_{T^-}status(T^+ \cap T^-)\]
