石取りゲーム

質問

石の山がいくつかあって、２人で交互に石の山から石を取っていき、最後の石を取ったほうが負けというゲームがあります。

山の数はいくつでもいいのですが、それぞれ山の石の個数をa,b,c,d,・・・・としたとき、
最初の山の状態は、a≧b≧c≧d≧・・・とします。

石の取り方は、
・好きな山から、任意の個数を取る。
・取ったあと、a≧b≧c≧d≧・・・の関係が成り立つように別の山から石が除かれる。

たとえば、
(10,9,9,6,3)の山があった場合、
２番目の山から４個とって５個にしたら、３番目以降の山からも５個を超えた分だけ石が除かれて、
(10,5,5,5,3)となります。

山が２つの場合は、(k,k-1)の状態を良形とすれば、
自分の手番のときに、良形にできれば必勝となります。

では、山が３つの場合や４つの場合、必勝となるための良形とはどんな状態でしょうか。
良形かどうかを簡単に確認する方法はあるでしょうか。

回答No.6

B-juggler · ベストアンサー

Ｎｏ．２です。　了解しました。チョンプですね。

だったら未解決ですね。この形だと、少し先にいけるかもと思ったけど。

あまり深く追求するのはやめておきましょう＾＾；

（４，２，１）は勝てないですね　すみません。

（４，２，２）で、手番負けなんですね・・・。

（３，１，１）も手番負けだから、ひょっとすると、

（ｊ＋２、ｊ，ｊ）　のときは、手番負けなのかも？

で、話が変わりますが、順序が違ってしまったけど

何をやろうとしていたかを書いていなかったです。

２つの山の場合、勝つパターンは分かった。
↓
３つの山のとき、勝つパターンと、負けるパターンを探し出し
一般化する。
↓
４つの山のとき、一部ではあるだろうけれど拡張可能。と見ていました。

なので、３つの山での、「手番勝ち」、「手番負け」を探していました。

多分、（ｋ，ｋ，ｋ）は手番勝ちですね。

だとすると、（２，２，２，１）となったとき、手番負けですよね。
　＃多分そうだよ・・・。

この形式なら少し先にいけるのかもね。
気が向いたら＾－＾

お礼

紹介していただいたサイトに書かれていましたが、
（ｋ，ｋ，ｋ，・・・，ｋ）は先手必勝ですね。

チョンプの盤で考えると縦と横を入れ替えてもゲームとしては同じなので、
（ｋ，ｋ－１）
と
（２，２，２，・・・，２，１）
は同じ形になり、どちらも後手必勝です。

３つの山で、３番目の山が０～２個の場合は、
（ｋ，ｋ－１，０）　（ｋ≧１）
（３，１，１）
（２，２，１）
（ｋ，ｋ－２，２）　（ｋ≧４）
が後手必勝になることまでは分かったのですが、３個以上の場合は不規則になるようで、何か規則性はないかと質問した次第です。

とりあえず締め切りますが、何か分かったらまた質問しますので、よろしく願いします。

回答No.5

B-juggler

こんばんは　Ｎｏ．２です　

えっと、チョンプ　なのかどうかちょっと分かりかねますが、

こういうページがありましたので、一応。

http://www.lab2.kuis.kyoto-u.ac.jp/~itohiro/lecture/Nim08-web.pdf

アクロバットリーダーがいるけど、組み合わせゲーム理論の講義内容みたいですね。

これは正直、難しいと思う。

何でもかんでも式化すればいいかって話で・・・。

私どちらかというと普段はやらないんだよね。
　＃なので、半分本職なのね。

３つの山を考えていますが

それぞれ　大きい順に　Ｌ、Ｍ、Ｓ　（ポテトかっヽ（・∀・）ノ　）

としておきます。

今、ＬとＭの差が　１　のとき、　何も考えず、先手必勝。

（Ｌ，Ｍ，Ｓ）・・（ｋ＋１，ｋ，ａｎｙ（≦ｋ）　）

こうなっているときは、黙って、ａｎｙを全部とって、２つにして勝ちですね！

　何も断りを入れていないけど、ｋは自然数ね。
　ａｎｙ≠０ね

ＬとＭの差が２以上のとき、条件満たさなければ先手必敗だと思うんだけどね～。
　＃まだ微妙・・・。

（ｋ＋２，ｋ，ａｎｙ）　のときに、　ａｎｙ（Ｓの山から）全部は取れないですね。

　＃（ｋ＋１，ｋ）作られて負け。

ｋ＋１も作れないよね　（Ｌの山から一本）

　＃これは　ａｎｙ　全部取られて負けだね。

（３，１，１）で、先手が勝てる手があるかどうか。

