Rustでヒューリスティックコンテストを解いてみる

Rustのお勉強として、RustにIntroduction to Heuristics Contestの解答を移植しました。

atcoder.jp

気になるポイント

私は競プロではC#を使っているのですが、だいぶ書き方が異なる部分があり戸惑っています。 C#だとこう書く、というのが煩雑な書き方になったり、不可能だったりするのでそこの見極めができないと厳しい。。

以下、自分なりに工夫した点ですが、より良い方法があれば教えて頂けると助かります。

ローカル環境とAtCoder環境の切り替え

ローカルでは便利クレートを使い、AtCoderではそれらをコンパイルしない、としたいです。
フィーチャーフラグを使うことで対応しました。

[features]
default = ["local"]
local = []
#[cfg(feature = "local")]
use log::{debug, error, info, warn, LevelFilter};

struct Logger {}

#[cfg(feature = "local")]
impl Logger { 
    // loggingの記述
}

#[cfg(not(feature = "local"))]
impl Logger {
    // 何もしないメソッドの実装
}

入力

proconioに頼るのも良いのですが、今回はローカルではファイルからの読み込みに切り替えたいため、普通に書きました。 マクロを書くとだいぶ扱いやすくなります。

#[macro_export]
macro_rules! input_value {
    ($f: expr, $x: expr) => {
        let mut line = String::new();
        $f.read_line(&mut line).unwrap();
        $x = line.trim().parse().unwrap();
    };
}

#[macro_export]
macro_rules! input_vec {
    ($f: expr, $x: expr) => {
        let mut line = String::new();
        $f.read_line(&mut line).unwrap();
        let mut iter = line.split_whitespace();
        $x = iter.map(|v| v.parse().unwrap()).collect();
    };
}

let mut D: i32;
let mut C: Vec<i32>;
let mut f: Box<dyn std::io::BufRead>;
if config.is_local {
    f = Box::new(BufReader::new(File::open("input/input_02.txt").unwrap()));
} else {
    f = Box::new(BufReader::new(std::io::stdin()));
}
input_value! {f, D}
input_vec! {f, C}

Vecとusize

Vecのインデックス参照を行うときにi32型は許してくれず、usize型でないとエラーになります。
D[i as usize][j as usize][(k + 1) as usize] は可読性が厳しいと思ったので、トレイトを作って対処しましたが、もう一声すっきり書きたいなぁという感じです。

trait IndexAt<T> {
    fn at(&self, i: i32) -> T;
    fn mt(&mut self, i: i32) -> &mut T;
}

impl<T: Copy> IndexAt<T> for Vec<T> {
    fn at(&self, i: i32) -> T {
        self[i as usize]
    }
    fn mt(&mut self, i: i32) -> &mut T {
        &mut self[i as usize]
    }
}

// 2次元配列に対応する記述は省略

atメソッドで値を取得、mtメソッドで可変参照を取得なのですが、できればポインタは自動で外したい・・

// 1次元配列に対応するVecを参照する
if self.command.at(d) == k {
    last = d;
}     

// 2次元配列に対応するVecを更新する
*last_contest.mt(d, k) = last;

時間測定

wataさんのコードが参考になります。
スタティックライフタイムで開始時間を保持しているのですが、 関数内で定義した変数が関数を抜けても保持され続けるのはなかなか面白いですね。

// https://atcoder.jp/contests/intro-heuristics/submissions/14855120 より
pub fn get_time() -> f64 {
    static mut STIME: f64 = -1.0;
    let t = std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap();
    let ms = t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9;
    unsafe {
        if STIME < 0.0 {
            STIME = ms;
        }
        ms - STIME
    }
}

グローバルな静的クラス

Rustだと、グローバルな静的クラスに相当するものが作りにくいです。 lazy_staticを使う方法など試しましたが、どうしても煩雑になってしましました。 結局、Config構造体やInput構造体の参照をどんどん渡していく方法としています。

Enum

Enumが強力だということで、とりうる行動（今回ではコンテストの交換、コンテストの変更）をEnum型にしてみました。 EnumのVariantを関数の引数にはできないため、構造体を作る必要があります。
また、パターンマッチでムーブしてしまうので、Copyトレイトを実装しなくてはいけません。
Enumを使わない場合に比べて、ちょっと扱いやすくなったような、そうでもないような。

#[derive(Debug)]
enum Action {
    Swap { action: ActionSwap },
    Change { action: ActionChange },
}

#[derive(Debug, Copy, Clone)]
struct ActionSwap {
    d1: i32,
    d2: i32,
}

#[derive(Debug, Copy, Clone)]
struct ActionChange {
    d: i32,
    k: i32,
}

new_score = match action {
    Action::Swap { action } => state.score_swap(action),
    Action::Change { action } => state.score_change(action),
};

if annealer.accept(state.score, new_score) {
    match action {
        Action::Swap { action } => state.update_swap(action),
        Action::Change { action } => state.update_change(action),
    }
}

参考文献

Rustを学ぶにあたって、以下を参考にさせていただきました。

