Gomoku AI:如何使用位板找出连接是否被阻止？

Question

我正在实现一个具有数组位板的Gomoku AI。我有8个阵列板(行，列，对角线/，对角线)，4个人和4个计算机。每个数组都包含整数，每个整数表示一行、一列或一条对角线，我可以对其执行逐位操作。

public int[] humanRows = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

每当人类玩家或计算机选择移动时，属于该玩家的所有四个棋盘都会更新。这样，我可以很容易地检查5行，这是很好的。

for(int row: humanDiagonals){
        if ((row & (row>>1) & (row>>2) & (row>>3) & (row>>4)) != 0){
            return humanPiece;
        }
    } 

但现在问题来了。我希望能够找到所有模式(open-4、4-one-end-blocked等)来输入到我的求值函数中。但是我不能检查connect-4是否已经被阻塞，因为我不能用位板表示一个正方形的所有3个状态(空，X填充，O填充)。如果我使用&运算符合并位板，所有填充的方块将只表示为1，我将无法区分它们。我有一个类似下面的方法，但如你所见，它没有考虑阻塞的末端。

 public int comboCount(String combo, int[] board) {
    int count = 0;
    int len = combo.length();
    for (int row : board) {
        if (row != 0) { // if the row is not empty
            int shiftedRow = row;
            for (int i = 0; i < len; i++) {
                int temp = row >> i;
                shiftedRow &= temp;
            }
            String rowString = Integer.toBinaryString(shiftedRow);
            for (int k = 0; k < rowString.length(); k++) {
                if (rowString.charAt(k) == '1') {
                    count += 1;
                }
            }
        }
    }
    return count;
}

有谁能帮我找到一个解决方案。我有一种感觉，这个问题有一个简单的解决方案，但我不能理解它。这是我第一次修补比特，所以如果可能的话，请让解决方案变得简单。

Answer 1

你只需要先检查一行中是否有四行(但不能更长)，然后再检查合并后的电路板是否有更长的行。

使用这些方便的函数...

private static boolean hasFourInRow(int row){
    return (row & (row >> 1) & (row >> 2) & (row >> 3)) != 0;
}

private static boolean hasFiveInRow(int row){
    return (row & (row >> 1) & (row >> 2) & (row >> 3) & (row >> 4)) != 0;
}

private static boolean hasSixInRow(int row){
    return (row & (row >> 1) & (row >> 2) & (row >> 3) & 
            (row >> 4) & (row >> 5)) != 0;
}

以下是您可以轻松检测到您提到的情况的方法：

public static void main(String[] args) {
    int humanRow = 0b00011110;
    int computerRow = 0b00100001;

    if (hasFourInRow(humanRow) && !hasFiveInRow(humanRow)){
        int combinedRow = humanRow | computerRow;

        if (!hasFiveInRow(combinedRow)){
            System.out.println("Open 4!");
        } else if (!hasSixInRow(combinedRow)){
            System.out.println("4-one-end-blocked!");
        } else {
            System.out.println("4-both-ends-blocked!");
        }
    }       
}