多分ないかなぁ～？？

ところが（４，２，２）なら勝ちなのよね。

Ｓの山から　一本とって　（４，２，１）で勝ちですね。
これで後手は動けない。

２進数で考えたほうが少し得かな？
４＝（１００）２進数　→　これを　一本とみなす。
２＝（１０）２進数　→　同じく一本とみなす。

そうすると、　（４，２，１）は　（１，１，１）と同じ。

でもこの場合はダメなのよね。う～ん、難しいね。

（１，１，１）は先手勝ち。　Ｍの山を取れば、（１，０，０）で終わり。

（４，２，１）は、この方法が使えない。（４，０，０）なら、先手勝ちだもん。

（４，１，１）にするしかないけど、先手は（３，１，１）にして、後手に手無し。

　＃（３，２，１）は、Ｓとって先手勝ちね。

今のところ考えている三つの山の場合、「ＬとＭの差が１のとき」

「（１，１，１）～（４，４，４）　同じ数の山」
　＃（５，５，５）が大丈夫かどうか検討中。
　＃（５，３，３）で後手に手がなければ、先手勝ち。
　＃これができれば、（Ｊ（≦ｋ＋２），ｋ，ｋ（≠１）　が大丈夫）

これは大変な問題だ！　数学オリンピックかなんかかな？

お礼

回答ありがとうございます。

このゲームは表現方法はちょっと違いますが、まさしくチョンプでした。

ＬとＭの差とか２進数で考えるというのは参考になりました。自分でももう少し考えてみます。

この問題は、（５，５，５，５，５）のときどうすれば勝てるかというクイズがあって、
正解は、（５，１，１，１，１）にして、あとは１番目の数と山の数を同じにしていけば勝てるということでした。
例えば、
（５，１，１，１，１）→（４，１，１，１，１）→（４，１，１，１，０）
（５，１，１，１，１）→（５，１，１，０，０）→（３，１，１，０，０）

これを一般化したらどうなるかと考えてしまいました。

このことから、（３，１，１）は後手の勝ちですね。

（４，２，１）は後手勝ちと書かれていますが、
（２，２，１）にすればいいので、先手勝ちではないでしょうか。
（４，２，２）が後手勝ちのようです。

ともかく、未解決の問題だということが分かっただけでも質問した甲斐がありました。

回答No.4

2ac0uO

これはチョンプと言うゲームで、多分現在でも未解決だろうと思います。
必勝法が知られているのは、（Ｎ，１，１，１，・・・，１）と言うパタンと、
（２，２，２，・・・，２，１，１，・・・，１）と言うパタンくらいではないかと思います。

お礼

チョンプと言う名前があったんですね。知りませんでした。
ありがとうございます。

未解決でしたか。
三山崩しのように簡単な計算で判断できないかと思ったんですが無理のようですね。

（Ｎ，１，１，１，・・・，１）（山の数がＮ個）のパタンは分かっていましたが、
（２，２，２，・・・，２，１，１，・・・，１）と言うのは？
（２，２，２，・・・，２，１）ではないですか？

補足

チョンプで検索したらいろいろ出てきました。
やはり一筋縄ではいかないようですね。

回答No.3

qaz_qwerty_me

＃１です。
大きな勘違いしていました m(_ _)m

３目並べは全く関係ないですね ^ ^;

２進法がキーワードです

回答No.2

B-juggler

ゲーム理論かな？
ニムのゲームに似ているけど、少し違うんだね。

半分本職領域なので、ちょっと考えておきますね

ｍ（＿　＿）ｍ

一つだけ確認。山が二つで、（２，１）が勝ちなら、

相手は二個取れば負けでいいんだね。取り除かれた分も自分がとったことになるんだね。

これだけ確認させてください。補足して貰えると助かります。
　＃まぁ、でもそういうことなんだろうけど。

自分（２，１）｛にする｝　→　相手（１，１）　→自分（１，０）　これで勝ちだよね。

後は拡張すればいいのか・・・。ちょっと考えさせて。

お礼

＞取り除かれた分も自分がとったことになるんだね。

そうです。

(k,k-1)のとき、
相手が１番目の山から何個か（全部じゃなく）取った場合、(k,k)の形になるので、自分は２番目の山から１個取れば、(k,k-1)の形になります。
相手が２番目の山から何個か取った場合、自分は１番目の山から同じ数だけ取れば、(k,k-1)の形になります。
最終的に(1,0)になって、相手が最後の石を取ることになります。

問題は、山が３つ以上の場合です。

回答No.1

qaz_qwerty_me

宿題かな？

３目並べで検索すれば解法はあるような気がします