Rustの日本語ドキュメント、プログラミング言語Rust日本語版
https://doc.rust-jp.rs/
https://doc.rust-jp.rs/book-ja/

実践Rustプログラミング入門
www.amazon.co.jp

序盤の章で言語の特長や抑えておくべき概念、文法をざっくり説明してくれるのが分かりやすかったです。

実践Rust入門[言語仕様から開発手法まで]
https://www.amazon.co.jp/dp/4297105594

AtCoderコンテストにRustで参加するためのガイドブック
https://doc.rust-jp.rs/atcoder-rust-resources/

Kaggle Haliteを強化学習で解こうとした話

本記事は 強化学習苦手の会 Advent Calendar 2020 - Adventar 8日目の記事とするべく、コンペ終了後に書いた記事に追記しました。

7日目の記事(Kaggleの強化学習コンペがグダグダだった話 - Qiita)への返歌みたいなものになります。

雑感

  • 強化学習でどこまで行けるんだろう、ということで勝敗に拘らず強化学習を試してみましたが、何も考えないと思っていたより厳しいなぁという印象でした。

    • 「岩塩のあるところまで行く」→ まぁまぁ簡単にできる
    • 「岩塩のあるところまで行って、スタート地点まで戻ってくる」→ 工夫しないと厳しい
    • 「岩塩のあるところまで行って、スタート地点まで戻ってくるのを複数の船で協調する」→ さらに厳しい

  • 結局、カリキュラムラーニングじみたことをやって、「岩塩のあるところまで行って、スタート地点まで戻ってくるのを複数の船で協調する」までは出来ました。
    ただ、ルールベースならそこまで難しくないことではありますね。

  • AlphaStarやOpenAI Fiveはもっと難しい問題を解いているわけで、彼らと同じリソースをつぎ込めば上位には来れたのだとは思います。 そこの差が、どこまでリソースの差で、どこまでが手法の差なのか。私は強化学習苦手なので、当たり前のことを見落としていることはありえます。

  • 典型的な強化学習の課題設定は単独のAgentの行動をコントロールするものが多いようですが、この問題は複数の船の行動をコントロールするというのも難しいポイントで、ライブラリをそのまま突っ込むことができません。私はPFRLを改造しましたが、結構時間と精神力を持っていかれました。

  • コンペで強化学習を使え、とは言っていなかったように思います。

  • コンペとしては良コンペだと思いました


    （kaggle-environmentsのコードは解読が大変だったので、不満はありますが・・笑）

  • 1位の人のソリューション
    https://www.kaggle.com/c/halite/discussion/183543
    手法の概要からソースコードまで付けてくれて、言うこと無い有り難いシェアだと思います。
    印象的なのは手数の多さと、良くこの量のコードをバグらせずに書き続けられるなという感じですね。



（以下は9月に書いた記事です）

KaggleのHalite by Two Sigmaを強化学習で解こうとして、1か月ほど頑張っていました。

www.kaggle.com

@higeponさんと@Seed57_cashさんとチームを組んで、情報共有しながらやっていました。

最終Submissionはこのような感じです。複数の船でHaliteを集めて基地に搬入する、というところまではできましたが、他のプレイヤーに勝てるAIにするには、ここから何個か超えなくてはいけない壁があるようには思います。

予想どおりでしたが、強化学習で動きを学ばせるのはかなり大変ですね。 ルールベースだと簡単な動きも、何も工夫をしない強化学習だと一晩回してもまだしょっぱい動きだったり、なかなか厳しいものだなと。

取り組んだことを記述して行きます。一応念のため、以下にはご注意下さい。

  • 単純なミスをしていて、本来できるはずのことができていない可能性はあります
  • 強化学習のプロがやると一瞬で悩んでいた問題を解決したりするかもしれません

1. Haliteのルール

ルールは以下の日本語概要が分かりやすいです。
https://www.kaggle.com/iicyan/japanese-halite-introduction

さらに要約すると、

  • 盤面は21x21、4人対戦
  • 各プレイヤーはターンごとに行動を同時に指示する
  • 指示の対象は、それぞれの船（待機・上下左右移動・基地への変換）と基地（待機・船の生産）
  • 最初に各プレイヤーは船を１隻保持している。盤面にはHalite（岩塩）が配置されている。
  • 基地はコストを払って船を生産できる。船は基地に変換できる。
  • 各Haliteは時間経過とともに上限まで徐々に増加する
  • 船がHaliteの上で待機することによりその25%を船に貯め込む（Collect）
  • 船が基地に到着することで、溜め込んだHaliteをそのプレイヤーが取得する（Deposit）
  • 船同士が衝突したとき、最もHaliteが少ない船が勝ち、その他の船からHaliteを奪い取り船に貯める
  • 400ターン終了時に最も多くHaliteを最も保持している人の勝ち

2. 全体的な方針

2-1. ライブラリの利用

やってみると痛感するのですが、強化学習は至るところにバグを埋め込むポイントがあり、スクラッチで書くのはリスクがあります。 また、新しめの手法を気軽に試しやすいことを考えて、ライブラリを使うことにしました。

