Пользователь
0,0
рейтинг
24 марта 2015 в 16:34

Разработка → Dagaz: Пинки здравому смыслу (часть 4)

imageПусть же вихрем сабля свищет!
Мне Костаки не судья!
Прав Костаки, прав и я!


Козьма Прутков "Новогреческая песнь"
 

Мат и пат, рокировки и взятия на проходе. Может ли какая-то другая игра (кроме Шахмат) доставить большую головную боль разработчикам? Конечно же да! И я уверен, что большинство из вас эту игру знает…

7. Турецкий удар


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

Осетинские шашки, по всей видимости, являются одной из древнейших шашечных игр. Хотя в ней и используется «шашечный» принцип боя (перепрыгиванием через фигуру противника), отличий от привычных нам шашек пожалуй больше чем сходства. В игре не используется шахматная доска. Отсутствует превращение фигур. Фигуры ходят «только вперёд» (по вертикали или диагоналям) на одну клетку и, дойдя до последней линии, теряют возможность выполнять «тихие ходы». Из этой позиции фигуры всё-таки могут продолжать двигаться, поскольку бить фигуры противника разрешается в любом направлении. Самым важным отличием от других шашечных игр является тот факт, что взятие в «Осетинских шашках» не является обязательным. А главным объединяющим фактором является то, что одним ходом можно брать несколько фигур противника сразу! Взятие осуществляется «по цепочке» — выполнив «ударный» ход, фигура может продолжить движение, при условии, что на следующем шаге она возьмёт ещё одну фигуру. 

К вопросу о ''Кенах''
В настоящее время, на территории Осетии, распространена другая интересная шашечная игра. В Кены играют на привычной нам доске 8x8. Начальная расстановка аналогична "Турецким шашкам". На последней горизонтали происходит превращение фигур в дальнобойные дамки (Перец). Ходы фигур также осуществляются по правилам, сходным с применяемыми в «Турецких шашках», за исключением того, что не превращенной фигуре (Кену) разрешено бить назад, а также перепрыгивать через дружественные кены (без боя, конечно), стоящие рядом (аналогичного правила нет ни в одной другой из традиционных шашечных игр).

Правило перепрыгивания через дружественные фигуры может быть понято по разному. Можно ли прыгать назад (если взятие назад разрешено)? Разрешается ли перепрыгивать несколько своих фигур «по цепочке» и, если да, то можно ли перемежать перепрыгивание через свои фигуры со взятием вражеских? К сожалению, все описания «Кенов», которые мне удалось найти, обходят эти вопросы стороной. Единственное, в чём они солидарны — это то, что такое перепрыгивание не разрешается превращенным дамкам (через свои дамки перепрыгивать тоже нельзя). Чтобы как-то разобраться в этом вопросе, я разработал свою реализацию «Кенов» и выложил ролик на YouTube:



Несколько дней назад моё ожидание увенчалось успехом. Sultan Ratrout снабдил меня подробнейшими комментариями по этой игре. Вот что он пишет:

There are some similarities between the two checkers games «Kena» and «Kens» Your implementation of the game is correct. It’s called Ossetian Kena or simply Kena.

Kens is a game influenced by the Osseitan Kena. As for Kens rules, they are found on the websites “di.fc and boardgamsgeek”. Kens has the same rules of Turkish checkers except that Kens cant jump a friendly piece backwards and kens cant jump more than one friendly piece consecutively.
...

Выяснилось, что существует не одна а две похожих игры «Kens» и «Kena» (не исключено, что это разделение произошло именно по причине недостаточно детального описания правил). В одной из них, перепрыгивать назад и «по цепочке» нельзя, в другой — разрешается. По всей видимости, и в том и другом варианте взятие является обязательным.

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

Мы уже потеряли множество настольных игр и продолжаем их терять. Полные правила "Воздушного боя" известны теперь лишь одному безымянному коллекционеру. Мы знаем, что Сталин, по всей видимости, любил настольные игры, но похоже, что теперь уже никто не вспомнит как ходят эти фигуры. Я обращаюсь ко всем читателям. Если вам известны правила экзотических и даже самых обычных настольных игр — делитесь с ними. Уточняйте описания в Wikipedia и других общедоступных источниках. Пишите людям, собирающим правила игр, не стесняйтесь их поправлять, если они ошибаются. Не дайте этим знаниям пропасть безвозвратно!

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



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

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



