*Bounty: 200*

*Bounty: 200*

I’m writing a program that finds the minimax value of Chain Reaction on various small boards (à la Solving Go on Small Boards). Here’s a brief description of the game of Chain Reaction:

Chain Reaction is a two player combinatorial game played on an n×m game board (where n,m ≥ 2) in which players Red and Green take turns to place a single atom of their color in an empty square or in a square that they control. Placing more than one atom in the same square creates a molecule.

The more atoms in a molecule, the more unstable it becomes. When a molecule becomes too unstable it splits and its atoms move to orthogonally adjacent squares, changing the color of the atoms in those squares to match their color. This can cause a chain reaction of splitting molecules.

Molecules in the four corner squares require two atoms to split. Molecules on the edge of the board require three atoms to split. Molecules in the center of the board require four atoms to split. Atoms of a splitting molecule each move in a different direction. The game ends immediately after one player captures all of the atoms belonging to the other player.

I found the minimax value of Chain Reaction on the 2×2, 2×3, 2×4, 2×5, 2×6, 3×3 and 3×4 boards. However, I haven’t verified their correctness. Here are the values I obtained:

```
+---+---+---+---+---+---+
|nm| 2 | 3 | 4 | 5 | 6 |
+---+---+---+---+---+---+
| 2 |-2 |+4 |-6 |+8 |+10|
| 3 | |+7 |+10| | |
+---+---+---+---+---+---+
```

A positive value represents a win for Red. A negative value represents a loss for Red. The absolute value represents the number of moves to the terminal state under optimal play. A move consists of a turn by each player. Therefore, a value of -2 means that Red loses in two moves (i.e. Red loses in 4 turns). On the other hand, a value of +4 means that Red wins in four moves (i.e. Red wins in 7 turns). This is assuming Red plays first starting on an empty board.

Anyway, here’s the C program that I wrote to obtain these values:

```
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int x, y, z, m, v, h;
} transposition;
transposition table[2][0x1000000] = {0};
int v, w;
int negamax(int x, int y, int z, int m, int alpha, int beta) {
static int result = -8000, color = 1, height;
if (m) { // a move is to be played
// begin: add the atom to the board
int x2 = y & z, y2 = w ^ y ^ z ^ w & x2, z2 = ~z & (x | y), m2 = ~m;
x = x2 & m | m2 & x;
y2 = y2 & m | m2 & y;
z2 = z2 & m | m2 & z;
m &= z & (w | y);
y = y2, z = z2;
// end: add the atom to the board
while (m) { // a chain reaction is caused
// move the atoms to the North, East, west and South squares
int news[4] = { m >> v, m << 1, m >> 1, m << v };
m = 0; // splitting molecules for next iteration
for (int i = 0; i < 4; i++) { // for each direction, add atoms
int n = news[i];
x2 = y & z, y2 = w ^ y ^ z ^ w & x2, z = ~z & (x | y), m2 = ~n;
x = x2 & n | m2 & x;
y2 = y2 & n | m2 & y;
z2 = z2 & n | m2 & z;
m |= n & z & (w | y); // collect splitting molecules
y = y2, z = z2;
}
if ((x & (y | z)) == 0) { // the chain reaction wiped out the player
height = 0;
return result;
}
}
x ^= y | z; // swap players (i.e. Red becomes Green and vice versa)
}
// begin: calculate hash index and lookup transposition tables
int index = w;
index ^= x + 0x9E3779B9 + (index << 6) + (index >> 2);
index ^= y + 0x9E3779B9 + (index << 6) + (index >> 2);
index ^= z + 0x9E3779B9 + (index << 6) + (index >> 2);
index &= 0xFFFFFF;
for (int i = 0; i < 2; i++) {
transposition t = table[i][index];
if (t.x == x && t.y == y && t.z == z) {
height = t.h;
switch (t.v & 3) {
case 0: return t.v;
case 1: if (t.v > alpha) alpha = t.v; break;
case 2: if (t.v < beta) beta = t.v; break;
}
if (alpha >= beta) return t.v;
break;
}
} // end: calculate hash index and lookup transposition tables
int moves = y | z, cut = beta + 1 & ~3, value = -9000, h = 0, move;
result += 2 * (1 + color); // update return value for next ply
color =- color; // switch players
for (moves = (w | x | moves) & ~(x & moves); moves; moves &= moves - 1) {
m = moves & -moves; // the move is played when we call negamax
int val = -negamax(x, y, z, m, -beta, -alpha);
if (val > value) { value = val; move = m; }
if (val > alpha) alpha = val;
if (++height > h) h = height;
if (alpha >= beta) { value = (value + 1 & ~3) + 1; break; }
}
color =- color; // switch back players
result -= 2 * (1 + color); // restore return value for current ply
// begin: save return value in transposition table
transposition t = table[0][index];
int i = h < t.h;
if (!i) table[1][index] = t;
t.x = x;
t.y = y;
t.z = z;
t.m = move;
t.v = value;
t.h = height = h;
table[i][index] = t;
// end: save return value in transposition table
return value;
}
int main(int argc, char * argv[]) {
if (argc != 3) {
printf("Usage: %s nrows mcolsn", argv[0]);
printf(" nrows: number of rows (in the interval [2, 5])n");
printf(" mcols: number of cols (in the interval [n, 33/n-1])n");
return EXIT_SUCCESS;
}
int n = atoi(argv[1]);
if (n < 2 || n > 5) {
printf("Error: nrows must be in the interval [2, 5]n");
return EXIT_FAILURE;
}
int m = atoi(argv[2]);
if (m < n || m > 33 / n - 1) {
printf("Error: mcols must be in the interval [n, 33/n-1]");
return EXIT_FAILURE;
}
// begin: calculate initial empty bitboard values
v = m + 1, w = (1 << m) - 1;
{
int a = (1 << m - 1) + 1, b = w - a;
int i = n - 1, j = v, k = i * j;
w |= w << k;
x = a | a << k;
for (int k = 1; k < i; k++, j += v) {
w |= a << j;
x |= b << j;
}
}
// end: calculate initial empty bitboard values
int value = negamax(x, 0, 0, 0, -8000, 8000) / 4;
printf("#%dn", (value < 0 ? -2000 : 2000) - value);
return EXIT_SUCCESS;
}
```

Things you should know about my implementation:

- I used negamax with alpha beta pruning and transposition tables.
- I used the two-deep replacement scheme for transposition tables (with 2×2
^{24}entries). - I used bitboards to represent the game state. The variables
`w`

,`x`

,`y`

and`z`

hold the four bitboards that represent the game state. The variable`w`

never changes and hence it’s a global variable. The variable`m`

holds the bitboard for the current move. An explanation of how these bitboards work is found here. - The values are represented by integers such that:
- +2000 represents a win in 0 moves.
- +1999 represents a win in 1 move.
- +1998 represents a win in 2 moves.
- …
- -1998 represents a loss in 2 moves.
- -1999 represents a loss in 1 move.
- -2000 represents a loss in 0 moves.

- I’m using integrated bounds and values. Hence, the values are multiplied by 4. For lower bounds, the values are incremented. For upper bounds, the values are decremented.

I’d really appreciate it if you’d verify the correctness of my program and the values that it generates. Critiques and suggestions to improve my code are also welcome.