5分でわかる Combinatris

Transcript

1. © Alp, Inc. 2022/12/15 Alp 忘年会 LT 5分でわかる Combinatris by Kory
2. © Alp, Inc. 皆さん テトリスは ご存じですね？
3. © Alp, Inc. • テトリミノ (四つの正方形が繋がった もの; 全7種) が降ってくるので、 フィールドに積み上げていく • テトリミノで埋まっているラインがで きると、すぐにそのラインが消えてス コアが入る • フィールドよりも上にテトリミノが溢 れてしまったらゲームオーバー 5分でわかる Combinatris テトリス Typical Tetris Game.svg From Wikimedia Commons, the free media repository
4. © Alp, Inc. でも僕、 テトリスはあんまり やったことないんです…
5. © Alp, Inc. LT で話せるほどの テトリスの知識は無い…
6. © Alp, Inc. なので（？）今日は、 テトリスではなく Combinatris について話していきます
7. © Alp, Inc. © Alp, Inc. ?
8. © Alp, Inc. ブラウザで遊べるゲームです https://dirk.rave.org/combinatris/
9. © Alp, Inc. 5分でわかる Combinatris Combinatris の基本ルール • 5 × 30 のマス目があるフィールド。一マスには空白か文字か括弧が入る • 左端中央から文字と中身が空の括弧が降ってくるので、右側に積み上げる • 括弧が全部埋まった時、特定のルール (後述)で行の文字列が変形されていく • 文字列の変形回数 (×10) がそのままスコアになる。目指せ 3000 点！ • 左側に文字や括弧があふれるか、変形が無限ループするとゲームオーバー • 各行は独立していて、行と行の間が干渉することはない
10. © Alp, Inc. 5分でわかる Combinatris Combinatris の基本ルール • 5 × 30 のマス目があるフィールド。一マスには空白か文字か括弧が入る • 左端中央から文字と中身が空の括弧が降ってくるので、右側に積み上げる • 括弧が全部埋まった時、特定のルール (後述)で行の文字列が変形されていく • 文字列の変形回数 (×10) がそのままスコアになる。目指せ 3000 点！ • 左側に文字や括弧があふれるか、変形が無限ループするとゲームオーバー • 各行は独立していて、行と行の間が干渉することはない
11. © Alp, Inc. 5分でわかる Combinatris Combinatris の基本ルール • 5 × 30 のマス目があるフィールド。一マスには空白か文字か括弧が入る • 左端中央から文字と中身が空の括弧が降ってくるので、右側に積み上げる • 括弧が全部埋まった時、特定のルール (後述)で行の文字列が変形されていく • 文字列の変形回数 (×10) がそのままスコアになる。目指せ 3000 点！ • 左側に文字や括弧があふれるか、変形が無限ループするとゲームオーバー • 各行は独立していて、行と行の間が干渉することはない Ix → x (x) → x Kxy → x Sxyz → xz(yz) Yx → x(Yx) 変形ルール一覧 Combinatris では左端の文字によって適用するルールが決まる
12. © Alp, Inc. © Alp, Inc. Combinatris での変形例
13. © Alp, Inc. 5分でわかる Combinatris Combinatris での変形例 Ix → x (x) → x Kxy → x Sxyz → xz(yz) Yx → x(Yx) 簡単な変形例
14. © Alp, Inc. 5分でわかる Combinatris Combinatris での変形例 Ix → x (x) → x Kxy → x Sxyz → xz(yz) Yx → x(Yx) 簡単な変形例 ...................S →.................KS →................IKS ↝.................KS →................KKS ↝..................K +K +I β +K β
15. © Alp, Inc. 5分でわかる Combinatris Combinatris での変形例 Ix → x (x) → x Kxy → x Sxyz → xz(yz) Yx → x(Yx) どんどん大きくなる変形例
16. © Alp, Inc. 5分でわかる Combinatris Combinatris での変形例 Ix → x (x) → x Kxy → x Sxyz → xz(yz) Yx → x(Yx) どんどん大きくなる変形例 .................SSS →...............SSSS ↝.............SS(SS) →............SSS(SS) ↝.......S(SS)(S(SS)) →......SS(SS)(S(SS)) +S β +S β +S ↝..S(S(SS))((SS)(S(SS))) β ここにもう一回 S を積むと 30 文字を超えてゲームオーバー
17. © Alp, Inc. 5分でわかる Combinatris Combinatris での変形例 Ix → x (x) → x Kxy → x Sxyz → xz(yz) Yx → x(Yx) 爆発する変形例 .................SSS →...............YSSS ↝............S(YS)SS ↝..........(YS)S(SS) ↝............YSS(SS) ↝.........S(YS)S(SS) ↝......(YS)(SS)S(SS) +Y β β このまま大爆発してゲームオーバーになります β β
18. © Alp, Inc. 5分でわかる Combinatris Combinatris での変形例 Ix → x (x) → x Kxy → x Sxyz → xz(yz) Yx → x(Yx) 無限ループ典型 (YI) ...................I →.................YI ↝..............I(YI) ↝...............(YI) ↝.................YI +Y β β 2行目と5行目が等しい！ 変形がループしてしまうので ゲームオーバー
19. © Alp, Inc. © Alp, Inc. ところでなぜ S, K, I, Y なのか？
20. © Alp, Inc. 5分でわかる Combinatris ところでなぜ S, K, I, Y なのか？ • S, K, I, Y の変形規則は普通のコンピューター上で実行できる • 驚きの事実として、逆に、どのようなコンピュータープログラム が与えられても、そのプログラムと同じ計算をする S, K (と括弧) の羅列が書き下せることが知られている 「S, K の文字列変形だけ」でも、我々が触れている コンピュータ程度の計算能力がある！
21. © Alp, Inc. 5分でわかる Combinatris ところでなぜ S, K, I, Y なのか？ Entscheidungsproblem (「停止性問題」) • 「一般のコンピュータプログラムが与えられた入力で停止 　するかどうかは、無限のメモリを用いても有限の時間で 　判定することができない」 (Church 1935, Turing 1936) つまり、 S, K, I, Y の組み合わせが 「爆発しない」ことは本質的に判定不可能 →我々は (一般ケースでは) 　解けないものを解かされている！！
22. © Alp, Inc. © Alp, Inc. Combinatris の 複雑性
23. © Alp, Inc. 5分でわかる Combinatris Combinatris の複雑性 • Combinatris では、テトリスと同じように、スコアが高くなるほど 文字が落ちてくる速度が速くなってくる • しかも、テトリスと違って「次に落ちてくる文字」を見せてく れない！ • 2000 点を超えた瞬間にものすごい速度で降ってきてほとんど即 ゲームオーバーになる 2000 点になる直前に、「一文字積むだけで数千点入るコンボ」 を実行することでハイスコアが狙える！
24. © Alp, Inc. でも思い出してほしい
25. © Alp, Inc. 4枚前のスライド ↓
26. © Alp, Inc. コンボって言ったって、 どう積めばいいか わからなさすぎる
27. © Alp, Inc. でも僕は プログラムの書き方は わかる
28. © Alp, Inc. ソルバ書けばよくね？ 非有界な Combinatris は Turing 完全性より決定不能だが、 今回我々が遊んでいるやつは有界なので プログラムで探索できる
29. © Alp, Inc. 5分でわかる Combinatris Combinatris の複雑性 というわけで、 Scala でゲーム自体を再実装 し… 型を考えるのに 5 時間 くらい使い、実装に3時 間くらい使った… https://github.com/kory33/ combinatris-solver
30. © Alp, Inc. 5分でわかる Combinatris Combinatris の複雑性 深さ優先探索を してみた https://github.com/kory33/ combinatris-solver
31. © Alp, Inc. 結果…
32. © Alp, Inc. 5分でわかる Combinatris Combinatris の複雑性 93コンボを起こす 積み方があった ((Y((SSS)IS)I)KS)SSS
33. © Alp, Inc. なんもわからんね
34. © Alp, Inc. 5分でわかる Combinatris Combinatris の複雑性 今後の課題 • この深さ優先探索はだいぶ雑で、ゲームの全状態を網羅的に探索 できているわけではない • 幅優先探索もやってみたが、「探索予定のゲーム状態」のキュー がすぐに膨らんで OutOfMemoryError になってしまう • いい感じに枝刈りをしつつ、全状態を探索し、最もスコアの高い コンボを特定したい • 「二回文字を落とす」ような二段階コンボも気になる
35. © Alp, Inc. 良い Combinatris ライフを！