”石取りゲーム”　ケイレスの一般化／日本大学【スタディサプリ進路】

大学・短期大学・専門学校の進学情報サイト

私立大学／東京・福島・千葉・神奈川・静岡

ニホンダイガク

”石取りゲーム”　ケイレスの一般化

数学科　教授　古津博俊

　ケイレスというゲームを石取りゲームの用語で記述すると以下になる。
（１）幾つかの石の山がある状態から始める。
（２） 2人で交互に着手する。
（３）着手は、「どれか一つの山から１個か２個の石を取り除き、その山に石が２個以上残っていればその山を２つの山に分けてもよい」とする。
（４）着手出来なかった方を負けとする。
　このゲームは最初の状態により先手必勝か後手必勝かが決まっており、それは以下のようにして判定できる。まず、0以上の整数nに対して、0以上の整数G(n)を対応させる関数を求める。求める方法は省略するがG(0)=0から順に求めていくことが出来る。このG(n)をnのG数と呼ぶ。このゲームの場合、nが正ならば出てくるG数は1から8までに限られ、nが71以上では12を周期として同じ数字の列が繰り返し並ぶ。最初の状態の各山の石の数のG数をそれぞれ２進数で表す。そして各桁ごとに排他的２進和をとり、それらがすべて0であれば後手必勝、そうでなければ先手必勝である。
　このゲームの（３）の部分を別のルールに変更したものがケイレスの一般化である。「どれか一つの山」という部分は変更せず、何個の石を取れるか、取った後の山を分けてよいか、山の石を全て取ってしまってよいかを決める。そのルールを８進小数で表すことにし、ゲームコードと呼ぶ。ケイレスのゲームコードは0.77になる。
　例えば、ゲームコードが4.32で表されるゲームを考える。これを記述すると以下のルールになる。
（１）どれか一つの山に着手する。
（２）その山から石を取らずに２つの山に分けてよい。
（３）山の石の数が1個だけならその1個を取ってよい。
（４）山の石の数が2個以上のときその山から1個を取ってよい。
（５）山の石の数が3個以上のときその山から2個を取ってよい。
　このゲームのG数は、G(0)=0でG(1)から先は周期4で1,2,0,3が繰り返される。従って、最初の状態の山の石の数が5,3,1の場合、図２のように後手必勝となる。実際の状態の推移を図１に載せておく。
＜メッセージ＞
　ゲームコードを変えることにより、無数のゲームが考えられ、その中には4.32のようにすぐに周期的になるもの、ケイレスのようにしばらくしてから周期的になるもの、そして周期的になりそうにないものが存在するため、いろいろ考えることは多い。

参考：「石取りゲームの数理」一松信（森北出版）