Шахматы: реализация проверки корректности хода и поиск возможных ходов при нестандартной размерности доски?

Question

[Stas404]

Приветствую!
Разыскиваю информацию на тему проверки корректности хода и поиска возможных ходов в шахматах с различной размерностью доски (классические шахматы: 8x8, мини-шахматы: 5x5 и любые другие нестандартные размерности, а в перспективе и формы).
Найти реализации проверок для классических шахмат проблем не составило, но они не работают с другими размерностями — например, рокировка. На данный момент предполагается делать рокировку по правилам шахмат Фишера, когда это возможно.
Есть ли у читающих что-нибудь интересное по этому поводу (ссылки, реализации)?
Если писать самому, то что можете подсказать, в частности про алгоритмы проверок?

Answer 1

[Елизавета Борисова]

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

Для более точного ответа надо смотреть код, который выбрали.

Трехкратное повторение позиции — позиция повторилась третий раз, ничья.
Правило 50 ходов — 50 последних ходов были без взятия фигур, ничья.

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

Обращайтесь, если нужна профессиональная консультация по шахматам. шахматным алгоритмам, и js.

Comments

[Stas404]

Спасибо, за готовность помочь, Елизавета )
Давайте попробую более детально сформулировать что к чему — глядя на вопрос сейчас, вижу, что он действительно недостаточно полно описывает то, что нужно.
Значит, необходимо реализовать игру в шахматы (точнее по шахматным правилам) на поле NxN с любым количеством фигур. Королей всегда два (белый, черный), возможна рокировка в обе стороны при соблюдении правил «король не ходил, ладья не ходила, поля не под боем», фигуры ходят согласно правилам классических шахмат. Начальное расположение фигур может быть любым, пока без проверки на корректность.
Совершенно верно, что проверка ходов большинства фигур совпадает с проверкой ходов в классических шахматах (хотя они и заточены по 8x8 и надо править), но вот всякие другие подводные камни, например, рокировка — не совсем понятно, как быть. Возможно стоит делать рокировку по правилам шахмат Фишера.
Код еще никакой не выбрал, затем сюда и написал, чтобы подсказали )

[Stas404]

PS: из другой ветки — по поводу «движка». Движки на js есть и разряд на 3-2 в принципе играют, когда постараются. Но в контексте того, чтобы играть с компьютером в любой размерности — это не требуется, нужна только проверка на корректность (игра человек с человеком).
Тот факт, что нужно писать самому уже прояснился окончательно. Просто сначала показалось, что идея не настолько уникальна, что ее еще никто не реализовывал.

[Елизавета Борисова]

Правило рокировки зависит от конкретного размера доски 8*8 - король передвигается на 2 поля и ладья на 3(4). Если размер доски меняется, пустые поля видимо заполняются дополнительными фигурами (хотя не очевидно), и ладьи отодвигаются. Соответственно обычная рокировка невозможна просто.
Вы меняете размер- значит вы должны установить правила начального положения фигур, какие фигуры добавляются, меняется ли рокировка (например, теперь король-ладья перепрыгивают по N полей), как двигаются пешки в начале и тп. В сторону уменьшения фигур обозначаете, какие фигуры уходят, что с рокировкой.
Фишеровские шахматы могут помочь только в плане генераций начальных расстановок. По рокировкам там есть договоренность, что если короли-ладьи на своих местах, то она возможна, если нет - невозможна.
Вы еще не забудьте слонов генерировать парами))

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

Например, вот были попытки на пару клеток доску увеличить. Даже Капабланка об этом думал: https://ru.wikipedia.org/wiki/%D0%A8%D0%B0%D1%85%D...
Но ему пришлось ввести новую фигуру - это уже не шахматы значит. Вот кто-то еще вводил фигуру www.chess100.narod.ru/pravila.htm#AAAAAAAA
Фишер тоже очень долго думал, как спасти шахматы от просчета- додумался только фигуры перемешивать.

Все из-за баланса, в размере 8*8 фигуры координируются наилучшим образом. А с нарушенным балансом играть могут только слабые игроки.
Например, рассмотрим только увеличение доски, уменьшать невозможно без снятия дополнительных фигур(я надеюсь вы догадаетесь, какие фигуры снять и сколько?!) и вырождения в ничейные эндшпиля.
При увеличении более 10 клеток - конь становится маломощным, пешки вряд ли доберутся до последних горизонталей, играть придется ооочень долго. Плотность фигур нарушена, из-за этого
ни одной стороне невозможно(невыгодно) "атаковать", обе стороны будут вынуждены стоять в обороне на первых горизонталях.
Откуда вообще предположение, что в это можно играть?

