I'm interested in writing a chess engine (mostly as a learning exercise) and would be interested in any resources that people know of that could be of interest or use, anything really: Papers, Books, Theory, Tutorials, anything that could be useful.
Overview of many algorithms useful in chess - http://www.frayn.net/beowulf/theory.html - should be a good starting point to understanding the measure of the problem, and several ways to simplify the computational work.
This is basically in the field of Artificial Intelligence (AI).
The most common way to make a computer "think" in chess game is using the mini-max method where computer "think" by analyzing the results from making different moves ahead of time from the current state.
The "goodness" of results from different moves can be determine from many criteria such as score, number of enemies left, winning state, for example. For instance, if you move the player to the right and you win the game, that's a very good state. But if you move it to the left you get nothing. It is reasonable to move to the right. This function that define "goodness" is usually called Heuristic Function.
This process is done recursively for many turns. The greater the number of turns, the more time you will need. And the greater the number of turns, the more intelligent your software is. Thinking ahead in only one turn may only result in greedy selection. Intelligent chess software has great heuristic function and think ahead in many turns.
ps. There are some details of mini-max algorithm I didn't explain here but this should cover the basic idea.
Claude Shannon's 1949 paper (warning: PDF) on the subject is a good starting place
From my archives:
- This is a useful chess programming wiki.
- This is a simple introduction to chess programming.
- This is a more advanced introduction.
- This is Adam Berent's interesting computer chess blog.
- This is a good analysis of MTD, a sophisticated search algorithm.
- This is a good guide to validation of move generation.
- This describes the basic architecture of a chess program.
- This is lots of good information on the Dark Thought chess program.
- These are more notes on chess programming.
- A reasonable introduction to rotated bitboards.
- A reasonable introduction to magic bitboards.
- A look at null-move pruning and verified null-move pruning.
- Here is an old report from 2 students who wrote a chess program.
- A bunch of miscellaneous chess programming links.
- Finally, here is Wikipedia's take on computer chess.
When creating my chess engine I spent months trying to collect good resources that describe some of the harder aspects of creating a chess game. Here is a list of the ones I found most useful:
Chess Programming by François Dominic Laramée
This is the article that got me into computer chess, It is a great overview of how computers play chess. It is extremely easy to read and it will introduce you to all the terms and keywords.
http://www.gamedev.net/reference/programming/features/chess1/
Computer chess wiki, this has really expanded over the last few months. It is an excellent resource for reference material.
http://chessprogramming.wikispaces.com/
Louis Kessler's Computer Chess Links
Once you go through the above resources the remainder can be found at the following links page.
http://www.lkessler.com/cclinks.shtml
Last but not least I write a Computer Chess Blog that takes you through all the steps of writing a chess engine in C# from scratch, it includes a computer chess links section and a chess game starter kit.
Adam Berent
Hi,
I have joined the same league of Paul Wicks(above), I too want to write a chess engine for my own learning sake's, only constraint is my day job(which is to work on boring web services and stuff..) but its worth the pain.
I decided to build it using layer-by-layer approach. I'm almost through with the multi-player part i.e. (HUMAN vs HUMAN).
Once I'm done with this, I would love to incorporate the AI layer to support (COMPUTER vs HUMAN) playing scheme.This is the part that I'm most worried about, I have found very nice help tips here in this thread, a big thanks to all of you.
Currently the language that I'm well versed with is Java, in case there's a performance hit then I might port it to C++.