Determining three in a row in Python 2d array

Question

Hey all-

I'm working on a tic-tac-toe game with a M x N board in Python. I'm trying to find an efficient way to determine if a player has won (3 in a row either vertical, horizontal, or diagonal direction.) Most 3x3 implementations of the game just check for all possible winning combinations after each turn. This seems a little extreme with a massive board.

4x4 example: (using 1s and 2s instead of Xs and Os)

board = ([1,0,2,1], [0,0,0,1], [2,2,0,0], [1,0,0,1])
for row in board:
    print row

Thanks- Jonathan

Answer 1

You can look if the player's move closed the game (looking on that row, that column and the 2 diagonals if they ar x checks consecutively), it's o(x) complexity. Let's say you're looking o that row to see if he won. Look to the left how many consecutively checks are and to the right. If the sum of them excedes x he won. You'll do the same on the columns and on the diagonals.

Answer 2

Check for horizontal win

for row in board:
    rowString = ''.join(row)
    if(rowString.count('111') > 2 or rowString.count('222') > 2):
        print "Somebody won"

Check for vertical win

for col in xrange(len(board[0])):
    colString = ""
    for row in board:
        colString = colString.append(row[col])
    if(colString.count('111') > 2 or colString.count('222') > 2):
        print "Somebody won"

Still stumped on diagonals...

Answer 3

If you have a board set up as follows:

board = 
([1,0,2,0],
 [0,1,2,0],
 [0,0,0,0],
 [0,0,0,0])

You can imagine it as x and y coordinates, starting from the upper left hand corner, having downward movement as positive y and rightward movement as positive x. A move at board[3][3] by either player would be a winning move. Using Teodor Pripoae process, we can construct the horizontal, vertical and diagonals around the last move. The horizontal case is easy.

def horizontal(board, y_coord):
    return board[y_coord]

The vertical case requires us to select the x_coord from each row:

def vertical(board, x_coord):
    return [row[x_coord] for row in board]

The diagonal case is a bit trickier. For this first function, it's computing the diagonal that goes from left to right as it goes top to bottom. Distance basically represents the horizontal distance from zero, when y is equal to zero.

def diagonal1(board, x_coord, y_coord):
    length = len(board[0])
    distance = x_coord - y_coord
    if distance >= 0:
        return [y[x] for x, y in enumerate(board) if distance + x <= length]
    else:
        return [y[x] for x, y in enumerate(board) if x - distance >= 0 and x - distance <= length]

This second function computes the diagonal that goes right to left as it goes top to bottom. In this function distance represents the vertical distance from zero as the horizontal distance is at zero.

def diagonal2(board, x_coord, y_coord):
    length = len(board[0])
    distance = y_coord + x_coord
    return [y[distance - x] for x, y in enumerate(board) if distance - x <= length]

Once you have these defined, you just need a way to check if a player has won. Something like this might do:

def game_over(direction, number_to_win, player_number):
    count = 0
    for i in direction:
        if i == player_number:
            count += 1
            if count = number_to_win:
                return True
        else:
            count = 0
    return False

Having written all of this, it seems like this is overkill, unless you have quite large M and N. While it may be more efficient than checking every victory condition, it does construct the entire horizontal, vertical and diagonal directions, rather than just those coordinates surrounding the last move, it isn't as efficient as it could be.

Maybe this is helpful, but it seems like Brian's suggestion to simply remove x's might be better.

Answer 4

Although this approach has a certain appeal, it's probably not especially fast.

# A bogus game with wins in several directions.
board = (
    [1,1,2,1],
    [0,2,1,1],
    [2,2,2,1],
    [1,0,0,1],
)

# A few convenience variables.    
n_rows = len(board)    
lft = [ [0] * i for i in range(n_rows) ]  # [[], [0], [0, 0], [0, 0, 0]]
rgt = list(reversed(lft))

# Create transpositions of the board to check for wins in various directions.
transpositions = {
    'horizontal' : board,
    'vertical'   : zip(*board),
    'diag_forw'  : zip(* [lft[i] + board[i] + rgt[i] for i in range(n_rows)] ),
    'diag_back'  : zip(* [rgt[i] + board[i] + lft[i] for i in range(n_rows)] ),
}

# Apply Jonathan's horizontal-win check to all of the transpositions.
for direction, transp in transpositions.iteritems():
    for row in transp:
        s = ''.join( map(str, row) )
        for player in range(1,3):
            if s.find(str(player) * 3) >= 0:
                print 'player={0} direction={1}'.format(player, direction)

Output:

player=1 direction=diag_back
player=2 direction=diag_forw
player=2 direction=horizontal
player=1 direction=vertical

The idea behind the diagonal transpositions is to shift the rows, using lft and rgt for left and right padding. For example, the diag_forw list looks like this after the padding is added (pad characters are shown as periods, even though zeroes are used in the actual code).

1 1 2 1 . . .
. 0 2 1 1 . .
. . 2 2 2 1 .
. . . 1 0 0 1 

Then we simply transpose that array, using zip(*foo), which allows us to use Jonathan's good idea for finding horizontal wins.