6

学校のプロジェクトでは、C++ で日付ゲームを作成する必要があります ( http://www.cut-the-knot.org/Curriculum/Games/Date.shtmlの例)。コンピューター プレーヤーは、アルファ ベータ プルーニングを使用して Minimax アルゴリズムを実装する必要があります。 . これまでのところ、対戦相手がそれらを縮小すると仮定しながら、潜在的な利益を最大化するという観点から、アルゴリズムの背後にある目標が何であるかを理解しています.

しかし、私が読んだリソースのどれも、ミニマックスがすべての決定の基礎となる評価関数を設計する方法を理解するのに役立ちませんでした。すべての例では、リーフ ノードに任意の番号が割り当てられていますが、実際にはそれらのノードに意味のある値を割り当てる必要があります。

直感的には、葉のノードが勝った場合は +1、負けた場合は -1 のようになりますが、中間のノードはどのように評価されるのでしょうか。

どんな助けでも大歓迎です。

4

3 に答える 3

5

最も基本的なミニマックスは、リーフ ノードのみを評価し、勝ち、負け、引き分けをマークし、それらの値をツリーに戻して中間ノードの値を決定します。ゲーム ツリーが扱いにくい場合は、カットオフの深さをミニマックス関数の追加パラメーターとして使用する必要があります。深さに達したら、不完全な状態に対して何らかの評価関数を実行する必要があります。

ミニマックス検索のほとんどの評価関数はドメイン固有であるため、特定のゲームのヘルプを見つけるのは難しい場合があります。評価では、特定のプレイヤーが勝利するポジションのパーセンテージを返す必要があることを覚えておいてください (ネガマックス実装を使用している場合ではなく、通常は最大)。あまり研究されていないゲームは、より研究されている別のゲームによく似ています。これは、ゲームのピックアップ スティックと非常に密接に結びついています。ミニマックスとアルファベータのみを使用すると、ゲームは扱いやすいと思います。  

非ターミナル ポジションの評価関数を作成する必要がある場合は、これがスティック ゲームの分析に少し役立ちます。これがデート ゲームに役立つかどうかを判断できます。

最終的な位置と、その位置につながる可能性のあるすべての動きを見て、結果を強制する方法を探し始めます。スティック ゲームでは、最終的な位置は最後の移動で 3 つ以下のスティックが残っていることです。したがって、ターミナル ポジションからすぐに進むポジションは、対戦相手に 4 本のスティックを残すことになります。目標は、何があっても対戦相手に 4 本のスティックを残すことです。これは、5 本、6 本、または 7 本のスティックがあなたに残されている場合に行うことができます。あなたが 5、6、または 7 のいずれかになるために対戦相手がいる必要がある場所は 8 です。このロジックを延々と続けると、パターンが非常に迅速に利用可能になります。常に 4 で割り切れる数を相手に残せば勝ち、それ以外は負けです。  

これはかなり些細なゲームですが、ヒューリスティックを決定する方法は、割り当てに直接適用できるため、重要です。最後に移動したものが最初に移動し、一度に 1 つの日付属性しか変更できないため、勝つには残り 2 つの移動が必要であることがわかります... など。

頑張ってください、あなたが何をしているのか教えてください。

于 2010-06-28T19:09:11.170 に答える
3

評価関数の最も単純なケースは、勝利の場合は +1、敗北の場合は -1、未完了のポジションの場合は 0 です。ツリーが十分に深い場合、この単純な関数でも優れたプレーヤーが得られます。分岐係数が高い重要なゲームでは、通常、いくつかのヒューリスティックを使用した、より優れた関数が必要です (たとえば、チェスの場合、ピースに重みを割り当てて合計を見つけることができます)。日付ゲームの場合、すべての中間ノードに 0 を指定して、最も単純な評価関数を使用します。

補足として、ミニマックスはこの特定のゲームに最適なアルゴリズムではありません。しかし、私はあなたがすでにそれを知っていると思います.

于 2010-06-08T23:55:03.710 に答える
0

あなたがリンクしたデートゲームについて私が理解していることから、プレーヤーにとって可能な唯一の結果は勝つか負けるかであり、間にはないようです（私が間違っている場合は私を訂正してください）。

この場合、勝ちのポジションに1の値を割り当て（現在のプレーヤーは12月31日になります）、負けのポジションに-1の値を割り当てる（他のプレーヤーは12月31日になります）だけです。

ミニマックスアルゴリズム（アルファベータ法なし）は次のようになります。

A_move(day):
   if day==December 31:
       return +1
   else:
       outcome=-1
       for each day obtained by increasing the day or month in cur_date:
           outcome=max(outcome,B_move(day))
       return outcome

B_move(day):
   if day==December 31:
       return -1
   else:
       outcome=+1
       for each day obtained by increasing the day or month in cur_date:
           outcome=min(outcome,A_move(day))
       return outcome
于 2010-06-28T20:16:58.647 に答える