Род Стивенс

Книги → Delphi. Готовые алгоритмы → Глава 8. Деревья решений

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

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

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

Точно так же можно записать ответы на первые ходы, если противник начи­нает игру. Пользователь имеет девять вариантов первого хода, поэтому вы долж­ны записать девять ответных ходов. Теперь программе не придется проводить поиск по дереву, пока противник не сделает два хода, а компьютер - один. В этом случае игровое дерево содержит менее чем 6! = 720 путей. Записано всего девять ходов, а размер игрового дерева сильно уменьшился. Это еще один пример про­странственно-временного компромисса. Использование дополнительных объе­мов памяти для хранения нескольких ходов очень сокращает время, необходимое для поиска в игровом дереве. В программе TicTac предусмотрено 10 заранее вы­численных ходов: один для первого хода и девять - для ответного, если против­ник ходит первым.

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

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

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

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

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

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

← предыдущая следующая →

Страницы раздела: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

Публикация компанией Dropbox кода Zulip – средства общения для IT-разработчиков

20.11.2015
Одной из одобрительно встреченных программистами инициатив, реализующихся в рамках акции Hack Week, стала публикация исходного кода приложения Zulip – веб-приложения для общения между собой разработчиков в сфере IT-технологий.

Объединение ОС Android и Chrome

17.11.2015
Слухи об объединении двух крупнейших ОС компании Google, Android и Chrome, гуляют по Интернету уже более 5 лет, но до сих пор этого не случилось, хотя очевидно, что с течением времени эти ОС становятся всё более похожими: так, в последнее время появилось немало Android-устройств, к которым прилагаются клавиатуры, а Chrome OS «научилась» работать с сенсорными экранами.

Конференция Linux Piter 2015

15.11.2015
Уже почти через неделю в Санкт-Петербурге впервые в истории пройдёт конференция, посвящённая проблемам свободного программного обеспечения – Linux Piter 2015.