9
\$\begingroup\$

I'm making a simple connect four game that I will eventually extend by creating an AI that the player can play against. Given that AI algorithms are reasonably complex, I find myself wanting to reduce the algorithmic complexity of my win-checker in order to maximize performance once the entire thing is built.

Currently, my win-checker checks all spaces on the board for wins. My win-checking is separated into 3 different functions - one for checking horizontally, another vertically, yet another diagonally. Each algorithm is essentially the same; I've copied the WinChecker class below for your understanding. As you can see, the win checking methods are all very similar with only 2 or 3 lines of code have been changed.

The issue is that as it is designed currently, each time a player places a piece, my program checks roughly 200 possible combinations on the board for a win. If I am to use this same algorithm to help the AI deduce what move to make, I should find myself with a slow AI. However, even if I had plenty of processing power to resolve these problems quickly, I'd like to learn a bit about algorithms and make my program as efficient as possible.

How can I improve my win-checking algorithm to achieve better or maximum computational efficiency?

Any other comments about my code are also welcome.

The whole project is available on Github, if seeing more of the program will help you analyze the code.

class WinChecker:

    def __init__(self, game, board):
        self.game = game
        self.board = board

    def check_for_win(self):
        results = []
        results.append(self.check_win_horizontally())
        results.append(self.check_win_vertically())
        results.append(self.check_win_diagonally())
        try:
            win = results.index(True)
            # if the above statement does not generate a ValueError, then a win exists
            return True
        except ValueError:
            return False

    def check_win_horizontally(self):
        win = False

        for i in range(self.board.rows):
            row = i
            cols = [0, 1, 2, 3]
            while not win:
                try:
                    # seq will represent the current 4 squares being examined
                    seq = []
                    for i in range(len(cols)):
                        # append current 4 squares to seq list
                        seq.append(self.board.board[row][cols[i]])
                    if self.check_equal(seq):
                        return True
                    else:
                        # increment each value in cols, this is how the horizontal
                        # win checking progresses from left to right
                        for i in range(len(cols)):
                            cols[i] += 1
                        continue
                except IndexError:
                    # we've hit the end of this row, break the loop and move to the next row
                    break
        return win

    def check_win_vertically(self):
        win = False

        for i in range(self.board.cols):
            col = i
            rows = [0, 1, 2, 3]
            while not win:
                try:
                    # seq will represent the current 4 squares being examined
                    seq = []
                    for i in range(len(rows)):
                        # append current 4 squares to seq list
                        seq.append(self.board.board[rows[i]][col])
                    if self.check_equal(seq):
                        return True
                    else:
                        # increment each value in rows, this is how the horizontal
                        # win checking progresses from top to bottom
                        for i in range(len(rows)):
                            rows[i] += 1
                        continue
                except IndexError:
                    # we've hit the end of this col, break the loop and move to the next col
                    break

        return win

    def check_win_diagonally(self):
        win = False

        for i in range(self.board.cols):
            col = i
            cols = [col, col+1, col+2, col+3]
            rows = [0, 1, 2, 3]
            while not win:
                try:
                    # seq will represent the current 4 squares being examined
                    seq = []
                    for i in range(len(rows)):
                        # append current 4 squares to seq list
                        seq.append(self.board.board[rows[i]][cols[i]])
                    if self.check_equal(seq):
                        return True
                    else:
                        # increment each value in rows, this is how the diagonal
                        # win checking progresses from top to bottom
                        for i in range(len(rows)):
                            rows[i] += 1
                        continue
                except IndexError:
                    # we've hit the end of this col, break the loop and move to the next col
                    break

        return win

    def check_equal(self, lst):
        return lst[1:] == lst[:-1] if lst[0] != self.board.NONE else False
\$\endgroup\$
6
\$\begingroup\$

Instead of checking the entire board each time, write a function which checks if placing a piece on a given field will result in a win. This can then be used both for checking whether the last actual piece played was a winning piece, or when implementing the AI whether this is a good place to place it.

A simplistic approach to an AI version, would be to let this win function return how many pieces of the specific kind is placed in this row, and whether there is room for the remaining pieces to be placed. That is the function could return max of how many pieces of your kind is in the row (and if its 4 you win), and how many available spaces are there within a reach of 4 pieces.

Finally when contemplating which move to make next, you don't need to check all places, as the pieces drop to the bottom, so you only need to check one for each column.

\$\endgroup\$
2
\$\begingroup\$
  • Win checking looks too complicated. Assuming that the number of columns is accessible as self.board.cols, I'd rather go for something like

        def check_win_horizontally(self):
            for row in range(self.board.rows):
                for col in range(self.board.cols - 4):
                    if self.check_equal(self.board.board[row][col:col+4])
                        return True
            return False
    
  • Regarding performance, it doesn't make sense to test all possible quartets; most of them do not ever change. You need only test viable candidates, that is those which include a last played peg.

