Если бы у нас была бесконечная вычислительная мощность, есть ли алгоритм, который бы идеально играл в шахматы?

29

Существует ли такой алгоритм, при котором, если бы компьютер обладал бесконечной вычислительной мощностью, он мог идеально играть в шахматы, чтобы он никогда не проигрывал?

Если так, где я могу найти псевдокод для него?

Ион
источник
8
Что вы подразумеваете под идеальными шахматами?
Херб Вулф
5
@HerbWolfe Я предполагаю, что он имеет в виду, что он никогда не делает ход, который позволяет противнику заставить его проиграть, и уходит в отставку, если и только если каждое возможное движение позволяет противнику заставить его проиграть.
Дэвид Шварц
5
@DavidSchwartz - «идеальные шахматы», конечно, не поддаются определению. Также не может «бесконечная вычислительная мощность». Означает ли это «выполняет все последовательности команд за 0 раз»? «Имеется ли в наличии бесконечное количество процессоров»? FWIW - мое определение «идеальных шахмат» - «никогда не проигрывает».
Боб Джарвис - Восстановить Монику
24
Да, это называется грубой силой. С бесконечной вычислительной мощностью вам не нужно выполнять альфа-бета-отсечение, хотя вам также может понадобиться довольно большой объем памяти для хранения дерева поиска.
Майкл
4
Понятие «алгоритм» и понятие бесконечной вычислительной мощности на самом деле не смешиваются. Теория алгоритмов и вычислимости основана на предположении о достижении результата за конечное число шагов. Если вам разрешено бесконечное количество шагов, различие между тем, что вычислимо, а что нет, исчезает.
Майкл Кей

Ответы:

62

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

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

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

отметка
источник
13
@Wildcard Нет, он ничего не предполагает: он просто содержит все возможные легальные игры в шахматы и выберет все те, в которых игрок под рукой не проигрывает.
gented
11
@ gented, я имел в виду этап «отставки» алгоритма. Это не необходимый шаг вообще.
Wildcard
38
Правило трех повторений ограничивает пространство поиска, поэтому компьютер не обязательно должен быть бесконечно мощным, просто астрономически мощным.
Хоа Лонг Там
9
Для справки сравните нижнюю границу для числа возможных игр ( 10 ^ 120 ) с количеством атомов в наблюдаемой вселенной (порядка 10 ^ 80 ). Самый простой алгоритм должен найти все эти игры и сохранить их данные. Хранение одной игры на атом заняло бы в 10-40 раз больше атомов, чем мы оцениваем в наблюдаемой вселенной.
Инженер Тост
6
Этот ответ великолепен до самого конца, когда вы ссылаетесь на «бесконечно мощный компьютер». Это не то, что вы имеете в виду, и эта фраза не относится ни к вопросу, ни к обсуждению.
Дон Хэтч
25

Смотрите https://en.wikipedia.org/wiki/Endgame_tablebase .

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

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

itub
источник
9
В качестве дополнительного примечания: если бы вы на самом деле создали такую ​​таблицу, независимо от того, на чем вы хранили информацию, она бы весила примерно в 10 ^ 43 раз больше, чем наблюдаемая вселенная; учитывая, что в наблюдаемой вселенной существует ~ 10 ^ 123 возможных шахматных позиций и только ~ 10 ^ 80 барионов.
Shufflepants
6
@ Шафлпантс, кто сказал, что я храню его с помощью барионов?
Майкл
3
@Christoph И, предполагая сохранение информации, и предполагая, что у вас есть детектор и ваш суперкомпьютер с бесконечной вычислительной мощностью, вы могли бы медленно в течение чего-то вроде лет googolplex считывать настольную базу как излучение излучения.
Shufflepants
3
@Shufflepants Обратите внимание, что для реальной выигрышной стратегии может потребоваться гораздо меньше места, чем для полной таблицы. Например, у Нима есть выигрышная стратегия, которую легко описать, нет необходимости строить огромную таблицу всех возможных состояний.
Федерико Полони
1
Это решение, как указано, не является жизнеспособным. Масса такой таблицы образовала бы черную дыру, и было бы невозможно извлечь данные из нее.
Эмори
19

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

ВСЗ
источник
Это не правда. Он сказал, что вы обладаете бесконечной вычислительной мощностью, но не сказал ничего о бесконечном пространстве.
Убадуб
@ubadub: Нам не нужно бесконечное пространство. Продолжительность игры ограничена из-за правила 50 ходов, и можно составить правило для сортировки всех возможных ходов с позиции. Поскольку они могут быть отсортированы, они могут быть сохранены как целое число. Это вся память, необходимая для обхода всего дерева. И если у вас есть бесконечное время, вы можете ходить по дереву так часто, как вы хотите, так что вам не нужно хранить все возможные шахматы.
вс
Длина игры ограничена, но она чрезвычайно велика; как указывал кто-то другой, если вы создадите таблицу для хранения всех таких игр, «независимо от того, на чем вы храните информацию, она будет весить примерно в 10 ^ 43 раз больше, чем наблюдаемая вселенная; учитывая, что возможно ~ 10 ^ 123 шахматные позиции и всего ~ 10 ^ 80 барионов в наблюдаемой вселенной
убадуб
2
@ubadub: Это правда, но я не говорил о «столе для хранения всех таких игр». Существует много связанных с деревом алгоритмов, которым не нужно хранить все узлы всего дерева в памяти.
VSZ
@ vsz хорошая мысль
убадуб
13

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

https://en.wikipedia.org/wiki/Minimax

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

chessprogrammer
источник
4

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

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

С учетом этих функций простой рекурсивный алгоритм «решает» игру.