今回使ったのはpfrlですが、以下のような利点があったように思います。

  • コードが読みやすい
  • さまざまなアルゴリズムに対応している
  • PyTorchベース
  • 並列で環境を動かせるため、効率的に学習できる
  • 経過時間やスコアなどのを容易にログ出力できたり、TensorBoardに対応している

github.com

他にもOpenAI Stable Baselineなど、いくつか強化学習用のライブラリがあります。

github.com

2-2. タスクの解釈

このタスクでは、船の生産や船から基地への変換は考えないことにするとしても、複数の船の行動を選択する必要があり、ここが悩ましいポイントです。 よく強化学習の対象にされるAtariのゲームでは選択肢から行動を選ぶだけですし、このように複数の対象の行動を選択するというタスクの例はあまり見つけられませんでした。
（MADDPGという手法など、そのような研究はあるようです  https://github.com/openai/maddpg）
結局、それぞれの船ベースで報酬が最大となるように行動を選択するタスクと解釈して、まずは進めることにしました。

なお、先行してこのコンペに上位で強化学習をしていた参加者がいて、その方のアプローチも参考にしました。 https://www.kaggle.com/c/halite/discussion/169623#948042

また、StarCraftをプレイするAlphaStar、Dota2をプレイするOpenAI Fiveも複数の対象の行動を選択する点は近いように思います。 （大規模すぎて良く分かりませんが・・・）OpenAI FiveではTeam Playという要素により対象間の連携を反映しているようです。

（参考）
https://note.com/npaka/n/nb719e603b4aa
https://note.com/npaka/n/n16ac9b6004bd

3. １隻でHaliteを集めることを学習させる

まずは「1隻、1プレイヤー、30ターンで最も多くHaliteをCollectする」タスクを学ばせました。

DQNで、雑なネットワークを元に作ってみたところ、これすら上手く学習できないのには驚きました。一晩回したり、Rainbowを試してみてもまだ微妙な動きでした。
試しにアルゴリズムをPPOに変えてみたところ、上手く行き、数分程度で良い動きを学ぶことができたため、以下はPPOメインで進めています。
（本当は動かした時間やステップを記述すべきなのですが、コードも試行錯誤していた段階なのでデータを捨ててしまっている・・）

4. １隻でHaliteをDepositすることを学習させる

次に、「1隻、1プレイヤー、30ターンで最も多くHaliteをDepositする」タスクを学ばせます。 これが厳しかったです。

Depositするには、HaliteをCollectしたあと、基地に戻る必要があります。 強化学習のエージェントには盤面と行動に対する報酬のみが渡され、何も分からないまま動き、報酬を得て学びが進んでいくわけですが、 Depositによって報酬が得られることを学ぶには、Haliteを集め「偶然」基地に辿り着く必要があります。 しかし、ランダムに進んでも簡単には辿り着かないため、報酬が疎に与えられることになります。

うまく学習できず局所解にはまっているようで、上下運動のみを繰り返すことしかしなかったり、基地の周りをぐるぐる回るAIが発生しました。 また、まずはCollectを学んでそのうちDepositも学んでほしい、という意図でCollectにも報酬を与えましたが、高くしすぎるとDepositを学ぶことをあきらめてCollectばかりするようになりました。

PPOのパラメータのチューニングやその他の工夫を試しましたが、結局明確に効いたのは以下の２つでした。

  • アップデートまでに集めるエピソード数を増やす
    PPOで方策をアップデートするまでの間隔を増やしていくと徐々に良くなりました。ただ、学習の進みは当然遅くなります。

  • モデルのネットワーク構造に行動の性質を取り入れる（@Seed57_cashさんの貢献）
    盤面と対応させたCNNから、対象が中心になるように盤面をスライドさせた（np.rollを用いた）のちに、上下左右の移動位置のセルの値を抜き出し、層を通して行動選択のSoftMax関数に通すようにしました。
    行動と盤面の関係性が明示的にモデルに伝えられるためか、これによりかなり動きが自然になりました。

納得行く動きを得るには1000万ステップ、10時間程度学習させる必要がありましたが、これでDepositまで学べるようになりました。

5.  複数隻でHaliteをDepositすることを学習させる

5-1. 複数の行動対象への対応

そして、「複数隻、1プレイヤー、30ターンで最も多くHaliteをDepositする」タスクを学ばせます。

ライブラリ内の処理では、一つの環境の遷移に対して一つの行動・報酬が対応しますが、ライブラリを改造し、遷移に対して複数の船による行動・報酬が対応するようにして進めました。
報酬の処理も気をつける必要があり、今回のルールだとHaliteが少ない船は味方から奪った方が得になってしまいます。 それを抑止するよう、味方から奪ったHaliteはペナルティにするなどの調整を行いました。

ただ、「Depositするためには基地に戻らなくてはいけない」と「基地の近くは密になって衝突しやすい」がコンフリクトする要素であり、 最初から学習させようとしてもあまり上手く進まなかったため、下記のカリキュラム学習を適用しました。

