Пользователь
27,4
рейтинг
12 марта 2015 в 18:27

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

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

                          Михаил Булгаков «Мастер и Маргарита»
 

«Мат королю!» — многие из нас впитали эти слова с молоком матери. Сама концепция шаха (и мата) кажется очевидной людям знакомым с Шахматами с детства, но так ли она проста на самом деле? После лёгкой разминки с превращениями фигур, я предлагаю заняться действительно сложными вопросами.

8. Шах и мат


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

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

Пример кажется странным, поскольку сама суть «крестиков-ноликов» заключается в выстраивании линий? Вот вам менее очевидный пример: в Hasami Shogi фигуры могут двигаться и «поедать» друг друга. Для того, чтобы убрать фигуру противника с доски, её необходимо «взять в клещи», окружив своими фигурами с двух сторон (на самом деле, правила взятия в Hasami Shogi более сложные, но об этом я расскажу как-нибудь в другой раз). Это правило роднит Hasami Shogi с древнейшими игровыми системами «окружных шашек», такими как Seega.

Логично предположить, что, как и в Seega, в Hasami Shogi, для победы, необходимо «съесть» все фигуры. Действительно, такой вариант игры существует, но и в нём достаточно взять не все, а лишь ограниченное количество (обычно 5) фигур. Дело в том, что используемый способ взятия (зажиманием «в клещи») весьма медлителен. Для того, чтобы взять фигуру противника, необходимо должным образом разместить две своих фигуры (разумеется, это не отменяет того факта, что одним ходом можно брать несколько фигур сразу). В Seega ситуацию спасает ограниченная подвижность фигур, но в Hasami Shogi фигуры дальнобойные и противник практически всегда может избежать угрозы.


Правило «внезапной смерти» оказывается как нельзя кстати. В большинстве вариантов Hasami Shogi, победа достигается выстраиванием «в ряд» 5 своих фигур (за пределами их первоначального расположения, иначе было бы не интересно). Взятие фигур противника в них является не целью игры, а лишь тактическим приёмом, помогающим победить. Здесь, как и в «Крестиках-ноликах», условием победы является относительное расположение фигур.

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


Условие «внезапной смерти» может быть связано и с абсолютным расположением фигур. Так, в китайской игре Доу-шу-ци (Джунгли), для победы, необходимо привести любую из своих фигур в «Логово» противника (отмеченное место на доске). Аналогичное правило вносит тактическое разнообразие в японскую игру Doubutsu Shogi. В ней для, для победы, достаточно провести своего короля на последнюю горизонталь доски (при этом, потеря короля — означает поражение). Сходные правила действуют в играх семейства Тафл, но там королевская фигура есть лишь у одной из сторон (это несимметричные игры).

Как я уже говорил выше, наиболее привычная нам трактовка «правила внезапной смерти» связана с потерей главной фигуры или группы фигур. Именно в таком виде оно использовалось в древнейших шахматных играх, таких как Чатуранга. В этой игре требовалось «съесть» вражеского короля («оголение» короля, то есть взятие всех остальных фигур, также считалось победой). Если говорить о варианте игры для четырёх игроков, то подобная трактовка правил завершения игры является, пожалуй, наиболее разумной. До победы одного из игроков играть гораздо интереснее чем до первого проигрыша.

С этим было связано одно недавнее изменение, которое Howard McCay внёс в мою реализацию Yonin Shogi (вариант японских шахмат для четырёх игроков). Помимо адаптации игры под более раннюю версию Zillions of Games 1.0, он изменил условие победы. Теперь игра не заканчивается взятием одного из вражеских королей. Для победы, необходимо «съесть» их всех! Более того, взятых королей можно выставлять на доску как свои фигуры! В таком виде игра стала гораздо интереснее.


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

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

Честь изобретения (почти) современной шахматной игры принадлежит персам. По всей видимости, именно в Шатрандже были объединены понятия «главной фигуры» и форсированных ходов. Так появилось понятие шаха — король не должен оставаться под ударом по завершении хода того игрока, которому он принадлежит. Ход, избавляющий короля от угрозы, является форсированным (не важно, взятие ли это угрожающей фигуры или просто уход в более спокойное место).

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


До сих пор всё выглядело вполне логично, но что будет если усложнить правила? Например, как поставить мат нескольким королям? В "Шахматах-Тамерлана" игрок может получить до трёх королей, выполнив превращение королевской пешки и двойное превращение «пешки пешек». В "Тю Сёги" ситуация аналогична — «Пьяный слон» может превратиться в «Крон-принца» (фактически второго короля).

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

Не менее интересны метаморфозы понятия шаха при игре более чем двух игроков. Я уже упоминал выше о Yonin Shogi. Единственное её отличие от традиционных Сёги — участие в игре четырёх игроков (и, как следствие, другая начальная расстановка фигур). Результатом этого «небольшого» отличия стала совершенно неадекватная обработка шахов в Zillions of Games версии:



