Game Tree; Strategies

Содержание и основные понятия

Back to the table of contents
Alterna · Chapter 18 · page 18.2
Game Tree; Strategies
Minimax + Alpha Beta Visualizer for Small S.
Each player's move is a tree node. Each leaf is a terminal position (win/win). The minimix from the bottom up calculates the optimal move. Alpha-beta cuts off branches that do not affect the result.
GEF
PIF
EEG No.21.23
01
Game Tree
Game Tree
- a root tree where:
The root is the starting point.
An even depth (0, 2, 4...) is the first step.
The centre at odd depths (1, 3, 5, ...) is a move by the Second.
Leaves are terminal items (win/win), evaluation +1/ -1.
02
Minimax algorithm
Let's go upstairs:
At level
max
(First picks)
maximum
among the children.
At level
min
We'll take it.
minimum
among the children.
Alpha Beta
If α (best for max) ≥ β (better for min), the support can be cut off, it will not affect the result. This accelerates the minimax by a factor of 2 to 10 in practice.
03
Minimax Visualizer
Set the terminal values of leaves - see the marks max/min
🌳
Minimax: tree for N=3 (deep 3)
Foliage values (8 unit, decimal place)