プログラミングっぽい独特なパズルゲームを開発しているZachtronicsが出したEXAPUNKSというゲームで遊んでいます。
簡単なアセンブリ のような言語でEXAというウイルスのようなエージェントをプログラミングし、ストーリーを追いながらハッキングでデータを改ざんしたりハードウェアを操作したり、時には別のハッカー (プレイヤー)のプログラムと対戦したりするというパズルゲームです。
store.steampowered.com
VIDEO www.youtube.com
さて、本編もなかなかやりごたえのある内容(かつ適度な楽しめる難易度)なのですが、少しストーリーを進めると、おまけで息抜きにミニゲーム 「ПАСЬЯНС」(ソリティア )で遊べるようになります。
数字カードは赤黒赤黒…と互い違いの色で降順に重ねることができ、絵のカードは同じスートのカードは重ねられるという条件を満たしつつ、一枚、またはこの条件で重ねたカードをまとめて移動して積み重ねていき、最終的に 10-9-8-7-6 という降順のセット4つと各スートの絵文字4枚を重ねたセット、計8セットを作れば勝利、というルールです。
なお、途中で一枚だけ、右上の空きスペースに避けておくことが可能です。
息抜き用とはいえ、適当にやっていると結構、途中で詰まってしまうくらいの難易度です(UNDOもできないし)。
せっかくのプログラミングゲームなので、このПАСЬЯНСをプログラムで解かせてみました。とはいえこのゲームのEXA用言語ではなく、普通のRuby です。
Solve ПАСЬЯНС puzzle in EXAPUNKS · GitHub
※ 以下のデータ入力と操作の自動化については次の記事で:
EXAPUNKSのソリティアを自動操作で解く - Okiraku Programming
入力として data.txt というファイルに、カードの並びを左上から右に記入したものを与えます。絵のカードは各スートを s h c d の文字で、数字のカードは赤6なら r6 黒10なら b10 のように記述します。上記のスクリーンショット であれば、以下のようになります。
r10 r8 b8 r6 h c c b7 r7
d b8 s d b6 b9 r9 b10 b10
c b9 r10 r7 c r8 h r6 d
s r9 d h s h b7 b6 s これに対して solver.rb を走らせると、以下のように解法の手順が表示されます。
movable: 0 -> 4 :: s -> s
movable: 0 -> 9 :: c -> []
movable: 0 -> 2 :: d -> d
movable: 3 -> 5 :: h -> h
movable: 4 -> 8 :: s-s -> s
movable: 7 -> 3 :: b6 -> r7
... :: の左が移動するカードの位置(0が左で8が右の山、9は右上の空きスペース)、:: の右はカードの数字や絵カードのスートを示します。
まず、0(一番左)のスペードの絵カードを4(真ん中)のスペードに重ねる。
次に、0(一番左)のクラブの絵カードを右上の空きスペースに退避する。
…
という感じです。
このままでも、通常は一瞬で、遅くとも数秒で解けますが、稀に延々計算していて解が表示されないことがあります。このプログラムでは素朴に手順を深さ優先で探索しているために、解が見つからない場合には最後の方の似たような手順を何度も調べ続けてしまうためです。
ランダムな配置でどれくらい解ける*1 のか調べてみたところ、だいたい96%くらいは解けるようでした。
ちょっと素朴すぎるので、次のように適当に深読みしすぎるのを防止してやると、ほぼ確実に解けるようになります。
+$depth_limit = []
+
def scan(deck, steps)
+ (0...(steps.length-1)).each do |depth|
+ return if ($depth_limit[depth] += 1) > 30 * 9 ** (steps.length - depth + 1)
+ end
+
rem = 0
(0..9).each do |i|
unless deck[i].length == 0 || completed(deck[i])
+ $depth_limit[steps.length] = 0
rem += 1
scan_i(deck, i, steps)
end
時間がかかる例として、以下の入力があります。
b10 r8 h b6 c b7 r10 r7 r7
h s b10 b6 d b8 r10 r9 s
c c d r6 s s d h r9
h b9 b8 b7 b9 d c r6 r8 depth_limitをつけた上で、手元のMacBook Pro でだいたい10秒くらいかかります。せっかくCPUインテンシブ な負荷なので、たまたま手元にあるRuby のバージョンごとに速度を測ってみました。
Ruby バージョン
所要実時間(3回平均)
CPU時間(user+sys, 3回平均)
ruby 2.3.7p456
10.63s
10.59s
ruby 2.5.3p105
10.42s
10.38s
ruby 2.6.3p62
8.79s
8.77s
ruby 2.6.3p62 --enable-jit
8.39s
16.76s
ruby -trunk(2.7.0-dev 025206d0dd)
9.17s
9.13s
ruby -trunk(2.7.0-dev 025206d0dd) --enable-jit
8.13s
10.56s
JIT で多少ですが実時間が早くなっていますね。
また、ruby -trunkではJIT なしの時はv2.6.3よりも若干遅くなっていますが、JIT ありではさらに高速になっており、かつJIT 時のCPU時間の上昇も抑えられているのが分かります。