Bitboard representation for nine men morris game

StackOverflow https://stackoverflow.com/questions/15405419

Question

I'm writing a Nine Men's Morris game in Java and have already the implemented the game rules and an AI using negamax. However, the game is based on arrays and move generation takes quite some time when the AI is thinking (starting from a ply of 6).

My positions array is based on the following diagram:

// 0        1        2
//    3     4     5
//       6  7  8
// 9  10 11    12 13 14
//       15 16 17
//    18    19    20
// 21       22       23

I've got further arrays filled with possible mills and adjacent positions.

I decided to change the game from arrays to using bitboards so that move generation and other areas that currently use arrays will be much more faster.

My first step would be to have a bitboard for each player which will keep track of the player's pieces on the board.

The second steps would be to determine where the free positions are. I know I can do this by doing:

freepositions = ~(player1bb | player2bb);

So my question is, how can I setup/update the player's bitboards to keep track of their pieces?

Was it helpful?

Solution

Taking into consideration that a player's bitboard is 24bits long with position 0 of the board being the first bit, setting the bitboard when a player makes a move turns out to be quite simple by doing the following:

player1bb |= (1 << pos);

OTHER TIPS

Bitboards are fun :-)

I am cooking up some code for this problem but here is something to get you started hopefully:

public class BitBoard {
    public static final int White = 0;
    public static final int Black = 1;

    public long[] board = { 0, 0 };
    public int Player = 0;
    public int[] left = { 9, 9 };

    public int Opponent()
    {
        return Player == White ? Black : White;
    }

    public void makemove(int from, int to, int capture)
    {
        if (from == 0) { 
            assert left[Player] > 0 : "makemove: no left";
            left[Player]--;
        }       
        if (from != 0)
        {
            assert (board[Player] & from) != 0 : "makemove: source empty";
            board[Player] &= ~from;
        }
        assert (board[Player] & to) == 0 : "makemove: target must be empty";
        board[Player] |= to;
        if (capture != 0)
        {
            assert (board[Opponent()] & capture) != 0 : "makemove: capture empty";
            board[Opponent()] &= ~capture;
        }
    }

    public void unmakemove(int from, int to, int capture)
    {
        if (capture != 0)
        {
            assert (board[Opponent()] & capture) == 0 : "unmakemove: capture empty";
            board[Opponent()] |= capture;
        }
        assert (board[Player] & to) != 0 : "unmakemove: target empty";
        board[Player] &= ~to;
        if (from != 0)
        {
            assert (board[Opponent()] & capture) != 0 : "unmakemove: source must be empty empty";
            board[Player] |= from;
        }
        if (from == 0) { 
            assert left[Player] < 9 : "unmakemove: too many left";
            left[Player]++;
        }           
    }

    public void generatemoves()
    {
        // determine phase

        // 

    }
}

Didn't test this fully but following code shows how to use:

import java.math.*;

public class NineMenBitboard {
    static int tst;

    //   A  B  C  D  E  F  G
    // 1 0        1        2
    // 2    3     4     5
    // 3       6  7  8
    // 4 9 10 11    12 13 14
    // 5      15 16 17
    // 6   18    19    20
    // 7 21       22       23

    // positions

    static int A1 = 1 << 0;
    static int D1 = 1 << 1;
    static int G1 = 1 << 2;
    static int B2 = 1 << 3;
    static int D2 = 1 << 4;
    static int F2 = 1 << 5;
    static int C3 = 1 << 6;
    static int D3 = 1 << 7;
    static int E3 = 1 << 8;
    static int A4 = 1 << 9;
    static int B4 = 1 << 10;
    static int C4 = 1 << 11;
    static int E4 = 1 << 12;
    static int F4 = 1 << 13;
    static int G4 = 1 << 14;
    static int C5 = 1 << 15;
    static int D5 = 1 << 16;
    static int E5 = 1 << 17;
    static int B6 = 1 << 18;
    static int D6 = 1 << 19;
    static int F6 = 1 << 20;
    static int A7 = 1 << 21;
    static int D7 = 1 << 22;
    static int G7 = 1 << 23;

    // mills

    static int hor1 = A1 | D1 | G1;
    static int hor2 = B2 | D2 | F2;
    static int hor3 = C3 | D3 | E3;
    static int hor4_1 = A4 | B4 | C4;
    static int hor4_2 = E4 | F4 | G4;
    static int hor5 = C5 | D5 | E5;
    static int hor6 = B6 | D6 | F6;
    static int hor7 = A7 | D7 | G7;

    static int ver1 = A1 | A4 | A7;
    static int ver2 = B2 | B4 | B6;
    static int ver3 = C3 | C4 | C5;
    static int ver4_1 = D1 | D2 | D3;
    static int ver4_2 = D5 | D6 | D7;
    static int ver5 = E3 | E4 | E5;
    static int ver6 = F2 | F4 | F6;
    static int ver7 = G1 | G4 | G7; 

    public static void main(String[] args) {
        // sample on how to loop bits

        BitBoard game = new BitBoard();
        game.makemove(0, A1, 0);
        game.makemove(A1, A4, 0);


        System.out.println();

        tst = 255;

        for(int looper = tst, i = Integer.highestOneBit(looper); looper != 0; looper &= ~i, i = Integer.highestOneBit(looper))
        {
            System.out.println(i);
        }       

        System.out.println(tst);
      }
}

Also added a loop to show how you can loop through positions.

Have fun. I'll be coding this game too since I want to refresh my AB pruning :-)

Here is the Perft code. Am doing all first moves as well, but in a future version I'll probably only do the 6 unique ones (the others will just result in evaluating mirrors).

public long Perft(int depth)
{
    long nodes = 0;

    ArrayList<Integer> moves = generateMoves();

    if (depth == 1) 
    {
        //for(int move : moves)
        //  System.out.println(moveStr(move));
        return moves.size();
    }

    for (int move : moves) {
        int capture = 1 << (move >> 10) >> 1; 
        int to = 1 << ((move >> 5) & 31) >> 1;
        int from = 1 << (move & 31) >> 1;           
        makemove(from, to, capture);
        //System.out.print(this);
        nodes += Perft(depth - 1);
        unmakemove(from, to, capture);
    }
    return nodes;       
}

I packed moves into ints as you see.

For the sanity check here are my first perft results:

  • 1 24
  • 2 552
  • 3 12144
  • 4 255024
  • 5 5140800
  • 6 99274176 (3.107ms)
  • 7 1873562112 (53 sec)
  • 8 takes too long

I know you aleadry implemnted it ,but you should implement it like that

//  0        1           2
//     8     9       10
//        16  17  18
//  7 15  23      19 11  3
//        22   21 20
//    14    13       12
//  6       5            4

that way you can move threw postions pos >> 1 for privious pos << 1 for next , pos << 8 for next byte same postion pos >> 8 previous for byte same postion

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top