« 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 ![[TypeKey Profile Page]](http://oleg.moltenstudios.com/blog/nav-commenters.gif)
at December 31, 2004 11:11 PM