More Morabaraba

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.

So, I'm going to do something about it. Jurie's approach is based on finesse. He has really done his homework well; he's consulted with some very strong Morabaraba players and worked out some clever evaluation metrics (AHEM's static eval is extremely simplistic), and is in the process of implementing a genetic algorithm to fine-tune the evaluation weightings (yikes). I have every confidence that Jurie's approach will steamroller the current AHEM implementation, which is extremely unsubtle - Jurie himself, with the assistance of his Morabaraba experts, is able to regularly defeat AHEM. The problem is, I can't respond with a similar level of finesse. Oh, sure, I have some obvious ideas on how to improve AHEM's evaluation, but nothing like the level of cunning which Jurie is working on. Fortunately, however, I aim to fight dirty. I reckon a ply or two of search depth is probably worth quite a lot of finesse, and so my plan is to seriously turn up the brute force put out by AHEM v2.

The current AHEM implementation was intended to provide a simple, comprehensible platform for further development; I think it's probably fair to say it's done that. The code is in C#, it's easy to read and uses "human-comprehensible" data structures. All of this means it's a bit tame in the brute force department. To take the fight back to Jurie, I've started a whole new version (yes, that's the THIRD time I've started a whole new version!) which is in nice, minimalist C. I've had what I think are some cunning ideas about bitboard-based representations for Morabaraba which mean that the new version should scream with pace; a level of brute-force performance that couldn't be approached by AHEM, and hopefully won't be approached by Jurie's Java implementation. At the same time, I'll make a few eval improvements, and should end up with something significantly stonger than AHEM v1 - and hopefully strong enough to hold it's own against the new challenger (and perhaps even strong enough not to be laughed at by Jurie's Morabaraba experts).

Of course, there are some issues with writing bitboard based AIs (I know, because Blikskottel, Deep Brew and my very first Morabaraba effort all used bitboards). They're tricky to write; the code can be incomprehensible, hard to maintain and hard to debug. In order to manage these issues, I'm working on some key tools: firstly, a GUI bitboard editor (set up a position and it will give you the bitboard in hex); secondly, a movegen test mechanism (basically a library of test positions and what legal moves should be generated in each one); and thirdly, a GUI to actually play against the thing (peering at ASCII renditions of Morabaraba boards is not much fun). I have this neat plan of reusing the GUI components which I wrote for AHEM v1, as they're fairly neatly encapsulated, and dropping in the v2 engine with some simple C# bindings. Hopefully this will mean that I have a pleasant dev/test framework, but without having to invest significant time in anything except the new engine. Of course, when finished, all of these tools will be release under the GPL, as is my custom.

If anyone else out there is interested in writing a computerised Morabaraba player (or indeed has written one!), it would be great if you could email me - I would love to set up some kind of computer Morabaraba forum where we can all discuss ideas, test programs against each other, devise standards etc.