ミニマックス深さ優先探索ゲーム木

Question

私はナイン・メンズ・モリスゲーム用のゲームツリーを構築したいです。私は、ノードの評価を行うための木の上にミニマックスアルゴリズムを適用したいです。ミニマックスは、ノードを評価するために、DFSを使用しています。だから私は、所定の深件まで最初のツリーを構築する必要があり、その後、ミニマックスを適用したり、木や評価を構築するプロセスは、再帰的なミニマックスDFS？

で一緒に発生する可能性があります

ありがとう アービンド

Answer 1

あなたは深さ優先探索を深め反復を見てみることができます。

Answer 2

はいあなたは再帰的なミニマックスで同時に構築し、評価することができます。
それはメモリ空間を節約できますので、それは良いアプローチです。

実際に、あなたもアルファベータ同時にの剪定を適用することができます。

の編集はこちらから擬似コードがあるウィキミニマックスする ：

function integer minimax(node, depth)
    if node is a terminal node or depth == 0:
        return the heuristic value of node
    α = -∞
    for child in node: # evaluation is identical for both players 
        α = max(α, -minimax(child, depth-1))
    return α

我々は（おそらく）各ノードにゲーム/ボードの状態を保存するので、

、我々は埋め込むことができます ゲーム状態の作成
ミニマックスアルゴリズムで、すなわち

function integer play_minimax(node, depth)
    if node is a terminal node or depth == 0:
        return the heuristic value of node
    α = -∞
    LOOP: # try all possible movements for this node/game state
        player = depth mod 2
        move = make_game_move(node, player)
        break if not any move
        α = max(α, -play_minimax(move, depth-1))
    return α