13

私はミニマックスを本当に理解せずに実装しようとして一日を過ごしました。さて、私はミニマックスがどのように機能するかを理解していると思いますが、アルファベータ法は理解していません。

これがミニマックスの私の理解です：

  1. 深さの制限まで、可能なすべての動きのリストを生成します。

  2. 下部のすべてのノードにとって、ゲームフィールドがどれほど有利かを評価します。

  3. すべてのノードについて（下から開始）、レイヤーが最大の場合、そのノードのスコアはその子の最高スコアになります。レイヤーが最小の場合、そのノードのスコアはその子の最低スコアです。

  4. スコアを最大にしようとしている場合はスコアが最も高く、最小スコアが必要な場合はスコアが最も低い移動を実行します。

アルファベータプルーニングについての私の理解は、親レイヤーが最小で、ノードのスコアが最小スコアよりも高い場合、結果に影響を与えないため、プルーニングできるということです。

しかし、私が理解していないのは、ノードのスコアを計算できる場合は、ノードより下のレイヤー上のすべてのノードのスコアを知る必要があるということです（ミニマックスの私の理解では）。つまり、同じ量のCPUパワーを引き続き使用することになります。

誰かが私が間違っていることを指摘してもらえますか？この答え（ミニマックスは馬鹿のために説明されました）は私がミニマックスを理解するのを助けました、しかし私はアルファベータ剪定がどのように役立つかわかりません。

ありがとうございました。

4

5 に答える 5

17

アルファベータを理解するために、次の状況を考慮してください。白が変わり、白がスコアを最大化しようとし、黒がスコアを最小化しようとしています。

ホワイトは、ムーブA、B、およびCを評価し、Cで最高のスコアが20であることを確認します。次に、ムーブDを評価するときに何が起こるかを考えます。

白がムーブDを選択した場合、黒によるカウンタームーブを考慮する必要があります。早い段階で、黒は白の女王を捕らえることができ、そのサブツリーは女王を失ったためにMINスコア5を取得します。ただし、すべての黒人の反動を考慮しているわけではありません。残りをチェックする価値はありますか？いいえ。

黒が5未満のスコアを取得できるかどうかは関係ありません。これは、白が「C」を移動するとスコアが20に保たれる可能性があるためです。黒は、スコアを最小化しようとしているため、スコアが5を超えるカウンター移動を選択しません。はすでにスコア5の移動を見つけました。白の場合、DのMIN（これまでのところ5）がCのMIN（確かに20）を下回るとすぐに、移動Cが移動Dよりも優先されます。そこで、ツリーの残りの部分を「剪定」し、レベルを上げて、最後まで白い動きE、F、G、H....を評価します。

お役に立てば幸いです。

于 2011-10-25T14:44:15.283 に答える
3

ノードの値を決定するために、ノードのサブツリー全体を評価する必要はありません。アルファベータプルーニングは、動的に計算された2つの境界アルファとベータを使用して、ノードが取ることができる値を制限します。

アルファは、ゲームツリーの別のパスを介して最大プレーヤーが（最小プレーヤーが何をするかに関係なく）保証される最小値です。この値は、最小化レベルでカットオフ（プルーニング）を実行するために使用されます。最小プレーヤーが最小ノードのスコアが必然的にアルファよりも小さいことを発見した場合、最大プレーヤーはすでにより良い動き（値がアルファを持つもの）を持っているため、そのノードからの選択肢を評価する必要はありません。

ベータは、最小プレーヤーが保証される最大値であり、最大レベルでカットオフを実行するために使用されます。最大プレーヤーが最大ノードのスコアが必然的にベータよりも大きいことを発見した場合、最小プレーヤーはすでにパスを持っているため、最小プレーヤーはこのパスを取ることを許可しないため、そのノードからのそれ以上の選択肢の評価を停止できます。それはベータの値を保証します。

アルファベータプルーニング、その擬似コード、およびいくつかの改善点の詳細な説明を書きました：http: //kartikkukreja.wordpress.com/2014/06/29/alphabetasearch/

于 2014-06-29T19:17:08.410 に答える
1