Первым, в глаза бросается совершенно непривычный для нас способ взятия фигур. Фанорона относится к редкой разновидности «контактных» шашек (другой интересный представитель этого направления — современная игра Bushka). Для того чтобы удалить фигуру противника с доски, нужно подойти к ней вплотную, либо отойти от неё. Удаляется не только атакованная фигура, но и все вражеские фигуры, стоящие за ней по направлению атаки. Пожалуй, этот момент лучше проиллюстрировать:



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

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

В армянских и русских шашках, превращение происходит в процессе боя — фигура, ставшая дамкой, продолжает взятие уже по новым правилам. В турецких, старофранцузских и английских шашках превращение происходит лишь по завершении хода. В турецких шашках, фигура может продолжать бой (если есть такая возможность), но поскольку «рубка» назад запрещена, фигура остаётся в зоне превращения. В старофранцузском и английском вариантах, простая шашка на последней горизонтали просто не может продолжать движение и останавливается.

Кстати
Оригинальным образом решается эта проблема в другой древнейшей игровой системе — "Сенегальских шашках". Превращения фигур, в этой игре, не происходит. Рубка и ходы назад запрещены — фигуры могут двигаться и «рубить» только вперёд и вбок. Шашки, дошедшие до последней горизонтали — просто снимаются с доски! Это правило совершенно лишает игроков стимула к продвижению фигур. Выгодно как можно дольше вести игру в центре доски! Как только фигуры теряют возможность рубить друг друга — игра заканчивается. Побеждает тот игрок, у которого осталось больше фигур.

Забавную метаморфозу претерпевает это правило в международных, 100-клеточных шашках. Превращение, по прежнему, происходит лишь по завершении хода, но «рубка» назад не только разрешена, но и обязательна! Фигура должна продолжать бой и если в его процессе она покидает последнюю горизонталь — никакого превращения не будет, она останется простой фигурой!

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

Во всей своей красе «социальное неравенство» предстаёт в «Итальянских шашках». В этой игре, простая шашка не только не может бить дамку, но и ценится ниже! Требуется бить максимально возможное количество фигур соперника, а при равном их количестве, брать максимальное количество дамок. Своего апогея эта дискриминация достигает в другой итальянской игре. В Damone, помимо дамок есть еще и «императоры», неприкосновенные для всех нижестоящих фигур. Этим игра напоминает Dablot, но, в отличии от последнего, превращения в ней всё же возможны. Простые шашки могут превратится в дамок, а дамки в императоров (повторные превращения запрещены — простая шашка никогда не станет императором).



Приоритет другого рода действует в «Португальских шашках» — если имеется выбор между взятием дамкой или простой шашкой, игрок должен рубить дамкой. Самая сложная формулировка «правила большинства» действует в «Старофранцузских шашках». Позволю себе цитату:

  • Первоначально выбор из двух вариантов взятия был добровольным, вне зависимости от качества и количества шашек, и только в 1653 году было введено Правило большинства (при серийном взятии игрок должен рубить максимально возможное количество).
  • Если при серии взятий можно рубить одинаковое количество шашек простой шашкой или дамкой, игрок обязан брать дамкой. Однако если количество снимаемых шашек одинаково в обоих случаях, но в одной «ветке» есть дамки противника (или их там больше), игрок обязан выбрать именно этот вариант, даже если тогда придется рубить простой шашкой, а не дамкой.
  • Кроме того, ранг снимаемых шашек не имеет значения, серийное взятие подчиняется количеству: брать шашки нужно по максимуму. При выборе взять или 3 простых шашки или 2 дамки игрок обязан взять 3 простых.

Думаю, вы уже поняли, что, в плане реализации, шашечные игры ничуть не проще шахмат. Что предоставляет Zillions of Games, чтобы облегчить жизнь разработчикам? Рассмотрим эти возможности:

  • Частичные ходы, реализуемые командой add-partial
  • Приоритеты ходов, определяемые move-priorities
  • Ряд хитрых настроек настроек, поддерживаемых командой option

