我如何使用 convolve2d 来计算两个玩家在 connect 4 中达到获胜条件的次数？

Question

我正在创建一个连四游戏，棋盘是 7x6 棋盘。我希望能够计算每个玩家获得的 4-in-a-row 的数量。当第一个玩家放置他们的第一个 4-in-a-row 时，游戏并没有结束。只有当棋盘完全填满时，游戏才会结束。游戏的可能结束状态如下：

 ----------------
 |2 2 1 2 2 1 1 |
 |1 2 2 2 1 2 1 |
 |2 1 2 1 2 2 1 |
 |1 1 1 1 2 2 1 |
 |2 1 1 1 1 1 1 |
 |2 1 2 2 2 2 2 |
 ----------------

在这种情况下，玩家 1 的得分为 10，玩家 2 的得分为 2。我希望能够使用 convolve2d 来计算两个玩家的 4-in-a-row。 4 行可以是对角线、水平线或垂直线。我找到了 Manuel Faysse 的这个答案：

但是，这只会计算单行 4 的出现次数。我已经实现了一个通过蛮力执行此操作的功能，但它相当缓慢且麻烦。我怎样才能改变 Manuel 给出的答案来做我想做的事情？

暴力破解方式：

class MaxConnect4game:
    def __init__(self):
        self.gameboard = [[0 for i in range(7)] for j in range(6)]
        self.current_move = 0
        self.piece_count = 0
        self.player1Score = 0
        self.player2Score = 0
        self.gameFile = None
        self.computer_column = None
        self.depth = 1

    def countScore(self):
        self.player1Score = 0;
        self.player2Score = 0;
        # Check horizontally
        for row in self.gameboard:
            # Check player 1
            if row[0:4] == [1] * 4:
                self.player1Score += 1
            if row[1:5] == [1] * 4:
                self.player1Score += 1
            if row[2:6] == [1] * 4:
                self.player1Score += 1
            if row[3:7] == [1] * 4:
                self.player1Score += 1
            # Check player 2
            if row[0:4] == [2] * 4:
                self.player2Score += 1
            if row[1:5] == [2] * 4:
                self.player2Score += 1
            if row[2:6] == [2] * 4:
                self.player2Score += 1
            if row[3:7] == [2] * 4:
                self.player2Score += 1

        # Check vertically
        for j in range(7):
            # Check player 1
            if (self.gameboard[0][j] == 1 and self.gameboard[1][j] == 1 and
                    self.gameboard[2][j] == 1 and self.gameboard[3][j] == 1):
                self.player1Score += 1
            if (self.gameboard[1][j] == 1 and self.gameboard[2][j] == 1 and
                    self.gameboard[3][j] == 1 and self.gameboard[4][j] == 1):
                self.player1Score += 1
            if (self.gameboard[2][j] == 1 and self.gameboard[3][j] == 1 and
                    self.gameboard[4][j] == 1 and self.gameboard[5][j] == 1):
                self.player1Score += 1
            # Check player 2
            if (self.gameboard[0][j] == 2 and self.gameboard[1][j] == 2 and
                    self.gameboard[2][j] == 2 and self.gameboard[3][j] == 2):
                self.player2Score += 1
            if (self.gameboard[1][j] == 2 and self.gameboard[2][j] == 2 and
                    self.gameboard[3][j] == 2 and self.gameboard[4][j] == 2):
                self.player2Score += 1
            if (self.gameboard[2][j] == 2 and self.gameboard[3][j] == 2 and
                    self.gameboard[4][j] == 2 and self.gameboard[5][j] == 2):
                self.player2Score += 1
        # Check diagonally

        # Check player 1
        if (self.gameboard[2][0] == 1 and self.gameboard[3][1] == 1 and
                self.gameboard[4][2] == 1 and self.gameboard[5][3] == 1):
            self.player1Score += 1
        if (self.gameboard[1][0] == 1 and self.gameboard[2][1] == 1 and
                self.gameboard[3][2] == 1 and self.gameboard[4][3] == 1):
            self.player1Score += 1
        if (self.gameboard[2][1] == 1 and self.gameboard[3][2] == 1 and
                self.gameboard[4][3] == 1 and self.gameboard[5][4] == 1):
            self.player1Score += 1
        if (self.gameboard[0][0] == 1 and self.gameboard[1][1] == 1 and
                self.gameboard[2][2] == 1 and self.gameboard[3][3] == 1):
            self.player1Score += 1
        if (self.gameboard[1][1] == 1 and self.gameboard[2][2] == 1 and
                self.gameboard[3][3] == 1 and self.gameboard[4][4] == 1):
            self.player1Score += 1
        if (self.gameboard[2][2] == 1 and self.gameboard[3][3] == 1 and
                self.gameboard[4][4] == 1 and self.gameboard[5][5] == 1):
            self.player1Score += 1
        if (self.gameboard[0][1] == 1 and self.gameboard[1][2] == 1 and
                self.gameboard[2][3] == 1 and self.gameboard[3][4] == 1):
            self.player1Score += 1
        if (self.gameboard[1][2] == 1 and self.gameboard[2][3] == 1 and
                self.gameboard[3][4] == 1 and self.gameboard[4][5] == 1):
            self.player1Score += 1
        if (self.gameboard[2][3] == 1 and self.gameboard[3][4] == 1 and
                self.gameboard[4][5] == 1 and self.gameboard[5][6] == 1):
            self.player1Score += 1
        if (self.gameboard[0][2] == 1 and self.gameboard[1][3] == 1 and
                self.gameboard[2][4] == 1 and self.gameboard[3][5] == 1):
            self.player1Score += 1
        if (self.gameboard[1][3] == 1 and self.gameboard[2][4] == 1 and
                self.gameboard[3][5] == 1 and self.gameboard[4][6] == 1):
            self.player1Score += 1
        if (self.gameboard[0][3] == 1 and self.gameboard[1][4] == 1 and
                self.gameboard[2][5] == 1 and self.gameboard[3][6] == 1):
            self.player1Score += 1

        if (self.gameboard[0][3] == 1 and self.gameboard[1][2] == 1 and
                self.gameboard[2][1] == 1 and self.gameboard[3][0] == 1):
            self.player1Score += 1
        if (self.gameboard[0][4] == 1 and self.gameboard[1][3] == 1 and
                self.gameboard[2][2] == 1 and self.gameboard[3][1] == 1):
            self.player1Score += 1
        if (self.gameboard[1][3] == 1 and self.gameboard[2][2] == 1 and
                self.gameboard[3][1] == 1 and self.gameboard[4][0] == 1):
            self.player1Score += 1
        if (self.gameboard[0][5] == 1 and self.gameboard[1][4] == 1 and
                self.gameboard[2][3] == 1 and self.gameboard[3][2] == 1):
            self.player1Score += 1
        if (self.gameboard[1][4] == 1 and self.gameboard[2][3] == 1 and
                self.gameboard[3][2] == 1 and self.gameboard[4][1] == 1):
            self.player1Score += 1
        if (self.gameboard[2][3] == 1 and self.gameboard[3][2] == 1 and
                self.gameboard[4][1] == 1 and self.gameboard[5][0] == 1):
            self.player1Score += 1
        if (self.gameboard[0][6] == 1 and self.gameboard[1][5] == 1 and
                self.gameboard[2][4] == 1 and self.gameboard[3][3] == 1):
            self.player1Score += 1
        if (self.gameboard[1][5] == 1 and self.gameboard[2][4] == 1 and
                self.gameboard[3][3] == 1 and self.gameboard[4][2] == 1):
            self.player1Score += 1
        if (self.gameboard[2][4] == 1 and self.gameboard[3][3] == 1 and
                self.gameboard[4][2] == 1 and self.gameboard[5][1] == 1):
            self.player1Score += 1
        if (self.gameboard[1][6] == 1 and self.gameboard[2][5] == 1 and
                self.gameboard[3][4] == 1 and self.gameboard[4][3] == 1):
            self.player1Score += 1
        if (self.gameboard[2][5] == 1 and self.gameboard[3][4] == 1 and
                self.gameboard[4][3] == 1 and self.gameboard[5][2] == 1):
            self.player1Score += 1
        if (self.gameboard[2][6] == 1 and self.gameboard[3][5] == 1 and
                self.gameboard[4][4] == 1 and self.gameboard[5][3] == 1):
            self.player1Score += 1

        # Check player 2
        if (self.gameboard[2][0] == 2 and self.gameboard[3][1] == 2 and
                self.gameboard[4][2] == 2 and self.gameboard[5][3] == 2):
            self.player2Score += 1
        if (self.gameboard[1][0] == 2 and self.gameboard[2][1] == 2 and
                self.gameboard[3][2] == 2 and self.gameboard[4][3] == 2):
            self.player2Score += 1
        if (self.gameboard[2][1] == 2 and self.gameboard[3][2] == 2 and
                self.gameboard[4][3] == 2 and self.gameboard[5][4] == 2):
            self.player2Score += 1
        if (self.gameboard[0][0] == 2 and self.gameboard[1][1] == 2 and
                self.gameboard[2][2] == 2 and self.gameboard[3][3] == 2):
            self.player2Score += 1
        if (self.gameboard[1][1] == 2 and self.gameboard[2][2] == 2 and
                self.gameboard[3][3] == 2 and self.gameboard[4][4] == 2):
            self.player2Score += 1
        if (self.gameboard[2][2] == 2 and self.gameboard[3][3] == 2 and
                self.gameboard[4][4] == 2 and self.gameboard[5][5] == 2):
            self.player2Score += 1
        if (self.gameboard[0][1] == 2 and self.gameboard[1][2] == 2 and
                self.gameboard[2][3] == 2 and self.gameboard[3][4] == 2):
            self.player2Score += 1
        if (self.gameboard[1][2] == 2 and self.gameboard[2][3] == 2 and
                self.gameboard[3][4] == 2 and self.gameboard[4][5] == 2):
            self.player2Score += 1
        if (self.gameboard[2][3] == 2 and self.gameboard[3][4] == 2 and
                self.gameboard[4][5] == 2 and self.gameboard[5][6] == 2):
            self.player2Score += 1
        if (self.gameboard[0][2] == 2 and self.gameboard[1][3] == 2 and
                self.gameboard[2][4] == 2 and self.gameboard[3][5] == 2):
            self.player2Score += 1
        if (self.gameboard[1][3] == 2 and self.gameboard[2][4] == 2 and
                self.gameboard[3][5] == 2 and self.gameboard[4][6] == 2):
            self.player2Score += 1
        if (self.gameboard[0][3] == 2 and self.gameboard[1][4] == 2 and
                self.gameboard[2][5] == 2 and self.gameboard[3][6] == 2):
            self.player2Score += 1

        if (self.gameboard[0][3] == 2 and self.gameboard[1][2] == 2 and
                self.gameboard[2][1] == 2 and self.gameboard[3][0] == 2):
            self.player2Score += 1
        if (self.gameboard[0][4] == 2 and self.gameboard[1][3] == 2 and
                self.gameboard[2][2] == 2 and self.gameboard[3][1] == 2):
            self.player2Score += 1
        if (self.gameboard[1][3] == 2 and self.gameboard[2][2] == 2 and
                self.gameboard[3][1] == 2 and self.gameboard[4][0] == 2):
            self.player2Score += 1
        if (self.gameboard[0][5] == 2 and self.gameboard[1][4] == 2 and
                self.gameboard[2][3] == 2 and self.gameboard[3][2] == 2):
            self.player2Score += 1
        if (self.gameboard[1][4] == 2 and self.gameboard[2][3] == 2 and
                self.gameboard[3][2] == 2 and self.gameboard[4][1] == 2):
            self.player2Score += 1
        if (self.gameboard[2][3] == 2 and self.gameboard[3][2] == 2 and
                self.gameboard[4][1] == 2 and self.gameboard[5][0] == 2):
            self.player2Score += 1
        if (self.gameboard[0][6] == 2 and self.gameboard[1][5] == 2 and
                self.gameboard[2][4] == 2 and self.gameboard[3][3] == 2):
            self.player2Score += 1
        if (self.gameboard[1][5] == 2 and self.gameboard[2][4] == 2 and
                self.gameboard[3][3] == 2 and self.gameboard[4][2] == 2):
            self.player2Score += 1
        if (self.gameboard[2][4] == 2 and self.gameboard[3][3] == 2 and
                self.gameboard[4][2] == 2 and self.gameboard[5][1] == 2):
            self.player2Score += 1
        if (self.gameboard[1][6] == 2 and self.gameboard[2][5] == 2 and
                self.gameboard[3][4] == 2 and self.gameboard[4][3] == 2):
            self.player2Score += 1
        if (self.gameboard[2][5] == 2 and self.gameboard[3][4] == 2 and
                self.gameboard[4][3] == 2 and self.gameboard[5][2] == 2):
            self.player2Score += 1
        if (self.gameboard[2][6] == 2 and self.gameboard[3][5] == 2 and
                self.gameboard[4][4] == 2 and self.gameboard[5][3] == 2):
            self.player2Score += 1

