Рекомендуемый формат данных для описания правил шахмат

Question

Я собираюсь писать шахматный сервер и один или несколько клиентов для шахмат, и я хочу описать правила шахмат (например, допустимые ходы на основе состояния игры, правила для того, когда игра завершена) на языке программирования независимо. Это немного сложно, поскольку некоторые из правил шахмат (например, King Castling, en passent, рисуются на основе трех или более повторных ходов) основаны не только на макете платы, но и на истории движений.

Я бы предпочел формат быть:

• текстуального
• люди читаемого
• на основе стандарта (например, YAML, XML)
• легко интерпретируемые в различных языках

Но я готов пожертвовать любым из них подходящим решением.

Мой главный вопрос: как я могу построить алгоритмы такой сложности, которые работают с таким сложным состоянием из формата данных?

Следующий вопрос: можете ли вы привести пример аналогичной проблемы, решаемой аналогичным образом, которая может служить отправной точкой?

Редактировать: В ответ на запрос на ясность - подумайте, что у меня будет сервер, написанный на Python, один клиент, написанный на C#, и другой клиент, написанный на Java. Я хотел бы избежать указания правил (например, для допустимого перемещения деталей, условий проверки и т. Д.) В каждом месте. Я бы предпочла указать эти правила один раз на языке независимо.

Answer 1

Давайте думать. Мы описываем объекты (местоположения и фрагменты) с состояниями и поведением. Нам нужно отметить текущее состояние и постоянно меняющийся набор разрешенных изменений состояния из текущего состояния.

Это программирование. Вам не нужен какой-то «метаязык», который вы затем можете проанализировать на обычном языке программирования. Просто используйте язык программирования.

Начните с обычных определений классов на обычном языке. Получите все, чтобы работать. Тогда эти определения классов являются определением шахмат.

С только крохотные исключениями все языки программирования

• Текстология
• Читабельно
• Разумно стандартизированы
• легко разобраны их соответствующих компиляторов или интерпретаторов.

Просто выберите язык, и все готово. Поскольку для разработки нюансов потребуется некоторое время, вы, вероятно, будете более счастливы с динамическим языком, например Python или Ruby, чем со статическим языком, например Java или C#.

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

---

Поскольку первоначальные требования были неполными, вторичный второстепенный вопрос заключается в том, чтобы иметь код, который работает совместно с несколькими клиентами.

1. Не имеют клиентов на нескольких языках. Выбери один. Java, например, и придерживаться его.

2. Если у вас должны быть клиенты на нескольких языках, вам нужен язык, который вы можете внедрить во всех трехязыковых средах. У вас есть два варианта.

   • Вставить интерпретатор. Например, Python, Tcl и JavaScript являются легкими интерпретаторами, которые вы можете вызывать из программ C или C#. Этот подход работает для браузеров, он может работать на вас. Java, через JNI также может использовать это. Существуют механизмы правил BPEL, с которыми вы можете попробовать.

   • Создайте интерпретатор как отдельный подпроцесс. Откройте именованный канал или сокет или что-нибудь между вашим приложением и вашим порожденным интерпретатором. Ваши клиенты Java и C# могут разговаривать с подпроцессом Python. Ваш Python-сервер может просто использовать этот код.

Answer 2

Edit: Чрезмерно многословный ответ удален.

Короткий ответ: написать правила в Python. Используйте Iron Python для взаимодействия с клиентом C# и Jython для клиента Java.

Answer 3

Это отвечает на вопрос :-)

последующей

я могу указать на то, что одна из самых популярных шахматных серверов вокруг документов его протокол here (Предупреждение, FTP ссылок, и не поддерживает пассивный FTP), но только для написания интерфейсов к нему, не для каких-либо других целей. Вы можете начать писать клиент для этого сервера в качестве учебного опыта.

Уместно отметить, что хорошие шахматные серверы предлагают гораздо больше возможностей, чем просто реле перемещения.

Тем не менее, существует более базовый протокол, используемый для взаимодействия с шахматами, задокументированный here.

О, и кстати: Board Representation at Wikipedia

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

Answer 4

Существует уже широко используемый формат, характерный для шахмат под названием Portable Game Notation. Также есть Smart Game Format, который можно адаптировать для множества различных игр.

Answer 5

Я бы предложил Пролог для описания правил.

Answer 6

Drools имеет современную концепцию прав человека для чтения - https://www.jboss.org/drools/. У них есть способ, которым пользователи могут вводить свои правила в Excel. Гораздо больше пользователей могут понять, что есть в Excel, чем в других инструментах.

Answer 7

Что я собрал из ответов до сих пор:

Для представления данных шахматной доске:

Смотрите статью Википедии на шахматной доске [представлений] (http://en.wikipedia.org/wiki/Board_representation_(chess))

Для. данные по перемещению шахматных фигур:

См. статьи в Википедии по Portable Game Notation и Algebraic Chess Notation

Для шахмат правила представления:

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

1. Используйте язык, где embedable интерпретатор существует для целевых языков (например, Lua, Python).
2. Используйте виртуальную машину, которую могут скомпилировать общие языки (например, IronPython для C#, JPython для Java).
3. Используйте фоновый демон или подпроцесс для правил, с которыми могут взаимодействовать целевые языки.
4. Реализовать алгоритмы правил на каждом целевом языке.

Хотя мне бы хотелось, чтобы декларативный синтаксис, который мог быть интерпретирован несколькими языками для обеспечения соблюдения правил шахмат, мое исследование привело меня к нежелательному кандидату. У меня есть подозрение, что Constraint Based Programming может быть возможным маршрутом, учитывая, что решатели существуют для многих языков, но я не уверен, что они действительно выполнили бы это требование. Спасибо за внимание и, возможно, в будущем появится ответ.

Answer 8

Чтобы представить текущее состояние платы (включая возможности рокировки и т. Д.), Вы можете использовать Forsyth-Edwards Notation, что даст вам краткое представление ascii. например:

 
rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1 

Будет ли положение открытой доски.

Затем, чтобы представить конкретный ход с позиции, вы можете использовать numeric move notation (как используется в шахматах в переписке), что дает вам короткое (4-5 цифр) представление движения на доске.

Что касается правил, я хотел бы узнать себя. В настоящее время правила для моего шахматного движка написаны только на Python и, вероятно, не так декларативны, как хотелось бы.

Answer 9

Я согласен с комментарием, оставленным пользователем ΤΖΩΤΖΙΟΥ, а именно: просто дайте серверу выполнить проверку и пусть клиенты отправят потенциальный ход. Если это не так, как вы хотите принять дизайн, тогда просто напишите правила на Python, как это предложил С. Лотт и другие.

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

Каждое правило может быть реализовано как функция, а затем для каждого полудвижения справедливость определяется, если она проходит все проверки ,

Для каждого потенциального переезда, представленный, вам просто нужно будет проверить правила в следующем порядке:

1. является предлагаемое движение потенциально действует? (правая «фигура» для куска)
2. подходит ли это подставкам на доске? (кусок заблокирован, будет ли он смещаться с края)
3. ли движение нарушает государственные требования? (Я в проверке после этого шага? Я пройти через проверку? Это ан захвата Passant законно?)

Если все те, в порядке, то сервер должен принять этот шаг как юридическое ...