Этот факт упоминался в предыдущих ответах шахматным программистом (минимакс) и Acccumulation (который предоставляет версию программы на python).

Я написал такую ​​программу более 20 лет назад. Я проверил это, играя в крестики-нолики (крестики-нолики, если вы американец). Конечно же, он играл в идеальную игру.

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

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

Gareth
источник
Ваш алгоритм работает только для двух игроков с совершенными знаниями. Это упадет для игр со скрытой информацией, таких как Stratego , потому что любая реализация функции (a) нарушает правила игры. Он также не подходит для игр с потенциально бесконечной продолжительностью: например, исключить правило 50 ходов из шахмат, и он не может сказать, что два короля, преследующие друг друга по доске, не являются выигрышным состоянием. Все, что он может сказать, это то, что это не конечное состояние.
Марк
Действительные баллы. Я отредактирую свой ответ.
Gareth
3

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

Сначала несколько определений:

  1. Любой ход, который выигрывает игру для игрока, который делает этот ход, является выигрышным ходом.

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

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

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

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

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

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

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

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

  1. Каждый ход, который приводит к победе, является выигрышным ходом.
  2. Каждый ход, который приводит к потере, является проигрышным ходом.
  3. Каждый ход, в результате которого противник имеет только выигрышные или проигрышные ходы, является либо выигрышным, либо проигрышным.
  4. Назовите nколичество ходов в самой длинной шахматной игре. (На данный момент мы игнорируем неограниченные последовательности, хотя включить их нетрудно.)
  5. Мы не nдолжны рассматривать ходы с предыдущими ходами.
  6. Каждый ход с n-1предыдущими ходами является либо выигрышным, либо проигрышным, поскольку nходы заканчивают самую длинную игру.
  7. Таким образом, каждое движение на глубине n-2сопровождается только выигрышными или проигрышными ходами и, таким образом, само по себе является выигрышным или проигрышным ходом.
  8. И так до первого хода.
Дэвид Шварц
источник
1
Ваши определения выигрышных и проигрышных ходов недостаточно полны. Например, первый ход не выигрывает игру (# 1) и не оставляет противнику только проигрышные ходы (# 4), так что это не «выигрышный ход». Он также не проигрывает игру (# 2) и не оставляет противнику ни одного выигрышного хода (# 3), так что это не «проигрышный ход». Ваша стратегия требует, чтобы каждый ход был определен как «выигрышный ход» или «проигрышный ход», что просто не соответствует действительности, как вы его определили.
Ядерный Ван
2
@NuclearWang Он определяет каждый ход как выигрышный или проигрышный. Как вы думаете, третий вариант? Визуализируйте дерево всех возможных шахматных игр (и помните, мы пока исключаем связи или бесконечные последовательности). Каждая цепочка заканчивается либо победой, либо поражением. Это просачивается вверх по дереву, в конце концов идентифицируя каждое движение как выигрышное или проигрышное.
Дэвид Шварц
13
@NuclearWang: либо первый ход - выигрышный ход для одного игрока, либо шахматы - это (как крестики-нолики) ничья с идеальной игрой. Мы не знаем, что, потому что никто никогда не имел вычислительной мощности для выполнения этого алгоритма до конца, и никто не нашел более прямого доказательства.
Хоббс
8
В шахматах нет случайности и скрытой информации, что не оставляет места для «возможно». Каждая позиция выиграна, потеряна или вытянута (даже если нам не удалось идентифицировать их как таковые). И это объяснение опускает «нарисованный» вариант для простоты, но в основном это составляет 1) позиция рисуется, если она нарисована в соответствии с правилами, и 2) позиция рисуется, если у нее нет выигрышных ходов, но она имеет хотя бы один ход, который оставляет противника без выигрышных ходов.
Хоббс
2
@DavidSchwartz: Если кто-то не находится в проигрышной позиции, каждый не идеальный ход - это плохо. В проигрышной позиции, как правило, не было бы ни одного «идеального» хода (за исключением ситуации с принудительным ходом), поскольку любой законный ход мог иметь некоторую вероятность быть единственным выигрышным или ничьим ходом в некоторых мыслимых (возможно, очень надуманных) обстоятельствах. Уход в отставку, однако, показался бы однозначным худшим «ходом». Предположим, что игра доказана как победа белых с d4. Вы хотели бы играть шахматную программу , которая ответила на 1. d4с ...resigns?
суперкат
2

Предположим , у вас есть три функции: win_state, get_player, и next_states. Входные данные для win_stateсостояния игры, и выходные данные равны -1, если белые находятся в мате, 0, если это ничья, 1, если черные находятся в мате, и Noneиначе. Входные данные для get_playerсостояния игры, а выходные - -1, если ход черных, и 1, если ход черных. Вход для next_states- это список возможных следующих состояний игры, которые могут возникнуть в результате легального хода. Затем следующая функция, когда задано игровое состояние и игрок, должна сообщить вам, в какое игровое состояние нужно перейти, чтобы этот игрок выиграл.

def best_state(game_state,player)
  def best_result(game_state):
     if win_state(game_state):
        return(win_state)
     else:
         player = get_player(game_state)
         return max([best_result(move)*player for move in next_states(game_state)])*player
  cur_best_move = next_states(games_state)[0]
  cur_best_outcome = -1
  for state in next_states(game_state):
     if best_result(state)*player > cur_best_outcome:
           cur_best_outcome = best_result(state)*player
           cur_best_move = state
return(best_move)
Acccumulation
источник
0

Используйте справочную таблицу

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

def play-move(my-color, board-position):
    return table-of-best-moves[my-color, board-position]

Подвох

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

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

Бен Ковиц
источник