Без поддержки частичных ходов ни о какой реализации шашек речи бы не было. Команда add-partial позволяет объединить последовательность взятий в длинный составной ход. Кроме того, эта команда позволяет выполнить превращение фигуры (например, шашки в дамку) при завершении любого частичного хода (эта возможность пригодится в «Русских шашках»). Единожды выполнив взятие, фигура в шашках не может продолжить ход «тихим» перемещением. Она должна продолжать брать фигуры противника. Очевидно, что требуется какая-то возможность для разделения частичных ходов по типам. И такая возможность есть:

Типы ходов
(define man-jump-add (
   if (not-in-zone? promotion-zone)
      (add-partial jumptype)
   else
      (add-partial King jumptype)
))
...
(piece
   (name Man)
   ...
   (moves
      (move-type jumptype)
      (man-capture nw) (man-capture ne)(man-capture sw)(man-capture se)

      (move-type nonjumptype)
      (man-shift nw) (man-shift ne)
   )
)


Если в команде add-partial указан тип хода (jumptype в примере), составной ход может быть продолжен только ходами этого типа. Типы же используются и для задания приоритета ходов:

(move-priorities jumptype nonjumptype)

Эта запись означает, что если существует возможность взятия, «тихий» ход выполнять нельзя. В списке приоритетов можно перечислять и более двух типов, но возможность выполнения хода какого-либо типа полностью запрещает все ходы, типы которых следуют далее по списку. Как определяется «правило большинства»? Очень просто и «хардкорно»:

(option "maximal captures" true)

Можно указать, что при равном количестве фигур следует брать большее количество дамок:

(option "maximal captures" 2)

На этом возможности заканчиваются. Например, нельзя указать, что следует брать минимальное количество фигур (зачем это может понадобиться — другой вопрос). Команда option пригодится и в реализации Фанороны:

(option "pass partial" true)

Дело в том, что игрок не может просто взять и прекратить выполнение составного хода. Такую возможность необходимо явно разрешить. Мне очень не нравится как сама «магия» команды option так и реализация, с её помощью, пропуска ходов (в данном случае, частичных), но это, пожалуй, тема для отдельного разговора.

А как быть с ''Турецким ударом''?
С этим всё сложно. Взятые, в процессе выполнения составного хода, фигуры необходимо помечать (чтобы исключить возможность их повторного взятия), используя атрибуты или превращение фигур. По завершении составного хода, все помеченные фигуры удаляются с доски. Проблема в том, что генератор ходов ZoG не предоставляет какой-либо возможности постобработки. В результате, приходится определять, какой из частичных ходов выполняется последним.

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

Русские шашки
(define international-checker-add
   (if (not-flag? more-captures-found?)
       (if (in-zone? promotion-zone) (change-type King) )
       add
      else  
         (add-partial jumptype)    
   ) 
)

(define international-checker-jump-find
   mark
   (if (on-board? $1)  
     $1    
     (if (and enemy? (empty? $1)(not captured?) ) 
        (set-flag more-captures-found? true)
     )
   )
   back
)

(define shashki-jump   
 (
   $1 
   (verify enemy?) 
   (verify (not captured?))    
   (set-attribute captured? true)
   (set-flag more-captures-found? false)              
   (set-flag short-jump? true)              
   $1                                   
   (international-checker-jump-find $1)
   (international-checker-jump-find $2)
   (international-checker-jump-find $3)           
   (opposite $1)               
   (if (flag? more-captures-found?)                    
       (set-attribute captured? true)     
    else  
       mark  
       capture                            
       a0 
       (while (on-board? nxt) 
         nxt
         (if captured? capture (set-flag short-jump? false))           
       )
       back  
     )

   $1 to
   (verify empty?) 
   (verify (or (not-flag? short-jump?) (flag? more-captures-found?)))
   (if (in-zone? promotion-zone) (change-type King))
   (international-checker-add) 
 ) 
)

...
(variant
   (title "Shashki (Russian Draughts)")
   ...
   (piece
      (name Checker)
      ...
      (attribute captured? false)
      (moves
         (move-type jumptype)
             (shashki-jump nw ne sw)
             (shashki-jump ne nw se)
             (shashki-jump sw nw se)
             (shashki-jump se sw ne)

        (move-type nonjumptype)
             (checker-shift nw)
             (checker-shift ne)
      )
   )
   ...
)


