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

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

Really в сообщении #139378 писал(а):

Это определение бесполезно для того чтобы посчитать количество незаконных позиций.
С другой стороны, это еще один способ найти все законные позиции.

Вы правы. Я имел лишь в виду, что оно бесполезно для подсчёта числа расстановок без перечисления расстановок. Это довольно обычное требование в комбинаторике.

ddn в сообщении #139193 писал(а):

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

Готовы ли Вы доказать, что для всякой расстановки, которая получается с рокировкой, либо существует партия, приводящая к той же конфигурации без рокировки, либо существует партия, при которой король и ладья не двигались? При отсутствии такового доказательства упомянутый факт становится важен.

ddn в сообщении #139193 писал(а):

Это в принципе возможно и вполне обозримо.

Готовы ли Вы доказать, что любая полученная по этому рецепту позиция может возникнуть во время игры? Я почему-то сомневаюсь.

~~~

Мне кажется, что смешивается две совершенно разных задачи: точный подсчёт числа корректных позиций и оценка числа корректных позиций. Ддя второй задачи приведённые ddn правила работают, для первой — нет. Отсюда и разногласия не по существу.

[e7e5]

Евгений Б. писал(а):

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

Для справки:
Математик Р.Шуриг:"Число различных положений, которые могут занять на шахматной доске все 32 фигуры, выражается 52 значным числом. Оно читается так: 7534 октильонов 68312 септильонов, 361 225 сектильонов 327000 квинтильонов"

Математик М. Крайчик: "Общее число возможных вариантов шахматных партий 2х10 в 116 степени. Это неизмеримо больше, чем число электронов во всей Вселенной..."

Можем дать такие оценки здесь?

[ddn]

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

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

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

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

2. "Взятие на проходе" было/не было - как учесть???

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

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

3. Сразу откидываем все позиции, на которых одновременно шах белому королю и черному.

Это относится к моему пункту 3.

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

4. Откидываем позиции, когда перед ходом белых черный король находится под шахом и наоборот.

Тоже мой пунки 3. Но здесь требуется расширенное понимание позиции, которое включает не только состав и расположение фигур (включая пешки) на доске, но и:
(а) очередность хода;
(б) наличие/отсутствие ходов у королей и (если король не ходил) наличие/отсутствие ходов у соответсвующих ладей; (по другому: наличие/отсутствие возможности по отдельности длинной и короткой рокировки для каждого короля, обусловленное лишь наличием/отсутствием ходов);
(в) наличие/отсутствие возможности взятия "на проходе" для каждой пешки, расположенной на 4-й (по отношению к игроку) горизонтали.

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

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

Крестики-нолики - не игра с фигурами на доске, ее анализ другой, к тому же он слишком прост.
Всего допустимых позиций $5807$. Из них завершенных позиций $998=662+316+20$ (победа первого+поражение первого+ничья, т.е. невозможность хода). Число допустимых партий (завершенных) $289728$.

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

ddn в сообщении #139193 писал(а):

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

Готовы ли Вы доказать, что для всякой расстановки, которая получается с рокировкой, либо существует партия, приводящая к той же конфигурации без рокировки, либо существует партия, при которой король и ладья не двигались?

Видите ли: "можно в общем случае" - значит можно для всех случаев, а "нельзя в общем случае" - не означает, что нельзя для любого случая. "Нельзя в общем случае" - просто значит можно не для всех случаев, значит существует расстановка (случай), к которой приводит как некоторая партия с рокировкой, так и некоторая партия без рокировки. И такой пример совсем нетрудно построить! (вот вам доказательство через контрпример)

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

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

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

При отсутствии такового доказательства упомянутый факт становится важен.

Совсем не важен. Нас же интересует вопрос: существует ли партия, приводящая к данной расстановке, а не то - с рокировкой эта партия или без, и двигался ли король? Но может, конечно, Вас интересует не просто расстановка, а позиция (включающая в себя еще и "флаг"=да/нет возможности рокировки с каждой из ладей) - тогда да.

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

ddn в сообщении #139193 писал(а):

Это в принципе возможно и вполне обозримо.

Готовы ли Вы доказать, что любая полученная по этому рецепту позиция может возникнуть во время игры? Я почему-то сомневаюсь.
~~~
Мне кажется, что смешивается две совершенно разных задачи: точный подсчёт числа корректных позиций и оценка числа корректных позиций. Для второй задачи приведённые ddn правила работают, для первой — нет. Отсюда и разногласия не по существу.

