java - 五子棋人工智能 : How to find out if a connect is blocked using bit boards?

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};

每当人类玩家或计算机选择一个 Action 时，属于该玩家的所有四个棋盘都会更新。这样，我可以轻松检查连续 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 填充)。如果我使用 & 运算符合并位板，所有填充的方 block 将仅表示为 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!");
        }
    }       
}