5-2. カリキュラム学習

強化学習でカリキュラム学習という手法について聞くものの、実際にはどうやるんだ、という気持ちです。 結局、以下の順に学習を進めていきました。これが正しい方法かは分からないのですが、少なくとも学習時間は節約できて便利ですね。

  • 「1隻、1プレイヤー、30ターンで最も多くHaliteをDepositする」タスク
  • 「1隻、4プレイヤー、30ターンで最も多くHaliteをDepositする」タスク
  • 「複数隻、4プレイヤー、30ターンで最も多くHaliteをDepositする」タスク 
  • 「複数隻、4プレイヤー、100ターンで最も多くHaliteをDepositする」タスク 
  • 「複数隻、4プレイヤー、400ターンで最も多くHaliteをDepositする」タスク 

6. 提出

基地が船を生産するかどうか、また船を基地に変換する動きも強化学習させて判断させたかったのですが、 時間的な都合もありここまでで、Kaggleへの提出をします。

@higeponさんのNotebookが参考になります。
https://www.kaggle.com/c/halite/discussion/164005

ポイントは以下のような感じ：

  • 強化学習エージェントの行動選択の部分のみ抽出し、提出するファイルをsticky_tapeで一つの.pyファイルにまとめる
  • モデルはbase64でエンコードして、文字列として提出ファイル内に保存する
  • 出力するファイルの制限は100MBとかなり余裕があり、大きなモデルもサブミットできるようです。
    （なお、今回の作成したモデルのサイズは100kB程度でした）
        https://www.kaggle.com/c/halite/discussion/161588
  • Kaggle Dockerに入っていないライブラリは手で依存部分を貼り付けるなどする必要があります。学習でなく推論部分のみなので、それほど大変ではありませんでしたが。

7.  有望なアプローチの考察

今回はそこまでたどり着けませんでしたが、こんなことできないかなーと考察していたものです。

良いアルゴリズムの利用

  • 今回はPPOを使用しましたが、もっと探索効率の良いアルゴリズム・工夫はありそう
  • 私が試したときはDQN/RainbowはPPOに対して劣っていたが、本当にそうなのかどうか
  • PPOはon-policyのアルゴリズムで、ヒューリスティクスとの統合を考えたときにはoff-policyのアルゴリズムの方が自由にできそう？
  • このタスクでは難しそうですが、AlphaZeroやモンテカルロ木探索が使えればその方が良さそう

ヒューリスティクスとの統合など

何らかの形でヒューリスティクスと統合できれば、効率的な学習ができそうです。

  • Abstract Action
    「上下左右に動く」を選択対象の行動にするのではなく、「最も近くの基地に帰る」「最も近くの敵に近づく」といった戦術の単位を行動とする手法です。この考え方がハマるタスクであれば、効果がありそうです。
  • 盤面のモデルの活用
    今回のタスクでは、盤面がどのように遷移するかのモデルが明確に分かっていますが、単純に強化学習を行う場合は、報酬だけが与えられせっかく分かっている盤面のモデルが使われません。
    例えば、次の盤面を予想するタスクを追加で解かせる、といったアプローチはありそうです。（既にそういった手法は誰かが考えていそうですが。Muzeroなどもこの発展といえる？）　　 　
  • 大まかな戦略はルールベースで作り、個別の動きは強化学習で学ばせる
    本当は戦略についても学んでほしいところですが、なかなかに厳しいので、そこを妥協したアプローチです

模倣学習

他のプレイヤーの対戦データも落とせたので、模倣学習を上手くできれば上位に入れる可能性はあるのではないかと思います。 最初から学習させるより学習時間も節約できるでしょうし、対戦相手が手に入ると下記のリーグトレーニングなどを節約でき、効果的です。 GAIL（Generative Adversarial Imitation Learning）といった手法が有名なようです。

Fictitious Self-Play, リーグトレーニング

いわゆる「じゃんけん環境」では、自己対戦を繰り返しても戦略がぐるぐる回ってしまう可能性があります。
そのため、AlphaStarでは、Fictitious Self-Playや他のプレイヤーの弱点を突くことを主目的とするプレイヤーを作る、といったアプローチが使われていたようです。

tadaoyamaoka.hatenablog.com

8.  （参考）強化学習の計算時間

強化学習では学習のステップ・エピソードをたくさん回したいのですが、計算時間は主に以下から構成されます。

  • 環境の更新などのCPU処理
  • 行動選択の推論のGPU処理
  • モデルの学習のGPU処理

CPUやGPUの使用率を見るほか、環境を並列にして回してみる、行動選択をランダムに差し替える、モデルの学習をスキップする、とするとボトルネックの箇所が把握できます。

今回のタスクでの計算時間は以下のようになりました。
（PCはi9-9900K 8コア、GeForce 2080Ti。強化学習の環境は8並列で計算した。）

  • 1隻・1プレイヤーで、環境をCythonで高速化すると10000ステップが4秒。（学習のGPU処理がほとんど）
  • 1隻・1プレイヤーで、環境を高速化していないと10000ステップが20秒。
  • 5隻・4プレイヤーで、環境を高速化していないと10000ステップが200秒。（環境の更新などのCPU処理がほとんど）

