Index

1. Halma board game

• the board consists of a grid of 16 by 16 squares
• the game may be played by two or four players
• we will only consider two player game
• each player’s camp consists of a cluster of adjacent squares in one corner of the board
• in two-player games, each player’s camp is a cluster of 19 squares
• in the four-player game, each player’s camp is a cluster of 13 squares
• see http://en.wikipedia.org/wiki/Image:Halma4.svg
• each camp exists in the board corner
• each player has a set of pieces in a distinct colour, of the same number as squares in each camp.

2. Halma Objective

• is to move all your pieces to occupy the opposing camp
• which is diagonally opposite to your own
• Victorian board game
• a move consists of moving one piece:
• either one square (assuming it is empty)
• or hopping over another piece (of any colour)
• a piece may hop multiple times in any direction and it leaves any hopped pieces alone

3. Kangaroo Halma

• variation - to speed the game up, allows the hopping piece to take giant hops over any piece in any direction
• as long as all squares either side of the hop are empty
• each hop must be symmetrical
• you can still perform multiple hops during one move for one piece
• each hop may be of different symmetrical lengths

4. How can you program the game?

• need to decide which data structures to use
• need a board representation
• maybe use two 256 bit sets
• one to determine whether a position is occupied
• one to determine whether black or white
• ```CONST
BoardSize = 256 ;

TYPE
Squares = [0..BoardSize-1] ;
SoS     = SET OF Squares ;
Colour  = (Blue, Red) ;

Board = RECORD
(* is the square used at all? *)
used  : SoS ;
(* if so which colour occupies the square? *)
colour: SoS ;
END ;```

5. Efficiency

• problem with the previous method
• to search for legal moves would require searching the complete 256 bitset
• maybe we could utilise a list of pieces array as well
• gives us a fast method to find each piece
• at the expense of having to maintain both data structures

6. Revised halma board data structures

• ```Squares = [0..BoardSize-1] ;
SoS     = SET OF Squares ;
Colour  = (Blue, Red) ;

Board = RECORD
used  : SoS ;   (* is the square used at all? *)
colour: SoS ;   (* if so which colour occupies the square? *)
pieces: ARRAY [MIN(Colour)..MAX(Colour)] OF ARRAY [1..Pieces] OF CARDINAL8 ;
(* home is a count of the number of tiles in the destination base *)
home  : ARRAY [MIN(Colour)..MAX(Colour)] OF CARDINAL ;
END ;

Moves = RECORD
(* pieceHead[0] is start of peg 1 moves in the heap *)
(* pieceHead[1] is start of peg 2 moves in the heap *)
pieceHead: ARRAY [0..Pieces] OF CARDINAL ;
pieceList: ARRAY [0..PieceHeap] OF CARDINAL8 ;
END ;```

• how many bytes are used by the first version of the halma board data structure?
• how many bytes used by the second?
• is this an acceptable tradeoff?

7. Board manipulation routines

• need a function to initialise the board
• need a function to test whether a square is empty
• need a function to effect a move

8. Initialisation

• ```void board_init (h_board *b)
{
}```

9. Data structure performance

• the above data structures perform reasonably
• able to search around 4,000,000 positions in about 10 seconds on a 2.7GHz desktop machine
• between 3-4 plies
• looks far enough ahead to play moderately and still be fun

10. Halma implementation

• uses PyGame to handle the GUI
• game engine written in Modula-2, console text input/output
• the GUI written python connects to the game engine using the pexpect module
• this allows the user to make a move
• move is conveyed to the game engine
• the GUI moves the tile slowly and smoothly across the board
• the game engine is considering the next move at the same time
• very easy to implement this technique using Python and pexpect

11. Halma Evaluation Function

• short circuits any score if all pieces are in destination base
• otherwise it gives a score for each peg based on how close it is to the corner square in destination base
• it incrementally adjusts the score every time a tile is moved

12. Algorithms used

• AlphaBeta is used to explore the game tree
• once the best move has been found it creates a graph of all squares reachable from this tile
• uses Dijkstra’s routing algorithm to work out shortest path between tile and destination square
• nearly as much code as the AlphaBeta and tree exploration code

13. Conclusion

• python, pygame and pexpect can be used to produce 2D games
• Halma has been packaged into a .deb package and can be downloaded and installed on an i386 or x86_64 based Ubuntu or Debian operating system

Index

1. Halma board game
2. Halma Objective
3. Kangaroo Halma
4. How can you program the game?
5. Efficiency
6. Revised halma board data structures
7. Board manipulation routines
8. Initialisation
9. Data structure performance
10. Halma implementation
11. Halma Evaluation Function
12. Algorithms used
13. Conclusion
Index

This document was produced using groff-1.22.