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

109

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

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

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

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

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

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

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

Перелет
источник
1
+1: отличная тема. Однако я думаю, что это должно быть вики-фидом, о чем свидетельствует разнообразие и объем ответов.
IAbstract
1
«Думаете, я указал на то, что еще не доказано удовлетворительно»? На что вы указали, что формально не доказано?
S.Lott
2
да! как может быть 20 разных ответов на такой чёрно-белый вопрос! (каламбур не предназначен).
Peter Recore
5
Меня тоже удивляет количество людей, которые публикуют свои умозрительные ответы, не зная, что ответ на самом деле был определен математически - ответ в том смысле, что доказано, что у шахмат есть решение - просто непрактично вычислять его.
DJClayworth
3
Напоминает анекдот про компьютер Perfect Chess Playing. Играя белыми, он думает, думает, думает, а потом .... сдается!

Ответы:

104

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

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

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

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

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

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

С. Лотт
источник
22
Все эндшпили с 6 и менее фигурами были перечислены и решены. См. Tablebase и bitbase здесь: en.wikipedia.org/wiki/Tablebase . Например, есть эндшпиль KQNKRBN, где требуется 517 ходов, чтобы заставить мат! Но общее количество шахматных партий составляет около (10 ^ (10 ^ 50)).
HTTP 410,
2
Сценарий победы - это одно. Другое дело - исчерпывающе перечислить. В любом случае информация идеальна - все известно - игра детерминирована по определению.
S.Lott
11
@RoadWarrior: не согласен. Случайное относится к погоде. Бог кидает кости. Случайность не применима к шахматам - по определению. В шахматах есть полная информация. Погода имеет квантовые эффекты - она ​​не может быть полной.
S.Lott
3
Прогнозировать погоду сложно из-за хаотических нелинейных факторов, а не из-за каких-либо квантовых эффектов. При наличии достаточных вычислительных мощностей и знаний мы могли бы теоретически создать «правильный» прогноз погоды.
HTTP 410
3
@monojohnny: Правила запрещают повторение одной и той же позиции трижды. Шахматы просто конечны. Он большой, но конечный.
S.Lott
72

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

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

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

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

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

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

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

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

Artelius
источник
2
+1, это действительно отличный способ объяснить это. Не могу поверить, что никогда об этом не думал!
Zifre
2
Почему отсутствие идеальной стратегии у черных означает, что у белых действительно идеальная стратегия? А как насчет того, чтобы у обоих игроков не было идеальной стратегии? Если бы ваше предположение было правдой, разве это не было бы правдой для каждой игры для двоих, то есть в каждой игре есть идеальная стратегия?
Джон М. Наглик,
8
@john: Поскольку в шахматах есть точная информация и нет случайных элементов (в отличие от многих, многих других игр для двух игроков), единственный способ, чтобы не было идеальной стратегии для черных, - это если белые могут добиться победы, несмотря на любую попытку черный - другими словами, если есть идеальная стратегия для белых.
Дэйв Шерохман
2
На самом деле эта логика не всегда верна, но так ли это в данном случае?
BlueRaja - Дэнни Пфлугхёфт
4
@john "почему здесь так много дискуссий" - потому что некоторые люди не знают ответа, но все равно публикуют здесь.
DJClayworth
30

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

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

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

BCS
источник
6
«[Ты] ты никогда не скоро» - это немного мягко сказано. Помимо предела ожидаемой продолжительности Вселенной, у вас есть проблема с хранением - количество состояний в Chess намного превышает 500 миллиардов миллиардов шашек; фактически, это превышает количество частиц во Вселенной.
Майкл Дорфман,
30
«[...] на самом деле, это превышает количество частиц во Вселенной.». Пока оно не превышает количество состояний частиц во Вселенной, надежда еще есть ;-)
Карстен
1
что происходит, когда программа, которая всегда заставляет оппонента проигрывать, играет против него самого ????
Джон Деметриу
1
@BCS хм, а что, если есть прогноз, в котором, если я играю вторым игроком, а другой использует ту же эвристику, что и я, то действительно следуйте этой эвристике, чтобы выиграть, и если у первого игрока есть аналогичная эвристика ???? ?
Джон Деметриу
1
Я говорю, что если есть идеальный алгоритм и он есть у обоих игроков, будет неопределенное количество вероятностей, что алгоритм может изменить, чтобы он стал идеальным
Джон Деметриу
15

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

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

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

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

