Текст книги "Романтика искусственного интеллекта"

Этапы игры

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

Есть начало игры. В стартовой позиции, в таких играх, как рэндзю, го, реверси, доска практически пустая, у обоих игроков нет ресурсов, достаточных для начала острой борьбы. В таких играх, как шашки, сеги, шахматы, все фигуры – на доске, но контакт с противником минимальный, а значит, серьезное нападение на построения оппонента невозможно. В играх, подобных войне башен (описание всех этих игр вы можете найти на lotos-khv.ru), уже в начале игры контакт между соперниками максимальный, но напряжение размазано по доске равномерно, ни у одного из игроков нет перевеса в какой-либо части поля, а значит, решающая атака первые 2–3 хода невозможна. Это означает, что в начале игры противники реально могут ставить перед собой только стратегические задачи по накапливанию позиционного преимущества. В шахматах этот этап называется дебютом.

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

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

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

Дебют

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

Прежде всего дебют отличается специфической игровой целью. Заметим сразу, что в шахматах отыгрыш материала в дебюте, даже одной пешки, – это очень серьезно. Отдача материала в миттельшпиле может означать комбинационный удар, но в дебюте таких возможностей, как правило, нет, поэтому потеря любой фигуры в начале игры, скорее всего, восполнена не будет, поэтому для дебютной оценочной функции можно не выделять фигуры как отдельные факторы. Целесообразно выделить два материальных фактора: пешечный, уменьшение которого разумно считать крайне опасным (но не фатальным, мы помним о возможности гамбитов), и фигурный, уменьшение которого можно признать сопоставимым с поражением в партии.

Вернемся к определению специфической игровой задачи. Шахматисты, говоря о дебютной цели, используют термин «развитие». Это означает, что в начале игры необходимо обеспечить максимальную подвижность фигур, отсутствие уязвимых пунктов в позиции и захват стратегически важных территорий. Как учесть эти факторы?

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

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

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

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

Эндшпиль

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

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

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

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

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

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

Оценка, основанная на приоритетах факторов

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

Заметим, что есть в шахматах события, настолько сильно влияющие на ход партии, что их можно признать доминирующими. Например, выигрыш или проигрыш ферзя настолько сложно скомпенсировать, что это событие можно признать почти равнозначным победе (поражению). Таких ситуаций достаточно много. Например, проигрыш центра в дебюте – практически некомпенсируемая потеря, лишняя пешка в эндшпиле при прочих равных также становится доминирующим фактором. А выигрыш фигуры в эндшпиле способен с лихвой уравновесить пешечную недостаточность. В общем, идея такова: есть факторы, влияние которых на ход игры настолько велико, что их превосходство позволяет не считать остальные.

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

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

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

Интересная гипотеза. Интегральный признак

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

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

Конечно, здесь возникает вопрос: что считать контролируемым пространством? Если правила рэндзю не предполагают рубки, а такой возможности, как уже было сказано, нет, то все поля, доступные для одного из игроков, очевидно, доступны и для другого. Пространственный фактор сомнителен и в другой позиционной игре – го. Сама цель игры го формулируется как захват как можно большего пространства. Объявлять же цель игры фактором игры несколько бессмысленно.

Видимо, для того чтобы можно было пространство объявить единым игровым фактором, к нему надо что-то добавить. В отношении рэндзю такая доформулировка выглядит достаточно просто. Будем считать полезным пространством такое, на котором игрок может создать угрозу. Напомним, что в этой игре угрозой считаются открытая тройка (ряд камней, способный следующим ходом превратиться в четверку, пусть даже прикрытую) и любая четверка (ряд камней, способный следующим ходом превратиться в пятерку и таким образом завершить партию победой). Рассмотрим следующий пример (рис. 2.5):

Рис. 2.5. Позиция рэндзю

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

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

Давайте разберемся детальнее с термином «комбинация». Рассмотрим абстрактную игру на стандартной шахматной доске. Два игрока, будем называть их Первый и Второй, ведут борьбу фигурами одинаковой ценности, и пусть в некотором игровом эпизоде они оказывают давление на два пространственных пункта: А и В. Под давлением на пункт будем называть количество ударов (возможностей срубить то, что стоит на этом пункте). Предположим, что давление со стороны каждого игрока на каждый пункт одинаково. Это означает, что ни один из них не сможет выиграть борьбу, если начнет ее первый. Но пусть у Первого фигуры, бьющие пункт А, и фигуры, бьющие пункт В, – это разные фигуры, а у Второго некоторые из фигур участвуют в давлении на оба пункта. Тогда со стороны Первого возможен комбинационный удар. А именно, атаковав один из этих пунктов, он вынуждает Второго отвлечь силы от защиты другого пункта, на который Первый и направит решающие усилия.

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

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

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

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

В общем и целом идея конструирования единого признака лично мне представляется весьма интересной. В моей школе программистов одна из первых игр, сделанных моими учениками, – «война башен» – была реализована на базе именно этой идеи. Начиналась работа с создания довольно объемной оценочной функции, затем, выявляя взаимосвязи факторов, мы отбрасывали их один за другим, в результате получив однофакторную функцию, играющую против человека весьма прилично. После, к сожалению, в стремлении улучшить качество игры оценка опять несколько усложнилась, но это не дало усиления игры. И программу, и описание игры желающие могут найти на www.lotos-khv.ru. Эта практика показала, что реально однофакторная функция потребует глубокого понимания игры, и без какой-то серьезной теории, расшивающей два упомянутых проблемных пункта, не обойтись.

В заключение

Наш анализ построения игровых программ посредством технологии оценочной функции и дерева перебора в основном велся на шахматном материале как наиболее знакомом для большинства потенциальных читателей этой книги. Но общие идеи, очевидно, будут работать для любой игры, и чем игра проще, тем, видимо, технология сработает эффективнее. Есть даже игры, чьи правила и игровое пространство позволяют построить исчерпывающее дерево перебора, а значит, обойтись минимальной оценочной функцией, может быть, даже только с двумя значениями: выиграл, проиграл. Но по-настоящему интересные игры, конечно, такого не позволяют. Как максимум, можно полностью просчитать завершающую фазу игры. Например, это можно сделать в реверси, игре, изобретенной в Германии, и мельнице, пришедшей из древней Средней Азии. Кстати, за счет такой возможности именно реверси стала популярна для разработчиков игровых программ. Имея возможность просчитать последние 10–15 ходов, вполне допустимо проявить некоторую небрежность в середине игры, с учетом, что противник – человек – скорее всего, также будет несколько небрежен. Для сложных игр, повторимся, возможна гипотеза идеальной оценочной функции, позволяющей делать вывод о ходе без просмотра дерева перебора, но это не более чем гипотеза, пока что ни для одной игры подобная эффективно работающая функция построена не была.

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