Board Representation

Perhaps obviously enough, your Morabaraba program will need some way to represent the Morabaraba board in memory. You can probably think of a number of ways to do this off the top of your head, but it is a suprisingly important topic, and one which will repay careful thought and planning. The representation you choose should provide for the following features:

• It should provide complete, unambiguous representation of the position (in Morabaraba, this includes the number of cows yet to play, or the last capture (required for the machine gunning rule))
• It should be used consistently across the entire program - converting formats between the move generator and the static evaluator (for example) will slow your program down dramatically
• It should support high-speed implementations of the move generator and the static evaluator
• It should be very quick to make and unmake moves, as this is done very often during the move search

The two most commonly-used board representations are arrays and bitboards, although more exotic data structures (such as linked lists) have been tried with varying success.

Arrays

Arrays are perhaps the most natural representation; in Morabaraba, the most obvious takes on this would be a 24-element array or a two-dimensional (8x3) array, with each element corresponding to a position on the board. You might store 0 for an unoccupied position, -1 for a Black piece, or 1 for a White piece. Note that you will separately have to store the side-to-move, number of cows yet to play, and some method of recording which captures are illegal because of the machine-gunning rule.

This array-based approach has the golden advantage of being quite straightforward to implement and work with, and is the least likely to harbour inexplicable bugs. This is important, as you're probably going to be dealing with quite a bit of odd behaviour early on - keeping the basics simple can mean that you get to stability and good-quality much sooner than you would otherwise. The simple array-based approach can also support fairly good performance given a well-optimised implementation.

With careful thought, you may decide on alternative array-based structures. For example, you may draw inspiration from the 0x88 representation often used in Chess, though perhaps not directly applicable to Morabaraba. Alternatively, rather than using an array of positions, you may use arrays of cows (a 12-element array each for White and Black), with each element specifying the board position (1 - 24) of the piece, or 0 if the cow has not yet been played, or -1 if it has been captured.

Bitboards

Bitboards were invented by Robert Hyatt for his chess program Cray Blitz, and have since been used in many successful AI programs. A bitboard is simply an integer in which each bit corresponds to a location on the board. For example, you may use a 24-bit integer for White pieces, and another for Black. Each bit corresponds to a position on the board - eg if White occupies a square, then the corresponding bit is set to 1 in the White bitboard integer. Similarly, if Black occupies a square, then the corresponding bit is set to 1 in the Black bitboard integer. If a square is unoccupied, the corresponding bit will be 0 in both bitboards. You also have to store side-to-move, number of cows yet to play and machine gunning constraints: the first two can be encoded into "spare" bits (assuming you use 32-bit integers for your bitboards) or stored separately, whereas the latter can have its own bitboard representation.

The main advantage of bitboards is speed. Move generation can be reduced to simple binary arithmetic (using AND, OR, NOT and XOR operators), which processors can execute very rapidly. It's also quite easy and compact to test for patterns in the ecval using bitboards. Unfortunately, where bitboards are blazingly fast (even more suitable for Morabaraba than for Chess), they are also quite tricky, and producing a good implementation will probably require a lot more work than a simple array-based approach.

Conclusion

Selection of a board representation is a trade-off between speed and complexity; ultimately your choice is a personal one. My first Morabaraba releases were array-based; eventually I switched to bitboards, but I should warn that this involved an almost complete rewrite. While modern software development techniques could allow abstraction of the board representation (create an encapsulated Board class) which could be altered later, this does involve some sacrifice of processing speed, as the code generated by the compiler will almost certainly be slower than a tightly-coupled approach. Many programming "good practices" get sacrificed at the altar of speed when building a Morabaraba program - how many is ultimately up to you. More speed often means less maintainable code; while the speed is a very good thing in a Morabaraba program, the less-maintainable code may mean that you find it more difficult to implement clever new ideas in the future.