Article
・Kaggleやデータ分析初学者向けのチュートリアル解説本を執筆しました。本記事とあわせてご参照くださいませ。
『Pythonで動かして学ぶ！Kaggleデータ分析入門』
・その他のKaggle参戦記事一覧はメニューのKaggle挑戦記事からご参照くださいませ。
・その他のKaggle参戦記事一覧はメニューのKaggle挑戦記事からご参照くださいませ。
はじめに
今回はKaggle UMコンペこと、「UM – Game-Playing Strength of MCTS Variants」の参戦振り返り記事となります。 モンテカルロ木探索のバリエーションによるAIエージェント同士の様々なボードゲームの対戦において、AI1のAI2への勝率を予測するというお題で、オーソドックスなテーブルコンペなものの、いくつかの工夫やアプローチが効果的であり学びの多いコンペでした。結果はteamでの参加でprivate LB23位でsilverとなりました。本記事では本コンペの取り組みやscore推移、上位ソリューションを振り返っていきます。
| (1) UMコンペの概要
本コンペでは、AI agent1/2のアルゴリズムに関する特徴、およびボードゲーム/ルールに関する806の特徴量（Idなどは除く）が与えられ、複数試合したときのagent1のagent2に対する勝率(-1〜1の間。-1がagent2の完全勝利。1がagent1の完全勝利)を予測するというものでした。agentが対戦するゲームは同じボードゲームでもルールが異なるものがあり、またtrainとtestでは与えられるゲーム/ルールが異なることが示唆されていました(agentアルゴリズムはtrainとtestで同じ)。なお予測精度の評価指標はRMSEでした。
以下、簡単にデータ概要について記載します。まず、agentのアルゴリズムは下記72パターンの組み合わせがありました。
・[SELECTION]：選択フェーズの戦略。UCB1/UCB1GRAVE/ProgressiveHistory/UCB1Tuned の4通り
・[EXPLORATION_CONST]：探索定数。0.1/0.6/1.41421356237 の3通り
・[PLAYOUT]：プレイフェーズの戦略。Random200/MAST/NST の3通り
・[SCORE_BOUNTDS]：スコア制限。true/false の2通り
同じagent同士の対戦はなく、全てのagent同士の対戦が何らかのボードゲームにおいてログがありました。おおよそagent同士の組み合わせあたり平均45のゲームルールの対戦ログが存在していました。全てのゲームルールにおいて全てのagent組み合わせの対戦ログが存在するわけではないということになります。また元々のデータにagent1とagent2を入れ替えたデータが含まれているものの、シミュレーションによる勝率を計算したログのため、agent1とagent2を入れ替えたログは単純に勝率が反転しているというわけではなく、少なからずランダム性によるノイズが含まれておりました。
勝率は-1から1の値を取りますが、各agent組み合わせ・ボードゲームルールセットごとに15試合(稀に30試合あるいは45試合)シミュレーションした結果による勝率のため、離散値となります。0を中心とした正規分布ではなく、-1や1が多い傾向があります。
またagentはどのようなゲームルールでも強い最強のagentがあるというわけではなく、agentごとの組み合わせあるいはゲームルールによって勝率は大きく異なりました。下記は単純なagent組みわせごとの勝率のマトリックスです。
ボードゲームルールセットには806の特徴量がありましたが、特徴量間で全く同じ値となるもの、nullの値や固定の値となるものがあり特徴選択を丁寧に行う必要がありました。
| (2) 本コンペの取り組み
本コンペに取り組むに当たり考えたことは以下のことでした。
・追加データをどのように作成するか
本コンペでは独自のゲームルールセットを自身で定義し追加データを作成する手順が共有されていました。しかしこの手順は手間とコンピュータリソースががかかるため多くの参加者は公開されていたtrainデータのみを用いていたようです。一方で、前述の通り各ゲームルールセットごとに全てのagent組み合わせがtrainログにあるわけではないため、pseudo用の大量の追加データを作成することが容易に可能です。
・ルールによって明確に勝敗が決まるゲームの後処理
たとえば「ターンが非常に長いゲームにおいてはいかなるagent組み合わせによっても必ず引き分けになる（シミュレーションが終わらない）」、「ランダム性がなく完全に先行有利なゲームの場合、先行のagentが完全勝利になる」などルールベースで定義できそうなことがいくつかありました。もちろんモデルにそれらを学習できるといいのですが後処理をかけることでセーフティーバーとしてスコアを微増することが考えられます。
・離散値となるターゲットを予測結果からどのようにアサインするか
前述の通り、ターゲットは15試合のシミュレーションによる勝率のため、連続値ではなく離散値となります。回帰モデルで学習して予測すると連続値になります。この値をどのように後処理できるのかあるいはどのようなアプローチをするのか、工夫のしがいがありそうです。
・特徴量をどのように選択するか
前述の通り、特徴量は多いものの、重複しているものや固定値となっているものもありました。これらの値は除外するとして全く同じ値ではないものの相関が高いものなどいくつかの基準で選択されるべき特徴量があり、それらを精査していくことが考えられます。
・testに対してどのようなcv戦略を行うか
testデータはunseenなゲームルールセットであることが示唆されている中で、group k foldがベースラインとして考えられそうですが、ゲームルールセットごとに完全勝利や引き分けとなりやすいゲームなど傾向が大きく異なります。これらをどのように各foldに割り振るか工夫が必要そうです。
下記が最終的な私のアプローチの概要となります。
(step.1) trainデータの特徴量選択。固定値や重複カラム以外に、相関が高いもの、値が特定の値以外の出現率が低いものなどを削除して300ほどに絞り込み。
(step.2) 特徴量生成。agent1とagent2のアルゴリズムの差異の距離や、agent1のアルゴリズムとゲームルール特性を組み合わせた特徴などを追加。
(step.3) cvはgame nameのgroupでcold rate（-1,1という極端な値になる割合）をgame nameごとに算出し、それをstratifiedしたskgfの5foldで分割。
(step.4) 「勝率を回帰」「勝ち数/負け数を回帰で予測した上で勝率計算」「勝率を0〜1の間に変換してxentorpyを誤差とした分類モデル」の3アプローチで予測。
(step.5) 上記モデルのバリエーションを複数作成した上で各モデルの予測値をnelder-meadでアンサンブル。
(step.6) 上記で求めた予測に対してゲームルールの値に応じてルールベースで後処理(-1/0/1になるゲームの割り当て)。
(step.7) 上記の後処理を経た結果に対して-1/0/1/それ以外となる分類モデルを学習した上で-1/0/1がある確率以上となるデータを後処理。
(step.8) 各ゲームルールごとにtrainデータに含まれていないagent組み合わせに対して、上記フローで予測した勝率をつけたpseudoデータを作成し、trainに加える。
step.2の特徴量生成では、「実際のagent同士の対戦において先行がどれだけ有利か」を示す予測特徴量が大きく寄与しました。先行有利関連ではAdvantageP1という特徴量がすでに与えられていたものの、それはランダムな動きをするagent同士の対戦において先行有利かどうかを示すため、実際のagent同士の対戦では微妙に先行有利の意味合いが異なります。その他、step.4の様々なアプローチ、特に回帰問題に対してtargetを0〜1の値にscalingすることでxentropyを誤差として適用できるということはアンサンブル上、大きな利点でした。実際、私自身は今回初めて使用したものの、これまでkaggleの過去様々なコンペの上位ソリューションで採用されていたアプローチだったようです。step.8のpseudoデータ作成はスコアを大きく引き上げてくれたのですが、どのようなagent/ゲームルールの組み合わせデータを追加すべきか、もっと粘れたとも思います。さらにstep.1の特徴量選択は粘れば粘るほど精度が高くなった上に、特徴量選択の仕方でモデルの多様性を出すことができるため、ここにももっと力を入れるべきでした。
なお、予測値に対して連続値からの離散値への当てはめはscipyでガウスカーネルによる重み付けによるsoft assignはじめ様々なアプローチを実装したのですがcvにoverfitしてLBの向上には繋がりませんでした。この点は何かよいアプローチがなかったかと今でも考えます。
なお、今回は中盤以降、masanoryさんとチームマージして2人チームで取り組みました。masanoryさんからは様々なアイデアの示唆をいただき、特に上記で言うとstep.2、step.4、step.5あたりは彼のアイデアが大きく寄与しています。また基本的にはお互いのアプローチを深くは共有せず(githubでコード共有はしていたものの)、アンサンブルの多様性をだすように努めました。彼は公開notebookのアプローチを中心に、様々なバリエーションを作成することで良いスコアを出すことができていました。
| (3) 上位ソリューション
1位ソリューションは下記のとおりでした。
・追加特徴量：各アルゴリズムにおけるバランスや探索スピード特徴量をシミュレーションして計算。
・モデル:LightGBM(DART)、CatboostのほかTabMを使用し、Nelder-Meadでアンサンブル比率計算。
・追加データ:14,365行の追加の学習データを生成(484個の新たなゲームルールセットを生成)。
・特徴量選択:自身でシミュレーションしてホストから与えられたデータの特徴量と比較、一致していない特徴は削除すると精度向上（特徴量選択は1つ1つ削除ではなく複数同時に削除が重要だったとのこと）。
正直、追加データの生成や特徴量生成含め、試していないアプローチが非常に多く、与えられた情報を全て活用しているように感じました。私自身、コンペ期間中にyandexからリリースされたTabMはキャッチアップはしていたものの、実際には使用していませんが、シングルモデルとして非常に有用だったとのことで次回以降のテーブルコンペでは必ず試してみようと思いました。
その他、上位ソリューションは概ね我々よりも比較的シンプルなアプローチが多かったのですが”flip aug”というデータ拡張に関して多くの上位入賞者が工夫して取り入れていました。これはagent1とagent2の対戦結果のログに対して、agent1とagent2を入れ替えた上で勝率であるターゲットを反転させるというデータ拡張となります。ここでターゲット変数だけを反転させるのではなく、AdvantageP1という変数も反転させることが重要でした。さらにBalanceというゲームバランスを表す変数も反転させるとより良いデータ拡張になるようでした。正直このデータ拡張はコンペ初期に思いついたものの、もともとagent1,agent2を入れ替えたログは存在していることから特に深く考えずに採用しなかったという悪手をとってしまいました。ちなみにlate subにより検証したところ、もし私の上記アプローチにこのデータ拡張を採用したとしたら金メダル圏内である10位相当のスコアが得られたようです。
| (4) おわりに
本コンペを2つの観点から振り返りたいと思います。
・最終盤でもう一度これまでの実験を振り返る
今回、flip augが強力だったのですが、最序盤に思いついたことで深く考えずに棄却してしまいました（実際には少し試してうまくいかなかった）。もし最終盤でこの実験を振り返ることができていたら、そして正しくcvスコアを出すことができていたら採用できていたはずです。序盤・中盤ではbaselineやアプローチが固まりきっておらず実験が不安定であることもあるため、必ず最終盤にうまくいかなかった実験・アイデアも含めてもう一度振り返ることが重要だと思いました。
・正しいはずのアプローチには様々なパラメータ設定ふくめ時間をかけて粘る
上記flip augもそうですがその他の細かいアプローチ・実装に関して、少しの設定違いで大きく精度が異なるものがありました。これらに関してデフォルトの設定や仮に決めたパラメータで満足せず、とことんパラメータを探索してから次のアイデアにいく必要性を感じました。ただ同時にあるアイデアが効果的かどうかは、別のアイデアと同時に試すことが前提であることもあり、うまくいくはずのアプローチがうまくいかないときに別の要因が原因であることもあるため、前述の通り、いくつかの実験を経て振り返る必要があると思いました。
private23位は自己ベストではあるのですが、スコアも密で少しの工夫で金圏に手が届いたと感じるからこそ、悔しい思いも残るコンペではありました。
余談ではありますが、コンペ終了日にボードゲームカフェでゲームをしながらコンペの振り返りをしたのは良い思い出です。
以上、UMコンペの振り返りとなります。
関連記事:
人気記事:
