C

It's been another long hiatus since the last release of my Morabaraba program, but at last there's a new version in the pipeline.

With the 0.6 release out the door, AHEM is now a very capable Morabaraba engine, and is also reasonably usable. I now need to consider what to do next. There are three categories of endeavour:

Engine Enhancements

Improve the playing strength - there are still lots of possibilities to consider:

• Fine-tune evaluation weightings (which are a bit arbitrary at the moment) - would require some kind of automatic playoff tool to verify improvements
• Build an opening book using drop-out expansion - I think this would probably improve the quality of the first few moves significantly, given a few months' calculation
• Enhance the search using something like PVS
• Knowledge improvements would probably help significantly, but I really need some input from expert players

GUI Enhancements

Over the Easter weekend, I've had some more time to put into AHEM (Adam's Happy Electronic Morabaraba), and it's shaping up nicely. I've made some serious improvements to the engine, including:

• improved quiescence
• transposition tables
• killer heuristic
• null-move proving
• knowledge enhancements
• Used the Intel C Compiler to build the DLL which ships with the GUI - this on its own brings a significant speed boost

Also a key bugfix which was impairing the search in key positions. All in all, the current unreleased code makes AHEM 0.5 look like a beginner, performing deeper, faster and smarter searches. I was planning on adding a bunch of UI features for release 0.6 but I'm tempted to just bundle up these engine enhancements and ship it - the engine is really beginning to look strong, like something that might actually not be embarrassed by competition!

Well, I beefed up the eval (including what I think are reasonable notions about space and mobility) and made some search algorithm improvements (recapture extensions and move ordering), with the result that the soon-to-be-released AHEM v0.3 is now much stronger than anything that has gone before - so much so that a 3-ply search from v0.3 easily crushes a 5-ply search from v0.1. The most irritating behaviour now is that when the search engine sees multiple wins, it comes to the conclusion that any move is winning, and basically starts moving randomly. Sigh. I need to add a bit of code to encourage it to prefer the shortest win.

In spite of labouring under the disadvantage of a greatly inferior evaluation and search algorithm (including no attempt at move ordering), the new version 0.2 engine for AHEM (Adam's Happy Electronic Morabaraba) is now scoring victories against the old engine. This is attributable purely to gaining extra search depth from raw speed. As the search algorithm and eval are upgraded to the level of the v0.1 version, additional search depth gains should result. This is a tremendous vindication of the decision to go ahead and build the new move generation strategy using C. Although I was going to make further improvements to the eval and the search engine, this result fulfils my 0.2 release criterion ("better than 0.1"!). Accordingly, I'm going to take a bit of time off from engine development to package and publish the release. This means that the new movegen is complete, but the release will still have extremely naive eval (basically just material) and search (alphabeta with no effort at move ordering).

You should know that I'm probably going to bore you with Morabaraba-related blog entries for a little while, but the process will culminate in a really decent free Morabaraba engine. Today I have finished the new move generator. Although it's only had som limited ad-hoc testing, it understands all three phases of the game, and it fully-understands captures (including not shooting cows in mills). It also (here's where I get a bit smug) is pumping out a little over 10 million positions per second on my laptop (with CPU throttled as I'm on batteries). That's fast; roughly 6x the speed of AHEM v1. What is more, the way the new move generator works, making and unmaking moves is almost free, which will increase the speed advantage even more. Also, looking for interesting patterns in the eval is much easier with bitboards, so that will give another noticeable speed boost. I should also mention that I've been testing with GCC 3.4.4 on Cygwin with NO OPTIMISATION FLAGS whatsoever; I also plan to use a range of compilers and settings to find the ultimate optimisation; I have a feeling that this will scream on a 64 bit processor compiled by the Intel compiler with the EM64T optimisations. All told, I plan to be looking at something like 10x-20x as many nodes as AHEM v1 in the same period of time, in spite of having a smarter eval. That's got to be worth a ply or two in any position.

As some of you may now, I've had an interest in computer Morabaraba for a few years now. I've often claimed that AHEM (Adam's Happy Electronic Morabaraba) is the "world's strongest Morabaraba engine", because to all intents and purposes, it was the world's only Morabaraba engine.

Well, all that is about to change. Over the last little while, I've been trading emails with Jurie Oberholzer, an honours student at the University of Witwatersrand. As part of Jurie's research project, he is focussing on creating a strong evaluation function for Morabaraba - and therefore a stronger player. Jurie is working in Java, and is getting close to finalising his project (about a month left, I think). His questions and ideas lead me to suggest that Jurie is about to open up a can of whoop-ass all over AHEM. Those of you who know me will realise I have a competitive streak about a mile broad, and this is being prodded in the worst possible way.