|Strategy Game Programming||Introduction|
These pages intend to give a comprehensive overview of the elements of a computer program which can play two-player strategy games like
tic-tac-toe, connect four, checkers and chess. I will always assume the players to be called 'white' and 'black', with 'white' being the
one to move first in the game. Evaluations will be given from white's point of view. Code fragments are written in C.
I have organized this tutorial in five parts:
Perhaps you wonder whether you should read this stuff. What does this guy know anyway? As an avid chess player, I wanted to write a chess program as soon as I got my first computer, an Atari ST back in 1987 or so. Knowing nothing of all the things I'm writing about now, I failed miserably. I went back to square one and started over with simpler things. I wrote a connect four program, and a program to solve the game of Solitaire for my grandmother, and that was about that for a long time. In 1996 I started a checkers program which today has become the de-facto standard for checkers, since it is - at the time of writing - by far the best free checkers program around. I generated the 8-piece endgame database for checkers, and also wrote an automated opening book generator for checkers. Finally, in the summer of 2002 I wrote a chess program. It's a decent amateur program, but nothing more. I never found the time to work on it seriously - I'm sure I could improve it, however I have no idea whether it would become a really good program.
Most computer programs nowadays use a brute-force approach to games - this is also called the Shannon-A strategy,
named after Claude Shannon, a computer science pioneer. He wrote the first computer chess program, at a time
when the word computer had a completely different meaning: a person who computed according to fixed rules. He even had
his program play a game of chess, that must have been a lot of work! At this time, Shannon guessed that there would
be a more promising approach to game-playing, a more human way: look at promising continuations instead of looking
at all possibilities. This is the so-called Shannon-B strategy, supposed to mimic humans. However, it seems
that with the incredible computing power of modern PC's the brute-force approach is better. Most computer programs
playing chess and similar games nowadays use the brute-force approach, where you basically look at all possibilities
for both sides up to a fixed depth. Most of these programs also use selective extensions, but this 'selective' search is far
away from what Shannon envisioned with his B-strategy - human-like look-ahead where only very few possibilities are considered.
Human chess masters might calculate about one or two positions per second, and can still compete with chess programs that
are calculating millions of positions per second. This gives you an idea of just how much more selective the search
of the human is!
Comments and questions are welcome!