「MiniMax」再帰を実装するより良い方法 [終了]

Question

閉まっている。 この質問は オフトピック. 。現在回答を受け付けておりません。

---

この質問を改善したいですか? 質問を更新する っていうことは 話題に沿った スタックオーバーフロー用。

閉まっている 5年前.

ゲームに MinMax アルゴリズムを使用していますが、多くの可能性があるため、「アルファ-ベータ プルーニング」を使用しても、MinMax 再帰に時間がかかりすぎます。

私のコードは次のようになります。

min(state,depth,alpha,beta):
    if stopingCond: 
        return value

    for moves in allmoves:
        state.do(move)
        beta = min(beta, max(state,depth,alpha,beta) )
        if alpha >= beta: return beta
    return beta

max(state,depth,alpha,beta):
    if stopingCond: 
        return value

    for moves in allmoves:
        state.do(move)
        alpha = max(beta, min(state,depth,alpha,beta) )
        if alpha >= beta: return alpha
    return beta

時々使えることはわかっています for 再帰の代わりにループがありますが、変換する方法が見つかりませんでした。

誰かが良いアイデアを持っているなら、喜んでそれを聞きます！

ありがとう、

Answer 1

一般に、minmax の再帰は同等の反復アルゴリズムで置き換えることはできません。そのため、再帰ツリーの一部の分岐をできるだけ早く停止することでパフォーマンスを向上させる、ベータ プルーニングなどの最適化手法が存在します。

あなたのゲームでは minmax (または一般に再帰的アルゴリズム) がまったく必要ない可能性があり、他の手法を使用して最適な解決策を見つける他の方法がある可能性がありますが、正確なルールのセットがなければそれを判断することは不可能です。