Павел Н. Дубнер
18 Мая 1998 г.
e-mail: infoscope@writeme.com

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

Данный текст содержит описание программы, играющей в КАЛАХ. Программа задумывалась как иллюстрация к переводу статьи Д.Кнута и Р.Мура об организации перебора при поиске хода. В качестве иллюстрации был выбран КАЛАХ - не из-за того, что это такая уж популярная игра, и не потому, что она так уж интересна. Соображения были достаточно банальными.

С одной стороны, хотелось выбрать игру достаточно сложную, чтобы применение в ней методов сокращения перебора дерева игры было "по делу"; приводимые в большинстве книжек (см., например, [Нильсон]) примеры типа игры в крестики-нолики на поле 3*3 вызывают у меня аллергию. С другой стороны, не хотелось тратить время и усилия на программирование пользовательского интерфейса, а для КАЛАХа все необходимое можно осуществить тривиальными средствами.

Играют двое. Вначале у каждого из игроков имеется по 36 камешков (конечно, любых мелких равноценных предметов); камни расположены поровну на шести полях, пронумерованных слева направо. Поля соперников расположены друг против друга. Кроме того, каждый игрок имеет по специальному полю, называемому "калах" и расположенному справа от шестого игрового поля. Вот как можно изобразить начальную позицию:

                     Поля игрока B
               +-----------------------+
               | 6   5   4   3   2   1 | -- номера позиций
    +----------+-----------------------+----------+
    | Калах    | 6 | 6 | 6 | 6 | 6 | 6 |  Калах   |
    | игрока B |---+---+---+---+---+---| игрока A |
    |          | 6 | 6 | 6 | 6 | 6 | 6 |          |
    +----------+-----------------------+----------+
               | 1   2   3   4   5   6 | -- номера позиций
               +-----------------------+
                    Поля игрока A

0 6 6 6 6 6 6   - Поля игрока B
  6 6 6 6 6 6 0 - Поля игрока A

0 6 6 6 6 6 6
  0 7 7 7 7 7 1

Если ход закончился в своем калахе (т.е. последний из распределяемых камней попал в свой калах), то игрок делает еще один ход. Так, начавший игру в предыдущем примере, должен пойти повторно - например, со второго поля, придя к позиции

0 6 6 6 6 7 7
  0 0 8 8 8 8 2

Во всех остальных случаях очередь хода передается противнику. Это и произошло сейчас в начатой нами партии. Противник может ответить ходом с первого поля (как мы вскоре увидим, неудачным): ход B = 1 приводит к позиции

1 7 7 7 7 8 0
  1 0 8 8 8 8 2

1 7 0 7 7 8 0
  0 0 8 8 8 8 10

Разумеется, чтобы определить победителя, можно не дожидаться опустошения чьих-либо полей: калах может только пополняться, и тот, кто набрал больше половины камней, уже не может проиграть. Продолжать игру в таком случае стоит лишь для того, чтобы выразить исход партии точным счетом.

Подведем итоги формулировкой правил игры.

ПРАВИЛО 1. Игроки ходят по очереди.

• 1.1. При очередном ходе играющий снимает с одного из своих полей все камни и распределяет их по одному на последующие поля в порядке возрастания их номеров; полем, следующим за шестым, считается свой калах. Далее камни распределяются по чужим полям (опять-таки в порядке возрастания их номеров), затем вновь по своим (чужой калах пропускается) и так далее, как бы совершая обход полей против часовой стрелки.
• 1.2. Если последний из распределяемых камней попал в "свой" калах, то игрок делает еще один ход. Во всех остальных случаях очередь хода передается противнику.
• 1.3. Если последний камень попал на пустое поле игрока, совершавшего ход, а на противоположном поле соперника есть хотя бы один камень, то содержимое обоих полей переносится в КАЛАХ игрока, совершавшего ход (после чего, согласно правилу 1.2, ход переходит к его противнику).
• 1.4. Если на полях игрока, сделавшего ход, не остается ни одного камня, то все камни, находящиеся на полях противника, переносятся в калах противника, и игра заканчивается.

ПРАВИЛО 2. Игра заканчивается, когда одному из противников нечем ходить.

ПРАВИЛО 3. Выигрывает тот, у кого по окончании игры в калахе оказалось больше камней. Если в обоих калахах находится по 36 камней, фиксируется ничья.

