В этой главе обсуждаются методы, которые можно использовать для поиска в таких огромных деревьях. Во‑первых, в ней вначале рассматриваются деревья игры (game trees). На примере игры в крестики‑нолики обсуждаются способы поиска в деревьях игры для нахождения наилучшего возможного хода.
В следующих разделах описываются способы поиска в более общих деревьях решений. Для самых маленьких деревьев, можно использовать метод полного перебора (exhaustive searching) всех возможных решений. Для деревьев большего размера, можно использовать метод ветвей и границ (branch‑and‑bound technique) позволяет найти наилучшее решение без необходимости выполнять поиск по всему дереву.
Для очень больших деревьев нужно использовать эвристический метод или эвристику (heuristic). При этом полученное решение может быть не наилучшим из возможных решений, но оно, тем не менее, лежит достаточно близко к наилучшему, чтобы его можно было использовать. Используя эвристики, можно проводить поиск практически в любых деревьях решений.
В конце этой главы обсуждаются некоторые очень сложные задачи, которые вы можете попытаться решить при помощи метода ветвей и границ или эвристического метода. Многие из этих задач имеют важные применения, и нахождение хороших решений для них крайне необходимо.
Стратегию настольных игр, таких как шахматы, шашки, или крестики‑нолики можно смоделировать при помощи деревьев игры. Если в какой то момент игры существует 30 возможных ходов, то соответствующий узел в дереве игры будет иметь 30 ветвей.
========187
Например, для игры в крестики‑нолики корневой узел соответствует начальной позиции, при которой доска пуста. Первый игрок может поместить крестик в любую из девяти клеток доски. Каждому из этих девяти возможных ходов соответствует выходящая из корня ветвь. Девять узлов на конце эти ветвей соответствуют девяти различным позициям после первого хода игрока.
После того, как первый игрок сделал ход, второй может поставить нолик в любую из оставшихся восьми клеток. Каждому из этих ходов соответствует ветвь, выходящая из узла, соответствующего текущей позиции игры. На рис. 8.1 показан небольшой фрагмент дерева игры в крестики‑нолики.
Как можно увидеть на рис. 8.1, дерево игры в крестики‑нолики растет очень быстро. Если оно продолжит расти таким образом, так что каждый следующий узел в дереве будет иметь на одну ветвь меньше, чем его родитель, то дерево целиком будет иметь 9 * 8 * 7 … * 1 = 362.880 листьев. В дереве будет 362.880 возможных путей, соответствующих 362.800 возможным играм.
В действительности многие из узлов дерева будут отсутствовать, так как соответствующие им ходы запрещены правилами игры. Если игрок, ходивший первым, за три своих хода поставит крестики в верхней левой, верхней средней и верхней правой клетках, то он выиграет и игра закончится. Узел, соответствующий этой позиции, не будет иметь потомков, так как игра завершается на этом шаге. Эта игра показана на рис. 8.2.
После удаления всех невозможных узлов в дереве остается около четверти миллиона листьев. Это все еще очень большое дерево, и поиск его методом полного перебора занимает достаточно много времени. Для более сложных игр, таких как шашки, шахматы или го, деревья игры имеют огромный размер. Если бы во время каждого хода в шахматах игрок имел 16 возможных вариантов, то дерево игры имело бы более триллиона узлов после пяти ходов каждого из игроков. В конце этой главы обсуждается поиск в таких огромных деревьях игры, а следующий раздел посвящен более простому примеру игры в крестики‑нолики.
@Рис. 8.1. Фрагмент дерева игры в крестики‑нолики
========188
@Рис. 8.2. Быстрое окончание игры
Для выполнения поиска в дереве игры, нужно иметь возможность определить вес позиции на доске. Для игры в крестики‑нолики, для первого игрока больший вес имеют позиции, в которых три крестика расположены в ряд, так как при этом первый игрок выигрывает. Вес тех же позиций для второго игрока мал, потому, что в этом случае он проигрывает.
Для каждого игрока, можно присвоить позиции один из четырех весов. Если вес равен 4, то это значит, что игрок в этой позиции выигрывает. Если вес равен 3, то из текущего положения на доске неясно, кто из игроков выиграет в конце концов. Вес, равный 2, означает, что позиция приводит к ничьей. И, наконец, вес, равный 1, означает, что выигрывает противник.
Для поиска дерева методом полного перебора можно использовать минимаксную (minimax) стратегию, при которой делается попытка минимизировать максимальный вес, который может иметь позиция для противника после следующего хода. Это можно сделать, определив максимально возможный вес позиции для противника после каждого из своих возможных ходов, и затем выбрав ход, который дает позицию с минимальным весом для противника.
Подпрограмма BoardValue, приведенная ниже, вычисляет вес позиции на доске, проверяя все возможные ходы. Для каждого хода она рекурсивно вызывает себя, чтобы найти вес, который будет иметь новая позиция для противника. Затем она выбирает ход, при котором вес полученной позиции для противника будет наименьшим.
Для определения веса позиции на доске процедура BoardValue рекурсивно вызывает себя до тех пор, пока не произойдет одно из трех событий. Во‑первых, она может дойти до позиции, в которой игрок выигрывает. В этом случае, она присваивает позиции вес 4, что указывает на выигрыш игрока, совершившего последний ход.
======189
Во‑вторых, процедура BoardValue может найти позицию, в которой ни один из игроков не может совершить следующий ход. Игра при этом заканчивается ничьей, поэтому процедура присваивает этой позиции вес 2.
И наконец, процедура может достигнуть заданной максимальной глубины рекурсии. В этом случае, процедура BoardValue присваивает позиции вес 3, что указывает, что она не может определить победителя. Задание максимальной глубины рекурсии ограничивает время поиска в дереве игры. Это особенно важно для более сложных игр, таких как шахматы, в которых поиск в дереве игры может продолжаться практически вечно. Максимальная глубина поиска также может задавать уровень мастерства программы. Чем дальше вперед программа сможет анализировать ходы, тем лучше она будет играть.
На рис. 8.3 показано дерево игры в крестики‑нолики в конце партии. Ходит игрок, играющий крестиками, и у него есть три возможных хода. Чтобы выбрать наилучший ход, процедура BoardValue рекурсивно проверяет каждый из трех возможных ходов. Первый и третий возможные ходы (левая и правая ветви дерева) приводят к выигрышу противника, поэтому их вес для противника равен 4. Второй возможный ход приводит к ничьей, и его вес для противника равен 2. Процедура BoardValue выбирает этот ход, так как он имеет наименьший вес для противника.
@Рис. 8.3. Нижняя часть дерева игры
Private Sub BoardValue(best_move As Integer, best_value As Integer, pl1 As Integer, pl2 As Integer, Depth As Integer)
Dim pl As Integer
Dim i As Integer
Dim good_i As Integer
Dim good_value As Integer
Dim enemy_i As Integer
Dim enemy_value As Integer
DoEvents ' Не занимать 100% процессорного времени.
' Если глубина рекурсии слишком велика, результат неизвестен.
If Depth >= SkillLevel Then
best_value = VALUE_UNKNOWN
Exit Sub
End If
' Если игра завершается, то результат известен.
pl = Winner()
If pl <> PLAYER_NONE Then
' Преобразовать вес для победителя pl в вес для игрока pl1.
If pl = pl1 Then
best_value = VALUE_WIN
ElseIf pl = pl2 Then
best_value = VALUE_LOSE
Else
best_value = VALUE_DRAW
End If
Exit Sub
End If
' Проверить все допустимые ходы.
good_i = -1
good_value = VALUE_HIGH
For i = 1 To NUM_SQUARES
' Проверить ход, если он разрешен правилами.
If Board(i) = PLAYER_NONE Then
' Найти вес полученного положения для противника.
If ShowTrials Then _
MoveLabel.Caption = _
MoveLabel.Caption & Format$(i)
' Сделать ход.
Board(i) = pl1
BoardValue enemy_i, enemy_value, pl2, pl1, Depth + 1
' Отменить ход.
Board(i) = PLAYER_NONE
If ShowTrials Then _
MoveLabel.Caption = _
Left$(MoveLabel.Caption, Depth)
' Меньше ли этот вес, чем предыдущий.
If enemy_value < good_value Then
good_i = i
good_value = enemy_value
' Если мы выигрываем, то лучшего решения нет,
' поэтому выбирается этот ход.
If good_value <= VALUE_LOSE Then Exit For
End If
End If ' End if Board(i) = PLAYER_NONE ...
Next i
' Преобразовать вес позиции для противника в вес для игрока.
If good_value = VALUE_WIN Then
' Противник выигрывает, мы проиграли.
best_value = VALUE_LOSE
ElseIf enemy_value = VALUE_LOSE Then
' Противник проиграл, мы выиграли.
best_value = VALUE_WIN
Else
' Вес ничьей или неопределенной позиции
' одинаков для обоих игроков.
best_value = good_value
End If
best_move = good_i
End Sub
Программа TicTac использует процедуру BoardValue. Основная часть кода программы обеспечивает взаимодействие с пользователем, рисует доску, позволяет пользователю выбрать ход, задавать опции и так далее.
Если не выбрана команда Show Test Moves (Показывать проверяемые ходы) из меню Options (Опции), то производительность программы будет намного выше. Если выбрана эта опция, то программа выводит каждый анализируемый ход. Постоянное обновление экрана занимает намного больше времени, чем действительный поиск в дереве.
Другие команды в меню Options позволяют вам, выбрать уровень мастерства программы (максимальную глубину рекурсии) и выбрать игру крестиками или ноликами. При высоком уровне мастерства первый ход занимает намного больше времени.
=====192
Подпрограмма BoardValue имеет интересный побочный эффект. Если она находит два одинаково хороших хода, то она выбирает из них первый попавшийся. Иногда это приводит к странному поведению программы. Например, если программа определяет, что при любом своем ходе она проигрывает, то она выбирает первый из них. Иногда этот ход может показаться человеку глупым. Может создаться впечатление, что компьютер выбрал случайный ход и сдается. В какой то степени это действительно так.