干し柿落しゲームは、takaken氏の作成した対戦ゲームで、石取りゲーム(Nim)を拡張したものです。
遊んだことがなければ、この記事を読む前に遊ぶことをおすすめします。ぜひ、自分で必勝戦略を構築してみてください。
干し柿落としゲームはNimより複雑であり、自明にGrundy数に帰着できるわけではありませんが、意外ときれいな構造を持っていることがわかりました。
まず準備として、Grundy数の雰囲気の説明から書きます（厳密な議論は行わないので、すでに知っている読者は飛ばしてかまいません）。
Grundy数の雰囲気
Grundy数は、不偏ゲームの局面に割り当てられる非負整数です。
不偏ゲームとは、二人零和有限確定完全情報ゲームであり、さらに手番がどちらのプレーヤーにあるかと無関係に有効な着手の集合が決まるものです。 有効な着手がなくなった時点で、勝利プレーヤーが決まります。
Grundy数は、不偏ゲームの局面が必勝局面であるか、どんな着手をすればよいかの判断に役立ちます。
将棋やチェスは、手番によって動かせる駒が異なりますので、不偏ゲームではありません。 囲碁やオセロも、手番によって置ける石の色が異なりますので、不偏ゲームではありません。 このように普通の対戦型ボードゲームは不偏ゲームではありません。
しかし、意外と身近に不偏ゲームは存在します。 まずは、不偏ゲームの例とその必勝法を見てみます。
不偏ゲームの例とその必勝法
21を言ったら負けゲーム
以下のようなゲームを考えます。
- 先手番プレーヤーは、1から始まる連続する自然数を1つか2つか3つ言う（つまり、「1」「1、2」「1、2、3」のどれかを言う）
- 以下、プレーヤーは交互に、直前のプレーヤーが言った数に続く連続する自然数を1つか2つか3つ言う（「1、2」「3、4、5」「6」「7、8、9」のように進行する）
- 21を言ってしまったプレーヤーの負け
これは不偏ゲームになっています。 「21を言ってしまったら負け」という部分は、「21は言えない」ということにすれば「有効な着手がないので負け」で解釈できます。
このゲームは、後手必勝です。必勝戦略は、以下の通りです。
- 相手が1つ言ったら3つ、2つ言ったら2つ、3つ言ったら1つの自然数を言う
こうすることで、自分の手番を常に4の倍数で終わらすことができます。 特に、自分は20を言うことができます。 つまり、相手は21を言わざるを得ない（有効な着手がない）状況に追い込まれます。
二山石取りゲーム
以下のようなゲームを考えます。
- 盤面には、石の山が二つあり、片方の山にはk1個、もう片方の山にはk2個の石が含まれる
- 先手番プレーヤから交互に、「石が存在する山を一つ選び、そこから1つ以上任意個の石を取り除く」を行う
- 石が取れなくなったプレーヤーの負け
これも不偏ゲームになっています。
このゲームは、k1=k2であれば後手必勝です。必勝戦略は、以下の通りです。
- 相手が選ばなかったほうの山から、相手と同じ数の石を取り除く
こうすることで、k1=k2を保ったまま相手に手番を回すことができます。 ゲームが進行し、k1=k2=0となった時、相手には有効な着手がありませんのでこちらの勝ちです。
不偏ゲームの必勝法の特徴
二つの例から一般化するのは乱暴ですが、実際に以下のような特徴があります。
- 何か指標があり、それが特定の値であるとき、必敗局面である
- 21を言ったら負けゲームでは、最後に言った自然数を4で割った余り（0で手番が回ってくると必敗）
- 二山石取りゲームでは、各山に含まれる石の数の差（0で手番が回ってくると必敗）
- 相手の任意の着手に対して、指標の変化を"打ち消す"ような着手をすることにより、必勝局面を維持できる
Grundy数
先ほど見つけた"指標"は場当たり的で、他の不偏ゲームへの適用は不可能でした。 Grundy数は、この"指標"を統一的に割り当てる方法で、いろいろと良い性質があるようです。
具体的にどういう数が割り当てられるかというと、
- 有効な着手がない場合、0が割り当てられる
- k未満の任意の非負整数tについてGrundy数がtである局面へ遷移する着手があり、かつG数がkである局面へ遷移する着手がない場合、kが割り当てられる
言い換えると、次のようになります。
- Grundy数が0である局面へ遷移する着手がない場合、その局面のGrundy数は0
- Grundy数がkの場合、k未満の任意の非負整数tについて、Grundy数がtである局面に遷移する着手がある
- 特に、Grundy数が0である局面に遷移する着手があることが重要
このことからGrundy数は、その局面が必敗局面であるときに0、必勝局面であるときに正の数が割り当てられることがわかります。
min-max法を用いてこのゲームの必勝戦略をみつけるだけであれば、正の数を使い分ける必要はありません。 しかし、その場合には最悪指数的に大きいゲーム木を探索する必要があります。
不偏ゲームの場合、いくつかの独立な不偏ゲームの和に分解できることがあります。 この時、その局面のGrundy数は分解されたゲームのGrundy数から求めることができます。 つまり、その局面のGrundy数を、探索することなく直に計算することができます。 これが、わざわざ正の数を使い分けることの利点です。
具体的には、各部分ゲームのGrundy数を二進法で表し、そのビットごと排他的論理和(xor)が全体ゲームのGrundy数になるという性質があります。
本題：干し柿落としゲーム
遊んでみましたか？ 時間がないという場合でも、自分で遊んだほうがルールが理解できると思います。 ぜひ、以下を読む前に遊ぶことをおすすめします。最初の数問だけでも、ぜひ。
干し柿落しゲームは、以下のようなゲームです。
手を動かしてみる
"勝利条件"が確定していない場合をA、"勝利条件が【最後に着手したプレーヤーの勝ち】の場合をW、勝利条件が【最後に着手したプレーヤーの負け】の場合をLと書きます。 ゲームの盤面は、山に含まれる干し柿の数を並べて書きます。山に含まれる干し柿の数は一桁の数字で表せます。
例えば、三山あり、干し柿の数がそれぞれ1、2、3であり、"勝利条件"が確定していない盤面のことを、123Aと書きます（ステージ6の初期盤面です）。
以下、ネタバレが含まれます。
山が一つの場合
- 0Wで手番を迎えた場合、相手が最後に着手しているのでこちらの負けです。
- 0Lで手番を迎えた場合、相手が最後に着手しているのでこちらの勝ちです。
0Aで手番を迎えた場合、「"勝利条件"を【最後に着手したプレーヤーの勝ち】に確定させる」着手を行えば勝ちです。相手には有効な着手がないためです。
1Wで手番を迎えた場合、最後の一つの干し柿を落として勝ちです。
- 1Lで手番を迎えた場合、最後の一つの干し柿を落とすしかなく、負けです。
1Aで手番を迎えた場合、「"勝利条件"を【最後に着手したプレーヤーの負け】に確定させる」着手を行えば勝ちです。[]の付録に詳しく説明が書かれています。
2Wで手番を迎えた場合、二つの干し柿を一度に落とせば勝ちです。
- 2Lで手番を迎えた場合、干し柿を一つだけ落とせば、必敗局面である1Lを相手に押し付けることができて勝ちです。
- 2Aで手番を迎えた場合、負けです。有効な着手により遷移できる局面は0A, 1A, 2W, 2Lですが、いずれも必勝局面だからです。この局面を作ることが勝利への道です。
山が複数ある場合
- 干し柿の数が同じ山のペアがある場合、そのペアを取り除いた局面が必勝局面であれば、元の局面も必勝局面です。
- 石取りゲーム（二山）と同様に、相手の着手と同じ着手をすることで、必勝局面を維持できるためです。
その他
- 13Aは必敗局面です。
一般化してみる
山が一つの場合
- kW(k>2)で手番を迎えた場合、全ての干し柿を一度に落とせば勝ちです（必敗局面0Wへの遷移）。
- kL(k>2)で手番を迎えた場合、干し柿を一つ残すように他全部を落とせば勝ちです（必敗局面1Lへの遷移）。
- kA(k>2)で手番を迎えた場合、干し柿を二つ残すように他全部を落とせば勝ちです（必敗局面2Aへの遷移）。
つまり、3個以上の干し柿が残っている局面で手番を迎えた場合、ルール部分に依存せず必勝です。
山が二つで、片方の干し柿が1つの場合
- 11Wで手番を迎えた場合、負けです。二山石取りゲームk1=k2=1と全く同じ状況です。
- 11Lで手番を迎えた場合、勝ちです。
11Aで手番を迎えた場合、「"勝利条件"を【最後に着手したプレーヤーの勝ち】に確定させる」ことで必敗局面11Wを相手に押し付けることができて勝ちです。
12Wで手番を迎えた場合、11Wへ遷移すれば勝てます。
- 12Lで手番を迎えた場合、1Lへ遷移すれば勝てます。
12Aで手番を迎えた場合、2Aへ遷移すれば勝てます。
13Wで手番を迎えた場合、11Wへ遷移すれば勝てます。
- 13Lで手番を迎えた場合、1Lへ遷移すれば勝てます。
13Aで手番を迎えた場合、負けです。有効な着手で遷移できる先は1A, 11A, 12A, 3A, 13W, 13Lですが、いずれも必勝局面だからです。
1kW(k>3)で手番を迎えた場合、11Wへ遷移すれば勝てます。
- 1kL(k>3)で手番を迎えた場合、1Lへ遷移すれば勝てます。
- 1kA(k>3)で手番を迎えた場合、13Aへ遷移すれば勝てます。
山が二つで、片方の山の干し柿が2つの場合
- 22Wで手番を迎えた場合、負けです。二山石取りゲームk1=k2=2と全く同じ状況です。
- 22Lで手番を迎えた場合、負けです。有効な着手で遷移できる先は12L, 2Lしかなく、いずれも必勝局面だからです。
22Aで手番を迎えた場合、2Aにするなり、22Wや22Lにするなど選択肢がたくさんありますが、いずれにせよ勝ちです。
2kW(k>2)で手番を迎えた場合、22Wへ遷移して勝てます。
- 2kL(k>2)で手番を迎えた場合、22Lへ遷移して勝てます。
- 2kA(k>2)で手番を迎えた場合、2Aへ遷移して勝てます。
これ以上頑張っても法則が見えてくるわけではないので、結論に移っていきます。
【最後に着手したプレーヤーの勝ち】ルールの時
これは石取りゲーム(Nim)とまったく同様です。
各山にある干し柿の数のxorがGrundy数となっています。
山が二つ以下の場合の表を書いてみます。
| W | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 |
| 1 | 1 | 0 | 3 | 2 |
| 2 | 2 | 3 | 0 | 1 |
| 3 | 3 | 2 | 1 | 0 |
Grundy数の定義に従っていることを確認しておきます。 あるマスの値は、そのマスの左にあるマスに存在しなく、上にあるマスにも存在しない最小の非負整数になっていることがわかります。
【最後に着手したプレーヤーの負け】ルールの時
一般的なゲームでは、着手がなくなったプレーヤーの負けです。 それに対して着手がなくなったプレーヤーの勝ちというルール、一般的なゲームにおいて負けることを目的にプレイすることと同義です。 こういった勝利条件が反転したゲームは、misére ゲームと呼ばれます。
【最後に着手したプレーヤーの負け】に確定したゲームは、mis'ereゲームになっています。
一般に、miséreゲームのGrundy数を求めることは容易ではありません。 しかし、石取りゲーム(Nim)の場合には比較的簡単に求めることができます。
山が二つ以下の場合の表を書いてみます。
| L | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 1 | 0 | 2 | 3 |
| 1 | 0 | 1 | 3 | 2 |
| 2 | 2 | 3 | 0 | 1 |
| 3 | 3 | 2 | 1 | 0 |
この場合でもGrundy数の定義に従っていることが確認できます。
そもそも、Wの場合と見比べるとほとんど変わっていないことがわかります。0L, 1L, 11Lの部分だけが異なります。 なぜ他の部分は変わらないのでしょうか。
00L,01L,10L,11L以外の局面のGrundy数を定義に従って計算する場合を考えます。 重要なのは、00L, 01L, 10L, 11Lの部分はGrundy数の位置を入れ替えただけであるという点です。 位置を入れ替えただけであるため、「左にあるマスに書かれている数∪上にあるマスに書かれている数」は集合として一致します。 よって「そのマスの左にあるマスに存在しなく、上にあるマスにも存在しない最小の非負整数」という部分に影響を及ぼしません。
山が三つ以上ある場合を考えます。 その場合、三次元、四次元、……の表を考えることになります。 Wの場合とGrandy数が変わるのは、111...111Lより内側だけになります。 その外側では、上で書いたこととまったく同じように、"集合として一致"するためGrundy数はWの場合と変化しません*1
つまり、【最後に着手したプレーヤーの負け】ルールの時、その局面のGrundy数は以下のように算出されます。
- 干し柿が2個以上残っている山がある場合、各山にある干し柿の数のxorがGrundy数になっている
- 干し柿が1個の山しかない場合、各山にある干し柿の数のxorを求め、さらに1とxorしたものがGrundy数になっている
ルールが未確定の時
山が二つ以下の場合の表を書いてみます。
| A | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 0 | 2 | 3 | 0 | 1 | 5 | 4 | 7 | 6 |
| 1 | 3 | 2 | 1 | 0 | 4 | 5 | 6 | 7 |
| 2 | 0 | 1 | 2 | 3 | 7 | 6 | 5 | 4 |
| 3 | 1 | 0 | 3 | 2 | 6 | 7 | 4 | 5 |
| 4 | 5 | 4 | 7 | 6 | 1 | 0 | 3 | 2 |
| 5 | 4 | 5 | 6 | 7 | 0 | 1 | 2 | 3 |
| 6 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 7 | 6 | 7 | 4 | 5 | 2 | 3 | 0 | 1 |
Grundy数の定義に従っていることを確認しておきます。 あるマスの値は、そのマスの左にあるマスに存在しなく、上にあるマスにも存在しなく、さらにW/Lの表の同じ位置にも存在しない最小の非負整数になっていることがわかります。
どうやらこれも排他的論理和的な雰囲気があります。 実は、以下のような法則があります。
- A33より内側は、各山にある干し柿の数のxorを求め、さらに2とxorしたものがGrundy数になっている
- それ以外は、各山にある干し柿の数のxorを求め、さらに1とxorしたものがGrundy数になっている
このようになる理由は、A33より内側の部分はGrundy数の出現位置を入れ替えただけであり、ラテン方陣である性質を維持しているからです。
なお、山が三つ以上ある場合も同様になっています。
注意点として、いくつかのゲームに分解してこの表の値をxorするのでは正しくも止まりません。 分解された各ゲームは、"勝利条件"を決めるという手を共有してしまっていて、独立していないからです。
干し柿落としゲームにおけるGrundy数の求め方
まとめます。
- 【最後に着手したプレーヤーの勝ち】ルールの時、各山にある干し柿の数のxorがGrundy数
- 【最後に着手したプレーヤーの負け】ルールの時、干し柿が2個以上残っている山があれば、各山にある干し柿の数のxorがGrundy数
- 【最後に着手したプレーヤーの負け】ルールの時、干し柿が2個以上残っている山がなければ、各山にある干し柿の数のxorと1をxorしたものがGrundy数
- ルールが未確定の時、干し柿が4個以上残っている山があれば、各山にある干し柿の数のxorと1をxorしたものがGrundy数
- ルールが未確定の時、干し柿が4個以上残っている山がなければ、各山にある干し柿の数のxorと2をxorしたものがGrundy数
干し柿落としゲームにおける必勝法
- 初期局面のGrundy数が0であれば、後手必勝
- そうでなければ、以下の条件を満たす手があるはずで、それを打ち続ければ先手必勝
- Grundy数(G)を二進法で表した時の最高位をKとおく（K=1,2,4,...）
- 【最後に着手したプレーヤーの勝ち】ルールの時、干し柿の数を二進法で表した時にKの位が1である山のうち一つを選び、その山に残っている干し柿の数をS個として、それがS xor G個になるように取り除く
- 【最後に着手したプレーヤーの負け】ルールの時、かつ干し柿が二つ以上残っている山がない場合
- 干し柿が1つの山から1つ取り除く（これしか可能な着手がないですが、勝利への道です）
- 【最後に着手したプレーヤーの負け】ルールの時、かつ干し柿が二つ以上残っている山がある場合
- ルールが確定していないとき、かつ干し柿が4個以上残っている山がない場合
- ルールが確定していないとき、かつ干し柿が4個以上残っている山がある場合
おわりに
干し柿落としゲームにおけるGrundy数を求めてみました。一般に、miséreゲームのGrundy数や、ルールが途中で変化するゲームのGrundy数を求めることは難しいです。 しかし、干し柿落としゲームにおいては、特定の境界線があり、その内側と外側で計算方法を変化させれば、よくあるxorを用いる方法を少し拡張するだけでGrundy数を求めることができるというきれいな性質があることがわかりました。
必勝法は、その境界をまたぐ操作であるかによって場合分けが発生し、複雑です。
しかし、境界は二の冪であり、境界をまたぐ手を打つべきかどうかは求めることができます。 よって、まず「境界をまたぐ手を打つべきか」を求め、その後具体的にどのような手を打つべきかを求めることで必勝法を構成することができました。
*1:余談ですが、擬ポテンシャルに似ている感じがします。
