ポケモンバトルのAIを作ってみたよ
※2020/2/16 追記
ソード・シールド環境ではこっちを開発しています
みんなこんばんわ。がりゅきゃんリーダーです(真顔)。
たった今世界で一番人権のない作業として名高い、排水溝の髪の毛取りの修行を終えたのですがつくづくハゲになりたいと感じました。
今回は前回記事で紹介したPokemon Online製対戦ライブラリを応用して、ポケモンバトルのAIを作りましたよという記事です。はてなブログの使いやすさに感動して涙を流しながら書いたので是非読んでください。
AIとは
こっちじゃなさそう
たぶんこっち。
本来の意味としては、本当に人間と同等の知的行動をするシステムのことです。ですがそんな某ネコ型ロボットみたいなものは現状存在しないので多少解釈を広げて、
人間しかできなさそうな複雑な思考過程を模擬した単一のプログラム・ソフトウェアだけを指して人工知能と呼ぶことが多いです。
例としては、上のURL内にもありますが画像のパターン認識、翻訳、あとは自動車の制御とか。
しかしここではこれを強調したい。
対戦ゲーム。
日本人的にたぶん一番有名なのは将棋。電王戦。
ポーカー(テキサス・ホールデム)で「無敵」だというAIも昨年の始めに話題になりました。
それと非常にタイムリーですが、先週あたりにグーグルが開発した囲碁のAIがニュースに載りましたね。
6×6オセロや五目並べなんかはもう必勝法が見つかっているらしいです。対戦前から完全解析してしまうとあんまり人工知能って感じはしないですが。
さて、
我が国には将棋やオセロと肩を並べるほどの超有名対戦ゲームがあります。
それは…
ﾎﾟｹ…
ポケモン！
この記事を読む方が最終的にどういう層になるのか分かりませんが、一応大方はポケモントレーナーであると思うので細かい説明は省きます。
このゲーム、コンピューターにやらせてみたいと一度は思ったことがあるでしょう。
但し書き
つかみで期待させといて申し訳ないんですが、ポケモンバトルと言っても今回取り扱うものには1つ大きく限定した点があります。
「お互いのPT情報は全て完全に分かっているものとする」
二人零和有限確定完全情報ゲームという厨二っぽいwordを聞いたことがある人もいると思いますが、ポケモンはものの見事にこれに当てはまっていません。
後述のミニマックス法は元々この二人零和有限確定完全情報ゲーム向けの手法なので、この枠組みに可能な限り近づけるための妥協案ということです。
ミニマックス法
それで、ポケモンバトルでどうやって「最善手」を導き出すのかという話。
本筋に入る前に、一応釘を挿しておくと
「完全解析は無理です。」
さっきも単語だけ出しましたがここで言っている完全解析とは、実現し得る全ての対戦パターンを列挙して勝ち手順を見つけることです。
ポケモンの場合は他の対戦ゲームと比べてターン数が少ないという楽さがあるのですが、それでも無理です。大ざっぱに見積もったらなんか1千万年くらいかかる計算らしいですよ。*1
というわけで、完全解析ができないから、対戦途中までの限られた先読みだけで工夫をこらして最善手を導く必要があるのです。
そのための方法が、ミニマックス法。王道を征く。
そのものズバリの解説は引用だけで済ませて頂きます。
珍しくWikipediaが分かりやすい
最大値をとって、最小値をとって、とかの探索手順を順を追って確認したい人はこちら
ここでは、ポケモンバトルへの応用例を説明します。
手前：バンギラス(かみくだく)、ファイアロー(ブレイブバード)
奥：ライコウ(10まんボルト)、ローブシン(ドレインパンチ)
という対戦を用意しました。ゲーム木の図示のためかなり単純にしてあります。
この局面において2手先までのゲーム木を生成すると次のようになります。
ここでオセロや将棋と違うのは、自分と相手の手を同時に実行するということです。
そのため、ゲーム木は必ず偶数段で作る必要があります。
かみくだくの方が評価値が高いので、2手読みの範囲ではこちらが最善手ということになります。直感通りの結果になってますね。
局面の静的評価関数
さて、息を吸うようにゲーム木が作れたみたいな論の進み方になってますが、1つ大事なことを説明し忘れています。
「局面の静的評価関数」
です。(ｲﾐﾜｶﾝﾅｲ人はさっきの引用URL見てネ)
実際のところミニマックス法のAIはこれをどう設定するかが全てで、かなり重要なところなんですが、
正直大した考察は未だにできていないので、結果だけさっと述べて終わりにします。
評価値＝(自分の残りポケモン数＋自分の残りポケモンの平均HP割合)
÷ (相手の残りポケモン数＋相手の残りポケモンの平均HP割合)
1つだけ言うと、残ポケ数を少し意識したかった。もっとよさげな式があれば誰か教えてください。
実装とか
結果的には半年かかりました。
対戦のシミュレーション部分は前回作ってあったので今回開発したのはその利用側です。
簡略化するとこんな感じで、左側のevaluateValue()関数を再帰的に実行させて木構造の全て*2の局面の評価値を求めています。
デバッグの用途も兼ねて、局面の状況をひと目で確認できるGUIも作ってみました。
Qtのフォームデザイナーで簡単に作ったものです。
前の記事でもチョロっと書きましたが、PO*3にはいい感じのPT作成画面(Teambuilder)があって、しかもテキストファイルでのインポート/エクスポート機能まで付いてます。
せっかくなので、先ほどのGUIにもPO形式でのPT読み込み機能をつけました。そのため試したいポケモンがいたらTeambuilderを立ち上げてささっとファイルを作るだけで簡単に読み込めます。シミュレーターとして普通に便利。
戦わせてみた
卒論でいえば実験方法と実験結果に対応するところですが、大学4年のみなさんはもう卒論は出しましたか？ぼくはM1なので毎日研究室で踊りながら卒論勢応援してます。
今回作成したAIの性能テストとして、
「シングル66での実戦テスト」を行いました。条件は以下の通り。
・ルールはシングルバトル 6 vs 6。伝説縛り・レベル制限などは一切なし
・お互いのPTはレベルも含めてランダム生成*4
・AI側は毎回深さ2での最善手探索を行い、評価値の一番高いコマンドを実行する
・相手側のコマンド選択は常にランダム
1戦目：勝ち
(うまく見えてないかもしれないので一応説明しとくとgifアニメになってます。1ターンごとの切り替わりですが。)
2戦目：勝ち
右側のログには各ターン各コマンドの評価値と実際に選択した手が流れてます。
3戦目：勝ち
メモには「的確に技を打って勝利 普通」って書いてあった
結果的には50戦試行して48勝2敗でした。
知能がありそう。
さすがにランダムbot相手だと当たり前じゃない？とか言われそうですがまあ最初なので。
人間(俺)と比べたらもちろんまだまだですよ
懸念事項
つくオフはAI使えないってマジ？
本当は割と真面目に書くつもりでしたが記事が長すぎてドン引きしたのでやめました
まとめ
ということで、知能がありそうなAIが出来上がりました。がりゅう城*5に来れば遊べます。
さすがに半年分の成果を1つの記事にまとめるのは無謀だったので、全体を薄く書いて文字サイズとか変えちゃってかなりウケ狙いの記事になりました。ウケる。
実装の部分とか無限に書くことが残ってるんですがそういう個別記事はツイッターのRT数を見て多かったら書きます(正直)。
以上、Yes, がりゅ can ! でした～～～
今週末はねんどろLIVEに行きます。
*1:シングル3vs3だと、1ターンにつき自分の手は平均的に技4つ＋交代1匹の5通りくらいです。相手も同じく5通りとしましょう。
とすると1ターン後の対戦局面ですら5^2 = 25通りあります。
対戦終了までに大体15ターンかかるとして、全部で25^15 ≒ 10^21 通りの対戦パターンが存在する見積もりになります。
ここからはさらに大ざっぱな見積もりですが、1局面の生成が1usで可能だとしても、10^15 [s] ≒ 10^10 [day] ≒ 10^7 [year]
もかかります。AZ(フラエッテおじさん)もびっくりの待ち時間。
*2:実際には全てじゃありません。俗に「枝刈り」と言われる計算上の工夫をしています。
*3:Pokemon Online
*4:そういう関数があらかじめあったので使ってるんですが、本当にランダムなのでたまにゲンシグラードンとか出てきます。つよい。
*5:ぼくの自宅のことです。伝わりづらいネタの説明にも使えるし脚注って神機能なんじゃないか。
