Game Search
2-player game as a search problem
| 元素 | 描述 |
|---|---|
| Initial state | initial board configuration, which player’s move |
| Successor function | returns a list of (move,state) pairs, each indicating a legal move and the resulting state |
| Terminal test | determine when game is over |
| Utility function | a value for the terminal state, e.g. +1 for win, 0 for draw, -1 for loss. |
Minimax Algorithm
- Generate entire game tree, down to leaves.
- Evaluate each leaf (terminal state) using utility function.
- Values are backed up through the tree
- MAX-level: prefer max value (i.e. you)
- MIN-level: prefer min value (i.e. opponent)
- At the root, choose the series of moves which leads to the terminal state w/ highest value.
- Make the perfect decision
- Could use Depth-First Search, but not Bidirectional Search since it is BFS(level by level會佔用太多資源)
Max先選A1，接著Min選A11
Alpha-beta pruning
- prune branches that do not affect the final decision.
- exploiting the fact of an adversary
- If a position is probably bad
- If the adversary can force a bad position
- If
mis better thannfor Player, we will never get tonin play. - 參考電腦下棋的關鍵： Min-Max 對局搜尋與 Alpha-Beta 修剪算法
Cutting Off Search
Cutoff-test function
- Depth limit: a preset limit
- Iterative-deepening: when time is up, return the move selected by the deepest search
- Error-prone because of limited search