Полезное для программистов:

Фриланс
Новости
Статьи
   
Рубрики:

Error. Page cannot be displayed. Please contact your service provider for more details. (12)


Описание программы, играющей в калах (ч1)

Поиск:
1. Введение


    

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

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

  2. Правила и нотация


    

Играют двое. Вначале у каждого из игроков имеется по 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

Для указания хода игрока достаточно назвать номер поля; таким образом, запись хода игрока А с первого поля можно обозначать так: А = 1.

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

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

Подобные серии ходов удобно считать одним ходом; записывают такой "составной" ход, перечисляя через запятую номера полей, с которых делаются последовательные одиночные ходы серии. Так, если после хода с первого поля игрок А делает ход со второго поля, это записывается в виде А = 1,2.

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

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

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

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

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

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

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

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

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

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

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

  3. Взаимодействие с программой.



    

На экране текущая позиция представлена двумя рядами полей: сверху располагаются поля игрока 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 нотация с одним исключением: одиночные ходы не отделяются друг друга запятыми - разделителями всюду служат пробелы.


  4. Представление позиции



    

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

Прежде всего, можно отвести каждому игроку по массиву из 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), широко используемая перебирающими функциями.


Автор: algolist






Просмотров: 1750

 

 

Новые статьи:


Популярные:
  1. Как сделать цикличным проигрывание MIDI-файла?
  2. Создание AVI файла из рисунков
  3. Как устройство "отключить в данной конфигурации"?
  4. Kто в данный момент присоединен через Сеть?
  5. Как узнать количество доступной памяти?
  6. Как реализовать в RichEdit разноцветный текст?
  7. Как скрыть свое приложение от ProcessViewer
  8. Как программно нажать/скрыть/показ кнопку "Start"?
  9. Модуль работы с ресурсами в PE файлах
10. Функции вызова диалоговых окон выбора
11. Проверка граматики средствами Word'а из Delphi.
12. Модуль для упрощенного вызова сообщений
13. Функции для записи и чтение своих данных в, ЕХЕ- файле
14. Рекурсивный просмотр директорий
15. Network Traffic Monitor
16. Разные модули
17. Универсальная функция для обращения к любым экспортируем функциям DLL
18. Библиотека от VladS
19. Протектор для UPX'а
20. Еще об ICQ, сообщения по контакт листу?
21. Использование открытых интерфейсов
22. Теория и практика использования RTTI
23. Работа с TApplication
24. Примеры использования Drag and Drop для различных визуальных компонентов
25. Что такое порт? Правила для работы с портами
26. Симфония на клавиатуре
27. Загрузка DLL
28. Исправление автоинкремента
29. Взаимодействие с чужими окнами
30. Проверить дубляжи в столбце


 

 

 
 
На главную