Connect Fourをちゃんと強化学習できた話

アルファ碁ゼロの手法で、Connect FourというゲームのAIを強化学習で作成させてみました。

Connect Fourは、「重力付き四目並べ」のようなゲームです。（四目並べ - Wikipedia）
そこまで探索空間が大きすぎず、またソルバーもあるため、強化学習が正しくできるかのテスト用としては妥当なゲームでしょう。なお、正しく打てば先手必勝です。

参考文献の「AlphaGo Zeroの手法でリバーシの強化学習をやってみる」のコードをforkしたものを元に作成しました。 Connect Four用に直し、自分の好みで構造を整理しています。

コードは以下にアップロードしました。細かい工夫がたくさんあり複雑な割には分かりやすくなったはず・・

github.com

学習結果

  • 環境：
  • 学習時間：
    • 18時間程度、170000ゲームの自己対戦
  • 強さ：
    • 先手番はほぼ10割の勝率
    • 後手番は完璧なソルバーには当然勝てないが、10%ランダムに打つソルバーには5割、30%ランダムに打つソルバーには9割勝てていて、ほぼ悪手は適切に咎められる感じ
      　（以下、先手番を黒番、後手番を白番ということにします）
    • 100000ゲームくらいから十分な強さになってくるか。170000ゲームでもまだ収束しきってはいなく、もう少しだけ強くなりそうです。

参考文献

AlphaGo Zeroの手法でリバーシの強化学習をやってみる

https://qiita.com/mokemokechicken/items/a5803b4280751848e36b
https://github.com/mokemokechicken/reversi-alpha-zero
アルファ碁ゼロの手法の細かい工夫がしっかりと実装されていて、今回大変参考にしました。

最強囲碁AI アルファ碁 解体新書 増補改訂版

https://www.amazon.co.jp/dp/B07F11T4CS
手法が分かりやすく説明されている書籍です。

Lessons From Alpha Zero

https://medium.com/oracledevs/lessons-from-alpha-zero-part-6-hyperparameter-tuning-b1cfcbe4ca9a
丁寧に書かれており、単なるアルファ碁ゼロの手法だけでなく、学習を高速化するためのさまざまな工夫が書かれています。コードが無いのだけが残念。

SOLVING CONNECT 4: HOW TO BUILD A PERFECT AI

強化学習でなく、探索ベースのConnect4のソルバーの作り方が説明されています。
http://blog.gamesolver.org/

また、Webアプリとしても公開されていて、作成したAIの強さを確認するのに便利です。 https://connect4.gamesolver.org/en

Kaggle Connect X

https://www.kaggle.com/c/connectx
Kaggleで以前行われたメダルなしのコンペです。モデルのアップロードはできないはずなので微妙かも。

なお、Connect4をアルファ碁ゼロの手法で十分に学習できたというコードやモデルは見つけられませんでした。

さまざまなポイント

今回やってみて気づいたさまざまなポイントについて記述していきます。

アルファ碁ゼロの手法

今回は、AlphaGo Zeroの手法に加えて、AlphaZeroの手法のようにモデル同士を戦わせることを省略するようにしました。
ざっくりとまとめると、以下のようになります。

  • 自己対戦による棋譜データをもとにモデルの学習を行う。次の手を指す確率（ポリシー）と盤面の評価（バリュー）を同時に学習するデュアルネットワークを用いる
  • 自己対戦の着手はモンテカルロ木探索により決定する。
    • 探索の中で未評価のノードに到着した場合、モデルによる推論を行う。推論によりポリシーとバリューが求まり、バリューをその探索の勝敗とする。
    • 探索の中で評価済のノードに到着した場合、今までの探索の勝敗とポリシーから次の手を決定する
    • 探索を複数回繰り返し、最も選択された手を着手する。
  • 特にモデル同士を対戦させることはせず、棋譜がたまるとモデルの学習を行い、自己対戦用のモデルを更新する

アルファ碁関連の手法はAlphaGo, AlphaGo Zero, AlphaZeroとあり、混乱しやすい名前となっています。
（AlphaGoとAlphaGo Zeroの違いは「最強囲碁AI アルファ碁 解体新書 増補改訂版」が分かりやすいです）

自己対戦ワーカーと学習ワーカー

アルファ碁ゼロの手法の構成として、自己対戦ワーカーと学習ワーカーを作成し、それぞれのプロセスを常に動かしておくのが良さそうです。

  • 自己対戦ワーカーは、自己対戦し学習データを生成しつづける。定期的に学習ワーカーによって作成されたモデルを読み込み、アップデートする
  • 学習ワーカーは、生成された学習データをウォッチし、十分に溜まっていればモデルの学習を行う

AlphaGo Zeroメソッドではモデル同士を対戦させて上回っているときのみ更新するため評価ワーカーが必要ですが、AlphaZeroメソッドでは不要になります。
今回は、学習の進行状況を把握するために、プレイヤーとソルバーを戦わせる評価ワーカーを動かしています。