На экране текущая позиция представлена двумя рядами полей: сверху располагаются поля игрока B, снизу - поля игрока А. Над каждым полем игрока B и под каждым полем игрока A находится номер этого поля. Номера полей игрока A меняются от 0 до 5, игрока B - от 7 до 11; номера используются для обозначения ходов. Слева от полей находится калах игрока B, справа - калах игрока A. На экране "имена" A и B нигде не указаны, эти обозначения используются лишь в файле, содержащем запись сыгранной партии (см. ниже).

В данной версии игрок B - обязательно программа. Игроком А может быть либо человек, либо сама программа.

Когда очередь хода принадлежит человеку, в верхнем левом углу появляется надпись: "Введи ход:". В ответ нужно ввести номер поля, с которого хочется пойти. Если указано допустимое поле, производится соответствующее раскладывание камней, причем если в результате хода последний камешек попал в свой калах, вопрос повторяется. Если указано пустое поле или нажата неверная клавиша, раздается писк и запрос повторяется. Если в ответ нажать клавишу ESC, происходит выход из программы.

Когда программа начинает думать, в левом верхнем углу появляется мигающая надпись "Думаю...". После того, как ход найден, эту надпись сменяет другая: "Пойду с {X}". На месте, обозначенном здесь {X} может стоять один или более номеров полей, с которых будут производиться ходы. Например, может появиться: "Пойду с 7 8 9 10". Чтобы программа сделала каждый из перечисленных ходов, нужно нажать клавишу ENTER. Если найден составной ход, то после каждого из одиночных ходов надпись "Пойду..." повторяется, причем последовательность {X} сдвигается влево. Так, после приведенной в качестве примера надписи нажатие клавиши ENTER приводит к соответствующему изменению позиции на экране и появлению надписи: "Пойду с 8 9 10". После того, как сделан последний одиночный ход, программа переходит к запросу ходов игрока.

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

Сыгранная партия сохраняется в файле lastgame.klh. Используется описанная в разделе 1 нотация с одним исключением: одиночные ходы не отделяются друг друга запятыми - разделителями всюду служат пробелы.

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

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

Вспоминая, что камни со своего поля могут попасть и на поля противника, предпочтем второе представление: будем представлять позицию массивом desk[14], в котором элементы desk[0]..desk[5] - поля игрока A, desk[6] - его калах, элементы desk[7]..desk[12] - поля игрока B, а desk[13] - калах игрока B. Ход будем представлять номером поля, с которого нужно начать раскладывать камешки.

Итак, пусть desk[14] - позиция, move - ход, который нужно сделать. Трудностей при реализации ровно две: во-первых, нужно пропустить калах противника, во-вторых, камней может быть столько, что придется обойти поля игроков более одного раза. Из-за этого не удается организовать обычный цикл. Функция scatterStones реализует описанные действия. Она возвращает 1, если последний камень попал в "свой" калах, и 0 в противном случае. Возвращаемое значение используется для проверки применимости правила 1.2. Применением правила 1.3 "заведует" сама функция scatterStones.

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

Значение, возвращаемое функцией scatterStones, используется при проверке применимости правила 1.2. Между прочим, из-за этого правила не удается представлять ход одним числом - номером поля. Будем называть вынуждающим ход, при котором последний из распределяемых камней попадает в "свой" калах; позицию, получаемую в результате вынуждающего хода, - вынужденной, все остальные - невынужденными. Ходы, которые делаются из вынужденной позиции, будем называть вынужденными или форсированными. Например, позиция, получаемая из начальной после хода A = 1, является вынужденной. Вынужденные позиции не нужно оценивать, оценивать нужно лишь невынужденные позиции. Продолжим приведенный пример: оценивать нужно позиции, получаемые в результате одного из ходов A = 1,2; A = 1,3; A = 1,4; A = 1,5; A = 1,6. Естественно считать, что позиции, непосредственно получаемые из вынужденной, все являются сыновьями отца этой вынужденной позиции. При этом следует учитывать, что ход, следующий за вынуждающим, может оказаться сам вынуждающим - отцом любого хода из серии вынуждающих является отец первого из них. Мы видим, таким образом, что описанный в разделе 1 "составной ход" оказался полезным не только для сокращения записи.

Итак, в структуре, представляющей узел дерева игры, будем хранить одиночные ходы в массиве move, размерность которого выберем заведомо превосходящей все мыслимые пределы; при этом понадобится еще переменная, в которой хранится текущее количество "одиночных" ходов, представляющих "составной". Таким образом, приходим к структуре следующего вида:

typedef struct treeNode { 
  int forced;   /* Кол-во вынужденных ходов. */ 
  int move[30]; /* Ход в данную позицию */ 
  int desk[14]; /* Поля и калах игроков: */
                /* A (0..6) и B (7..13). */
} NODE,*PNODE;
   

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

