Романтика искусственного интеллекта
Шрифт:
Даже на этом, довольно простом примере видно, что игрок – человек использует довольно сложный понятийный аппарат: перехват, зоны гарантированной поддержки, угроза, одновременная угроза. Вопрос здесь вот какой: а имеем ли мы техническое устройство, способное оперировать понятиями такого смыслового уровня? Если взглянуть на проблему глазами специалиста середины XX века, то ответ отрицательный. Современный уровень развития систем искусственного интеллекта, конечно, другой, и сейчас движение в сторону моделирования человеческого способа мышления уже не выглядит таким уж невероятным. Но дело в том, что в интеллектуальных играх техника повторила прецедент колеса. В то время когда интерес к моделированию шахмат был очень велик, ресурсы для реализации человекоподобного шахматиста можно сказать что отсутствовали, и теория искусственного интеллекта нашла возможность решить поставленную
Первая базовая идея – дерево перебора
Допустим, шахматная ситуация допускает десять ходов игрока. Конечно, реально в шахматной партии, даже если осталась пара фигур, вариантов хода существенно больше, чем десять, но мы для упрощения анализа остановимся на числе в 10 продолжений. Тогда его противник тоже имеет выбор из 10 ходов. Таким образом, ход игрока и реакция его оппонента создадут 100 позиций. Еще пара ходов (игрок – противник), и конечных позиций уже 10 000. Простая арифметика дает астрономическое число. N ходов обоих игроков породят 10N ситуаций. Таким образом, партия в 100 ходов даст 10100 конечных позиций. А значит, даже если бы в каждой позиции действительно было бы возможно только 10 ходов, количество конечных ситуаций практически необозримо.
Есть, правда, вопрос: а зачем анализировать возможные продолжения от исходной позиции до конечной? Вопрос вполне правомерный. Люди-шахматисты, очевидно, не выполняют подобной работы, однако партии в исполнении людей выглядят вполне разумно. Есть, кстати, любопытная легенда об одном из величайших шахматистов всех времен и народов – Хозе Рауле Капабланке. Вроде бы его как-то спросили, как далеко он продумывает игру, на что Рауль ответил: на один ход. Значит, это возможно – не смотреть глубоко.
Вспомним, однако, что человек – довольно сложно устроенная машина. У нас такой нет. Мы не можем опираться на опыт, нет и возможности использовать развитую шахматную теорию, что, конечно, минус. Знание теории дает довольно много. Допустим, требуется выяснить, выдержит ли некая конструкция удар кувалдой. Знание теории сопротивления материалов позволяет провести расчет и дать ответ без кувалды. Если теория испытателю неизвестна, то остается только выполнить удар. Примерно такова же ситуация и в шахматах. Если мы знаем, что потеря центра в дебюте – это почти всегда плохо, и если мы видим, что такая угроза существует, то нет необходимости анализировать все продолжения, будет вполне достаточно сосредоточиться на угрозах центру. Если такой теоретический факт неизвестен, то придется провести анализ на некоторое количество ходов вперед, чтобы обнаружить то, о чем теория говорит сразу. Конечно, шахматная теория существует, но давайте пока осложним себе жизнь и положим, что она нам неизвестна. Итак, зафиксируйте свое внимание на проблеме. Обход дерева перебора необходим, но полный его обход невозможен. Продолжим анализ.
Чем меньше мы знаем, тем больше возможностей необходимо проверять
А значит, есть жесткая необходимость уметь строить дерево перебора от текущей позиции вглубь на как можно большее число ходов. Это фундаментальная необходимость. Конечно, повторимся, для шахмат существует глубокая и хорошо разработанная теория. Придумать форму записи этой теории в виде, пригодном для компьютерной программы, сложно, но можно. Но мы ведь говорим об игре вообще. А игр человечество придумало сотни, и для подавляющего их большинства никакой теории нет вообще. Перебор же в силу своей простоты реализации возможен всегда. Есть и интересная особенность игрового перебора. Все возможные ходы представляют собой не хаотичное множество, а довольно строгую структуру дерева. Что-то вроде такого, как на картинке ниже (рис. 2.3).
При наличии такой структуры все, что мы должны сделать как программисты, – это научиться обходить дерево в поисках ветки, обладающей нужными свойствами. А для того, чтобы уяснить, что такое «нужные свойства», рассмотрим вторую базовую идею.
Рис. 2.3. Дерево перебора
Вторая базовая идея – оценочная функция
Итак, допустим, мы в анализе позиции продвинулись по дереву перебора на несколько ходов вперед и получили некоторое количество позиций, которые будем считать конечными. Необходимо их оценить. Самая примитивная ситуация – это кто-то уже выиграл. Возможно, будут и такие ситуации, но, скорее всего, каждая из конечных позиций находится в подвешенном состоянии: нет очевидного проигрыша, нет и очевидной победы, но что-то изменилось, и это что-то требуется измерить простыми количественными показателями. Иначе говоря, необходима числовая оценка, характеризующая качество позиции.
Заметим сразу, что оное качество определяется разными видами факторов. Очень важно, какой материал находится на доске. Материальное преимущество, в принципе, может быть решающим. Например, если в игре в шашки у вас четыре дамки, а у противника одна шашка и ход за вами, то совершенно не важно, как расположены шашки. Если у вас на доске к концу шахматной партии остались ферзь и король, а у противника только король и ход за вами, то опять не важно, кто где стоит. Материал часто решает дело, поэтому оценка материала даже без учета его расположения может дать очень много.
Много, но не все. При игре королем против короля и ферзя вполне возможен пат, то есть ничейная ситуация. В русских шашках (поле 8x8) известно, что три дамки гарантированно ловят одну стандартной комбинацией, при условии что эта единственная дамка не стоит на главной диагонали. А значит, если противник, в свою очередь, может превратить свою единственную шашку в дамку, вставшую на главную диагональ, то ситуация из проигранной становится ничейной. Из этих примеров следует, что обе группы факторов – и материальные, и позиционные – могут решить исход игры, и обе группы должны быть учтены самым тщательным образом. Но материальные факторы просчитать несколько легче, поэтому начнем с них.
У каждой из фигур есть собственная сила, не зависящая от расположения
К сожалению, в деле учета материала нет никакой строгой теории, и, может быть, такая теория даже невозможна. Ведь что нам нужно, по сути? Необходимо точно определить значимость каждой фигуры. Мы можем совершенно произвольно определить стоимость самой слабой фигуры – пешки или самой сильной – ферзя. Например, пусть пешка стоит 1 балл. А вот далее начинаются серьезные проблемы. Необходимо договориться, насколько сильнее пешки каждая из фигур. Причем безотносительно конкретной позиции. Это сложно во многих планах. Для любого шахматиста сила фигуры привязана к позиционным факторам: сдвоенные слоны сильнее двух несвязанных. Сила пешки увеличивается по мере ее продвижения к последней горизонтали. В дебюте ладьи мало что решают, но в эндшпиле, когда большая часть доски пустеет, их сила резко возрастает. Конь очень важен в миттельшпиле, но в эндшпиле ему сложно перескакивать с фланга на фланг. Слон скачет с большой легкостью, но у слона серьезные проблемы в миттельшпиле, где он на каждом шагу наталкивается на пешки и свои, и противника, кроме того, для слона доступна только половина шахматного поля – половина его цвета. Но тем не менее надо как-то от всего этого отвлечься и оценить собственную силу фигур, ведь интуитивно ясно, что есть какие-то внутренние характеристики.
Такая ситуация характерна для многофигурных игр, особенно если фигуры можно рубить. В русских шашках проблема проявляется слабее, видов фигур только два: шашка и дамка. В рэндзю проблемы материала вообще нет, в этой древней игре только один вид фигур – камень, и более того, после каждого хода количество камней игроков одинаково, а значит, материального фактора нет вообще. Но мы сейчас говорим о шахматах.
Стандартный подход к оценке материала опирается на составление экспертного мнения. Сделаем так: соберем группу опытных шахматистов и дадим задание оценить силу фигуры, например по десятибалльной шкале, приняв цену пешки в один балл. После чего составим оценку для каждой фигуры как среднее арифметическое оценок для данной фигуры по всем экспертам. Как это ни странно, но такой простой способ сработает, и довольно неплохо. Дело в том, что эксперты тоже не имеют никакой теории силы фигур, как и мы, а значит, опираются на собственные интуитивные ощущения. В игре эксперт использует тоже свои представления о силе фигур, а следовательно, если эксперт добросовестно передаст свое понимание вопроса, он как бы передаст свой реальный опыт, а значит, даст программе возможность эффективно сыграть против себя. С учетом же того, что мы собрали сильных экспертов, становится ясно, что их личная сила, таким образом, передается и программе.