Up Next

Search Tree Introduction

In chess, both players know where the pieces are, they alternate moves, and they are free to make any legal move.  The object of the game is to checkmate the other player, to avoid being checkmated, or to achieve a draw if that's the best thing given the circumstances.

A chess program selects moves via use of a search function.  A search function is a function that is passed information about the game, and tries to find the best move for side that the program is playing.

There are lots of ways to write a search function, and I don't want to stifle creativity by only talking about one of them, but I want these pages to focus on practical methods.  I figure that people who don't have any interest in writing a chess program might want to understand how the good ones work, and those who are considering writing a chess program are probably interested in following in the footsteps of those who have written strong programs.

It is possible that everything I say is crap, and it's important to keep an open mind about this.  What I say here may not have anything to do with techniques that will produce the strongest program.  Keep this in mind, and if you can think of a better way to do it, go for it.

Modern chess programs view a game of chess as a tree.  You have the root position, which is the position on the board now.  From this position, the side to move can choose amongst some number of legal moves.  These legal moves result in successor positions, which are positions that the side to move essentially gets to pick from.  It's not the move that you are selecting, it's the position.

Each of these successor positions will result in a position that your opponent can consider to be the root position, and they will choose from amongst their successors.

What you end up with is something that looks like a family tree.  You have the ancestors at the top, then you have their children, and then you have their children's children, and so on.  The tree is very, very bushy, since each position tends to have about 35 successors in chess.

Ideally, you would like to write a program that can work its way through all of the generations, until it finds a checkmates or draws, then choose the path that will get it to the best possible outcome.  It is theoretically possible to do this, but in practicality, it is impossible to search most positions this deeply.

So what is done instead is that the tree is searched as deeply as possible within a given time frame, and in those positions where you don't know how the game will end, you look at the position, take a guess, and assign a value to this position based upon the guess.

So now you have this giant family-tree structure, with all of the possible outcomes labeled according to their real or guessed value, and you want to make sense out of it, and pick the move now that will allow you to reach the position that seems to be the best.

You do this by using a tree search algorithm.  The most obvious one is min-max.

 
Send mail to brucemo@seanet.com with questions or comments about this web site.
Copyright © 2001 Bruce Moreland
Last modified: 01/24/03