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
CodePudding user response：
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.