Python Reversi/Othello AI working under 1 second

Question

---

In an recent assignment we were given a task to create Reversi/Othello AI which can make a valid move under 1s. I have started with a simple bot, which takes all available moves and scores them based on board with values. On the second bot I added also mobility value to the ranking. Now I have made a bot which searches with minmax 3 moves ahead and evaluates the moves based on score. My problem is, it gets beaten by the score/mobility one step ahead bot. Is it possible or did I code the AI wrong? Is it because I am searching only 3 steps ahead?

My bot starts with this:

possible_moves = self.get_available_moves(board,self.my_color,self.opponent_color)
for [x, y] in possible_moves:
    new_board = self.make_board_copy(board)
    new_board[x][y] = self.my_color
    new_alpha = self.minmax(new_board,1,alpha,beta)
    if new_alpha > alpha:
        alpha = new_alpha
        best_move = [x,y]

And then goes to this:

    def minmax(self, board, depth, alpha, beta):
    # END NODE
    if depth == self.max_depth:
        return self.evaluate(board)
    else:
        # MAX NODE = MY MOVE
        if depth % 2 == 0:
            possible_moves = self.get_available_moves(board,self.my_color,self.opponent_color)
            for [x, y] in possible_moves:
                new_board = self.make_board_copy(board)
                new_board[x][y] = self.my_color
                new_alpha = self.minmax(new_board,depth+1,alpha,beta)
                if new_alpha > alpha:
                    alpha = new_alpha
                if alpha > beta:
                    return alpha
            return alpha
        # MIN NODE
        else:
            possible_moves = self.get_available_moves(board,self.my_color,self.opponent_color)
            for [x,y] in possible_moves:
                new_board = self.make_board_copy(board)
                new_board[x][y] = self.my_color
                new_beta = self.minmax(new_board, depth + 1, alpha, beta)
                if new_beta < beta:
                    beta = new_beta
                if beta < alpha:
                    return beta
            return beta

I checked the code many times and still can't figure out if my code is bad or if the AI is getting beaten because it does not search deep enough.

Answer 1

If it's using the same evaluation, I think it's unlikely that the lower depth search beats the higher depth search, and probably impossible.

Can you explain the alpha and beta, and the minmax functions a bit more, or show more code? Are both alpha and beta always positive?

I think there might be something wrong in your odd node function:

if new_beta < beta:
    beta = new_beta
if beta < alpha:
    return beta

If alpha and beta are both positive values, then you want the first line to be

if new_beta > beta:

It also depends how your score the board positionally. That's obviously very important - I don't know if your AI is trying to learn this from playing, or if you've given it an evaluation based on various positional factors and judgements.