inani_waonの日記

コンテスト覚書

CodinGame Fall Challnege 2020参加記録

CodinGameのFall Challnege 2020に参加しました。

 

www.codingame.com世界 190/7036位

日本 56/320位

でした。日本人がおかしい。

ゴールドリーグのやや上位といったところで、残念ながら目標のレジェンドには届きませんでした。

 

ゲーム概要

tsukammo.hatenablog.com企業系Wiki、もといツカモさんのブログが詳しいです。いつもありがとうございます。

ボードゲームのセンチュリー:スパイスロードのパクリオマージュでしたね。ただし先手後手の概念を外して同時着手ゲームになっています。

 

ゲーム分析

基本的にボードゲームの攻略がそのまま流用できそうです。CASTでデルタ評価を増やしていき、途中でポーションという形に清算するゲームだと思いました。最速でポーションを作るよりも、上位デルタを残しておいて分解呪文で復帰するのが強いですね。

ポーションの先取り合戦要素もあり、同時着手の中で読むのは難しかったです。

私はこのゲームのコンセプトは「価値が流動的に変わる環境の中で最善を選ぶ問題」だと考えていて、評価関数による静的な評価が難しいことから探索部分の作りこみが肝だと思っていましたが、LEARNについては先が見えない状態で評価しないといけないことや、枝刈りもしないといけないことから評価関数も頑張らないといけない問題でしたね。

私は最終的にビームサーチ(BFS系列)で挑みましたが、コドゲ公式のタグはMonte Carlo tree search、BFS、graph traversalとなっており、好きなアプローチで挑める問題だったようです。

 

 やった事

Wood2

一番高い注文をこなす。 

Wood1

先頭の注文をこなす。

 低Tierデルタからチェックし、それ以上のデルタが不足していたら生成・アップグレードする。出来ることがなければRESTする。

Bronze

ここでシミュレータを書く。

ついでに原始モンテカルロでシミュレートできるようにして、各コマンド毎に勝率計算して一番勝てるものを採用。CASTはRepeat回数毎に分解して別コマンドとした。

シミュレータではBREWやLEARNの補充はランダムに行った。(補充ルールは明記されていなかったのでサーバを解析した)

序盤はターン毎に100戦弱、50ターン目で300戦程度シミュレートできた。

先頭5ターンはLEARN固定にしてみたけどさほど効果は無かった。

Silver

10ターンLEARN→ビームサーチ(幅400)→4回BREWしたらモンテカルロという方法を取った。これはビームサーチに終盤の勝敗を考慮する機能を積んでいなかったため。

評価関数は[獲得済点数+デルタ+呪文]とした。デルタはターン毎に減衰し、Tier2とTier3は注文も考慮して一定数以上は評価しないようにした。*1呪文評価は最大Repeat時に何点稼げるかと、4点行動で獲得済点数+デルタが80点取るには何回呪文をCASTする必要があるかで決定。*2Tierの偏りを防ぐため、Tier毎の生成数と消費数をチェックして偏りをもつ呪文にペナルティを与えた。*3

ビームサーチシミュレータは相手は動かず自分だけ動くシミュレーションで、BREWやLEARNの補充は行わなかった。

Gold

重複する枝の抑制のため、直前の行動から次の行動を制限した。ノードを合流する方法はオブジェクトの生成自体を抑えられないため行わなかった(言語と速度的な都合)

基本的にはBREW、LEARNは急がないと相手に取られてしまうケースがあり、ビームサーチにおいては評価の低い行動が枝狩りされやすい。そのためBREW・LEARN>強いCAST>弱いCAST>RESTの優先順で行動するようにした。

以下のルールにより、初期呪文の1点行動も探索への影響を小さくしつつ考慮できるようになった。ビーム幅400で、毎ターン10000ノードで10手くらい。

  • REST直後はRESTにより復活したCASTしか行わない
  • 順番を前後可能なCAST→CASTは、稼げる点数が多い順にしか行わない(同点はidが若いものを先に使うことにした)
  • CAST→LEARN、CAST→BREWはCAST実行前にも可能なら行わない
  • RESTから2ターンはREST禁止(これは重複ではないが、あまりに弱そうなので省いた)

