If given infinite processing power, is there an algorithm that would play chess perfectly?

Question

Does there exist such an algorithm where, if given infinite processing power, a computer could play chess perfectly, i.e., it can generate perfect moves from any position?

If so, where can I find the pseudo-code for it?

Answer 1

Does an algorithm exist? Yes. According to Zermelo's Theorem, there are three possibilities for a finite deterministic perfect-information two-player game such as chess: either the first player has a winning strategy, or the second player has a winning strategy, or either player can force a draw. We don't (yet) know which it is for chess. (Checkers, on the other hand, has been solved: either player can force a draw.)

Conceptually, the algorithm is quite simple: construct a complete game tree, analyze the leaf nodes (the game-ending positions), and either make the winning initial move, resign (if the opponent has a forced win), or offer a draw (if the position is a draw).

The problem lies in the details: there are approximately 10⁴³ possible positions, and an even larger number of moves (most positions can be reached in more than one way). You really need your infinitely-powerful computer to take advantage of this, since a computer that can take advantage of this algorithm either can't fit in the known universe, or won't finish computation until sometime after the universe ends.

Answer 2

See https://en.wikipedia.org/wiki/Endgame_tablebase.

With infinite computer power, one could build such a table for the starting position and solve chess.

In practice, only positions with up to seven "men" (pawns and pieces, counting the kings) have been solved using current supercomputers, so we are very far from solving chess. The complexity of the problem increases exponentially with the increase in the number of pieces.

Answer 3

If you really had infinite processing power, such an algorithm would be actually trivial to write. As chess has a finite number of possible states, you could in theory just iterate through them all until you find a path of perfect play. It would be horribly inefficient, but if you have infinite processing power, it wouldn't matter.

Answer 4

To directly address the question: yes there is such an algorithm. It is called minimax. (The endgame tablebases are generated by using this algorithm (backwards!), but the plain old simple minimax algorithm is all you need). This algorithm can play any two player zero sum game perfectly. Find pseudocode here:

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

note that variants of this algorithm are used by modern computer chess programs.

This algorithm basically generates the move which will minimize the opponent's chances, i.e., it would choose a move for White that is +2 instead of +1. Then, it generates the opponent's move which will maximize his chances, i.e., it would choose a move for Black that is -2 instead of -1.

Answer 5

Not only is there an algorithm to play perfect chess, it is possible to write a short program that will (given infinite resources) play any deterministic perfect-knowledge finite-duration two-player game perfectly.

The game engine does not even need to know the rules of the game it is playing. All it needs is an opaque representation of a "game state" and functions that (a) given any game state, provide a list of legal next game states and (b) given a game state, decide if it is a win for player 1, a win for player 2, a draw, or it is not an end state.

Given those functions a simple recursive algorithm "solves" the game.

This fact has been alluded to in previous answers by chessprogrammer (minimax) and by Acccumulation (who provides a version of the program in python).

I wrote such a program over 20 years ago. I tested it by playing noughts-and-crosses (tic-tac-toe if you are American). Sure enough it played a perfect game.

Of course this will fall over quickly on any imaginable computer for any serious game. Because it is recursive it is effectively building the entire game tree on the stack, so you will get a "stack overflow" (pun very much intended) before you get anywhere near analysing the 10^123 states of chess referred to in other answers. But it is fun to know that in principle this small program would do the job.

For me this also says something interesting about AI: however much "intelligence" you think is exhibited by Deep Blue, or Go Zero, or indeed by a human playing Chess or Go there is a sense in which these games have trivial, exactly computable optimal solutions. The challenge is how to get a good though not optimal solution in a reasonable time.

Answer 6

I will ignore the possibilities of draws or infinite sequences of moves for simplicity. Once the algorithm is understood, it is not particularly difficult to extend it to those cases.

First, some definitions:

1. Any move that wins the game for the player who makes that move is a winning move.

2. Any move that loses the game for the player who makes that move is a losing move.

3. Any move that leaves the other player with at least one winning move is also a losing move. (Since the opponent can take that move and force a loss.)

4. Any move that leaves the other player with only losing moves is also a winning move. (No matter what move your opponent makes, you will win.)

5. A perfect strategy means always making winning moves if any remain and resigning when one has only losing moves remaining.

Now, it's trivial to write a perfect strategy. Simply explode all possible move sequences and identify winning/losing moves. Ignoring stalemate, this will eventually identify every move as either a winning move or a losing move.

Now, the strategy is trivial. Look at all your possible moves. If any winning moves remain, take one and win. If only losing moves remain, resign, since your opponent can force you to lose.

It is not difficult to adjust the strategy to include the possibility of a stalemate.

Update: Just in case it's not clear how this identifies every move as a winning more or a losing move, consider:

1. Every move that results in a win is a winning move.
2. Every move that results in a loss is a losing move.
3. Every move that results in the opponent having only winning or losing moves is either a winning or a losing move.
4. Call n the number of moves in the longest possible chess game. (We are ignoring unbounded sequences for now, though including them is not difficult.)
5. There are no moves with n prior moves we need to consider.
6. Every move with n-1 prior moves is either a winning move or a losing move since n moves ends the longest game.
7. Thus every move at depth n-2 is followed by only winning moves or losing moves and thus is itself a winning move or losing move.
8. And so on back to the first move.

Answer 7

Suppose you have three functions: win_state , get_player, and next_states. The input for win_state is a game state, and the output is -1 if white is in checkmate, 0 if it’s a draw, 1 if black is in checkmate, and None otherwise. The input for get_player is a game state, and the output is -1 if it’s black’s turn and 1 if it’s white’s turn. The input for next_states is a list of possible next game states that can result from a legal move. Then the following function, when given a game state and a player, should tell you what game state to move to for that player to win.

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)

Answer 8

Use a look-up table

Yes. It's easy. You don't even need infinite processing power. All you need is a look-up table that contains, for each possible board position, the best move to play in that position. Here is the pseudo-code:

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

The catch

The only catch is that this look-up table would have to be very, very large—perhaps larger than the Milky Way galaxy—and it would take a long time to construct it—perhaps longer than the current age of the universe, unless there's some undiscovered regularity in chess that makes it much simpler than we can see right now. But if you had this look-up table, the subroutine to choose a perfect move every time could be implemented in as little as one CPU instruction.

Also, given our current knowledge of chess, there's no way to be sure that perfect play guarantees that you won't lose. For example, if perfect play guarantees a win for White, then Black would lose even if Black plays perfectly.