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

Допустим, шахматная ситуация допускает десять ходов игрока. Конечно, реально в шахматной партии, даже если осталась пара фигур, вариантов хода существенно больше, чем десять, но мы для упрощения анализа остановимся на числе в 10 продолжений. Тогда его противник тоже имеет выбор из 10 ходов. Таким образом, ход игрока и реакция его оппонента создадут 100 позиций. Еще пара ходов (игрок – противник), и конечных позиций уже 10 000. Простая арифметика дает астрономическое число. N ходов обоих игроков породят 10N ситуаций. Таким образом, партия в 100 ходов даст 10100 конечных позиций. А значит, даже если бы в каждой позиции действительно было бы возможно только 10 ходов, количество конечных ситуаций практически необозримо.

Есть, правда, вопрос: а зачем анализировать возможные продолжения от исходной позиции до конечной? Вопрос вполне правомерный. Люди-шахматисты, очевидно, не выполняют подобной работы, однако партии в исполнении людей выглядят вполне разумно. Есть, кстати, любопытная легенда об одном из величайших шахматистов всех времен и народов – Хозе Рауле Капабланке. Вроде бы его как-то спросили, как далеко он продумывает игру, на что Рауль ответил: на один ход. Значит, это возможно – не смотреть глубоко.

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

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

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

Рис. 2.3. Дерево перебора

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

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

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