こんにちは。今回は攻略記事となります。
攻略するゲームはこちら、iOS/Android向けにリリースされているアプリ、「棒消しボンバー！」になります。以前レビューした「おもいをつたえるプログラム」のGigabitさん作成です。
ダウンロードは以下からどうぞ。
iOS版/Android版
なお当然ですが、本記事はネタバレが多数ありますので、自分で勝ち方を考えたい方は見ないようにしてください。
さて、ルールを簡単に説明しましょう。こんな感じです。
さて、今回の記事はこのゲームの爆弾なしルールにおける必勝法を解説することを目的としています。(爆弾ありルールの場合、爆弾がどこに行くかが不明なため必勝法はありません)
分かりやすい書き方を心がけますが、最低限必要な知識としてビットごとの排他的論理和という概念が必要なので先に解説します。高校の数学か情報くらいの知識があると分かりやすいと思います。
この2進法の一桁をビットと呼びます。
いくつか例を挙げましょう。10進法に直すとどうなるかをかっこ内で記載してます。
このビットごとの排他的論理和には重要な性質がいくつかあります。まずはxをどのような整数としてもx⊕x=0となることです。また、普通の足し算と同じように、計算の順番を入れ替えても結果は変わらず、0との排他的論理和をとっても値は変わりません。これらの性質はこのゲームを解析するのに大切な役割を果たします。
ここで少しここだけの用語を導入します。同時に消すことができる棒のまとまりを、”塊”と呼ぶことにしましょう。1つのみの棒からなる塊を”孤立した塊”、2つ以上の棒からなる塊を”大きな塊”とします。
さて、これで準備も整ったので結論を述べましょう。本ゲームの必勝戦略は以下の通りです。
文章では非常に分かりにくいので具体例を見ていきましょう。
以下は上の戦術が必勝法であることの証明になります。
この手の議論に慣れていない方には難しく感じられると思いますが、興味のある方はぜひ読んでみてください。
今回も1つ前提知識が必要になりますのでその解説から入ります。数学的帰納法です。
P(n)を自然数nに関する性質(なんでもいい)とします。このP(n)について以下のことが分かっているとします。
例を挙げましょう。
P(n)を、「1+2+4+…+2n = 2n+1-1」という主張とします。
n=1のときP(1)は「1+2 = 4-1」となってこれは明らかに正しいです。
またP(k)が正しいと仮定します。すると1+2+4+…+2k = 2k+1-1が成り立ちますが、
1+2+4+…+2k+1 = (1+2+4+…+2k)+2k+1 = 2k+1+2k+1-1 = 2(k+1)+1-1
が成り立ち、これはまさにP(k+1)が正しいことを示しています。以上のことより、すべての自然数nに対してP(n)が正しいことが示せました。
また、数学的帰納法はよくドミノ倒しに例えられます。
いちばん最初のドミノが倒れる(P(1)が正しい)ことが分かり、さらにk番目のドミノが倒れたら必ずk+1番目のドミノも倒れる(P(k)が正しいならばP(k+1)も正しい)のが分かっているならば、ドミノは止まることなく倒れ続け、全て倒れることが分かるでしょう。
それでは証明に移っていきたいと思います。
まずは孤立した塊しか存在しない場合です。これは明らかでしょう。一気に2個以上の棒を消すことはできませんから、お互いに1つずつ消すほかなく、奇数個の場合先手の人が最後の1個を消すことになり、偶数個の場合後手の人が最後の1個を消すことになります。
大きな塊が1個の場合も簡単です。大きな塊から1個を残すか全て消すかを適切に選べば、孤立した塊のみが奇数個ある状況に相手を追い込むことができます。
難しいのは大きな塊が2個以上ある場合です。次のような段階に分けて証明します。
g'=y1⊕y2⊕x2⊕x3⊕…⊕xn
=y1⊕y2⊕(x1⊕x1)⊕x2⊕x3⊕…⊕xn x⊕x=0という性質を使いました
=y1⊕y2⊕x1⊕(x1⊕x2⊕x3⊕…⊕xn) 計算の順序を入れ替えました
=y1⊕y2⊕x1 元の状態のgrundy数が0であることを使いました
となることが分かります。
ここでg'が0であったとして矛盾することを示しましょう(背理法)
g'=0とすると、0=y1⊕y2⊕x1の両辺に⊕x1して
x1=y1⊕y2が分かります。ここでx1個の棒がある塊から1個以上の棒を消してy1個、y2個の塊になったのですからx1>y1+y2であることが分かります。(この＋は普通の足し算です)
ところで、⊕の定義は繰り上がりを無視した足し算だったため、⊕の結果が普通の足し算より大きくなることはありません。したがって
x1>y1+y2≧y1⊕y2となりx1=y1⊕y2に矛盾します。
以上のことから、grundy数が0の状態からはどのような手を選んでもgrundy数が1以上になってしまうことが示せました。
gを2進法で表したときの最も上の位に注目します。この位は1になっているわけですが、⊕では繰り上がりがないためxたちのどれかが同じ位で1になっていることが分かります(その位が全て0だとしたらそのビットごと排他的論理和であるgのその位も0になるはずです)。そのうちの1つを、必要ならば添え字を入れ替えてx1とします。
x1⊕g=yとします。この時x1の山の左端からx1-y個の棒を消すことで状態が(y,x2,...,xn)となり、grundy数を0にすることができます。
x1⊕x2⊕x3⊕…⊕xn=g
g⊕x1⊕x2⊕x3⊕…⊕xn=g⊕g 両辺に⊕gしました
(g⊕x1)⊕x2⊕x3⊕…⊕xn=0 g⊕g=0という性質を使いました
y⊕x2⊕x3⊕…⊕xn=0 (g⊕x1)を先に計算しました
となり示せました。
以上でgrundy数が1以上の状態からは1手でgrundy数を0にできることが示せました。
仮に大きな塊が1個のみの状態になったとして、その状態を(x1,x2,...,xn)とします。並び替えることで大きな塊に対応するものをx1としても良いです。残りは孤立した塊なのでx2以降は全て1です。x1は大きな塊(すなわちx1≧2)なので、1の位よりも左のどこかの位で1になっています。この時他のどのxたちもその位は0であるため、排他的論理和の計算規則よりgrundy数gもその位が1になります。これはg=0に矛盾します。したがってこのようなことは起こりえず、iiの手順に従ってgrundy数を0にすれば大きな塊が2個以上の状態を保つことになることが示せました。
P(k)が正しいとします。この時P(k+1)が正しいことを示します。
盤面に残っている棒の本数がk以下の時はP(k)より必勝戦略は正しいので、ちょうどk+1本の棒が残っている場合のみを考えればOKです。grundy数が0の場合、大きな塊が1個になるかgrundy数が1以上になるような手しか打てません。1個以上の棒を消さなくてはならないので、その状況で盤面に残っている棒の個数はk個以下です。したがってP(k)の仮定より必勝戦略は正しいです。
grundy数が1以上の場合、ii、iiiで示した手を打つことによってgrundy数が0の状態にすることができます。この時盤面に残っている棒の個数はk個以下なので、P(k)より必勝戦略は正しいです。以上より数学的帰納法を用いてすべてのnについてP(n)が正しいことが分かりました。これはつまり、盤面に残っている棒の個数が何個であっても必勝戦略は正しいということなので、示したかったことがようやく示せました。
これで本記事で紹介した必勝戦略の正しさを証明できました。
一応気を付けてはいますが、万一誤りがあった場合は教えてください。
ちなみに、本記事の必勝戦略の思いつき方ですが、ニムという有名なゲームからの類推になります。詳細は割愛しますが、ニムは本ゲームからすでに消された棒を飛び越えて消すことができないというルールをなくし、勝敗を反転(最後の1個を消した人の勝ち)としたゲームです。ニムについてはgrundy数が0になるような手が必勝戦略であることが有名な事実なので、それを本ゲームに応用してみました。詳細はWikipediaなどをご覧ください。
今回はかなり理屈っぽい話になりました。
次回はまたゲームレビューに戻りたいと思います。それでは。
攻略するゲームはこちら、iOS/Android向けにリリースされているアプリ、「棒消しボンバー！」になります。以前レビューした「おもいをつたえるプログラム」のGigabitさん作成です。
ダウンロードは以下からどうぞ。
iOS版/Android版
なお当然ですが、本記事はネタバレが多数ありますので、自分で勝ち方を考えたい方は見ないようにしてください。
さて、ルールを簡単に説明しましょう。こんな感じです。
- 盤面にいくつかの棒が並んでいる
- 2人のプレイヤーが交互に棒を消していき、最後の1個を消した方が負け
- 一度に消せる棒の数に制限はないが、同時に消せるのは同じ段にある棒に限る
- すでに消された棒をまたいで消すこともできない
- (爆弾ありルールの場合)盤面に存在している爆弾に触っても負け
さて、今回の記事はこのゲームの爆弾なしルールにおける必勝法を解説することを目的としています。(爆弾ありルールの場合、爆弾がどこに行くかが不明なため必勝法はありません)
分かりやすい書き方を心がけますが、最低限必要な知識としてビットごとの排他的論理和という概念が必要なので先に解説します。高校の数学か情報くらいの知識があると分かりやすいと思います。
ビットごとの排他的論理和に関する解説(クリックで展開)
2進法の解説
コンピュータの中では、数字は全て0と1のみで表されているというのを聞いたことがある方も多いでしょう。我々が普段使っている数字は10進法で表記されています。1,2,3...と数えていって、9の次で繰り上がりをして10になるため10進法と呼ばれます。2進法は2で繰り上がりが起こります。1の次ですぐに繰り上がりが起こるので10。次は11。その次はまた繰り上がりが起こりますが、さらに次の位も繰り上がるので結局100になります。このような体系で表記された数字が２進数です。 10進法と2進法を比較すると下の表のようになります。| 10進法 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 2進法 | 1 | 10 | 11 | 100 | 101 | 110 | 111 | 1000 | 1001 | 1010 |
ビットごとの排他的論理和
ビットごとの排他的論理和とは、2進法で表記してさらに繰り上がりが起こらないような変わった足し算のことです。例えば1+1は我々の慣れ親しんだ10進法なら2ですが、２進法では繰り上がりが起こって10になります。そこで繰り上がりが起こったところを無視すると0になります。これが排他的論理和です。この記事では、記号⊕で表すことにします。ちなみに、多くのプログラミング言語では記号^で表します。いくつか例を挙げましょう。10進法に直すとどうなるかをかっこ内で記載してます。
- 1⊕1=0 (1⊕1=0)
- 1⊕0=1 (1⊕0=1)
- 100⊕110=10 (4⊕6=2) 3桁目の繰り上がりを無視しています
- 110⊕101=11 (6⊕5=3) 3桁目の繰り上がりを無視しています
- 1011⊕111=1100 (11⊕7=12) 1,2桁目の繰り上がりを無視しています
このビットごとの排他的論理和には重要な性質がいくつかあります。まずはxをどのような整数としてもx⊕x=0となることです。また、普通の足し算と同じように、計算の順番を入れ替えても結果は変わらず、0との排他的論理和をとっても値は変わりません。これらの性質はこのゲームを解析するのに大切な役割を果たします。
さて、これで準備も整ったので結論を述べましょう。本ゲームの必勝戦略は以下の通りです。
|
文章では非常に分かりにくいので具体例を見ていきましょう。
 | これは初期状態です(青のターンとはプレイヤーのターンです。赤がCPUです)。 この状態は大きな塊が2つ以上あるのでgrundy数を計算します。その値は 1⊕2⊕3⊕4⊕5⊕6=7>0 となるので先手必勝です。例えば一番下の段から5個の棒を消すとgrundy数を 1⊕2⊕3⊕4⊕5⊕1=0 とすることができ、必勝手順(の1つ)となります。 grundy数の値を0にする手の見つけ方については下記で紹介します。 |
 | 続いてこちらの場合、大きな塊が1つだけ残っています。 孤立した塊は2個で偶数ですので、大きな塊から1つだけ棒を残して消し、相手に手番を渡すのが必勝戦略になります。 |
 | この状態は大きな塊が2つ以上あるのでgrundy数を計算します。 1⊕3⊕2⊕3⊕1⊕2=0 となるので、残念ながらこの局面は(相手が適切な手を打つと)必敗です。勝ち目はありません。 |
