0

木

こんにちは、次のコードの例としてチェスを使用して、アルファ ベータ プルーニング アルゴリズムを理解しようとしています。

def minimax(position, depth):
"""Returns a tuple (score, bestmove) for the position at the given depth"""
    if depth == 0 or position.is_checkmate() or position.is_draw():
        return (position.evaluate(), None)
    else: 
        if position.to_move == "white":
            bestscore = -float("inf")
            bestmove = None
            for move in position.legal_moves():
                new_position = position.make_move(move)
                score, move = minimax(new_position, depth - 1)
                if score > bestscore: # white maximizes her score
                    bestscore = score
                    bestmove = move
            return (bestscore, bestmove)
        else:
            bestscore = float("inf")
            bestmove = None
            for move in position.legal_moves():
                new_position = position.make_move(move)
                score, move = minimax(new_position, depth - 1)
                if score < bestscore: # black minimizes his score
                    bestscore = score
                    bestmove = move
            return (bestscore, bestmove)

私が入手したブログへのリンクは次のとおりです: LINK (強調表示された構文が好きな場合は、リンクからコードを表示できます)

私が理解していないのは、アルファベータの剪定では、ツリーの上位に移動すると、アルファ変数とベータ変数の値が時々変化する必要があるということです。私の問題を説明する写真を添付し​​ました-手順1）、2）、および3）は理解していますが、4）の手順はわかりません。4) ステップは図のように見えるはずですが、そのステップで値が変化するコードで何が起こっているのかわかりません。私はコードを注意深くたどりましたが、何らかの理由で 4) のステップで a = 5 と b = 5 になってしまいました。

4

1 に答える 1

0

あなたのコメントの推論は正しくないと思います。あなたのコメントから、検索がツリーの右の枝に行き、次に木の左の枝に戻ると暗黙のうちに信じていますが、これはもちろん正しくありません。

ツリーの左側の枝にある (5) 非葉ノードでは、検索はその下のノード (葉ノード (5) および (4)) のみを訪問したため、ロジックは間違っています。ツリーの右側のブランチであるため、値がどうなるかわかりません. したがって、あなたのコメント

「最大ノード（正方形）があり、選択は5（左側）と4（右側）の間で行われます。そして、それらの上のMAXノードはより大きな値を必要とするため、アルファを5に設定する必要があると思います.下限です。」は正しくありません。

ルート ノード (最大ノード) だけが右側の値 4 を知っているため、これは間違っていますが、ステップ 4 の後にのみ実行できます。実際、検索の最後にのみ実行できます。ツリーの右の枝が訪問されます。

于 2015-01-06T02:39:16.327 に答える