機械学習周りのプログラミング中心。 イベント情報
ポケモンバトルAI本電子書籍通販中

ゲーム木探索入門 part03 実験用パーティの選定【PokéAI】

前回に続き、ゲーム木探索の下準備をします。

従来行っていたような、ランダムに生成したパーティ1000個を戦わせるような実験が計算コスト上できない見通しです。ランダムなパーティ同士の対戦だと、ポケモンや技自体の強さが大きく離れている場合が多く、パーティ同士の組み合わせにより勝敗の大部分が決まってしまうため、行動選択のアルゴリズムの評価がしづらくなります。過去の実験で、強化学習したエージェントとランダムに行動するエージェントそれぞれにランダムなパーティを割り当てて対戦させると、強化学習側の勝率は7~8割となっていました。乱数による要因もありますが、プレイヤーとしての経験上もパーティ自体の良し悪しがバトルに与える要因が大きいことは間違いないでしょう。 そのため、行動選択のアルゴリズムを正しく評価するため、パーティ間の強さに大きな差がないこと、ランダムに行動を選ぶ場合と比べてちゃんと思考することで強さが向上するようなパーティを手動で選定することにしました。

実験用パーティの選定

パーティ間の強さをそろえるには、トップレベルのプレイヤーが採用しているパーティを選べばよいと考えられます。ポケモンバトルは対人戦が盛んであり、その中で洗練されたパーティの間では強さに大きな開きはないと考えられます。 プロジェクト全体の趣旨としてはパーティも自動で生成したいですが、バトル中の思考部分の強化に集中するため人間の知識を一時的に投入することを許容することとします。

まずパーティの候補として考えたのは任天堂による公式大会「ニンテンドウカップ2000」または「モバイルカップ2001」で代表選手が使用していたものです。しかしながらこれらの大会で使われたパーティの情報は、少なくともWeb上では見つけられませんでした。一部の試合のテレビ放送と思われる動画は見つかるものの、網羅的な情報とは言い難い状況です。

次に、ポケモン金銀のルールで対戦を楽しめる据え置き型ゲーム「ポケモンスタジアム金銀」のモードとして存在するニンテンドウカップに登場する敵プレイヤーのパーティが使えないか検討しました。しかしながら全ポケモンに「メロメロ」を覚えさせているパーティなど、そのパーティを用いるゲーム内のキャラクターのイメージに沿った構築がなされているようで強さのバランスが取れているとは言い難い内容でした。

上記のように公式情報からパーティを選定するのは難しいと判断したため、ファンサイトからパーティ構築を選定することとしました。 ここでは、ポケモン金銀バーチャルコンソール)の大会を開催されているゴールド氏の提示した構築例を用いることにします。ダメージ計算ツール等が普及した現代の環境で十分練られた構築であると考えられ、提示されているパーティ間に強さに大きな差はないと考えられます。また、様々な補助技も含まれておりこれらをうまく運用することが前提となっているため、行動選択の良し悪しが勝敗に大きく影響すると考えられます。

gold.hatenadiary.jp

11個の構築例が示されているため、そのうち先頭から10個を利用することとします。また、6匹*1から3匹を選出するルールを想定して記述されていますが、選出の機構は実装しないため、私が3匹を選んで固定することとします。必ずしも上から3匹ではなく、様々なポケモンが含まれるようにばらつきを加えています。以上の方法で構築したパーティを示します。当面はこれらのパーティを用いてアルゴリズムの評価を行います。

パーティ0
カビゴン  55 すてみタックル じわれ     のろい     ねむる    
ガラガラ  50 じしん     いわなだれ   だいもんじ   こごえるかぜ 
サンダー  50 10まんボルト めざパこおり  でんじは    ねむる    
------------
パーティ1
ケンタロス 55 つのドリル   すてみタックル じしん     みがわり   
パルシェン 50 れいとうビーム なみのり    こごえるかぜ  だいばくはつ 
ナッシー  50 サイコキネシス やどりぎのタネ ねむりごな   だいばくはつ 
------------
パーティ2
ラプラス  55 れいとうビーム つのドリル   メロメロ    みがわり   
カビゴン  50 のしかかり   ばくれつパンチ ねごと     ねむる    
ナッシー  50 サイコキネシス やどりぎのタネ ねむりごな   だいばくはつ 
------------
パーティ3
ミルタンク 55 おんがえし   ばくれつパンチ のろい     ミルクのみ  
ナッシー  50 サイコキネシス めざパむし   ねむりごな   だいばくはつ 
ゴローニャ 50 じしん     だいもんじ   ほえる     だいばくはつ 
------------
パーティ4
スイクン  50 なみのり    ふぶき     ねごと     ねむる    
エアームド 50 ドリルくちばし どくどく    のろい     ねむる    
ライコウ  55 かみなり    めざパこおり  ねごと     ねむる    
------------
パーティ5
バンギラス 55 かみくだく   ばくれつパンチ だいもんじ   すなあらし  
ハピナス  50 ちきゅうなげ  れいとうビーム でんじは    タマゴうみ  
エアームド 50 ドリルくちばし ふきとばし   のろい     ねむる    
------------
パーティ6
ブラッキー 50 でんじほう   おいうち    あまえる    ねむる    
カビゴン  55 おんがえし   はらだいこ   みがわり    まもる    
ワタッコ  50 めざパひこう  やどりぎのタネ アンコール   ねむりごな  
------------
パーティ7
ミルタンク 52 かげぶんしん  まるくなる   ころがる    ミルクのみ  
ガラガラ  52 じしん     いわなだれ   だいもんじ   こごえるかぜ 
カイリキー 51 クロスチョップ いわなだれ   めざパむし   じわれ    
------------
パーティ8
ファイヤー 55 だいもんじ   めざパくさ   にほんばれ   ねごと    
サンダース 50 10まんボルト でんじは    リフレクター  ねむる    
ヘラクロス 50 メガホーン   めざパかくとう こらえる    きしかいせい 
------------
パーティ9
フーディン 55 サイコキネシス れいとうパンチ アンコール   じこさいせい 
ヘラクロス 50 メガホーン   じしん     ねごと     ねむる    
サイドン  50 じしん     いわなだれ   カウンター   のろい    
------------

