3

minmax アルゴリズムの疑似コードを取得したい。def maxAgent(gameState, depth) と minAgent の 2 つの関数を作成する必要があります。そのための適切で簡単な擬似コードを持っている団体はありますか。

4

2 に答える 2

2

minmax アルゴリズムは、プレーヤー A のスコアを最大化し、プレーヤー B のスコアを最小化しようとします。ノードが与えられると、スコアの最大値 (A の場合) または最小値 (B の場合) を取得することで、最適なプレイからの最終結果を見つけることができます。後続ノード。

リーフ ノードには勝者 (A の場合は 1、B の場合は -1) が割り当てられ、他のすべてのノードのスコアは 0 であると仮定します。その後、次のような方法で A の最終的な勝者の結果を計算できます。

  getMaxScore(node) {
    score = node.score;
    for each child node 
       score = max(score, getMaxScore(node))  
    next

    return score;
  }

これが基本的なアルゴリズムです。スコアが 1 になるとすぐに評価をショートサーキットでき、A の勝利が確定します。

アルゴリズムは B の getMinScore と同じですが、min 関数を使用するだけで、ショートサーキットの場合は -1 を探します。

于 2010-07-29T04:43:41.830 に答える
2

A と B の 2 人のプレイヤーが交代でプレイします。

与えられたボードの位置 P を評価するスコアリング関数 f が与えられます。f(P) の値が大きいほど、A にとっては有利であり、B にとっては不利です (つまり、f(P) は、P が A にとってどれほど「良い」かの推定値です)。それ以上の先読みを行わずに)。

ボードの位置 P を考えてみましょう。

P がリーフ ノードの場合 (つまり、P が勝者であるか、必要なだけ先を見ている場合)、このノードのスコアとして f(P) を返します。

それ以外の場合、P はリーフ ノードではなく、子 C1、...、Cn を持ちます。S1、...、Sn を与えて、子のスコアを再帰的に計算します。

A が P でプレーする場合、A は常にアドバンテージを最大化するためにプレーするため、P のスコアは max{S1, ..., Sn} です。

B が P でプレーする場合、B は常に A のアドバンテージを最小限に抑えるためにプレーするため、P のスコアは min{S1, ..., Sn} です。

それはコードに変換するのに十分なはずです。

それが終わったら、必要な検索の量を (大幅に) 削減する必要があるアルファ ベータ プルーニングを見てください。アルファベータ剪定は、A の最大アドバンテージを M にするために B がプレーできると A が推測する場合、B は A にそのオプションを決して許可しないため、スコアが M より大きいサブツリーを考慮する意味がないという考えに基づいています!

于 2010-07-29T06:39:54.243 に答える