Solving Chain Reaction on Small Boards: Verifying Correctness

Question

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:

+---+---+---+---+---+---+
|n\m| 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 3: 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 mcols\n", 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("#%d\n", (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²⁴ 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.

Answer 1

This code is a bit hard to analyze for correctness, since the idea of bitboards is new to most people and hard to intuitively grasp in a short time. I think that's why this question hasn't received any answers.

You do have comments, which give a good high-level overview of what the goal of each section is, but it's not always clear why the code does what it does in order to accomplish things. In particular what do the members of transposition represent?

My suggestion would be to add more functions. Abstract out the various bit-twiddling operations with meaningful function names. Abstract out the hashing. Abstract out the "begin...end" sections. That way it would be both easier (both for you and others) to understand and also prove correctness.

Are you required to use straight C? A little bit of object-orientation could also improve the code's readability too.

A question for you. In this code:

    printf("Usage: %s nrows mcols\n", 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");

What do n and m stand for? it looks like they should be specified somewhere, but they're not.