Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

Частичные результаты [ править ]

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

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

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

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

Теоретик информации Клод Шеннон в 1951 году утверждал, что ни один компьютер не может реально решить шахматы, поскольку ему нужно либо сравнить примерно 10 120 возможных вариантов игры, либо иметь «словарь», обозначающий оптимальный ход для каждого из примерно 10 43 возможных положения доски. [4] Таким образом, теоретически возможно решить шахматы, но требуемые временные рамки (по Шеннону 10 90 лет) ставят эту возможность за пределы любой возможной технологии.

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

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

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

Варианты шахмат [ править ]

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

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

См. Также [ править ]

  • Число Шеннона (вычисление нижней границы сложности дерева игр в шахматы)
  • Преимущество первого хода в шахматах

Ссылки [ править ]

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

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

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

Внешние ссылки [ править ]

  • «Бесконечные шахматы, бесконечная серия PBS» Бесконечные шахматы, бесконечная серия PBS.