stringtranslate.com

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

Клод Шеннон

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

Расчет Шеннона

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

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

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

Более узкие границы

Верхний

Приняв во внимание числа Шеннона, Виктор Эллис вычислил верхнюю границу 5×10 52 для числа должностей и оценил истинное число примерно в 10 50 . [4] Более поздние работы доказали верхнюю границу 8,7×10 45 , [5] и показали верхнюю границу 4×10 37 при отсутствии повышений. [6] [7]

Ниже

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

Точные оценки

Джон Тромп и Питер Остерлунд оценили количество допустимых шахматных позиций с уровнем достоверности 95% , основываясь на эффективно вычислимой биекции между целыми числами и шахматными позициями. [5]

Количество разумных шахматных партий

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

Смотрите также

Примечания и ссылки

  1. ^ Шеннон, Клод Э. (март 1950 г.). Леви, Дэвид (ред.). "XXII. Программирование компьютера для игры в шахматы" (PDF) . Philosophical Magazine . 7. 41 (314). Нью-Йорк, Нью-Йорк: Springer : 256–275. doi :10.1080/14786445008521796. ISBN 978-1-4757-1970-3. ISSN  1941-5982. Архивировано из оригинала (PDF) 2020-05-23.
  2. ^ "A048987". OEIS .
  3. ^ "A079485". OEIS .
  4. ^ Эллис, Виктор (1994). Поиск решений в играх и искусственном интеллекте (PDF) . Маастрихт, Нидерланды: докторская диссертация, Университет Лимбурга . ISBN 978-90-900748-8-7.
  5. ^ ab Тромп, Джон (2022). «Рейтинг шахматных позиций». GitHub .
  6. ^ Штейнербергер, Стефан (август 2015 г.). «О числе позиций в шахматах без продвижения». International Journal of Game Theory . 44 (3): 761–767. doi :10.1007/s00182-014-0453-7. ISSN  0020-7276. S2CID  31972497.
  7. ^ Гурион, Даниэль (12 октября 2022 г.). «Верхняя граница числа шахматных диаграмм без продвижения». Журнал ICGA . 44 (2) (версия 2-го изд.): 44–55. arXiv : 2112.09386 . doi : 10.3233/ICG-220210 . Получено 18.12.2021 .
  8. ^ Грайм, Джеймс (24 июля 2015 г.). Сколько шахматных партий возможно? (Видео). Numberphile – через YouTube .Доктор Джеймс Грайм рассказывает о числе Шеннона и других шахматных вещах (фильмы Брэди Харана). MSRI, Математические науки.

Внешние ссылки