Exhaustive Search

In fact, most of deterministic games with two players (chess, checkers, go, etc...) can be solved by a well known algorithm called Minimax. Minimax requires a game to have an end and that the end has a numeric score. The players are called Min and Max. Min wants to get the lowest (minimum) score possible, Max wants to get the highest (maximum) score. At each turn both players make the best decision, this results in a minimum loss for each player: indeed Min gets the minimum of the maximum scores the game could face him.

A chess game finishes with a victory for a side or a draw. These ending can be related to a number: +1 white wins, -1 black wins, 0 otherwise. So Max is going to play with white and Min with black.

The easiest way to implements Minimax is using recursion. The function takes the game board as input and here is its flow:

1. If an ending condition matches, then returns the score.
2. Else for each available move call Minimax recursively to get its score
3. Returns the best score (the maximum if it's Max turn, the Min otherwise)

In Python:

def minmax(gameboard, side):
   ending = check_end(gameboard)
   if ending is not None:
       return (ending, [])

   results = []
   for move in generate_moves(gameboard):
       score, moves = bestmove(make_move(gameboard, move))
       results.append((score, [move] + moves))

   if side == 'max':
       return max(results)
   else:
       return min(results)

check_end checks for the ending condition and returns its score. If it doesn't match any game endings returns None.

minimax returns a pair (score, move_list). The second item of the tuple is useful to get the history of the game.

Not so easy

Easy, isn't it? So why did it take so long before we were able to build a good artificial chess player? The answer is quite fascinating: chess game has too many variants.

For each position we have to follow all the possible moves. In middle-game the average number of moves is over 20, this means that if it would be possible to find a forced victory for either player with just 30 turns, we would have to compute about 20^30 positions. Let's say our computer is good enough to elaborate 1 billion of billion positions in a millisecond, then it would take about 34 billion years for Minimax to finish.

That sounds crap. How can we deal with this problem?

Here come strategies developed during last century. These strategies help our chess engine reducing the number of positions to consider. Few of them are optimal, so they don't actually change the result of the Minimax algorithm, many others are heuristics and take the risk to do some mistakes in order to dramatically reduce the time required to choose the best move.