世界樹と魔女と迷宮の石取りゲーム


３個ずつ石をとって最後に石をとったほうが勝ち。なのだけれど意外に複雑。
一つの山だけをみると、自分が取った時点で、石を4x個残すのが必勝。
石が１０個なら、先攻で２個とればいい。
最初が８個や１２個なら後攻が勝てる。
二人だからこれ自体はさほど難しくない。

ちょっと複雑なのはこの山が３つあること。



まず山が２つの時から考える。
石の個数が同じ山の場合、先攻になってしまうと、
後攻側は別の山で先攻と同じだけ取るだけでよい。
真似戦略で、これなら後攻側が最後の石をとることになる。
先攻は負け。

次に２つの山の個数が違う場合。
個数差が３以内なら先攻がその個数分とれば、
２つの山の個数が同じになり、あとは後攻と同じことをすればいい。
１手かけてさっきのと同じ状態にしただけ。先攻が必勝。

じゃ、差が４以上の場合は？となると、
やはり真似戦略がそのまま有効。
差が４なら最後にその４多い山が残る。
４の山が一つある状態と大差ない。
つまり後攻は先攻の真似をするだけでいい。後攻が必勝。


差が５なら、先攻側が多い山から１だけとり、
残りは真似をすれば、さっきの４の時の後攻真似と同じになる。
差が６なら２だし、７なら３だ。
８なら４の時と同じで後攻側が真似するだけで、
残り８の山をやるのと同じになる。
要は差を調整できればいい。差が4xかそうじゃないかの違い。

ということは、２つの山の場合は、
相手の真似をするという戦略だけで単純化でき、
先後でそのまま勝敗がきまると言ってもいい。




で３つの山がある場合。
単純な真似戦略ができない。
または真似をできても、勝敗は残りの一つの山の数字次第となる。
なので順々に考える。


１つの山だけ残っている場合は、特に語るまでもないのだが、
これは１つの山だけになった瞬間に勝敗は決まっているということになる。
ということは２つの山になった時点で、そういう状態にしなければならない。
で、２つの山になった時点での勝敗も先ほどの通りわかっている。
つまり、３つ目の山をどういう形にして２つの山にするか。が焦点になる。

どの山が３つ目なのかは一見わからない。どれも３つ目になり得るからだ。
そこで３つの山を単純化する。4xかそうでないかだ。


仮に(３,３,４)の山があるとする。
４の山が1つあるなら、後攻が有利だ。
先攻が４を削りに来るなら、次に自分で４の山をなくせば同じ数の山２つ。
３なら同じ数だけ別の３の山を削ればよい。最後は４の山だけが残る。
これは手順が違うだけで、やることは同じ。

これが(３,４,４)なら逆に先攻が有利となる。
３を削れば２つの山の後攻と同じだからだ。

(４,４,４)は後攻。
先攻と別の山を同じ数だけ崩せばいい。
(１,１,４)になろうが、(２,２,４)になろうが、(３,３,４)と同じになるからだ。

(３,３,３)もわかりやすく先攻だ。
どの山でも削りきってしまえば２つの山の後攻と同じになるからだ。
(３,４,４)と同じ仕組み。


では(５,４,４)ならどうか。
そう。５から１を引けば(４,４,４)になる。先攻有利だ。
(５,５,４)にはどうか。
先攻が４の山に手を出せば、後攻側は次に山を消せばいい。
あとは先攻の真似で良く、後攻が勝てる。
ということは(５,５,５)はどの山でもいいから１を引けばいいので先攻。



以上から4xの山が奇数個あるなら後攻。偶数個なら先攻が有利ではないか？
という仮説が生まれる。

しかし(７,６,４)はどうだろうか。先攻が７から１を引いて、
(６,６,４)にすればあとは後攻側の真似で勝てる。
後攻側から見れば先攻負けだ。4xはどちらも奇数個だ。

仮説は否定される。4xが直接的なものではなく、
どうやら手数の問題ではないか？となる。



３以下は一手で解消できるが、４は最低でも２手かかる。
相手がどうとっても、２手で４を調整できるのが肝だ。
５以上になってしまうと、コントロールができないのだ。

