[AI] Game Search

ゲーム定義

参加者2名

ゼロとゲーム:1つの勝利、もう1つの失敗(ウィンウィンなし)

シリーズ

ここではTic-Tac-Toeゲームを例に,ゲームアルゴリズムをまとめる.

人の参加者はMaxで、もう一人の参加者はMinで、ゲームはいつもMaxが先に始まります.

いつも相手に最善の方法があると仮定しています.

MiniMax Algorithm

b 1、b 2、c 1、c 2は端末ノードである.上の図のようにゲームツリーが完成しました.各ノードの評価値(スリープ値)が大きいほどMAXに有利であり、評価値が低いほどMINに有利である.
端末ノードの評価が終了すると,底から遡及する.この場合、MINの場合は評価値の低いノードを選択した方が良く、MAXの場合は評価値の高いノードを選択した方が良い.したがって、次のように選択します.

MINについては、b 1およびb 2のb 1の評価値がより小さいので、3、c 1およびc 2のc 1の評価値がより小さいので、2を選択する.逆にMAXの立場ではa 1とa 2の方がa 1の評価値が大きいので3を選択する.
このアルゴリズムをMiniMaxアルゴリズムと呼ぶ.

Pseudo Code

function minimax(node, depth, player)
    if depth == 0 or leaf node:
        return 해당 node의 heuristic 값
    if player == 'max':
        value = -(무한대)
        for each child of node:
            value = max(value, minimax(child, depth-1, 'min')
        return value
    else:
        value = +(무한대)
        for each child of node:
            value = min(value, minimax(child, depth-1, 'max')
        return value

現在のノードから可能なサブノードを生成し、各ノードに対してminimax関数を再帰的に呼び出して、自身の最適な移動を選択します.(最大参加者はより大きな値を選択し、最小参加者はより小さな値を選択します)
MiniMaxアルゴリズムは完全な深さ優先探索を提供する.従って、ツリーの最大深さがmであり、各ノードが作成できるサブノード数がbである場合、時間複雑度はO(b^m)である.

MiniMaxアルゴリズムをTic-Tac-Toeに適用

各ノードが回路基板の状態を表すと仮定する.

マザーボードのステータスがMAX参加者にとって有利である場合、ノードの評価値は+1である.

MIN参加者にとって有利である場合、ノードの評価値は−1である.

の場合、評価値は0です.

Alpha-Beta Pruning

前述したように,MiniMaxアルゴリズムの時間的複雑さは指数関数的に増大し,これは問題である.これを補うためにα−βトリムが出現した.

上図に示すように、alpha−beta剪断はminimaxアルゴリズムにおいて最終結果に影響を及ぼさない分岐を除去するように動作する.
(d)Cノード上で最初のサブノードのみをチェックして停止するのは、ルートノードAがMAX値を取得しなければならず、現在の最大値3より大きい値があればリフレッシュし、3より小さい値があれば無視できるためである.CノードはMIN値を得る必要があるため、サブノードの最小値を得る必要があり、評価値が2より大きいサブノードがある場合、Cは評価値として2を得る.Aの場合、Cは常に2未満の値を有するので、Cの残りのサブノードは考慮されない.
Rule

Alpha値はMAXノードのみで更新されます.

Beta値はMINノードでのみ更新されます.

Alpha>=Betaの場合、トリミングを行います.(サブノードは移動しません.)

別の例を下図に示します.(下から練習についていく)

Properties

の実行は最終結果に影響しません.

Prunningの効果はサブノードの検出順序によって影響される.たとえば、最後にナビゲートしたサブノードがAlpha>=Betaの条件を満たす場合、最終的にはすべてのサブノードにナビゲートされます.したがって,最悪の場合,MiniMaxアルゴリズムと同様の時間的複雑さが生じる可能性がある.

運転完了時、時間複雑度はO(b^(m/2))である.(すべてのノードについて、最初のサブノードでAlpha>=Betaを満たす.)

Pseudo Code

function alphabeta(node, depth, alpha, beta, player)
    if depth == 0 or leaf node:
        return 해당 node의 heuristic 값
    if player == 'max':
        value = -(무한대)
        for each child of node:
            value = max(value, minimax(child, depth-1, 'min')
            alpha = max(alpha, value)
            if alpha >= beta:
                break
        return value
    else:
        value = +(무한대)
        for each child of node:
            value = min(value, minimax(child, depth-1, 'max')
            beta = min(beta, value)
            if alpha >= beta:
                break
        return value