5
\$\begingroup\$

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×224 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.

\$\endgroup\$
2
+100
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ The members of transposition represent the state of the game board (i.e. x, y, z), the best move (i.e. m), the value of the position (i.e. v) and the height of the subtree (i.e. h). We need to store the state of the game board so that we can check whether the transposition table entry is valid. We need to store the move in case we decide to use iterative deepening (which I'm currently not doing). We need to store the value because that's what we're memoizing. We need to store the height because we're using the two-deep replacement scheme to prioritize which positions to store. =) \$\endgroup\$ – Aadit M Shah Dec 30 '17 at 14:54
  • \$\begingroup\$ I did specify what n and m stand for in the description of the game. To quote, "Chain Reaction is a two player combinatorial game played on an n×m game board (where n,m ≥ 2)...." This program uses 32 bit integers to represent the game board. Hence, it can only support 2 to 5 rows (i.e. n is in the interval [2, 5]) since the number of columns has to be at least equal to the number of rows and 6×6 > 32. Given the value of n, the number of columns (i.e. m) must be in the interval [n, 33/n-1] so that the game board doesn't exceed 32 bits. Hope that elucidates things. \$\endgroup\$ – Aadit M Shah Dec 30 '17 at 15:03
  • \$\begingroup\$ I'm not required to use C. I just prefer using it over C++ because I don't believe in object-orientation (I'm a functional programmer). That being said, I'll certainly break my code into smaller functions and better data structures so that it's easier to understand. I'll update the code in my question as soon as possible. Thanks for the feedback. Glad to have some external input on my code. I really do appreciate it. \$\endgroup\$ – Aadit M Shah Dec 30 '17 at 15:10
  • \$\begingroup\$ The problem is, sometimes you use n and m, sometimes you use rows and cols, and sometimes use yous nrows and mcols. Try to be consistent. How about just rows and cols? Single-letter variable names don't help anyone at all. Use meaningful variable names. \$\endgroup\$ – Snowbody Dec 31 '17 at 5:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.