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

user_13888307 0
Viewed 49

I am creating a connect four game, the board is a 7x6 board. I want to be able to calculate the number of 4-in-a-row that each player gets. The game does not end when the first player places their first 4-in-a-row. The game will only end when the board is completely full. A possible end state for the game could be as follows:

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

In this case, the score for player 1 would be 10, and the score for player two would be 2. I want to be able to use convolve2d to calculate the 4-in-a-row's for both players. The 4-in-a-row's can be diagonal, horizontal, or vertical. I found this answer by Manuel Faysse: https://stackoverflow.com/a/63991845/13888307

However, this will only count a single occurrence of a 4-in-a-row. I have implemented a function to do this through brute force, but it is rather slow and cumbersome. How can I change the answer given by Manuel to do what I want?

Brute force way:

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
scipy algorithm python
1 Answers

The answer you found does almost all the hard work. All you need to do is change the if statement to a 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

Explanation

There are plenty of sites that explain convolution (e.g. Wikipedia) but to give you some practical intuition, this hopefully helps to show how convolution extends when you have a long series of 1's (in this case):

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

You can repeat this experiment for the other kernels on different 2-d arrays and you'll get similar results. Hence, for your problem all you need to do is sum all the cases where your result is equal to 4.

Extension

You could, if you wanted to, come up with code that would work for arbitrary lengths pretty easily from here. For example,

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.
user_29984470
Related