Решение шахмат - Solving chess

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

В более слабом смысле решение шахмат может относиться к доказательству того, какой из трех возможных исходов (победа белых; победа черных; ничья) является результатом двух идеальных игроков, не обязательно раскрывая саму оптимальную стратегию (см. косвенное доказательство ).[1]

Нет полного решения для шахмат ни в одном из двух смыслов. известен, и не ожидается, что шахматы будут решены в ближайшем будущем. Существуют разногласия по поводу того, экспоненциальный рост вычислительной мощности будет продолжаться достаточно долго, чтобы когда-нибудь ее можно было решить "грубая сила ", т.е. проверив все возможности.

Частичные результаты

абcdежграммчас
8
Chessboard480.svg
а7 черная ладья
h7 черный рыцарь
c6 белая королева
f4 черный король
d3 белый король
h2 белый конь
d1 черный слон
h1 черная королева
8
77
66
55
44
33
22
11
абcdежграммчас
А помощник капитана 546 позиция найдена в 7-частном столе Ломоносова. Ход белых. (В этом примере добавляется 8-я фигура с помощью банального взятия первым ходом.)

Таблицы для эндшпиля решали шахматы в ограниченной степени, определяя идеальную игру в ряде эндшпиль, включая все нетривиальные эндшпили, в которых не более семи фигур или пешек (включая двух королей).[2]

Одним из следствий разработки основы таблицы эндшпиля из 7 фигур является то, что было найдено много интересных теоретических концовок. Одним из примеров является позиция «мат на 546», которая при идеальной игре представляет собой принудительный мат за 546 ходов, игнорируя Правило 50 ходов.[3] Такая позиция недоступна для решения любого человека, и ни один шахматный движок также не играет ее правильно без доступа к базе данных.

Прогнозы относительно того, когда и будут ли решены шахматы

Теоретик информации Клод Шеннон В 1951 году утверждал, что ни один компьютер не может решить шахматы, так как ему нужно будет сравнить примерно 10120 возможных вариантов игры, или иметь "словарь", обозначающий оптимальный ход для каждого из примерно 1043 возможные позиции доски.[4] Таким образом, теоретически возможно решать шахматы, но требуемые временные рамки (по Шеннон, 1090 лет) выводит эту возможность за пределы любой возможной технологии.

Однако количество математических операций, необходимых для решения шахмат, может значительно отличаться от количества операций, необходимых для получения всего игровое дерево шахмат. В частности, если у белых принудительный выигрыш, только часть дерева игры потребует оценки для подтверждения существования принудительного выигрыша (т.е.без опровержений со стороны черных). Более того, расчет сложности шахмат Шенноном предполагает, что средняя продолжительность игры составляет 40 ходов, но нет математического основания утверждать, что принудительная победа любой из сторон будет иметь какое-либо отношение к этой продолжительности игры. Действительно, в некоторых партиях, сыгранных с умением (игра на уровне гроссмейстера), было всего 16 ходов. По этим причинам математики и теоретики игр не хотели категорически заявлять, что решение шахмат - неразрешимая проблема.[4][5]

Ханс-Иоахим Бремерманн, профессор математика и биофизика на Калифорнийский университет в Беркли, далее утверждал в статье 1965 года, что «скорость, память и вычислительная мощность любого возможного компьютерного оборудования будущего ограничены определенными физическими барьерами: световой барьер, то квантовый барьер, а термодинамический барьер. Эти ограничения означают, например, что ни один компьютер, каким бы он ни был сконструирован, никогда не сможет исследовать все дерево возможных последовательностей ходов игры в шахматы ». Тем не менее, Бремерманн не исключил возможность того, что компьютер когда-нибудь сможет решать шахматы. Он писал: «Для того, чтобы компьютер играл в идеальную или почти идеальную игру, необходимо либо полностью проанализировать игру ... либо проанализировать игру приблизительным образом и объединить это с ограниченным количеством поиска по дереву. ... Однако теоретического понимания такого эвристического программирования все еще очень не хватает ".[6]

Последние научные достижения существенно не изменили эти оценки. Игра шашки была (слабо) решена в 2007 г.,[7] но он имеет примерно квадратный корень из числа шахматных позиций. Джонатан Шеффер, ученый, который возглавлял эту работу, сказал о прорыве, таком как квантовые вычисления может потребоваться до того, как можно будет попытаться решить шахматы, но он не исключает такой возможности, говоря, что единственное, чему он научился в результате своих 16-летних усилий по решению шашек, «никогда не недооценивать достижения в области технологий».[8]

