Есть ли идеальный алгоритм для шахмат?

Question

Недавно я беседовал с не-кодером о возможностях шахматных компьютеров. Я не очень хорошо разбираюсь в теории, но думаю, что знаю достаточно.

Я утверждал, что не может быть детерминированной машины Тьюринга, которая всегда побеждала или зашла в тупик в шахматах. Я думаю, что даже если вы будете искать по всему пространству всех комбинаций ходов игрока 1/2, единственный ход, который компьютер выбирает на каждом шаге, основан на эвристике. Основанный на эвристике, он не обязательно побеждает ВСЕ ходы, которые мог сделать противник.

Мой друг, напротив, думал, что компьютер всегда будет выигрывать или проигрывать, если он никогда не совершит «ошибку» (но вы это определяете?). Тем не менее, будучи программистом, взявшим CS, я знаю, что даже ваш удачный выбор - учитывая мудрого противника - может заставить вас сделать «ошибочные» шаги в конце. Даже если вы знаете все, ваш следующий шаг будет жадным в соответствии эвристике.

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

Редактировать: Хм ... похоже, что я тут взъерошил некоторые перья. Это хорошо.

Если подумать еще раз, кажется, что нет теоретической проблемы с решением такой конечной игры, как шахматы. Я бы сказал, что шахматы немного сложнее, чем шашки в том смысле, что победа не обязательно заключается в численном истощении фигур, но в мате. Мое первоначальное утверждение, вероятно, неверно, но, опять же, я думаю, что я указал на то, что еще не было удовлетворительно доказано (формально).

Я думаю, что мой мысленный эксперимент состоял в том, что всякий раз, когда берется ветвь в дереве, алгоритм (или запоминаемые пути) должен находить путь к мату (без соединения) для любой возможной ветви на ходах противника. После обсуждения я куплю, что, учитывая больше памяти, чем мы можем мечтать, все эти пути могут быть найдены.

Answer 1

«Я утверждал, что не может быть детерминированной машины Тьюринга, которая всегда побеждала или зашла в тупик».

Ты не совсем прав. Там может быть такая машина. Проблема заключается в огромности государственного пространства, которое оно должно было бы искать. Это конечно, это просто ДЕЙСТВИТЕЛЬНО большой.

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

Сценарии дебютов позволяют вам перейти к середине игры, которая дает вам «сильную» позицию. Неизвестный результат. Даже финальные игры - когда их меньше - сложно перечислить, чтобы определить лучший следующий ход. Технически они конечны. Но количество альтернатив огромно. Даже у 2 ладей + короля есть что-то вроде 22 возможных следующих ходов. И если для спаривания требуется 6 ходов, вы смотрите на 12 855 002 631 049 216 ходов.

Делать математику на начальных ходах. В то время как есть только около 20 начальных ходов, есть что-то около 30 или около того вторых ходов, поэтому к третьему ходу мы смотрим на 360 000 альтернативных состояний игры.

Но шахматные партии (технически) конечны. Огромный, но конечный. Там отличная информация. Есть определенные начальное и конечное состояния, нет бросков монет и бросков кубиков.

Answer 2

Я почти ничего не знаю о том, что на самом деле было обнаружено в шахматах. Но, как математик, вот мои рассуждения:

Сначала мы должны помнить, что белые должны идти первыми, и, возможно, это дает им преимущество; возможно, это дает черным преимущество.

Теперь предположим, что нет идеальной стратегии для черных, которая позволяет ему всегда побеждать / тупить. Это означает, что независимо от того, что делают черные, существует стратегия, которой белые могут следовать, чтобы выиграть. Подождите минуту - это значит, что - это идеальная стратегия для белых!

Это говорит о том, что по крайней мере один из двух игроков имеет отличную стратегию, которая позволяет этому игроку всегда выигрывать или ничьей.

Тогда есть только три возможности:

• Белые всегда могут выиграть, если играют идеально
• Черные всегда могут выиграть, если они прекрасно играют
• Один игрок может выиграть или сыграть вничью, если он играет идеально (а если оба игрока играют отлично, то они всегда зашли в тупик)

