Глава 2
Вся жизнь – игра
Есть один вид человеческой деятельности в высшей степени интеллектуальный, но тем не менее, как оказалось, легко поддающийся алгоритмизации. Я имею в виду игру. Первые программы, эффективно играющие против человека, появились еще на заре развития вычислительной техники. Что интересно, штурм игры искусственным интеллектом пришелся на шахматы, каковые следует признать одной из наиболее сложных игр. И успех пришел достаточно быстро. Начало шахматных разработок можно отсчитывать от статьи Клода Шеннона, опубликованной еще в 1949 году, в которой рассмотрены основные проблемы игровых моделей. Шеннон впервые представил игру в виде дерева позиций, ветви которого – это возможные ходы, а выбор хода – это выбор наилучшего продолжения из возможных. Процедура выбора получила название минимаксной. Ее название характеризует самую суть действия машины, и немного позже мы это обсудим.
Рис. 2.1. Клод Элвуд Шеннон
Клод Элвуд Шеннон (рис. 2.1) – американский инженер и математик, его работы являются синтезом математических идей с конкретным анализом чрезвычайно сложных проблем их технической реализации. Является основателем теории информации, нашедшей применение в современных высокотехнологичных системах связи. Шеннон внес огромный вклад в теорию вероятностных схем, теорию автоматов и теорию систем управления – области наук, входящие в понятие «кибернетика».
Первым проект Шеннона реализовал Тьюринг, но его программа, показав принципиальную приемлемость, тем не менее не смогла выиграть даже у слабого шахматиста. Первой если не сильной, то вполне играющей шахматной программой можно считать проект MANIAC–I, реализованный в 1956 году группой сотрудников Лос-Аламосской лаборатории. Эта программа наиболее точно соответствовала идее Шеннона, ей также не удалось показать выдающихся результатов, но одну из трех партий против слабого игрока она уже могла выиграть.
Дальнейшее развитие игровых программ было связано с двумя факторами: развитием математического аппарата игровых программ и ростом ресурсов вычислительных машин. На годы главной игрой, на которой упражнялись специалисты по искусственному интеллекту, остались шахматы, но со временем, с ростом доступности компьютеров, появлением большого числа программистов, руки стали доходить и до других игр. Сегодня в сети можно найти программы, играющие против человека в самые различные игры. Что же касается шахмат, то здесь были достигнуты просто великолепные результаты. Программы, использующие ресурсы персональных компьютеров, вполне успешно играют против хороших шахматистов, а гроссмейстеры-суперкомпьютеры смогли разделить шахматный пьедестал с гроссмейстерами-людьми.
В 1996 году состоялся первый матч Deep Blue с Гарри Каспаровым, в котором чемпион мира одержал победу со счетом 4:2. Deep Blue – это 6-процессорный суперкомпьютер, способный просчитывать 100 млн позиций в секунду. Через год состоялся матч-реванш с модернизированным 8-процессорным Deep Blue, считающим вдвое быстрее. Компьютер впервые победил лучшего шахматиста планеты со счетом 3,5:2,5. Пока компьютер не умел оценивать позицию, как человек, рост силы игры достигался по большей части за счет увеличения мощности «железа». Даже в качестве алгоритма перебора все еще использовался «брутфорс» (грубая сила), перебиралось как можно больше вариантов, но очень быстро. В 2003 году состоялся еще один матч Каспарова против компьютера – Deep Junior, работавшего на 4-процессорной системе с процессорами Pentium IV 1,9 ГГц и 3 Гб оперативной памяти. Junior стал первой программой, демонстрирующей «человечную» игру и способной пойти на жертву ради инициативы. Матч закончился вничью.
Компьютер против человека. Как это выглядит в принципе?
Для меня лично, когда я впервые увлекся проблемами искусственного разума, было самым большим открытием то, что моделирование интеллекта выполняется на базе очень простых принципов. Их техническая реализация может быть трудоемкой и даже очень трудоемкой, так как есть необходимость учитывать огромное количество деталей, и одной формулой процесс не опишешь. Но базовых идей очень немного, и их понимание не требует исключительной одаренности.
В этой главе мы рассмотрим принципы создания программ, играющих в интеллектуальные игры. Информации главы вполне достаточно, чтобы написать несложную программу, которая будет вполне прилично играть, при условии что вы – технически грамотный программист. Конечно, я не советую пытаться соревноваться с коллективами, пишущими программы, играющие в шахматы или го. Для начала можно попробовать реализовать игру попроще.
А теперь поговорим о том, как это работает. Базовые идеи разберем на шахматах, думаю, что хотя бы правила этой игры известны всем. Две вещи сомнения не вызывают: для принятия решения об очередном ходе необходимо уметь оценивать ситуацию, насколько она хороша или насколько она плоха, и необходимо уметь просчитывать течение игры на некоторое количество ходов вперед. Просчет игры заключается в построении всех возможных вариантов с точки зрения «грубой силы» или всех разумных вариантов, если есть хорошая эвристика.
Как эту работу выполняет человек
В решении задач искусственного интеллекта возможны два общих подхода. Можно попытаться реализовать человеческий способ мышления, и можно придумать метод, решающий ту же задачу, но иначе, не по-человечески. Примеров успешной реализации второго подхода масса. Например, движущийся по земле аппарат человек снабдил колесами, а не ногами. Наши летательные аппараты также принципиально отличаются от устройства птицы или летающего насекомого. А значит, и программа, играющая в шахматы или шашки, не обязана выглядеть по образцу и подобию своего создателя. Но тем не менее рассмотреть процесс игрового мышления человека полезно. На картинке (рис. 2.2) этюд мастера шахматной композиции Рихарда Рети.
Рис. 2.2. Этюд мастера Рети
По замыслу автора, белые, начиная, должны свести игру к ничьей. Попробуем провести человеческий анализ этой позиции. В чем здесь проблема? Позиция содержит две угрозы. С одной стороны, черная пешка рвется к последней горизонтали, и белый король ее уже не догонит. Аналогичная угроза есть и для черных, белая пешка через два хода может стать фигурой, но черный король успевает ее перехватить, а белый не успевает прийти на помощь своей пешке. То есть перед белым королем стоят две задачи: помощь своей пешке и перехват черной – не решаемые по отдельности.
Однако если две задачи не решаются каждая в отдельности, это не означает, что не решаема и их комбинация. Белый король имеет возможность, двигаясь по черной диагонали, одновременно приближаться к зоне перехвата черной пешки и к зоне поддержки своей. Если черные будут выполнять движение пешкой, то белый король успеет поддержать свою, а если черные решат уничтожить белую пешку, то белый король успеет перехватить черную. Таким образом, правильным решением для белых оказывается движение по диагонали.
Даже на этом, довольно простом примере видно, что игрок – человек использует довольно сложный понятийный аппарат: перехват, зоны гарантированной поддержки, угроза, одновременная угроза. Вопрос здесь вот какой: а имеем ли мы техническое устройство, способное оперировать понятиями такого смыслового уровня? Если взглянуть на проблему глазами специалиста середины XX века, то ответ отрицательный. Современный уровень развития систем искусственного интеллекта, конечно, другой, и сейчас движение в сторону моделирования человеческого способа мышления уже не выглядит таким уж невероятным. Но дело в том, что в интеллектуальных играх техника повторила прецедент колеса. В то время когда интерес к моделированию шахмат был очень велик, ресурсы для реализации человекоподобного шахматиста можно сказать что отсутствовали, и теория искусственного интеллекта нашла возможность решить поставленную задачу совсем иным, но очень эффективным способом. Коротко этот способ можно обозначить двумя словосочетаниями: «дерево перебора» и «оценочная функция».
Первая базовая идея – дерево перебора
Допустим, шахматная ситуация допускает десять ходов игрока. Конечно, реально в шахматной партии, даже если осталась пара фигур, вариантов хода существенно больше, чем десять, но мы для упрощения анализа остановимся на числе в 10 продолжений. Тогда его противник тоже имеет выбор из 10 ходов. Таким образом, ход игрока и реакция его оппонента создадут 100 позиций. Еще пара ходов (игрок – противник), и конечных позиций уже 10 000. Простая арифметика дает астрономическое число. N ходов обоих игроков породят 10N ситуаций. Таким образом, партия в 100 ходов даст 10100 конечных позиций. А значит, даже если бы в каждой позиции действительно было бы возможно только 10 ходов, количество конечных ситуаций практически необозримо.
Есть, правда, вопрос: а зачем анализировать возможные продолжения от исходной позиции до конечной? Вопрос вполне правомерный. Люди-шахматисты, очевидно, не выполняют подобной работы, однако партии в исполнении людей выглядят вполне разумно. Есть, кстати, любопытная легенда об одном из величайших шахматистов всех времен и народов – Хозе Рауле Капабланке. Вроде бы его как-то спросили, как далеко он продумывает игру, на что Рауль ответил: на один ход. Значит, это возможно – не смотреть глубоко.
Вспомним, однако, что человек – довольно сложно устроенная машина. У нас такой нет. Мы не можем опираться на опыт, нет и возможности использовать развитую шахматную теорию, что, конечно, минус. Знание теории дает довольно много. Допустим, требуется выяснить, выдержит ли некая конструкция удар кувалдой. Знание теории сопротивления материалов позволяет провести расчет и дать ответ без кувалды. Если теория испытателю неизвестна, то остается только выполнить удар. Примерно такова же ситуация и в шахматах. Если мы знаем, что потеря центра в дебюте – это почти всегда плохо, и если мы видим, что такая угроза существует, то нет необходимости анализировать все продолжения, будет вполне достаточно сосредоточиться на угрозах центру. Если такой теоретический факт неизвестен, то придется провести анализ на некоторое количество ходов вперед, чтобы обнаружить то, о чем теория говорит сразу. Конечно, шахматная теория существует, но давайте пока осложним себе жизнь и положим, что она нам неизвестна. Итак, зафиксируйте свое внимание на проблеме. Обход дерева перебора необходим, но полный его обход невозможен. Продолжим анализ.
Чем меньше мы знаем, тем больше возможностей необходимо проверять
А значит, есть жесткая необходимость уметь строить дерево перебора от текущей позиции вглубь на как можно большее число ходов. Это фундаментальная необходимость. Конечно, повторимся, для шахмат существует глубокая и хорошо разработанная теория. Придумать форму записи этой теории в виде, пригодном для компьютерной программы, сложно, но можно. Но мы ведь говорим об игре вообще. А игр человечество придумало сотни, и для подавляющего их большинства никакой теории нет вообще. Перебор же в силу своей простоты реализации возможен всегда. Есть и интересная особенность игрового перебора. Все возможные ходы представляют собой не хаотичное множество, а довольно строгую структуру дерева. Что-то вроде такого, как на картинке ниже (рис. 2.3).
При наличии такой структуры все, что мы должны сделать как программисты, – это научиться обходить дерево в поисках ветки, обладающей нужными свойствами. А для того, чтобы уяснить, что такое «нужные свойства», рассмотрим вторую базовую идею.
Рис. 2.3. Дерево перебора
Вторая базовая идея – оценочная функция
Итак, допустим, мы в анализе позиции продвинулись по дереву перебора на несколько ходов вперед и получили некоторое количество позиций, которые будем считать конечными. Необходимо их оценить. Самая примитивная ситуация – это кто-то уже выиграл. Возможно, будут и такие ситуации, но, скорее всего, каждая из конечных позиций находится в подвешенном состоянии: нет очевидного проигрыша, нет и очевидной победы, но что-то изменилось, и это что-то требуется измерить простыми количественными показателями. Иначе говоря, необходима числовая оценка, характеризующая качество позиции.
Заметим сразу, что оное качество определяется разными видами факторов. Очень важно, какой материал находится на доске. Материальное преимущество, в принципе, может быть решающим. Например, если в игре в шашки у вас четыре дамки, а у противника одна шашка и ход за вами, то совершенно не важно, как расположены шашки. Если у вас на доске к концу шахматной партии остались ферзь и король, а у противника только король и ход за вами, то опять не важно, кто где стоит. Материал часто решает дело, поэтому оценка материала даже без учета его расположения может дать очень много.
Много, но не все. При игре королем против короля и ферзя вполне возможен пат, то есть ничейная ситуация. В русских шашках (поле 8×8) известно, что три дамки гарантированно ловят одну стандартной комбинацией, при условии что эта единственная дамка не стоит на главной диагонали. А значит, если противник, в свою очередь, может превратить свою единственную шашку в дамку, вставшую на главную диагональ, то ситуация из проигранной становится ничейной. Из этих примеров следует, что обе группы факторов – и материальные, и позиционные – могут решить исход игры, и обе группы должны быть учтены самым тщательным образом. Но материальные факторы просчитать несколько легче, поэтому начнем с них.
У каждой из фигур есть собственная сила, не зависящая от расположения
К сожалению, в деле учета материала нет никакой строгой теории, и, может быть, такая теория даже невозможна. Ведь что нам нужно, по сути? Необходимо точно определить значимость каждой фигуры. Мы можем совершенно произвольно определить стоимость самой слабой фигуры – пешки или самой сильной – ферзя. Например, пусть пешка стоит 1 балл. А вот далее начинаются серьезные проблемы. Необходимо договориться, насколько сильнее пешки каждая из фигур. Причем безотносительно конкретной позиции. Это сложно во многих планах. Для любого шахматиста сила фигуры привязана к позиционным факторам: сдвоенные слоны сильнее двух несвязанных. Сила пешки увеличивается по мере ее продвижения к последней горизонтали. В дебюте ладьи мало что решают, но в эндшпиле, когда большая часть доски пустеет, их сила резко возрастает. Конь очень важен в миттельшпиле, но в эндшпиле ему сложно перескакивать с фланга на фланг. Слон скачет с большой легкостью, но у слона серьезные проблемы в миттельшпиле, где он на каждом шагу наталкивается на пешки и свои, и противника, кроме того, для слона доступна только половина шахматного поля – половина его цвета. Но тем не менее надо как-то от всего этого отвлечься и оценить собственную силу фигур, ведь интуитивно ясно, что есть какие-то внутренние характеристики.
Такая ситуация характерна для многофигурных игр, особенно если фигуры можно рубить. В русских шашках проблема проявляется слабее, видов фигур только два: шашка и дамка. В рэндзю проблемы материала вообще нет, в этой древней игре только один вид фигур – камень, и более того, после каждого хода количество камней игроков одинаково, а значит, материального фактора нет вообще. Но мы сейчас говорим о шахматах.
Стандартный подход к оценке материала опирается на составление экспертного мнения. Сделаем так: соберем группу опытных шахматистов и дадим задание оценить силу фигуры, например по десятибалльной шкале, приняв цену пешки в один балл. После чего составим оценку для каждой фигуры как среднее арифметическое оценок для данной фигуры по всем экспертам. Как это ни странно, но такой простой способ сработает, и довольно неплохо. Дело в том, что эксперты тоже не имеют никакой теории силы фигур, как и мы, а значит, опираются на собственные интуитивные ощущения. В игре эксперт использует тоже свои представления о силе фигур, а следовательно, если эксперт добросовестно передаст свое понимание вопроса, он как бы передаст свой реальный опыт, а значит, даст программе возможность эффективно сыграть против себя. С учетом же того, что мы собрали сильных экспертов, становится ясно, что их личная сила, таким образом, передается и программе.
Но необходимо заметить, что вопрос, сформулированный так примитивно, – как оценить собственную силу фигур безотносительно позиции, – не дает эксперту возможности передать более значительную часть своего знания – знания о взаимной силе фигур.
Материальные факторы зависят от взаимного расположения, и это обстоятельство значительно усложняет анализ
Следующим шагом необходимо поинтересоваться у экспертной компании не только о том, как оценить некий фактор, но и какие вообще материальные факторы возможны. Имеются в виду факторы, определяемые положением фигур. Группа таких факторов выглядит намного сложнее. И здесь в полный рост встает проблема взаимопонимания. Цель разработчика – грамотно задать вопрос. Искусство вопроса предполагает, что задающий вопрос, может быть, не эксперт, но все же имеет хорошее представление о предмете. Поэтому хотите вы или нет, но если взялись писать программу, играющую в интеллектуальную игру, вам придется и самому научиться в нее играть на приличном уровне. Это даст возможность правильно сформулировать вопрос и выделить из ответов существенную информацию. Критерий хорошего экспертного ответа (в отношении определения фактора) таков: фактор должен быть легко алгоритмизируем. А это не всегда так. Вот пара примеров.
Хороший фактор. Сдвоенные слоны. Так называются слоны, находящиеся на соседних диагоналях. Это обстоятельство алгоритмически легко проверяется, поэтому фактор не только сильный с точки зрения шахматиста, но и удобный с точки зрения программиста.
Плохой фактор. Ладья имеет высокую степень свободы. Не вполне понятно, что имеется в виду. Этим может быть сказано, что ладья может своим ходом встать на значительное число полей, что, конечно, неплохо, но что, если все такие поля бьются фигурами противника. Кроме того, «высокая степень свободы» – это качественная оценка, а нам необходимы оценки количественные. Фактор можно превратить в хороший следующей переформулировкой: ладья полностью контролирует открытую вертикаль. Что такое открытая вертикаль, понятно и легко проверяемо, а контроль означает, что ладья будет угрожать любой фигуре, вставшей на эту вертикаль, причем если вертикаль уже открыта, значит, на ней нет пешки. Любая же другая фигура сопоставима с ладьей, и, значит, ладейная угроза всегда будет существенна.
Если разработчику и экспертной группе удалось сформулировать хорошо алгоритмизируемые факторы материальной группы, то следующий шаг очевиден, необходимо опять провести численную оценку по той же шкале, по которой проводилась оценка абсолютной силы фигур.
Есть группа факторов, определяющих не силу фигуры, собственную или во взаимодействии с еще одной или двумя фигурами, а оценивающих качество позиции в целом. Это так называемые позиционные факторы
Здесь разработчика и экспертов ожидают наиболее существенные проблемы в связи с тем, что хорошо алгоритмизируемых позиционных факторов не бывает. Как, например, описать, что означает: давление на королевский фланг, контроль центра, низкая активность фигур, слабое фигурное взаимодействие на фланге и т. д.? Некоторые рекомендации и здесь возможны, но хорошее решение позиционной проблемы, обладающее математической строгостью, если и возможно, то пока даже в отношении такой разработанной игры, как шахматы, неизвестно.
В шахматах, однако, есть один хорошо алгоритмизируемый позиционный фактор – это давление на пункт. В отношении любого поля доски реально посчитать количество фигур, держащих этот пункт под ударом. Вот это количество ударов можно считать первичной оценкой фактора. Подчитав количество ударов на поля, принадлежащие центру, несложно оценить, кто из игроков имеет больше шансов выиграть борьбу за центр и, следовательно, кому из них плюсовать этот фактор. А оценку фактора, входящую в оценочную функцию, необходимо опять спрашивать у экспертной группы по уже известному сценарию.
Кстати, этот фактор – давление на пункт, или, иначе говоря, возможность захвата пункта, можно выделить в очень многих играх, а стало быть, его допустимо считать общеприменимым
Идея опоры на чисто арифметический подсчет ударов, конечно, весьма спорна, так как давление разными фигурами явно не равноценно. Например, не факт, что давление ферзем более сильно, чем давление пешкой. В определенных условиях пешка в силу своей мало-ценности может оказаться более эффективной. Но, с другой стороны, учитывать в позиционном факторе еще и силу фигуры, осуществляющей давление, может слишком сильно усложнить оценочную функцию, увеличив вероятность ошибки. Здесь работает общее правило, утверждающее, что чем сложнее механизм, тем меньше вероятность его правильной работы.
Как считать оценочную функцию?
Существует общий принцип, вытекающий из природы игровой стратегии, стремящейся минимизировать ущерб.
Он называется принципом минимакса
Пока ясно, что есть факторы, описываемые двумя числами – ценой и количественным значением. Это как в овощном ларьке, у каждого овоща есть цена, и есть их наличное количество. Центр доски или королевский фланг, конечно, присутствуют на доске в единственном экземпляре, и пара сдвоенных слонов может быть только одна, но материальные факторы, в том числе и ферзь, могут быть в нескольких экземплярах (пешка может стать ферзем). Введем обозначения: mk – это количество фактора, и vk – это цена, или, еще говорят, вес фактора. Тогда общая оценка позиции может быть записана следующим выражением:
Теперь попробуем разобраться, как оценочную функцию использовать для выбора хода. Для этого представим себе некую гипотетическую игру, в которой на каждый ход одного из игроков существуют ровно два ответа. Назовем игроков: Первый и Второй – и выберем продолжение для Первого игрока, при глубине анализа в один ход (один ход – это ход Первого и ответ Второго). Анализ игры в этом случае будет опираться на такое дерево (рис. 2.4):
Рис. 2.4. Пример минимакса
Похожая картинка уже была, но здесь информации несколько больше. Конечные ситуации оценены, и есть вопрос, какой ход: левый или правый – должен выбрать Первый игрок. Возможно, кому-то покажется, что лучший ход – левый, так как именно там расположена ветка с наилучшей оценкой в пять баллов. Но нужно понимать, что после левого хода Первый игрок передает право выбора хода Второму, и этот Второй выберет ветку, оканчивающуюся единичной оценкой. Поэтому необходимо выбирать правый вариант, в котором Второй игрок отдаст Первому ветку с худшей оценкой 2. Заметим, что Первый игрок реально может выбирать только из худших оценок, и все, что в его силах, – это выбор наилучшего из худшего. Данный принцип называется принципом минимакса. Рассмотрим для иллюстрации более сложный пример. Дерево перебора оформим в виде таблицы, на нижнем уровне которой – значения оценочной функции на максимальной глубине дерева перебора, на промежуточных уровнях – значения оценки, выбранные противниками в свою очередь хода (оценки переходят снизу вверх):
Как и любой эвристический механизм, минимакс имеет свои плюсы и минусы, не гарантируя наилучшего продолжения, он позволяет выбрать действительно разумный вариант игры
Принцип основан на предположении, что игроки имеют равную силу. Действительно, преуменьшать возможности оппонента нет смысла. Если окажется, что он играет сильнее, чем предполагалось, – это может иметь плохие последствия. Исходить из того соображения, что соперник играет лучше, – заведомо проигрышная психология. Оптимальная точка зрения заключается в том, что я играю так хорошо, как могу, и мой соперник играет не хуже. В терминах мини-макса это означает следующее. Если выбор хода за мной, то я выберу ход с наилучшей оценкой для себя и наихудшей для противника, он, в свою очередь, сделает то же самое.
Из этого следует интересный вывод: если игра для каждого из игроков предоставляет равные возможности и если оценка позиции содержит все возможные факторы и все они оценены верно, то игра для обоих игроков возможна только на ничью. А если один из игроков – компьютерная программа, не умеющая допускать ошибки по невнимательности, то у человека против такой программы нет шансов, так как в этом случае выигрывать будет тот, кто в состоянии проанализировать дерево перебора на большую глубину. Конечно же, счетные возможности компьютера неизмеримо выше, нежели человека. Но, к сожалению или к счастью, полный анализ достаточно сложной игры, даже такой, как русские шашки, представляет собой исключительно тяжелую теоретическую задачу, и похоже, такой анализ не был выполнен еще ни для одной игры с полной информацией. А значит, всегда есть возможность построить более качественную оценочную функцию.
Кроме того, всегда есть возможность принимать решение на основе опыта. Распознав ситуацию на доске, человек может найти в своей памяти прецедент, завершившийся положительным или отрицательным результатом после определенного хода, и этот прецедент даст информацию о ходе без анализа дерева перебора.
А теперь давайте посмотрим, что дает фактическая невозможность составить идеальную оценочную функцию. Она, идеальная функция, была бы не нужна, будь у нас возможность выстроить дерево перебора от начала игры до самого конца, в этом случае достаточна предельно простая оценка с одним фактором – игра выиграна или игра проиграна. Можно утверждать, что:
Чем глубже дерево перебора для игрока, тем меньше у него потребность в хорошей оценке. И наоборот, если построить идеальную оценочную функцию, то потребность в дереве перебора отпадет полностью. Очередной ход можно будет просто вычислять из знания текущей ситуации.
Но идеальная оценка невозможна, невозможно и полное или даже очень глубокое дерево перебора. Это означает, что вывод о качестве выбранного хода всегда может быть ошибочен, что создает возможность для так называемого комбинационного удара, выполнение которого выходит за рамки минимакса. В чем суть комбинации (тактического приема)? А суть в следующем: игрок допускает резкое ухудшение своей позиции в анализе дерева перебора на глубину в N ходов, но на большей глубине он получает значительно большую компенсацию. Например, можно отдать ферзя, если в результате противник получит мат, можно отдать легкую фигуру, если за этим последует взятие тяжелой фигуры противника. А иногда в шахматах отдают материал за позиционный выигрыш.
Заметим, конечно, что, увеличивая вычислительные ресурсы, мы даем возможность программе просчитывать варианты, которые выглядят как комбинации (отдача материала или позиции с последующим отыгрышем), но всегда есть несчитаемая глубина дерева перебора и всегда, с точки зрения минимакса, плохая оценка на максимальной глубине – это безусловно плохая оценка.
Оптимизация минимаксной процедуры. Альфа-бета-алгоритм
В этом параграфе мы обсудим два момента: как увеличить глубину дерева перебора и как без полного перебора обнаружить комбинационный удар. Начнем с метода, позволяющего более глубоко копнуть дерево перебора. Заметим, для начала, что более глубокое дерево без увеличения вычислительных ресурсов возможно только за счет отсечения некоторых его не очень значимых ветвей. Только это дает возможность другие, более важные ветки просмотреть глубже. А процедура отсечения ветки нуждается в критерии, позволяющем оценить ветвь игры до ее анализа.
Интуитивный критерий лежит на поверхности. Предположим, следующим ходом (напомню, мы в качестве базовой игры рассматриваем шахматы) игрок теряет ферзя. С точки зрения простой оценочной функции, это очень плохо, и такой ход разумно исключить из рассмотрения. Предположим далее, что следующим ходом противник теряет ферзя. Обычный здравый смысл говорит, что на этом варианте следует сосредоточиться. Но мы сделаем несколько парадоксальный вывод, что этого хода также следует избегать. Дело в том, что, выстраивая теорию, мы исходили из предположения, что силы игроков равны. Из чего следует, что ни один из игроков выиграть слишком много не может. И следовательно, как выигрыш ферзя, так и его проигрыш необходимо признать делом нереальным. Математически расчетная схема выглядит так: определим для оценочной функции пределы значений, для которых ни одному из игроков не гарантирована победа. Эти два уровня опять-таки можно определить экспертной оценкой. Назовем нижний уровень уровнем альфа, а верхний – уровнем бета. Далее все очень просто. Идя по дереву перебора, будем выполнять оценку промежуточных ситуаций (в чистом минимаксе интересны только конечные позиции), и если эта оценка ниже уровня альфа или выше уровня бета, то такую игровую ветку отсекаем. На вопрос, как все же решиться взять ферзя противника, ответим немного позже.
Если вам показалось, что такой политикой игрок отказывается от возможности (но не любой, а лишь авантюрной, с точки зрения альфа-бета-алгоритма) выигрыша в пользу гарантированной ничьей, то вам показалось правильно. Цель алгоритма в том и состоит, чтобы обеспечить ничью при равных возможностях. Если же вы ставите своей целью победу, то необходимо несколько изменить подход.
Конец ознакомительного фрагмента.