How hard is it to implement a chess engine?

Question

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 ...

Answer 1

To make a good one is hard, but probably at about the right level for a graduate project (when I took my batchelor's in Computer Science, a friend of mine wrote a chess engine for his final year dissertation).

And yes there are Open Source ones, the leading contender being GNU Chess, which is very well respected.

Answer 2

All depend of the goal that you fix about the AI of the game ! if it's a 2 players game.. easy ! But the AI is quite hard ...Right, the well know open source is GNU Chess !

Some algorithms : http://www.vclcomponents.com/s/0__/source_code_genetic_algorithm_chess
Here is a chess programming wiki !

Answer 3

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

Answer 4

You need to generate all the vaild moves for the given state. Then for every possibility you should to check the opponents possible moves. If there is at least one of them which makes your position worse then you should not follow that branch. To do this you need some kind of scoring to determine how well you are doing. Chess already have some rules about which unit worth how much points. It is enough to look ahead only a few steps like this. Beating the program will still be challenging.

This is of course far from perfect: real players can sacrifice some units to achieve long term goals. This algorithm will not do that.

Answer 5

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.

Answer 6

We did a mancala AI followed by a chess AI in Algorithms and Data Structures (sophomore CS).

However, the professor provided big chunks of the chess engine, and we had to do things like improve the decision function, implement checkmate, and other things.

Answer 7

In my undergrad AI course we spent half a semester creating various chess engines and testing them out using XBoard or WinBoard. Then at the end of the semester we had a tournament where the student's chess engines competed with each other in XBoard. Overall it worked out pretty well.

Interfacing to XBoard is fairly easy if I recall correctly. Here are some links.

http://www.gnu.org/software/xboard/

interface for XBoard

http://www.tim-mann.org/xboard/engine-intf.html

I'm not sure if this gets you everything you want, I think our chess engines had to create their own board representations and come up with moves on their own, but at least it gets you a graphical board that knows the rules and has a GUI.

Answer 8

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 valid 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.

Answer 9

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.

Answer 10

Every year at my university, the Introduction to AI course (3rd year course) requires students to create a chess program from scratch along with a paper, and we covered a chapter about adversarial search in lecture so that students have enough knowledge to do it. For us, the project can be done either on our own or with another (obviously expecting a better program if done with a partner, such as deeper ply, etc.). Because the Computer Graphics course is also a 3rd year course, students are allowed to combine the final project of that with the final project of the AI course.

Since I happen to be in my 3rd year and am taking both courses (which have now ended with the first semester), I teamed up with a friend who's also in both courses and we've been working on the program since the end of our exams (which was around Dec. 21) and it's due on Jan. 11.

It's completely doable within a month (especially as a graduate project). We're making a 3d chess program thus it requires more work than just a chess engine of course. The hardest parts will be deciding on a board representation, implementing all the rules (en passant, castling, promotion, etc.), creating a heuristic function, and the game tree (which is usually done with alpha-beta pruning).

Here is the site which we're using to document progress, and later host the code and the paper once we're done (it's a bit empty right now). http://sites.google.com/site/chessatbrock/