javabit-manipulationartificial-intelligencebitboard

Java connect four bit wise functions and bit board errors


Essentially im trying to create a connect four Ai and i came across an article which uses bit boards to optimize making moves and checking for wins. Essentially i took a few methods from a git hub readme which are supposed to make a move and undo a move on your bit board unfortunately it appears that the methods are not working properly because it's placing ones at the end of the bit string instead of spacing them by 7. I assume this is probably some java thing that is preventing these from working correctly and i have posted a sample program below which i think demonstrates the problem accurately. For example if i set a long variable so that it has a row of four ones on the 5th row and display it. It displays correctly without the beginning zeros but on the other hand if i add three tokens to the first column. And then three tokens to the third column. It displays as 111, and 111. When it should be

000000000000000000000000011100000000000000
000000000000000000000000000000000000000111

and without the leading zeros so

11100000000000000
111

Then if i run another test with these colum drops 1,3,1,3,2,4 which should result in this board state.

|   |   |   |   |   |   |   |
|   |   |   |   |   |   |   |
|   |   |   |   |   |   |   |
|   |   |   |   |   |   |   |
| X |   | O |   |   |   |   |
| X | X | O | O |   |   |   |
-----------------------------

It displays 10, 10 when it should be

000000000000000000001000001100000000000000
000000000000000000000000000000000010000011

or

1000001100000000000000
10000011

Here is some testing code which demonstrates this second scenario. At this point im at a loss because the operations of these methods are quite elegant and complex although they are only 3 lines of code it would be greatly appreciated if anyone could tell me whats wrong with what im doing. Cheers!

public class EConnectFour {
    private static int[] height = {0, 0, 0, 0, 0, 0, 0};
    private static int counter = 0;
    private static int[] moves = new int[42];
    private static long[] bitBoard = new long[2];



    public static void main(String[] args) {
          long TOP = 0b0000000001000000100000010000001000000000000000000L;
          System.out.println(Long.toBinaryString(TOP));
          makeMove(1);
          makeMove(3);
          makeMove(1);
          makeMove(3);
          makeMove(2);
          makeMove(4);
          System.out.println(Long.toBinaryString(bitBoard[0]));
          System.out.println(Long.toBinaryString(bitBoard[1]));
    }

    private static boolean isWin(long board) {
        int[] directions = {1, 7, 6, 8};
        long bb;
        for(int direction : directions) {
            bb = board & (board >> direction);
            if ((bb & (bb >> (2 * direction))) != 0) return true;
        }
        return false;
    }

    private static void makeMove(int column) {
        long move = 1L << height[column]++;
        bitBoard[counter & 1] ^= move; 
        moves[counter++] = column;  
    }

    private static void undoMove() {
        int column = moves[--counter];
        long move = 1L << --height[column];
        bitBoard[counter & 1] ^= move;
    }
}

Solution

  • You inadvertently kept dropping tokens into the same first slot.

    Replace:

    // long move = 1L << height[column]++;
    long move = 1L << (height[column]++ + ((column-1) * height.length));
    

    Your reference to column is off by one (arrrays in Java are 0-indexed). At the end of your run, the height looks like this:

    height = [0, 2, 1, 2, 1, 0, 0]
    

    You can fix that with:

    long move = 1L << (height[column-1]++ + ((column-1) * height.length));
    

    Final version of makeMove:

    private static void makeMove(int column) {
        long move = 1L << (height[column-1]++ + ((column-1) * height.length));
        bitBoard[counter & 1] ^= move; 
        moves[counter++] = column;  
    }
    

    Version of undoMove:

    private static void undoMove() {
        int column = moves[--counter];
        moves[counter] = 0;  
        long move = 1L << (--height[column-1] + ((column-1) * height.length));
        bitBoard[counter & 1] ^= move;
    }