Число возможных шахматных партий

[Ktina]

У товарища Мунафо прочла следующее:

Товарищ Мунафо писал(а):

$10^{10^{50}}$- An estimate of the number of possible chess games, given by G. H. Hardy ("Ramanujan: Twelve Lectures on Subjects Suggested by His Life and Work", 1999).

Как говорил великий Станиславский,

Великий Станиславский писал(а):

Не верю!

Давайте найдём самую самую самую грубую верхнюю границу:

У меня не более 16 фигур, каждая из которых может пойти на одно из не более 64 полей. Следовательно, для каждого полухода - не более 1024 возможностей.

Далее, если за 50 ходов (100 полуходов) не была взята ни одна фигура и не была продвинута ни одна пешка, игра заканчивается.
У нас 32 фигуры и 96 продвижений пешек (16 пешек, по 6 продвижений на каждую), следовательно, через

$$100\cdot(32+96)=100\cdot 128=12800$$

полуходов игра закончится в любом случае.

Таким образом, число возможных шахматных партий не превышает

$$1024^{12800}<(10^4)^{(10^5)}<10^{10^6}$$

, что намнооого меньше $10^{10^{50}}$.

Так с чем же мы имеем дело?

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

А когда ввели правило 50 ходов?

[Ktina]

Профессор Снэйп в сообщении #592326 писал(а):

А когда ввели правило 50 ходов?

Извольте просветить.

Кстати, забыла дать ссылку на товарища Мунафо: http://mrob.com/pub/math/numbers-21.html#lp1_e050_1

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

Ktina в сообщении #592327 писал(а):

Извольте просветить.

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

Вот что в статье из Вики написано:

Цитата:

В XIX веке правило применялось в различных версиях и только к определённым эндшпилям.

Рамануджан, я так понимаю, мог застать ещё другую версию этого правила.

[Ktina]

Профессор Снэйп в сообщении #592328 писал(а):

Вот что в статье из Вики написано:

Цитата:

В XIX веке правило применялось в различных версиях и только к определённым эндшпилям.

Даже если дать миллион ходов на партию, всё равно не выходит.

[worm2]

Да, странная оценка. Если у нас нет ограничения на число ходов, то шахматная партия может длиться сколь угодно долго.
Хотя подождите... Кажется, я понял в чём дело. $10^{50}$ — это похоже на оценку числа позиций (с точностью до десятка порядков). Таким образом, $10^{10^{50}}$ похоже на оценку числа партий, которые завершаются только по правилу трёхкратного повторения позиции (ну и всяких там матов с патами). С хорошим таким запасом оценка

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

worm2 в сообщении #592343 писал(а):

по правилу трёхкратного повторения позиции

Да, я вот тоже про это вспомнил.

[Ktina]

worm2 в сообщении #592343 писал(а):

Да, странная оценка. Если у нас нет ограничения на число ходов, то шахматная партия может длиться сколь угодно долго.
Хотя подождите... Кажется, я понял в чём дело. $10^{50}$ — это похоже на оценку числа позиций (с точностью до десятка порядков). Таким образом, $10^{10^{50}}$ похоже на оценку числа партий, которые завершаются только по правилу трёхкратного повторения позиции (ну и всяких там матов с патами). С хорошим таким запасом оценка

Всё равно не понимаю, как получается $10^{10^{50}}$

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

Попытаюсь прикинуть число позиций.

При всех фигурах (и пешках) на доске получается

$$ \frac{64!}{32! \cdot 8! \cdot 8! \cdot 2^6} \cdot k \approx k \cdot 4.63 \cdot 10^{42} $$

Какой из числовых множителей за что отвечает, думаю, пояснять не надо. Множитель $k > 2$ учитывает особенности некоторых позиций, не связанные с расстановкой фигур (очерёдность хода, возможности для рокировок, возможности для взятия пешек на проходе). А ещё пешки могут превращаться в чо попало...

Естественно, что не все позиции возможны. С другой стороны, все фигуры не обязаны присутствовать на доске.

-- Чт июл 05, 2012 17:50:29 --

Но да, с точностью до нескольких порядков $10^{50}$ - хорошая оценка для количества возможных позиций. Теперь если партией считать произвольную последовательность из десяти позиций, то получается $10^{10^{50}}$ партий

[Ktina]

Профессор Снэйп в сообщении #592380 писал(а):

...Теперь если партией считать произвольную последовательность из десяти позиций, то получается $10^{10^{50}}$ партий

Так почему из десяти?
А, кажись, поняла.
Если вместо десяти взять 100 или 1000, разница будет пренебрежибельной, поскольку

$$100^{10^{50}}=(10^2)^{10^{50}}=10^{2\cdot 10^{50}}<10^{10^{51}}$$

, то есть можно взять даже не тысячу, а миллиард.

[Утундрий]

Интересно, а сколько у вас с таким подходом получится позиций для, к примеру, крестиков-ноликов?

[Ktina]

Утундрий в сообщении #592584 писал(а):

Интересно, а сколько у вас с таким подходом получится позиций для, к примеру, крестиков-ноликов?

$3^9$ возможных позиций, $(3^9)$...ой, стоп-машина!
Так в шахматах тогда не $10^{10^{50}}$ получается, а $(10^{50})^{10}$...

[Утундрий]

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

[Yu_K]

А кто-то пробовал варианты судоку посчитать? Там попроще... и была статейка на архивах...

[Хорхе]

Где-то я читал, что Харди просто сделал описку, и на самом деле его оценка -- $10^{10^5}$.