Но что из этого действительно правильно, мы можем никогда не узнать.

Ответ на вопрос да : для шахмат должен быть идеальный алгоритм, по крайней мере для одного из двух игроков.

Answer 3

Для игры в шашки было доказано, что программа всегда может выиграть или завязать игру. То есть не существует выбора ходов, которые может сделать один игрок, что заставит другого игрока проиграть.

Исследователи потратили почти два десятилетия , просматривая 500 миллиардов миллиардов возможных позиций шашек, что, кстати, все еще составляет бесконечно малую долю от числа шахматных позиций. Усилия по проверке включали лучших игроков, которые помогли программе проверки правил исследовательской программы в программное обеспечение, которое классифицировало шаги как успешные или неудачные. Затем исследователи запускают программу в среднем на 50 компьютерах в день. Несколько дней программа работала на 200 машинах. Пока исследователи следили за прогрессом и соответствующим образом настраивали программу. Фактически, Chinook победил людей, чтобы выиграть чемпионат мира по шашкам еще в 1994 году.

Да, вы можете решать шахматы, нет, не скоро.

Answer 4

Речь идет не о компьютерах, а только об игре в шахматы.

Вопрос в том, существует ли безотказная стратегия, чтобы никогда не проигрывать игру? Если такая стратегия существует, то компьютер, который знает все, всегда может использовать ее, и она больше не является эвристической.

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

Таким образом, вам нужно будет доказать, что такая стратегия существует или не существует для шахмат. Это в основном то же самое, просто пространство возможных ходов значительно больше.

Answer 5

Я очень поздно захожу в эту ветку, и вы уже поняли некоторые проблемы. Но, как бывший мастер и бывший профессиональный шахматный программист, я подумал, что могу добавить несколько полезных фактов и цифр. Есть несколько способов измерения сложности шахмат :

• Общее количество шахматных партий составляет примерно 10 ^ (10 ^ 50). Это число невообразимо велико.
• Количество шахматных партий в 40 ходов или меньше составляет около 10 ^ 40. Это все еще невероятно большое число.
• Количество возможных шахматных позиций составляет около 10 ^ 46.
• Полное дерево поиска в шахматах (число Шеннона) составляет около 10 ^ 123, исходя из среднего коэффициента ветвления 35 и средней продолжительности игры 80.
• Для сравнения, число атомов в наблюдаемой вселенной обычно оценивается примерно в 10 ^ 80.
• Все эндшпили из 6 штук или меньше были сопоставлены и решены .

Мой вывод: хотя шахматы теоретически разрешимы, у нас никогда не будет денег, мотивации, вычислительной мощности или хранилища, чтобы когда-либо это делать.

Answer 6

Некоторые игры фактически были решены. Крестики-нолики - это очень простой способ создания ИИ, который всегда будет выигрывать или связывать. Недавно было решено и Connect 4 (и было показано, что это несправедливо по отношению ко второму игроку, поскольку из-за идеальной игры он проигрывает).

Шахматы, однако, не были решены, и я не думаю, что есть какие-либо доказательства того, что это честная игра (то есть, дает ли идеальная игра ничью). Говоря строго с теоретической точки зрения, шахматы имеют конечное число возможных конфигураций фигур. Следовательно, пространство поиска конечно (хотя и невероятно велико). Следовательно, существует детерминированная машина Тьюринга, которая могла бы отлично играть. Однако может ли кто-нибудь когда-либо быть построен, это другой вопрос.

Answer 7

К 2040 году рабочий стол в среднем за 1000 долларов сможет решить задачи проверки всего за 5 секунд (5x10 ^ 20 расчетов).

Даже на такой скорости 100 компьютеров потребуется примерно 6,34 x 10 ^ 19 лет для решения шахмат. Все еще не осуществимо. Даже близко.

Примерно в 2080 году наши средние рабочие столы будут иметь примерно 10 ^ 45 вычислений в секунду. Один компьютер будет иметь вычислительную мощность для решения шахмат примерно за 27,7 часа. Это, безусловно, будет сделано к 2080 году, если вычислительная мощность будет расти, как и последние 30 лет.