ゲーム終了の概念を入れる。とはいえ、ゲーム完了と未完了を上手く区別しながらビームサーチする方法は浮かばなかった。そのため、6個BREWしてシミュレーション開始時の敵点数に負けていたら絶対に勝てないので-100点。逆に勝っている場合は、1ターン早く終わらせるごとに相手の行動を1個減らせるのでターン毎に+4点(自分はRESTしかしない)とした。

探索中のゲーム終了判定とは別に、1手詰めや2手詰めもある程度行った。これが出来るようになったので、モンテカルロシミュレータは廃止した。モンテカルロは原始的なものだと勝率100%になり、負けの可能性が出てくるまで緩い手を打ち続けて負けてしまう弱点があった。

ポーション先取り合戦の要素として、相手の行動をそれとなく考慮した。そのターンに可能なBREWは次ターンでは不可、そのターンに可能なBREWがなく次ターンに可能なBREWがあれば2ターン後に不可とした。

 

やりたかった事

ポーションまでの距離数を、 もう少し長い距離まで探索したかった。

ビームサーチで多様性を残すための工夫を入れてみたかった。

 

何も分からんだった事

 LEARNの評価。何を何回使うのが最善か、を計算できればもう少しリアルな評価関数が書けた気がする。動きを制御するための作りこまれた評価関数も美しいと思いますが、個人的には評価関数は事実に近いのが良いと考えています。

 

没戦略(噛み合わなくて廃棄)

呪文評価(1)

インベントリのパターン1001通りに対しての呪文評価を付け、その平均を呪文評価とする。また、同様に呪文同士のシナジー*4を計算し、手持ちの呪文同士のシナジーの総和も評価に加える。3色構成みたいな歪なLEARNになりやすく、また1001パターンも出現頻度が違ううえに呪文はRepeatできるように工夫して使うものなのでリアルじゃなかった。

呪文評価(2)

呪文評価に応じて重みを付け、想定使用回数を強力な呪文ほど多くする。ついでに下位互換互換の重みを低くしたり、個人的に気に入らない呪文を補正したり。これは上位に刺さりやすい一方で下位に負けやすく、大成功と大失敗に偏りやすいようだった。

 

 没戦略(ネタ寄り)

3色デッキ

あえて1色を捨てて3色で統一する。デルタのTier混成状態はRepeat呪文の効率が悪いため。しかしポーションに特定の色を含むかはほぼ半々なので、注文の半分をこなせなくなるのは痛く、特に相手の状況を読んで先回りするタイプには弱いと判断。

 

魔導書をTier0銀行的に利用する

 引き出しが面倒くさいし結構盗まれる。普通に探索中に考慮するので没ではなかった。

 

何もしない

実は何もしないのが正解のケースがあり、相手がトライフォース職人で行動不可かつ自分が獲得済み得点で勝っている場合は、下手にBREWしてTier3の消費先を出すよりもCASTとRESTだけして待ち続けた方が強い。しかしまあ、Gold上位ではなかなか無いケースだし相手が固まっていればそもそも自分有利だしで、優先して実装するものではなかったよねと。

 

総評

デルタのTier毎に[1,2,3,4]点という基準があり、適当にビームサーチを書くところまでなら楽で面白かったです。LEARNの構築やBREW争奪戦になると一気に想定できない域に入ってしまい、相性もあるのでここで完全に足止めされてしまった。

上位の人の考察を聞いてもLEARNはやっぱり何も分からんという感じで、実装要素はありながらも考察ゲーの部分が大きかったのかなと思いました。考察力を鍛えにはどうしたらいいのかな。

シミュレートの確度が下がるごとに報酬を下げるというのは前回のPACでもあったパターンなので、数をこなしてパターンを覚えるというのも1つの手段ですね…。

 

 

蛇足

お婆ちゃんネタ

このゲームは自キャラであるお婆ちゃん*5を操るゲームであり、開催中のTwitterではこの設定に乗っかったネタ発言が多く見られました。お婆ちゃんが動かなくなった、お婆ちゃんを改造する、お婆ちゃんの感度を上げる、etc…。

凝ったキャラ設定*6とビジュアライザがあり方針の言及も出来るコンテストなので、こういった楽しみ方も出来るのはいいですね。

TCGネタ

開催中、TwitterではこのゲームをTCGに例えて戦略を話す光景がよく見られました。元々TCG用語でもデッキタイプに厳密な定義は無いことが多いのですが、私はこんな感じで使ってました。

アグロ:相手のLEARNが済む前に動き始め、相手が回り始める前に決着を付けるタイプ。*7

