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
• ```#define SQUARES_ON_BOARD (16*16)
#define BITS_PER_BYTE 8

typedef int h_bitset[SQUARES_ON_BOARD /
(sizeof(unsigned int) * BITS_PER_BYTE)];

typedef struct {
h_bitset occupied;
h_bitset colour;
} h_board;```

## 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

• ```#define SQUARES_ON_BOARD (16*16)
#define BITS_PER_BYTE 8
#define PEGS_PER_COLOUR 19
#define WHITE 0
#define BLACK 1
#define NO_PLAYERS 2

typedef int h_bitset[SQUARES_ON_BOARD /
(sizeof(unsigned int) * BITS_PER_BYTE)];

typedef struct {
h_bitset occupied;
h_bitset colour;
unsigned char position[NO_PLAYERS][PEGS_PER_COLOUR];
} h_board;```

• 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)
{
add_piece (b, WHITE, 0, 0);
add_piece (b, WHITE, 1, 1);
add_piece (b, WHITE, 2, 2);
add_piece (b, WHITE, 3, 3);
add_piece (b, WHITE, 4, 16);
add_piece (b, WHITE, 5, 17);
add_piece (b, WHITE, 6, 18);
add_piece (b, WHITE, 7, 32);
add_piece (b, WHITE, 8, 33);
add_piece (b, WHITE, 9, 34);
add_piece (b, WHITE, 10, 48);
add_piece (b, WHITE, 11, 49);
add_piece (b, WHITE, 12, 50);
add_piece (b, WHITE, 13, 64);
add_piece (b, WHITE, 14, 65);
}```

## 9. add_piece

• ```void add_piece (h_board *b, int colour, int piece, int square)
{
INCL(b->occupied, square);
if (colour == WHITE)
EXCL(b->colour, square);
else
INCL(b->colour, square);
b->position[piece] = square;
}```

## 10. INCL

• ```void INCL (h_bitset *b, int element)
{
int array_element = element/
(sizeof(unsigned int) * BITS_PER_BYTE);
int bit_in_element = element % sizeof(unsigned int);
b[array_element] |= (1 << bit_in_element);
}```

## 11. EXCL

• ```void EXCL (h_bitset *b, int element)
{
int array_element = element/
(sizeof(unsigned int) * BITS_PER_BYTE);
int bit_in_element = element % sizeof(unsigned int);
b[array_element] &= (! (1 << bit_in_element));
}```

## 12. IS_IN

• ```int IS_IN (h_bitset *b, int element)
{
int array_element = element/(sizeof(unsigned int)
* BITS_PER_BYTE);
int bit_in_element = element % sizeof(unsigned int);
return (b[array_element] & (1 << bit_in_element)) != 0;
}```

## 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. add_piece
10. INCL
11. EXCL
12. IS_IN
Index

This document was produced using groff-1.22.