Есть ли больше 40-ходовых шахматных партий, чем атомов во Вселенной?

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

• В более ранних сообщениях упоминается число Шеннона , которое является его оценкой сложности дерева игры в шахматы (т. е. количества возможных игр ). Шеннон дал оценку 10 ¹²⁰ в качестве примечания в «Программировании компьютера для игры в шахматы». Другая оценка Виктора Эллиса составила 10 ¹²³ (это упоминается в его докторской диссертации, ссылка на которую приведена на странице Википедии ). Он написал:

Сложность шахматного дерева 10 ¹²³ основана на среднем коэффициенте ветвления 35 и средней продолжительности игры 80 дюймов.

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

• Вышеупомянутое кажется перепутанным со сложностью пространства состояний , т. е. числом возможных допустимых и достижимых позиций на шахматной доске (которое кардинально отличается от числа, запрашиваемого в вопросе). Фактически, строгая верхняя граница для этого была получена Аллисом (указ. соч.) как 5 * 10 ⁵² , что намного меньше, чем количество атомов в видимой Вселенной (по оценкам, 10 ⁸⁰ ; ср . Википедия ).

Обозначение : Ход в шахматах состоит из двух ходов , один ход белыми и один ход черными. Таким образом, у нас есть « мат в два хода » (1. f3 e5 2. g4 Фh4#). Используемая здесь нотация является алгебраической .

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

1. e4 e5
2. d4 d5
3. с3 с6

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

• Белый белопольный слон может ходить на любую клетку по диагонали f1-a6 (6 клеток => 5 возможных ходов).
• Белый чернопольный слон может ходить на любое поле по диагонали c1-h6 (6 полей => 5 возможных ходов).
• Белый ферзь может ходить на любое поле по диагонали d1-a4 (4 поля => 3 возможных хода).
• Белый конь на g1 может ходить на любую клетку из множества {g1,f3} (2 клетки => 1 возможный ход).

Черные фигуры ограничены симметрично. Продолжайте это для следующих 74 слоев. Затем белый игрок сдается.

Мы наблюдаем, что:

• Кусочки никогда не мешают друг другу. Захваты никогда не делаются. Проверка никогда не происходит. Следовательно, для каждого слоя есть 14 разрешенных ходов.

• Мы использовали очень немногие из реальных возможных ходов, доступных нам. Возможных 40-ходовых игр будет намного больше, чем в этом классе.

• Эти партии длятся ровно 40 ходов. (Если вы считаете отставку за слой, то вы можете отказаться от черного на предыдущем слое.)

Следовательно, мы построили набор из 14 ⁷⁴ различных шахматных партий по 40 ходов. Более того, 14 ⁷⁴ > 10 ⁸⁴ , а 10 ⁸⁰ — это оценка числа атомов в наблюдаемой Вселенной .

Некоторые комментарии:

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

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

• Вероятно, вокруг есть конструкции получше, чем то, что я привожу здесь.

Редактировать 2019-01: ответ на этот вопрос сводится к знанию того, сколько существует возможных способов сыграть в шахматы с 40 ходами и сколько атомов существует во Вселенной. Последнее известно, и все эти ответы в конечном итоге цитируют шахматных экспертов, различающихся только интерпретацией своих фигур.

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

DavePhD также изложил цитаты наиболее явно, показывая, что моя зависимость от сайта Wolfram была ошибочной.

Редактировать: я оставлю оригинал как есть, но хочу добавить исправление благодаря комментарию Майка Данлави. Я неправильно понял вопрос, и поэтому, если вопрос действительно заключается в том, что игры, длящиеся 40 ходов или меньше (я читал, 40 ходов или больше), больше, чем количество атомов во Вселенной, я переключаю свой ответ на несогласие. Все числа приведены ниже, но теперь мы сравниваем 10 ^ 80 (количество атомов) и 10 ^ 43 (количество из 40 ходов или менее шахматных партий). Таким образом, число атомов больше.

Я согласен.

Во- первых, Вики приводит эту цифру о количестве атомов во Вселенной:

Два приблизительных расчета дают количество атомов в наблюдаемой Вселенной близкое к 10^80.

Затем Вики предоставляет число Шеннона как количество возможных шахматных партий, в которые можно сыграть:

Сложность шахматного дерева была впервые рассчитана Клодом Шенноном как 10 ^ 120, число, известное как число Шеннона.

Наконец, Wolfram Mathworld приводит число игр менее 40 ходов :

Количество возможных игр из 40 ходов или менее P(40) приблизительно равно 10^40 (Beeler et al. 1972) ... Шеннон (1950) дал оценку: P(40) = 64! / (32! * 8! ^ 2 * 2! ^ 6) = 10 ^ 43.

Я вижу, что пришли другие ответы, пока я печатал. Кажется, что они сравнивают общее количество возможных игр (10^120) с количеством атомов во вселенной (10^80), но вы ищете количество атомов по сравнению с играми, в которых больше 40 ходов . В таком случае мы рассматриваем:

10^80 против 10^120 - 10^43 (для осторожности)

Справедливости ради, собственный ответ автора (@Vian) правильный, поскольку 10 ^ 43 даже не вдавливает 10 ^ 120 и, следовательно, по сути все еще сравнивает 10 ^ 80 и 10 ^ 120. Просто хотел объяснить, почему я думаю, что вопрос немного отличается от простого сравнения количества атомов и количества всех возможных шахматных партий.

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

В частности, сайт http://mathworld.wolfram.com/Chess.html перепутал количество позиций с количеством 40-ходовых партий.

Хотя математический мир говорит

Количество возможных игр из 40 ходов или менее P(40) приблизительно равно 10^(40) (Beeler et al. 1972).

Сама ссылка Билера очень ясна, что речь идет о позициях, а не об играх:

Есть около 10^40 возможных позиций

и хотя математический мир говорит

Шеннон (1950) дал оценку ... 10 ^ 43.

Шеннон действительно писал в XXII. Программирование компьютера для игры в шахматы Философский журнал , Сер.7, Том. 41, № 314 - март 1950 г.:

В типичных шахматных позициях допустимо порядка 30 ходов. Число сохраняется практически постоянным до тех пор, пока игра почти не закончится, как показано на рис. 1. Этот график был построен на основе данных, предоставленных Де Гроотом, который усреднил количество разрешенных ходов в большом количестве основных игр ( De Groot, 1946, a ). Таким образом, ход за белых, а затем за черных дает около 1000 возможностей . Типичная партия длится около 40 ходов до отказа одной из сторон. Это консервативно для нашего расчета, поскольку машина будет рассчитывать на мат, а не на отставку. Однако даже при таком значении будет 10^120 вариаций , которые нужно будет рассчитать от исходной позиции.

...

Другой (столь же непрактичный) метод — иметь «словарь» всех возможных положений шахматных фигур. Для каждой возможной позиции есть запись, дающая правильный ход (либо рассчитанный с помощью описанного выше процесса, либо предоставленный шахматным мастером). Когда машина делает ход, она просто ищет позицию и делает указанный ход. Количество возможных позиций, общего порядка 64! / 32!(8!)^2(2!)^6 или примерно 10^43

В шахматах «игра на 40 ходов» означает, что каждый игрок ходит фигурой 40 раз: 80 ходов или 80 полуходов.

в стандартной шахматной терминологии один ход состоит из хода каждого игрока ; следовательно, ход в шахматах — это полуход. Таким образом, после 20 ходов в шахматной партии было выполнено 40 слоев — 20 белыми и 20 черными.

Таким образом, для игры с 40 ходами, если аппроксимировано, что существует некоторое постоянное (c) количество допустимых полуходов, приближение количества игр с 40 ходами имеет вид:

с ^ 80

Итак, пока «с» больше 10, количество игр с 40 ходами больше, чем количество атомов во Вселенной.

Например, есть 20 возможных первых полуходов (16 ходов пешкой и 4 хода конем) и 20 возможных вторых полуходов.

Итак, Шеннон, цитируя Де Гроота, использует оценку «30» для «с» и, следовательно:

30 ^ 80 = ~ 1,5 х 10 ^ 118

Итак, да, игр с 40 ходами (80 полуходами) ровно больше, чем количество атомов во Вселенной .

После некоторого лучшего поиска я нашел это:

Число Шеннона

Аллис также оценил сложность дерева игры как минимум в 10 ^ 123, «исходя из среднего коэффициента ветвления 35 и средней продолжительности игры 80». Для сравнения, количество атомов в наблюдаемой Вселенной, с которой ее часто сравнивают, оценивается между 4×10^79 и 10^81.

http://en.wikipedia.org/wiki/Шеннон_номер

Кроме того, вот кто-то, кто пытается объяснить это более ясно .

Небольшой поиск в Google дает следующие оценки:

Атомов во вселенной: 10^80

40-ходовые шахматные партии: 10^40

дать или взять несколько нулей.