Текущие шахматные алгоритмы проходят примерно на 1 или 2 уровня вниз по дереву возможных путей в зависимости от хода игрока и ходов противника. Допустим, у нас есть вычислительные возможности для разработки алгоритма, который предсказывает все возможные движения противника в шахматной игре. Алгоритм, который имеет все возможные пути, которые противник может пройти в любой момент в зависимости от ходов игроков. Может ли быть когда-нибудь идеальный шахматный алгоритм, который никогда не проиграет? Или, может быть, алгоритм, который всегда победит? Я имею в виду, что в теории кто-то, кто может предсказать все возможные ходы, должен быть в состоянии найти способ победить каждого из них или просто выбрать другой путь, если определенный из них приведет его к поражению.
edit-- Что мой вопрос на самом деле. Допустим, у нас есть вычислительная мощность для идеального алгоритма, который может играть оптимально. Что происходит, когда противник играет с тем же оптимальным алгоритмом? Это также относится ко всем играм с двумя игроками с конечным числом (очень большим или нет) ходов. Может ли быть когда-нибудь оптимальный алгоритм, который всегда побеждает?
Личное определение: оптимальный алгоритм - это идеальный алгоритм, который всегда выигрывает ... (не тот, который никогда не проигрывает, а тот, который всегда выигрывает
источник
Ответы:
Ваш вопрос похож на старый каштан: «Что происходит, когда непреодолимая сила встречает неподвижный объект?» Проблема заключается в самом вопросе: две описанные сущности не могут существовать в одной логически непротиворечивой вселенной. Ваш оптимальный алгоритм, алгоритм, который всегда выигрывает, не может быть сыгран обеими сторонами в игре, где одна сторона должна выиграть, а другая по определению проиграть. Таким образом, ваш оптимальный алгоритм, как определено, не может существовать.
источник
Во-первых, я считаю, что шахматные алгоритмы выглядят более чем на два уровня, хотя они не учитывают все различные возможности; Обрезка дерева поиска очень важна, чтобы избежать комбинаторного взрыва числа возможных ходов.
Для такой игры, как шахматы, есть три варианта определения личности победителя: либо игрок 1 имеет выигрышную стратегию, либо игрок 2 имеет выигрышную стратегию, либо оба игрока играют в оптимальной игре. Неизвестно, как обстоят дела с игрой в шахматы. Однако, поскольку шахматы - конечная игра, существует компьютерный алгоритм, состоящий из очень большого стола, который оптимально играет в шахматы.
Конечно, такой алгоритм не будет практичным. Но для некоторых более простых игр была определена «ценность» игры (какой игрок выигрывает, если таковой имеется), и был разработан оптимальный алгоритм. Такая игра известна как решенная игра .
Математическим предметом, который имеет дело с (так называемыми) комбинаторными играми, является теория комбинаторных игр . Математики разработали рекурсивный метод определения стоимости игры по заданному графику игры, который включает в себя все разрешенные позиции и ходы. Вы должны быть в состоянии найти описание этого алгоритма в записи Википедии или любых примечаниях к лекции по этому вопросу.
источник
Прежде всего, хорошие шахматные алгоритмы смотрят дальше, чем на 1 или 2 уровня. Вместо того, чтобы использовать поиск по наивному дереву, они выполняют альфа-бета-обрезку, чтобы сузить число вариантов для рассмотрения. Обратите внимание, что для начальных и конечных игр используется большая база данных ходов, так как она имеет лучшую производительность, чем поиск по дереву, который используется в середине игры.
На вопрос: я полагаю, что вы спрашиваете: « Решаемы ли шахматы ?». Гипотетически так и есть, хотя мнения расходятся о том, будет ли этот результат достигнут в ближайшее время. Например, шашки были решены в 2007 году, но у них намного меньше позиций (около квадратного корня из числа в шахматах). Смотрите статью в Википедии для получения дополнительной информации.
Между прочим, нынешние лучшие шахматные ИИ почти всегда побеждают или играют вничью с чемпионами мира; поэтому, хотя в настоящее время они не идеальны, алгоритмы, по крайней мере, довольно хороши!
источник
В принципе, шахматы разрешимы, как и любая другая игра. Однако, как указали другие ответы, в ближайшее время этого не произойдет.
Редактировать: в комментариях было отмечено, что [1] - обман, поэтому пропустите оставшуюся часть этого ответа.
Тем не менее, в этом направлении произошли некоторые недавние события. [1] утверждает, что показал, что шахматное открытие под названием « Королевский гамбит» решено : у белых есть только один ход, в то время как все остальные вступительные ходы приводят к победе черных. Обратите внимание, что [1] не исследовал дерево игры в полном объеме, а только утверждает, что эти результаты сохраняются с высокой вероятностью.
[1] http://chessbase.com/newsdetail.asp?newsid=8047
источник
Можно ли всегда выиграть партию в шахматы или нет, зависит от правил игры. Тем не менее, существует метод / алгоритм с именем Minimax (подробнее см. Https://en.wikipedia.org/wiki/Minimax ). Алгоритм состоит в том, чтобы попытаться предсказать, какой игрок имеет преимущество в различных сценариях с рекурсивной функцией. Вот четкое объяснение того, как это работает с более простой игрой: крестики-нолики https://www.neverstopbuilding.com/blog/2013/12/13/tic-tac-toe-understanding-the-minimax-algorithm13 ,
источник
добавит еще один ответ, который подчеркивает огромное пространство состояний, на самом деле не концептуализированное в вопросе или не указанное в других ответах. должен не согласиться с вашей предпосылкой:
см. информацию о статье Шеннона 1950 года «Программирование компьютера для игры в шахматы», в которой была представлена область компьютерных игр / алгоритмов игры в шахматы и анализ которых в основном не изменился и до сих пор звучит (даже в результате последующей компьютерной революции и закона Мура ). он оценивает количество ходов. это абсолютно астрономический. в диапазоне «никогда в рамках мыслимого оборудования, даже с революционными непредвиденными достижениями».
Это документированный психологический факт [3], возможно, один из многих психологических отклонений [2], что люди испытывают затруднения при понимании чисел такого масштаба. Смотрите также контрафактивное мышление . [4] , а суперкомпьютеры вычислить массовые проблемы, ее неоспоримая не в пределах любого суперкомпьютера , который в настоящее время построен и мог быть построен. (и многие поклонники шахмат утверждают, что этот «комбинаторный взрыв» в возможностях движения / позиции является неотъемлемым аспектом «аромата» игр, который, кажется, намеренно разработан в тысячелетней игре).
следовательно, шахматы принципиально отличаются от некоторых игр, в которых есть «разрешимые» пространства состояний меньшего размера [из которых есть некоторые исследования в области компьютерных наук, теории игр и т. д.], и некоторые ключевые способы не могут быть оценены в этих рамках.
Теперь, несмотря на это, возможно (но маловероятно), что в игре может быть теоретическое понимание, которое можно было бы использовать для существенного сокращения пространства поиска. это происходило с 1950 года, но на самом деле не было принципиально прорывных путей.
смотрите также
[1] какова вычислительная сложность решения шахмат, tcs.se
[2] предвзятость человека при суждении и принятии решений
[3] Студенты психологии публикуют исследования по концептуализации чисел
[4] контрфактивное мышление
источник