着手の選択か、モンテカルロ木探索での選択かの区別

「次の手の着手を何によって決めるか」と「モンテカルロ木探索の中で次の手を何によって決めるか」を区別する必要があります。

  • 着手選択は、モンテカルロ木探索で探索した回数が最も多い手を指す
  • モンテカルロ木探索での選択は、探索での勝率であるQ値と、次の手を指す確率（ポリシー）などで求められるU値を加重平均した値が最も大きい手を指す

実際にはここに、

  • 着手選択は、序盤はモンテカルロ木探索の（最も回数の多い手でなく）回数に比例した確率で指す
  • モンテカルロ木探索での選択にはディリクレ分布によるノイズを与える

などのオプションが入ってくるため、混乱しないように理解しておくことが必要ですね。

どっちの手番問題

二人ゲームの探索を書くと、普通は相手番をひっくり返しているうちに混乱してしまい、相手評価が最も低い手を打つべきところで最も高い手を打つような類のバグが発生しがちです。

今回は、このような処理になっています。

  • 着手選択では、黒番に変換する （白番であれば、盤面をひっくり返して自分が黒番だと思い込む）。
  • モンテカルロ木探索では、黒番も白番もあるが、評価値は常に黒番からの評価を返すようにする（白番であれば、評価を反転させる）
  • ニューラルネットの推論・学習を行うデータは、次の手番ベースに変換する。
    • つまり、（次の手番のnp.array,  次の手番でない方のnp.array）の組を入力とし、
      次の手番が指す確率（ポリシー）と次の手番側の評価（バリュー）を返す

並列および非同期処理による効率化

アルファ碁ゼロの手法では、新しい盤面がモンテカルロ木探索で出てくるたびにニューラルネットの推論を行います。 ここで、これを並列や非同期処理を何も考えずに行ってしまうと、バッチサイズ1の推論を延々とGPUで行うことになり、かなり非効率になってしまいます。

そのため、以下のような流れで並列および非同期で自己対戦を行うと良いでしょう。

  • 並列で、自己対戦ワーカーを動かす。つまり、複数のゲームを同時に行う
  • 自己対戦ワーカーで、Pythonのasyncioなどの非同期処理の枠組みを使う。
    つまり、各ゲームでのモンテカルロ木探索は非同期に行い、推論のデータを投げて待っている間には他のノードの探索を進める
  • 推論データが一定以上溜まったらニューラルネットでの推論を行い、結果を返す。

このようにするとGPUが効率的に扱えるため、結構CPUがボトルネックになる印象があります。特にPythonで雑な盤面の更新を行うと速度に影響が出てきます。

メモリリーク

細かい計算を大量に行うためか、ずっと流しっぱなしにしているとメモリが枯渇して落ちてしまうことがあります。

  • keras.backend.clear_sessionを行う
  • 定期的にプロセスを再起動する
  • ニューラルネットライブラリのバージョンを適切にする

などの対処法がありますが、現状完全には解決できていなく4-5時間連続で流すと再起動が必要になるようです。 つらいので、いずれ再調査したいです。

評価の難しさ

Connect Fourはソルバーが存在し、AIが指した手が合っているか間違っているかを把握できるのが素晴らしい点です。

当初、昨年末に学習を試みた際には、「SOLVING CONNECT 4: HOW TO BUILD A PERFECT AI 」のテストケースを使って、

を出力させていました。

正答率は8-9割までは行くのですが、それ以上には上がらず、十分に学習できていない、と思い込んでいました。

しかし、改めてソルバーと対戦させてみたところ、勝ちの状況からは負けず、負けの状況から相手が悪手を指したときには勝ちになる手を正しく指せていました。 おそらく、上記テストケースには適切に打った場合には到達しない盤面も含まれているため、強いゲームAIが必ずしもそれらの盤面を正しく評価できる必要はないということなのでしょう。 さらに、ゲームAIとしては、モンテカルロ木探索を行うため多少のニューラルネットの評価の誤りは修正してくれます。

対戦相手となるAIと対戦させるのが適切な評価といえそうで、今回は一定の確率でランダムに指し、それ以外では最適な手を指すソルバーと対戦させて勝率を測ることにしました。

ソルバーによる手数制限

試行錯誤する過程で、一定手数が経過したときにソルバーで勝敗判定して打ち切る機能を追加しました。 例えば、勝敗判定の手数を7手にすると当然ながら自己対戦や学習は高速に進み、1時間くらいで収束します（それでも100000ゲームくらい必要なようですが）

パラメータや手法が有効かどうかを確認するためには、このようにゲームをフルでやらずに一定手数に制限した環境で試すと効率的でしょう。

フロントエンド何もわからない（その４）

今回は、かなり自分用のメモです。

やりたいこと

  • 計算結果のデータをGCP上に貯めたのちに、Vue.jsなどを使ってビジュアライズしたい。
  • 自分しか使わない

ソリューション

いろいろ調べた限り、以下が良さそうでした。

