2

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.

aschultz
  • 1,658
  • 3
  • 20
  • 30
Matouš Dzivjak
  • 71
  • 2
  • 5

1 Answers1

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.

Dr Xorile
  • 967
  • 1
  • 7
  • 20
  • The board scoring is hardcoded base on some table I have found on internet: – Matouš Dzivjak Oct 21 '16 at 05:23
  • ` score_board = [[99, -8, 8, 6, 6, 8, -8, 99], [-8, -24, -4, -3, -3, -4, -24, -8], [8, -4, 7, 4, 4, 7, -4, 8], [6, -3, 4, 0, 0, 4, -3, 6], [6, -3, 4, 0, 0, 4, -3, 6], [8, -4, 7, 4, 4, 7, -4, 8], [-8, -24, -4, -3, -3, -4, -24, -8], [99, -8, 8, 6, 6, 8, -8, 99]]` – Matouš Dzivjak Oct 21 '16 at 05:26
  • I have found my mistake. When I was making new node - making some move, I just placed it in but didnt flipped the stones that should have been flipped, now it works nice and smooth. Thank you anyway – Matouš Dzivjak Oct 21 '16 at 05:43