Русские документы
Ежедневные компьютерные новости RSS rusdoc.ru  Найти :
Новости
Последние поступления
Книжный магазин
  Hardware:
Видеоустройства
Системные платы
Процессоры
Мобильные устройства
Аудиосистема
Охлаждение системы
Накопители информации
КПК и ноутбуки
Телефоны и связь
Периферия
Система
Сети
Разные устройства
 
  Programming:
Web-разработка
Языки программирования
Технологии и теория
Разработка игр
Программная инженерия
 
  Software:
Операционные системы
Windows 7
Базы данных
Обзоры программ
Графика и дизайн
   
  Life:
Компьютерная жизнь
Разные материалы
   
Партнеры
Публикация
Правовая информация
Реклама на сайте
Обратная связь
Экспорт в RSS Экспорт в RSS2.0
    Читать в Яндекс.Ленте



Игровые деревья и поиск в них

Раздел: Programming / Теория разработки @ 01.09.2010 | Ключевые слова: деревья игры алгоритмы версия для печати

Автор: GORKOFF
Источник: habrahabr

Сегодня мы немного поговорим о деревьях решений. Многие реальные задачи можно смоделировать с помощью таких деревьев. Каждый узел будет представлять собой один шаг решения задачи, ветвь в дереве соответствует решению, которое ведёт к более полному решению, листы представляют собой окончательное решение. Наша цель – найти в дереве лучший путь от корня до листа.

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

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

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



Как можно видеть из рисунка, дерево игры растёт чрезвычайно быстро. Если дерево продолжит расти таким образом, то во всём дереве будет содержаться 9!=362880 листьев.

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

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

Каждому игроку можно назначить четыре значения для конкретной позиции на поле: 4 соответствует выигрышу, 3 – не ясная ситуация, 2 – ничья, 1 – проигрыш. Для исчерпывающего исследования игрового дерева можно использовать стратегию минимакса. При этом мы будем пытаться минимизировать максимальное значение, которое может иметь позиция для противника после следующего хода. Сначала определяется максимальное значение, которое может набрать противник после каждого из ваших возможных ходов. Затем выбирается ход, при котором противник получает минимальное значение.

Процедура, поиска оптимального хода, вычисляет значение позиции поля. Эта процедура исследует каждый возможный ход. Для каждого хода она рекурсивно вызывает себя, чтобы определить значение которое будет иметь позиция противника. Затем она выбирает ход, который даёт противнику минимальное значение. Рекурсивное обращение процедуры к себе будет продолжаться, пока не наступит одно из трёх возможных событий. Во-первых, может быть найдена позиция, в которой игрок побеждает. В этом случае процедура устанавливает значение позиции поля в 4. В случае если игрок проигрывает, то значение поля будет установлено в 1. Во-вторых, может быть найдена позиция, в которой ни один игрок не может сделать ход. Игра заканчивается ничьей, поэтому процедура устанавливает значение позиции в 2. И, наконец, процедура может достичь заранее установленной глубины рекурсии. Если она превышает допустимую глубину, то значение поля устанавливается в 3, указывая на неопределённый исход. Максимальная глубина рекурсии предохраняет программу от слишком большой траты времени. Это особенно важно для сложных игр, вроде шахмат, где поиск может продолжаться практически бесконечно долго. Максимальная глубина рекурсии также позволяет также позволяет задавать уровень мастерства. Чем глубже программа может исследовать дерево, тем лучше будут её ходы.

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



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

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

Использование дополнительной памяти для хранения нескольких ходов значительно сокращает время, необходимое для поиска в дереве.

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

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

P.S. С днём знаний.

Это интересно:








версия для печатиРаспечатать статью


Вернуться в раздел: Programming / Теория разработки


Реклама:
Читать наc на:

Add to Google
Читать в Яндекс.Ленте






Rambler's Top100
© Copyright 1998-2012 Александр Томов. All rights reserved.