ミニマックスアルゴリズム：コスト/評価関数？

Question

学校のプロジェクトは、私はで（C ++での例を日付ゲームを書いていますhttp://www.cut-the-knot.org/Curriculum/Games/Date.shtml の）コンピュータプレイヤーはアルファ・ベータ法とミニマックスアルゴリズムを実装しなければならないところ。これまでのところ、私は目標は、相手がそれを縮小化されますと仮定しながら、潜在的な利益を最大化するという点で、アルゴリズムの背後にあるものを理解しています。

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

直感は、それが勝利のリーフノードのための1のようなものに、そして-1損失のために、どのように中間ノードが

？評価しないだろうと言われます

任意の助けが最もいただければ幸いです。

Answer 1

最も基本的なミニマックスは、勝利をマークし、リーフノードのみを評価損失と引き分け、および中間ノード値を決定するために、ツリーまでこれらの値をバックアップします。ゲーム木が難治性である場合には、あなたのミニマックス関数への追加パラメータとしてカットオフ深さを使用する必要があります。深さに達すると、あなたが不完全な状態のための評価関数のいくつかの種類を実行する必要があります。

ミニマックス検索で

ほとんどの評価関数は、それほど難しいことができ、あなたの特定のゲームのためのヘルプを見つけること、ドメイン固有のものです。ただ、（ただしnegamax実装を使用しない場合、通常は最大）の評価は、特定のプレーヤーの勝利という位置の割合期待のいくつかの種類を返す必要があることを覚えておいてください。ちょうど約あらゆる少ない調査のゲームは密接に他の多くの研究のゲームに似ているために起こっています。 ピックアップスティックのゲームと非常に密接で、この1本のネクタイ。唯一のミニマックスとアルファベータを使用して、私はゲームが扱いやすいですよね。

あなたは非末端位置のための評価関数を作成する必要がありますしている場合は、

は、ここに日付ゲームのためかその便利な場合はあなたが決めることができ、スティックゲームの分析と少しの助けである。

端子の位置とその位置につながることができ、すべての動きを見て、結果を強制する方法を探し始めます。スティックゲームでは、端末の位置は、最後の移動中に残った3本の以下の棒です。すぐにその端末の位置を進める位置は、したがって、あなたの対戦相手に4本のスティックを残しています。目標は、今どんな4本のスティックで相手を残していない、そしてそれはあなたに残して5、6または7スティックのいずれかから行うことができ、あなたはそれらの位置のいずれかであなたを残すために相手を強制したいと思います。あなたは5、6または7のいずれかになるようにするためにあるように、相手のニーズ場所は8で上とに、このロジックを続行し、パターンは非常に迅速に利用できるようになります。常に4で割り切れる数で相手を残して、あなたは何か、あなたが失う、勝利。

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

運のベスト、私たちはあなたがやって終わるのか分からせます。

Answer 2

は、評価関数の最も単純な場合は、勝利のために+1 -1以外の完成位置に対する損失を0。あなたのツリーが深い十分です考えると、これでも簡単な関数はあなたに良い選手を与えるだろう。任意の非自明なゲームのために、高分岐率で、一般的には、いくつかの経験則で（例えばチェスのためにあなたが作品に重みを割り当て、合計などを見つけることができる）、より良い機能を必要としています。日付ゲームの場合には、私はすべての中間ノードの場合は0で、最も単純な評価関数を使用することになります。

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

Answer 3

私はあなたがにリンクされている日の試合の理解何から、それはプレーヤーのための唯一の可能な結果が勝つか負ける、の間に存在していないされていることを（私が間違っている場合は、私を修正してください）。

そうです

は、この場合には、当選位置（現在のプレイヤーが12月31日に取得）との-1失う位置に値（他のプレイヤーが12月31日に取得）に1の値を割り当てるだけの問題です。

このようになります（アルファ・ベータ法なし）あなたのミニマックスアルゴリズムます：

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