MOLEK-SYNTEZのSolitaireソルバー
MOLEK-SYNTEZのソリティアミニゲームを解くのが面倒になったのでpythonでソルバーを作った。
少し前にMOLEK-SYNTEZというゲームを紹介した。
本編は原子をぶつけて化合物を作るだが、ミニゲームでソリティアも遊べる。
MOLEK-SYNTEZで獲得できるsteam実績は6個あるが、うち4個はソリティア関連である。頭おかしい。
「CHARLATAN」という実績を達成するには100回ソリティアする必要がある。
steamの実績獲得率は1.5%で、完全クリアと同程度の人数しか達成できていない。
面倒なので自動化したくなった。
調べてみると、前作ShenZhen I/Oのソリティアは完全に自動化されていた。
放っておいたらソリティアを解き続けてくれるらしい。
GitHub - emichael/shenzhen-solitaire-bot: Bot for Shenzhen I/O Solitaire
ShenZhen I/Oのコードを参考に、MOLEK-SYNTEZ版を作成した。
(クリック自動化まではモチベが沸かなかったので、ソルバ部分だけ作った)
このソリティアは恐らくNP-Hardだが、問題サイズが小さくゴールが明確なので、
適当に評価関数を与えて最良優先探索をすれば簡単に解が見つかる。
def score(self): # todo(komori): reconsider calculation # s_val = 8 - 2 * sum(self.pile_fixed) s_val = 8*1*4 + 4*(8-1) - 8 * sum(self.pile_fixed) + 0.1 * self.move_num s_val += 5 * sum(self.pile_illegal) for pile in self.piles: prev = None for card in pile: if prev and not prev.goes_on(card): s_val -= 1 prev = card if pile: s_val += 1 if pile[0].number < 11: s_val += 2 return s_val
score()が小さいほど答えに近くなるお気持ち。
整列に近いpileは点数を低く、小さい数から始まったりillegalな配置のpileは点数を高くしている。また、人力で動かすことを考慮して、手数の大きさに応じて点数を増やしている。
(これで解の手数が5手ぐらい短くなる)
実行結果はこんな感じになる。
States explorered: 0 Lowest Score: 50.00 Current Score: 50.00 Elapsed time: 0.00s States explorered: 122 Lowest Score: 46.70 Current Score: 47.10 Elapsed time: 1.00s States explorered: 257 Lowest Score: 39.60 Current Score: 40.90 Elapsed time: 2.02s States explorered: 480 Lowest Score: 38.10 Current Score: 38.50 Elapsed time: 3.03s States explorered: 743 Lowest Score: 38.10 Current Score: 43.70 Elapsed time: 4.03s Solution found ===0=== 7 7 9 8 7 8 T 6 6 T 7 V 0 V 9 0 9 K T 6 9 T D 0 8 V 6 D 0 D 8 V K K K D (略)
NPSが120ぐらいしかないが、大体の問題は10秒以内に解けるので目をつぶる。
愚直に全探索をすると探索局面数が10万局面を超えて探索が終わらない。
最良優先探索を取り入れると1000局面程度の探索で解を見つけることができる。
ソルバーがあってもマウスポチポチするのがめんどいな…。
時間があったらマウスの動きも自動化したい。
2020-06-23 追記
探したらすでにソルバーがあった。悲しい。
GitHub - Hegemege/molek-syntez-solitaire-bot: Solver bot for solitaire in MOLEK-SYNTEZ