poetry publishでPyPIに勝手に公開されないのかどうか

poetry publishをうっかり実行してしまい、privateなファイルが全世界に公開されると困るので。。 自分だけならまだ注意すれば良いけど、人に薦めることを考えると気になります。

結論

poetry new <package-name> からpoetry publishをしてみたところ、以下のようにまー大丈夫っぽい。

他の言語

C#の.NET Coreでは、dotnet publish コマンドは違った位置づけで、あくまでローカルに発行するだけ（のはず）。
https://docs.microsoft.com/ja-jp/dotnet/core/tools/dotnet-publish

Rustのcargo publishでは、publish = falseオプションがある。
opt-inにすべきでは？というIssueがある。
https://doc.rust-lang.org/cargo/reference/manifest.html#the-publish-field
https://github.com/rust-lang/cargo/issues/6153

ソフトウェアのアーキテクチャについて

最近、小〜中規模のプログラムを保守性高く記述するにはどうすればよいかが気になっていて、 ソフトウェアのアーキテクチャについて調べていました。

本を読んでみる

以下の本を浅めに読み通してみました。どの本もそれぞれ学ぶべき点があって興味深かったです。

学んだこと

疎結合の重要性

とにかく疎結合にすることが重要。分割すると脳のリソースにも優しいし、分担して作業できるし、テストもできる。

インターフェイス

インターフェイスは、振る舞いだけを定義し、基本的に実装を記述しない要素。
C#などの強い型付けの言語では使われるが、Pythonなどではあまり使われない印象がある（Pythonのabcモジュールはあるが）
インターフェイスを使うと、具体的なクラスでなく振る舞いに対して記述することが強く意識付けられ、 具体的なクラスに依存しづらくなるため、疎結合なプログラムを作りやすいように思える。

依存性の注入(Dependency Injection)

「依存オブジェクトの注入」と理解した方が良さそう。 依存オブジェクトを内部で生成するとテストがしづらいが、コンストラクタなどから与えるとモックなどを使ったテストができるようになる。
注入が必要な依存オブジェクトが増えると面倒になるが、その場合にはDIフレームワークを用いる選択肢がある。

（参考）SOLID原則

※各原則は私の要約です。（書籍などに明確に定義が記述されていないものもあるため）

S - 単一責務の原則

「クラスを変更する理由はひとつのみであるべき」
クラスの責務はひとつのみであるべき。それはそう。

O - 開放・閉鎖の原則

「拡張に対して開いており、変更に対して閉じているべき」
要するに、モジュールの振る舞いを拡張できるとともに、拡張したときに既存のコードに変更が発生しないということ。
これを満たすには、モジュールの機能をどう拡張するかの拡張ポイントを考えることになる。

L - リスコフの置換原則

「SがTの派生型であるとすれば、T型のオブジェクトをS型のオブジェクトと置き換えたとしても、プログラムは動作しつづけるはず」
要するに、あるオブジェクトを派生型のオブジェクトに置き換えたとしても動作しつづけるはずということ。 これもそれはそう。

I - インターフェイス分離の原則

「クライアントが使用しないメソッドに依存するよう強制されるべきではない」
上記「インターフェイス」参照

D - 依存性反転の原則

「上位レベルのモジュールは下位レベルのモジュールに依存すべきではない。両方とも抽象に依存すべき」
「抽象は詳細に依存してはならない。詳細が抽象に依存すべき」
確かにそれはそう。実現するには、インターフェイスを使った上で依存関係を上手くほぐしていく必要がありそう。

C#からC++を呼び出してポインタを使う

C#からC++を呼び出す方法を調べていたのですが、ポインタつかってごにょごにょできることを知って驚きました。 安全に使うには当然いろいろと気をつけなくてはいけないのですが、C++ではここまでできるのかと。

ソースコード

lib.hの記述

class Value
{
public:
    int v;
};

typedef void *Handle;
extern "C" int CreateValue(Handle *out, int x);
extern "C" int AddValue(Handle handle, int x);
extern "C" int GetValue(Handle handle, int *out);

lib.cppの記述

#include "lib.h"

int CreateValue(Handle *out, int v) {
    *out = new Value{v};
    return 0;
}

int AddValue(Handle handle, int v) {
    auto p = static_cast<Value*>(handle);
    p->v += v;
    return 0;
}

int GetValue(Handle handle, int *out) {
    auto p = static_cast<Value*>(handle);
    *out = p->v;
    return 0;
}

main.csの記述

ポイントは以下のとおり：

  • DllImportでC++ライブラリとのインターフェースを定義する
  • IntPtr型でC++のポインタを扱う
using System;
using System.Runtime.InteropServices;

class Program
{
    static void Main(string[] args)
    {
        External.CreateValue(out var ptr, 10000);
        int v;
        External.GetValue(ptr, out v);
        Console.WriteLine(v);
        for (int i = 0; i < 5; i++)
        {
            External.AddValue(ptr, 100);
            External.GetValue(ptr, out v);
            Console.WriteLine(v);
        }
        // おそらくメモリリークしている
    }
}

static class External
{
    private const string Path = "../../../lib.so";

    [DllImport(Path)]
    public static extern int CreateValue(out IntPtr ptr, int v);

    [DllImport(Path)]
    public static extern int AddValue(IntPtr ptr, int v);

    [DllImport(Path)]
    public static extern int GetValue(IntPtr ptr, out int v);

}

参考文献

アンマネージ コードとの相互運用

docs.microsoft.com

xgboostのAPI

github.com

実際ちゃんと使うのであれば、xgboostが行っているようにさまざまな用心をする必要がありそうです。

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