Это часть весьма удачного пакета «шашечных» игр, включающего в себя Белорусские шахматы" (с корректно работающим «матом королём») и «Либерийские шашки» (с очень остроумным запретом завершения игры при трёхкратном повторении позиции), но реализация «Русских шашек» в нём содержит досаднейшую ошибку.

Ответ

В первом случае, всё нормально. Белая шашка берёт две чёрных и превращается в дамку. Вторая диаграмма иллюстрирует ошибку. Белая шашка берёт чёрную, превращается в дамку и остаётся на последней линии, хотя и должна, по правилам «Русских шашек», взять следующую фигуру ходом дамки.

Локализовав ошибку, исправить её просто. Всё дело в проверках international-checker-jump-find, определяющих, имеется ли у хода продолжение. Этот макрос проверяет, можно ли взять следующую фигуру из целевой позиции, но делает это по правилам не превращённой фигуры. Это работает для «Международных шашек», но в «Русских шашках» не учитывает все возможности. Моё исправление не слишком изящно, но решает проблему:

Исправление
+(define shashki-checker-jump-find
+   mark
+   (while (and (on-board? $1) (empty? $1))
+     $1
+   )
+   (if (on-board? $1)  
+     $1    
+     (if (and enemy? (empty? $1)(not captured?) ) 
+        (set-flag more-captures-found? true)
+     )
+   )
+   back
+)

(define shashki-jump   
 (
   $1 
   (verify enemy?) 
   (verify (not captured?))    
   (set-attribute captured? true)
   (set-flag more-captures-found? false)              
   (set-flag short-jump? true)              
   $1                                   
+   (if (in-zone? promotion-zone)
+       (shashki-checker-jump-find $1)
+       (shashki-checker-jump-find $2)
+       (shashki-checker-jump-find $3)           
+    else
       (international-checker-jump-find $1)
       (international-checker-jump-find $2)
       (international-checker-jump-find $3)           
+   )
   (opposite $1)               
   (if (flag? more-captures-found?)                    
       (set-attribute captured? true)     
    else  
       mark  
       capture                            
       a0 
       (while (on-board? nxt) 
         nxt
         (if captured? capture (set-flag short-jump? false))           
       )
       back  
     )

   $1 to
   (verify empty?) 
   (verify (or (not-flag? short-jump?) (flag? more-captures-found?)))
   (if (in-zone? promotion-zone) (change-type King))
   (international-checker-add) 
 ) 
)


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

Кстати, я уже упоминал, в предыдущих статьях, что описания ходов дамок выглядят просто чудовищно. По какой-то причине, команда add-partial не работает внутри цикла (происходит аварийный останов программы), а дамка, во всех вариантах шашек с дальнобойными дамками (кроме "Тайских"), должна иметь выбор, на какое свободное поле, после взятой фигуры, ей приземляться. Конечно, выход был найден:

Ход дамок
(define international-king-jump1      
 ( 
   (international-king-work) 
   to
   (verify (position-flag? allowed?)) 
   (verify (or (not-flag? short-jump?) (flag? more-captures-found?)))
   (international-checker-add)
 )  
)

(define international-king-jump2      
 ( 
   (international-king-work)
    $1 (verify empty?) to
   (verify (position-flag? allowed?)) 
   (verify (or (not-flag? short-jump?) (flag? more-captures-found?)))
   (international-checker-add)
 )  
)

