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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Каждый ход, который приводит к победе, является выигрышным ходом.
2. Каждый ход, который приводит к потере, является проигрышным ходом.
3. Каждый ход, в результате которого противник имеет только выигрышные или проигрышные ходы, является либо выигрышным, либо проигрышным.
4. Назовите nколичество ходов в самой длинной шахматной игре. (На данный момент мы игнорируем неограниченные последовательности, хотя включить их нетрудно.)
5. Мы не nдолжны рассматривать ходы с предыдущими ходами.
6. Каждый ход с n-1предыдущими ходами является либо выигрышным, либо проигрышным, поскольку nходы заканчивают самую длинную игру.
7. Таким образом, каждое движение на глубине n-2сопровождается только выигрышными или проигрышными ходами и, таким образом, само по себе является выигрышным или проигрышным ходом.
8. И так до первого хода.

Предположим , у вас есть три функции: 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)

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

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

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

Подвох

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

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