パネル系ゲームの攻略を考える

ウラルさんのゲーム

この手のゲームはいろいろな研究ができて楽しいですよね。

研究してみる

具体的には以下のものについて考えたいと思います。

  • 完全性
    • 全ての初期配置でクリア可能かどうか
  • 最小手数
    • 最小性をどうやって担保するか
  • 計算複雑性
    • 最短手数を計算するのにどのくらい時間がかかるか

語句の定義

これが曖昧だと語句でこんがらがるので、以下のように定義します。

  • ある一つのパネルを押して盤面を変化させることを “変換” とする
  • 最初に与えられた4×4の盤面を “初期行列” とする
  • 任意の時点での4×4の盤面を “行列” とする
  • 何もしない変換を “単位変換” とする
  • 何もしない変換の行列を “単位行列” とする(全ての値が0)

まずこのゲームをどうやって数学の世界に落とし込むかということが重要になります。

これ自体は簡単で青いパネルを1、白いパネルを0として考えればいいわけです。

つまり、初期盤面は以下のように表現できるわけです。

数学的な表現に落とし込む

パネルを押した時に押したパネルの周囲のパネルも反転するのですが、これをどうやって数学的な表現に直せばいいでしょうか?

計算空間

ここで、以下のような計算空間(これは正しい表現ではない)を考えます。

一見すると不思議な計算に見えますが、こういうヘンテコな計算の世界を定義するわけです。このヘンテコな計算方法はXOR(排他的論理和)として知られています。

パネルを押して、その周囲のパネルの色が反転するというのをこの計算空間を使って求めます。押したときに反転するパネルを1、そうでなければ0という風に考えます。

例えば、初期行列から左上隅のマスを押したときに次にどのような状態になるかは以下のように求めることができます。

左上隅のマスを押したときの変化

これを用いることでマスを押したときに次にどのような状態になるかが計算できるわけですね。

以後、初期行列を変換した(初期行列に足された)行列のことを “変換行列” と呼ぶことにします。

対称性

パネルの押し方と、押したときの反転パネルの表現ですが例えば一番上の列ですと四通りの押し方があるように思えます。

実質二通り

ところがこれらは対称のものが存在するので、実際には二通りだけ考えれば良いことがわかります。

実質二通り

二列目も同様に四通りありますが、対称なのでこれも二通りだけ考えれば問題ありません。また、これ以降は上下に対称なのでやはり考える必要がありません。

よって、考えるべき基本的な変換行列は次の四つしかないことがわかります。

ちなみに回転も認めれば更に減って以下の三通りだけ考えればいいのだ!

基本の変換行列

完全性

さて、このゲームが完全であるかどうかについてウラルさんが研究してくださったので、その成果を発表したいと思います。

どんな初期行列からでもクリアできるかというのは「与えられた任意の行列をゼロ行列にできるか」というのと等価です。

これを全て検証するのは難しい問題ですが、任意の一マスだけを反転させることが可能ならばそれを繰り返せばどんな初期状態の行列でもゼロ行列に持っていけることがわかります。

またこの場合も、16マス全てについて反転可能かどうかを調べる必要はなく、上に挙げた三マスについてだけ調べれば大丈夫です。

基本変換行列を達成するパネルの押し方

ウラルさんの研究結果から、それぞれの行列を達成するパネルの押し方が発見されました。

このことから、任意の初期行列をゼロ行列にすることができるということが証明できました。

これらの情報から、最も手数がかかるのは全てのマスが青い初期行列のケースで、

100手かかることも求められます。

もちろんこれはワーストケースを考えているので、どんな初期行列でも高々100手あればクリアできるということを示しているにすぎません。

実際には全部青いマスの場合は四隅を押せば四手でクリアできます。

これ、パネルの押す順番って関係ないの?

ないよー、何故ならこの計算空間では可換性が成り立つからね。

可換性

パネルを押す順番が関係ないかどうかは交換法則があるかどうかで決まります。

わかりやすく言えば加算や乗算には交換法則が成り立ちます。

交換律

減算や除算は加算や乗算に直せば交換法則が成り立ちます。

今回想定する計算空間には計算が一種類(排他的論理和)しかないので、考えることは簡単です。

計算法則
交換法則が成立

さて、これを見ると交換法則が成り立っていることがわかります。

というよりも、交換法則が成り立つような計算空間を定義したと考えたほうが正しい。

先ほど求めた三つの変換行列をそれぞれA, B, Cとすれば「可換性があるのでその三つを押す順番は入れ替えても良い」ということになります。

つまり、上のような感じで順番を代えても問題ないことになります。

解を求める

解法

今回の問題の場合、反転させたいマスが八つあるのでそれぞれについてパネルの押し方を考えます。

これは基本変換行列を反転させたり回転させたりすればすぐにどのマスを押せばいいかわかります。

それぞれのマスの押す回数

さて、ここでそれぞれのマスを押す回数が求められました。