\$\endgroup\$
2
\$\begingroup\$

It is probably not worth the effort, as the board is small, and 4 is itself a smallish number, but efficiency wise, you want to minimize duplicate checks. Consider this alternative approach to checking a single row for a win:

def is_row_a_winner(self, row):
    consecutive_items = 0
    last_seen_item = None
    for item in self.board.board[row]:
        if item == self.board.NONE:
            consecutive_items = 0
        elif item == last_seen_item:
            consecutive_items += 1
        else:
            consecutive_items = 1
        last_seen_item = item
        if consecutive_items == 4:
            return True
    return False

This is only checking each position of the row once, rather than 4 times, so the algorithm is inherently more efficient.

If rather than scanning row by row, you want to go with scanning from the last entered position, you could go with something like:

def is_position_a_winner_row(self, row, col):
    item = self.board.board[row][col]
    cols = len(self.board.board[0])
    if item == self.board.NONE:
        return False
    consecutive_equals = 1
    for delta in (+1, -1):
        next_col = col + delta
        while 0 <= next_col < cols:
            if self.board.board[row][next_col] == item:
                consecutive_equals += 1
            else:
                break
            next_col += delta
            if consecutive_equals == 4:
                return True
    return False

We can take the abstraction a step higher, to avoid repeating ourselves, and have a single function efficiently check for a win from a single location:

def is_position_a_winner(self, row, col):
    item = self.board.board[row][col]
    rows = len(self.board.board)
    cols = len(self.board.board[0])
    if item == self.board.NONE:
        return False
    for delta_row, delta_col in [(1, 0), (0, 1), (1, 1), (1, -1)]:
        consecutive_items = 1
        for delta in (1, -1):
            delta_row *= delta
            delta_col *= delta
            next_row = row + delta_row
            next_col = col + delta_col
            while 0 <= next_row < rows and 0 <= next_col < cols:
                if self.board.board[next_row][next_col] == item:
                    consecutive_items += 1
                 else:
                     break
                 if consecutive_items == 4:
                     return True
                 next_row += delta_row
                 next_col += delta_col
    return False

You would have to do the timings, but as I said originally, there is a good chance that using Python built-in methods, e.g. list[:-1] == list[1:], ends up being faster than what I have outlined here, even though the approach is algorithmically less efficient. But that's a whole different story...

\$\endgroup\$
2
\$\begingroup\$

Really, you only need one function:

def does_square_contain_win(i, j)

At each square, check 4 masks:

   (i,j)
   ▼  
---*--- ---*--- ---**** ---*---
----*-- --*---- ------- ---*---
-----*- -*----- ------- ---*---
------* *------ ------- ---*---
  • right_diag: [[i,j], [i-1,j+1], [i-2,j+2], [i-3,j+3]]
  • left_diag: [[i,j], [i-1,j-1], [i-2,j-2], [i-3,j-3]]
  • right: [[i,j], [i,j+1], [i,j+2], [i,j+3]]
  • down: [[i,j], [i-1,j], [i-2,j], [i-3,j]]

To do that, write a helper function that picks out the values from the mask, given a starting cell (i,j) and tells you if they all contain the same color chip. If the mask contains any out of bound index, it automatically returns false.

Your main function -- the one that tells you if there is a win -- simply loops every board element and calls does_square_contain_win on it. The entire implementation should be 10-15 lines of code.

\$\endgroup\$
  • \$\begingroup\$ Hmmm... So I'm trying to understand your answer. You're saying that I should call this method, as you've defined it, each time someone places a piece on the board? Thus, this method would look at the piece that was just placed on the board, check all directions diagonally, vertically, and horizontally from that spot to see if there's a win? That makes sense, but it seems more complex than that. However, you've also made me realize that my current algorithm doesn't check for your left_diag case - a glaring omission! \$\endgroup\$ – jdogg Dec 5 '15 at 4:38
  • \$\begingroup\$ I was actually answering the question of how, given an entire board, to determine if there is a win on it. That requires checking all i,j pairs, ie, all board positions, using the method I suggested. It's related to your comment though. As the game progresses, and chips fall one at a time, you only need to check the position of the new chip, since you know the previous board had no win, and if the newly dropped chip created a winning line, that line must contain the chip. \$\endgroup\$ – Jonah Dec 5 '15 at 5:06
  • \$\begingroup\$ However, note that if you use my method as the game progresses, the 4 lines I suggest will not suffice, even though they do suffice if you check the entire board. If you check after each new chip, and only test the position of the new chip, you'll also have to include masks for "left horizontal", "diag up left", and "diag up right", as well as account for the chance that you dropped the winning chip in the middle of a 4 in a row, rather than an endpoint. Since checking the entire board will so fast anyway, I'd prefer to do that every time, since the algorithm is simpler. \$\endgroup\$ – Jonah Dec 5 '15 at 5:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.