Ribbonim(ひも状石取りゲーム)について

Ribbonim(ひも状石取りゲーム)とは,ひも状に並んだ石(コマ,点)を順番に取っていき(消していき), 最後の1つを取って場にコマをなくしてしまった人が負け,というゲーム。 テレビ朝日の番組「堂本剛の正直しんどい」ではこれの一種(1,2,3,4,5 配置)を「ピラミッドゲーム」と呼んでいた。 これの 3,5,7配置のものを「357ゲーム」と呼ぶ人もいるが,357ゲームというのは三山崩しゲーム (ニムとも呼ばれている。3,5,7配置のひも状石取りゲームにさらに制約を加えたものと考えられる) の名称として使われていることが多いので誤解を招く。

よくある簡単な「石取りゲーム」 (subtraction game) や「山崩しゲーム」 (Nim) とこのゲームが違うところは, 場の石の「並び」に関するルールがあって,それによって1ターンで取れる石のパターンの複雑性が多少増している点。

正確なゲーム内容とルール

3 5 7 初期配置Your browser cannot render SVG. Adobe SVG Viewer Corel SVG Viewer SVG Map Toolkit Renesis Player SIE IESVG Having fun with XAML (Silverlight) and SVG 1 2 3 4 5 初期配置Your browser cannot render SVG. Adobe SVG Viewer Corel SVG Viewer SVG Map Toolkit Renesis Player SIE IESVG Having fun with XAML (Silverlight) and SVG

このようにルールはとっても簡単。 要点をズバッと言ってしまうなら,系列の中間の構成要素を取り除くことで系列を2つに分けるか, 端の構成要素を取り除くことで系列を小さくする(あるいは消失させる)か, どちらかを毎ターン行って,最後に全部消失したら終わり,ということである。

subtraction game では,同時に取ってよい石の上限が決められていて,プレイヤーは各ターンにおいて その上限以下(かつ1以上)で好きな数の石を取ってよいのだが, このゲームでは「系列」という概念が加わって,あるターンで一度に取れる石の上限がダイナミックに変化するのが特徴。 Nim も1ターンで取れる数の上限は変化するのだが,Ribbonim のほうが変化が複雑である。

最近調べたところによると,"Circular Nim" と呼ばれているゲームがあるようだ。 これは1つのサークルを初期状態としてのゲームのようで,Ribbonim と subtraction game の合いの子のような感じだ。

少々回顧

私がこのゲームに初めて出会ったのは,任天堂GAMEBOYのソフトで「忍者タートルズ」のアクションゲームがあって, その中でミニゲームとして組み込まれていた,3,5,7配置のものだ。 最初はコンピュータに負けていたが,すぐに必勝パタンを身に付けてしまった。 それ以後,このゲームでは負けたことがない。亜種があることは後に知り, 数学的な分析はその後自分の趣味で考案した。

このゲームから初期配置が三角形に見えることから,昔私は「三角石取りゲーム」とも呼んでいた。 今は,このゲームの性質が Nim に似ていることから,Ribbonim と呼んでいる。

このゲームをけしかけて相手が悔しがる表情をみるのはもう飽きたので, ここにこのゲームの真髄というか勝ち方を公開してしまう。

必勝法

このゲームの必勝法を考えることは一種の有限離散数学で,組み合わせゲーム理論と呼ばれるカテゴリに含まれるはず。 ここでは,2人プレイに限定する。これは二人零和有限確定完全情報ゲームである。 そしてこのゲームには,ルール上,引き分けはあり得ないので,先手必勝か後手必勝かのどちらかである。

上記のルールからして,このゲームには「ターン」の概念が存在する(自分の番,相手の番,というやつ)。 各ターンには操作が実行される前の状態(開始状態)があり,プレイヤーの選択(意思決定)した操作が実行され, 実行後の状態(終了状態)ができあがる(これが次のターンの開始状態である)。 このゲームでの状態とは,その時その場での石の配置パタンである。これを本項では「フィールド」と呼ぶことにする。 将棋で言うところの盤面である(ちなみに盤面は英語でboard, surfaceと呼ばれている)。 すると,開始フィールドに対して操作を加えて終了フィールドを作るのがターンであると言える。 以後は,単に「フィールド」と言う場合は,開始フィールドを指すものとする。

2人プレイの系列石取りゲーム全体において存在し得るすべてのフィールドを, 「勝ちフィールド」と「負けフィールド」に二分することができる。 「勝ちフィールド」(「勝ち開始フィールド」または「必勝フィールド」)とは,そのフィールドを開始フィールドとしてターンが回ってきたプレイヤーが 最善手をとることで必ずゲームに勝てる,というフィールドのこととする。 「負けフィールド」(「負け開始フィールド」または「必敗フィールド」)とは,「勝ち開始フィールド」以外のすべてのフィールドである。 俗に「必勝パタン」という言葉があるが,この言葉をこの手のゲーム(石取りゲーム,五目並べ,リバーシなど)で使うと 開始フィールドのことを指すのか終了フィールドのことを指すのかがわかりにくくなるため,使用しないでおく。 「勝ちターン」は「勝ち開始フィールド」を開始フィールドとするターン, 「負けターン」は「負け開始フィールド」を開始フィールドとするターン,とする。

