Улучшение поиска в дереве игры

Если бы для поиска в дереве игры мы располагали только минимаксной стратегией, то выполнить поиск в больших деревьях было бы очень сложно. Такие игры, как шахматы, настолько сложны, что программа может провести поиск всего лишь на нескольких уровнях дерева. К счастью, существуют несколько приемов, которые можно использовать для поиска в больших деревьях игры.

@Рис. 8.4. Нумерация клеток доски игры в крестики‑нолики

======193

@Рис. 8.5. Программа игры в крестики‑нолики сдается

Предварительное вычисление начальных ходов

Во‑первых, в программе могут быть записаны начальные ходы, выбранные экспертами. Можно решить, что программа игры в крестики‑нолики должна делать первый ход в центральную клетку. Это определяет первую ветвь дерева игры, поэтому программа может игнорировать все пути, не проходящие через первую ветвь. Это уменьшает дерево игры в крестики‑нолики в 9 раз.

Фактически, программе не нужно выполнять поиск в дереве до того, пока противник не сделает свой ход. В этот момент и компьютер и противник выбрали каждый свою ветвь, поэтому оставшееся дерево станет намного меньше, и будет содержать менее чем 7! = 5040 путей. Просчитав заранее всего один ход, можно уменьшить размер дерева игры от четверти миллиона до менее чем 5040 путей.

Аналогично, можно записать ответы на первые ходы, если противник ходит первым. Есть девять вариантов первого хода, следовательно, нужно записать девять ответных ходов. При этом программе не нужно поводить поиск по дереву, пока противник не сделает два хода, а компьютер — один. Тогда дерево игры будет содержать менее чем 6! = 720 путей. Записано всего девять ходов, а размер дерева при этом уменьшается очень сильно. Это еще один пример пространственно‑временного компромисса. Использование большего количества памяти уменьшает время, необходимое для поиска в дереве игры.

Программа TicTac2 использует 10 записанных ходов. Задайте 9 уровень мастерства, и пусть программа делает первый ход. Затем задайте те же опции в программе TicTac. Вы увидите громадную разницу в скорости работы этих двух программ.

Коммерческие программы игры в шахматы также начинают с записанных ходов и ответов, рекомендованных гроссмейстерами. Такие программы могут делать первые ходы очень быстро. После того, как программа исчерпает все записанные заранее ходы, она начнет делать ходы намного медленнее.

Определение важных позиций

Другой способ улучшения поиска в дереве игры состоит в том, чтобы определять важные позиции. Если программа распознает одну из этих позиций, она может выполнить определенные действия или изменить способ поиска в дереве игры.

========194

Во время игры в шахматы игроки часто располагают фигура так, чтобы они защищали другие фигуры. Если противник берет фигуру, то игрок берет фигуру противника взамен. Часто такое взятие позволяет противнику в свою очередь взять другую фигуру, что приводит к серии обменов.

Некоторые программы находят возможные последовательностей обменов. Если программа распознает возможность обмена, она на время изменяет максимальную глубину, на которую она просматривает дерево, чтобы проследить до конца цепочку обменов. Это позволяет программе решить, стоит ли идти на обмен. После обмена фигур их количество также уменьшается, поэтому поиск в дереве игры становится в будущем более простым.

Некоторые шахматные программы также отслеживают рокировки, ходы, при которых под боем оказывается сразу несколько фигур, шах или нападение на ферзя и так далее.