Python: List not searching diagonally

Question

I am implementing a Python version of the game Othello / Reversi. However, my algorithm seems to be having trouble when searching in the southwest direction.

Here are some important functions to understand how my current code works:

def _new_game_board(self)->[[str]]:
    board = []
    for row in range(self.rows):
        board.append([])
        for col in range(self.columns):
            board[-1].append(0)
    return board
def _is_valid_position(self, turn:list)->bool:
        '''return true if the turn is a valid row and column'''
        row = int(turn[0]) - 1
        column = int(turn[1]) - 1
        if row >= 0:
            if row < self.rows:
                if column >= 0:
                    if column < self.columns:
                        return True
        else:
            return False


def _is_on_board(self, row:int, col:int)->bool:
    '''returns true is coordinate is on the board'''
    if row >=0:
        if row < self.rows:
            if col >=0:
                if col < self.columns:
                    return True




def _searchNorthEast(self)->None:
    '''Search the board NorthEast'''
    print("NorthEast")
    row = self.move_row
    column = self.move_column
    should_be_flipped = list()
    row += 1
    column -= 1
    if self._is_on_board(row, column):
         print("column searching NorthEast on board")
         if self.board[row][column] == self._opponent:
             should_be_flipped.append([row, column])
             while True:
                row += 1
                column -= 1
                if self._is_on_board(row, column):
                    if self.board[row][column] == self._opponent:
                        should_be_flipped.append([row, column])
                        continue
                    elif self.board[row][column] == self.turn:
                        self._to_be_flipped.extend(should_be_flipped)
                        break
                    else:
                        break
                else:
                    self._to_be_flipped.extend(should_be_flipped)
    else:
        pass

    def _searchSouthWest(self)->None:
    '''Search the board SouthWest'''
    print("in SouthWest")
    row = self.move_row
    column = self.move_column
    should_be_flipped = list()
    row -= 1
    column += 1
    if self._is_on_board(row, column):
         print("column searching SouthWest on board")
         if self.board[row][column] == self._opponent:
             should_be_flipped.append([row, column])
             while True:
                row -= 1
                column += 1
                if self._is_on_board(row, column):
                    if self.board[row][column] == self._opponent:
                        should_be_flipped.append([row, column])
                        continue
                    elif self.board[row][column] == self.turn:
                        self._to_be_flipped.extend(should_be_flipped)
                        break
                    else:
                        break
                else:
                    self._to_be_flipped.extend(should_be_flipped)
    else:
        pass

def _move_is_valid(self, turn:list)->bool:
    '''Verify move is valid'''
    self._to_be_flipped = list()
    self._opponent = self._get_opposite(self.turn)
    if self._is_valid_position(turn):
        self.move_row = int(turn[0]) - 1
        self.move_column = int(turn[1]) - 1
        self._searchRight()
        self._searchLeft()
        self._searchUp()
        self._searchDown()
        self._searchNorthWest()
        self._searchNorthEast
        self._searchSouthEast()
        self._searchSouthWest()
        if len(self._to_be_flipped) > 0:
            return True
    else:
         return False

Now let's say the current board looks like the following:

. . . .
W W W .
. B B .
. B . .

Turn: B

and the player makes a move to row 1 column 4, it says invalid because it does not detect the white piece in row 2 column 3 to be flipped. All my other functions are written the same way. I can get it to work in every other direction except in this case.

Any ideas why it is not detecting the piece in this diagonal direction?

Answer 1

Don't Repeat Yourself. The _search* methods are extremely redundant which makes it difficult to see that the signs in

row -= 1
column += 1

are correct. Since you've given only two directions (NE, SW) and no documentation of the board orientation, I cannot tell if the signs agree with the board layout or even agree with themselves.

The _search* methods are also too long and should be divided into multiple functions, but that's a secondary concern.

Answer 2

I agree with msw about not repeating stuff. It is tempting to go ahead and do what you can once you see it, but generalizing will save you the headaches of debugging.

Here is some pseudocode that should give the general idea. I might not be able to finagle working with your code, but hopefully this shows how to reduce repetitive code. Note it doesn't matter if -1 is up or down. The board class is simply a 2x2 array of (open square/player 1's piece/player 2's piece,) along with whose turn it is to move.

# x_delta and y_delta are -1/0/1 each based on which of the up to 8 adjacent squares you are checking. Player_num is the player number.
def search_valid(x_candidate, y_candidate, x_delta, y_delta, board, player_num):
    y_near = y_candidate + y_delta
    x_near = x_candidate + x_delta
    if x_near < 0 or x_near >= board_width:
        return False
    if y_near < 0 or y_near >= board_width:
        return False # let's make sure we don't go off the board and throw an exception
    if board.pieces[x_candidate+x_delta][y_candidate+y_delta] == 0:
         return False #empty square
    if board.pieces[x_candidate+x_delta][y_candidate+y_delta] == player_num:
         return False #same color piece
    return True #if you wanted to detect how many flips, you could use a while loop

Now a succinct function can loop this search_valid to see whether a move is legal or not e.g.

def check_valid_move(x_candidate, y_candidate, board, player_num):
    for dx in [-1, 0, 1]:
        for dy in [-1, 0, 1]:
            if not x and not y:
                continue # this is not a move. Maybe we don't strictly need this, since board.pieces[x_candidate+x_delta][y_candidate+y_delta] == player_num anyway, but it seems like good form.
            if search_valid(x_candidate, y_candidate, dx, dy, board, player_num):
                return True
    return False   

A similar function could actually flip all the opposing pieces, but that's a bit trickier. You'd need a while function inside the for loops. But you would not have to rewrite code for each direction.