Dagaz: На полпути

[godlin]

Что-то мне кажется с декларативностью у Вас не очень получилось…

[GlukKazan]

Да, описание ходов, само по себе, довольно императивно, но здесь я отталкивался от существующих аналогов. И в ZoG и в Ludi и в Axiom оно примерно такое же, но только без any и инвариантов. Чего то более декларативного, в этой области, я не видел. Если что-то придумаете или найдёте, сообщите мне. Меня этот вопрос очень интересует.

[godlin]

Было бы неплохо, если бы сначала Вы где-нибудь объяснили начальный код («Очень простые шашки»), а то не всё понятно. :)

[GlukKazan]

как-то так:

   (pre                                  ; Предварительные действия (для любого из определённых (двух) ходов
      (check is-friend?)                 ; На текущей клетке дружественная фигура?
      (take)                             ; Взять её в руку
      (log position)                     ; Отметить начальную позицию (для нотации хода)
      (let captured 0)                   ;  Определяем переменную - счётчик взятых фигур
   )
   (post                                 ; Завершающие действия для любого из ходов
      (check (<= max-captured captured)) ; Взято фигур не меньше глобального счётчика?
      (set! max-captured captured)       ; Обновить глобальный счётчик
      (log " - " position)               ; Отметить конечную позицию (для нотации хода)
      (drop)                             ; Поместить фигуру на доску
   )
   (move                                 ; Тихий ход
      (check (any nw ne))                ; Двигаемся на северо-запад или северо-восток (если возможно)
      (check is-empty?)                  ; Позиция пуста?
   )
   (move                                 ; Бой фигур
      (while true                        ; Повторять в цикле
         (let dir (any nw ne sw se))     ; Выбираем одно из 4 направлений
         (check dir)                     ; Двигаемся в выбранном направлении (если это возможно)
         (check is-enemy?)               ; Вражеская фигура?
         (capture)                       ; Берём её (можно ещё и отметить промежуточную позицию командой log)
         (inc! captured)                 ; Увеличиваем счётчик взятых фигур
         (check dir)                     ; Продолжаем двигаться в том же направлении (если это возможно)
         (check is-empty?)               ; Пустая клетка?
         (end-move)                      ; В этом месте ход может быть завершён
      )
   )

[godlin]

Чтобы перейти к декларативному стилю, надо, в частности, while, скажем, менять на пару «состояние — действие». Например, я бы попробовал как-то так:

1. задан список текущих позиций шашек А.

2. если нет активной шашки, и есть шашки, у которых есть доступные ходы -> выбрать (any) активную шашку (из тех, что с доступными ходами)

3. если нет активной шашки, и нет шашек, у которых есть доступные ходы -> конец игры

4. если есть активная шашка и у неё есть варианты ходов-> сделать (any) возможный ход

5. если есть активная шашка без вариантов хода -> снять с неё метку активности.

Этот список прогоняется до тех пока не сработает пункт 3.

Это навскидку :)

[GlukKazan]

while здесь не перебирает шашки на доске. Это цикл последовательных шагов в цепочечном взятии. Надеюсь, комментарии выше немного прояснили этот момент. Это моя промашка. Я настолько часто писал ZRF код, что посчитал всё это самоочевидным.

[godlin]

Фишка в том, что в при декларативном подходе не должно быть циклов. Должны быть рекурсии.

[GlukKazan]

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

[godlin]

Вы заметили, что никто не комментирует, кроме меня?
Возможно, это потому, что сквозь Ваш текст вообще крайне сложно прорваться (во всяком случае, для меня — точно ;))…

Объясните, пожалуйста, почему в этом фрагменте:

(game 
   (name chess-game)
   (loss 
      (exists?
         (any King)
         (if is-friend?
             (check is-attacked?)
         )
         (check no-moves?)
      )
   )
)

написано:

         (if is-friend?
             (check is-attacked?)
         )
         (check no-moves?)

а не, скажем:

         (check is-friend?)
         (check is-attacked?)
         (check no-moves?)

[GlukKazan]

Это очень правильный вопрос. Дело в том, что предикат is-attacked? крайне дорогой в вычислительном отношении. По хорошему, чтобы проверить атакуется ли фигура на поле, необходимо выполнить просмотр ещё на один ход вперёд и найти ходы, атакующие фигуру на поле. Именно фигуру, а не пустое поле, поскольку в таких играх, как Ультима, тип атаки может зависеть от типа атакуемой фигуры (Хамелеон бьёт фигуры их атаками). В общем, хотелось ограничить количество обращений к столь дорогому предикату.

Пожалуй, в отношении традиционных Шахмат, этот код не вполне верен. Он будет фиксировать проигрыш и в случае пата (есть варианты шахмат, в которых пат считается поражением). Для Шахмат более правильно будет:

(loss 
   (check no-moves?)
   (check (exists?
      (any King)
      (if is-friend?
          (check is-attacked?)
      )
   ))
)

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

Что касается сложности текста — ничего не могу поделать. Текст сложен. Тема сложная. Я старался изложить всё как можно проще, но не мне судить, насколько хорошо это удалось.

[GlukKazan]

Опять всё напутал. Вот код для Шахмат (надеюсь, теперь правильно).

(loss 
   (check no-moves?)
   (check (exists?
      (any King)
      (check (and is-friend?
          (check is-attacked?)
      ))
   ))
)

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

[GlukKazan]

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