Обращу особое внимание на то, что в массиве move хранится ход из предыдущей позиции в ту, которая отражена в массиве desk. Это, в частности, означает, что если move[0] < 6, то ходил игрок А, и, значит, в текущей позиции ходить должен игрок В; наоборот, если move[0] > 6, то ходил игрок В, поэтому в текущей позиции ходить должен игрок А. На этом простом наблюдении построена функция Aplays (реализуется макросом, определенным в файле kalah.h), широко используемая перебирающими функциями.

Для поиска лучшего хода воспользуемся идей, которую иллюстрирует процедура F2 из статьи Кнута и Мура. Вот ее слегка переделанный текст на придуманном Д.Кнутом алголо/паскале-подобном языке:

integer procedure F2(ref(position) p,integer alpha,integer beta): 
begin integer m,t; ref(position) q; 
   generate(p); 
   q := first(p); 
   if q = NULL then F2 := f(p) else 
    begin m := alpha; 
     while q <> NULL and m < beta do 
      begin t := -F2(q, -beta, -m); if t > m then m := t; q := next(q); 
      end; 
     F2 := m; 
    end; 
end.
  

Вызов функции generate формирует всех сыновей исходной позиции в некотором порядке. Входным параметром функции generate является адрес p узла, для которого нужно сгенерировать поддерево. Вызовом функции first процедура F2 получит первого из сыновей позиции p, если он имеется. Последовательные вызовы next доставляют следующих по порядку сыновей позиции p (обратите внимание - сыновья, получаемые в результате вызова next, находятся на том же уровне дерева игры, что и первый, полученный вызовом first). Когда при обходе дерева игры будет достигнута терминальная позиция, вызов first/next даст NULL.

Применение процедуры F2 представляется совершенно тривиальным. Нужно порождать узлы очередного уровня дерева игры при каждом вызове процедуры generate; освободить занимаемую деревом память можно по окончании оценки исходной позиции. На первый взгляд все это выглядит совершенно замечательно, однако, следует принять во внимание, что совершенно нет необходимости реально строить полное дерево игры, расточая память и время. Для прохода деревьев имеется стандартная техника - использование стека; см. первый том замечательного "Искусства программирования для ЭВМ" Д.Кнута. Каждому вызову generate/first соответствует операция проталкивания (push) в стек, а когда first/next возвращает NULL, мы убираем (pop) из стека текущий узел, переходя к анализу узла, лежащего в стеке "ниже".

Когда first возвращает NULL, позиция p оценивается напрямую - в программе это делает функция estimate, которая возвращает попросту разность камней, находящихся в калахах противников. Однако, за разумное время достичь терминальной позиции удается лишь в самом конце игры, поэтому в начале и середине игры мы вынуждены ограничивать глубину просмотра: объявлять терминальными узлы, находящиеся на уровне, большем заданного, и вводить оценочную функцию для них.

Стандартный способ ограничения глубины просмотра заключается в том, что функция generate(p) НЕ генерирует сыновей позиции p, если уровень p превосходит константу MAXLEVEL, ограничивающую глубину просмотра. Эту константу будем считать параметром, задаваемым извне программы. Когда глубина просмотра превосходит заданный уровень, функция first возвращают NULL.

Идею, иллюстрируемую процедурой F2, в программе реализует функция ABprune. Ниже содержатся комментарии к этой реализации. Сразу обращу внимание на отличие ABprune от приведенного выше "канонического" варианта F2: отсутствует вызов функции generate - вместо нее добавлены операторы, управляющие текущим уровнем дерева игры.

Текущий уровень рассматриваемых узлов дерева игры содержится в переменной cL. Перебирая позиции уровня cL, будем использовать cL-й элемент массива wStack типа NODE. Процедура first инициализирует cL-й элемент этого массива, а процедура next увеличивает на 1 поле move и возвращает NULL, если значение этого поля вышло за допустимые пределы.

Функция first проверяет значение cL: если оно сравнялось с максимально допустимым уровнем перебора, функция возвращает NULL, в противном случае устанавливаются поля cL-го элемента массива wStack, после чего вызывается процедура next, которая пытается сделать очередной допустимый ход. Устанавливаемое значение wStack[cL].move[0] - "предпервое", оно будет увеличено в функции next.

Несколько сложнее устроена функция next. Ее входным параметром является оцениваемый узел p. Используя информацию об исходной позиции, содержащуюся в p->desk, и текущую позицию, содержащуюся в cL-м элементе стека wStack[cL], функция next формирует следующую позицию, если она есть.