構成

  • ミニマムに作るとき
    tornadoなどのpythonサーバで、Vue.jsを用いたhtmlを呼び出す構成にする
    python側でデータの処理を行いREST APIを用意し、javascriptで呼び出す

  • もうちょっと頑張るとき
    フロントエンドをNuxt.js、バックエンドをflaskなどのpythonサーバという構成にする
    やはりpython側にデータの処理を任せる

データ

配置場所

認証が問題なく通るので、フロントエンド・バックエンドともにローカルで立てるので良いかと思いました。
Web上で構成したい場合には、Google App Engineを使うのが良さそう。

その他

  • フロントエンドとバックエンドに分けると、CORSの処理をしなくてはいけない。
    flaskでCORSの処理をする場合は、以下のStackOverflowの回答が分かりやすかった https://stackoverflow.com/a/52875875

Google Cloud Runで想定外の課金が発生した話

ヒューリスティックコンのパラメータチューニングをGCPでやる - threecourse’s blogを試している中で、Google Cloud Run（以下、Cloud Run）で1万円使ってしまったので、 同じようなことを試す人がもしいたら（あまりいないと思いますが・・）ということで注意喚起のためにもメモ。

やったこと

  • Cloud Run内で、最適化プログラムを動かす
  • 1回の計算は4秒で、その中で5万行くらい標準エラーに出すようにしていた
    （コンペ用のプログラムで、雑多な情報を提出時に無視される標準エラーに出すようにしていた）
  • 計算をトータルで2万回くらい投げた

何が起こったか

対策

教訓

  • この程度で済んで良かったが、下手すると桁が違ってた可能性があるので怖い
  • 他の人がやっていないことをやるとき、サービスをよくあるユースケースと違うことに使うときには気をつけましょう
  • 課金のアラーム設定や見積もり、内訳をちゃんと確認しましょう（見積もりもちょっと遅れてやってくるので難しい部分はあるのだが・・）

ヒューリスティックコンのパラメータチューニングをGCPでやる

AtCoderのヒューリスティックコン（https://atcoder.jp/contests/intro-heuristics）のような短時間のコンペのパラメータチューニングをGCPで行ってみました。
理想のラン環境を求めて - threecourse’s blog のつづきです。
（ソースコードは、敵に塩を送りたくない整理できていないので公開せず、考え方のみまとめています。）

概要

  • GCPを使って、並列でOptunaによるパラメータチューニングを行う
  • Google Cloud Run（以下Cloud Run）というサービスを使うと、計算時間の短い計算を比較的簡単にスケーリングしてくれる
    （他のサービスだと、クラスタの構成が面倒だったり、起動時間がかかったりする）

設定と結果

設定は以下のとおりです：

  • Introduction to Heuristics Contest（https://atcoder.jp/contests/intro-heuristics）を問題とする
  • 焼きなまし解法の「終了温度」「開始温度／終了温度」「2点スワップの割合（残りは1点更新）」をチューニング対象のパラメータとする
    （参考：Introduction to Heuristics Contestの解法 https://img.atcoder.jp/intro-heuristics/editorial.pdf）
  • パラメータチューニングのために100試行を行う。
  • パラメータの評価に用いるスコアは、10テストケースの平均をとする。
  • 10並列 x 5バッチ（2ケースごとのバッチにする）で並列処理させる

結果は以下のようになりました：

  • 並列なしだと2秒 x 10テストケース x 100試行で2000秒かかるところ、90秒程度で計算完了（なかなか実用的）
  • ベストのパラメータは、（開始温度・終了温度・2点スワップの割合）＝（2488, 556, 0.79）となった。 解説を参考に作成した（開始温度・終了温度・2点スワップの割合）＝（2000, 600, 0.5）と同程度の結果となった。

雑感：

  • AtCoder環境の方がCloud Runより2倍程度性能が良さそうなので、Cloud Runでの計算時間は2倍程度にすると良さそう。
  • チューニングを繰り返すと微妙なパラメータがベストとなることもあり、「最適なパラメータチューニング」となっているかは分からない。 引き続き要検討だが、試行回数を増やすのが良いような気もする。

構成

全体の流れ

パラメータチューニングの全体の流れは、以下のようになります。

  1. Optunaの初期化を行う
  2. Google Cloud Storage（以下GCS）にテストケースとバイナリをアップロードする
  3. Optunaでの並列パラメータチューニングの実行を開始する
  4. 各パラメータの試行では、
    ・10個のテストケースを実行し、その結果の平均をスコアにする
    ・10個のテストケースの実行は、2ケースごとのバッチにしてCloud Runに計算依頼を飛ばすことで行う
    ・Cloud Runの計算において、GCSからテストケースとバイナリをダウンロードする
    ・10並列で行う（つまり、10並列 x 5バッチ = 50個の計算依頼が飛んでいる状況になる）
  5. パラメータの試行100ケースが全て終わると、最も良いパラメータを選んで終了する

最適化プログラムの構造

