« A spam story | Main | Numbers... »

## December 31, 2004

### The Minimax Algorithm

A while ago, I built a home-made chess engine. It was not very strong, but was a “worthy” opponent. In a few posts, I will describe the basics of how its done (and more!). Chess is a “zero-sum” game meaning that a player can only gain at someone else’s expense. The core of the chess engine is the famous Minimax algorithm. In chess, there are two players - lets call them Sean and Vlad.

How does Sean evaluate a position? If he has mate, he evaluates the position
to positive infinity. If he is getting mated; however, he evaluates the position
to negative infinity. Sean wants to maximize this value - but Vlad also gets a
say in this. Vlad, clearly wants to minimize this value. Hence, Sean’s value is the minimum of
the values resulting from each of Vlad’s replies. Here, Sean is whats known to be
the *maximizing* player, and Vlad as the *minimizing* player.

However, Sean is unable to calculate all the possibilities till the end of the game,
so at one point he would have to “guess” the value of the position. At one point, he has to
intuitively look at a position and decide how good it is. He will examine factors such
as material, king safety and pawn structure and eventually decide: “Okay, I am
winning by +2.33 pawns”. This is known as a *heuristic evaluation*. Of course, this
is still guessing and Sean would have to *hope* that he’s guessing well.

In this case, Sean looks only so many moves ahead. This is called the *depth*. The
number of possibilities increases exponentially with each half-move or *ply*. The
rate of increase is called the *effective branching factor*. However, Minimax
all by itself is not very efficient. One could greatly increase depth by means
of a pruning algorithm. But more on that next time.

Posted by Oleg Ivrii at December 31, 2004 01:12 PM

## Comments

Did you prune, Oleg? I wrote a checker program using the same algorithm last year, it groaned for a minute on my PII when I asked it to look 4 moves ahead. I heard that there is a heuristic that can let the program look ahead 10 moves in about half a second (probably A* or IDS).

Posted by: Richard Peng at December 31, 2004 10:22 PM

Of course I pruned, but I cannot tell the story all in one post. Checkers requires much sharper heuristics - but has a much lower effective branching factor resulting in a much larger depth.

Posted by: Oleg Ivrii at December 31, 2004 11:11 PM