Iv. Динамические структуры данных

X
 

O

x


O
 
X
 

O
X
X
O
 
X
 
X
O
 
X X

X O
 
X
 

O

X
 
X
O
X X 

O X 
X
 

O X
X

-3
-2 
⎯ 
+ 
+
-3 
-3
-2 
-3
-4
-4
-3 
-4

---

Программирование на языке Си
©
 К. Поляков, 1995-2009 
http://kpolyakov.narod.ru
31
Обозначим игрока, который ходит в корневой позиции (в данном случае – нолики) знаком 
«плюс», а его соперника – знаком «минус». Попытаемся найти лучший ход для игрока «плюс» в 
этой позиции. Пусть все варианты следующих ходов были оценены для игрока «плюс». Он 
должен выбрать такой, в котором оценка максимальная для него.
С другой стороны, как только игрок «плюс» сделает свой ход, игрок «минус» из всех воз-
можных ходов сделает такой, чтобы его оценка с позиции игрока «плюс» была минимальной. 
Поэтому значение минусового узла для игрока «плюс» равно минимальному из значений сыно-
вей этого узла. Это означает, что на каждом шаге соперники делают наилучшие возможные 
ходы. 
Для того, чтобы выбрать оптимальный ход в корне дерева, надо оценить позицию в его 
листьях. После этого каждому плюсовому узлу присваивается максимальное из значений его 
сыновей, а каждому минусовому – минимальное. Такой метод называется методом минимак-
са, так как по мере продвижения вверх используются попеременно функции максимума и ми-
нимума. Общая идея метода состоит в том, чтобы выбрать лучший ход на случай худших (для 
нас) действий противника. Таким образом, лучшим для ноликов в корневой позиции будет ход 
в угол. 

---

IV. Динамические структуры данных
©
 К. Поляков, 1995-2009 
http://kpolyakov.narod.ru
32