2

I'm making an Othello player, and implemented a minimax algorithm with alpha-beta pruning. Then I did a bunch of research on the best ones online and keep hearing about a "negamax" algorithm that they all use. It seems like most people think negamax is faster than minimax (i think because it doesn't switch between min and max player?), so I'd like to turn my minimax algorithm into negamax if that's not too difficult.

I was wondering if people had any insight on how much faster using negamax is, and any tips or code on how to turn my minimax code into a negamax algorithm that'd be appreciated!

Here's my minimax algorithm:

def minimax(Board, maximizingPlayer, depth, count):
     # maximizing player has 'B' and minimizing 'W'
     if maximizingPlayer: player, opp = Board.player, Board.opp
     else: player, opp = Board.opp, Board.player

     moves_list = Board.get_moves_list(player, opp)
     best_move = (-1,-1)

     # base case
     if ( depth==0 or moves_list == [] ):
         best_score, parity, mobility, stability = Board.evaluate()
         best_move = (-1, -1)
         return best_score, best_move, count

     # maximizing player
     if maximizingPlayer:
           best_score = float("-inf")
           for move in moves_list:
                new_board = deepcopy(Board)
                new_board.play_legal_move(move[0], move[1], player, opp, flip=True)
                the_score, the_move, count = minimax(new_board, False, depth-1, count+1)
                best_score = max(best_score, the_score)
                if (the_score == best_score):
                    best_move = move

           return best_score, best_move, count
     # minimzing player
     else:
           best_score = float("inf")
           for move in moves_list:
                new_board = deepcopy(Board)
                new_board.play_legal_move(move[0], move[1], player, opp, flip=True)
                the_score, the_move, count = minimax(new_board, True, depth-1, count+1)
                best_score = min(best_score, the_score)
                if (the_score == best_score):
                    best_move = move

           return best_score, best_move, count

Since I got a response asking about my Alpha-beta pruning, here is that:

def alphabeta(Board, maximizingPlayer, depth, count, alpha, beta):
     # maximizing player has 'B' and minimizing 'W'
     if maximizingPlayer: player, opp = Board.player, Board.opp
     else: player, opp = Board.opp, Board.player

     moves_list = Board.get_moves_list(player, opp)
     best_move = (-1,-1)

     # base case
     if ( depth==0 or moves_list == [] ):
         best_score, parity, mobility, stability = Board.evaluate()
         best_move = (-1, -1)
         return best_score, best_move, count

     # maximizing player
     if maximizingPlayer:
           best_score = float("-inf")
           for move in moves_list:
                new_board = deepcopy(Board)
                new_board.play_legal_move(move[0], move[1], player, opp, flip=True)
                the_score, the_move, count = alphabeta(new_board, False, depth-1, count+1, alpha, beta)
                if (the_score > alpha):
                    alpha = the_score
                    best_move = move
                if beta <= alpha: break

           return alpha, best_move, count
     # minimzing player
     else:
           best_score = float("inf")
           for move in moves_list:
                new_board = deepcopy(Board)
                new_board.play_legal_move(move[0], move[1], player, opp, flip=True)
                the_score, the_move, count = alphabeta(new_board, True, depth-1, count+1, alpha, beta)
                if (the_score < beta):
                    beta = the_score
                    best_move = move
                if beta <= alpha: break

           return beta, best_move, count
4

1 回答 1

5

我认为现在您已经实现了 minimax，它已经足够好了，但是您需要在 minimax 中实现最重要的优化，即alpha-beta剪枝，这将是对您的代码的简单更改，并显着提高速度。

编辑：-

注意到您使用了 alpha-beta，因此您可以实现 negamax，但您认为它不切换的想法是不正确的，但它减少了 minimax 的代码（我怀疑速度是否有显着提高）。这里的想法是，一个玩家的移动点始终是另一个玩家的-ve，但相同的大小允许您计算 max(a,b) = -min(-a,-b)。

这里的简单翻译是：-

score = -negamax(depth-1,-player)
best = max(score,best)

这些只是使用 negamax 评估 minimax 的行

在这里，您不需要交替评估 min 和 max，但给予 minplayer 的分数始终为负数的事实足以让您始终评估 max 以获得正确的分数。

笔记：-

这在速度方面不是显着的优化，但使代码简单易读，因此值得，但不幸的是，您需要删除大量代码才能将代码转换为 negamax，所以我建议不要这样做。

于 2014-06-10T06:57:14.043 回答