Не понимаю Вас! Как еще можно понимать корректную позицию? Только как "могущую возникнуть во время игры" - как еще? Поймите, НЕ СУЩЕСТВУЕТ никаких правил корректности или некорректности той или иной позиции, взятой самой по себе - просто не сущестует!!! Есть правило начальной позиции (их в принципе можно задать любым множеством), есть правила хода (последовательной смены позиций), есть правила завершения игры (притом, они сводятся к невозможности хода без удара по своему королю или к невозможности хода, выводящего из под удара по своего короля - ход же на свободную клетку или взятием сам по себе всегда возможен при соблюдении общепринятых правил начальной позиции и хода). Эти правила определяют, какие позиции возможны на данном номере хода, на некотором произвольном ходе. Но совершенно бессмысленно говорить корректности или некорректности позиции, взятой самой по себе - безотносительно ее истории, то есть безотносительно правил начальной позиции, хода и завершения игры. Позиция, взятая сама по себе, может быть совершенно любой: даже с произвольным составом фигур - к примеру, с двумя слонами на поле одного цвета при восьми пешках, даже с положением пешки на 1-й и 8-й горизонтали - ее превращение обязательно только на переходе с 7-й на 8-ю горизонталь (хотя правила ее движения с этих горизонталей специально не прописаны), даже с взаимным шахом/матом, даже с шахом королями друг другу, даже без одного или двух королей, даже с любым количеством королей (хотя правила шаха и мата там специально не прописаны)!!! Только правила начальной позиции, хода и завершения игры делают такие позиции невозможными! Только эти правила определяют какая позиция возможна во время игры (корректна), а какая во время игры невозможна (некорректна).
Когда я говорил о своем рецепте, я имел ввиду только возможные позиции! Оценка числа позиций - это другое дело.

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

[e7e5]

ddn писал(а):

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

Поясните, пожалуйста, как именно вы это выясните?
Будет ли протокол этой партии единственным?
Если не единственный, то много ли найдется таких позиций, когда протокол будет все-такие единственным на некотором интервале ходов?

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

ddn в сообщении #139585 писал(а):

я действительно утверждаю и бОльшее (но уже без строго доказательства): для любой допустимой расстановки, к которой приводит некоторая партия с рокировкой, существует и некоторая партия без рокировки, приводящая к ней.

Осмелюсь оспорить это утверждение. Пример позиции (частичной) — все белые пешки на месте, Лf1, Крg1. Скажете невозможно?

ddn в сообщении #139585 писал(а):

Видите ли:

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

ddn в сообщении #139585 писал(а):

Нас же интересует вопрос: существует ли партия, приводящая к данной расстановке,

Совершенно согласен. Я бы даже сказал — кооперативная партия.

Просто мне не очевидно, что для любой позиции, удовлетворяющей приведённым Вами трём правилам существует кооперативная партия, к ней приводящая (правда, и правила-то сформулированы весьма неформально).

ddn в сообщении #139585 писал(а):

Как еще можно понимать корректную позицию?

Как удовлетворяющую трём правилам ddn Шучу, шучу. Корректная позиция — только та, которая может возникнуть в процессе игры. Поэтому нам нужно лишь доказать, что всякая позиция, удовлетворяющая трём правилам, — корректная. (Дополнительное утверждение — что всякая позиция не удовлетворяющая правилам, некорректна, — доказывается легко. Но его очень мало.)

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

ddn в сообщении #139585 писал(а):

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

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

e7e5 в сообщении #139621 писал(а):

Будет ли протокол этой партии единственным?

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

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

[ddn]

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

:evil:

ddn в сообщении #139585 писал(а):

я действительно утверждаю и бОльшее...

Осмелюсь оспорить это утверждение. Пример позиции (частичной) — все белые пешки на месте, Лf1, Крg1. Скажете невозможно?

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

ddn писал(а):

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

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

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

ddn в сообщении #139585 писал(а):

Видите ли:

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

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

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

ddn в сообщении #139585 писал(а):

Нас же интересует вопрос: существует ли партия, приводящая к данной расстановке,

Просто мне не очевидно, что для любой позиции, удовлетворяющей приведённым Вами трём правилам существует кооперативная партия, к ней приводящая (правда, и правила-то сформулированы весьма неформально).