合計すると40だから40回押さないとダメ?

よく考えたら40回も押さなくていいことがわかるよん。

単位行列(変換)

さて、ここで同じマスを二回押した場合の挙動について考えましょう。

えーっと、一度反転させたものをもう一度反転させるわけだから…

元に戻るということやね!

二回変換するともとに戻る

当たり前だが、A以外でも同じ変換を二回行なうと元の状態に戻ります。

ここで、Iとは元の行列に足しても全く変化しない変換と定義します。つまり、全ての値が0の行列ということですね。

単位変換Iの定義

全ての値が0の変換ということはどのマスも押していないのと同じなので、これは無視して良いということになります。

つまり、あるマスを「偶数回押すというのは一度も押さなくてよい」「奇数回押すというのは一度だけ押す」と考えればいいことになります。

結果

単位行列に従って、押すべきマスと押さなくてよいマスを分けると以下のようになります。

解法

このとき、色がついているマスが十あるので、この初期状態の最短手数は”高々”十手であることがわかりました。

同じマスを二回以上押さない解のことを合理的な解、と呼ぶことにします。

最小手数を求める

さて、ここで今回の問題について厳密に最小手数が十手であると断言してよいのでしょうか?

初期行列

まず、初期行列が全部で何通りあるかを考えます。

初期状態の一例

16のマスに対して白か青かの二通りが考えられるので、

通りの初期状態が考えられます。

更に、単位行列の性質から同じマスを二回以上押す意味がないので全てのマスは押すか押さないかの二択になります。これも全てのマスについて考えらえるのでマスの押し方も、

となります。

マスの押す場合の数と初期状態の数が等しいので「違うマスの押し方によって同じ変換にならない」ことが証明できれば、初期状態に対して合理的な解がただ一つしか存在せず、それが最小手数解であることが保証されます。

合理的な解と初期行列は一対一対応か?

上の図はあくまでも一例。実際にはそれぞれ65536通りあるので、紙面の都合上全てを書ききることはできません。

つまり、一つの初期状態に対して解が一対一対応であればいいということですね。

独立性

さてここで問題となるのは「あるマスを押したときの変換行列が他のマスをいくつか押したときと同じ変換行列にならないかどうか」ということです。

もしもこれがYESなら、初期行列と解が一対一対応でなくなるので唯一解が最小手数解であることが保証されなくなります。

要するに「Aという変換と、BとCを押した変換が同じものにならないと言えるか」ということになります。

成り立つか?

これだけだと確かめるのが難しそうに思えますが、先程の単位行列の話を持ち込むと少しだけわかりやすくなります。

単位行列に変換

もしもAという変換がB+Cと同じ変換であるなら、可換性から更にAを押した状態を考えることができます。

このとき、左辺は単位変換の法則から同じ変換を二回行えばもとに戻るのでIになります。

一方、左辺は “同じ項を含まない” 変換の和になっています。

今回はわかりやすく右辺は二項になっていますが、項の数がいくつであっても同じ議論ができます。

つまりこれは「同じ変換を二回使わずに単位行列をつくることができるか?」という問題と等価だということです。

初期行列から同じマスを押さずに、再び初期行列に戻れるか?という考えもできますね。

で、これは結果的に「そのような組み合わせはない」ということがわかっているのですが、証明ができていません。誰か頼んだ。

ある種の証明

独立性自体の証明はできていないのですが、これが正しいことはわかります。

何故なら、ウラルさんが如何なる初期行列においても解が存在するということを証明したからです。

考え方の違い

この論理によって、合理的な解が唯一であり最小手数解であることが保証されるわけです。

しかも、この考えは別の問題でも推し進めて使うことができそうです。

一般的なルールでは合理的解の数と初期行列の組み合わせが同じになるので、真ん中のケースが一番多そうな気がします。

以下、いろいろな予想。

予想

逆変換について

  • 全ての変換行列に対して逆変換が存在するとき、合理的解の数と初期行列の数は一致する

逆変換とは、押したセルを押せば元の行列に戻る(一回でなくてもよい)ということを指します。

完全性について

  • 「完全性がある」というのは「任意の一マスを反転させる変換行列の組み合わせがある」というのと同値である

独立性について

  • 逆変換があれば、独立性がある

まとめ

さて、結論として最小手数解を求めることができたのですが、これは果たして正しい求め方だったのでしょうか?

ルールが複雑になって、パネルの数が増えれば手作業で「任意の一マスを反転させる変換行列の組み合わせ」を見つけることは困難になります。

コンピュータでパッと解があるかどうか、最小解であるかどうかを求める方法はないのでしょうか?

また、今回はその手の解析をしなかったために計算複雑性について全くの手つかずになってしまいました。次回への宿題ということにします。

あと、この手の問題は恐らくあみだくじと同じで合理的解と組み合わせが常に等しく、必ず一対一対応になる気がします。

記事は以上。