Число Шеннона , названное в честь американского математика Клода Шеннона , представляет собой консервативную нижнюю границу сложности дерева игры в шахматы, равную 10 120 , на основе в среднем примерно 10 3 возможностей для пары ходов, состоящих из следующего хода белых. ходом за черных, и типичная игра продолжительностью около 40 таких пар ходов.
Расчет Шеннона [ править ]
Шеннон показал расчет для нижней границы игрового дерева сложности шахмат, в результате чего около 10 120 возможных игр, чтобы продемонстрировать непрактичность решения шахматы по грубой силе , в его 1950 статьи «Программирование компьютера для игры в шахматах». [1] (Эта влиятельная статья познакомила с компьютерными шахматами .)
Шеннон также оценил количество возможных позиций, « примерно 10 43 ». Сюда входят некоторые незаконные позиции (например, пешки на первом ряду, оба короля под шахом) и исключаются легальные позиции после взятия и повышения.
| Количество слоев (полуходов) | Количество возможных игр |
|---|---|
| 1 | 20 |
| 2 | 400 |
| 3 | 8 902 |
| 4 | 197 281 |
| 5 | 4 865 609 |
| 6 | 119 060 324 |
| 7 | 3,195,901,860 |
| 8 | 84 998 978 956 |
| 9 | 2,439,530,234,167 |
| 10 | 69 352 859 712 417 |
После того, как каждый игрок передвинул фишку 5 раз (10 слоев ), остается 69 352 859 712 417 возможных игр, которые можно было сыграть.
Более узкие границы [ править ]
Верхний [ править ]
Принимая во внимание числа Шеннона, Виктор Аллис вычислил верхнюю границу 5 × 10 52 для количества позиций и оценил истинное число как около 10 50 . [2] Недавние результаты [3] улучшают эту оценку, доказывая верхнюю границу ниже 2 155 , которая меньше 10 46,7, и показывая [4] верхнюю границу 2 × 10 40 в отсутствие рекламных акций.
Нижний [ править ]
Аллис также оценил сложность дерева игр как минимум 10 123 «на основе среднего коэффициента ветвления 35 и средней продолжительности игры 80». Для сравнения, количество атомов в наблюдаемой Вселенной , с которой ее часто сравнивают, приблизительно оценивается как 10 80 .
Количество разумных шахматных партий [ править ]
Для сравнения с числом Шеннона, если шахматы анализируются на предмет количества «разумных» партий, в которые можно сыграть (не считая смешных или очевидных проигрышных ходов, таких как перемещение ферзя для немедленного взятия пешкой без компенсации), то результат приближается к 10 40 играм. Это основано на выборе примерно из трех разумных ходов на каждом слое (полуход) и продолжительности игры в 80 ходов. [5]
См. Также [ править ]
Примечания и ссылки [ править ]
- ^ Клод Шеннон (1950). «Программирование компьютера для игры в шахматы» (PDF) . Философский журнал . 41 (314).
- ↑ Виктор Аллис (1994). Поиск решений в играх и искусственном интеллекте (PDF) . Кандидат наук. Диссертация, Лимбургский университет , Маастрихт, Нидерланды. ISBN 978-90-900748-8-7.
- ^ Джон Тромп (2010). «Шахматная площадка Джона» .
- ^ С. Steinerberger (2014). «Международный журнал теории игр». Международный журнал теории игр . 44 (3): 761–767. DOI : 10.1007 / s00182-014-0453-7 .
- ^ "Сколько шахматных партий возможно?" Доктор Джеймс Грайм говорит о числе Шеннона и других шахматах (фильмы Брэди Харана). ИИГС, математические науки.
Внешние ссылки [ править ]
- Математика и шахматы
