2.9 Game Playing (BT104CO)
1. Formal Definition of a Game
A game is formally defined as a search problem using these six components:
$S_0$
Initial State: How the game starts (e.g., an empty board).
$Player(s)$
Turn-Taker: Defines which player has the move in state $s$.
$Actions(s)$
Legal Moves: Returns the set of valid actions in state $s$.
$Result(s, a)$
Transition: Defines the state resulting from move $a$ in state $s$.
$Terminal\_Test(s)$
End-Check: True when the game is over.
$Utility(s, p)$
Outcome Score: The numeric value for player $p$ at the end.
2. The Minimax Algorithm
The core strategy for games is the Minimax Search. In a two-player game, we name the players MAX (the AI) and MIN (the opponent).
MAX Player
Tries to maximize its utility. Always wants the highest possible score.
MIN Player
Tries to minimize MAX's utility. Always chooses the lowest score for the AI.
1. Generate the whole game tree down to terminal states.
2. Apply Utility Function to the terminal states.
3. Back up values: MIN nodes choose the minimum child; MAX nodes choose the maximum child.
3. Alpha-Beta Pruning (Optimization)
Since the search tree grows exponentially ($b^d$), we use Alpha-Beta Pruning to ignore branches that cannot affect the final decision.
Alpha ($\alpha$)
The highest-value choice found so far for MAX.
Beta ($\beta$)
The lowest-value choice found so far for MIN.
Pruning Rule: If at any point $\alpha \ge \beta$, we stop searching that branch. A rational opponent would never allow the game to move into that branch.
4. Real-Time Games (Heuristic Minimax)
Cutoff Test: Stop searching at a certain depth (e.g., 5 moves ahead) rather than the end.
Evaluation Function ($Eval$): "Guess" how good a state is (e.g., material value in Chess: Queen=9, Pawn=1).
5. Game Environment Dimensions
| Property | Typical Value | Why? |
|---|---|---|
| Observability | Fully Observable | Both players see the whole board. |
| Determinism | Deterministic | No luck or "dice" (usually). |
| Agents | Multiagent | At least two players involved. |
| Relation | Competitive | One's gain is the other's loss. |