ゲーム理論

トピックを拡張するために、有名なニームのゲームのバリエーションを分析します。

そして、テーブルの上には石の山がいくつかあります。 1回の動きで、任意のパイルから任意の数の石を取り出すか、任意のパイルを2つの空でないものに分割することが許可されます。

通常のルールでは、移動できないプレイヤーは負けとなります。 景品では、テーブルに石が残っていないのに負けた人。







解決策



この問題を解決するには、オリンピック選手はゲームの理論に精通している必要があります



このゲームのバリエーションの分析は、通常のゲームほど複雑ではありません。

通常のゲームのSprag-Grandi関数（または誰かが使用したSprag-Grundi）の形式は次のとおりです。



G（n）=

{ nのn-1 （mod 4）== 0}、

{ n for n（mod 4）== 1または2}、

{ nのn + 1 （mod 4）== 3}



証明はnの帰納法によって与えることができます。 n = 1の場合は些細なことです（いつでも拾い上げて、全体を勝ち取ることができます）。 Grandi関数をすべてのk <nに対して保持させます。 nを確認します。

1. このようなヒープから、必要な数の石、つまりより小さなパラメーターを使用した関数を削除することで、より小さなサイズのヒープを取得できます。
2. ヒープを2つに分割しても、n = 4 * k + 3を除き、G（k）、k <n以外のグランディ数の位置を取得できないことを確認できます。 次に、P（1、n-1）= G（1）xor G（n-1）= 1 xor（4 * k + 2）= 4 * k + 3 = n つまり、G（4 * k + 3）= n + 1です。

変更されたルールに従ってゲームに戻りましょう。

すべてのヒープに1つの石がある場合を除いて、ゲームは通常のゲームに似ているという主張を証明しましょう。 この場合、プレイヤーに依存するものはなく、ゲームの結果はパリティnによって決まります。



証明。

Sprague Grandi番号の定義によれば、Pからのすべてのポジションが負け、Pからのすべてが勝っている（P（not not P）と表記）こと、Pから他のポジションへの移動がないことを示します。

どんな立場からでもそれを証明するのは簡単です！ R Rに動きがあります。これを行うには、ゲームの戦略をわずかに変更する必要があります。 たとえば、選択した動きでパイルに1石を残す場合、代わりにパイル全体を取り、逆も同様です。パイル全体を取り込んだ場合、代わりに1石を残します。 そして最後に、パイルを2 x 1ストーンに分割した場合、常に1ストーンのみを残すことができます。



この方法では、「ギブアウェイ」のルールに関する問題を解決することができ、極端な場合のみを考慮します。