Best approach for writing a chess engine?

Question

I'm a chess enthusiast and a programmer. I recently decided to start making a chess engine using my chess and programming knowledge. So here's my question:

What language (I'm familiar with Java, C++ and Python) and methodology should I adapt while writing a chess engine?

A little guidance would be much appreciated.

Edit:

So I decided to make it in JavaScript. I download this Chess UI from github and now I'm all set! My first step would be to write legal moves for it. So can anybody point me in the right direction? (I'm new to jQuery but have alot of programming experience).

P.S: I'm not trying to make a very efficient engine (I know its way too difficult), I just want to get familiar with the process and learn some new techniques along the way.

Answer 1

2072-rated chess player here. I made this website in pure JavaScript over a weekend. It's not a chess engine (I designed it to create entertaining opening positions as sort of a perverse Chess960 engine), but it's a starting point. The source code is here.

There are a lot of complications involved in making a functional board. These include:

• First, figuring out how to represent the basic legal moves. You have to kind of do math with the beginning and ending coordinates. For instance, with rook moves, one of the coordinates has to be the same before and after. With knight moves, the sum of the absolute value of the coordinate changes has to be 3, and both coordinates must change. With bishop moves, either the sum of the coordinates remains the same, or they both increase by the same amount. Pawns are trickiest because you not only have to figure out if they can move two squares or one (check the row and the color instead of storing how many moves they've made) but also have to deal with the whole capture-diagonally, move-forward thing.
• Capturing is a challenge because of pawns and check. You can't just say that if a piece moves to another piece's square, then it's a capture. After all, pawns can't move to another piece's square to capture - they have their own special way of capturing.
• You have to figure out an efficient way to see if enemy pieces are in the way of a piece's move in order to decide if it's legal or not.
• Check is challenging to deal with. After every move, you have to check all the squares that the enemy pieces can go to and see if one of them involves your king and, if so, it's an illegal move.
• Castling, en passant, promotion, stalemate, forced draws, repetition - none of these are trivial to handle given the scale of the problem.

All chess engines work by looking at all (possibly a heuristically determined subset) of the legal moves in a position and evaluating numbers to represent their relative values by making those moves and recursively doing the same thing for the resulting positions. Your twin problems here are

• How to store this data efficiently
• How to proceed with this recursive search - after all, you can't let it go on forever, so you have to put a limit and then figure out how to design your algorithm to do the most optimal and thorough search within that limit. For instance, you want to make sure that it at least comes up with some evaluation for each possible starting move, but you might also want it to spend more time evaluating more promising moves instead of giving an equal amount of time to every move.

This all on top of designing the algorithm in the first place, which there is plenty of information available on.

As for which language to go with (although I guess you already decided on JavaScript), I think it depends more on your goal than anything else. I wanted to make mine online (and get better at JavaScript), so JavaScript was my choice. Any object-oriented programming language will do though.

Once you get comfortable with what you're doing, the following resources will probably prove really helpful:

• Chess Programming Wiki
• Chess Programming Forum
• StockFish on Github

Good luck!

Answer 2

The problem with "chess program" as a concept is that there are many pieces which can absorb a lot of time, and not necessarily interest you at the moment. You can spend years just working on graphics, or an alpha-beta search, or a visualization to help develop for the search engine, or... well, there are lots of pieces.

I recommend finding an open source chess program (there must be many) and set about improving the parts of it that interest you the most. You may eventually replace the entire program, one function at a time, or you may learn enough and be motivated to throw it away and design your own program from scratch. In any case, the key is to start "light" and learn the ropes before trying to architect an entire program.

Answer 3

If you are familiar with the rules of chess, a good starting point about basic techniques is http://www.frayn.net/beowulf/theory.html An extensive collection of Materials and links you can find here: http://chessprogramming.wikispaces.com/ And third: Learn from others code. Have a look at the sources of Crafty. It's the leading open source engine. Very important wil be to think about Test cases, to see if you make improvements: Start for example with some easy simple end-game positions with 3 or 4 figures.

Answer 4

I assume you already know about the concept of Min-Max, trees and pruning, heuristic and other basics and what I write here are just some details that might have been underestimated.

I with company a friend wrote our own chess engine sometimes ago. I share some issues and ideas we had and I hope you find them useful.

Since we both were java programmers our language turned our to be java and we started with an object oriented approach. Pieces were objects, board was object, files and ranks (rows and columns in chess literature) were objects. And this was wrong. The overhead was massive and the program was struggling to go further than 2 moves (4 ply) in the search tree.

So with some search we ended up with a brilliant idea (not ours though!): Representing pieces and board as Long integers (64bit). This makes sense because a chess board have 64 squares. The rest was bit wise operations (running very near to cpu = extremely fast). For example, consider a binary 64 bit integer in which the ones are presenting the squares on the board that your piece can attack. Now if you execute a logical "AND" between two numbers like this, a non-zero result states that you have an square with attackers. There are several ways of doing presenting the chess board and pieces, So:

1 - Decide about your Board Presentation

Then you need and opening database. Chess opening is somehow solved ant it is highly recommended to have and opening book. In this case, you have lot's of extra time in blitz games.

2 - Find yourself an opening book.

We did these, but still we were far from being good:

3 - A good chess engine should be able to see 6 moves (12 ply) ahead.

So what we did then, was to use the dead time (if it's a human vs computer engine).

4 - Use the time when opponent is thinking to create some levels of your tree.

And still we were far far away from 12 plies. By more study, we discover some tricks! For example it was suggested to skip one ply of the tree and start from the next ply (like there is no opponent). The idea is that if a move is extremely idiotic, then why to waste the time and see what are the opponents responses to that move. However, one good engine should be able to distinguish between and idiotic move and genius queen sacrifice.

5 - Learn the programming tricks for this specific problem (chess).

Me and my friend, in this state, were still bad :/ What we could do -and we partially did- was to save the calculated positions. If you calculate a position, then save it for future! The same goes for loops in the search tree. The point was to save/retrieve the efficiently:

6 - Save the data you generate...Efficiently!

and finally:

7 - Code with maximum optimization.

This problem is extremely expensive both in CPU time and memory. It's very important to write your code very efficiently. Remember that we are talking about the branch factor of 35. This means a useless "if" somewhere in your heuristic, can be turn into 3.3792205e+18 useless "if"s somewhere deep in your search tree.

Chess programming is a very very interesting challenge and it's the time that you can put your programming capabilities into a serious test. There are few more points that I can suggest but I'm sure you will discover them by yourself. There many more points that I don't know but you can find them on internet!

Good luck and have fun!

p.s. I don't know javascript very well but something is telling me base on the difficulty of the problem, maybe, considering all that C++ can offer, it would be a better to drop javascript and do it in C++.

Answer 5

As mentioned, there is nothing terribly hard about build a chess engine. Perhaps, you should concentrate on how wish to use and (potentially) deploy this application as this will probably determine your choice of language.

If this is just a fun exercise, you may want to code it in Javascript and deploy it as a web page. If you never want to make it into a expert chess game, at least others will be able to play with it and its source code.

If you wish to learn a particular technology at the same time, say WPF, then this might be a good way to kill two birds with one stone. MVVM could be overkill for this app, but you'd learn it at least.

If you wish to target android devices, then Java would be a good choice. Similarly, Objective-C for iOS devices.

Long and short, choice of language does not exist in a vacuum.

Answer 6

As per your edit, you're up to the stage of defining 'legal' moves.

There are two ways of describing moves in chess. Descriptive notation and Algebraic notation. What you probably want is a function that takes the piece, starting position and ending position as parameters. eg. Knight from QN1 to QB2 is invalid, but Knight from QN1 to Q2 is valid. Thinking about it, Algebraic notation may be simpler due to the ability to easily calculate 'relative' positioning.

To ensure you're writing the minimum amount of code required, I'd start with writing tests for that function first. If you're using Algebraic notation, you probably don't need a test per piece/start/end. Get each test working, and refactor out duplication before moving on to the next 'move'. Your code will end up cleaner.

Once you've sufficiently covered the legal and illegal moves for each piece, I'd start adding in checks for other variables (such as moving a King into 'check' and 'mate' conditions).

I recommend qunit for unit tests and jasmine for behavioral tests in JavaScript.

Answer 7

I actually have written a chess engine. Prepare yourself for both a treat and a nightmare. When my friends and I did it, it was in a timed programming contest and the language we decided to go with was Java. I feel Java or C is your best choice, but I see that you've decided to go with Javascript. I can't really knock it cause I'm unfamiliar with it.

The main problem here will be that there are just so many move/win scenarios with every piece that you need to account for, so I would recommend that you write out all these possible situations for each piece before you actually begin coding. Just jumping in without planning will turn this fun project into a repetitive chore. But that's really the main thing. Just plan outside of code first and make sure you get every scenario for one piece at a time.

Good Luck

Answer 8

For the computer-player-making-decisions part of the game, I can't recommend enough the book "Artificial Intelligence: A Modern Approach" (book website http://aima.cs.berkeley.edu/). Depending on your background in mathematics (graph theory helps) it may be a little high level, but it is written as simply as this academic stuff can be and it contains a very up-to-date overview (and some depth) of techniques to make programs decide things.

It will point out things to you such as stating a goal (i.e. checkmate or a null), evaluating how close a particular state (board layout) is to that goal, how to generate the different possible following states starting from the current one, and how to traverse what is an immense problem space.

One thing that might help in designing an AI algorithm is to figure out how to decide which move to play next as if you had all the time in the world, starting from a situation very close to a won game. You optimize it so that it finds a solution in a reasonable amount of time (hours), then find ways to choose a winning path even though you haven't explored all the outcomes yet, so that you can actually interrupt the "thinking" to a turn's worth of time.

Only then would I look at optimizing the representation of to make the individual calculations faster, such as using long integers as was suggested. No matter how fast so you can make a single comparison, if the way you traverse the problem space does not have a good heuristic, it's going to take ages to do so.

Answer 9

You can go really any way you want, but these are my thoughts on the subject:

I'd use Java as that allows you to be very high-level, and have user interface libraries (AWT, Swing) at your direct disposal. You can use an object-oriented approach to modeling the chess board and pieces. Other objects could stand in for the move history and scoring. Even the players could be objects, and then you might in the future extend your Player class to provide an artificial intelligent computer player.

You might want to take a look at model-view-controller (MVC) as that is a very nice approach in this case to tie your model objects (domain model) to the user interface (view) and to allow the user to manipulate the model (through the controller).

You may also want to apply test-driven development, which not only ensures that all methods behave the way you expect, but also forces you to write testable, modular code.

Answer 10

The rules of chess itself are fairly simple. You just need to be able to create a matrix (2-dimensional array) for the board, and find a way to encode the concepts of the pieces, the movement rules for each piece, validation that a move is legal, and conditions that signal the end of the game. Nothing particularly hard about any of that. You ought to use whichever language you're most familiar with.

Now if you want to make a chess-playing AI that will take the role of one of the players, that's where things get tricky. But again, language choice isn't the biggest issue here; understanding the AI principles involved is. That will be a much more important factor.

(Having said that, this sort of decision-making can be extremely computationally intensive, and you'll probably want to use something that compiles to native code rather than a scripting language. And C++ is a very bad choice, not because it's not well-suited to this problem but simply because it's a very bad language in general, and trying to implement complex stuff in it is a good way to code up all sorts of headaches for yourself.)