Написать валидацию доски (позиции на доске).

[nekr0z]

No description provided.

[nekr0z]

В теме проверки легальности позиции (даже если мы не берём 960) оказалось на удивление много вкусного; некоторые даже считают, что задача эта алгоритмически невыполнима.

Из курьёзов: автор этой диаграммы считает, что позиция на доске (ход белых, пешка c5 может быть взята на проходе, у чёрных доступна рокировка) не может быть достигнута легально…

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

Вот это последнее соображение приводит меня к мысли, что целиться в абсолютную валидацию, может быть, и незачем; достаточно валидировать основные моменты:

1. Существует один и только один король каждого цвета.
2. Король цвета, у которого нет хода (в том смысле, что ход у другой стороны), не находится под шахом.
3. Король цвета, имеющего ход, находится под шахом не больше, чем двойным; если шах двойной, то это не два слона, не два коня, не пешка+пешка, не пешка+конь, не пешка+слон.
4. На доске не больше 8 пешек каждого цвета.
5. На горизонталях 1 и 8 пешек нет.
6. В случае, если открыто взятие на проходе, перед «проходным» полем находится пешка нужного цвета, проходное поле и поле за ним пусты.
7. Количество фигур соответствует количеству недостающих пешек: два ферзя и три ладьи одного цвета требуют не более шести пешек этого цвета на доске, и т. д. Учесть, что из двух однопольных одноцветных слонов один — проведённый.
8. Конфигурация пешек должна хотя бы примерно соответствовать количеству фигур на доске; так, 6 белых пешек на вертикали h возможны только в том случае, если у чёрных на доске не осталось ничего, кроме короля (и вряд ли такая позиция возникла в реальной игре).
9. Белые пешки на h2 и h3 означают, что белой пешки на g2 быть не может, и т.д.
10. Король не на месте не сочетается с возможностью рокировки, аналогично для ладьи.
11. Белый слон может быть заперт на 1-й горизонтали пешками только на своей стартовой позиции (т.е. невозможна позиция с белым слоном на e1 и белыми пешками на d2 и f2, например). При наличии белых пешек на d2 и f2 чёрный слон может оказаться на e1 только в результате проведения туда пешки; если белая пешка есть и на e2, чёрного слона на e1 быть не может вообще. Аналогично для 8-й горизонтали.

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

делает невозможной рокировку, а, например, вот это:

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

Что думаете?

[loskutovanl]

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

Ещё я не могу себе представить двойной шах двумя ладьями.
По сути двойной шах может быть ферзь пешка (ферзь вертикаль или горизонталь); ферзь конь; ферзь слон (ферзь вертикаль или горизонталь); ладья пешка; ладья конь; ладья слон; ферзь ладья (только если ферзь по диагонали шахует)

[loskutovanl]

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

[nekr0z]

Ещё я не могу себе представить двойной шах двумя ладьями.

Ход белых.
После fxg=R чёрный король под двойным шахом двумя ладьями.

Аа, ну да.
С ферзем также получается.

Очень замороченно будет валидировать все случаи

[nekr0z]

Ещё я не могу себе представить двойной шах двумя ладьями. По сути двойной шах может быть ферзь пешка (ферзь вертикаль или горизонталь); ферзь конь; ферзь слон (ферзь вертикаль или горизонталь); ладья пешка; ладья конь; ладья слон; ферзь ладья (только если ферзь по диагонали шахует)

Ход белых. После Ne8 имеем двойной шах конь+слон.

[da070116]

есть ещё кейс задачи-шутки, там бывает и не такое. Ради интереса полез в редактор доски на lichess, там позиция ошибочна только при нескольких королях на доске, ходе стороны, которая даёт шах, и пешках на 1/8 горизонталях. Sapienti satis?)

[nekr0z]

Ради интереса полез в редактор доски на lichess [...]

Lichess в явном виде поддерживает 960 и Bughouse, поэтому у них так: в их редакторе пользователь, сколько мне помнится, нигде в явном виде не выбирает, для какого варианта он редактирует доску, поэтому отсекаются только такие, которые заведомо невозможны ни в каком варианте.

[da070116]

Нет, какие-то варианты правил там есть. но поскольку это всё от лукавого, даже не разбирался, что это за правила такие

[sadmadrus]

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

[loskutovanl]

Ещё я не могу себе представить двойной шах двумя ладьями. По сути двойной шах может быть ферзь пешка (ферзь вертикаль или горизонталь); ферзь конь; ферзь слон (ферзь вертикаль или горизонталь); ладья пешка; ладья конь; ладья слон; ферзь ладья (только если ферзь по диагонали шахует)

Ход белых. После Ne8 имеем двойной шах конь+слон.

Да, соглашаюсь, что две ладьи и слон плюс конь возможны для двойного шаха.
Может для простоты просто проверять что шах не тройной ? ..
А то много нюансов получается для каждого варианта двойного шаха КМК

[nekr0z]

Может для простоты просто проверять что шах не тройной ? ..

Ну, есть явно нелегальные двойные шахи — например, шах двумя пешками невозможен точно :) Но это посмотрим по ходу дела.

[nekr0z]

Написано. Для добавления проверок открыл новый тикет #41