И это больше чем просто баг одной конкретной реализации! Давайте немного подумаем. Допустим игрок «Юг» ставит своего короля под удар одной из фигур игрока «Восток», но пока до того дойдёт ход (по часовой стрелке), угроза может быть ликвидирована «Западом» или «Севером» (вероятнее последним, если игра идёт «пара на пару»). Следовательно никакой угрозы не было и «Юг» имел право сделать такой ход! А если «Север» и «Запад» не стали предпринимать ничего в отношении этой угрозы? Как можно видеть, в такой игре понятия шаха и мата имеют мало смысла.

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


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

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

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

Уфф… В этом и разобраться то непросто, не то что реализовать. Кстати говоря, с реализацией шахов и матов в ZoG всё довольно печально. В условиях завершения игры (победы, ничьей или поражения) могут применяться лишь следующие предикаты:

  • stalemated — Отсутствие возможности хода
  • repetition — Троекратное повторение позиции
  • captured — Взятие фигуры определённого типа (например короля)
  • checkmated — Мат фигуре заданного типа
  • absolute-config — Абсолютное расположение фигур (например достижение заданной позиции)
  • relative-config — Относительное расположение фигур (например «5 в ряд»)
  • pieces-remaining — Оставшееся количество фигур (например, в "Мельнице" — две оставшиеся фигуры означают поражение)
  • total-piece-count — Аналогично предыдущему, но без учёта принадлежности фигур игроку

Всё это жёстко «зашито» в ядро программы и минимально управляется другим «хардкодом» — командой option (доступной лишь в версии 2.0). Например, при помощи опции "include off-pieces" можно заставить систему учитывать в предикате pieces-remaining не только фигуры размещённые на доске, но и те, что находятся «в резерве». Какой либо системы в наборе доступных опций нет.

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

Утифудзумэ вручную
(define safe 
   (and (on-board? $1) 
        (not-defended? $1) 
        (not-enemy? $1)
   )
)

(define no-mate 
   (or (not-piece? Gyokusho n) 
       (not-enemy? n) 
       not-defended? (attacked? no-king) 
       (safe e) 
       (safe w) 
       (safe ne) 
       (safe nw) 
       (safe nne) 
       (safe nn) 
       (safe nnw)
   )
)

(define drop-Fu (
 (verify-first Fu)
  END next
  (while on-board?
    mark 
    (set-flag friendly-Fu false)
    (while (and (not-flag? friendly-Fu) (on-board? n))
      (if (and friend? (piece? Fu)) (set-flag friendly-Fu true))
      n)
    back
    (if (not-flag? friendly-Fu)
	mark
	(while (on-board? n)
	  (if (and empty? (no-mate)) add)
	  n)
	back)
    e)
))


Это работает, но понять, что делает этот код, крайне сложно. При этом, используется тот факт, что пешка в Сёги атакует вплотную, всего одно поле. От её шаха нельзя закрыться, а можно лишь отойти либо «съесть» пешку. Совершенно не представляю каким образом подобный комплект «ручных» проверок выглядел бы в случае реализации Шатар. Для реализации форсированных ходов используется механизм приоритетов (либо жестко закодированная «магия», при использовании предиката checkmated).

Приоритеты
...
(moves
    (move-type noncapture-type)
    (man-shift ne)
    (man-shift nw)

    (move-type capture-type)
    (man-jump ne)
    (man-jump nw)
    (man-jump se)
    (man-jump sw)
    (move-type nomove-type)
)
...
(move-priorities capture-type noncapture-type)


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

Реализация проверок на шах в Dagaz
(define invariant
  (check 
      (not-exists?
         any-position
         (check is-friend?)
         (check (is-piece? King))
         (check is-attacked?)
      )
  )
)

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

(pieces
   ...
   (pre  goals)
   (post invariant)
   ...
)


Кстати
Вычисление предиката is-attacked? — довольно таки трудоёмкая операция (именно поэтому она выполняется в конце списка проверок). Дело в том, что далеко не во всех играх атакуются те поля, на которых фигуры заканчивают свой ход. Примером являются всем известные Шашки, в которых атакуемое поле «перепрыгивается».

В более сложных случаях, результат вычисления is-attacked? зависит от того, какой тип фигуры атакуется. Например «Хамелеон» в игре Ультима атакует каждую фигуру по тем правилам, по которым ходит она сама. Если бы в подобной игре была предусмотрена рокировка, пришлось бы уточнять для какого именно типа фигуры выполняется проверка (для проверки на шах этого делать не требуется, поскольку фигура уже установлена на доске, а не просто проходит через поле):

Рокировка в Dagaz
(define O-O
   (check (not is-moved?))
   (check not-attacked?)
   (take-piece-to-head current-pieces)
   (check w)
   (check is-empty?)
   (check (not-attacked? King))
   (check w)
   (check is-empty?)
   (check (not-attacked? King))
   (drop-pieces current-pieces)
   (check w)
   (check (not is-moved?))
   (set! is-moved? true)
   (take-piece-to-head current-pieces)
   e e
   (drop-pieces current-pieces)
   add-move
)