パラメータを受け取り、計算結果を返せるように、最適化プログラムを組んでおく必要があります。

  • 引数として「名前」「テストケース名」「各パラメータ」を受け取り、
    結果である「スコア」や「焼きなましの計算回数/更新回数」などの補助情報をjsonファイルなどに出力する仕組みにします。
  • こうすることで、外部からPythonなどを用いて、最適化プログラムを並列で叩いてその結果を取得できるようになります。
  • このまま提出するとWrong Answerになってしまうので、コンパイル定数などを用いて手元でコンパイルしたときと提出したときの挙動を変える必要があります。

Optuna

Optunaは、改めて非常に使いやすいツールですね。

その他、以下の機能が便利でした。

Cloud RunにデプロイするDockerイメージ

Cloud Runは、リクエストを処理している間のみ課金され、また自動的にスケールしてくれるという素晴らしいサービスです。

Cloud Runを使うためには、httpリクエストを受け取り、レスポンスを返すDockerイメージを作成する必要があります。
今回は、flaskでhttpリクエストの処理を行い、その中でC#の最適化プログラムを動かすため、C#とPython（Anaconda）を動かせる構成にしています。

Dockerイメージ内の処理は、以下のような流れになります。

  1. httpリクエストのデータとして、「ランの名前」「計算対象となるケース名のリスト」「パラメータ」を受け取る
  2. 「ランの名前」を基にGCSからテストケースとバイナリをダウンロードする
  3. 「計算対象となるケース名のリスト」の各ケースを「パラメータ」を指定して実行し、結果を取得する
  4. 結果のリストをレスポンスとして返す

Cloud Runの設定

最大100までインスタンスを立ち上げ、インスタンス内の同時実行数は1、実行時間制限は（一応）15分、インスタンスはCPU1個、メモリ512MBという設定にしました。

同時実行数を1にすることで、複数の計算で同時にCPUを使うことを防ぎ、正しく計測できるようにしています。 たまになぜか計算回数が半分くらいになることがあるようですが、概ね計測に問題は無さそうです。 もう少し攻めた設定にしても良いかもしれません。

なお、インスタンスがスケーリングしている最中には、429や500といったレスポンスを返すことがあるので、それらのときには少し待って再度リクエストを投げるようにする必要があります。

Cloud Runの料金はそれほどでもないのですが、ログには注意が必要です。 標準出力がログとして飛んでいってしまうので、最適化プログラムで一定間隔ごとに焼きなましの温度などを出力するようにしていると、1回のチューニングで数十GBのログが飛んでいくことがあるようです（怖）。GCPのログ取り込みで除外設定を作成するか、最適化プログラムを叩くときに標準出力・標準エラーをDEVNULLなどで抑止する必要があります。

追記：
threecourse.hatenablog.com

継続的インテグレーションについてのメモ

参考資料

少し古いが、テストの分類など以下のスライドがよくまとまっている。

www.slideshare.net

また、CircleCIでチュートリアル＋αをやりました。 circleci.com

（CircleCIのドキュメント、Orbs・ジョブ・アーティファクトといった用語の具体例がなかなか出てこないので、初心者には分かりづらいような・・）

その他、以下の書籍を参考にしました。

継続的インテグレーションとは？

定義は上記文献や継続的インテグレーション - Wikipediaを参照。

私の理解では、常に「クリーン」な状態を保ちながら開発するために、ソースコードのバージョン管理とテスト・ビルド・デプロイを自動化して接続すること。CIと略記される。

CIサーバ

継続的インテグレーションを行うために、以下のCIサーバと呼ばれるサービスがある。

  • CIrcle CI
  • Google Cloud Build
  • GitHub Actions
  • JenkinsやTravisCIなど

CIサーバでは、以下の設定を行うことになる。

  • ビルド、テストといったジョブを定義する
    設定ファイルはyamlなどで記述する
  • トリガーを指定する
    Pushされたとき、プルリクエストが送られたときなど、ジョブを起動するトリガーを指定する
    APIを叩くなどで手動実行もできる
  • GitHubやBitBucketなどと連携設定をする

CIサーバは、以下の機能を持つ。

  • トリガーとなるイベントが発生すると、上記のジョブを実行する
    ジョブは、docker imageを用いて行われる。また、並列や依存関係を考慮して実行が行われる
  • テストに失敗するとそのジョブは失敗する。
  • アーティファクトと呼ばれるビルド時生成物を保存する仕組みがある
    アーティファクトの例は、テストのカバレッジやビルドされたバイナリなど
  • ジョブの状況、テスト結果やアーティファクトをWeb画面から見ることができる

雑感

  • ユニットテストだけで良いのなら、CIサーバを用いて綺麗な流れで開発できそう。
    結局は、時間や手間のかかるテストをどう扱うかが問題になる。
  • 上記書籍などでもその議論がなされている。時間などでテストの種類を階層化し、時間のかかるテストはコミットごとに行うのではなく定期実行する、といったアプローチになる
  • 開発においては、プルリクエストを送る前に手元でテストしたい気もする。それらを考えると、トリガーとか複雑なワークフローよりも、任意のタイミングで任意のジョブを実行して、結果をいい感じに管理できるようにしたい