Motivated by a recentish chess-related question (http://www.allegro.cc/forums/thread/600698), I returned to chess programming. I found that it was probably better to rewrite almost the entire thing from scratch (move generator, search, evaluation) and after more than a month of tinkering with it, things seem to be coming along fairly well.

{"name":"599212","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/a\/8\/a8506c1a6d60f6dd39a8145e69853386.png","w":893,"h":665,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/a\/8\/a8506c1a6d60f6dd39a8145e69853386"}

All rules are implemented (obviously) although I disabled repetition checks and left out the 50-move rule (the first are actually important if for no other reason than to kick the program out of searching cycles) for the time being.
The program reaches a somewhat decent 7-8 ply search depth fairly easily, but the evaluation function mostly only looks at material, which is not really good enough. The program will also mess up its opening quite badly, but I haven't really invested any time into that department yet.
That said, if I give it a decent starting position I find that it can already give me a hard time, so I fully expect the program to be able to beat me consistently if I put some more effort into it.

The (Allegro 5 based) graphical interface is very elementary at the moment: you can make a move (not underpromotions though), tell the computer to play a move or load a position from disk. No time control, difficulty settings or other options. I'll be adding those eventually, and I'll make a text-based interface and a UCI/xboard interface (standard protocols for chess engines, so they can be used with other interfaces) too. Eventually.

If the Allegro interface is a bit more polished and the program doesn't make a complete mess of the opening anymore, I'll put it on the depot (along with some information on how the program works and what decisions I made in its design and why).

Oh, I do plan to give it enough rudimentary opening knowledge that it will at least be able to place its pieces half-way decently on its own before adding an opening book.
Right now (at 5s per move), it calculates the first position to 8 ply and plays 1. f2-f3... (however, previous preferred 1. e2-e4 or 1. d2-d4, so it should be able to do better with a little tweaking).

Hey, it has some merit: it attacks e4 and it moves your weakest pawn^[1] to a saver square!

No, seriously, it's pretty atrocious, for pretty much the reasons you mentioned.
It's said that letting a computer play an opening on its own (no opening book) is the ultimate proof that computers can't "really" play chess. They're unbeatable in tactical positions though.

It should either have a decent-ish evaluation for opening positions (centre control, develop pieces, castle king are all good), or it needs to draw moves from an opening book. Otherwise you end up with silly things like 1. Nh3 or 1. h4. Many moves are bad, although e4 d4 Nf3 Nc3 c4 f5 g3 h3 b3 b4 a3 are all playable, which is slightly more than half (a3 obviously isn't that great, but it's surprisingly enough not completely horrible either because a6 is a semi-useful move in many black defences, which means you get to play a black defence as white, so you have a tempo more).

I'll work on that in due course; I'm trying to get it to perform decently in test positions first. It needs a better mate determination; right now it will sometimes find a deep mate and discard it until it reaches a deeper overall search depth, at which point it sometimes no longer sees the mate because the line that lead to it has been overwritten in the transposition table, so it can't look as deep. I'll fix that, then improve the evaluation function so it is more aware of piece placement, mobility and (very important) king safety (that will also help detect mate threats). I'll probably have a look at the openings after that.

That said, I just fixed a stupid mistake in my search implementation (it was trying to give accurate scores to all moves, which is stupid: you only need an accurate score for the best move, for the others you only need to know that they're worse) and now the search is about three times faster. Yay!

Ok. That reminds me: at the moment it probably only compiles on OS X... although that shouldn't be hard to fix.

It's a fun project to undertake, but it's not an easy task. Bugs can be very subtle and hard to find, and it's not so easy to make the program fast (read: strong).

Of course. Though as I said, you cannot specify an under promotion at the moment (the program will play them, but if you play a promotion the move will be matched to a queen promotion). This is more of an interface limitation though, the engine will play them if applicable. I should really fix repetition detection though; the 50-move rule is less important.

Linux is probably easier for me to get to work than Windows.

I doubt it, to be honest... the size of the search tree is just too prohibitive.

Anyway, things are progressing nicely. I took a break from running it against test positions and played an actual game yesterday. I'm not entirely unhappy with how it played the game in the end, but there are quite a few oddities that need to be worked out (I was white):

This is still without an opening book of any kind, so it's quite interesting that the first 10 or so moves are quite decent (3. ... f5 is a bit odd though). 12. ... Kf8 is of course a horrible move, but it should be very obvious from how the game progressed that the program has no notion of "king safety" (and that it desperately needs such a concept). Personally (without analysing the game in detail) I thought black was slightly better until around move 20 or so, at which point the scales tipped. By the time I got to play 24. Rc8+ I felt fairly certain I would be able to win.

EDIT: fixed a few typos I made in transcribing the game above, attached PGN file of the game for easy viewing.

I wonder if you could program a pixel/vertex program to work as a move generator? Anyway, I really enjoy the subject of <game>-playing computer programs (I don't enjoy chess much though). I would love to try it out at some point (and I have a mac).

Ok, i looked at the game and the moves seem pretty decent, does your engine focus on mate and / or material at this point ?

Are you hardcoding decisions or you got a rules database? While you should not focus on the opening, maybe you should start after the opening movements (setup the initial board with a finished opening) and see how it goes.

Cool! What license are you releasing the code under?

I'm making a mechanical chess board that allows you to play people online. I'm looking into making chess-bots so that the online community can be started.

http://www.chessghost.com/sand/

Chess programming is really an interesting thing. I'll give it a go one day.

See the main variation printed at the bottom of the "Iterations" window.
After 1. ... Kxf7 2. Ne6 Black's queen has nowhere to go. The only alternative is 2. ... Kxe6, which leads to a forced mate after 3. Qd5+ Kf5 4. g4+ (which is why the program opts for 2. ... dxe6 3. Qxd8 instead).
Neither of the alternatives 1. ... Rxf7 and 1. ... Kh8 do anything to prevent 2. Ne6 either, of course.

Hmm... good point, I didn't realise I hadn't put those in! Easy to add though.

Amazing!
I was able to speed the program up by some 20-30% by just refactoring code in various parts of the move generator and board update code. Remember how barnches are expensive and chars are slower than ints? Well, they're faster than unconditionally calculating things you don't have to while relying on the compiler to pair instructions to eliminate any overhead (and we're not talking expensive calculations here, we're talking bitshifts and logical ors):

is a whopping 20% faster than

static inline uint8_t get_piece(const board_t *board, const int where)
{
   assert(where<=H8);
   assert(board);
   int n;
   int piece = 0;
   for (n=0; n<6; n++)
      piece |= ((board->bbp[n]>>where)&1)<<n;
   piece |= ((board->bbc[1]>>where)&1)<<7;

   return piece;
}

Maybe I shouldn't be surprised, but 20% is a lot more than I was expecting to get (yes, that piece of code gets run all the time).

Anyway, I'm happy. Test suite score has increased to 275/300.