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

Question

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

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

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

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

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

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

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

Answer 1

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

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

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

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

• 1012 * Текстология *
• Человек для чтения
• Разумно стандартизировано
• Легко анализируется соответствующими компиляторами или интерпретаторами.

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

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

---

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

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

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

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

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

Answer 2

Что я получил из ответов на данный момент:

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

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

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

См. Статьи в Википедии о Нотации переносимых игр и Обозначение алгебраических шахмат

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

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

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

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

Answer 3

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

Answer 4

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

Answer 5

Это ответ на следующий вопрос: -)

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

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

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

Да, и, кстати: Представительство в Википедии

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

Answer 6

Редактировать: Удалить слишком многословный ответ.

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

Answer 7

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

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

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

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

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

Если все в порядке, сервер должен принять ход как законный ...

Answer 8

Для представления текущего состояния доски (включая возможности рокировки и т. Д.) Вы можете использовать Запись Форсайта-Эдвардса , которая даст вам краткое представление ascii. e.g.:

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

Будет позиция открытия доски.

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

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

Answer 9

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