以下は上の戦術が必勝法であることの証明になります。
この手の議論に慣れていない方には難しく感じられると思いますが、興味のある方はぜひ読んでみてください。
今回も1つ前提知識が必要になりますのでその解説から入ります。数学的帰納法です。
数学的帰納法の解説
私の時は高校の数学Bで習いました。自然数に関する性質を証明するときの強力な道具となります。ここで、自然数とは0より大きい整数のこととします。P(n)を自然数nに関する性質(なんでもいい)とします。このP(n)について以下のことが分かっているとします。
- P(1)は正しい
- P(k)が正しいとしたら、P(k+1)も正しい
例を挙げましょう。
P(n)を、「1+2+4+…+2n = 2n+1-1」という主張とします。
n=1のときP(1)は「1+2 = 4-1」となってこれは明らかに正しいです。
またP(k)が正しいと仮定します。すると1+2+4+…+2k = 2k+1-1が成り立ちますが、
1+2+4+…+2k+1 = (1+2+4+…+2k)+2k+1 = 2k+1+2k+1-1 = 2(k+1)+1-1
が成り立ち、これはまさにP(k+1)が正しいことを示しています。以上のことより、すべての自然数nに対してP(n)が正しいことが示せました。
また、数学的帰納法はよくドミノ倒しに例えられます。
いちばん最初のドミノが倒れる(P(1)が正しい)ことが分かり、さらにk番目のドミノが倒れたら必ずk+1番目のドミノも倒れる(P(k)が正しいならばP(k+1)も正しい)のが分かっているならば、ドミノは止まることなく倒れ続け、全て倒れることが分かるでしょう。
まずは孤立した塊しか存在しない場合です。これは明らかでしょう。一気に2個以上の棒を消すことはできませんから、お互いに1つずつ消すほかなく、奇数個の場合先手の人が最後の1個を消すことになり、偶数個の場合後手の人が最後の1個を消すことになります。
大きな塊が1個の場合も簡単です。大きな塊から1個を残すか全て消すかを適切に選べば、孤立した塊のみが奇数個ある状況に相手を追い込むことができます。
難しいのは大きな塊が2個以上ある場合です。次のような段階に分けて証明します。
- grundy数が0の場合、次にどのような手を打ってもgrundy数を0にすることができない
- grundy数が1以上の場合、上手い手を選ぶことでgrundy数を0にすることができる
- iiの手によって大きな塊が1個以下になってしまうことはない
- 上の3つから数学的帰納法によって必勝戦略の正しさを証明する
「grundy数が0の場合、次にどのような手を打ってもgrundy数を0にすることができない」の証明
grundy数が0である盤面において、塊に何個の棒が含まれているかを表す数の組を(x1,x2,...,xn)とします。今後このような数の組を、”盤面の状態”と呼ぶことにします。今、適当な手を考え、それが消した山に対応する数字がx1であるとします(そうでなかった場合、適当に山を並び替えて添え字を入れ替えればよいです)。その手の結果x1がy1とy2になったとします(消した部分の左と右に塊が残ることがあるので2つの数になることがあります。塊が1つのままだったり塊ごと全て消した場合には、y1やy2を0とすることで表現できます)。この状態のgrundy数g'を考えてみましょう。g'=y1⊕y2⊕x2⊕x3⊕…⊕xn
=y1⊕y2⊕(x1⊕x1)⊕x2⊕x3⊕…⊕xn x⊕x=0という性質を使いました
=y1⊕y2⊕x1⊕(x1⊕x2⊕x3⊕…⊕xn) 計算の順序を入れ替えました
=y1⊕y2⊕x1 元の状態のgrundy数が0であることを使いました
となることが分かります。
ここでg'が0であったとして矛盾することを示しましょう(背理法)
g'=0とすると、0=y1⊕y2⊕x1の両辺に⊕x1して
x1=y1⊕y2が分かります。ここでx1個の棒がある塊から1個以上の棒を消してy1個、y2個の塊になったのですからx1>y1+y2であることが分かります。(この＋は普通の足し算です)
ところで、⊕の定義は繰り上がりを無視した足し算だったため、⊕の結果が普通の足し算より大きくなることはありません。したがって
x1>y1+y2≧y1⊕y2となりx1=y1⊕y2に矛盾します。
以上のことから、grundy数が0の状態からはどのような手を選んでもgrundy数が1以上になってしまうことが示せました。
grundy数が1以上の場合、上手い手を選ぶことでgrundy数を0にすることができる」の証明
盤面の状態を(x1,x2,...,xn)として、そのgrundy数をgとします。gを2進法で表したときの最も上の位に注目します。この位は1になっているわけですが、⊕では繰り上がりがないためxたちのどれかが同じ位で1になっていることが分かります(その位が全て0だとしたらそのビットごと排他的論理和であるgのその位も0になるはずです)。そのうちの1つを、必要ならば添え字を入れ替えてx1とします。
x1⊕g=yとします。この時x1の山の左端からx1-y個の棒を消すことで状態が(y,x2,...,xn)となり、grundy数を0にすることができます。
y⊕x2⊕x3⊕…⊕xn=0の証明
これは⊕に慣れていれば簡単です。x1⊕x2⊕x3⊕…⊕xn=g
g⊕x1⊕x2⊕x3⊕…⊕xn=g⊕g 両辺に⊕gしました
(g⊕x1)⊕x2⊕x3⊕…⊕xn=0 g⊕g=0という性質を使いました
y⊕x2⊕x3⊕…⊕xn=0 (g⊕x1)を先に計算しました
となり示せました。
x1の山からx1-y個消せる(0<x1-y≦x1)ことの証明
gの一番上の位とx1の同じ位はどちらも1であることが先ほどの議論より判明しています。したがってg⊕x1の結果その位は(繰り上がりがなくなるため)0になります。そこよりも下の位ではいろいろと値が変わっているかもしれませんが、一番上の位で小さくなっているので、x1>g⊕x1=yであることが分かります。この式を変形し、y≧0を考慮すれば0<x1-y≦x1が得られます。「iiの手によって大きな塊が1個以下になってしまうことはない」の証明
1度に2個以上の塊から棒を消すことはできないため、大きな塊が2個以上の状態からいきなり0個になることはありません。したがって大きな塊が1個の状態にならないことを示せばよいです。仮に大きな塊が1個のみの状態になったとして、その状態を(x1,x2,...,xn)とします。並び替えることで大きな塊に対応するものをx1としても良いです。残りは孤立した塊なのでx2以降は全て1です。x1は大きな塊(すなわちx1≧2)なので、1の位よりも左のどこかの位で1になっています。この時他のどのxたちもその位は0であるため、排他的論理和の計算規則よりgrundy数gもその位が1になります。これはg=0に矛盾します。したがってこのようなことは起こりえず、iiの手順に従ってgrundy数を0にすれば大きな塊が2個以上の状態を保つことになることが示せました。
上の3つから数学的帰納法によって必勝戦略の正しさを証明する
nに関する主張P(n)を、「盤面に残っている棒の本数がn以下であるようなすべての状態に対して、上の必勝戦略は正しい」とします。P(1)が正しいのは明らかです。棒が1本だけ存在している状態というのは明らかに先手の負けです。P(k)が正しいとします。この時P(k+1)が正しいことを示します。
盤面に残っている棒の本数がk以下の時はP(k)より必勝戦略は正しいので、ちょうどk+1本の棒が残っている場合のみを考えればOKです。grundy数が0の場合、大きな塊が1個になるかgrundy数が1以上になるような手しか打てません。1個以上の棒を消さなくてはならないので、その状況で盤面に残っている棒の個数はk個以下です。したがってP(k)の仮定より必勝戦略は正しいです。
grundy数が1以上の場合、ii、iiiで示した手を打つことによってgrundy数が0の状態にすることができます。この時盤面に残っている棒の個数はk個以下なので、P(k)より必勝戦略は正しいです。以上より数学的帰納法を用いてすべてのnについてP(n)が正しいことが分かりました。これはつまり、盤面に残っている棒の個数が何個であっても必勝戦略は正しいということなので、示したかったことがようやく示せました。
一応気を付けてはいますが、万一誤りがあった場合は教えてください。
ちなみに、本記事の必勝戦略の思いつき方ですが、ニムという有名なゲームからの類推になります。詳細は割愛しますが、ニムは本ゲームからすでに消された棒を飛び越えて消すことができないというルールをなくし、勝敗を反転(最後の1個を消した人の勝ち)としたゲームです。ニムについてはgrundy数が0になるような手が必勝戦略であることが有名な事実なので、それを本ゲームに応用してみました。詳細はWikipediaなどをご覧ください。
今回はかなり理屈っぽい話になりました。
次回はまたゲームレビューに戻りたいと思います。それでは。
コメント