How hard is it to implement a chess engine? [closed]

I'm wondering how hard it would be to implement a chess engine. Are there already open-source implementations?

It seems that you'd need a scoring function for a given board constellation, and a very fast way of exploring several likely future board constellations. Exploring all possible future moves is of course impossible, so one could greedily follow the most promising moves, or use approximate techniques like simulated annealing to follow likely moves probabilistically.

Do you think that is within the scope of a machine learning graduate student project -- assuming there was an open-source implementation that the students could use, that does the basic things like returning the next possible moves for a given figure? Probably too hard?

It would be a fun project to have different teams work on chess engines and then let them play against each other ...

I have spent the last year building my own chess engine in C#. It was not all that difficult. During my work I have made mistakes, I have found that information on the internet was just not presented clearly, and much of it was simply copied from other sites.

In order to make life easier for someone else going through this process, I have been documenting the development of my chess engine and posted much of the source code on my blog:

http://www.chessbin.com

I have even created a Chess Game Development Kit that will get you started in developing your own chess engine, which contains:

1. All the code necessary to represent a chess board and chess pieces
2. Code related to validating chess piece movement
3. Graphical User Interface that displays the chess position and allows you to move pieces around the board

My site is basically dedicated for people just like you; people that want to get started on building their own chess engine.

Yes, this is definitely within the scope of a student project. Here are some links from my archive to get you started:

• This is a useful chess programming wiki.
• This is a simple introduction to chess programming.
• This is a more advanced introduction.
• 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.
• Here is an old report from 2 students who wrote a chess program.
• Finally, here is Wikipedia's take on computer chess.

Crafty is one of the top chess engines and completely open source. However I would discourage you from using it for a student project it's written in C, very complex and very hard to understand because it is highly optimized.

For educational purposes I would recommend taking a look at Adam Berents site where he describes the process he went through when he implemented a chess engine in C#. The source code is available as well of course. It's an excellent point to start from, in my opinion.

I cannot answer on your question, but I can answer to your final comment

"It would be a fun project to have different teams work on chess engines and then let them play against each other ... "

This is already done on FICS chess server. I suggest you to login there (needs telnet) and check the documentation as well, you will probably be able to get in touch with people able to give you specific hints on their chessbots

A reasonable chess engine on modern PCs is certainly doable, especially if you're old enough to remember there were many Chess programs that used just a few K of memory on 1 and 2 MHz 8-bit machines that could play pretty well. You can whip out a chess engine in an interpreted language nowadays and beat the pants off a top 6502 or Z80 programmer coding his tightest fastest stuff.

I got to work with Dan Spracklen, who did the original Sargon in 1978 with his wife Kathleen. Kathleen's brother did the port to Apple II, and I worked with him and with his son. (At the time I worked with these guys, the chess-for-consumer-profit business was done. I remember one guy who brought out Atari ST and Amiga Chess games and there was really not much market for them by that time.)

"Computer Gamesmanship" is a terrific introduction to chess programming as hobbyists performed it in 1983. It's still a delight to read. Covers the good stuff: alpha-beta, minimax, etc.

It's a good enough book that you can start there and then learn about the advances made since.