03. 山崩し(石取りゲーム) 必勝法 -とんでもないイカサマ技-

ここでは山崩しというゲームについて紹介しましょう. 英語では NIM (ニム) と呼ばれるゲームです. 山崩しには様々な変種が数多くありますが, まずは簡単な一山崩しから紹介します.

一山崩し

一山崩しはn枚のコイン(あるいはマッチ等何でも良い) を使って遊ぶ二人ゲームです. 2人のプレイヤー先手と後手は, 交互に山からコインを取ります. ただし毎回1枚か2枚か3枚のコインを必ず取らねばなりません. 最後のコインを取ったプレイヤー(最後に『コインを取る』という動作をしたプレイヤー) の勝ちです.

このゲームにはもちろん引き分けはありません. このゲームには, 必勝手順が分かる簡単な方法があります. 以下ではこれを解説しましょう.

実はスタート時のコインの枚数が4の倍数ならば, 後手に必勝手順があり, それ以外の場合は先手に必勝手順が存在します. ではスタート時が15枚の例でこれを解説しましょう. 先手は山からコインを取り, 残ったコインの枚数を4の倍数にします. この場合, 3枚を山から除いて12枚とします. その後は, 後手が1枚取ったら先手は3枚取り, 後手が2枚取ったら先手は2枚取り, 後手が3枚取ったら先手は1枚取ります. これによって, 先手は必ず山のコインの数が4の倍数の状態で後手に渡すことができます. 最終的に4枚の状態で後手に渡されるので, 後手が何をしても, 先手は最後のコインを取ることができます. スタート時のコインの枚数が4の倍数のときは, 後手は上記の先手と同様の手順で必ず勝つことができます.

 

三山崩し

次にもう少し難しい三山崩しについて説明しましょう.

これもコインを使って遊ぶ二人ゲームです. コインを3つの山に積みます. 1つ目の山には9枚, 2つ目の山には6枚, 3つ目の山には5枚のコインを積みます. 2人のプレイヤー先手と後手は交互に山からコインを取ります. ただしどれか1つの山を選び, そこから1枚以上コインを取らねばなりません. (何枚とってもかまいません. その山のコインをすべて取って山をなくしてもかまいません) 最後のコインを取ったプレイヤーの勝ちです.

このゲームも, 先の一山崩しのように, 必勝手順が分かる簡単な方法があります.

ゲームの最初に3つの山のコインが9枚, 7枚, 3枚となっている例を使って, この必勝手順を解説しましょう. 各山のコインの枚数を2進法で表すと, 1001, 0111, 0011となります(本来7は111, 3は11ですがすべて4桁になるように頭に0を加えています). 2進法の桁は右から順に1の桁, 2の桁, 4の桁, 8の桁となっています. 1001, 0111, 0011という3つの数字を見ると, 8の桁に1があるのは1つ(の数字, この場合は9), 4の桁に1があるのは1つ, 2の桁に1があるのは2つ, 1の桁に1があるのは2つ, 1の桁に1があるのは3つとなっています.

図1にゲームの進行の例を表してみます.

図1: 三山崩しのゲーム進行の例

図1: 三山崩しのゲーム進行の例

このとき実は先手の必勝手順があるのですが, それは, 9枚の山から5枚コインを取って4枚とすることです. これによって3つの山のコインは4枚, 7枚, 3枚となります. このときの各山のコインの枚数を2進法で表すと, 0100, 0111, 0011, となっており, 各桁の1の数はすべて偶数となっています(8の桁は0個, 4の桁と2の桁と1の桁にはそれぞれ2個の1がある).このように, 各山のコインの数を2進法で表したとき, すべての桁において1の個数が偶数個ならば, 山がバランスしていると呼ぶことにします. このゲームの必勝手順は, 常に山がバランスしている状態で相手に手番を渡すことです. 山がバランスしている状態で手番となったプレイヤー(この場合後手) は, 1つの山から石を取る限り, 山がバランスしていない状態にすることしかできません. 例えばこの場合, 4枚, 7枚, 3枚のコインからなる3つの山を渡された後手は, 4枚の山から(2枚取って)2枚とすると, 山のコインの枚数は2枚, 7枚, 3枚であり, 2進法で表すと0010, 0111, 0011 となり, 4の桁に1が1個, 2の桁に1が3個あり, バランスしていません. これ以外にも, 他のどんな取り方をしても, 1つの山から取る限り, 残った山はバランスしてない状態になってしまいます. これに対し, バランスしていない山を渡されたプレイヤー(この場合先手) は, 必ずバランスした状態に戻すことができます. 例えば2枚, 7枚, 3枚という山の場合は, 1の個数が奇数となっている最大の桁は4の桁であり, ここに1のある山, すなわち7枚のコインの山に着目します. この山からコインを取ることでバランスした山にすることができます. 他の山が2枚 0010 と3枚 0011 となっているので, 7枚からコインを取って山をバランスさせるには, 2進法で 0001 すなわち1枚とすれば良いことが分かります. よって先手は7枚の山から6枚のコインを取り1枚とします. この結果山は2枚, 1枚, 3枚となり, 2進法で表すと0010, 0001, 0011 となり山はバランスしています. 以下これを続けると, すべての山が0枚というバランスした状態で先手は後手に手番を渡すことができ, この時点で最後のコインを先手が取っているので先手の勝利となります.

 

以上からわかるように, 初期配置で山がバランスしていなければ, 先手には必勝手順があります. もし初期配置で山がバランスしていたときは, 逆に後手が(常に山がバランスした状態で先手に手番を渡すことができるので) 必勝手順を持っています.

 

逆型ゲーム

山崩しには様々な変種があり, かなり詳しく研究されています. 変種の1つに, 最後にコインを取ったプレイヤーが負けという逆型ゲームがあります. 一山崩しの逆型ゲームについて簡単に述べておきましょう.

 

このゲームでは最初のコインの枚数が, 4で割って1余る数のとき後手に必勝手順があり, それ以外は先手に必勝手順があります. 必勝手順はもとの一山崩しと同じで, 相手が1枚, 2枚, 3枚のコインを取ったときは, それぞれ3枚, 2枚, 1枚という枚数のコインを取るという対応をします. 最初のコインの枚数が, 4で割って1余る数字でないときは, 先手は1, 2, 3枚どれかの枚数のコインを取って, 山のコインの枚数を4で割って1余る数字, 例えば1, 5, 9, 13, 17といった数にします. このあと後手に対応して先手は上記の手順に従うことで必ず4枚ずつコインを減らすことができ, 最終的に1枚のコインからなる山を相手に渡し, 相手が最後の1枚を取らされて負けとなります.

 

三山崩しの逆型ゲームについても必勝手順が解明されていますが, これについては専門書等(1)を参照して下さい.

 

イカサマ技

最後に, このゲームで相手に必勝手順があると分かった時の, とんでもないイカサマ技を教えましょう.

 

それは, ゲームのコマ(コインでなくマッチが望ましい) を1つ手に隠し持ち, 1つコマを取りながら, 手の中のコマをそこに置いてくることです(コインだと音がするのでマズイ). すると, 自分は何も取っていないことになり, 先手と後手が入れ替わって, 今度は自分に必勝手順があることになります.

 

山崩しで遊ぶときは, このイカサマ技に引っ掛からないよう, 十分注意しましょう. ちなみに, これをヤレと言っているわけではありませんよ, いいですね!

(1)一松信, 『石とりゲームの数理』, 森北出版, 2003.