ランプ:膨大なデルタを操り、特にBREW後に残したTier3から再始動するタイプ。*8

パーミッション:相手が取りたいBREWやLEARNを取り、相手の動きを妨げるタイプ。*9

 

 実装は苦しい点もありましたが、お祭り的にわいわい楽しめるコンテストでした。

以上となります。

*1:これをしないとTier3を10個作って行動不能になる、通称トライフォース職人になってしまう。

*2:実はバグがあり、ほとんど評価されていませんでした。

*3:全呪文の総消費が30で総生成が10なら消費呪文の評価を1/3にする

*4:ある盤面で呪文Aを唱えた後に呪文Bを唱えるとBだけを唱えるより良くなるか

*5:コタケとコウメ。

*6:キャラ設定を作ったのは任天堂では?

*7:LEARNの上11枚で決着を付ける。

*8:お婆ちゃん、荒野の再生は禁止になったでしょ。

*9:語源通り"許可を取る"行為は無いのでコントロールとかの方が適切かもしれない。

CodinGame デバッグ補助手法

現在CodinGame(以下コドゲ)ではFall Challenge 2020が開催されていますが、

コドゲ独自の仕様で詰まっている人が多そうなので、取り急ぎ解説を書き殴ってみます。

 
目次

 

 

デバッグ表示

ゲーム中に内部情報を表示してデバッグしたいこと、ありませんか?

表示しましょう。

 

