algorithm - 勝つ選手を見つける方法

Question

2 人のプレイヤーが次のゲームをプレイします。ゲームの開始時に、彼らは n (1<=n<=100000) 個の石の山から始めます。ゲームの各ステップで、プレーヤーはパイルを選択し、このパイルから少なくとも 1 つの石を取り除き、このパイルからまだ石がある他のパイルに 0 個以上の石を移動します。可能な手がなくなった場合、プレーヤーは負けます。最初の山札が与えられたら、どちらが勝つかを決定します。最初のプレーヤー、または両方が完全にプレーした場合は 2 番目のプレーヤーです。

Answer 1

これはNimのバリアントです。Nim の解決策を理解することは、このゲームをよりよく理解するのに役立ちます。

Nim にとって、ゲームnは石の山から始まります。次に、各プレイヤーは山を 1 つ選び、山から少なくとも 1 つ、場合によってはそれ以上の石を取り除きます。残りの石がなくなったらゲーム終了です。

上にリンクされたウィキペディアの記事には、パイルサイズのバイナリデジタル合計を計算することを含む、勝利戦略の優れた説明があります. それを読んでください。そうすれば、この変種を解決できるはずです。

Answer 2

まず、既知の結果を持つ位置を分析することから始めます。これは、すべての石が1つの山にある場合に当てはまります。次に、少なくとも1つの石がある他のパイルがないため、移動の2番目の部分を実行できません（これは、0個の石を移動しても、別の空でないパイルが必要であると想定しています）。したがって、これは位置を失います。

次に、どの位置から負けた位置に到達できるかを分析し始めます。これらは、勝利ポジションの最初のラウンドになります。

最初の観察：移動は2つのパイルにのみ影響するため、正確に2つのパイルがある場合にのみ、ルーズポジションに到達できることは明らかです。パイルが2つしかない場合は、そのうちの1つからすべての石を取り除くことで、いつでも負けた位置にたどり着くことができます。したがって、これが勝ちの位置になります。

だから今、あなたはあなたが見つけられた勝利の位置にあなたを連れて行くことをあなたに強制する位置がどれであるかについて考えなければなりません。これらは再び位置を失うことになります（ヒント：これは、それぞれ1つの石で3つの山がある場合のみだと思います）。

このように続けると、最終的には最終的な解決策が思い浮かびます。私はあなたのために問題全体を解決したくありません。これはあなたのスキルには役に立たないからです。自分で解決策を考え出す方がよいでしょう。

お役に立てれば。

注：単一の空でないパイルで操作を実行することが許可されている場合、つまりゼロストーンを移動するときに別の空でないパイルが必要ない場合、最初の負け位置は、ストーンがまったく残っていないときであり、最初の勝ちポジションは、任意の数の石を含む山が1つしかない場合です。