|
|
Tips for writing a chess program
You might have wondered why it is possible to make a program that plays grandmaster chess, but not a program that can play poker at the highest level. The
answer is quite simple. In chess, all information is on the board and
there is often one superior move to make. Poker, on the other hand, is
a game of incomplete information, which makes it much harder to
analyze. It is however possible to create a blackjack
program that can win the casino by using so called "card counting" algorithms.
Although it's possible to write a really strong chess program from scratch, you must remember that it's a huge undertaking. 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!)
|