Minimax

Minimax is applicable to deterministic, two-player, turn-taking, perfect-information, zero-sum games. Common games meeting these criteria include Chess and Go, as well as computationally simpler games such as Othello. Perhaps the most important of these properties is the zero-sum requirement, which means that any action that is good for one player is equally as bad for the other.

This notion of zero-sum allows us to categorise the two players by their respective objective:

• The maximising player wishes to make moves to maximise the game’s ‘value’
• The minimising player wishes to make moves to minimise the game’s ‘value’

In order to achieve this, we must define a ‘value’ function which evaluates the balance of the game for a given state.

The minimax algorithm computes the best move for the given player to make in order to end up in the best possible position after $d$ turns, assuming that the opposing player makes the optimal decision at every point.

A simple implementation of minimax may look similar to:

def minimax(state, depth, maximising):
	if depth == 0:
		return evaluate(state)
	best_move = None
	best_value = 0
	for move in find_moves(state, maximising):
		new_state = make_move(state, move)
		value, _ = minimax(new_state, depth - 1, not maximising)
		if best_move is None or (value > best_value) == maximising:
			best_move = move
			best_value = value
	return best_value, best_move

Pruning §

Exploring the full tree up to a depth $d$ is expensive and often unnecessary, as sometimes it is known that a branch cannot lead to a value better than the current best. In this case, the branch should be pruned and not explored. A common method for doing this with minimax is called alpha-beta pruning.

In order to implement this, two new parameters are introduced:

def minimax(state, depth, maximising, alpha, beta):

These are passed to the recursive calls:

		value, _ = minimax(new_state, depth - 1, not maximising, alpha, beta)

One of these values is possibly updated depending on whether the current player is minimising or maximising:

		if maximising:
			alpha = max(alpha, best_value)
		else:
			beta = min(beta, best_value)

We can then prune according to these values:

		if beta <= value:
			break

Move ordering §

To increase the number of branches pruned (and therefore reduce running time), we can use a heuristic function to estimate which moves are likely to be the best, and explore these first. The more accurate this ordering, the greater the number of branches which can be pruned.