Например, запустим программу TicTac с третьим уровнем мастерства. Перенумеруем клетки так, как показано на рис. 8.4. Сделаем первых ход в клетку 6. Программа выберет клетку 1. Выберем клетку 3, программа ответит ходом на клетку 9. Теперь, если занять клетку 5, то наступает выигрыш, если следующим ходом пойти на клетку 4 или 7.
Компьютер теперь может просмотреть дерево игры до конца и убедиться в своем проигрыше. В такой ситуации человек попытался бы заблокировать один из выигрышных ходов, либо поместить два нолика в ряд, чтобы попытаться выиграть на следующем ходу. В более сложной игре, такой как шахматы, человек также может выбрать одну из этих стратегий, в надежде на то, что соперник не увидит пути к победе. Соперник может ошибиться, давая игроку тем самым шанс на победу.
Программа же считает, что противник играет безошибочно и также знает о своем выигрыше. Так как ни один ход не приводит к победе, то программа выбирает первый попавшийся ход, в данном случае занимает клетку 2. Этот ход кажется глупым, так как он не блокирует ни одного из возможных выигрышных ходов, и не делает попытку выиграть на следующем ходу. При этом кажется, что компьютер сдается. Эта игра показана на рис. 8.5.
Один из способов предотвращения такого поведения состоит в том, чтобы задать больше различных весов позиций. В программе TicTac все проигрышные позиции имеют одинаковый вес. Можно присвоить позиции, в которой проигрыш происходит за два хода, больший вес, чем позиции, в которой проигрыш наступает на следующем ходу. Тогда программа сможет выбирать ходы, которые приведут к затягиванию игры. Также можно присваивать больший вес позиции, в которой имеются два возможных выигрышных хода, чем позиции, в которой есть только один выигрышный ход. В таком случае компьютер попытался бы заблокировать один из возможных выигрышных ходов.
Если бы для поиска в дереве игры мы располагали только минимаксной стратегией, то выполнить поиск в больших деревьях было бы очень сложно. Такие игры, как шахматы, настолько сложны, что программа может провести поиск всего лишь на нескольких уровнях дерева. К счастью, существуют несколько приемов, которые можно использовать для поиска в больших деревьях игры.
@Рис. 8.4. Нумерация клеток доски игры в крестики‑нолики
======193
@Рис. 8.5. Программа игры в крестики‑нолики сдается
Во‑первых, в программе могут быть записаны начальные ходы, выбранные экспертами. Можно решить, что программа игры в крестики‑нолики должна делать первый ход в центральную клетку. Это определяет первую ветвь дерева игры, поэтому программа может игнорировать все пути, не проходящие через первую ветвь. Это уменьшает дерево игры в крестики‑нолики в 9 раз.
Фактически, программе не нужно выполнять поиск в дереве до того, пока противник не сделает свой ход. В этот момент и компьютер и противник выбрали каждый свою ветвь, поэтому оставшееся дерево станет намного меньше, и будет содержать менее чем 7! = 5040 путей. Просчитав заранее всего один ход, можно уменьшить размер дерева игры от четверти миллиона до менее чем 5040 путей.
Аналогично, можно записать ответы на первые ходы, если противник ходит первым. Есть девять вариантов первого хода, следовательно, нужно записать девять ответных ходов. При этом программе не нужно поводить поиск по дереву, пока противник не сделает два хода, а компьютер — один. Тогда дерево игры будет содержать менее чем 6! = 720 путей. Записано всего девять ходов, а размер дерева при этом уменьшается очень сильно. Это еще один пример пространственно‑временного компромисса. Использование большего количества памяти уменьшает время, необходимое для поиска в дереве игры.
Программа TicTac2 использует 10 записанных ходов. Задайте 9 уровень мастерства, и пусть программа делает первый ход. Затем задайте те же опции в программе TicTac. Вы увидите громадную разницу в скорости работы этих двух программ.
Коммерческие программы игры в шахматы также начинают с записанных ходов и ответов, рекомендованных гроссмейстерами. Такие программы могут делать первые ходы очень быстро. После того, как программа исчерпает все записанные заранее ходы, она начнет делать ходы намного медленнее.
Другой способ улучшения поиска в дереве игры состоит в том, чтобы определять важные позиции. Если программа распознает одну из этих позиций, она может выполнить определенные действия или изменить способ поиска в дереве игры.
========194
Во время игры в шахматы игроки часто располагают фигура так, чтобы они защищали другие фигуры. Если противник берет фигуру, то игрок берет фигуру противника взамен. Часто такое взятие позволяет противнику в свою очередь взять другую фигуру, что приводит к серии обменов.
Некоторые программы находят возможные последовательностей обменов. Если программа распознает возможность обмена, она на время изменяет максимальную глубину, на которую она просматривает дерево, чтобы проследить до конца цепочку обменов. Это позволяет программе решить, стоит ли идти на обмен. После обмена фигур их количество также уменьшается, поэтому поиск в дереве игры становится в будущем более простым.
Некоторые шахматные программы также отслеживают рокировки, ходы, при которых под боем оказывается сразу несколько фигур, шах или нападение на ферзя и так далее.
В играх, более сложных, чем крестики‑нолики, практически невозможно провести поиск даже в небольшом фрагменте дерева игры. В этих случаях, можно использовать различные эвристики. Эвристикой называет алгоритм или эмпирическое правило, которое вероятно, но не обязательно даст хороший результат.
Например, в шахматах обычной эвристикой является «усиление преимущества». Если у противника меньше сильных фигур и одинаковое число остальных, то следует идти на размен при каждой возможности. Например, если вы берете коня противника, теряя при этом своего, то такой обмен следует выполнить. Уменьшение числа оставшихся фигур делает дерево решений короче и может увеличить относительное преимущество. Эта стратегия не гарантирует выигрыша, но повышает его вероятность.
Другая часто используемая эвристика заключается в присвоении разных весов различным частям доски. В шахматах вес клеток в центре доски выше, так как фигуры, находящиеся на этих позициях, могут атаковать большую часть доски. Когда процедура BoardValue вычисляет вес текущей позиции на доске, она может присваивать больший вес фигурам, которые занимают клетки в центре доски.
Поиск в других деревьях решений
Некоторые методы поиска в деревьях игры неприменимы к обобщенным деревьям решений. Многие их этих деревьев не включают поочередных ходов игроков, поэтому минимаксный метод и вычисленные заранее ходы в данном случае бессмысленны. В следующих разделах описаны методы, которые можно использовать для поиска в этих типах деревьев решений.
=======195
Метод ветвей и границ (branch and bound) является одним из методов отсечения (pruning) ветвей в дереве решений, чтобы не было необходимо рассматривать все ветви дерева. Общий подход при этом состоит в том, чтобы отслеживать границы уже обнаруженных и возможных решений. Если в какой‑то точке наилучшее из уже найденных решений лучше, чем наилучшее возможное решение в нижних ветвях, то можно игнорировать все пути вниз от узла.
Например, допустим, что имеет 100 миллионов долларов, которые нужно вложить в несколько возможных инвестиций. Каждое из вложений имеет разную стоимость и дает разную прибыль. Необходимо решить, как вложить деньги наилучшим образом, чтобы суммарная прибыль была максимальной.
Задачи такого типа называются задачей формирования портфеля[RV14] (knapsack problem). Имеется несколько позиций (инвестиций), которые должны поместиться в портфель фиксированного размера (100 миллионов долларов). Каждая из позиций имеет стоимость (деньги) и цену (тоже деньги). Необходимо найти набор позиций, который помещается в портфель и имеет максимально возможную цену.
Эту задачу можно смоделировать при помощи дерева решений. Каждый узел дерева соответствует определенной комбинации позиций в портфеле. Каждая ветвь соответствует принятию решения о том, чтобы удалить позицию из портфеля или добавить ее в него. Левая ветвь первого узла соответствует первому вложению. На рис. 8.6 показано дерево решений для четырех возможных инвестиций.
Дерево решений для этой задачи представляет собой полное двоичное дерево, глубина которого равна числу инвестиций. Каждый лист соответствует полному набору инвестиций.
Размер этого дерева очень быстро растет с увеличением числа инвестиций. Для 10 возможных инвестиций, в дереве будет находиться 210 = 1024 листа. Для 20 инвестиций, в дереве будет уже более миллиона листьев. Можно провести полный поиск по такому дереву, но при дальнейшем увеличении числа возможных инвестиций размер дерева станет очень большим.
@Рис. 8.6. Дерево решений для инвестиций
=======196
Чтобы использовать метод ветвей и границ, создадим массив, который будет содержать позиции из наилучшего найденного до сих пор решения. При инициализации массив должен быть пуст. Можно также использовать переменную для отслеживания цены этого решения. Вначале эта переменная может иметь небольшое значение, чтобы первое же найденное реальное решение было лучше исходного.
При поиске в дереве решений, если в какой‑то точке анализируемое решение не может быть лучше, чем существующее, то можно прекратить дальнейший поиск по этому пути. Также, если в какой‑то точке выбранные позиции стоят более 100 миллионов, то можно также прекратить поиск.
В качестве конкретного примера, предположим, что имеются инвестиции, приведенные в табл. 8.1. На рис. 8.6 показано соответствующее дерево решений. Некоторые из этих инвестиционных пакетов нарушают граничные условия задачи. Например, самый левый путь привел бы к вложению 178 миллионов долларов во все четыре возможных инвестиции.