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

Число Шеннона, названное в честь американского математика Клода Шеннона, является консервативной нижней границей (не оценкой) сложности дерева игр для chess из 10, основанной на среднем примерно 10 возможных вариантах для пары ходов, состоящих из за белыми следует ход за черных, и типичная партия длится около 40 таких пар ходов.

• 1 Расчет Шеннона
• 2 Более узкие границы
  • 2.1 Верхний
  • 2.2 Нижний
• 3 Количество разумных шахматных партий
• 4 См. Также
• 5 Примечания и ссылки
• 6 Внешние ссылки

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

Шеннон также оценил количество возможных позиций «общего порядка $64!\; 32!\; 8!\; 2\; 2\; !\; 6\; \{\backslash \; displaystyle\; \backslash \; scriptstyle\; \{\backslash \; frac\; \{64!\}\; \{32!\; \{8!\}\; ^\; \{2\}\; \{2!\}\; ^\; \{6\}\}\}\}$, или примерно 10 дюймов. Сюда входят некоторые незаконные позиции (например, пешки на первом ряду, оба короля под шахом) и исключаются легальные позиции после взятия и повышения.

После того, как каждый игрок передвинул фигуру 5 раз (10 ходов ), остается 69,352,859,712,417 возможных игр.

Верхний

Принимая во внимание числа Шеннона, Виктор Аллис рассчитал верхнюю границу 5 × 10 для количество позиций, а истинное число оценивается как около 10. Недавние результаты улучшают эту оценку, доказывая верхнюю границу ниже 2, которая меньше 10, и показывает верхнюю границу 2 × 10 в отсутствие рекламных акций.

Нижний

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

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

• Шахматный портал

• Решение шахмат
• Го и математика
• Сложность игры

1. ^Клод Шеннон (1950). «Программирование компьютера для игры в шахматы» (PDF). Philosophical Magazine. 41(314).
2. ^Виктор Аллис (1994). Поиск решений в играх и искусственном интеллекте (PDF). Кандидат наук. Диссертация, Лимбургский университет, Маастрихт, Нидерланды. ISBN 978-90-900748-8-7.
3. ^Джон Тромп (2010). «Шахматная площадка Джона».
4. ^С. Штайнербергер (2014). «Международный журнал теории игр». Международный журнал теории игр. 44 (3): 761–767. doi : 10.1007 / s00182-014-0453-7.
5. ^«Сколько шахматных партий возможно?» Доктор Джеймс Грайм говорит о числе Шеннона и других шахматах (фильмы Брэди Харана). ИИГС, математические науки.

• Математика и шахматы