точное количество расстановок шахматных фигур на доске

[Евгений Б.]

Возможно ли подсчитать точное количество расстановок шахматных фигур на доске?

Я читал, что их не более, чем 13^{64} (Число Гика)

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

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

Пешка может превратиться в любую фигуру
(теоретически возможно 9 ферзей или 10 коней, например)

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

Не обязательно все фигуры должны быть на доске
(какие-то могли уже быть взяты)

[Парджеттер]

Евгений Б. в сообщении #139104 писал(а):

Возможно ли подсчитать точное количество расстановок шахматных фигур на доске?

Ну а почему нет? Число клеток конечно, число фигур тоже.

[Евгений Б.]

Парджеттер писал(а):

Число клеток конечно, число фигур тоже.

Это так. Но как можно точно определить количество всех невозможных в игре вариантов?

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

[незваный гость]

Идея, конечно, хорошая. Только… как бы подсчитать число невозможных расстановок?! Ладно там, не бывает двух королей. Но существуют «законные» расстановки, которые в принципе не могут возникнуть в процессе игры (например, задача Ллойда — мат двумя ладьями и конём в центре доски). Задачи на ретроспективный анализ могут насчитывать по 40 ходов.

[Евгений Б.]

незваный гость писал(а):

...Но существуют «законные» расстановки, которые в принципе не могут возникнуть в процессе игры (например, задача Ллойда — мат двумя ладьями и конём в центре доски). Задачи на ретроспективный анализ могут насчитывать по 40 ходов.

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

а по поводу "40 ходов":
не совсем понимаю, что имеется ввиду - чьих ходов и зачем нужно количество ходов? я же ведь не ходы хотел подсчитать, а позиции. И всё же, можно ли с учётом этих 40 ходов подсчитать число расстановок или же без ретроспективного анализа это не возможно?

[Парджеттер]

Евгений Б. в сообщении #139133 писал(а):

ну вобщем-то ясно, что король не может встать на атакованное поле(иначе это мат уже будет)

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

[Профессор Снэйп]

Парджеттер писал(а):

Ну а почему нет? Число клеток конечно, число фигур тоже.

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

[незваный гость]

Евгений Б. в сообщении #139133 писал(а):

ну вобщем-то ясно,

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

Евгений Б. в сообщении #139133 писал(а):

а по поводу "40 ходов":
не совсем понимаю, что имеется ввиду

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

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

А пример с ретроспективным анализом я привёл к тому, что для определения корректности расстановки мало знать расстановку фигур — надо уметь построить историю. Ваше «ясно» с задачей Ллойда — это не более чем Ваша способность проанализировать историю (к счастью, краткую, в один ход белых). Ну и что? Вы можете доказать, что анализа в один ход (точнее, полуход) достаточно?

[Евгений Б.]

незваный гость писал(а):

Вы можете доказать, что анализа в один ход (точнее, полуход) достаточно?

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

незваный гость писал(а):

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

А разве нельзя исходя из правил игры их формализовать?Учесть, что пешки назад не ходят, короли не встают под шах и т.п.
Или и тут необходим ретроспективный анализ?

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

[Лукомор]

Евгений Б. в сообщении #139159 писал(а):

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

Лично мое мнение:
1. Число Гика нужно умножить на 2.
Это связано с тем, что одна и та же позиция может быть возможной при ходе одной стороны, и невозможной при ходе другой стороны.
2. Число невозможных позиций вычислить не удастся, это из области фантастики.
3. Нет ни какого смысла в знании точного количества невозможных позиций.
Допустим нам удалось создать полную базу данных по всем шахматным позициям, в которой на каждую позицию выделен 1 бит (а больше и не надо!).
Тогда биты, соответствующие невозможным позициям, нам просто безразличны.

[Алексей К.]

Лукомор в сообщении #139171 писал(а):

2. Число невозможных позиций вычислить не удастся, это из области фантастики.

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

Лукомор писал(а):

3. Нет ни какого смысла в знании точного количества невозможных позиций.

Но есть смысл (традиционный) в попытке узнать.

Лукомор писал(а):

3. Нет ни какого смысла в знании точного количества невозможных позиций.

Интересно, а как насчёт, например, магических квадратов? Чисто интересно. Или --- какой смысл в знании точного количества возможных позиций?

[незваный гость]

Евгений Б. в сообщении #139159 писал(а):

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

Блажен, кто верует.

Чтобы не быть голословным, как насчёт рокировки? Скажем, как Вы, взглянув на позицию, определите, двигался ли король? ладья?

И вообще, кто сказал, что остальные фигуры на доске не являются ограничениями?!

Евгений Б. в сообщении #139159 писал(а):

А разве нельзя исходя из правил игры их формализовать?Учесть, что пешки назад не ходят, короли не встают под шах и т.п.

Пожалуйста, вот формализация: законная позиция — это либо законная-белая, либо законная-чёрная позиция, при этом:
1) начальная позиция — законная белая;
2) законная чёрная позиция — позиция, возникающая из законной-белой при разрешённом правилами ходе белых;
3) законная белая позиция — позиция, возникающая из законной-чёрной при разрешённом правилами ходе чёрных;
4) остальные позиции незаконные.

Это рекурсивное определение совершенно формально. Вот только толку от него — шиш да кумыш.

А вот определение, которое позволит по статическому расположению фигур, без ретроанализа, определить, допустима ли позиция — флаг в руки.

[ddn]

незваный гость писал(а):

Чтобы не быть голословным, как насчёт рокировки? Скажем, как Вы, взглянув на позицию, определите, двигался ли король? ладья?

Нельзя определить в общем случае. Но к нашему вопросу это не имеет отношения.

незваный гость писал(а):

А вот определение, которое позволит по статическому расположению фигур, без ретроанализа, определить, допустима ли позиция — флаг в руки.

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

Число шахматных позиций оценено Шенноном как $10^{120}$

[Лукомор]

Возможны еще такие нехорошие варианты:
1. Позиция с виду допустимая, но она может получится, только если при рокировке король прошел через битое поле.
2. "Взятие на проходе" было/не было - как учесть???
3. Сразу откидываем все позиции, на которых одновременно шах белому королю и черному.
4. Откидываем позиции, когда перед ходом белых черный король находится под шахом и наоборот.

Ну и в качетве разумной альтернативы:
начать с чего-нибудь попроще - ну например крестики-нолики.
Всего вариантов: $3^9$, не так уж много.
Сколько из них недопустимых?
Задачка вполне решаемая ... А?

[Really]

незваный гость писал(а):

Пожалуйста, вот формализация: законная позиция — это либо законная-белая, либо законная-чёрная позиция, при этом:
1) начальная позиция — законная белая;
2) законная чёрная позиция — позиция, возникающая из законной-белой при разрешённом правилами ходе белых;
3) законная белая позиция — позиция, возникающая из законной-чёрной при разрешённом правилами ходе чёрных;
4) остальные позиции незаконные.

Это рекурсивное определение совершенно формально. Вот только толку от него — шиш да кумыш.

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

Профессор Снэйп писал(а):

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