Прежде всего нам нужно "вернуть" позицию, которая была на поле до того, как был сделан последний ход. Все очень легко, если в эту позицию мы прибыли непосредственно из позиции p, заданной входным параметром, если между ними не было вынужденных позиций. В этом случае нам достаточно скопировать позицию из p в wStack[cL]. Если же были сделаны форсированные ходы, wStack[cL].forced > 0 и, значит, нам нужно получить позицию, получаемую из позиции p->desk форсированными ходами wStack[cL].move[0], wStack[cL].move[1],..., до хода с номером wStack[cL].forced-1. Соответствующие действия реализует функция retPos.

Очередной ход должен быть сделан с непустого поля, номер которого больше поля, ход с которого мы рассматривали ранее. При этом необходимо учесть, куда попадает последний камень; функция scatterStones возвращает 1, если он попадет в свой калах. Если сделанный ход приводит в вынужденную позицию, увеличивается на 1 значение поля forced структуры, соответствующий элемент массива move устанавливается в "предпервое" состояние и поиск хода повторяется. Если допустимого хода нет, функция пытается уменьшить содержимое поля forced - ведь текущая позиция могла быть получена из вынужденной. Когда значение forced равняется нулю, и допустимого хода нет, функция возвращает NULL. Если же forced > 0, процесс поиска хода повторяется.

Вспомним еще, что нам нужно управлять текущим уровнем дерева игры (глобальная переменная cL). Наиболее естественно было бы увеличивать ее в процедуре first и уменьшать в next. При этом, однако, возникают трудности согласования работы first/next с перебором: вовсе не обязательно процедура next доработает до конца - посмотрите на второе условие выхода из цикла в F2. Поэтому было принято решение изменять переменную cL внутри процедуры ABprune.

Поговорим еще немножко об оценке терминальных позиций. Из множества возможностей здесь выбрана простейшая: оценкой позиции является разность количества камней в калахах противников. Ясно, что если в позиции ход сделал игрок А, его выигрыш равен desk[6] - desk[13], если же ход сделал игрок B, он выигрывает desk[13] - desk[6]. Это вычитание и реализует приведенная в программе функция estimate.

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

Одна из них основана на понятии активности поля. Ее принимают равной количеству камней, попадающих при ходе с этого поля на свои поля (но не в калах), минус количество камней, попадающих при этом на поля противника, плюс семь. Добавление семерки делается для того, чтобы активность всякого непустого поля была положительной. Активность пустого поля по определению равняется нулю. Сумму активностей всех полей обозначим через D_a и D_b, количества камней, попадающих в калахи, - через K_a и K_b. В журнале "Electronische Rechenanlagen" (1970, No.1) немецкий математик П.Рехенберг описал программу, оценочная функция в которой равнялась W = K_a*D_a - K_b*D_b. Сведения взяты из журнала "Наука и жизнь", 1971, N 12, с. 106- 114.

В этом же номере журнала "Наука и жизнь" рассмотрена и другая оценочная функция, предложенная Г.С.Цейтиным:

W = (K_a + 17.3/(37-K_a) - 40/D_a) - (K_b + 17.3/(37-K_b) - 40/D_b).

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

В проведенном соревновании программ П.Рехенберга и Г.С.Цейтина победила последняя, хотя и не с подавляющим результатом.

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

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

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

Рискну утверждать, что такие средства нужны всегда и, чтобы не ходить за примером далеко, скажу, что по моему мнению в приведенном коде есть какая-то тонкая ошибка, найти которую без инструментария мне не удалось. А индикатором наличия ошибки для меня служат некоторые партии, в которых программа играет "странно" - с моей точки зрения. Вот пример такой странной партии:

Игрок A : Программа
Игрок B : Программа
Первым ходил игрок A

 1) A: 0 3 B: 11 
 2) A: 5 B: 7 
 3) A: 2 B: 11 9 
 4) A: 3 5 B: 11 
 5) A: 2 B: 12 
 6) A: 5 3 B: 8 
 7) A: 0 5 4 5 B: 11 10 
 8) A: 5 4 5 1 B: 11 9 8 
 9) A: 2 B: 10 11 12 
10) A: 5 B: 7 
11) A: 4 B: 9 
12) A: 5 3 B: 9 
13) A: 5 4 B: 10 12 11

Конечно, быть может, программа работает верно (но что значит "верно" в подобном контексте?), а странность вызвана малой глубиной МОЕГО перебора: я просто не вижу того, что видит программа.

Я был бы рад узнать от кого-нибудь правду об этой программе.