プログラミングっぽい独特なパズルゲームを開発しているZachtronicsが出したEXAPUNKSというゲームで遊んでいます。
簡単なアセンブリのような言語でEXAというウイルスのようなエージェントをプログラミングし、ストーリーを追いながらハッキングでデータを改ざんしたりハードウェアを操作したり、時には別のハッカー（プレイヤー）のプログラムと対戦したりするというパズルゲームです。
store.steampowered.com
www.youtube.com
さて、本編もなかなかやりごたえのある内容（かつ適度な楽しめる難易度）なのですが、少しストーリーを進めると、おまけで息抜きにミニゲーム「ПАСЬЯНС」（ソリティア）で遊べるようになります。
数字カードは赤黒赤黒…と互い違いの色で降順に重ねることができ、絵のカードは同じスートのカードは重ねられるという条件を満たしつつ、一枚、またはこの条件で重ねたカードをまとめて移動して積み重ねていき、最終的に 10-9-8-7-6 という降順のセット4つと各スートの絵文字4枚を重ねたセット、計８セットを作れば勝利、というルールです。
なお、途中で一枚だけ、右上の空きスペースに避けておくことが可能です。
息抜き用とはいえ、適当にやっていると結構、途中で詰まってしまうくらいの難易度です(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時間の上昇も抑えられているのが分かります。
*1:5秒以内に終了しない場合は解けないとみなしました
