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: I will develop a C skeleton for strategy games to which only game-specific code will have to be added, but which takes care of the rest of the strategy game playing part.

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!
To sum up this in one sentence: Computers play strategy games by generating all possible continuations up to a (more or less) fixed depth and evaluating the resulting positions, which allows them to choose the best of these continuations.

Comments and questions are welcome!

[ Author homepage | Introduction | Part I | Part II | Part III | Part IV | Part V ]

This page was modified on 04.05.2005 using arachnoid