The Big Fun World of Chess AI

No one factor contributed to the long development time of my mediocre chess engine than Chess Programming Wiki . The bare bones AI for chess is verrry simple. Assume I'll make my best move, and the opponent will make the move that is worst for me, and work up from a certain depth. At that depth you return a simple evaluation of the position on the board, such as who has what pieces and where.

Now, if you learn anything about chess programming you will quickly see that it can be heavily sped up if you ignore certain variations that cannot possibly change the final result. This is an innocent enough change to your algorithm.

But wait, all good chess engines need a transposition table of course! So I read up on efficient hash table programming, created zobrist keys that update with the position, and created a fast lookup that probably returns the right score (in the end the chance of it affecting the final score is very very low). However, there are unforeseen complications with the optimization we made above, as we need to remember if we evaluated this position exactly, or if it is a bound of the position (happens when the position is not evaluated fully due to the above optimization).

So we fix our transposition table, and call it a day. Of course right now you would realize something: your chess engine is playing horribly, and it is slower than professional engines by a good magnitude. So you scour the chess programming wiki for optimizations and tricks. And they come by the dozen. In the end my simple chess engine turned out to use a negascout algorithm, a bit-board representation of the board, incremental evaluation, incremental hashing, magic bitboards for slider move generation, advanced pin and check detection, a transposition table that holds the top 2 moves for use with move sorting, partial move sorting for better results first, lots of odd and end techniques, a more extensive evaluation function, and a lot of things that I don't even remember programming. And it still sucked.

(Granted, it is able to beat most amateur players, as well as the person who graded it. However a program that grabs free pieces could have done that. )


There's no moral to the story though, because I'm proud to have a 'sophisticated' chess engine. However if not for the existence of the chess programming wiki I would have been done much sooner. Also, as a side note, the code was painfully programmed in non-OOP java. Anyone who thinks good OOP principles apply to chess programming should be shot (I once saw someone discussing the idea of making every type of piece its own class. I shuddered).

Oh I just thought of a moral: Don't implement more features than you are prepared to debug. I'm pretty sure my combination of stuff had some funky consequences that I did not really care to debug by the time I was finished programming it all, because it worked and it worked decently and my instructor wouldn't really care beyond that.


EDIT: How fun, my blog was picked up by google as a spam blog. I find that a bit odd, wonder what set it off.
And now the spam warning is gone.

Hello

I decided that I think much too much about programming, and have enough such thoughts to fill a blog. I also decided that such things aren't particularly normal, so I have decided to keep the blog pretty much anonymous. I will be posting/ranting on topics related to programming language design, algorithms, efficiency, yada yada.