4

そこで、2 人用のボード ゲームで単純なコンピューター プレーヤーを作成するために、最小最大木をいじってみました。アルゴリズムの基本はわかっているのですが、私の七面鳥注入脳をすり抜けてしまうケースが… MINが2段で勝てたらどうなるでしょうか？

例として、2 人のプレーヤーのうちの 1 人だけが正方形を所有できる connect4/tic-tac-toe タイプのゲームを想定します。MIN が正方形を取得できないようにするためだけに、MAX に正方形を占有させるにはどうすればよいですか?

オプションが Left と Right である簡単な例 (気の利いた ASCII アートで示されています) を試してみましょう。ツリーが大きすぎて最終状態まで移動できないと仮定すると、中間値はヒューリスティック関数に基づいて計算されます (下に * でマークされています)。・INFはMINが勝つ終末状態。

                MAX (a)             
                /   \
               A     B
              /       \
           MIN (b)    MIN (c)     
           /  \       /  \
          A    B     A    B
         /     |     |     \
      -INF    *5    *22    *20

MIN は状態 (b) のアクション A を -INF のスコアで
選択しようとしている MIN は状態 (c) のアクション B を選択しようとしている +20 のスコアに対して
MAX は状態 (a) のアクション B を選択しようとしている+20のスコア

もちろん、問題は、MAX が B を選択した場合、MIN がアクション A を実行し (その正方形がまだ使用可能であるため)、MIN が勝つことです。MIN が次の手で -INF を取得するのを防ぐために、状態 (a) でアクション A を選択することの価値を MAX に認識させる必要があります。

MIN が勝つことができるかどうかを確認するためにコードに一連のテストを入れますが、アルゴリズムがこれを処理する必要があるように思えます。これを引き起こしているMAXに関する値の決定に欠けていると思います。

（明確にするために編集）

4

2 に答える 2

3

ミニマックス ツリーの各ノードは、完全なゲーム ステートです。プレイヤーがアクションを選択すると、ゲームはその状態に移行し、両方のプレイヤーのアクションが制限されます(別のブランチから別のアクションを選択する方法はありません)。したがって、あなたの例では、状態 (a) でプレーヤー Max がアクション B を選択した場合、ゲームは状態 C になります。この時点で最小プレーヤーの選択肢は A(22) と B(20) の 2 つだけです。ツリーの深さは問題ではありません。最大プレイヤーと最小プレイヤーは常に、ゲームの現在の状態から最適なアクションを選択します。

三目並べのゲームでは、各状態が完全なボードである必要があります (もちろん、実行可能です)。たとえば、最初のレベルは、X がマーカーを配置できる各可能な場所になります。次に、それらの状態の各子は、親の状態 (X が配置された場所) などを考慮して、O が配置できる可能な場所のそれぞれになります...

ヒューリスティックは、ゲーム ツリー全体を表すことができない場合 (チェスなど) に役立ちますが、ミニマックス ツリーの使用方法を変更しないでください。

于 2011-12-21T22:01:10.513 に答える
0

問題がヒューリスティック関数にあると思われる場合。おっしゃる通り、(a)の状態でMAXがBを選ぶと、

MIN はアクション A を実行し (その正方形はまだ使用可能であるため)、MIN が勝ちます。

ただし、ツリーでは、これを-Infではなく* 22でマークします（MINが勝ちます）。

于 2011-12-19T11:49:27.513 に答える