К 2090 году на настольном компьютере за 1000 долларов будет достаточно вычислительной мощности, чтобы решить шахматы примерно за 1 секунду ... так что к этой дате это будет совершенно тривиально.

Учитывая, что шашки были решены в 2007 году, и вычислительная мощность для их решения за 1 секунду будет отставать примерно на 33-35 лет, мы можем, вероятно, примерно оценить, что шахматы будут решены где-то между 2055-2057. Вероятно, раньше, так как когда появится больше вычислительных мощностей (что будет иметь место через 45 лет), больше проектов можно будет посвятить таким проектам. Однако я бы сказал, 2050 не раньше, а 2060 самое позднее.

В 2060 году для решения шахмат потребовалось бы 100 средних рабочих столов 3,17 х 10 ^ 10 лет. Поймите, что я использую компьютер за 1000 долларов в качестве эталона, тогда как более крупные системы и суперкомпьютеры, вероятно, будут доступны, так как их соотношение цена / производительность также улучшается. Кроме того, их порядок вычислительной мощности увеличивается в более быстром темпе. Предположим, суперкомпьютер теперь может выполнять 2,33 x 10 ^ 15 вычислений в секунду, а компьютер стоимостью 1000 долларов - около 2 x 10 ^ 9. Для сравнения: 10 лет назад разница составляла 10 ^ 5 вместо 10 ^ 6. К 2060 году разница в величине, вероятно, составит 10 ^ 12, и даже она может возрасти быстрее, чем предполагалось.

Многое из этого зависит от того, есть ли у нас, людей, стремление решать шахматы, но вычислительная мощь сделает это возможным примерно в это время (до тех пор, пока продолжается наш темп).

С другой стороны, игра Tic-Tac-Toe, которая намного, намного проще, имеет 2 653 002 возможных вычислений (с открытой доской). Вычислительная мощность для решения Tic-Tac-Toe примерно за 2,5 (1 миллион вычислений в секунду) секунд была достигнута в 1990 году.

Возвращаясь назад, в 1955 году компьютер мог решать крестики-нолики примерно за 1 месяц (1 расчет в секунду). Опять же, это основано на том, что вы получите за 1000 долларов, если бы вы могли упаковать его в компьютер (настольный компьютер за 1000 долларов, очевидно, не существовал в 1955 году), и , этот компьютер был бы предназначен для решения Tic-Tac- То ... что было не так в 1955 году. Вычисления были дорогостоящими и не использовались бы для этой цели, хотя я не верю, что есть какая-то дата, когда крестики-нолики считались "решенными" компьютер, но я уверен, что он отстает от фактической вычислительной мощности.

Кроме того, учтите, что 1000 долларов за 45 лет будут стоить примерно в 4 раза меньше, чем сейчас, так что гораздо больше денег может пойти на такие проекты, в то время как вычислительные мощности будут продолжать дешеветь.

Answer 8

На самом деле возможно для обоих игроков иметь выигрышные стратегии в бесконечных играх без упорядочивания; Тем не менее, шахматы хорошо упорядочены. Фактически, из-за правила 50 ходов существует верхний предел количества ходов, которые может иметь игра, и, таким образом, существует только конечное число возможных игр в шахматы (которые могут быть перечисленным, чтобы решить точно .. теоретически, по крайней мере:)

Answer 9

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

Answer 10

Я думаю, что ты мертв. Такие машины, как Deep Blue и Deep Thought, запрограммированы с помощью ряда предопределенных игр и хитроумных алгоритмов для разбора деревьев на концах этих игр. Это, конечно, драматическое упрощение. Всегда есть шанс «обыграть» компьютер по ходу игры. Под этим я подразумеваю движение, которое заставляет компьютер делать движение, которое не является оптимальным (что бы это ни было). Если компьютер не может найти лучший путь до истечения времени, необходимого для перемещения, он вполне может ошибиться, выбрав один из менее желательных путей.

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

Существует увлекательная книга по этому типу GP, которая называется Blondie24 , которую вы можете прочитать. Речь идет о шашках, но это может относиться к шахматам.