Дерево игры и минимакс

Дерево игры — корневое дерево, где:

• Корень — стартовая позиция S.
• Чётная глубина (0, 2, 4, ...) — ход MAX (Петя, Первый).
• Нечётная глубина (1, 3, 5, ...) — ход MIN (Вася, Второй).
• Листья — терминальные позиции (цель достигнута).

Правило

• На уровне MAX — берём максимум среди детей.
• На уровне MIN — берём минимум среди детей.

Альфа-бета отсечение

• α — лучший результат для MAX на данном пути.
• β — лучший результат для MIN на данном пути.
• Если α ≥ β — поддерево можно отсечь.