あなたの質問は、評価関数の誤解を示唆していると思います

ノードのスコアを計算できる場合は、ノードより下のレイヤーにあるすべてのノードのスコアを知る必要があります（ミニマックスの私の理解では）

あなたがそこで何を意味していたのか完全にはわかりませんが、それは間違っているように聞こえます。評価関数（EF）は通常、非常に高速で静的な位置評価です。これは、単一の位置を見て、そこから「評決」に到達するだけでよいことを意味します。（IOW、常にnプライへの分岐を評価するとは限りません）

多くの場合、評価は本当に静的です。つまり、位置評価関数は完全に決定論的です。これは、評価結果を簡単にキャッシュできる理由でもあります（位置が評価されるたびに同じになるため）。

さて、例えばチェスの場合、通常、上記からかなりの明白な/秘密の逸脱があります：

  • 位置は、ゲームのコンテキストに応じて異なる方法で評価される場合があります（たとえば、正確な位置がゲームの早い段階で発生したかどうか、ポーンの移動/キャプチャなしで何回移動したか、アンパッサンとキャスリングの機会）。これに取り組むための最も一般的な「トリック」は、実際にその状態を「位置」に組み込むことです1

  • 通常、ゲームのさまざまなフェーズ（オープニング、ミドル、エンディング）に対して異なるEFが選択されます。これは設計にいくらかの影響を及ぼします（EFを変更するときにキャッシュされた評価を処理する方法？EFがプライごとに異なる場合にアルファ/ベータプルーニングを行う方法？）

正直なところ、私は一般的なチェスエンジンが後者をどのように解決するかを知りません（私は単におもちゃのエンジンのためにそれを避けました）

私は次のようなオンラインリソースを参照します：

1「チェック」/「膠着状態」の条件と同様に、評価関数の外部で特別な場合がない場合は、

于 2011-10-25T11:55:22.453 に答える
1

（非常に）mimimaxの簡単な説明：

  • nあなた（ボードポジションの評価者）は、ムーブをプレイする選択肢があります。それらすべてを試して、（対戦相手の）評価者に取締役会のポジションを与えます。

    • 対戦相手は、新しいボードの位置を評価します（彼にとっては対戦相手側）-本質的に同じことを行い、最大深度またはその他の条件に達して静的評価者が呼び出されない限り、（対戦相手の）評価者を再帰的に呼び出します-そして次に、最大評価を選択し、評価を返信します。

  • それらの評価が最小の移動を選択します。そして、その評価は、最初に評価しなければならなかったボードの評価です。

（非常に）α-β-剪定の簡単な説明：

  • nあなた（ボードポジションの評価者）は、ムーブをプレイする選択肢があります。それらすべてを1つずつ試して、ボードの位置を（対戦相手の）評価者に渡しますが、（ボードの）現在の評価も渡します。

    • 対戦相手は新しいボードの位置（彼にとっては対戦相手側）を評価し、評価をあなたに送り返します。しかし、彼はどのようにそれをしますか？彼は動きをする選択肢がありmます。彼はそれらすべてを試し、新しい取締役会のポジションを（1つずつ）（対戦相手の）評価者に与えてから、最大のポジションを選択します。
    • 重要なステップ：彼が返す評価のいずれかが、あなたが彼に与えた最小値よりも大きい場合、彼は最終的に少なくともその大きさの評価値を返すことは確実です（彼は最大化したいため）。そして、（最小化したいので）その値を無視するのは確実なので、彼はまだ評価していないボードの作業を停止します。

  • それらの評価が最小の移動を選択します。そして、その評価は、最初に評価しなければならなかったボードの評価です。

于 2011-10-25T15:08:48.907 に答える
1

ここに簡単な答えがあります-すべての子の正確な値を計算しなくても、ノードの値を知ることができます。

親ノードプレーヤーの観点から、子ノードが以前に評価された兄弟ノードよりも優れていることができないことがわかったらすぐに、子サブツリーの評価を停止できます。少なくともこれは悪いです。

于 2011-10-25T17:31:49.433 に答える