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

Question

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

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

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

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

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

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

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

Answer 1

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

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

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

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

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

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

Answer 2

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

Answer 3

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

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

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

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

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

Answer 4

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

Answer 5

Множество ответов здесь приводят важные теоретические моменты игры:

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

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

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

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

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

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

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

Дополнительные примечания относительно "совершенства":

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

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

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

Answer 6

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

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

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

Answer 7

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

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

Смотри также

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

Answer 8

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

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

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

Answer 9

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

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

Answer 10

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

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

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

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

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