Это немного длиннее простого checkmated, но и невероятно гибче! В случае, если все возможные ходы нарушают инвариант, список сгенерированных ходов оказывается пустым. Срабатывающий в этой ситуации предикат no-moves? определяет условие завершения игры (поражения).

Маленький хак
Вычисление предиката no-moves? также может быть трудоёмким (для проверки необходимо полностью сгенерировать хотя бы один ход), но здесь можно схитрить. До начала генерации ходов можно зарегистрировать отложенную проверку. Если множество ходов, по завершении генерации, пусто, проверка срабатывает и фиксируется поражение.

Инварианты, в том виде как они определены в этой статье, не кажутся какой-то «ракетной наукой», но мы ещё не дали им развернуться в полную силу. В следующей главе, постараемся выжать из них максимум того, на что они способны.
Валентин @GlukKazan
карма
121,2
рейтинг 27,4
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

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

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

  • +2
    Очень интересно! Спасибо!
    • +1
      Это всегда пожалуйста
  • 0
    Я так понимаю, что в шахматах правила форсированых ходов при шахе напрямую следуют из условий проигрыша. То есть, если бы игрок был не обязан уводить короля из под удара, то это всё равно не имело бы смысла делать. Так как игрок, оставивший короля под ударом тут же бы проиграл.
    А пат в этом случае был бы проигрышем, так как вынуждал игрока самого встать под удар.
    • 0
      Этот момент можно рассматривать с двух концов. Мне сейчас удобнее думать, что понятие мата следует из инварианта не попадания под шах. Проигрыш в виду отсутствия ходов это более универсальная концепция (хотя никто не мешает определить, например, пат как ничью или даже выигрыш). Что касается инвариантов… они могут быть очень разные. Вот здесь, например, инвариантом является то, что группа из одноцветных камней не должна разделяться.

      Видео

  • 0
    Несколько уточнений.

    Ответить на шах можно тремя способами:

    • уйти
    • взять шахующую фигуру
    • закрыть линию удара (если шах даёт линейная фигура).

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

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

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

      Если игрок не может сделать по правилам ни одного хода, он пропускает свой ход, но если какой-либо ход возможен, отказаться от своего хода нельзя. В старину существовало правило: если у одного игрока остался только «голый» король, который попал в пат, ему давалась льгота – возможность пропустить ход. Считалось, что одинокий король делал особый ход – вращался на месте (фишку действительно крутили, не сдвигая с места). В принципе, даже в шахматах нередки случаи, когда следующим ходом противник в ходе пата вынужден был бы разблокировать короля. Таким образом, в чанги пат надо было ставить на ДВА ХОДА вперёд, дабы неприятельский король как-нибудь ненароком не выкрутился.
      • 0
        Уф, какие запутанные правила у чанги. Насколько я понял, запрещается «прокручивать короля» два раза подряд.

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

        Так вот, моя идея в том, что игрок имеет право пропустить ход (независимо от того, пат ему или нет), тогда соперник имеет право немедленно остановить партию, взяв себе 3/4 очка, а может продолжить как обычно. Пока затрудняюсь сказать, обогатит ли эта модификация обычные правили или наоборот. Например, маневр «бешеная фигура» лишается всякого смысла; часть окончаний меняет свою оценку с ничейной до выигрышной. Можно рассматривать эту модификацию как способ повышения результативности партии (если кого-то всё еще беспокоит проблема ничейной смерти).
        • 0
          В Чанги да, пропускать ход можно лишь однократно. По поводу остановки партии по пропуску хода идея интересная. Немного похоже на нормальное завершение партии в Го (в том смысле, что никто не сдался). Там любой игрок может пропустить ход, но если другой игрок тоже пропустил ход, начинается подсчёт очков и завершение партии (в разных системах есть нюансы).
  • +1
    формализовать подобные правила — ещё та задача!
    • 0
      Ну да, Бегемот прав. Нельзя вот так вот сходу взять и сказать «Вам мат!». Надо разобраться, в какой фазе Луна, сколько королей на доске, сколько из них вражеских… А вообще, мой подход к этому вопросу напоминает решение математиком задачи об устойчивости табуретки. Сначала доказывается обобщённый случай N ножек, а потом просто берётся частный случай, для N=3.
  • +1
    Спасибо, очень интересно! Если вы делаете реализацию на джава, то вам может показаться интересным, идея написания дсл на котлине — очень просто, удобно, гибко и легкораширяемо. Многие случаи требуют адхок решений, которые плохо ложатся в исключительно декларативную модель. Написание дсл на языке вроде котлина или груви(менее типизировано, не советую), позволяет решить эту проблему и получить как бонус ide с автодополением. Рекомендую.
    • 0
      Да, Java. Посмотрю, спасибо.

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