Game Tree and Minimax

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

Back to the table of contents
Alterna · Chapter 19 · page 19.2
Game Tree and Minimax
Algorithm minimax with alpha-beta cut, animated visualization of the tree.
Game Tree
- every knot is a position, every child is a possible move.
Minimax
===Mix===MaX takes the maximum, MIN is the minimum.
Alpha Beta
Cuts out branches that have no effect on the result.
GEF
PIF
EGE No. 21
01
Game Tree
Game Tree
- a root tree where:
The root
- Start position S.
Elevated depth
(0, 2, 4, ...)
MAX (Petya, First)
.
Odd depth
(1, 3, 5, ...)
MIN (Vase, Second)
.
Leaves
- Terminal positions (target achieved).
02
Minimax algorithm
Rule
At level
MAX
- We'll take it.
maximum
among the children.
At level
MIN
- We'll take it.
minimum
among the children.
Alpha-beta cut-off
α
Best result for MAX is on the way.
β
The best result for MIN is on the way.
If
α ≥ β
- you can cut it off.
03
Minimax Visualizer
Enter 8 values of leaves -- you see the animation of the calculation from the bottom up.
🌳
Minimax: Deep Tree 3
Leaves (8 decimal places)
04
Game Tree Generator
Choose the type of game - the system will build a tree and show L/W markings
🎮
Game Tree Designer
Game Type
Start S
Purpose (≤ 0 or ≥N)
Max depth
Press "Build Tree"
Legend
▪ MAX (Feather)
·
▪ MIN (Vase)
·
▪ W is the winning
·
▪ L is a loser
🤖
Game: Nil Crosses v. I. (minimex)
And the EI uses the minimax algorithm to read all possible moves to depth and choose the optimal. Try to win!
Your move (X)
05
Alpha Beta: Comparison
Find out how many knots the alpha-beta vs is cutting off full minimax.
✂️
Alpha-beta vs Minimax: knots and cuts
Deepness of wood
The branches of each knot
Minimax (without cut-off)
Press Start
Alpha-beta (with cut-off)
Press Start
06
Mini-test: Minimax and trees
5 questions on Minimax and Game Trees
XP: 0
🎯
Test: Minimax
5 questions on Minimax and Game Trees