CODEWITHSUNDEEP
python
Matthew Hanson
Matthew Hanson

Reputation: 331

How to implement the function that checks for horizontal, vertical and diagonal lines of 4 tiles?

I am writing a Connect Four 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 I'm 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

Upvotes: 11

Views: 26280

Answers (3)

grgthemighty
grgthemighty

Reputation: 41

I think the problem lies in the conditional.

Here is a sample input that should be similar to what OP is using:

board = [['_','_','_','_','_','_','_'],
         ['_','_','_','_','_','_','_'],
         ['_','_','_','X','_','_','_'],
         ['_','_','_','O','_','_','_'],
         ['_','X','X','O','O','O','O'],
         ['X','X','X','O','O','X','O']]

I've reworked the conditional to be:

  for x in range(boardWidth):
    for y in range(boardHeight):
      try:
        if board[y][x] == tile and board[y][x+1] == tile and board[y][x+2] == tile and board[y][x+3] == tile:
          return True
      except IndexError:
        next

We have 6 different lists stored in the board list. The y comes first when accessing the board because it first tells us which list of those 6 we need to use, moving us up or down in the board list. Now the x index moves us within whichever y list we have accessed.

The try and except allow you to remove the for x in range(boardWidth - 3) because if an index error is received, we know we've reached the edge of the game board and cannot meet the win condition. So we move on to the next point to test.

Upvotes: 4

Manuel Faysse
Manuel Faysse

Reputation: 753

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.

    Illustrated example of convolution operation

    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.

Upvotes: 40

SuperBiasedMan
SuperBiasedMan

Reputation: 9969

You've just mixed up your dimensions, you should set them this way:

def checkOWin(board):
    boardHeight = len(board[0])
    boardWidth = len(board)

Because when you refer to board[x], that's counting the number of lists in the board, and when you refer to board[x][y] that's just referring to the length of one specific row in the board. 

if board[x][y] == tile and board[x+1][y] == tile and board[x+2][y] == tile and board[x+3][y] == tile:

When I flipped those values the function ran without errors.

Upvotes: 7

Related Questions