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

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

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

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

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

Изменить: Хмм ... похоже, я взъерошил здесь несколько перьев. Это хорошо.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Шахматы теоретически возможны, но практически невозможны (в 2008 году)

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

Шахматы - это пример матричной игры, которая по определению имеет оптимальный результат (подумайте о равновесии по Нэшу). Если каждый из игроков 1 и 2 делает оптимальные ходы, ВСЕГДА будет достигнут определенный результат (будет ли это выигрыш-ничья-поражение, пока неизвестно).

Как шахматный программист 1970-х годов у меня определенно есть мнение по этому поводу. То, что я написал около 10 лет назад, в основном верно и сегодня:

«Незавершенная работа и вызовы шахматным программистам»

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

Шашки были решены недавно (Ура, Университет Альберты, Канада !!!), но это было эффективно сделано грубой силой. Чтобы заниматься шахматами традиционно, нужно быть умнее.

Если, конечно, квантовые вычисления не станут реальностью. Если так, то шахматы решаются так же легко, как крестики-нолики.

В начале 1970-х годов в журнале «Scientific American» мое внимание привлекла короткая пародия. Это было объявление о том, что игру в шахматы решил русский шахматный компьютер. Он определил, что есть один идеальный ход для белых, который обеспечит победу при безупречной игре обеих сторон, и этот ход: 1. a4!

Многие ответы здесь указывают на важные теоретико-игровые моменты:

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

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

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

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

• Техники обрезки деревьев, такие как Alpha / Beta или MTD-f, уже значительно сокращают пространство поиска
• Доказуемая выигрышная позиция. Многие концовки попадают в эту категорию: вам не нужно искать, например, KR vs K, это доказанная победа. Немного поработав, можно доказать еще много гарантированных побед.
• Почти определенные победы - для "достаточно хорошей" игры без каких-либо глупых ошибок (скажем, об ELO 2200+?) Многие шахматные позиции являются почти верными победами, например, приличное материальное преимущество (например, лишний конь) без компенсирующего позиционного преимущества. Если ваша программа может форсировать такую ​​позицию и имеет достаточно хорошую эвристику для определения позиционного преимущества, она может с уверенностью предположить, что выиграет или, по крайней мере, сыграет вничью со 100% вероятностью.
• Эвристика поиска по дереву - при достаточно хорошем распознавании образов вы можете быстро сосредоточиться на соответствующем подмножестве «интересных» ходов. Так играют человеческие гроссмейстеры, так что это явно неплохая стратегия ... и наши алгоритмы распознавания образов постоянно улучшаются.
• Оценка риска - лучшее понимание «рискованности» позиции позволит гораздо эффективнее искать, сосредоточив вычислительные мощности на ситуациях, в которых результат более неопределенный (это естественное расширение поиска в состоянии покоя )

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

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

Дополнительное примечание относительно «совершенства»:

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

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

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

если вы просматриваете все пространство всех комбинаций ходов player1 / 2, единственный ход, который компьютер выбирает на каждом шаге, основан на эвристике.

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

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

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

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

• Алгоритм Бога

Я нашел эту статью Джона МакКуорри, которая ссылается на работу «отца теории игр» Эрнста Фридриха Фердинанда Цермело . Делается следующий вывод:

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

Логика мне кажется разумной.

Это прекрасно решаемо.

Всего 10 ^ 50 нечетных позиций. Для каждой позиции, по моим подсчетам, требуется как минимум 64 круглых байта для хранения (каждый квадрат имеет: 2 бита принадлежности, 3 бита). После того, как они сопоставлены, позиции, которые являются матами, могут быть идентифицированы, и позиции могут быть сравнены, чтобы сформировать взаимосвязь, показывающую, какие позиции ведут к другим позициям в большом дереве результатов.

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

Меня только на 99,9% убеждает утверждение о том, что размер пространства состояний не позволяет надеяться на решение.