ypnos
источник
Итак, у кого было желание проголосовать против моего ответа? Что в этом плохого? Хотите быть впереди?
ypnos
@ypnos, я вообще не голосовал против вашего ответа. Я просто прокомментировал, чтобы не допустить, чтобы вас сбили случайные отрицательные голоса. Вы набрали 30 повторений и потеряли только 1. Кроме того, +1;)
mmcdole
1
Несколько причин против. 1) Известно, что существует алгоритм решения игры, просто алгоритм нецелесообразно рассчитывать по какой-либо мыслимой технологии. 2) Решение игры НЕ подразумевает наличие безотказной стратегии. Крестики-нолики решены, но для второго игрока нет стратегии, позволяющей избежать проигрыша.
DJClayworth
2
«Речь идет не о компьютерах, а только об игре в шахматы». Ну, компьютерная наука на самом деле не связана с компьютерами. Они всего лишь инструмент. Информатика работает без компьютеров.
Янус Троелсен
1
На самом деле это вопрос о компьютерах, поскольку вопрос в том, может ли существовать машина Тьюринга (= компьютер), которая решает шахматы.
SDwarfs 06
14

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

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

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

HTTP 410
источник
3
Да ладно. Вы должны по-другому взглянуть на проблему. Не думайте о количестве игр, потому что транспозиции, альфа-бета-алгоритмы и тому подобное значительно сокращают это количество. Подумайте о позициях на доске (10 ^ 60) или комбинациях шахматных фигур (100 миллионов). С квантовыми вычислениями это тривиально.
lkessler
2
Альфа-бета в этом контексте (решение шахмат) потребует совершенной функции оценки. То же самое и с позициями на доске и комбинациями фигур. У нас нет идеальной оценочной функции, поэтому квантовые вычисления нам не помогают.
HTTP 410,
1
Каждый раз, когда я думаю, что что-то «тривиально», и я уверен, что никто этого еще не сделал, я также уверен, что ошибался хотя бы раз.
Дин Дж,
2
@lkessler: Позиции в совете директоров не говорят всей истории. По крайней мере, некоторая история игры необходима для рокировки или взятия на проходе или ничьей из-за отсутствия взятия или хода пешки, и вся история для ничьей путем повторения. Более того, поскольку в последнее время в квантовом компьютере был получен заметный результат исследования по фактору 15, я бы сказал, что сейчас нет ничего тривиального в квантовых вычислениях.
Дэвид Торнли
2
Для сравнения: если вы можете сгенерировать все возможные шахматные позиции, вы можете тривиально перебрать любой шифр со 128-битным ключом, так как 10 ^ 46 примерно равно 2 ^ 152 или 2 ^ 153. Есть веские причины думать, что это невозможно до тепловой смерти Вселенной.
Дэвид Торнли
9

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

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

Cybis
источник
8

К 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 раза меньше, чем сейчас, поэтому гораздо больше денег может пойти на такие проекты, как этот, в то время как вычислительные мощности будут продолжать дешеветь.

Фрэнк
источник
9
«Знаете ли вы, что продажи диско-пластинок выросли на 400% за год, закончившийся в 1976 году? Если эти тенденции сохранятся… ААЙ!» - Disco Stu
Джереми Фриснер
2
Закон Мура - вычислительная мощность удваивается каждые 18 месяцев - скорее всего, потерпит неудачу примерно в 2015 году. В противном случае придется кардинально изменить дизайн процессора компьютера. Так что 2080 год - нереальная цель.
Филип Смит
3
@Philip: Тактовая частота процессоров настольных компьютеров с 2003 года увеличилась лишь незначительно, и с тех пор улучшения в основном касались увеличения кэш-памяти и нескольких ядер. Поскольку процессор с тактовой частотой 3 ГГц имеет один тактовый цикл за время, необходимое свету для перемещения на 4 дюйма / 10 см, нельзя ожидать, что тактовая частота будет увеличиваться бесконечно. Более того, параллелизм обычно труден. Прогнозирование экспоненциального роста в течение пятидесяти лет, когда оно начало ломаться семь лет назад, не кажется безопасной ставкой.
Дэвид Торнли
1
@ Дэвид - это все правда. Но упускает из виду главное. Если вы уменьшите вдвое размер компонентов на кристалле, электроны будут работать вдвое больше при той же тактовой частоте. Это то, что подпитывает закон Мура.
Филип Смит
3
@Philip: Разумеется, сокращение вдвое не может продолжаться вечно. Атом кремния составляет около четверти нанометра в поперечнике, а производство микросхем сокращается до десятков нанометров. Более того, на квантовых уровнях частицы подчиняются статистическим правилам, а не абсолютным правилам, поэтому необходимо перемещать достаточно электронов за один раз, чтобы вызвать закон больших чисел. До сих пор закон Мура был чем-то средним между законом и самоисполняющимся пророчеством, но когда-нибудь это закончится довольно скоро.
Дэвид Торнли,
7

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