Варианты шахмат

Немного шахматные варианты которые проще, чем шахматы. Выигрышная стратегия для черных в Махараджа и сипаи легко запомнить. 5 × 5 Минишахи Гарднера вариант был слабо решено как ничья.[9] Несмотря на то что Проигрыш в шахматы играется на доске 8x8, его правило принудительного захвата сильно ограничивает его сложность, и вычислительный анализ не помог решить этот вариант как победу белых.[10]

Перспектива решения индивидуальных, конкретных шахматных партий становится все более трудной по мере увеличения размера доски, например, в больших шахматных вариантах, и бесконечные шахматы.[11]

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

Рекомендации

  1. ^ Аллис, В. (1994). «Кандидатская диссертация: поиск решений в играх и искусственный интеллект» (PDF). Департамент компьютерных наук. Лимбургский университет. Получено 2012-07-14.
  2. ^ "Ломоносовские столы". Получено 2013-04-24.
  3. ^ "Кто выиграет от этой головоломки?" Шахматная позиция mate-in-546, с обсуждением (Сообщение 1: Позиция, Сообщение 7: Играбельно).
  4. ^ а б Шеннон, К. (Март 1950 г.). «Программирование компьютера для игры в шахматы» (PDF). Философский журнал. 7. 41 (314). В архиве (PDF) из оригинала от 15.03.2010. Получено 2008-06-27.

    «В шахматах, в принципе, можно вести идеальную игру или сконструировать машину для этого следующим образом: в данной позиции рассматриваются все возможные ходы, затем все ходы соперника и т. Д. До конца игра (в каждом варианте). Конец должен наступить по правилам игры после конечного числа ходов (помня Правило рисования на 50 ходов ). Каждый из этих вариантов заканчивается победой, поражением или ничьей. Работая в обратном направлении от конца, можно определить, есть ли принудительный выигрыш, ничья или проиграна. Однако легко показать, что даже при высокой скорости вычислений, доступной в электронных калькуляторах, это вычисление непрактично. В типичных шахматных позициях будет порядка 30 разрешенных ходов. Это число остается постоянным до тех пор, пока игра почти не закончится, как показано ... Де Гроотом, который усреднил количество разрешенных ходов в большом количестве мастер-игр. Таким образом, ход белых, а затем ход черных дает примерно 103 возможности. Типичная игра длится около 40 ходов до выхода одной из сторон. Для наших расчетов это консервативно, поскольку машина рассчитывала бы мат, а не отставку. Однако даже на этой цифре будет 10120 вариации, которые должны быть рассчитаны от начальной позиции. Для машины, работающей со скоростью одно изменение в микросекунду, потребуется более 1090 лет, чтобы рассчитать первый ход! "

  5. ^ http://www.chessgames.com Магнус Карлсен против Вишванатлана Ананда, King's Indian Attack: Двойной Фианкетто (A07), 1 / 2-1 / 2, 16 ходов.
  6. ^ Бремерманн, Х.Дж. (1965). «Квантовый шум и информация». Proc. 5-й симпозиум в Беркли. Математика. Статистика и вероятность. Архивировано из оригинал на 27 мая 2001 г.
  7. ^ Шеффер, Джонатан; Берч, Нил; Бьёрнссон, Ингви; и другие. (14 сентября 2007 г.). «Шашки решены». Наука. 317 (5844): 1518–1522. Дои:10.1126 / science.1144079. PMID  17641166.(требуется подписка)
  8. ^ Сридхар, Сухас. "Шашки, решены!". Spectrum.ieee.org. Архивировано из оригинал на 2009-03-25. Получено 2009-03-21.
  9. ^ Мхалла, Мехди; Прост, Фредерик (2013-07-26). «Вариант минишах Гарднера решен». arXiv:1307.7118 [cs.GT ].
  10. ^ Уоткинс, Марк. «Проигрыш в шахматы: 1. e3 побеждает белых» (PDF).
  11. ^ Авиезри Френкель; Д. Лихтенштейн (1981), «Вычисление идеальной стратегии для шахмат n × n требует экспоненциального времени от n», J. Combin. Теория Сер. А, 31 (2): 199–214, Дои:10.1016/0097-3165(81)90016-9

внешняя ссылка