How Computer Chess Engine's Think ( Minimax Tree )

minimax tree

Ever wonder how computer chess engines make decisions and are as competitive as humans? Most of these chess programs were partly designed by titled grandmaster or international masters. They use an algorithm very similar to a Minimax Tree. A minimax tree is simply a tree sorting algorithm that maximizes its own moves and assumes that its opponent will minimize his own score. In other words, computer chess players assume you will make the best move you can possibly make.

For gaming, whether its checkers, chess, or a video game, the minimax tree is quite useful to learn and implement in your AI code.

The minimax tree, is simply a pathway, to make the best decision after looking at all the pathways up to a certain depth, called "ply". So a 3-ply minimax tree might be looking 3 moves ahead (in chess, if computer is white, one move for black and two moves for white). Most chess engines now look more than 18 moves.

When you look at a certain minimax tree, like below, the first triangle represents the computer player, and the decision the computer player makes determines the next score. Usually in minimax algorithms, the computer player looks at a certain depth, selects the most minimum scores in each grouping at the bottom, and then works backwards minimizing and then maximizing the score to select the pathway that will lead to the best possible position even if the opponent player plays his best possible game.

minimax tree chess

Since chess engines are not perfect, some grandmasters can beat some of the best chess engines out there. Although Kasparov lost a game to IBM's Deep Blue II, there were very few games played, and so we cannot say for sure Deep Blue II didn't simply use the advantage of being able to see many of Kasparov's older games and thus heuristically find Kasparov's weakness, or if it is actually a stronger algorithm than Kasparov's own algorithm.

There are many other factors to a chess engine, not just the minimax tree. Databases are used for openings, certain continuations, and endgames--giving the engine a huge advantage because it can instantly recall important solutions to specific chess problems.

Anonymous's picture

Awesome :) How did you

Awesome :) How did you find/work that out?

Post new comment

The content of this field is kept private and will not be shown publicly. If you have a Gravatar account associated with the e-mail address you provide, it will be used to display your avatar.