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

Question

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

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

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

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

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

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

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

Answer 1

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

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

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

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

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

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

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

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

Answer 2

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

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

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

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

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

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

Answer 3

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

Подробнее об этом в этом видео: 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

Answer 4

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

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

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

Answer 5

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

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

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

Answer 6

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

Answer 7

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