(define international-king-jump3      
 ( 
   (international-king-work)
    $1 (verify empty?) $1 (verify empty?) to
   (verify (position-flag? allowed?)) 
   (verify (or (not-flag? short-jump?) (flag? more-captures-found?)))
   (international-checker-add)
 )  
)
...
(variant
   (title "Shashki (Russian Draughts)")
   ...
   (piece
      (name King)
      ...
      (moves
         (move-type jumptype)
           (international-king-jump1 nw se ne sw)
           (international-king-jump1 ne sw se nw)
           (international-king-jump1 sw ne nw se)
           (international-king-jump1 se nw sw ne)
           (international-king-jump2 nw se ne sw)
           (international-king-jump2 ne sw se nw)
           (international-king-jump2 sw ne nw se)
           (international-king-jump2 se nw sw ne)
           (international-king-jump3 nw se ne sw)
           (international-king-jump3 ne sw se nw)
           (international-king-jump3 sw ne nw se)
           (international-king-jump3 se nw sw ne)
           (international-king-jump4 nw se ne sw)
           (international-king-jump4 ne sw se nw)
           (international-king-jump4 sw ne nw se)
           (international-king-jump4 se nw sw ne)
           (international-king-jump5 nw se ne sw)
           (international-king-jump5 ne sw se nw)
           (international-king-jump5 sw ne nw se)
           (international-king-jump5 se nw sw ne)
           (international-king-jump6 nw se ne sw)
           (international-king-jump6 ne sw se nw)
           (international-king-jump6 sw ne nw se)
           (international-king-jump6 se nw sw ne)
           ...
      )
   )
)


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

В целом, механизмы предоставляемые Zillions of Games вполне работоспособны, если бы не одно но. Реализовать с их помощью «Ossetian Kena», упомянутую под первым спойлером в этой статье, невозможно. Проблема в том, что начиная составной ход мы не знаем, будут ли в процессе его выполнения «съедены» фигуры противника. Кен может перепрыгивать через дружественные кены и бить враждебные, чередуя эти частичные ходы в произвольном порядке, в рамках составного хода.

Очевидно, что «перепрыгивание» и «бой» кеном должны иметь одинаковый тип хода (иначе не удастся построить составной ход, поскольку add-partial может принять только один тип), но этому типу хода не может быть задан более высокий приоритет, поскольку, в противном случае, простые перемещения не будут выполняться практически никогда. Это означает, что правило «обязательного взятия» определить не удастся.

Менее очевидно то, что опцию "pass partial" придётся установить в true (возможность прерывания составного хода игроком). При «перепрыгивании» дружественный кен не удаляется. Обнаружив первый же замкнутый цикл, программа будет прыгать по нему вечно. В редуцированном виде, правила становятся совершенно не играбельными. Обе стороны предпочитают проводить бессмысленные манёвры, а не рисковать своими фигурами, подставляя их под бой противника (это можно видеть в ролике под первым спойлером).

Разумеется, я бы не затевал весь этот разговор, если бы не знал как всё исправить. Для начала, стоит разобраться с тем, что нам мешает в ZRF. Я вижу несколько проблем:

  • Отсутствие пред- и постобработки при генерации ходов (усложняет логику, мешает реализовать противодействие «Турецкому удару» в играх подобных Фанороне)
  • Совмещение функций завершения генерации хода и перемещения фигур в командах add и add-partial (одна из причин, по которой add-partial не может принять несколько типов ходов)
  • Использование типов ходов как для управления построением составного хода, так и для задания приоритетов (механизм приоритетов действует лишь на первый частичный ход, но не на составной ход в целом)
  • Отсутствие универсального механизма реализации «правила большинства» (используя ZRF, корректно реализовать «Старофранцузские шашки» вряд ли получится)

В ZRF определение алгоритма генерации хода монолитно. Нет никакой возможности для выполнения некоего единого кода (до или после выполнения основного алгоритма), в рамках генерации произвольного хода (возможно из некоторой группы), но фактическая потребность в этом есть! Противодействие «турецкому удару» — прекрасная тому иллюстрация.

Из за необходимости определения последнего частичного хода (в рамках составного хода) код становится совершенно нечитаемым и подверженным разнообразным ошибкам. Мало того, этот подход не совместим с досрочным прерыванием составного хода (опция "pass partial"). Конечно, в Фанороне бороться с «турецким ударом» не требуется (в силу специфики механизма взятия фигур, он невозможен), но игры, в которых такая возможность может понадобиться, вполне имеют право на жизнь.

По поводу того, что совмещение функций перемещения фигур и завершения генерации хода — не самая удачная мысль, я уже неоднократно писал ранее. К счастью, в Axiom это исправлено. Что касается приоритетов, то я вообще считаю это решение крайне неудачным. Существует более универсальный подход, позволяющий реализовать и приоритеты и «правило большинства» и многое другое. Посмотрим, как определение «Ossetian Kena» могло бы выглядеть в идеальном мире:

