Dagaz: В дебрях нотаций
Плюнь тому в глаза, кто скажет, что можно обнять необъятное! …
Усердие всё превозмогает!
Козьма Прутков «Мысли и афоризмы»
Люди постоянно что-то придумывают. После изобретения шахмат, было разработано ещё несколько тысяч похожих игр. Первоначально, по давней привычке, оставшейся ещё со времён сочинения античных мифов, создавались химеры, сочетавшие в себе качества двух и более шахматных фигур, но впоследствии фантазия авторов окрепла и стала выдавать более интересные варианты. Чтобы не запутаться во всём этом зоопарке, требовалась какая-то система, возможность классификации новых фигур. И она возникла. Собственно, я знаю их две. К сожалению, обе они не работают.
Разнообразные варианты шахмат всегда были в фокусе внимания шахматного сообщества. В специализированных изданиях можно найти описания новых игр, разборы партий, а также статьи по истории шахмат. Попытки систематизации правил никогда не рассматривались как что-то экстраординарное. Скорее это жизненная необходимость. В основу таких классификаций было положено разделение всех шахматных фигур на два больших класса: leapers и riders.
Leaper-ы — прыгающие фигуры (например, шахматный «Конь» — это (1,2)-leaper), перемещающиеся на указанное в скобках количество полей, не обращая внимания на встречающиеся по пути фигуры. Фигуры перемещающиеся на одно поле также можно считать leaper-ами (Ferz из Шатранджа — это (1,1)-leaper), но, поскольку они перемещаются на соседнее поле, то могут перепрыгнуть лишь 0 фигур (всё законно). При большом желании, к тому же классу можно отнести и шахматную «Пешку», но обычно так не поступают. Большинство ортодоксов вообще не считает её фигурой.
Ладьи, слоны и ферзи попадают в другую категорию фигур. Это rider-ы — фигуры, перемещающиеся по прямой через произвольное количество пустых полей (Ладья — (1,0)-rider). Существуют и «прыгающие» rider-ы, такие как Nightrider (полученный из шахматного коня), но и они, по пути своего следования, могут перемещаться лишь по пустым полям. Предложенная классификация считалась разумной и удобной до тех пор, пока не обнаружились фигуры, которые в неё не укладываются. Так появились Hopper-ы и Locust-ы. Проблему это не решило, поскольку существовали сотни фигур, не являющиеся ни тем ни другим.
Parlett’s movement notation
Первую масштабную попытку, навести порядок в этом зверинце, предпринял, по всей видимости, David Parlett. В своей книге «The Oxford History of Board Games» он использовал нотацию собственного изобретения, для классификации различных фигур используемых в многочисленных вариантах шахматных игр.
- 1 — перемещение на соседнее поле
- 2 — через одно поле
- n — на произвольное количество полей (как Ладья или Слон)
Направление:
- * — Перемещение во всех (восьми) направлениях
- + — По ортогоналям (вертикалям и горизонталям)
- > — Вперёд по вертикали
- < — Назад по вертикали
- <> — Вперёд и назад по вертикали
- = — По горизонтали (вправо или влево)
- >= — По горизонтали или по вертикали вперёд
- <= — По горизонтали или по вертикали назад
- X — По диагоналям
- X> — По диагоналям вперёд
- X< — По диагоналям назад
Группировка:
- / — Последовательное выполнение двух ортогональных перемещений
- & — Повторение движения в том же направлении
- . — Выполнение одного действия вслед за другим
Этого набора правил вполне достаточно для описания простых случаев, таких как Король (1*) или Ладья (nX) в классических Шахматах. Но уже в случае шахматного Коня начинаются сложности. Как выразить тот факт, что эта фигура может «перепрыгивать» через другие фигуры? С Пешкой тоже всё непросто. Это единственная фигура в Шахматах выполняющая «тихий» и «ударные» ходы по-разному. Соответственно, требуются специальные символы, позволяющие эти ситуации разделить. Возникла необходимость в расширении нотации:
Условия выполнения хода:
- i — Первый ход фигурой (например ход Пешкой с начальной позиции через одно поле)
- c — Выполнение взятия (ударный ход)
- o — Ход без взятия (тихий)
Типы ходов:
- ~ — Перепрыгивание через другие фигуры
- ^ — Взятие перепрыгиваемой фигуры (как в шашках)
Дополнительные типы группировки:
- , — Разделитель вариантов ходов (например, для Пешки определяется три возможных варианта хода)
- - — Определение диапазона возможного перемещения фигуры
- Король: 1*
- Ферзь: n*
- Слон: nX
- Ладья: n+
- Конь: ~½
- Пешка: o1>, c1X>, oi2>
Что можно сказать об этой нотации? Прежде всего, она не очень-то очевидна и (что гораздо хуже) вовсе не универсальна. Да, мы предусмотрели специальный символ для «прыгающих» фигур и для взятия при «перепрыгивании», как в шашках (cn (^2X>), o1X>), но совершенно забыли про такой важный класс фигур, как Hoppers.
В результате, всевозможные «пушки» (например из Xiangqi и Janggi) остались «за бортом» нашего описания. Более того, даже шахматные фигуры описаны неточно. Да, для пешки описана возможность «прыжка» через пустое поле из начальной позиции (oi2>), но где описание взятия на проходе? Где нотация рокировок выполняемых Королём? Если какая-то возможность сложна для описания, это не значит, что описывать её не надо!
Ralph Betza’s ''funny notation''
Ralph Betza — личность, в мире шахмат, также известная. Помимо серьёзного увлечения классическими шахматами, он известен как разработчик более чем 40 весьма оригинальных вариантов этой игры, таких как «Chess with different armies» или «The Way of the Knight». Остро понимая необходимость системы классификации шахматных фигур, Ralph предложил свой вариант нотации. Предложенная им система стала, фактически, общепринятым стандартом, используемым для описания возможностей шахматных фигур.
Основу описания составляют заглавные буквы латинского алфавита. Каждая из них определяет ход фундаментального leaper-а: W — Wazir (0,1)-leaper
F — Fers (1,1)-leaper («Ферзь» из Шатранджа)
D — Dabbaba (0,2)-leaper
N — Knight (1,2)-leaper (всем известный шахматный «Конь»)
A — Alfil (2,2)-leaper
H — Threeleaper (0,3)-leaper
C — Camel (1,3)-leaper
J — Zebra (2,3)-leaper
G — Tripper (3,3)-leaper
Для наиболее употребительных фигур вводятся сокращения. Так шахматный «Король» (K = FW) сочетает в себе ходы фигур Fers и Wazir. Rider получается из leaper-а удвоением заглавной буквы. Шахматный «Слон» (B = FF) — это ни что иное как rider, полученный из фигуры Fers, также как «Ладья» (R = WW) построена на основе фигуры Wazir. Шахматный «Ферзь» (Q = BR) сочетает ходы этих двух фигур. Разумеется, этого недостаточно. Для «Пешки» (самой сложной фигуры) необходимо задавать модификаторы:
- f — Движение вперёд
- b — Движение назад
- v — Короткая запись модификатора fb
- l — Движение влево
- r — Движение вправо
- s — Короткая запись модификатора rl
- t — Выполнение одного действия вслед за другим
- с — Взятие
- m — «Тихий» ход
Помимо модификаторов, в нотации Betza могут использоваться цифры. W5, например, определяет ограниченный range, позволяющий перемещаться по ортогоналям, не более чем на 5 шагов. В некоторых случаях, для группировки «атомов» могут использоваться квадратные скобки. Например, t[WB] (или 1+.nX, в нотации Parlett-а) описывает фигуру «Aanca», перемещающуюся на одно поле ортогонально и, вслед за тем, на произвольное количество полей по диагонали.
- Король: K = WF
- Ферзь: Q = RB
- Слон: B = FF
- Ладья: R = WW
- Конь: N
- Пешка: mfWcfF
Всё это прекрасно, но «Пешка» должна уметь ходить через одно поле из начальной позиции! Нужно больше модификаторов для нотации Betza!
- g — Grasshopper
- p — «Пушка» (это из «Китайских шахмат»)
- h — Забавный модификатор, о котором скажу чуть ниже
- j — Обязательное «перепрыгивание» фигуры
- n — Движение без «прыжков» через фигуры
- o — Движение по цилиндрической доске
- z — Движение фигуры «зигзагом» (ещё один забавный модификатор)
Что означает модификатор »h»? Чтобы понять это, требуется вспомнить одну из фигур «Японских шахмат». Конь в них «прыгающий», как и в классических шахматах, но ходит только вперёд, всего на два поля. Как выразить это, посредством нотации Betza? fN — хорошая попытка, но, двигаясь «вперёд», конь, вообще говоря, может попасть на 4, а не на 2 поля! Модификатор h призван «разрулить» эту ситуацию:
- ff — Движение «вперёд-вперёд» (как «Конь» в Сёги)
- fs — Движение «вперёд-в стороны» (с поля e4 можно попасть на c5 или g5)
- fh — Движение вперёд (на все четыре стороны)
Должен сказать, что при использовании «Parlett’s notation» японский конь выглядит не лучше: (~½)> (narrow).
- Пешка: mfWcfFimfW2
Здесь не описано «взятие на проходе», но не будем слишком мелочными. Разумеется, эта нотация не универсальна! Вот что, по этому поводу, пишет сам автор:
The notation is not universal or perfect yet. Imagine a piece that moves one square diagonally, and if that square is empty it can continue by jumping two squares diagonally in the same direction, and then three squares (like a Bishop that goes faster and faster!). My notation has no way to describe such a piece.
Впрочем, такие ужасы как «Слон» с «изменяемой геометрией хода» вовсе не требуются для того, чтобы поставить нотацию Betza в тупик. Существует масса других забавных фигур, столетиями используемых в многочисленных вариантах Сёги. Начать, безусловно, следует с Chu Shogi и её «Льва»:
Эта фигура делает как бы два хода (оба на одно поле в любую сторону, как «Король»). Таким образом, «Лев» может съесть две фигуры за ход или выполнить ещё более хитрый акробатический номер — съесть фигуру находящуюся рядом с ним и, вторым ходом, вернуться на своё место. Такой ход, в различных «Shogi variants», имеет настолько фундаментальное значение, что ему присвоено имя собственное — igui. И это далеко не самое экзотическое применение концепции «второго хода»:
Это три фигуры из Ko Shogi. Cavalry (騎総 kisō) очень похожа на фигуру «Льва», но использует ход шахматного «Коня», при этом двигаясь в «ту же» сторону. Winged horse (天馬 temba) — более сильная фигура, продолжающая ход в любом доступном для «Коня» направлении. Twelve-mile fog (五里霧) выглядит проще, двигаясь дважды как Alibaba (AD), но после каждого хода, он может «убить» оказавшуюся с ним рядом фигуру противника ходом igui. Если этих примеров мало — найдутся ещё:
Roaming assault (招揺 shōyō) — «Боевая колесница», двигающаяся на пять (или меньше) полей по прямой, убивая все фигуры противника, попадающиеся на пути. Thunderclap (霹靂 hekireki) делает всё те же пять ортогональных ходов, но произвольно меняя направление! И не надо думать, что такое встречается только в Ko Shogi! Dai dai shogi, Tenjiku shogi, Taikyoku shogi — во всех этих играх используются похожие фигуры. H.G. Muller, разработчик замечательной шахматной программы WinBoard/XBoard, предложил ещё один забавный модификатор, позволяющий решить эту проблему.
Модификатор »a» означает выполнение «второго хода», что позволяет описать ход «Льва» как aK (двойной ход «Королём»). Как обычно, дополнительные модификаторы позволяют описывать более сложные ходы. Вот так, например, в расширенной нотации Betza выглядит ход фигуры из «Шашек»: fmF (fcafmF). Можете попробовать расшифровать это сами. Именно эта нотация используется при описании фигур в «исторических» вариантах Сёги:
- Cavalry: [NaffN][xN]
- Winged horse: aN
- Twelve-mile fog: a[DA]acxK
- Roaming assault: Wa5fW
- Thunderclap: a!5W
Думаете, нотация Betza стала универсальной? Тогда попробуйте описать, с её помощью, эту игру:
Итак…
Если у вас есть проблема и вы хотите использовать регулярные выражения…
Поймите меня правильно, я не ищу сложность ради самой сложности! Мне просто не нравится то, что существующие нотации неконструктивны. В самом деле, что мы делаем когда обнаруживаем новый тип фигуры? Мы добавляем новую букву! За примером далеко ходить не надо. Вот что пишет H.G. Muller по поводу рокировок:
'O' is not an original Betza atom, but many extensions use it as null-move. As such, any repetition of it, like O2, would be pointless, as would be any modifier prefixes. I therefore propose to use O + number as a shorthand for (conventional) castling. (After all, castling in PGN is denoted as O-O or O-O-O.) The number would indicate how many steps the King moves. The move of the Rook (or in general, the corner piece) is implied: it ends up next to the King on its other side. Also implied is that you cannot move through or out of check, and that all squares between King and corner have to be empty. So the full description of a King would be FIDE: WFisO2
Резервирование отдельной буквы для столь частной вещи как рокировка, мне лично, кажется очень расточительным! Следуя по этому пути, мы начнём резервировать всё новые и новые буквы для всех специфичных ходов! Например, в Jetan-е «Принцесса», один раз за игру, имеет право прыгнуть на любое свободное поле доски, не находящееся под боем. На рокировку этот ход не похож. Значит нужна новая буква? А что делать когда все буквы закончатся? И это не говоря о том, что на выходе мы имеем не вполне очевидную, не универсальную и, самое главное, избыточную нотацию:
- g — Grasshopper
- p — «Пушка» из «Китайских шахмат»
- j — Обязательное «перепрыгивание» фигуры
- …
Grasshopper — это почти то же самое, что и Пушка (во всяком случае, корейская)! Зачем тратить на него ещё одну букву? И его поведение непосредственно связано с «перепрыгиванием» через фигуры (j)! С нотацией Parlett-а та же история: '~' — перепрыгивание через фигуры, '^' — взятие перепрыгиваемой фигуры, а про hopper-ов мы вообще забыли! Вернёмся к Фанороне. Вся проблема заключается в её специфическом способе взятия:
Это не шахматное и не шашечное взятие. С учётом ограниченного размера доски, такой ход можно описать, используя модификатор 'a' для нотации Betza, но описание будет очень громоздким! Придётся описывать перемещение фигуры за целевое поле (со взятием по дороге вражеских фигур), а затем возврат, для цепочки каждой длины и для всех восьми направлений! И это не говоря о том, что далеко не на всех полях Фанороны все эти восемь направлений доступны. А ведь Фанорона — не какое-то новомодное изобретение! На Мадагаскаре в эту игру играют с 1600-го года.
(*)[p]|((\1[ex])*;~1(~1[ex])*)
Выглядит как полная абракадабра и чем-то напоминает регулярные выражения. В общем-то, это не случайно. Регулярные выражения были придуманы для описания конечных автоматов, а что такое игровая доска, с перемещающейся по ней фигурой, как не конечный автомат? Рассмотрим составные части более подробно:
С альтернативой дело обстоит немного сложнее. Две (или более) альтернативы начинают с одинакового начального состояния и работают независимо друг от друга. Мы достигаем цели если удаётся выполнить любую из альтернатив. Для простоты, можно считать, что запятая связывает действия как 'и', а точка с запятой — как 'или'. В принципе, этих двух действий уже достаточно, но, чтобы сократить описание, нам потребуются квантификаторы:
- {n, m} — Повторение действия от n до m раз (n < m)
- {n} — Повторение действия n раз ровно
- {n,} — Не менее n раз
- {, m} — Не более m раз
Всё как в регулярных выражениях. Разумеется, определяем и привычные сокращения:
- ? — {0,1}
- * — {0,}
- + — {1,}
Теперь поговорим о действиях. Очевидным действием является перемещение по одному из направлений доски. Традиционно, используются обозначения сторон света: 'N', 'S', 'W', 'E' — для ортогональных и 'NW', 'NE', 'SW', 'SE' — для диагональных направлений, но, по причинам, о которых я скажу чуть ниже, я бы не хотел использовать двубуквенные обозначения. Вместо них я решил использовать 'M', 'O', 'R' и 'T', аналогично тому как это делается в проекте «LUDÆ». Таким образом:
- N — Сервер
- S — Юг
- W — Запад
- E — Восток
- M — Северо-запад
- O — Северо-восток
- R — Юго-запад
- T — Юго-восток
- U — Вверх (об этом расскажу ниже)
- D — Вниз
- + — По ортогоналям (аналогично Parlett и LUDÆ)
- X — По диагоналям
- * — По всем (стандартным) направлениям
Обозначения обобщённых направлений конфликтуют с квантификаторами, но эту коллизию несложно разрешить. Действие перемещения всегда может быть взято в скобки, а квантификатор никогда не может следовать сразу за открывающейся скобкой. Следует заметить, что определения направлений тесно связаны с описанием доски. Выглядит это примерно вот так:
- fanorona-9x5
grid: a-i x 5-1
N = (0, -1)
E = (1, 0)
S = (0, 1)
W = (-1, 0)
O = a3>b4>c5,a1>b2>c3>d4>e5,c1>d2>e3>f4>g5,e1>f2>g3>h4>i5,g1>h2>i3
T = a3>b2>c1,a5>b4>c3>d2>e1,c5>d4>e3>f2>g1,e5>f4>g3>h2>i1,g5>h4>i3
R = c5>b4>a3,e5>d4>c3>b2>a1,g5>f4>e3>d2>c1,i5>h4>g3>f2>e1,i3>h2>g1
M = c1>b2>a3,e1>d2>c3>b4>a5,g1>f2>e3>d4>c5,i1>h2>g3>f4>e5,i3>h4>g5Если для фигуры задано движение «в любую сторону» ('*'), а позиция, на которой она находится, определяет лишь ортогональные направления — фигура сможет перемещаться только ортогонально. Почему я не хочу использовать двубуквенные обозначения? Всё просто — если я перечисляю несколько альтернативных направлений, то должен разделать их символом точки с запятой (например, движение не превращённой фигуры в «Турецких шашках» — W; N; E), но, поскольку такая запись будет встречаться часто, я хотел бы опускать точки с запятой, для большей лаконичности (писать просто — WNE). Мне не хотелось бы, чтобы в этих случаях возникали конфликты с двубуквенными обозначениями направлений.
Другие действия:
- \1,…\9 — Перемещение в направлении, ранее захваченном в переменную
- ~1,…~9 — Перемещение в направлении противоположном захваченному
- | — Постановка фигуры на доску (все последующие перемещения выполняем без фигуры)
- […] — Специальные действия, проверки и прочее
О переменных стоит рассказать подробнее. Велико искушение описать ход «Ладьи» следующим образом: NEWS+ (или даже просто: ++), но это будет очевидной ошибкой. Фактически, этим описанием мы говорим, что «Ладья» двигается по ортогонали, один или более шагов, но нигде не упоминаем о том, что движение должно происходить в одном и том же направлении! Это очень похоже на ход ранее упоминавшейся фигуры Thunderclap, но без какого либо ограничения дальности хода.
Выбор направления должен производиться один раз за ход, а это означает, что выбранное направление необходимо зафиксировать в переменной: (+)\1*. Это описание лучше, но и оно не совсем верно. Ладья может двигаться по прямой, до первой вражеской фигуры, но лишь по пустым полям. Чтобы «Ладья» не проходила сквозь другие фигуры, необходимо уточнить описание: (+)([p]\1)*. Буква в квадратных скобках здесь — специальная проверка того, что поле, на котором мы находимся пусто (если это не так, генерация хода прерывается). Это одно из стандартных действий, определяемых спецификацией:
- [p] — Поле пусто?
- [P] — Поле не пусто?
- [e] — Вражеская фигура?
- [E] — Не вражеская фигура?
- [f] — Дружественная фигура?
- [F] — Не дружественная фигура?
- [a] — Поле атаковано?
- [A] — Поле не атаковано?
- [s] — Поле защищено?
- [S] — Поле не защищено?
- [o] — Ход этого типа выполняется в первый раз за игру?
- [m] — Фигура перемещалась?
- [M] — Фигура не перемещалась?
- [r] — Поле посещалось ранее, в пределах составного хода?
- [R] — Поле не посещалось ранее, в пределах составного хода?
- [l] — Поле начала предыдущего частичного хода?
- [t] — Поле завершения предыдущего частичного хода?
- [x] — Взятие фигуры
Помимо перечисленного, квадратные скобки позволяют расширять спецификацию, вставляя ссылки на обработчики на каком либо универсальном языке программирования (например JavaScript). Указывая цифру в квадратных скобках, мы говорим, что в этом месте необходимо вызывать специальный обработчик, для выполнения действий, описание которых на языке спецификации невозможно либо нецелесообразно (как я уже упоминал выше, никто не может объять необъятное). Хорошим примером игры, иллюстрирующей необходимость подобных расширений, может послужить Ритмомахия.
Это действительно важные моменты (если мы говорим об универсальной нотации), но повторять их в описании практически каждой фигуры было бы чрезмерно. Разумно сделать эти постфикс и префикс частью описания игровой доски. Доска такого типа (default) обладает двумя свойствами. Во первых (и это главное) — каждое поле доски может содержать не более одной фигуры. Если мы ставим другую фигуру на занятое поле, фигура стоявшая на нём ранее автоматически «забирается». Второе правило заключается в том, что игрок имеет право перемещать только свои фигуры (это справедливо для подавляющего большинства игр).
Такой тип построения доски не является единственно возможным. Я могу определить ещё, как минимум, два типа: stack (для таких игр как «Пулук» или «Столбовые шашки») и heap (для разного рода «Манкал»). В случае «столбовых» игр, игрок имеет право перемещать «стопки» фигур (при условии того, что наверху стопки расположена его фигура) и устанавливать «стопки» друг на друга. В манкалах, «фигуры» размещаются на поле неупорядоченной «кучей». Игрок берёт «кучу» целиком и распределяет по другим полям доски. Фигуры на heap-доске не обязательно однотипны! Существует, как минимум одна манкала, для которой это не так.
Ещё одним важным конструктивным элементом является навигация внутри квадратных скобок. Например, если нам необходимо выполнить взятие, не перемещая саму фигуру, не обязательно писать что-то вроде N[x]S, запись вида [x>N] будет также вполне корректна.
После всех этих необходимых разъяснений, я могу «расшифровать» свою нотацию хода фигур в Фанороне:
(*) # Двигаемся в произвольном направлении (захватив его в переменную)
[p] # Если поле не пусто - прерываем генерацию хода
| # Ставим фигуру на доску
(
(\1[ex])* # Двигаемся вперёд и пока есть вражеские фигуры - берём их
; # или
~1 # Идём назад (на стартовое поле)
(~1[ex])* # Продолжая движение, берём по пути вражеские фигуры
)
Здесь, я сознательно опускаю моменты связанные с описанием составного хода (это отдельная и довольно интересная тема). Продолжая сравнение нотаций, приведу своё описание ходов шахматных фигур. Жирным шрифтом выделена та часть описания, за которую Parlett и Betza даже не брались (рокировки и взятия «на проходе»):
- Король: *[A];[MA](E[p]){2}[A]|E^[M]W{2};[MA](W[p]){3}[A]|W^[M]E{2}
- Ферзь: (*)([p]\1)*
- Слон: (X)([p]\1)*
- Ладья: (+)([p]\1)*
- Конь: N, OM; E, OT; S, TR; W, RM
- Пешка: N[p]; OM[e];[M](N[p]){2};[(te,=Pawn, x)>E]O[l>N];[(te,=Pawn, x)>W]M[l>N]
Завершить это повествование я хотел бы афоризмом всё того же Козьмы Пруткова:
Бывает, что усердие превозмогает и рассудок
