将Minimax转换为Negamax（python） [英] Converting Minimax to Negamax (python)

问题描述

我正在制作Othello播放器，并实现了带有alpha-beta修剪功能的minimax算法。然后，我对在线上的最佳算法进行了大量研究，并不断了解它们都使用的 negamax算法。似乎大多数人认为negamax比minimax快（我认为是因为它不能在min和max player之间切换？），所以我想将minimax算法转换为negamax，如果不太困难的话。

我想知道人们是否对使用negamax有多快有任何见识，以及关于如何将我的minimax代码转换为negamax算法的任何技巧或代码，这将不胜感激！ / p>

这是我的minimax算法：

  def minimax（Board，maximizingPlayer，深度，计数）：
＃如果maximizingPlayer：播放器，opp = Board.player，Board.opp，最大化播放器有'B'并最小化'W'
 
 else：播放器，opp =播放器.opp，Board.player 
 
 Moves_list = Board.get_moves_list（player，opp）
 best_move =（-1，-1）
 
＃基本情况
 if（depth == 0或moves_list == []）：
 best_score，奇偶校验，移动性，稳定性= Board.evaluate（）
 best_move =（-1，-1）
返回best_score，best_move，计数
 
＃如果maximizingPlayer：
，则使玩家
最大化：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 
＃最小化玩家
其他：
 best_score = float（ inf）
用于move_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 =移动
 
返回best_score，best_move并计数
  

自从我收到有关我的Alpha-beta修剪问题的答复以来，这是：

  def字母a（棋盘，maximizingPlayer，深度，计数，alpha，beta）：
＃最大化玩家具有 B并最小化 W 
（如果最大化）：玩家，opp = Board.player，Board.opp 
 else：玩家，opp = Board.opp，Board.player 
 
 moveslist = Board.get_moves_list（player，opp）
 best_move =（-1，-1）
 
＃基本情况
 if（depth == 0或moves_list == []）：
 best_score，奇偶性，移动性，稳定性= Board.evaluate（）
 best_move =（-1，-1）
 return best_score，best_move，count 
 
＃最大化玩家
如果最大化玩家：
 best_s core = float（-inf）
用于move_list中的移动：
 new_board = deepcopy（Board）
 new_board.play_legal_move（move [0]，move [1]，player，opp， flip = True）
 the_score，the_move，count =字母a（new_board，False，depth-1，count + 1，alpha，beta）
 if（the_score> alpha）：
 alpha = the_score 
 best_move =移动
如果beta< = alpha：打破
 
返回alpha，best_move，计算
＃最小化玩家
 else：
 best_score = float（ inf）
在moves_list中移动：
 new_board = deepcopy（Board）
 new_board.play_legal_move（move [0]， move [1]，播放器，opp，flip = True）
 the_score，the_move，count =字母a（new_board，True，depth-1，count + 1，alpha，beta）
 if（the_score< beta）：
 beta = the_score 
 best_move =移动
如果beta <== alpha：打破
 
返回beta，best_move，计算
  

解决方案

我认为您已经实现了minimax，这已经足够了，但是您需要实现minimax中最重要的优化是< a href = http://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning rel = nofollow> alpha-beta 修剪，这是对代码的简单更改，具有非常重要的意义

编辑：-

-beta，因此您可以实现negamax，但是您认为它不会切换是不正确的，但是会减少minimax的代码（我怀疑速度的显着提高）。这里的想法是，一个玩家的移动点数始终是另一玩家的-ve，但幅度相同，因此您可以计算max（a，b）= -min（-a，-b）。

这里的简单翻译是：-

 分数= -negamax（ depth-1，-player）
 best = max（得分，最佳）
  

这些是仅使用negamax来评估minimax的行

在这里，您不需要交替评估min和max，但是给minplayer的分数始终为正数玩家的负数就足够了，您可以始终评估max以获得正确的分数。

注意：-

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

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

解决方案

I think now that you have implemented minimax it is good enough but you need to implement the most important optimization in minimax that is alpha-beta pruning which would be a simple change to your code with very significant improvement in speed.

EDIT:-

Noticed that you have used alpha-beta so you can implement negamax but your notion that it doesnt switch is not correct but it reduces the code for minimax ( i doubt significant improvement in speed) . The idea here is that the points for a move for one player is always -ve of the other player but same magnitude that allows you to calculate max(a,b) = -min(-a,-b).

Simple translation here is :-

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

These are only lines to evaluate minimax using negamax

Here you dont need to evaluate min and max alternatively but the fact that the scores given to minplayer are always negative of positive player is sufficient so that you can always evaluate max to get correct score.

Note:-

This is not significant optimization in terms of speed but makes code simple and readable so its worth it but unfortunately you need erase alot of code to convert your code to negamax so i advice not to.

这篇关于将Minimax转换为Negamax（python）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！