tree - ミニマックス深さ優先探索ゲームツリー

Question

ナイン・メンズ・モリスのゲーム用のゲームツリーを作りたいです。ノード評価を行うために、ツリーにミニマックスアルゴリズムを適用したいと思います。MinimaxはDFSを使用してノードを評価します。では、最初に特定の深さまでツリーを構築してからミニマックスを適用する必要がありますか、それともツリーの構築と評価のプロセスを再帰的なミニマックスDFSで一緒に実行できますか？

ありがとうArvind

Answer 1

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

実際には、アルファベータ法を同時に適用することもできます。

編集：これはwikiミニマックスからの擬似コードです：

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 α

Answer 2

反復深化深さ優先探索を見ることができます。