ランダム行動での強さ比較

アルゴリズムを開発する前に、ランダムに行動を選択した場合でパーティごとの強さにどの程度差異があるかを確認します。

ランダム行動において、交代を選択する確率は10%としました。1パーティ当たりのバトル回数を{10, 100, 1000}に変えて、各2回試行することにより、レーティングバトル(イロレーティング)の実施方法によりどの程度ばらつくかについても確認します。

f:id:select766:20201210213533p:plain
各パーティのレート

上図に各パーティのレートを示します。横軸のパーティの番号は、前の章のパーティリスト上の番号に対応します。レートは概ね1300~1700の間に収まっています。過去の実験で極めて弱いパーティはレート1000以下という場合もあったため、パーティ間の強さに比較的バランスがとれているといえますが、強さが同じであるという仮定は置くべきではないと考えられます。平均的に一番強いのはパーティ0、一番弱いのはパーティ3のようです。バトル1000回(試行1)のときのレートは1651と1352で、レート差299はパーティ0の勝率が85%であることを示します。試行ごとに同じパーティでもレートにばらつきが無視できない幅で(強さの大小関係が変化する大きさで)変化しています。バトル回数が100回から1000回に増えても収束が良くなるというわけではありません。この要因について、以下に示すレーティングバトルの具体的なコードに即して検討します。

function ratingBattle(players: Player[], matchCount: number): number[] {
    // 全プレイヤーのレートを1500に初期化
    const rates: number[] = (new Array(players.length)).fill(1500);

    for (let i = 0; i < matchCount; i++) {
        const ratesWithRandom = rates.map((r) => r + rnorm() * 200); // rnormは正規乱数。
        const ranking = argsort(ratesWithRandom); // (現在のレート+正規乱数)をソートし、隣接するパーティ同士を対戦させる
        for (let j = 0; j < players.length; j += 2) {
            const left = ranking[j];
            const right = ranking[j + 1];
            const sim = Sim.fromParty([players[left].party, players[right].party]);
            // players[left]とplayers[right]が1回バトルを行う
            const { winner } = playout(sim, [players[left].agent, players[right].agent]);
            // winner: players[left]が勝利したら'p1'、players[right]が勝利したら'p2'
            if (winner) {
                // レート差からleftの期待勝率を求める
                const left_winrate = 1.0 / (1.0 + 10.0 ** ((rates[right] - rates[left]) / 400.0));
                let left_incr;
                if (winner === 'p1') {
                    left_incr = 32 * (1.0 - left_winrate);
                } else {
                    left_incr = 32 * (-left_winrate);
                }
                rates[left] += left_incr;
                rates[right] -= left_incr;
            }
        }
    }

    return rates;
}

基本的な考え方は、レートの近いパーティ同士を対戦させ、その結果に応じてレートを変動させるというものです。対戦結果に応じてレートを変動させる部分で、勝ったプレイヤーのレートは上昇し、負けたプレイヤーのレートは下降します。ここで、期待勝率と実際の結果の違いが大きいほど、大きくレートが変動するようになっています。コードからわかるように、期待勝率0%のプレイヤーが勝利した場合にレートが最も大きく変動し、その変化量は32に固定されています。プレイヤーがランダムに行動するため、補助技を連打し続けるなどのミスによりレート差にかかわらず弱い側が勝つことは頻繁に発生すると考えられます。その場合に今までのバトル数にかかわらずレートが一気に32変動するため、バトルを1000回行っても最後の数回の勝敗に大きく影響されてしまい、試行によって結果にばらつきが生じていると考えられます。バトル1回あたりの変動の大きさを減衰させるようなパラメータを導入すべきかもしれません。ただしばらくは、パーティ数を10しか用いず強さの幅も小さいため、ここで示したアルゴリズムでレートを逐次的に収束させるのではなく、総当たり戦を行ったうえですべての勝敗にもっともよくあてはまるレートを算出してもよいのではないかと考えています。参考サイトでは、最尤法による計算について考察がなされています。 最尤法によるレート推定と不確かさ : コンピュータ将棋基礎情報研究所

今回は、強さにばらつきが小さく行動選択の良し悪しが勝敗に影響するようなパーティの選定と、ランダムに行動させた場合の強さの評価結果を示しました。よりよい強さの評価手段は将来検討するとして、次はゲーム木探索を実装したいと思います。

*1:私はポケモンを数える単位に「匹」を使うことが多いのですが、テレビアニメだと「体」が使われているのでそちらに統一したほうがいいかもしれません。