BlueRaja - Дэнни Пфлугхофт
источник
4
Технически правило пятидесяти ходов, такое как повторение трех ходов (которое также ограничивает вещи - существует конечное количество возможных позиций, поэтому умножение этого числа на три дает нам верхний предел) не приводит к ничьей. Скорее, это дает любому игроку возможность потребовать ничью. Обычно это делает проигравший игрок, но это не обязательно. Таким образом, следующая игра является полностью законной: 1. Nc3 Nc6 2. Nb1 Nb8 3. Nc3 Nc6 4. Nb1 Nb8, повторяющееся до бесконечности. И если я не ошибаюсь, никто не опровергает, что это не результат двух идеальных алгоритмов, играющих белое и черное.
Lenoxus
6

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

Билл Ящерица
источник
5

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

Kibbee
источник
1
Это можно сделать, но можно ли это сделать на компьютере, который мы, вероятно, когда-нибудь увидим?
BCS
1
Наверное, не при нашей жизни. Все действительно интересные исследования в этой области проводятся в игре Go. :)
Bill the Lizard
IIRC большинству 6-летних может быть любой компьютер в Go.
BCS
2
@BCS: Больше нет. Лучшие программы го сейчас обгоняют игроков дан (профессионального) уровня.
Bill the Lizard
1
@BlueRaja: Это было в 2008 году. Я не знаю, каков текущий рекорд, но MoGo побила профи с 6 и 7 камнями на 19x19. ireport.cnn.com/docs/DOC-214010
Bill the Lizard
5

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

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

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

Джейсон Джексон
источник
Вот как вы обыграли современные компьютеры в шахматах. Завтра будет лучше. Тем не менее, я согласен с вами в том, что Blondie24 очарователен.
Bill the Lizard
Проголосовал снова. Этот пост не заслуживает отрицательной оценки.
Cybis
К сожалению, проблема шахматной игры слишком велика, чтобы машинное обучение работало. Они никогда не смогли бы заставить обучающуюся шахматную программу даже новичку играть без промахов. Эвристика лучше. Но Грубая сила была даже лучше. Машинное обучение извлекло уроки только из неудач с шахматами.
lkessler
Шахматные программы не допускают краткосрочных ошибок, а лучшие программы играют лучше, чем чемпионы мира. Я думаю, что последняя версия Rybka 64 bit имеет рейтинг 3200 ELO
Alex
5

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

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

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

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

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

Роберт Гулд
источник
Это не теория игр
BlueRaja - Дэнни Пфлугофт
4
Технически это комбинаторная теория игр.
Anaphory
5

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

Джон Смок
источник
5

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

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

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

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

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

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

lkessler
источник
3

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

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

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

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

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

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

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

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

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

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

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

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

mikera
источник
Наличие несовершенных противников - не настоящая проблема. Это просто позволяет идеальному игроку выигрывать / ничьей (каким бы ни был идеальный результат) за меньшее количество ходов. Оптимальный ход в каждой позиции всегда лучше или равен другим возможным ходам (по определению). Таким образом, неоптимальные ходы позволяют вашему оппоненту раньше достичь оптимального конечного состояния (победа / ничья) или даже позволяют добиться лучшего результата. Например, если черные всегда будут проигрывать, если белые будут играть идеально, возможно, что черные выиграют, если белые сделают только один неоптимальный ход. Но да, это должно немного усложнить анализ.
SDwarfs 06
@Stefan - несовершенные противники - огромная проблема, если вы заботитесь об оптимальной игре. В частности, вы можете представить себе ситуации, когда на самом деле предпочтительнее сыграть проигрышный ход (то есть ход, в котором идеальный противник определенно победит вас), если вы знаете, что вероятность того, что ваш оппонент совершит ошибку, достаточно высока.
mikera 06
Оптимальная игра, на мой взгляд, означает достижение наилучшего результата с нулевым риском. Ваш противник, вероятно, «слаб», но когда вы играете этот проигрышный ход, он, к сожалению, может случайно сделать хороший ход. Забота о неоптимальных оппонентах актуальна только в том случае, если есть выбор только между проигрышными ходами, когда один из них имеет более высокие шансы на ошибку со стороны (неоптимальной игры) оппонента, которая фактически приведет к ничьей или победе.
SDwarfs
1
Это не обычное определение оптимума в теории игр. Оптимальный обычно означает максимизацию ожидаемого результата. В этом случае оптимальный игрок пойдет на определенный риск, если в среднем получит лучший результат .
mikera 08
В таком случае вы совершенно правы!
SDwarfs 08
2

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

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

