Род Стивенс

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

* Как можно видеть на рис. 8.1, дерево игры в крестики-нолики растет чрезвы­чайно быстро. Если дерево продолжает расти таким образом (то есть каждый узел имеет на одну ветвь меньше, чем его родитель), то во всем дереве будет содержать­ся 9 * S * 7 ... * 1 = 362 880 листьев. В дереве окажется 362 880 возможных путей, соответствующих 362 880 сценариям развития игры.

На самом деле многие возможные узлы в дереве игры в крестики-нолики от­сутствуют, потому что они запрещены правилами игры. Если игрок, ходивший пер­вым, за три своих хода ставит крестик в ле­вый верхний, средний верхний и правый верхний квадраты, то крестики побеждают и игра заканчивается. Узел, соответствую­щий этой позиции на игровом поле, не име­ет дочерних узлов, потому что игра завер­шилась (см. рис. 8.2).

Удаление всех невозможных узлов сокра­щает дерево практически до четверти милли­она листов. Однако это все еще довольно боль­шое дерево, и исчерпывающий поиск займет

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

Минимаксный перебор

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

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

Для исчерпывающего исследования игрового дерева можно использовать стра­тегию минимакса (minimax). При этом вы пытаетесь минимизировать максималь­ное значение, которое может иметь позиция для противника после следующего хода. Сначала определяется максимальное значение, которое может набрать про­тивник после каждого из ваших возможных ходов. Затем выбирается ход, при ко­тором противник получает минимальное значение.

Процедура BoardValue, приведенная ниже, вычисляет значение позиции поля. Эта процедура исследует каждый возможный ход. Для каждого хода она ре­курсивно обращается к себе, чтобы определить значение, которое будет иметь но­вая позиция для противника. Затем она выбирает ход, который дает противнику минимальное значение.

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

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

Страницы раздела: 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.