4

これはハードウェアです:

Wythoff のゲームは 2 人のプレーヤーがいて、この例では 3 つの石の山があります。各プレーヤーは順番に山から石を取り、最後の石を拾うとプレーヤーが勝ちます。毎ターン、プレイヤーは 1 つの山から N 個の石、2 つの山から N 個の石、または 3 つの山すべてから N 個の石を取り除くことができます。

勝利構成とは、最初のプレイヤーが勝利を強制できる構成です。たとえば、(0,0,13)、(0,11,11)、および (5,5,5) は、最初のプレーヤーがすべての石をすぐに取り除くことができるため、勝ち構成です。

負ける構成とは、最初のプレーヤーが何をしても、2 番目のプレーヤーが強制的に勝つことができる構成です。たとえば、(0,1,2) と (1,3,3) は負け構成です: 正当な手は、2 番目のプレーヤーに勝ち構成を残します。

xi <= yi <= zi <= 100 であるすべての損失構成 (xi,yi,zi) を考えます。これらについて Σ(xi+yi+zi) = 173895 であることを確認できます。

検索して検索しましたが、負けた (コールド) ポジションをすべて見つける方法がわかりません。座標のバイナリ値を合計して nimnumber を取得し、nimnumber > 0 の場合はコールド ポジションです。しかし、最終的には Σ(xi+yi+zi) > 1mil になります。誰かが私を正しい方向に向けるのを手伝ってくれますか?

4

1 に答える 1

1

宿題なので、完全な解決策は投稿しませんが、ヒントは次のとおりです。

xi <= yi <= zi <= 100 であることは既にわかっているため、構成の数が 2*101^3 (自分の番の x2) を超えることはありません。これは 200 万をはるかに超えません。ルックアップ テーブルを作成して (たとえば、サイズ a、b、c の山に対応し、d の番です)、再帰をisWinningPosition[][][][]試してみてください。isWinningPosition[a][b][c][d](注意: ルックアップ テーブルの各エントリはtrue、 、false、およびnot computedを 3 つの別個のものとして処理する必要があります。)

于 2012-07-20T21:17:29.790 に答える