… мой двойник ожидает в доме Ихи, я встречаю его, я поднимаю мою фишку к [нему]
Я встречаю его в Прекрасном доме.
Я поднимаю три фишки и нахожу две фишки, мой двойник позади меня.
…
папирус времён Рамсеса III
До сих пор, я рассматривал игры, в которых каждая фигура действует как бы «сама по себе». Взаимодействие фигур, в таких играх, сводится к «поеданию» фигур противника. Но не все игры таковы. Существует множество игр, в которых одна фигура может «усиливать» или «ослаблять» другую, изменяя, тем самым, её свойства. Об этом я и хочу поговорить сегодня.
5. В единстве сила
Идея о том, что свойства фигур могут зависеть от их взаимного расположения, не нова. По всей видимости, этот принцип использовался в древнеегипетской игре Сенет, известной начиная с 3500 года до н.э. В наше время, точных правил этой игры никто не знает, но существует несколько реконструкций, основанных на анализе материалов, обнаруженных египтологами.
По версии Тимоти Кендалла, опубликованной в 1978 году, бой фигур в Сенете производился особым образом. Побитая фигура не убиралась с доски, а менялась местами с выполнившей ход. Эта идея хорошо согласуется с названием фигур Ibau — «танцоры» (в отличии от большинства других игр, Сенет использовал метафору танца, а не боевых действий). Игра в Сенет рассматривалась как «тренировка» в прохождении душой её посмертных испытаний (древние египтяне очень серьёзно относились к этому вопросу).
Важным моментом правил Кендалла является возможность «защиты» фигур друг другом. Запрещается «бить» фишку, входящую в состав «пары» — двух фишек, принадлежащих одному игроку, расположенных на соседних полях доски. К сожалению, реконструкция Кендалла не оговаривает ряд важных моментов. Можно ли перепрыгивать через «пару»? Можно ли разбивать «тройки» и «четвёрки» фишек? Эти вопросы оставлены без ответа. Правила хода фишек в «домах» (специальных полях доски) также не слишком удачны. В результате, игра получается довольно нудной:
Существует несколько «улучшений» правил Кендалла, среди которых я хотел бы выделить версию Дмитрия Скирюка. В этом варианте правил, «пары» препятствуют продвижению других фишек. Перепрыгивать их нельзя! Разбивать «пары» также нельзя, но если подряд стоят три и более фишек — это уже не «пара». Фишку, имеющую двух соседей, «бить» можно («тройка», таким образом, легко «разбивается» посередине). Простые изменения правил превращают «Сенет Кендалла» в очень динамичную и увлекательную игру. Как и в случае с "Игрой из города Ур", Дмитрий провёл большую работу по проверке предложенного им варианта правил на практике.
Сиджа — ещё одна египетская игра, в которой фигуры действуют «сообща». В этой древней игре, сохранившейся до наших дней, захват фигуры противника осуществляется путём «зажимания» её в «клещи» с двух сторон. Вполне возможно, что именно от этой игры произошли и другие «зажимные» игры, такие как Хнефатафл.
Способ взятия «зажимом в клещи» позволяет брать несколько фигур противника сразу (до трёх фигур, в разные стороны), но это не единственная возможность «увеличения производительности». В тибетской игре "Мин Манг" разрешается брать сразу несколько фигур противника, выстроенных в ряд, «закрыв» линейку своими фигурами с обеих сторон. Взятые фигуры «меняют цвет», аналогично тому, как это происходит в "Реверси".
Ещё дальше идут некоторые региональные варианты "Hasami Shogi". В следующем ниже видео показано, каким образом может быть взята «компактная» группа фигур, расположившихся в углу доски. Признаться честно, я пока затрудняюсь с формализацией этих правил. Например, из объяснения непонятно, как брать фигуры у края доски:
Своего наивысшего развития идея «связности» фигур достигает в другой древнейшей игре — Го. Эта игра строится на понятии «группы» камней. Камни, расположенные на соседних пунктах доски (по вертикали или горизонтали) составляют единую группу. Группа должна соседствовать с не захваченными пунктами доски (дамэ), в противном случае, она «умирает» и снимается с доски полностью. Удивительно, но столь простые правила приводят к невероятному разнообразию тактических комбинаций.
Но Го — далеко не единственная игра, активно использующая это понятие. В игре "Ордо", например, игроки преследуют две цели: прорыв к противоположной стороне доски и сохранение «строя» своих фигур. В отличии от Го, фигуры считаются связанными не только по ортогональным, но и по диагональным направлениям. Ходы «разрывающие» единую группу фигур не допускаются. Если группа оказалась разорвана, в результате атаки противника, её целостность должна быть восстановлена следующим ходом (в противном случае, игроку засчитывается поражение). На видео вариант этой игры, допускающий перемещение групп фигур, связанных по диагонали:
Конечно, это не предел того, куда может завести воспалённая фантазия изобретателя настольных игр. Связывая фигуры, совсем не обязательно ограничиваться соседними клетками. В «военной» игре Ги Дебора "Кригшпиль", прямые линии от «Арсеналов» и «Передатчиков» символизируют линии снабжения. Потеряв контакт с такой линией (непосредственный или через расположенную рядом фигуру), фигура «замирает», теряя возможность хода, до тех пор, пока контакт не будет восстановлен. Не знаю кому как, а мне это сильно напоминает «энергетическую сеть» протосов из Старкрафта.
Простота формулировки правил Го обманчива. Корректная их реализация, на языке ZRF, столь же многословна сколь малопонятна. Приведу, в качестве примера, фрагмент реализации "Stoical Go":
(define adjacent-to (or (position-flag? $1 n) (position-flag? $1 s) (position-flag? $1 e) (position-flag? $1 w) ) ) (define set-danger-flag (if (and (enemy? $1) (not-neutral? $1) (not-position-flag? safe $1)) (set-position-flag danger true $1) (set-flag Changed true) ) ) (define stone (name Stone) (image Black "images\Stoical Go\pieces\b$1.bmp" White "images\Stoical Go\pieces\w$1.bmp" ) (attribute makes-capture false) (drops ( (verify empty?) (verify (not-position? end)) (set-flag Capturing false) ; if next to enemy (if (or (and (enemy? n) (not-neutral? n) ) (and (enemy? s) (not-neutral? s) ) (and (enemy? e) (not-neutral? e) ) (and (enemy? w) (not-neutral? w) ) ) mark ; *** Initialize safe ; for each point ; if enemy ; if next to empty ; P[safe] = true a1 (while (not-position? end) (set-position-flag safe empty?) next ) back (set-position-flag safe false) a1 (while (not-position? end) (if (and enemy? not-neutral? (adjacent-to safe) ) (set-position-flag safe true) ) next ) ; *** Initialize danger ; for each adjacent ; if enemy ; P[danger] = true back (set-flag Changed false) (set-danger-flag n) (set-danger-flag s) (set-danger-flag e) (set-danger-flag w) (if (flag? Changed) ; *** Spread danger, safe ; Changed = true ; while Changed ; Changed = false ; for each point ; if enemy ; if !P[safe] ; if any adjacent is enemy with P[safe] ; P[safe] = true ; if !P[safe] and !P[danger] ; if any adjacent is enemy with P[danger] ; P[danger] = true ; Changed = true (while (flag? Changed) (set-flag Changed false) a1 (while (not-position? end) (if (and enemy? not-neutral?) (if (and (not-position-flag? safe) (adjacent-to safe)) (set-position-flag safe true) (set-flag Changed true) ) (if (and (not-position-flag? safe) (not-position-flag? danger) (adjacent-to danger) ) (set-position-flag danger true) (set-flag Changed true) ) ) next ) ) ; *** Add captures for stones ; for each point ; if P[danger] and !P[safe] ; capture a1 (while (not-position? end) (if (and (position-flag? danger) (not-position-flag? safe)) capture (set-flag Capturing true) ) next ) back ) ; if Changed ) ; if next to enemy ;!!!!!!! Find out if suicide ; if no captures (if (and (not-flag? Capturing) (not (or (empty? n) (empty? s) (empty? e) (empty? w) ) ) ) ; *** Initialize safe ; for each point ; P[safe] = empty and not-marked a1 (while (not-position? end) (set-position-flag safe empty?) next ) back (set-position-flag safe false) ; Changed = true ; while Changed and not adjacent to safe ; Changed = false ; for each point ; if friend ; if !P[safe] ; if any adjacent is friend with P[safe] ; P[safe] = true ; Changed = true (set-flag Valid (adjacent-to safe)) (set-flag Changed true) (while (and (not-flag? Valid) (flag? Changed) ) (set-flag Changed false) a1 (while (not-position? end) (if (and friend? (not-position-flag? safe) ) (if (adjacent-to safe) (set-position-flag safe true) (set-flag Changed true) ) ) next ) back (set-flag Valid (adjacent-to safe)) ) ; *** Add if not suicide ; verify next to safe square back (verify (flag? Valid)) ) ; if no captures ; *** Add stone (if (flag? Capturing) (go last-to) (if (piece? CapturingStone) (verify friend?) (change-type Stone) ) was-a-capture (change-type yes) back (add CapturingStone) else was-a-capture (if (piece? yes) (change-type no) (go last-to) (change-type Stone) ) back add ) ) ) ; drops )
Даже с комментариями, разобраться в этом крайне тяжело (ещё сложнее найти в коде ошибки). С появлением в Axiom массивов, ситуация несколько улучшилась (настолько, насколько это вообще возможно, при использовании языка ForthScript). Вот фрагмент кода, проверяющего связность групп из моей реализации Ordo:
20 CONSTANT LS 10 CONSTANT SS LS [] list[] VARIABLE list-size SS [] set[] VARIABLE set-size VARIABLE curr-pos : not-in-list? ( pos - ? ) curr-pos ! TRUE list-size @ BEGIN 1- DUP 0 >= IF DUP list[] @ curr-pos @ = IF 2DROP FALSE 0 ENDIF ENDIF DUP 0> NOT UNTIL DROP ; : not-in-set? ( pos - ? ) curr-pos ! TRUE set-size @ BEGIN 1- DUP 0 >= IF DUP set[] @ curr-pos @ = IF 2DROP FALSE 0 ENDIF ENDIF DUP 0> NOT UNTIL DROP ; : add-position ( -- ) list-size @ LS < IF here not-in-list? IF here list-size @ list[] ! list-size ++ ENDIF ENDIF ; : not-from? ( pos -- ? ) DUP from <> SWAP not-in-set? AND ; : check-dir ( 'dir -- ) EXECUTE here not-from? AND friend? AND IF add-position ENDIF ; : check-coherence ( -- ? ) here 0 list[] @ 0 BEGIN DUP list[] @ DUP to ['] n check-dir DUP to ['] s check-dir DUP to ['] w check-dir DUP to ['] e check-dir DUP to ['] nw check-dir DUP to ['] sw check-dir DUP to ['] ne check-dir to ['] se check-dir 1+ DUP list-size @ >= UNTIL 2DROP to TRUE SIZE BEGIN 1- DUP 0 >= IF DUP not-from? IF DUP from <> OVER friend-at? AND IF DUP not-in-list? IF 2DROP FALSE 0 ENDIF ENDIF ENDIF ENDIF DUP 0> NOT UNTIL DROP 0 list-size ! ;
Во всяком случае, теперь просматривается не вся доска, а лишь группа связанных фигур, что весьма благотворно сказывается на производительности. Для алгоритма построения связной группы требуется очередь, позволяющая добавлять элементы «в хвост», не останавливая перебора, начатого «с головы». Дойдя до элементов, добавленных в процессе обработки, цикл перебора должен обработать их так же как и все предыдущие элементы. Вот так должен выглядеть этот алгоритм «в новом дизайне»:
(define add-piece-neighbors (foreach current-group (all (if (any n s e w nw sw ne se) (check is-friend?) (if (not (piece-contains current-group)) (take-piece current-group) ) ) ) ) ) (define check-coherence (if (exists? any-position (check is-friend?) (take-piece current-group) add-piece-neighbors ) (check (not (exists? any-position (check is-friend?) (check (not (piece-contains current-group))) ) ) ) ) )
После двух предыдущих листингов, в это может быть трудно поверить, но здесь есть всё необходимое, чтобы решить задачу. Выбираем любую дружественную фигуру, добавляем в набор её соседей, затем соседей её соседей и так далее, пока соседи не кончатся. Если по завершении этой процедуры осталась хотя бы одна дружественная фигура, не принадлежащая построенному набору — инвариант нарушен. Очень жаль, что в ZoG и Axiom нельзя решить эту задачу также просто.
ссылка на оригинал статьи http://habrahabr.ru/post/256701/
Добавить комментарий