≪ 証明のためにもう少し厳密な定義 ≫

  1. 石が1つもないフィールドは,勝ちフィールドである。
  2. それにどのような1手を加えても勝ちフィールドに移行するようなフィールドは,負けフィールドである。
  3. それに1手加えることで負けフィールドに移行するような手が1つ以上存在するフィールドは,勝ちフィールドである。

≪ 勝ちフィールドと負けフィールドしか存在しないことの証明 ≫

勝ちフィールドでも負けフィールドでもないフィールドが存在すると仮定する(これを中立フィールドと呼ぶ)。

ゲームのルールより,フィールド中の石の数は有限である。 また,石が1つもないフィールド以外は,適用可能な手が1つ以上存在することは自明である。

上記の定義 3. より, すべての中立フィールドについて,それに加えることが可能な手の集合の中には, 負けフィールドへ移行するような手は含まれていない。 従って,任意の中立フィールドに加えることが可能な手の集合は,勝ちフィールドへ移行する手か 中立フィールドへ移行する手で構成されている。・・・ (A)

上記の定義 2. より, すべての中立フィールドについて,それに加えることが可能な手の集合には, 勝ちフィールド以外のフィールドへ移行する手が1つ以上含まれている。 従って,(A) と合わせると,任意の中立フィールドに加えることが可能な手の集合には, 中立フィールドへ移行する手が必ず1つ以上含まれている。

ある任意の中立フィールドをXとする。そしてそれに加えることが可能な手のうち 中立フィールドへ移行する手のどれか1つを適用して移行した先の中立フィールドをYとする。 ゲームのルールより,すべての手はフィールドの石の総数を減らすので,X の石の総数よりも Y の石の総数のほうが必ず少ない。 故に,すべての中立フィールドについて,それよりも石の総数が少ない中立フィールドへ移行する手が必ず存在する。・・・ (B)

任意の中立フィールドに対して,(B) に該当する手のみを適用して中立フィールドから中立フィールドへの移行を続けると, フィールド中の石の総数は有限であるため,いつか必ずフィールドの石の総数がゼロになる。 従って,石が1つもないフィールドは中立フィールドである。・・・ (C)

(C) は定義 1. と矛盾する。よって背理法により,最初の仮定が誤りであり, 勝ちフィールドでも負けフィールドでもないフィールドは存在しない。■

このゲームでは,「勝ちターン」が回ってきたプレイヤーが最善手をとると, 以降もそのプレイヤーは必ず「勝ちターン」であり,逆に相手プレイヤーは必ず「負けターン」である。 つまり,このゲームでの最善手とは,自分のターンに勝ちターンを連続させる手であり,それが必勝法である。

構成的方法

まず,基礎的な勝ちターンを考える。理解のために,1つずつ手順を追ってその理屈を説明しよう。

まず,ゲームのルール(最後の1個を取ったら負け)からして, 残り1個にして相手のターンにまわせば勝てるし, 勝つためにはそうしなければならない(相手の合理性を仮定すれば。←ゲーム理論的仮定)。

この最後の1個を取らされるターンを T1 とし, 取った後の何もない状態(ゲームとしてはターンは無いが形式的に)をT0, T1から一手ずつさかのぼっていったときの各ターンを T2, T3, ・・・と表記する。 偶数が勝ちターンで,奇数が負けターンである。もちろん,自分が必ず勝つためには,偶数ターンが自分のターンでなければならない。 上記の定義 2.,定義 3. を参考にして,T1 はどのような手を取っても必ず T0 に移行するフィールドのみで構成されるものとする。 また,T2 は T1 へ移行する手が1つ以上存在するフィールドのみで構成される。T3 と T2,T4 と T3,・・・の関係も同様。 勝ちターンのプレイヤーは負けターンに移行する手の中でも(どれでも必勝であることに変わりはないが)最短で勝てるものを選択し, 負けターンのプレイヤーは(どれでも必ず負けるが)負けるまでのステップが最も長くなる手を選択するものと考える。 そうすると,上の定式化での Tm (mは偶数) は「最長でも m 手で勝てるフィールド」の集合を意味し, Tn (nは奇数)は「負けるまでに最長 n 手かけさせることができるフィールド」の集合を意味する。

この Ti (i は 0以上の自然数) を順番に構成していく。 以下,o でエレメント(石),/ でシーケンス(系列)の区切り,を表す。 * の用法は,正規表現のそれと似て,ゼロ個以上の o である。 1行で,フィールドを1つ表す。3行あれば3種類のフィールドがあり得るということ。 # は行コメント。

もちろん T0 のフィールドは

         

であり,すべての可能な T1 は

o *        

だが,終了フィールドが必ず T0 になる T1 は

o        # T1

のみである。すると,T2 であり得る勝ちターンは,

o / o *
o o *

である。これ以外では1手では勝てない。ここから,1手戻ってあり得る開始フィールドは

