7

私はこれがこの質問をするのに正確に正しい場所ではないことを知っています、しかし多分賢い人が出くわして解決策を持っています。

私はコンピューターゲームを書こうとしていますが、この質問を解決するためのアルゴリズムが必要です。

ゲームは2人のプレーヤーの間で行われます。それぞれの側に1.000ドルがあります。3つの「ボックス」があり、各プレーヤーはそれらのボックスに入れる予定の金額を書き留めます。次に、これらの金額が比較されます。ボックスにもっとお金を入れた人は誰でも1ポイントを獲得します（それぞれ半分のポイントを引く場合）。より多くのポイントを獲得した人は、対戦相手に1.000ドルを獲得します。ゲームの例：

プレーヤーA：[500、500、0]プレーヤーB：[333、333、334]

プレーヤーAは、ボックスAとボックスBを獲得したために勝ちました（ただし、ボックスCを失いました）。

質問：お金を入れるための最適な戦略は何ですか？

質問がもっとありますが（数学に関連するのではなく、アルゴリズムに関連する）、最初にこれに対する答えを知る必要があります。

更新（1）：さらに調査した結果、これらのタイプの問題/ゲームは大佐ブロットゲームと呼ばれていることがわかりました。私は最善を尽くし、この主題に関する（非常に技術的な）文書をほとんど見つけませんでした。簡単に言えば、私が抱えている問題（上記のとおり）は、単純なBlottoゲーム（対称的なリソースを持つ3つの戦場のみ）と呼ばれます。難しいのは、たとえば、非対称のリソースを持つ10以上の戦場があるものです。私が読んだすべての文書は、単純なBlottoゲームは簡単に解決できると言っています。問題は、それらのどれも実際にその「簡単な」解決策が何であるかを言っていないということです。

更新（2）： Tom Sirgedasが言及した論文で、戦略を示すために小さなactionscriptファイルを作成しました。megaswfでテストできます。手順：三角形の内側の点をクリックします。赤い領域は勝利事例を表しています。青い領域は負けたケースを表し、小さな白っぽい線は引き分けを表します。

4

3 に答える 3

4

この論文で最適な戦略を見つけました：http ：//www.rand.org/pubs/research_memoranda/2006/RM408.pdf

これをBlottoの戦略と呼びましょう。

ここに画像の説明を入力してください

上の図を見てください。あなたが行うどんな動きも、三角形上の点で表すことができます。論文の戦略は、六角形の点をランダムに選ぶことを示しています。確率が高い六角形のエッジに近いポイントを選択します（六角形の中心の確率は0で、六角形の輪郭の最大確率まで線形にスケールアップします。六角形の輪郭上のすべてのポイントの確率は同じです）。

この解決策は「連続」ブロット用ですが、離散的なケース（N部隊を3つのグループに分割する）に興味があると思います。Nが3の倍数である場合、Blottoの戦略を個別のケースに適用すると、完全に機能します。他のNの値については、非常にうまく機能する六角形の境界線を微調整できましたが、完全ではありません。

これを打ち負かすことができる戦略がある場合、Blottoの戦略に勝つ静的な動きがなければなりません。Nが3の倍数でない場合を除いて、何もありません。大きな三角形と六角形が交わる線上の動き（たとえば、動き<0、.5、.5>）は、Blottoの戦略に勝つようです。失うよりわずかに多い。N = 100の場合、差は1％未満のように見え、Nが大きくなると縮小し続けます。

Blottoの戦略を実装するためのコード：

// generate a random number in the range [0,x) -- compensate for rand()%x being slightly un-uniform
int rnd( int x ) { int r; while ( 1 ) { r = rand(); if ( r < RAND_MAX/x*x ) return r % x; } }

// distance from center of triangle/hexagon to (x,y,z), multiplied by 3 (trilinear coordinates)
int hexagonalDist3( int x, int y, int z, int N ) { return max(max(abs(N-x*3),abs(N-y*3)),abs(N-z*3)); }

void generateRandomSimpleBlottoMove( int& x, int& y, int& z, int totalTroops )
{
   int N = totalTroops;
   while ( true )
   {
      x = rnd(N+1);
      y = rnd(N+1);
      z = N-x-y;

      // keep only moves in hexagon, with moves closer to the border having higher probability
      double relativeProbabilityOfKeepingThisMove = hexagonalDist3(x,y,z,N) > N ? 0 : hexagonalDist3(x,y,z,N);

      // minor adjustment for hexagon border when N is not a multiple of 3 -- not perfect, but "very close"
      if ( N % 3 != 0 && hexagonalDist3(x,y,z,N) == N ) 
         relativeProbabilityOfKeepingThisMove = N*(N%3)/3; 

      // possibly keep our move 
      if ( rnd(N) < relativeProbabilityOfKeepingThisMove )
         break;
   }
}
于 2011-03-03T01:14:52.030 に答える
0

したがって、これは実際には個別の数学の問題ではなく、ゲーム理論 (経済学) の問題です。質問にタグを付け直すことで、必要な注目を集めることができます。ゲーム理論では、「解」のアイデアは通常、ナッシュ均衡です。ゼロサム ゲームの場合、これを解決したいアルゴリズムは線形計画問題であることがわかります。設定方法の例については、このウィキペディアのページを参照してください。

于 2011-03-01T05:29:39.963 に答える
-1

このゲームに純粋なナッシュ均衡がないことを証明するのはかなり簡単だと私には思えます。純粋な戦略は、[333,333,334]のような固定された戦略です。私の証明のスケッチは次のとおりです。

プレーヤーAがプレイする純粋な戦略の場合、プレーヤーBはB2ポイントを獲得する別の純粋な戦略を見つけることができます。たとえば、Aが[500,500,0]を再生するとBは[501,0,499]を再生し、Aが[333,333,334]を再生するとBは[500,500,0]を再生します。2ポイントを獲得する方法は常にあります。もちろん、これはプレーヤーAが1ポイントを獲得することを意味します。

同様に、プレーヤーBがプレイする戦略の場合、プレーヤーAは自分を2にする別の純粋な戦略を見つけることができます。したがって、純粋なナッシュは存在しません。

また、（両方の）戦略が

1/3 [500,500,0]、1/3 [500,0,500]、1/3 [0,500,500]

（[500,500,0]を1/3の確率で、[500,0,500]を1/3の確率で、[0,500,500]を1/3の確率でプレイする）は、このゲームの混合ナッシュ均衡です。この戦略では、期待されるゲイン（#points）は3/2です。証明は私には骨の折れるようです。多分誰か他の人が簡単な証拠を持っているでしょう。

混合ナッシュは、可能な限り「最適」に近いものです。このゲームにはおそらく他の混合ナッシュ均衡があります。

于 2011-03-01T20:16:51.213 に答える