0. はじめに
この記事を書いた経緯
ぷよぷよAIを作ろう！という大学の授業があったので、色々調べたり考えたりしたことを備忘録として残しておきます✍
個人的にためになったなと思う以下の2点を主に書いていきます
- どんなアルゴリズムを実装するか
- そのアルゴリズムを如何に効率的に実装するか(開発フロー)
注意点
- 教材として提供されたコードは公開できないのでJavaコードを交えての説明はないよ
- 各戦略の評価はちゃんと計測したわけじゃないのでざっくりの感覚値
- 間違いがあったら教えてほしいよ
ぷよぷよのルール
今回の課題は授業用ということで本来のぷよぷよと若干ルールが違う
ぷよの色が5色
スタンダードは4色？実は4色と5色だととるべきアルゴリズムが全然変わったりする
同時ターン制
本来のぷよぷよだと相手が発火し始めてからし終わるまでに結構時間があるので、その間にカウンターを組めたりする。
けど相手と同時にぷよをおいていくこのルールだと発火の際のタイムロスがない。なので、お邪魔が降るまでに自分の盤面の発火ぷよを引かなければ相殺が間に合わない。
1ターンの思考時間は1秒
思考時間を少なくして速く積む必要がないため、1秒間の間でなるべく多く探索するのが鍵になる
1. アルゴリズム
ぷよぷよAIに使えそうなアルゴリズムを並べてみる
とはいえ、ぷよぷよ以外でも使える場面は結構ありそう
探索アルゴリズムについては以下のスライドがすごく参考になった
1-1. Bit演算
実装難易度: ★★★★☆
AI強化貢献度: ★★★★★
高速化をするならまずこれ！ちゃんと測ってないけど多分これで10倍くらい高速になる
5色のぷよを1bitずつに割り振るとすると(高さ12マス)×(5bit) = 60bit でJavaのlong(64bit)になんとか収まる
お邪魔ぷよも同様に列ごとにlongに格納する
ぷよの落下処理を実装しやすくするために高さごとよりも列ごとに管理するのがおすすめ
1-2. Monte Carlo法
実装難易度: ★★☆☆☆
AI強化貢献度: ★★★☆☆
各ターンで見えているツモは3つまでなので4つ目以降は自分で補わなくちゃいけない
でもすべてのツモを試すのは計算時間的に大変(5C2+5 = 15通りのツモがある)
そんなときに便利なのがMonte Carlo法！
制限時間いっぱいになるまでツモの配列をランダムで作り続けて、それぞれで探索した結果を最後にまとめれば、実際にどんなツモが次に来てもそこそこ安定した積みができる
1-3. Beam Search
実装難易度: ★★★☆☆
AI強化貢献度: ★★★★★
Monte Carlo法でツモを作ったあとは盤面の探索をしていく
ツモが決まっていればそれを置く方法は(ツモが異なる色のぷよでできている場合は)縦に12通り、横に10通りで合わせて22通りの置き方がある
つまり全探索しようと思うと1ターン進めるごとに探索する盤面は22倍ずつ増えていく
22^5=5e6くらいなのでおそらく4, 5手が限界になってしまう
でも大体の盤面は連鎖が組めていないようなものなので評価値(同じ色が隣り合っているとか大きい連鎖が打てるとか)が高い盤面に絞って探索を進めていくと効率的
これをすると探索幅200で20~30ターン先まで探索しても間に合うようになる(最大で6*12/2 = 36ターンで盤面が埋まるのでそれ以上は探索しない)
1-4. Monte Carlo Tree Search
実装難易度: ★★★★★
AI強化貢献度: ？？？
Monte Carlo法と名前が似てるけど全然別のアルゴリズム
パラメーター次第ではさっきのBeam Searchよりも多様な盤面を探索できるかも
でもぷよぷよのplayoutをどう定義するかに工夫が必要そう
AlphaGoで使われてるくらいだからちゃんと実装したら強いのかも？実際に実装してみた論文もあったりする
1-5. 疑似乱数のシード値をクラック
実装難易度: ？？？(僕には無理)
AI強化貢献度: ★★★★★
この授業で使われているぷよぷよのプログラムは次のツモをnextIntという疑似乱数生成器で作っている。
でも実はこのnextInt、最初のシード値さえ分かればnextIntで出てくる数字(ツモ)を完璧に予想することができる
だからこのシード値を割り出せれば全く別次元の強さになるんだけど厄介なのがnextIntのboundという引数(今回はぷよの色の数が入る)。
ぷよが4色(2のべき乗)のときはシード値を(以下の記事いわく)簡単に割り出せるらしいんだけど
2のべき乗でなく、しかも奇数である5色の場合は簡単にはシード値を見つけることができない
1-6. 並列処理
実装難易度: ★☆☆☆☆
AI強化貢献度: ★★★☆☆
これはアルゴリズムではないけど効果があったので書いておく
JavaのExecutorsというクラスで実装した
スレッドプールのサイズは3で固定にしたけどもっといい方法があるかも？
1-Ex. 番外編
その他思いついたけど実装しなかったものを書いていくよ
ゲーム情報をクラック
先生が提供してくれているコードをじっくり読み込めば勝手にゲーム内部の変数を変更できるかもしれない
特に共有渡しされている変数のメソッドを適切なタイミングで呼び出せばわんちゃん、、？
API経由で外部のリソースを利用
先生のPCがインターネットに繋がっている前提で外部のサーバーと通信するコードを書く
通信の送受信にかかる時間も考慮する必要があるが、例えばシード値の割り出しをGPUでごり押ししようと思った場合には有力な選択肢
勝負から逃げる
ぷよぷよAI同士を戦わせてると「負け確や、、」ってなるときが結構ある
そんなときはSystem.exit(1)を実行させれば強制的にゲームを終了させる事ができる
実質無敗のAIがつくれるが単位が来る保証はない
2. 開発フロー
ここまで色々使えそうなアルゴリズムを見てきたのはいいものの、どうやって実装するかが問題
1000行程度の規模の個人開発でも開発フローの意識は必須だと思った
2-1. 単体テスト
正直これを怠っていたのが個人的最大の反省点
JavaでいえばJUnitという単体テストのフレームワークがあるが、他の言語で開発するときももっと真面目にテスティングフレームワークを使おうと思った。
「テストコードを書いたほうが結局早い」の意味がわかった気がする
テスト駆動開発とかもちゃんと勉強したほうがいいのかもしれない
2-2. AIの強さ判定の自動化
AIのパラメーターや仕様を若干変えたときに強くなったのか弱くなったのかわからない場合がある
これを勝率や火力から自動で判定してくれるプログラムがあれば自信を持ってAIを強くしていける
そこで例えばGitHub Actionsが使えたりする
GitHubにpushした際に自動でAIの強さを計測してくれるプログラムを書ければよりスムーズに開発できるし、どのバージョンのコードがどの強さかも記録できる
ただし配布されたコードにはGUIをオフにする機能がなかったので、自分でGitHub Actionsの環境でも動くよう書き換える必要がある
3. まとめ
この課題が出たときは「１単位の重さじゃねぇ、、」と思っていたけど、なんだかんだ色々学べて面白かったし、次からの開発はもっと効率的にできると思う