Число Шеннона
Число Шеннона , названное в честь американского математика Клода Шеннона , является консервативной нижней границей сложности дерева игры в шахматах , равной 10. 120 , в среднем около 10 3 возможности пары ходов, состоящей из хода белых, за которым следует ход черных, и типичная игра, продолжающаяся около 40 таких пар ходов.
Расчет Шеннона [ править ]
Шеннон показал расчет нижней границы сложности дерева игры в шахматах, в результате чего получилось около 10 120 возможных игр, чтобы продемонстрировать непрактичность решения шахмат методом грубой силы , в своей статье 1950 года «Программирование компьютера для игры в шахматы». [1] (Эта влиятельная статья представила область компьютерных шахмат .)
Шеннон также оценил количество возможных должностей общего порядка: или примерно 3,7*10 43 . Сюда входят некоторые незаконные позиции (например, пешки на первой горизонтали, оба короля под шахом) и исключаются законные позиции после взятий и превращений.
| Количество слоев (полуходов) | Количество возможных позиций [2] | Количество матов [3] |
|---|---|---|
| 1 | 20 | 0 |
| 2 | 400 | 0 |
| 3 | 8,902 | 0 |
| 4 | 197,281 | 8 |
| 5 | 4,865,609 | 347 |
| 6 | 119,060,324 | 10,828 |
| 7 | 3,195,901,860 | 435,767 |
| 8 | 84,998,978,956 | 9,852,036 |
| 9 | 2,439,530,234,167 | 400,191,963 |
| 10 | 69,352,859,712,417 | 8,790,619,155 |
| 11 | 2,097,651,003,696,806 | 362,290,010,907 |
| 12 | 62,854,969,236,701,747 | 8,361,091,858,959 |
| 13 | 1,981,066,775,000,396,239 | 346,742,245,764,219 |
| 14 | 61,885,021,521,585,529,237 | |
| 15 | 2,015,099,950,053,364,471,960 |
После того, как каждый игрок передвинул фигуру по 5 раз (10 ходов ), остается 69 352 859 712 417 возможных игр.
Более жесткие границы [ править ]
Верхний [ править ]
Принимая во внимание числа Шеннона, Виктор Эллис вычислил верхнюю границу 5 × 10. 52 по количеству позиций и оценил истинное число примерно в 10 50 . [4] Последние результаты [5] улучшите эту оценку, доказав верхнюю границу 8,7x10 45 , и показывая [6] [7] верхняя граница 4×10 37 при отсутствии промоакций.
Нижний [ править ]
Эллис также оценил сложность игрового дерева как минимум в 10. 123 , «на основе среднего коэффициента ветвления 35 и средней длины игры 80». Для сравнения: количество атомов в наблюдаемой Вселенной , с которой ее часто сравнивают, примерно оценивается в 10. 80 .
оценки Точные
Джон Тромп и Питер Остерлунд оценили количество легальных шахматных позиций с уровнем достоверности 95% на уровне , основанный на эффективно вычислимой биекции между целыми числами и шахматными позициями. [5]
Количество разумных шахматных партий [ править ]
По сравнению с числом Шеннона, если шахматы анализируются на предмет количества «разумных» игр, в которые можно сыграть (не считая нелепых или очевидных проигрышных ходов, таких как перемещение ферзя для немедленного захвата пешкой без компенсации), тогда результат ближе к 10 40 игры. Это основано на выборе примерно трех разумных ходов на каждом этапе (полухода) и продолжительности игры 80 ходов (или, что эквивалентно, 40 ходов). [8]
См. также [ править ]
Примечания и ссылки [ править ]
- ^ Клод Шеннон (1950). «Программирование компьютера для игры в шахматы» (PDF) . Философский журнал . 41 (314). Архивировано из оригинала (PDF) 23 мая 2020 г.
- ^ "A048987 - Оайс" .
- ^ "A079485 - Оайс" .
- ^ Виктор Эллис (1994). В поисках решений в играх и искусственном интеллекте (PDF) . доктор философии Диссертация, Лимбургский университет , Маастрихт, Нидерланды. ISBN 978-90-900748-8-7 .
- ^ Перейти обратно: а б Джон Тромп (2022). «Рейтинг шахматных позиций» . Гитхаб .
- ^ С. Штайнербергер (2015). «О количестве позиций в шахматах без повышения». Международный журнал теории игр . 44 (3): 761–767. дои : 10.1007/s00182-014-0453-7 . S2CID 31972497 .
- ^ Гурион, Дэниел (16 декабря 2021 г.), Верхняя граница количества шахматных диаграмм без повышения , arXiv : 2112.09386 , получено 18 декабря 2021 г.
- ^ "Сколько возможно шахматных партий?" Доктор Джеймс Грайм рассказывает о числе Шеннона и других шахматных штучках (фильмы Брейди Харана). ИИГГ, Математические науки.