o / o * / o *
o * / o o *
o o o *

のいずれかであるが,T1, T2に含まれるものを除くと,

o / o * / o *
o o * / o o *

また,これらフィールドを反復できるもの(取った後にいずれT3のどれかに当てはまるフィールド) では次のターンで T2 にならないので,それらを除くと,T3は

o / o / o     # T3a
o o / o o     # T3b

の2つである。これらのどちらかで相手に渡せば(相手の開始フィールドであれば)必勝。

よって,同様にT4では,あり得るフィールドからT1~3に含まれるものを除いて,

o / o / o / o *
o / o / o o *
o o / o o / o *
o o / o o o *

が勝ちフィールドである。

これを1手戻すと

o / o / o / o * / o *
o / o / o * / o o *
o o / o o / o * / o *
o o / o o / o o *
o / o * / o o o *
o o / o * / o o o *
o / o o * / o o *
o / o o o o *
o o / o o o o *
o o * / o o o *
o * / o o o o o *

があり得るが,T1~4に含まれるフィールドを除くと,T5は

o / o / o / o * / o *
o / o / o o * / o o *
o o / o o / o * / o *
o / o o / o o o *
o / o o o * / o o o *
o o / o o o * / o o o *
o o o * / o o o *

のどれか。必ず T4 に移行するフィールドに限定すると,

o / o / o / o / o     # T5a
o / o / o o / o o     # T5b
o / o o / o o o       # T5c
o o o / o o o         # T5d

となり,これらのどれかで相手に渡せば必勝。ここまでは簡単。

T6では

o / o / o / o / o / o *
o / o / o / o / o o *
o / o / o o / o o / o *
o / o / o o / o o o *
o / o o / o o / o o *
o / o o / o o o / o *
o / o o / o o o o *
o / o o o / o o o *
o o / o o o / o o o *
o o o / o o o / o *
o o o / o o o o *

が勝ちフィールドとしてあり得る。

T7 では,

o / o / o / o / o / o / o   # T7a
o / o / o / o / o o / o o   # T7b
o / o / o / o o / o o o     # T7c
o / o / o o o / o o o       # T7d
o o / o o / o o / o o       # T7e
o o o o / o o o o           # T7f

とまあ,こんな感じ。 ふつうにプレイしていると,この辺で読まなければならないフィールド数が作業記憶容量を超えてくるので, これらのT7までのフィールドを覚えているとたいていの人には勝てる。 自分が取った後これら奇数ターンが相手に回るようにゲームを進めるべし。

手動で追っているとキリがないので, あり得るフィールドを列挙するプログラムを書いてそいつに列挙させることにする。 このプログラムはJavaScriptで強引に書いただけだから, 閲覧環境によっては非常に重い(場合によってはブラウザが固まる)かもしれないので,試す人は覚悟すべし。 できれば別プロセスで開くのがよい。応答しないとか言われてもあきらめるな。 プログラムは Java appletに移植し,JavaScript版は削除した。適切なVMを要するので注意。

これによると,357初期配置は先手必勝である(T14)。 12345初期配置も先手必勝である(T14)。 ただし,必勝のためには(初期配置から完読みできる人以外は)多少とも勝ちフィールドを覚えておく必要があるので, 単純な数かぞえゲームやn山崩しゲーム(ニム)ほど勝つのも簡単ではない。

変形ルール

通常は,Ribbonim は misère game であるが, 「場に石をなくした人が勝ち」という逆のルール(normal play game)を採用する場合もある。 しかし,これであっても,数学的な性質はほとんど変わらない。 また,いくつかの理由から,こちらのほうが必勝するのが簡単である。

T0 は負けターン,奇数が勝ちターン,偶数が負けターンであり,T1は,

o *

1手加えて,

o * / o *
o o *

であり,上と同様に,不適当なフィールドを除くと,

o / o     # T2

同様に,T3は

o / o / o *
o / o o *

T4は

o / o / o / o   # T4a
o o / o o       # T4b

T5は

o / o / o / o / o *
o / o / o / o o *
o o / o o / o *
o o / o o o *

T6は

o / o / o / o / o / o   # T6a
o / o / o o / o o       # T6b
o / o o / o o o         # T6c
o o o / o o o           # T6d

以降を知りたければ, こちらも上記のあり得るフィールドを列挙するプログラムで列挙できるので, 試してみる。

定理

TBD

結び

参加人数が3人以上になると,零和にしたとしても,もはやこの種のゲームは ロンドンブーツ1号2号の番組でやっていたみたいに社会的交渉や集団行動の部類に入ってしまい, 現実的に数学的な読みが可能な範疇ではなくなる。 (必勝法がないとは言わないが。)

多人数プレイは横におくとしても上に解説した2人プレイについては, この Ribbonim は単なる山崩しゲーム (Nim) に比べて格段におもしろいし, このゲームは身近な道具で簡単に始められるので, 時間つぶしや気晴らしにやってみてはどうだろうか。

  1. タイトルを変更,それに伴って内容書き換え on 2007-07-03
  2. first written on 2005-09-28