Python connect 4 check win function

Question

I am writing a connect 4 game in which you can choose the size of the board. The game works flawlessly for most board sizes but gives me problems when the board is taller then it is wide. I keep getting index out of range errors and im not sure what I have done wrong. This is what I have right now in terms of my check function as it is the only part giving me issues.

def checkOWin(board):

    boardHeight = len(board)
    boardWidth = len(board[0])
    tile = 'O'
    # check horizontal spaces
    for y in range(boardHeight):
        for x in range(boardWidth - 3):
            if board[x][y] == tile and board[x+1][y] == tile and board[x+2][y] == tile and board[x+3][y] == tile:
                return True

    # check vertical spaces
    for x in range(boardWidth):
        for y in range(boardHeight - 3):
            if board[x][y] == tile and board[x][y+1] == tile and board[x][y+2] == tile and board[x][y+3] == tile:
                return True

    # check / diagonal spaces
    for x in range(boardWidth - 3):
        for y in range(3, boardHeight):
            if board[x][y] == tile and board[x+1][y-1] == tile and board[x+2][y-2] == tile and board[x+3][y-3] == tile:
                return True

    # check \ diagonal spaces
    for x in range(boardWidth - 3):
        for y in range(boardHeight - 3):
            if board[x][y] == tile and board[x+1][y+1] == tile and board[x+2][y+2] == tile and board[x+3][y+3] == tile:
                return True

    return False

Any help or suggestions would be greatly appreciated. Thanks in advance!

Answer 1

Although the successive nested for loops are the obvious solution for win detection, it is a rather slow approach in a language such as python. The problem can actually be assimilated to a convolution operation on the two dimensions of the Connect 4 board, with convolution kernels designed to match horizontal, vertical and diagonal lines of 4 tiles.

A faster approach would thus be to:

1. Create kernels for horizontal, vertical and diagonal win detection.

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]

2. Create a 2D array from your board, in which all of a player's tiles are set to 1, and all empty/opponent tiles are set to 0.

3. Run the board through the convolution operations using Scipy's highly optimized convolve2d function.

4. In the array formed by the convolution output, any "4" indicates that there were 4 connected tiles in the board.

from scipy.signal import convolve2d

def winning_move(board, player):
    for kernel in detection_kernels:
        if (convolve2d(board == player, kernel, mode="valid") == 4).any():
            return True
    return False

This allows for a huge speed-up for detection of the winning conditions which is crucial when implementing tree-search like algorithms on the game tree. I also find this solution to be more elegant and readable.