Home
Download
How Computers
play chess
How NagaSkaki
plays chess
Tips for writing a
chess program
|
Tips for writing a chess program
The first thing you have to know is that it's a huge undertaking
to write a chess program from scratch. You will not finish it in a few
weeks - it might (and usually will) take years before you can call it
a decent chess player. But in the end it's worth all that effort when
you see your creation crushing its first opponent!
It is also important to do some research before starting. Look at how
other people wrote their programs and try to use the good parts. Don't
feel bad if you don't understand what they were doing, but don't try
to copy that code because it will only give you headaches later. Rather
write less efficient code; but code that you understand and can fix.
I would suggest writing a chess program as follows:
-
First write a move generator. This generator should
generate all possible moves in any position. It doesn't have to check
if a move puts or leave you in check - we call this a pseudo-legal
move generator. It is also a good idea to see how fast you can generate
the moves.
-
Write a simple evaluation function (you only need
to look at material - give the king a very high score) Implement a
simple search function (minimax or alpha beta) and see how poor your
creation plays!
-
Now you can add some positional knowledge to your
evaluation function and immediately you will see an improvement in
game play.
-
Change the high score of the king to checkmate, thus
the program knows that it is all over when the king can be taken.
-
Improve your search function by adding quiescence
search and upgrade from minimax to alpha beta.
-
You will probably find that your program sometimes
gets stuck in a loop and make the same move over and over without
getting anywhere. To fix this, give the score of a position some relation
to the depth searched (the sooner you can do something, the better.)
You can also add detection of draws by repetition.
-
Add move ordering to your search - you'll be amazed
at how much this help to search deeper (of course not if you still
use minimax search.)
-
If your program is relatively bug-free at this stage,
you can start adding all kinds of enhancements like: Null move, History
heuristics, Killer moves, Hash tables etc.
Last tip: Don't take things too seriously - if you get tired, stop programming
until you're motivated again (even if it takes years!)
Last updated: 18 October 2002
|