Не то, что неформально - они вообще не сформулированы полностью! Это только ЭСКИЗ! Набросок! Не более!
Вы поймите, ищется именно точный критерий возможности позиции - опираясь именно на определение через цепочку ходов от начальной позиции к конечной. Но можно прямо в лоб перебирать все ходы и следующие друг за другом позиции, а можно оптимизировать этот процесс ретроанализа. Мои пункты - это детализация алгоритма такой оптимизации. Благодаря обратимости движения фигур (не пешек) и короля, нужно рассмотреть сначала полный, но более простой, ретроанализ движения одних лишь пешек - здесь оптимизация минимальная, но и объем работы меньше, ибо пешек только 16 и хотят они просто. На расположение же фигур и королей почти не накладывается ограничений (кроме случаев особого расположения пешек) из-за обратимости их движений. Нужно углубить эту детализацию, рассмотреть частные случаи, исключения. Убежден, что это обозримо.

e7e5 писал(а):

ddn писал(а):

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

Поясните, пожалуйста, как именно вы это выясните?

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

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

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

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

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

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

Даю: $276$. Покажите!

Можете начинать прямо с $s^{[1568]}(276)=?$

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

[ИСН]

Вы путаете гипотезу Коллатца (это которая "3n+1" и которую проверить для любого числа - обычно не сильно труднее, чем записать само это число) с гипотезой $\sigma(n)-n$.
(Я верю в обе, но это оффтопик. А в обсуждаемую здесь - не верю, хоть она и конечна )

[e7e5]

ddn писал(а):

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

Офф-топик наверное - а что за проект, поподробнее можно?

[ddn]

e7e5 писал(а):

ddn писал(а):

В моем проекте уже есть ретроспективный анализ!...

Офф-топик наверное - а что за проект, поподробнее можно?

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

Не бейте меня, если я обманул ваши ожидания.

[ИСН]

ddn писал(а):

Не бейте меня, если я обманул ваши ожидания.

"Кто из вас по жизни всю дорогу компилился без Warning'ов, пусть первый бросит в него Exception"
а по сути - сказал ведь уже кто-то, что ретроспективный анализ бывает вынужден залезть о-го-го насколько вглубь...

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

ddn в сообщении #139657 писал(а):

Э-э.. Ваш вопрос несколько некорректно поставлен. Вы сейчас выдумываете какие-то незаконные рокировки и ходы. Есть только законные ходы!

В данном случае речь идёт о ретроанализе позиции, а не о перечислении позиций. При перечислении всё понятно. При ретроанализе мы имеем дело с ситуацией: некоторая позиция может возникнуть в результате рокировки. Вопрос — существует ли предшествующая часть игры, при которой эта рокировка является допусимым ходом? Поскольку мы идём с конца, мы не можем a priori сказать, могла или не могла быть рокировка.

ddn в сообщении #139657 писал(а):

Мои пункты - это детализация алгоритма такой оптимизации.

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

В тоже время целый ряд инвариантов может быть доказан от противного: например, не может быть одновременного шаха белым и чёрным (в частности, «короли не встречаются»). Для доказательства достаточно провести ретроанализ на один ход.

ddn в сообщении #139657 писал(а):

Ну как Вы вообще поймете, что тот или иной критерий не содержит ретроанализ в скрытой форме!

Вы имеете в виду, каково определение критерия, который не содержит ретроанализа? Например, что задающая критерий функция не является рекурсивной, т.е. не пытается анализировать позиции кроме данной.

Разница не в методе построения/доказательства критерия, а в том, как сам критерий работает.

ddn в сообщении #139657 писал(а):

Даю: $276$. Покажите!

ИСН в сообщении #139679 писал(а):

Вы путаете гипотезу Коллатца (это которая "3n+1" и которую проверить для любого числа - обычно не сильно труднее, чем записать само это число) с гипотезой $\sigma(n)-n$.

276, 138, 69, 208, 104, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

ddn в сообщении #139657 писал(а):

Для конкретной позиции все детали и особенности можно проанализировать непосредственно.

Известны композиции, в которых ретроанализ уходит на 40-50 ходов. (Каюсь, пытался отыскать на Интернете, не нашёл. Помню, листал древнюю подшивку Науки и Жизни — примерно 60-х.) Впрочем, у композиций другая цель.

Дело не в том, что Вы можете продемонстрировать для любой позиции. Дело в том, как это продемонстрировать для всех позиций.