(４,４,４)は手数としては絶対に６手かかる。
これが後攻勝ちであるから、その状態を１手で作れるから(５,４,４)は先攻勝ち。
(５,５,４)はまぁ別の理由で後攻勝ちではあるが、
やはりこれも偶数手で終わらせることができる。
その状態を１手でつくれる(５,５,５)は先攻で勝てるわけである。


(５,４,３)だとどうなるか。
５から１を引けば、(４,４,３)で勝ち目がないが、
２を引けば、(３,４,３)で勝てる。先攻有利。
３を引くと、(２,４,３)で後攻側は３から１を引けばよい。




これで大まかな材料は出そろった。
先後で必勝があるのならば、4xは言い換えればゼロと変わらない。
手数の問題として、どちらかが必ず２手で終わらせるように取るからだ。
実際、ゲーム中で(１２,８,８)が出たことがあったが、見込み通り後攻で勝てた。


ということは4xの山がいくつあるかが、最初に確認すべきことになる。
３つとも4xの山ならば、何のことはない後攻だ。
２つならばどうか。一手使えば4xの山を３つにできるので先攻。

１つならばどうなるか。
まずいえるのが4xの山を２つにしてしまうと負けるということだ。
しかしよく考えてみると、4xの山をゼロとみなすのであれば、
２つの山で考えるのと変わらない。
２つの山の差を4xにすることで、先攻が勝てるわけだ。
4xの山は相手に合わせてとればよいのだから、ほぼ真似でいい。
ただし、その２つの山がすでに同じ数もしくは4xの差であれば負ける。
(１０,６,４)や、(６,６,４)とかだ。
当然その場合は後攻が勝ちだ。




では4xの山がゼロならばどうすればよいだろうか。ここからがちょっと難解。

先ほどの4x山が１つの状態の勝ち確ができないようにすることが求められる。
4xの山を作らないことと、
同じ数の山を作って、相手に4x山を作らせないということだ。

当然双方がそれを考えて取っていけば、いつかは山が削られるのだが、
4xの山というのは別の見方をすると、4*ゼロ個の山である。
つまり先に山を削りきってはいけないということになる。
ということは、相手に山を取らせるためには、
4x+1である５およびその前段階の５+4xをどうとるかになる。


しかしわざわざ4x+1をとりにいく必要はなかったりする。
初期状態で4x+1個および4x個の山がない状態は限られるからだ。


例えば4x+1のある状態でいえば、
(７,６,５)のような状態が想定されるのだが、
これはどうやっても後攻勝ちになる。
(９,７,６)の状態は上から２手分多い状態なので、やはり後攻勝ち。

4x+1をとった状態という意味で、後攻が勝てるわけだ。


そして、4xおよび4x+1が入らないような初期状態では、
例えば(１１,７,６)は２つの山に4xの差があるので、
先攻が勝てることになる。(１０,７,６)も同様だ。
２つの山の差が必ず4xになるか、個数が同じになっていれば、
別の山で4xを作ればいいので、先攻勝ちである。

やはり初期状態によって先後で勝敗が決まるわけだ。



結論としては、
３つ山の個数が全部4x個なら後攻勝ち。
２つなら先攻勝ち。
１つなら、残り二つの山の差が4xなら後攻。そうじゃないなら先攻勝ち。
ゼロなら、4x+1の個数が山が一つはある状態、かつ、どの山の差も4xではない場合は後攻。
それ以外は先攻。




若干注意が必要なのは、状態に３以下が混じっているときだ。
この場合の取り方には注意が必要。
例えば７,４,３は後攻勝ちなのだが、先攻側が７から１をとってくるなら、
後攻は６から３をとらなくてはならない。
３から２をとってくるなら、７から２をとる。
一方の山が３以下になったら差の4xを埋めていくようにとっていく必要がある。
差の4xをキープする。
単純な真似ではないというところ。

あと、CPU側が最善を打たない。ということもある。
真似ができないこともあるので、結局考えなきゃいけない。


//