Answer 1

您找到的答案几乎完成了所有艰苦的工作。您需要做的就是将 if 语句更改为 sum:

import numpy as np
from scipy.signal import convolve2d

horizontal_kernel = np.array([[ 1, 1, 1, 1]])
vertical_kernel = np.transpose(horizontal_kernel)
diag1_kernel = np.eye(4, dtype=np.uint8)
diag2_kernel = np.fliplr(diag1_kernel)
detection_kernels = [horizontal_kernel, vertical_kernel, diag1_kernel, diag2_kernel]

def winning_moves(board, player):
    connect_4s = 0
    for kernel in detection_kernels:
        connect_4s += np.sum(convolve2d(board == player, kernel, mode="valid") == 4)
    return connect_4s

x = '2 2 1 2 2 1 1|1 2 2 2 1 2 1|2 1 2 1 2 2 1|1 1 1 1 2 2 1|2 1 1 1 1 1 1|2 1 2 2 2 2 2'
board = np.array([[int(a) for a in y.split(' ')] for y in x.split('|')])
#[[2 2 1 2 2 1 1]
# [1 2 2 2 1 2 1]
# [2 1 2 1 2 2 1]
# [1 1 1 1 2 2 1]
# [2 1 1 1 1 1 1]
# [2 1 2 2 2 2 2]]
winning_moves(board, 1)
# 10
winning_moves(board, 2)
# 2