[Stas404]

По поводу первого абзаца — все правильно.
И в качестве этих договоренностей, которые необходимо ввести при нестандартной размерности, как уже было обозначено, предполагается задействовать правила из шахмат Фишера — в частности, они дают правила для рокировки, которые сразу же можно применять с небольшими дополнениями относительно полей, куда переносятся фигуры. Тут, я думаю, все более-менее понятно.

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

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

[Елизавета Борисова]

Я не пишу про спасение шахмат от просчета, это к теме не относится, это был пример, что Фишер искал все играбельные модификации шахмат.
Я говорю, что никакие рекомендации по начальным позициям могут не помочь, на доске > 10.
Мне просто интересно , как человеку в прошлом с большим опытом в профессиональных турнирах,
как в это можно играть, человеку с человеком. Партии по 500 ходов без разменов и надежды на столкновение?!
Я не говорю, что идея ужасна, но поэтому там и возникали другие фигуры и фактический отход от шахмат. Вы можете пойти например по пути наборов юнитов, отойдя от набора в 6 фигур.

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

P.S. Если вы по какой-то причине не сможете реализовать приложение, мы в Matroid Games в принципе можем такое реализовать, для оценки присылайте описание продукта на email.

[Stas404]

> Мне просто интересно ,
> как человеку в прошлом с большим опытом в
> профессиональных турнирах,
> как в это можно играть, человеку с человеком.
> Партии по 500 ходов без разменов и надежды на столкновение?!

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

Говорить о том, насколько это будет сбалансировано, интересно и станет ли это популярным пока не имеет смысла — на данный момент это просто концепт. Причем, я удивлен, что его идея еще не была кем-то реализована, но это даже, наверно, и хорошо — вдруг и правда привлечет внимание при грамотной реализации и подаче.

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

Речь идет не о создании игры, которая будет строго математически сбалансирована, речь идет о создании «конфигурируемых шахмат», а вот как и кто их будет конфигурировать — вернемся к этому вопросу уже после первого этапа и рабочего прототипа. Даже если начальные позиции будут явно несбалансированными, создавать такие позиции — правао игроков. Я бы вот с удовольствием попробовал бы поиграть с друзьями в такие нестандартные шахматы и неважно, что поле 10 игр мы поймем, что такая расстановка заведомо дает преимущество белым или атаковать не выгодно — выберем другую.
Согласен, что второй этап видится гораздо более интересным )

P.S. По поводу вложений с моей стороны для реализации этого концепта — спасибо за предложение, но откажусь, т.к. нет цели делать ставку на коммерцию и это пока просто прощупывание почвы. Да и думаю, что справлюсь сам.

[Елизавета Борисова]

Stas404: ок, с изменением топологии, согласна, может быть что угодно, надо тестировать.
Баланс существует , когда могут играть и первый разряд, и гроссмейстер, но это действительно не актуально на данном этапе.

"Причем, я удивлен, что его идея еще не была кем-то реализована"
Все. что вы описали с изменением карт, топологий, конфигурацией правил игроками и тп - становится просто абстрактной пошаговой стратегией с юнитами. вы легко можете поступиться ограничениями правил передвижений 6 фигур, добавить какие угодно юниты.
Не реализовано из-за коммерческой целесообразности. Рынок пошаговых стратегий и так очень ограничен, на любителя подумать, так скажем. Классические шахматные сервера (блиц), даже самые популярные, тоже зарабатывают на уровне окупаемости.

[Stas404]

Елизавета Борисова: это все понятно — в общем и худшем случае получим бесплатную игрушку для развлечения тех, кто «с опытом» )
В конце концов, просто самому интересно было бы в такое поиграть.
По поводу юнитов и т.д. — так далеко, как раз, заходить не хочется, ибо, действительно, это будет уже совсем другая игра. Но возможность для дальнейшего наращивания новых возможностей и ограничений, как видим, заложена и наперспективу пригодится, мало ли что интересное придумается — это уже третий этап, не раньше )

Есть ли какие-нибудь мысли/информация относительно алгоритмов?
Например, определение факта, находится ли поле под боем.
Первое, что пришло в голову — решение в лоб, связано с перебором фигур противника и просмотром полей, куда они достают. Но, что-то этот подход мне не очень нравится.

[Елизавета Борисова]

Вы не обязаны перебирать все фигуры и поля каждый ход. это оверхед. Позиция в каждом полуходе меняется на положение 1-2 фигур (+-взятие).
Но на самом деле не ясно, с какой абстракцией вы хотите работать, И непонятно, сколько еще подобных вопросов у вас могут возникнуть, до того, как вы доберетесь до рабочей версии.

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