Move Generator

The move generator is simply a function which, given a particular position, is able to generate all possible legal moves. Obviously the move generator for every game is different, but in Morabaraba you should consider the following points:

• The move generator needs to understand the phases of the game:
• initially, cows are simply placed on any free spot
• then, cows are moved from spot to adjacent spot
• finally, when a player is down to just 3 pieces, any of the cows may move to any free spot
• When capturing, each permitted capture is a separate move
• Consider the "machine gunning" rule when capturing - you need to know what the last move made by the side-to-move was, in order to check whether a given capture is legal
• When generating captures, ensure that you only permit capture of cows not in mills (unless all the opponent's cows are in mills, in which case any cow may be captured)

Because the move generator is such a critical part of the system, it is important to test it very carefully - the tiniest bug in the move generator can result in your program failing completely or - even worse - making inexplicable, irrational, bad moves. Therefore it makes sense to build up a library of test positions of all different types (in every phase of the game, with white and with black to move, with and without captures, with and without possible "machine gunning" moves) and test completely every time the move generator is changed.

Most Morabaraba programs will be "tree searchers", using the AlphaBeta algorithm or one of its cousins. In these types of programs, the move generator may be called hundreds of thousands (or millions) of times in the course of computing the best move, so it is vital that your move generator is very efficient. If it is slow, your program will not be able to search far ahead, and will therefore not play well.