Bombeとかいうゲームについての手記 その5
このnoteは私が淡々と頭の中を整理するために書くnoteです。
過度な期待はしないでください。
その4で最適化をしばらく書いていく予定としたのですが、大変なことがおきました。
＿人人人人人人＿
＞ PCが重い ＜
￣Y^Y^Y^Y^Y^￣
ロボットのボタンを押してから数秒で20くらいしか進まない……！
これは既存のルールの最適化が求められている……！
ということで倉庫整理回です。優先的にCPU負荷を下げるようにルールを整理します。
今回注目するのはルール一覧の右上にあるCPU関係の数字です。
CPUから火を吹いているボタンを押すと切り替えられます。最初は地球みたいなマークになっているはずです。
右から2番目の列はそのルールを適用するときに使った合計CPU時間、一番右の列は1セルクリアするまでにかかる平均CPU秒数です。
無限になっているのはつまり1セルもクリアしてないということです。ちなみに297～302はその4で作ったルールです。
この一番右の列が低ければ低いほどCPUにとっては良いルールと言えます。
そのため、一番右の列を高い順に見ていこうと思います。
特に悪いのはCPU時間がやたら高いのに全然セルをクリアしないルールです。その点だけで言えば、297や299は割とマシだと言えるでしょう。(そもそも適用回数が少ないからクリアしなくてもCPUに負担はかからない)
その点で言えば281とかはヤバいです。4991万2244ってなんだ。桁が違うぞ。
とはいえこいつも立派なルールの一つ。このルールが言いたいことを考えて簡略化できるならしてみましょう。
何故このルールがやたらとCPUを食うか、それは適用できるかどうかを判定する回数の多さです。このルール、実は適用回数自体はそこまで多くありません。
では何故時間がかかるのか。それは適用できるかどうか、つまり適用前にチェックする回数が多いからです。
このルールには例えばこの盤面が含まれます。しかしほとんどのマスが文字もしくは?になっているので、適用できるかどうかは4つ以上のルールが存在する盤面であればほぼ毎回確認しなければなりません。つらい。(CPUのお気持ち表明)
ではまずいつもの通りに考えていきましょう。爆弾の個数内訳を考えます。
……が、このままだと非常に考えなければならないことが多くなりそうなので可能な限り簡単にします。
ちょっと簡単すぎましたかね。b,c,dはそれぞれ最大でも1つしか爆弾が入らないため、それぞれ1つの爆弾で確定です。故にaに爆弾は入らないため、aは爆弾が0個であることが確定します。
上記のパターンも同様です。やはりb,cには1つ、そしてdには2つ爆弾が確定します。故にaに爆弾は入らず、0個であることが確定します。
b欄に爆弾が入ることが非常に重要に思えます。
そうすると、aを確定させるために2-の情報は不要ではないでしょうか？消してみましょう。
やはりaが0であることを確定させるためには不要な情報でした。つまりなにはともあれbが確定すればaに爆弾が入らないことがわかるということです。bに少なくとも1つ爆弾が入るというのはどういう状況でしょうか？
一旦、このまま爆弾の個数内訳を考えます。
4+に対してマス目が4つしかないのですべて爆弾で確定しています。故にこのパターンしかありません。もう少し複雑な状況を考えてみましょう。下記などどうでしょうか。
9としたところは実際には？で成り立つのですが、一旦数字にしています。さて、何か思い出されませんでしょうか。
前回不採用にしたルールが適用できそうです。つまり、1-と1-が重なっているとき、a,b,c,d,e,fは2-であるのです。(χ=0,ψ=1のとき)
これは当然ですが成り立ちます。1-にはなりません。さて、それではそのような事実が判明しているときに、gに入る爆弾の個数は一体いくつになるでしょうか。
2+になります。d,e,fにどんなに都合よくたくさん入っても最大で2個しか入らないということは、gには最低2個以上爆弾が入らないとだめということです。しかも最大3個までしか入りませんので、
こういうことになります。さて、gには2または3この爆弾があるとしたときに、d,e,fにはどのように爆弾が入るでしょうか？実は数パターンしかありません。何故ならば、d,e,fのいずれも最大で1つしか爆弾が入らないためです。内訳表を書いてみましょう。
gが2個のときは1パターンしかありません。gが3このときは多少パターン数がありますが、それでも4パターンしかありません。そしてやはり常にbは0なのです。もっと言えばbのマス数も関係ありませんので、bのマス数も?にできます。
ここまでの考え方の流れを整理しましょう。
1. 1-と1-の関係性によってgの個数が定まります。
2. gの個数が定まった場合、d,e,fの爆弾内訳が確定します。
3. d,e,f,に0個の爆弾が入るパターンが存在しない限り、bには爆弾が入りません。
3.の考え方が非常に重要に思えます。とにかくd,e,fに一つ以上の爆弾が確定さえすれば、他の事情は一切関係なくbの個数が確定します。
さて、数字を変えても同じ考えが成り立つでしょうか。
個数内訳を考えてみましょう。もはやgの爆弾の個数は意味をなさないので考えません。d,e,fには1個以上の爆弾が入りそれぞれのマスは最大でも2個までしか入らないという点は考える必要があるでしょう。
d,e,fのみ考えただけでこれだけのパターン数がありました。このそれぞれのパターンに対してa,b,cも複数パターンあるので、やろうと思えばできますが、この方向へ考えを進めるのは危険な気がします。
『3. d,e,f,に0個の爆弾が入るパターンが存在しない限り、bには爆弾が入りません。』この意味を考えたときにこれだけでルール作成ができないのか考えました。つまり、
こういうことです。元の図と比べるとだいぶ簡略化されました。
これは非常に簡単そうなのでそのまま一般化してしまいます。
もちろん上記ルールは成り立ちます。さて、このときに1-側もなにかできないでしょうか。2-にでも変えてみます。
cには当然ながら最大でもχ個(マスの個数)までしか爆弾は入りません。
故にbは少なくとも1個以上の爆弾が確定します。
すると自動的にaには最大でも1個の爆弾しか入りません。
つまりここは0ではなく1-になるのです。
つまりこれが『3. d,e,f,に0個の爆弾が入るパターンが存在しない限り、bには爆弾が入りません。』を一般化したものになります。
さて、しかしこれだけでは終わりません。実はもう一つ情報を狭められる箇所があります。
そうです。真ん中が1以上に確定します。これ自体はルールとして弱いと思います。
しかし1+は要は右側の個数のうち溢れ出る個数なので、文字で表せます。
別にκでも良いのですが一旦ψにします(適用範囲が縮まりますからルールの意味が少し変わります)。するとどうでしょうか。なにか見えてきませんか？
このような場合、bの爆弾の個数はψ/ψ+1に確定します。これはかなり珍しいパターンですが、このように表現できるからにはしてもよいでしょう。
本当はこういったルールにしておいて適宜使ってほしいのですが、このルールは適用できません。何故ならば、無制限というエラーが出るからです。このエラーは文字の場合しか出ません。具体的にどういうことかというと、
こういったルールが成り立つときに、先程のルールは更に1+について適用できます。2-としているところは2以下であればよいので、0でも適用できます。1+に対して適用すると、ψが1のときですから、1+が生まれて、その1+がまた1+を生み出し……というループができてしまいます。
だから上記の無制限というエラーを取り除くためには、χ-の箇所を『χ-かつ!0』とか『χ-かつ1+』などと定義しなくてはなりません。このゲームには今のところそのような機能はないので、先程のルールは適用できません。
『bの爆弾の個数はψ/ψ+1に確定』というのはあくまで1+が確定するということさえルール化できてしまえば不要になるルールです。なので、実際には使うことはないのかもしれませんがそれは実際にロボットくんに解かせてから考えたいと思います。
さて、それでは元の重たいルールを削除して今回の新ルールを追加しました。ロボット君実行……！お、重い……！しばらく軽量化に腐心する事になりそうです。
……複雑度スライダーを少し下に動かせば、動作自体はいくらでも軽くなるのですが。
この記事が気に入ったらサポートをしてみませんか？