Джоэл Кохорн
источник
Собственно, цитата верна. Программы просматривают все возможные ходы для обеих сторон в текущей позиции и используют эвристику, чтобы найти хороший ход, чтобы вести игру в направлении, благоприятном для компьютера.
Bill the Lizard
1
Нет, они не рассматривают все возможные ходы. Они используют эвристику нулевого хода, чтобы обрезать дерево.
Alex
2

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

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

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

полигенные смазочные материалы
источник
1
Будучи довольно приличным шахматистом и много лет изучив проблему, я на 99,9% уверен, что стратегия префекта в шахматах для обоих игроков приводит к ничьей (как это было доказано с шашками). Также есть свидетельства того, что с увеличением силы игрока увеличивается и процент ничьих.
mikera
2

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

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

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

Бен Гартнер
источник
2

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

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

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

Соломон
источник
1

Меня только на 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), но вы можете выбрать большое целое число и запомнить, что многие конечные игры перечисляются в обратном порядке от каждого возможного (или даже не легко доказуемо невозможного, я полагаю) конечного состояния.

Дуг МакКлин
источник
1
Ваше m = 5898. Правила шахмат ФИДЕ определяют, что вы должны двигать пешку или брать фигуру (что-то, что необратимо меняет игру), по крайней мере, каждые 50 ходов (так называемое правило 50 ходов), или один из игроков может требовать ничью. Было подсчитано, что самая длинная возможная игра составляет 5898 ходов, если оба игрока будут сотрудничать и как можно скорее заявить о ничьей. Нет смысла продолжать игру, если оба игрока могут претендовать на ничью. Если игрок замечает, что проигрывает, он может потребовать ничью с тем же результатом. См: chess.com/blog/kurtgodden/the-longest-possible-chess-game
SDwarfs
1
Примечание: m = 5898 - количество «ходов». Максимальное количество полуходов (118-3) * 100 + 3 * 99 = 11797. Вы можете найти доказательство здесь (на немецком!): De.wikipedia.org/wiki/50-Z%C3%BCge-Regel# Schachmathematik
SDwarfs 06
1

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

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

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

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

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

MrDeeJayy
источник
1

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

  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 минут. Может быть, можно было бы даже оценить его как человека с ручкой и бумагой или даже мысленно, если бы потратил немного больше времени.

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

SDwarfs
источник
0

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

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

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

E Dominique
источник
5
Идеальный ход определяется стратегией «minmax»: это ход, который максимизирует ваш минимально возможный счет (с учетом всех возможных ходов, которые может сделать противник). Или, другими словами, предполагается, что противник также играет отлично.
Ник Джонсон,
Однако это интересный момент. Может ли возникнуть ситуация, когда ответ на лучший из возможных ходов поставит вас в невыгодное положение, если ваш противник не сделает лучший из возможных ходов? Какие последствия это имеет?
Нона Урбиз 01
Я не математик и не очень хороший шахматист; Я также предположил, что теоретически (если будет известно все дерево игры), что ответ на этот вопрос - «да». Однако теперь, когда вы упоминаете эту проблему [выбор другого игрока], означает ли это, что система потенциально непредсказуема? Есть ли в игре середина, когда другой игрок может поставить в невыгодное положение? Это немного похоже на то, что персептрон (нейронная сеть) может выучить «ИЛИ» и «И», но никогда не сможет уловить «XOR»? Шахматы - пример «хаотической» системы? FWIW, ИМХО, я думаю, что на данный момент ответ кажется «не знаю».
monojohnny
@Nona По определению, этот ход был бы лучшим ходом. Нет никаких предположений.
пикколбо
@piccolbo: Лучше - один из лучших ходов. В шахматах есть позиции, в которых несколько ходов приводят к одному и тому же результату (выигрыш, ничья или поражение за одинаковое количество ходов).
SDwarfs 06
0

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

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

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

Филипп Классен
источник
-1

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

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

Дия Хассен
источник
-2

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

Alex
источник
-3

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

AI-разработчик
источник