Конечно, 10 ^ 50 - невероятно большое число. Назовем размер пространства состояний n.

Какое ограничение на количество ходов в самой продолжительной игре? Поскольку все игры заканчиваются конечным числом ходов, такая граница существует, назовем ее m.

Начиная с начального состояния, не можете ли вы перечислить все n ходов в пространстве O (m)? Конечно, это занимает O (n) времени, но аргументы размера вселенной напрямую не касаются этого. O (m) места может быть даже не очень много. Для пространства O (m) не могли бы вы также отслеживать во время этого обхода, ведет ли продолжение какого-либо состояния на пути, по которому вы проходите, к EitherMayWin, EitherMayForceDraw, WhiteMayWin, WhiteMayWinOrForceDraw, BlackMayWin или BlackMayWinOrForceDraw? (Есть решетка, в зависимости от того, чья она очередь, аннотируйте каждое состояние в истории вашего обхода с помощью решетки.)

Если я чего-то не упускаю, это алгоритм O (n) времени / O (m) пространства для определения, в какую из возможных категорий попадают шахматы. Википедия приводит оценку возраста Вселенной примерно в 10-60 планковских времен. Не вдаваясь в аргументы космологии, давайте предположим, что до жары / холода / какой-либо смерти Вселенной осталось примерно столько же времени. Это оставляет нам необходимость оценивать один ход каждые 10 ^ 10-го планковского времени или каждые 10 ^ -34 секунды. Это невероятно короткий срок (примерно на 16 порядков меньше, чем самый короткий период, который когда-либо наблюдался). Давайте с оптимизмом скажем, что с супер-пупер-хорошей реализацией, работающей на вершине линии технологии настоящего или будущего неквантового P-is-a-правильного-подмножества-NP, мы могли бы надеяться оценить (возьмите один шаг вперед, классифицируйте результирующее состояние как промежуточное состояние или одно из трех конечных состояний) состояния с частотой 100 МГц (один раз каждые 10 ^ -8 секунд). Поскольку этот алгоритм очень распараллеливается, нам понадобится 10 ^ 26-е таких компьютеров, или примерно по одному на каждый атом моего тела, а также возможность собирать их результаты.

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

Мы могли бы также надеяться несколько сократить определение шахмат и убедить всех, что это все еще морально та же игра. Неужели нам действительно нужно требовать повторения позиций 3 раза перед розыгрышем? Неужели нам действительно нужно заставить убегающую партию продемонстрировать способность убежать за 50 ходов? Кто-нибудь вообще понимает, что за фигня с правилом en passant ? ;) Если серьезно, действительно ли нам нужно заставлять игрока двигаться (в отличие от того, чтобы рисовать или проигрывать), когда его или ее единственный ход, чтобы избежать проверки, или пат - это взятие на проходе ? Можно ли ограничить выбор фигур, на которые может быть переведена пешка, если желаемое превращение без ферзя не приводит к немедленному шаху или мату?

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

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

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

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

Однако запомнить такие данные было бы невероятно, если вообще возможно. Чтобы компьютер распознал наиболее оптимальный ход из (максимум) 8 мгновенно возможных ходов, было бы возможно, но не правдоподобно ... поскольку этот компьютер должен был бы иметь возможность обрабатывать все ветви, прошедшие этот ход, На всем пути к заключению подсчитайте все выводы, которые приводят к выигрышу или патовой ситуации, затем действуйте в соответствии с этим количеством выигрышных заключений против проигрышных заключений, и для этого потребуется ОЗУ, способное обрабатывать данные в террабайтах, или больше! А с современными технологиями для такого компьютера потребовалось бы больше, чем банковский баланс 5 самых богатых мужчин и / или женщин в мире!

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

В вашем мысленном эксперименте есть две ошибки:

1. Если ваша машина Тьюринга не «ограничена» (по памяти, скорости и т. Д.), Вам не нужно использовать эвристику, но вы можете вычислить и оценить конечные состояния (выигрыш, проигрыш, ничья). Чтобы найти идеальную игру, вам просто нужно использовать алгоритм Minimax (см. Http://en.wikipedia.org/wiki/Minimax ) для вычисления оптимальных ходов для каждого игрока, что приведет к одной или нескольким оптимальным играм.

2. Также нет ограничений по сложности используемой эвристики. Если вы можете рассчитать идеальную игру, есть также способ вычислить на ее основе идеальную эвристику. Если нужно, это просто функция, которая отображает шахматные позиции следующим образом: «Если я нахожусь в этой ситуации S, мой лучший ход - M».

Как уже указывали другие, это закончится тремя возможными результатами: белые могут форсировать победу, черные могут форсировать победу, один из них может форсировать ничью.

Результат идеальной игры в шашки уже «вычислен». Если человечество не уничтожит себя раньше, когда-нибудь появятся и расчеты для шахмат, когда компьютеры достаточно развиты, чтобы иметь достаточно памяти и скорости. Или у нас есть какие-то квантовые компьютеры ... Или пока кто-нибудь (исследователь, шахматный эксперт, гений) не найдет алгоритмы, которые значительно уменьшают сложность игры. Приведем пример: какова сумма всех чисел от 1 до 1000? Вы можете вычислить 1 + 2 + 3 + 4 + 5 ... + 999 + 1000 или просто вычислить: N * (N + 1) / 2 с N = 1000; result = 500500. А теперь представьте, что вы не знаете об этой формуле, вы не знаете о математической индукции, вы даже не знаете, как умножать или складывать числа ... Итак, Возможно, существует неизвестный в настоящее время алгоритм, который в конечном итоге снижает сложность этой игры, и для расчета наилучшего хода на текущем компьютере потребуется всего 5 минут. Может быть, можно было бы даже оценить его как человека с ручкой и бумагой или даже мысленно, если бы потратил немного больше времени.

Итак, быстрый ответ: если человечество выживет достаточно долго, это всего лишь вопрос времени!

Это просто может быть решаемо, но что-то меня беспокоит: даже если все дерево может быть пройдено, все равно нет способа предсказать следующий ход противника. Мы всегда должны основывать свой следующий ход на состоянии оппонента и делать «лучший» доступный ход. Затем, исходя из следующего состояния, мы делаем это снова. Итак, наш оптимальный ход может быть оптимальным, если оппонент будет двигаться определенным образом. Для некоторых ходов оппонента наш последний ход мог быть неоптимальным.

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

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

Математически шахматы были решены с помощью алгоритма Minimax , который восходит к 1920-м годам (обнаружен Борелем или фон Нейманом). Таким образом, машина Тьюринга действительно может играть в идеальные шахматы.

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

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

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

Подробнее об этом в этом видео: https://www.youtube.com/watch?v=PN-I6u-AxMg.

Есть также квантовые шахматы, где нет математического доказательства того, что это определенная игра http://store.steampowered.com/app/453870/Quantum_Chess/

а вот подробное видео про квантовые шахматы https://chess24.com/en/read/news/quantum-chess

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

64-битная математика (= шахматная доска) и побитовые операторы (= следующие возможные ходы) - это все, что Вам нужно. Так просто. Грубая сила обычно найдет самый лучший способ. Конечно, универсального алгоритма для всех позиций не существует. В реальной жизни расчет тоже ограничен по времени, таймаут остановит его. Хорошая шахматная программа подразумевает тяжелый код (пасы, сдвоенные пешки и т. Д.). Небольшой код не может быть очень сильным. Базы данных открытия и финала просто экономят время обработки, это своего рода предварительно обработанные данные. Устройство, я имею в виду - ОС, возможности потоковой передачи, среда, оборудование определяют требования. Язык программирования важен. Во всяком случае, процесс разработки интересный.