サンプルコードに何か書いてますね。(下のはC#です)

// To debug: Console.Error.WriteLine("Debug messages...");

エラー出力することでデバッグメッセージを出力できるようです。

 

ゲームの説明にも何か書いてますね(下のはFall Challenge 2020です)

Append text after any command and that text will appear next to your witch

コマンドの後に何か書くとゲーム画面にメッセージを表示できるようです。

最近のコンペ形式のゲームではほとんどこうなっていると思います。

 

下の画像は、実際に出力してみた例です。

f:id:inani_waon:20201117140659p:plain
f:id:inani_waon:20201117140949p:plain
左:エラー出力によるデバッグ表示 右:ビューアによるデバッグ表示

できました。

 

ゲームの再現

既存のゲームをIDEで動かして誤動作の原因を探りたいこと、ありませんか?

再現しましょう。

 

自分のローカルIDE上(VisualStudioとか)で動作するプログラムに

ゲームの標準入力の内容を流すと、ゲームを再現できます。 

標準入力の内容は対戦結果には含まれていないので、

標準入力を受け取った際にそのままエラー出力に流してやりましょう。

(少し上の、エラー出力によるデバッグ表示がその例です)

 

コピペには少し手間取るので、全コピーした後に上手く置換するか

ユーザースクリプト等で一括取得できるようにすると捗ります。

 

標準入力以外の自分のデバッグメッセージと混ざらないように注意。

私は自分のデバッグメッセージは"@ "で始めるルールにして識別しています。

 

再現性を確保するため、以下の事に気を付けましょう。

・乱数のseedを固定する

・時間いっぱい回すタイプであれば回した回数を記録しておき、それも再現する

・その他、実行する度に結果が変わるコードを書かない

 

時間の計測

制限時間いっぱい探索して最適手を探したいこと、ありませんか?

計測しましょう。

 

プログラミング言語毎の時間計測ライブラリについては省略しますが、

私はC#ではSystem.Diagnostics.Stopwatch()、

C++ではstd::chrono::system_clockとstd::chrono::millisecondsを利用しています。

 

AIのソースコードはなんとなく次のようになっているはずです。(例はC#

while(true){

    // 入力

    string input = Console.ReadLine();

 

    // ぼくの考えた最強の処理

    string command = GetCommand();

 

    // 出力

    Console.WriteLine(command);

}

 

時間計測コードは何処に挟んでも良さそうな気がしますが、

ゲームサーバを介して複数のAIが動く関係上、空白の時間が存在します。

今回はゲームサーバから見た自分のプログラムの応答時間を知りたいので、

[入力を受け取った直後]~[出力を返す直前]の区間で処理時間を計測しましょう。

 

while(true){

    // 入力

    string input = Console.ReadLine();

 

    // ※ここで時間計測開始

 

    // ぼくの考えた最強の処理 ※時間を見て処理を打ち切る

    string command = GetCommand();

 

    // ※ここで時間計測終了

 

    // 出力

    Console.WriteLine(command);

}

 

こんな感じですね。

 

なお、出力してから次の入力までの間にゲームサーバや対戦相手が何らかの処理を回す空白時間があるのですが、この間はCPUを割り当ててもらえないため、この間に自分も裏で探索を進めるということは出来ないようです。

ソース:コドゲのフォーラムの何処か 思い出したら貼る

 

 

とりあえずは以上。

分からないことがあればコドゲのチャットやTwittterなどで聞いてみましょう。

 

 

 

HACK TO THE FUTURE 2021 予選 参加記録

HACK TO THE FUTURE 2021 予選に参加しました。

8時間のマラソン形式のコンテストです。

結果は153,119点で、提出者866人のうち208位。

 

atcoder.jp

 

問題

問題はカードの回収。

20x20のマス内にある0~99のカードを順番に回収するというもの。

ただし回収枠はスタック形式で、一度拾ったカードを再度置くことができます。

 

考察

移動量のみで得点が決まるので、カードを再配置して移動量を削減する問題。

回収しながら再配置を行う戦略、10x10に再配置してから回収する戦略を考察。

 

後者の得点の見積もりはある程度やったのですが、

前者の見積もりが全く出来なかったのでどちらで進めるか悩みました。

悩んだ末、ある程度道が見えている後者で進めることにしました。

(が、最終的には前者になりました)

 

究極的にはTSPだというのは分かったのですが、

出来ると思わなくて投げ捨てていましたね…。

 

方策

1.最小値のカードへ順番に移動する

カード毎に座標を記録して、差の分だけUDLRの後、Iを出力しました。

この時点ではロボット座標を動かしてシミュレーションすることはしませんでした。

 

2.10x10の領域にカードを集める

偶数段目を右方向に全走査した後に奇数段目を左から全走査。

というのを20段続け、更に10x10の範囲に置きなおすというコードを書きました。

道中にカードがあるか判定してあったらスタックに積んでと、ひたすらに面倒臭かった。

最後まで使うつもりでしたが最終的には廃棄されてしまいました。

 

3.中央にカードを集める

10x10にカードを集めた後、0~99を順番に回収します。

そのとき、道中のカードを中央に寄せることが出来るなら寄せます。

上下左右のうち2方向だけでランダムに10000ルートを探索しました。

 

ここまで作ったところで10x10に集めない方が得点が良さそうだったので、

集めない方針に変更してタイムアップ。

 

感想会

公式解説(上記問題内にリンクあり)を見た感じ、

上位は10x10に集めている人がほとんどでした。

(集めない方が強い説も出ましたが、時間内に形にすることも大事)

愚直に走査せずTSPで集めること、2-optが利用できること、などなど。

 

反省点

  • 真面目に分析できたのは良かった

・10x10集めの初歩までは公式解説と同じ分析ができた

  • 本質的な部分に全く着手していない

・TSP

・なんとなく中央に集めたけど連続数値を近くする考慮はしていない

・完全乱択から選択はしたけど焼いてない

 

やり切った感はあるものの、今思うと時間いっぱいやったというだけで

時間があればまだやれる事はありましたね。

方針に悩みつつ進めたというのはありますが、

1日未満のマラソンでは時間が不足しがちなので

スピードアップして本質的な部分を強化していきたいところです。

 

 

 

ゲームAIにおける戦略の考え方

 

はじめに

この記事は、対戦ゲームにおいて勝利を目指すゲームAIの戦略を考えるための記事です。エンタメとして人間を楽しませるAIには触れていません。また体系的な知識の紹介ではなく、私個人の考え方を書きだしたものになります。生暖かい気持ちで読むことをお勧めします。

 

この記事のターゲット

プログラミングは多少出来るけど、ゲームAIは何をすればいいのかよく分からないという方。AtCoderで言えば茶色か緑~、コドゲで言えば未経験~Silverリーグくらい?

 

早速の寄り道

ここでは取り扱いませんが、ゲーム理論で調べると色々出てくると思います。一部だけでも役立つので、見れる範囲で見てみましょう。

 

記事中で扱う用語

リソース

ゲーム内における、ライフ、お金などの資源です。見方次第では、計算時間などもリソースと言えます。

 

アドバンテージ

対戦相手と比較して、あるリソースで有利な状態を指します。リソースAではアドバンテージがあるけどリソースBではディスアドバンテージ(不利)がある、というケースもあります。

 

ステージ

ゲームによりますが、いくつかの段階(ステージ)に分けることが出来ます。これはゲーム側でステージが明確に分かれているというわけではなく、そういう考え方が出来るということです。ゲーム中に「そろそろ終盤だな」と思ったりしないでしょうか。そんな感じのやつです。

 

基本的な考え方

ゲームの進行とは、アドバンテージの取捨選択、あるいは対戦相手とのアドバンテージの交換です。ゲームには複数のリソースがあり、通常は何か1つのリソースだけを伸ばせば勝てるようには出来ていません。*1 何かを取るために何かを諦める選択の連続です。

では、何のアドバンテージをどれくらい得るように動くべきなのか?それこそがゲームAIの性能や個性を決める重要なポイントです。*2 ゲーム全体の構造を元に、ステージ毎の戦略を考えてみましょう。

 

ステージ毎の戦略

例として、少し複雑ではありますが、Age of Empiresシヴィライゼーション、League of Legendsのような戦略ゲームを考えてみましょう。*3

序盤戦は、リソースを稼ぐステージです。自軍をパワーアップさせ、索敵を行い、自陣を広く堅牢にし、より有利な状態で相手と接敵できるようにします。ユニットや建築物というリソースの獲得、情報というリソースの獲得ですね。これらのリソースが敵軍を上回れば、そのままアドバンテージになります。

中盤戦は、互いのリソースを削り合い、より多くのアドバンテージを生むステージです。有利なユニットをぶつけて、自分の槍兵5体と相手の騎兵10体を相打ちさせたりします。*4 この例では互いにリソースは消費しますが、相手の方が多くのリソースを失うため、アドバンテージを得ることになります。また、上手く情報アドバンテージを活かせば、無防備な敵拠点を被害なしで殲滅することも出来るでしょう。戦略ゲームが好きな人間からすると、この辺りが一番楽しいのではないでしょうか。

終盤戦は、それまでに得たアドバンテージを活かしてゲームの終結を目指すステージです。最終的にゲームに勝つことができるなら、それまでに得たリソースやアドバンテージをいくらでも投入できます。相手を詰ませることが出来るのか?失敗してアドバンテージを失い、逆転を許すことにならないか?自分が不利側なら、逆転の手は無いか?という緻密な計算を行うことになるでしょう。そういった詰み狙いと詰み回避を行いながら、合間にアドバンテージの獲得を狙っていきます。

このように、ステージ毎に戦略を分けることで人間が考える際に行動の指針を立てやすくなります。

 

ゲームAIへの戦略の組み込み方

人間である実装者が戦略を考えられるようになったところで、次にゲームAIにそれを実装する方法を考えましょう。

ルールベース*5の場合、終盤で取るべき行動ほど優先順位を上げて何の行動をするか決めればそれっぽくなるのではないでしょうか。『詰みチェック>アドバンテージの取得>リソース稼ぎ』のような感じですね。ただコドゲの下位リーグに関して言えば、終盤ステージを意識せずにアドバンテージの取得まで、あるいはリソースを稼ぐだけでもリーグ突破できるものが多い気がします。*6 終盤や中盤の動作は序盤の動作が前提になるという意味でも、実装は序盤に行うリソース稼ぎからすると良いでしょうね。

評価関数を用いたゲーム木探索の場合は、リソースまたはアドバンテージを評価に組み込みます。どのリソースを稼ぐべきか、どのリソースでアドバンテージを得るべきかを、値の大小により優先順位を付けてAIに教えてあげる感じですね。何のリソースの優先度を上げればいいの?ということについては一概に言えないので、そこは各々工夫してみましょう。ここについては後で別の記事としてコツを書くかもしれないし、書かないかもしれません。

 

TronBattleでの例

簡単な具体例として、コドゲ定番のTronBattleで実装することを考えてみましょう。上下左右いずれかの未踏マスに移動して、最後まで脱落せずに生き残った人が勝ちになるゲームです。リソースの種類(≒ゲームの奥深さ)は少ないゲームですが、その分ゲームAIの入門にはうってつけです。

初級(序盤戦略):残りの移動可能なマス数を、残りライフというリソースとして考えます。4方向それぞれに移動した場合の残りライフを計算し、残りライフが最大になる方向に移動しましょう。これはルールベースでもゲーム木探索でも出来ますが、DFSあるいはBFSによる数え上げが必要です。リソースを稼ぐというよりはすり減らしていますが、こういう例も稀によくあります。

中級(中盤戦略):対戦相手との移動可能なマス数(残りライフ)の差を、アドバンテージとして考えます。4方向それぞれに移動した場合のアドバンテージを計算し、アドバンテージが最大になる方向に移動しましょう。これ単体では初級との差が『相手より広い場所にいるときに細い道を閉じる』だけになりイマイチかもしれませんが、数手読みや、ボロノイ図等による見込み計算を加えると更に強力になります。*7 *8

上級(終盤戦略):『自分の移動可能マス数>相手の移動可能マス数』の盤面にできれば勝ち確定です。そんな盤面にできる手が見つかったらやりましょう。*9 逆に、『自分の移動可能マス数<相手の移動可能マス数』になる場所には移動してはいけません。 この挙動自体は中級の動きができれば既に出来ている可能性が高いですが、出来ていなければやりましょう。また、1位が無理なときに2位を確定させるなどで期待順位を高めることが出来ます。

 

 おわりに

長々と書いてはみましたが、特に目新しいことでもなく、おそらくは無意識でやっている人も多いのではないかと思います。また無理にこの枠に当てはめようとしても上手く行かないケースもあるかと思うので、こういう考え方の人もいるんだなという程度に参考にしていただければ幸いです。

自分はこういう考え方をしてるよ!というご意見があれば是非コメントかTwitterで教えてください。

 

*1:優れたゲームとはそういうものだからです。分かれ道があって右か左かでうんうん悩むのが難しく、また楽しいものなのです。

*2:余談ですが、それを考えずに手を探索できる構造もあります。MCTSとか。

*3:実はLoLはプレイしたことありませんし、他2つもにわかなので、変な事を言っていたらエアプ乙と笑ってください。

*4:とりあえずコストや盤面は無視して、多く討ち取れたからヨシ!ということにしましょう。

*5:if文連打マン。

*6:リソースの取得がそのまま点になり、勝敗判定に使われるパターン。

*7:中盤戦略と言いつつ最序盤から行える戦略なので、例として適切なのか分かりませんね…。

*8:2人対戦を想定しています。3人以上の対戦が解放されているなら、誰と比較して何位を狙うかは好きにやりましょう。

*9:ターン順による誤差はあえて無視しているので、実装する際は自力で計算してみましょう。

MCTSの評価伝達遅延を防ぐ方法(MCTS-Solver)

ネタバレ

ぼくのかんがえたさいきょうの手法は既出で、MCTS-Solverというようです。

 

はじめに

モンテカルロ木探索(MCTS)は、ゲーム木の各ノードを評価しながら探索を行える優秀な探索アルゴリズムです。

 

Wikipedia : モンテカルロ木探索

https://ja.wikipedia.org/wiki/%E3%83%A2%E3%83%B3%E3%83%86%E3%82%AB%E3%83%AB%E3%83%AD%E6%9C%A8%E6%8E%A2%E7%B4%A2

 

しかしCodinGame*1のUltimate Tic-Tac-ToeというゲームでMCTSを使っていたところ、シミュレーション結果が優勢にも関わらず、ある瞬間に劣勢に反転して負けてしまうことが多々ありました。ある手を指されると劣勢なのに、それが評価に反映されずに優勢と勘違いしている状態ですね。

 

f:id:inani_waon:20200705075604p:plain

左図:シミュレーション勝率79% 右図:1ターン後。シミュレーション勝率32%

一般に、MCによるプレイアウトはランダムに行われるため、1つだけ良い手(または悪い手)があるのに弱いとされているようです。今回の問題はそれに加えて正しい評価を親ノードに伝える力が弱いためではないかと推定し、その改善を図ったものです。

 

前提

説明をシンプルにするため、以下の前提とします。

・二人零和有限確定完全情報ゲームである

・ゲーム結果は「勝ち、負け」のみが存在する

・ノードの選択はUCB1-Tunedを使用する*2

 

また、木の階層によって手番プレイヤーが入れ替わりますが、手番が入れ替わっても解説における主語は同じプレイヤーを指すものとします。階層が変わるたびに主語を入れ替えると書くのも読むのも大変そうなので…!

 

MCTSの動作の特徴

MCTSは対戦シミュレーションを繰り返すことで良い手を探し、以降のシミュレーションではその“良い手”を選択することでよりシミュレーション精度を上げることができます。

しかしこれだけでは隠れた良手を探すことが難しいので、UCT (Upper Confidence Tree)などを用いて探索が不足しているノードの探索を行います。結果そのノードが良い手であれば選択されやすくなり、徐々に各ノードの評価が調整されるという挙動になります。

 

MCTSの動作の欠点

前述の通りノードの評価はシミュレーションを繰り返すことで徐々に調整されますが、浅い階層の”良い手”が変化するのにかなりの回数のシミュレーションを要します。例えば、良い手だと思って探索を深めたが実は負け確定である、という場合を想定してみましょう。

 

f:id:inani_waon:20200705081849p:plain

図:負け確定のノードAが選択され、ノードBの探索が進まない

 

上の図は、シミュレーション結果が500/1000で負け確定のノードAと、シミュレーション結果が10/100でまだ勝敗が確定しないノードBを持つツリーの例です。*3

ノードBが多く選択されるようになるにはノードBの評価がノードAの評価を上回る必要がありますが、ノードAの評価を0.1に落とすには最低でも500/5000とするために4000回のシミュレーションが必要です。*4

それまでは評価0.1のノードBを探索する頻度は低くなり、ノードBの探索が不充分になってしまいます。ノードBを充分に探索して親ノードの評価を正しくするには、更に多くのシミュレーションが必要になるでしょう。これが根ノードまで再帰的に発生します。

 

MCTSの動作の改善

上記の欠点を改善するため、勝敗確定時の評価をシミュレーション外で親ノードに伝えることにしました。動作の変更点は以下の通りです。

  • 決着ノードまで展開したとき、決着状態を親に伝播する

ゲーム木の本質として、手番プレイヤーは選択肢の中で一番良い手を採用します。*5最高評価(必勝)が1つでもあればその手を採用し、全ての手の評価が確定したときはその中で一番評価が良い手を採用します。

よって手番プレイヤーが必勝の手を選択できる場合は必勝、全ての手が必負であれば必負で決着済とみなせます。バックプロパゲーションに似た方法で、決着ノードから親を辿りながら決着したことを設定していきます。*6

  • 決着済のノードを選択から除外する

決着済ノードを探索することを回避して、未決着ノードの探索に専念できるようにします。必勝のノードは親ノードも必勝になりますし、必負のノードはいくら探索が不足していても絶対に採用することは無いので、選択する必要はありません。*7

  • 手の採用では決着も考慮する

採用という言葉はオリジナルで出しましたが、ここでは根ノードから実際にプレイする手を選ぶ行為を指します。

ここまでの動作変更により、勝敗確定がシミュレーションの成績に反映されていない状態になるので、手の採用時にそれを考慮する必要があります。私の場合、決着を親に伝播する時点で過去のシミュレーション結果を書き換えて、シミュレーション結果(=勝率)だけ見て採用するようにしました。

 

以上により、変更前よりも高速に親ノードのシミュレーション結果を正しい値に近づけることができるようになりました。下の図では互いのシミュレーション勝率の合計が約100%になるはずが135.5%と大きく齟齬があり、中盤以降のシミュレーション能力が大きく違うことが分かります。*8

 

f:id:inani_waon:20200705083349p:plain

図:シミュレーションの回数が実質増え、シミュレーション勝率もより正確に。

 

検討した事項

それって正しいの?シミュレーションが改悪されない?

伝播対象のノードは『選ぶべきでない子ノードの結果』というノイズが混ざらなくなるため、兄弟ノード間でシミュレーション精度が変わることは予想されます。ただMCTSは兄弟ノード間で子の展開状態が違うものなので、精度が違う情報同士で比較するというのはMCTSが元々持っている性質なんですよね。シミュレーション全体の精度がどう変わるかはケースによるため厳密に回答できませんが、MCTSやUCTが本来したい事を阻害してはいないと判断しました。

なお、この記事を書いている終盤で判明しましたが、この手法は既出でMCTS-Solverというようです。参考論文はもうちょっと後の方に記載しています。

 

過去のプレイアウト結果を改竄するのは美しくないのでは?

プレイアウト結果と選択用のスコアを別で持っても良いと思います。過去のプレイアウト結果を見たいこともあるかもしれません。例えば完全に負け確定のときに、相手のプレイミスに期待するため少しでもシミュレーション結果が良い手を選ぶとか。

 

引き分けがある場合は?

ゲーム結果が3値以上の場合、決着済みのノードを選択から除外するだけでは本来よりシミュレーション結果が悪くなることがあります。具体的には、引き分け確定の手があるのに他の手を選択して負けたというケースです。

しかしその場合も、「引き分けの子を持つノードに引き分け未満の結果が伝播された場合、自身と自身より親のノードでは引き分けと扱う」とすることで、最低結果を保証しつつそれ以上の結果を出せないか探索することができました。(ここは正しいのか自信が無いです…)

ゲーム結果が4値以上でも、最低保証の値を記憶することで同様の処理ができます。

 

この処理って重くないの?

決着の親への伝播はシミュレーション終了時、かつ末端ノードまで展開した場合にしか行われないので、私のケースでは他の処理と比べてとても軽かったです。(標準的な対戦で全体の1%未満)

ノード選択時に決着の判断をするのは多少コストがかかりましたが*9、私のケースでは処理全体の3%未満であり、性能の上昇で充分に回収できたと考えています。

 

でもこれ、未決着ノードには何も伝わってないよね?

はい。

当記事では、決着ノードより親のシミュレーション結果まで手を加えると、探索と知識利用のバランスがあまりに崩れるのでは?と懸念し、決着ノードより親に対しては、MCTS本来の、シミュレーションを重ねることでの修正能力に期待することにしました。

おそらくここの手法次第で探索の性質が変わると思いますが、その点は検証しきれていません。あえて何もせず兄弟ノードとの精度差を出さない方がいいのか、本来勝っていた分を負けに塗り替えるのがいいのか、必敗ノードの探索自体を無かったことにするのがいいのか、はたまた何をしようがそこまで差は出ないのか…。*10

 この点については数学や選択関数に強い方の見解を聞いてみたいです…!

と思いましたが、論文を見つけました。

 

情報学広場:モンテカルロ木探索における子孫の勝敗確定時のプレイアウト結果の修正

https://ipsj.ixsq.nii.ac.jp/ej/?action=pages_view_main&active_action=repository_view_main_item_detail&item_id=175332&item_no=1&page_id=13&block_id=8

 

「結果を塗り替える 」「無かったことにする」それぞれが選択関数に与える影響を分析しており、別の手法の提案もあります。素晴らしいですね。ここでMCTS-Solverの存在を知りぐぐってみましたが、日本語の情報は少ないようです。

 

更に上手く活用するには

ノードを決着まで展開させなければこの手法は使えないため、ゲームの決着判定自体に先読み機能を持たせることが有効でした。*11

例えば神経衰弱なら、『相手の獲得枚数+場の枚数<自分の獲得枚数』であれば最後までプレイしなくても勝利確定であることが分かります。

 

終わりに

手法の正しさに確信が持てない状態で記事を書き始めましたが、裏付けを取っていくうちにそれなりに実績のある手法であることが判明しました。

 MCTS-Solverより先のステップについてはまだ調査を進めていない状態ですが、MCTS-Solver相当でも一定の性能向上は見られたため、1つの区切りとしてここまでの車輪の再発明記録を残しておく次第です。

 

*1:ゲームAI対戦プラットフォームです。

*2:UCT系列であればなんでも良さそうです。

*3:数値は説明のための適当な値です。

*4:説明のために簡略化しましたが、実際にはノードAを探索して勝ちの葉ノードに到達することもあるでしょうし、ノードBのシミュレーション結果も変化するのでもっと複雑です。

*5:貪欲法という意味ではなく、深く探索した結果が一番良い手という意味です。

*6:うちの場合は決着フラグを立ててどちらが勝ったかを設定しました。

*7:勝ちが確定しても最後までプレイする必要はあることに注意しましょう。

*8:レート0.7差と僅差の相手で、中盤までは合計勝率がほぼ100%になることから、序盤性能の差は小さいと推測しました。

*9:フラグを見るだけのシンプルなif文なので、データ構造とメモリアクセス効率の問題かもしれません。

*10:私のケースでは決着ノードの親にも「結果を塗り替える」を適用してみましたが、さほど差は出ませんでした。兄弟ノードとの差を無視すれば、「無かったことにする」が一番正しそうに見えますね…。

*11:勝ちが判明しても最後までプレイする必要はあることに注意しましょう(2回目)