0

ゲームに 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再帰の代わりにループを使用できる場合があることは知っていますが、それを変換する方法が見つかりませんでした。

誰かが良いアイデアを持っているなら、私はそれを聞いてうれしいです!

ありがとう、

4

1 に答える 1

1

一般に、minmax の再帰は同等の反復アルゴリズムで置き換えることはできません。そのため、再帰ツリーのいくつかの分岐をできるだけ早く停止することでパフォーマンスを改善しようとする、ベータ プルーニングなどの最適化方法があります。

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

于 2014-02-25T09:27:04.827 に答える