Нарушаемый инвариант
(define invariant
   (check (>= capturing-count max-capturing-count))
   (set! max-capturing-count capturing-count)
)

(define goals
   (check-loss no-moves?)
)

(define check-promotion
   (if (in-zone? promotion)
       (promote King)
   )
)

(define check-friend
   (check is-friend?)
   take-piece
)

(define (man-move direction)
   (check direction)
   (check is-empty?)
   drop-piece
   add-move
)

(define (man-jump direction)
   (check direction)
   (check is-friend?)
   (check direction)
   (check is-empty?)
   drop-piece
   (add-move-part jump-type)
)

(define (man-capture direction)
   (check direction)
   (check is-enemy?)
   (increment! capturing-count)
   capture
   (check direction)
   (check is-empty?)
   drop-piece
   (add-move-part jump-type)
)
...
(game
   (title "Ossetian Kena")
   ...
   (pieces
      (attribute capturing-count 0)
      (pre  goals)
      (post invariant)
      (piece 
            (name Man)
            (pre  check-friend)
            (post check-promotion)
            (moves
                (mode normal-type)
                (man-move n)  (man-move w)  (man-move e)
            )
            (moves
                (mode jump-type)
                (man-jump n) (man-jump w) (man-jump e) (man-jump s)
                (man-capture n) (man-capture w) (man-capture e) (man-capture s)
            )
      )
      (piece 
            (name King)
            ...
      )
   )
)


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

Иного рода проверки расположены в глобальном разделе описания pieces. Этот код выполняется до и после завершения всего составного хода (именно здесь должно выполняться превращение фигур в «Международных шашках»). Здесь же, фразой attribute можно определять переменные, доступные на любом этапе выполнения составного хода. В capturing-count мы подсчитываем общее количество взятых фигур. Инвариант заключается в том, что это значение не должно быть меньше максимального количества фигур, взятых во всех сгенерированных ходах.

Но как это может работать? Хорошо, если ходы будут генерироваться в направлении уменьшения количества взятых фигур (тогда новые варианты будут отбрасываться при проверке), но мы не можем гарантировать такой порядок генерации ходов! Здесь можно пойти на маленькую хитрость. Помимо проверки, можно сформировать отложенное условие, ассоциированное с каждым сгенерированным ходом. Если, при генерации последующего хода, значение max-capturing-count изменится, потребуется вновь перепроверить все ранее сгенерированные ходы (их не придётся перегенерировать заново) и отсеять те из них, для которых условие более не выполняется.

Этот механизм подобен тому, который я предлагал для «оптимизированного» вычисления условия завершения no-moves?. Слишком накладно каждый раз выполнять генерацию ходов лишь для того, чтобы определить проигрыш игрока. Гораздо разумнее зарегистрировать отложенную проверку, сгенерировать ходы обычным образом и зафиксировать поражение постфактум, если полученный список ходов пуст. В случае инвариантов, этот механизм используется не в целях оптимизации, а для обеспечения корректного их вычисления. Это то, что я называю "нарушаемым инвариантом" и я считаю, что эта концепция будет мне очень полезна при разработке генератора ходов. Во всяком случае, она гораздо универсальнее механизмов предлагаемых Zillions of Games и Axiom Development Kit.
Валентин @GlukKazan
карма
119,2
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (4)

  • +1
    Я впечатлен, какое разнообразие шашек, оказывается, успели придумать люди.
  • 0
    В таком случае, думаю стоит почитать и вот это.
    Прошу прощения, промахнулся веткой.
  • +1
    Шикарная статья!

    Вообще может похдодить в подобных играх не с интегральной точки зрения, а диференциальной?
    Ибо надо дать возможность записать эти правила просто, и чтобы можно было автоматически реализовать их.
    • 0
      Спасибо. Не вполне понял мысль на счёт интегрального и дифференциального подхода, думаю об этом стоит отдельно пообщаться.
      Хочется максимально декларативного DSL для описания правил настольных игр. Не как в ZoG. Там слишком много императива.
      И не как в Axiom, там вообще Forth.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.