说明

有很多网站解释了卷积 (e.g. Wikipedia)，但为了给您一些实用的直觉，这有望帮助您展示当您拥有一长串 1 时卷积是如何扩展的（在这种情况下）：

for ncol in range(4,10):
    result = convolve(horizontal_kernel, np.ones([1,ncol]), mode = "valid")
    n_result = np.sum(result == 4)
    print(f"{ncol} columns - result: {result}")
    print(f"            total: {n_result}")

# 4 columns - result: [[4.]]
#             total: 1
# 5 columns - result: [[4. 4.]]
#             total: 2
# 6 columns - result: [[4. 4. 4.]]
#             total: 3
# 7 columns - result: [[4. 4. 4. 4.]]
#             total: 4
# 8 columns - result: [[4. 4. 4. 4. 4.]]
#             total: 5
# 9 columns - result: [[4. 4. 4. 4. 4. 4.]]
#             total: 6

您可以对不同二维数组上的其他内核重复此实验，您会得到类似的结果。因此，对于您的问题，您需要做的就是对结果等于 4.

的所有情况求和

分机

如果您愿意，您可以从这里很容易地编写适用于任意长度的代码。例如，

class connect_game():
    def __init__(self, n_connect):
        horizontal_kernel = np.ones([1, n_connect], dtype = np.uint8)
        vertical_kernel = np.transpose(horizontal_kernel)
        diag1_kernel = np.eye(n_connect, dtype=np.uint8)
        diag2_kernel = np.fliplr(diag1_kernel)
        self.kernels = [horizontal_kernel, horizontal_kernel.transpose(), diag1_kernel, np.fliplr(diag1_kernel)]
        self.n = n_connect
        
    def winning_moves(self, board, player):
        connections = 0
        for kernel in self.kernels:
            connections += np.sum(convolve2d(board == player, kernel, mode="valid") == self.n)
        return connections



for n in range(2, 7):
    game = connect_game(n)
    print(f"Player 1 has {game.winning_moves(board, 1)} connections of length {n}.")

# Player 1 has 34 connections of length 2.
# Player 1 has 18 connections of length 3.
# Player 1 has 10 connections of length 4.
# Player 1 has 4 connections of length 5.
# Player 1 has 1 connections of length 6.

我如何使用 convolve2d 来计算两个玩家在 connect 4 中达到获胜条件的次数？

How can I use convolve2d to sum the number of times both players achieve the win condition in connect 4?

python

algorithm

scipy