5

MiniMax ツリーとアルファ ベータ プルーニングの概念は理解していますが、アルファ ベータ プルーニングに関する多くのリソース (ウィキペディアなど) で α​​ >= β のような条件が存在する理由がわかりません。具体的には、等号は紛らわしいです。私が理解しているように、アルファ ベータは minmax が返す動きを返しますが、ほとんどの場合は高速です。しかし、この例はそれと矛盾しています:

        .
      / |  \
    1   3*   2
  / |  / \   | \ \
  1 1 5   3  4 3 2

上は元の最小最大ツリーです。ご覧のとおり、スコア 3 の 1 つの手が選択されます。では、アルファ ベータを実行してみましょう。

        .
      / |  \
    1   3*   3*
  / |  / \   | \
  1 1 5   3  4 3

3 >= 3 であるため、最も右の手を切り捨てます。しかし、アルゴリズムは同じスコアを持つ 2 つの手のどちらかを選択できますが、min-max で見たように、正しい選択はわずかに悪いです。アルゴリズムが単純に α > β を指定した場合、これは発生しないため、2 も検索する必要があります。

それはウィキペディアの疑似コード (および他の多くのリソース) のタイプミスでしたか? または、ここで本当に大きなことを誤解していました。

4

2 に答える 2

2

通常、 equals が使用されます。これは、認識可能なパフォーマンスの向上を実現し、戻り値が equal ブランチから変化しないためです。

少なくとも有用である可能性がある唯一のポイントは、最初の層の検索深度ですが、パフォーマンスの低下はここで最悪です。

ミニマックスは、相手がミスを犯したかどうかを推測するのではなく、常に最高の動きをすることに依存しています。2 つの同等のブランチのうち、より良いものを選択するための特別な評価を含めると、投機にリソースを費やすことになります (ミニマックスではその定義により、投機を行いません)。

つまり、equals を使用しないことに意味はありません。

于 2015-07-16T07:43:02.677 に答える