Actionscript, chess and the quest for performance

The reaction to flashCHESSIII has been overwhelmingly positive, especially on forums, even though the blog entry received just a reply.

Advanced chess players were expecting a tougher engine though (some players have estimated an Elo rating of of 1500-1800 for the engine).

The first time I compiled and run the engine, after weeks of just writing code, it could evaluate about 1000 moves per second. After heavy optimizations using the Flex Builder profiler, which helped me identifying the trouble areas, the speed increased gradually to 10,000 moves per second. A ten-fold increase may sound impressive, but lets put it in context.

The number of nodes (possible moves) evaluated per second results in how “deep” the search can go – how many plies the computer may think ahead. Consider the game opening. White has 20 possible moves; for each of there, black has another 20 possible moves. So, at depth (ply) 1 we have 20 moves; at depth 2 we have 400 (20*20) possible moves; and so on, depending on how many pieces we have on the board and how much they can move at a given moment. The number of moves increase exponentially. Even with alpha-beta pruning (eliminating searching of nodes that cannot be beneficial) at depth 4 we have around 10,000 nodes (moves), while at depth 5 we’d have 150,000 nodes, 500,000 nodes at depth 6 and so on.

So, my Actionscript 3 engine can do 10,000 nodes/second, evaluating 4 plies ahead (it could go to about depth 5-6 by setting the Script Limits to timeout after 60 seconds instead of 15, but who waits that long?). A similar engine in terms of features, but written in C can do around 300,000 nodes per second. A really powerful engine like Crafty can do over 1,200,000 nodes per second. Deep Blue could do 200,000,000 nodes per second, evaluating up to 40 plies ahead.

Why so slow? First and foremost, Actionscript 3, while quite fast, is still run in a virtual machine that runs in a browser… it’s no match an application written in C. From my tests I’ve found Actionscript by to be 5-10 times slower than Java and 100-500 times slower than C.

Also, with Actionscript you can’t do any fancy multithreading or take advantage of multiple cores a system may have or a 64bit architecture (using bitboards would speed up calculations tremendously, but they require 64bit integers, preferable with hardware support; the Number type in Flash is only 57 bits long).

Then we have the memory issues. Because chess evaluates so many moves and board combinations, sometimes the same board position may occur in different parts of the search tree. Chess engines store this kind of info in what’s called Transposition Tables – which is a fancy name for a cache. Strong PC-based chess games sometimes allocate more than 200 Mb of RAM for this cache. Obviously, for a flash application I can’t do this unless I want to hear a lot of complains, so I’m clearing the cache after each search. It’s still used, just not as effective.

Finally, it’s the evaluation function. After each move, the board needs to be evaluated, that is to see the effect of that move. At its core, it counts the value of the pieces for each player. Then you can reward certain positions (castlings, two rooks working together, etc) and much more. You can spend years just tweaking the parameters and scores.

Still, it’s great fun. I could never understand those who start creating chess engines until I did that on my own. It’s a great challenge to think of new ways to improve both speed and effectiveness.

I hope to release beta 2 tomorrow…