2

私はオセロ プレーヤーを作成しており、アルファ ベータ プルーニングを使用してミニマックス アルゴリズムを実装しています。それから、私はオンラインで最高のものについてたくさんの調査を行い、それらがすべて使用している「ネガマックス」アルゴリズムについて聞き続けました. ほとんどの人は、ネガマックスはミニマックスよりも速いと考えているようです (最小プレーヤーと最大プレーヤーが切り替わらないからだと思いますか?)。

ネガマックスを使用するとどれだけ高速になるかについての洞察と、ミニマックスコードをネガマックスアルゴリズムに変換する方法に関するヒントやコードを知っているかどうか疑問に思っていました。

これが私のミニマックスアルゴリズムです：

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

アルファ ベータの剪定について質問する回答があったので、以下に示します。

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

ミニマックスを実装したのでそれで十分だと思いますが、ミニマックスで最も重要な最適化を実装する必要があります。これは、コードを単純に変更するだけで、速度が大幅に向上します。

編集：-

negamaxを実装できるようにalpha-betaを使用していることに気づきましたが、切り替えないという考えは正しくありませんが、minimaxのコードを削減します（速度の大幅な改善は疑わしいです）。ここでの考え方は、1 人のプレーヤーの移動のポイントは常に他のプレーヤーの -ve ですが、max(a,b) = -min(-a,-b) を計算できる同じ大きさであるということです。

ここでの簡単な翻訳は次のとおりです:-

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

これらは、negamax を使用してミニマックスを評価するための行のみです。

ここでは、min と max を交互に評価する必要はありませんが、minplayer に与えられるスコアが常に正の player よりも負であるという事実は、常に max を評価して正しいスコアを得ることができるという事実で十分です。

ノート：-

これは速度の点で重要な最適化ではありませんが、コードをシンプルで読みやすくするので価値がありますが、残念ながら、コードを negamax に変換するには大量のコードを消去する必要があるため、そうしないことをお勧めします。

于 2014-06-10T06:57:14.043 に答える