Rust で競プロ

Rust で競プロする話について書こうと思います。ちなみにこの記事は競プロアドベントカレンダーの7日目の記事です。

Rust とは何だったか

Rustは速度、安全性、並行性の3つのゴールにフォーカスしたシステムプログラミング言語です。 (公式サイトより引用)

Mozilla が開発しているコンパイル型のプログラミング言語です。 ムーブセマンティクスや変数の寿命といった独特な機能によってメモリの安全性やデータ競合の安全性をコンパイラが保証している点や、プログラミングする上で便利な構文が用意されているのが特徴的です。 言語の機能としては例えば imos さんの記事とかが詳しいです。

開発の世界では最近注目が集まってきているような気がしますが競プロではまだまだ使われている場面が少ないので、布教も兼ねてどういう感じか紹介したいと思います。

競プロで C++ 使ってるけど、Rust 使う利点/欠点は何?

利点としては、後述するような優れた構文やツールチェーンのおかげでプログラミングが柔軟にできる点は大きいのではないでしょうか。標準ライブラリも結構充実しているため少なくとも C++ と同等のことは出来るのではないかと思います。実行速度に関しても C++ に引けを取らない速さを達成しており安心できます。

欠点としてはマイナー言語にありがちなことですが、競プロでは使ってる人がそこまで多くないので競プロ用の便利ライブラリや問題の正解コードなどを探すのは難しくなるでしょう。また、日々コンパイラがバージョンアップしていくせいで最新の機能を使いたくてもオンラインジャッジが対応していないせいで使えないといった状況は覚悟したほうが良いです。 残念ながら日本語の情報はそこまで多くなく詰まった時にググって出て来る情報は大抵が英語なので、技術英語を読めるレベルの語学力は必須になるでしょう。

というわけなので、初心者の人は普通に C++ 使ったほうが良いと思います。逆に C++ をある程度使いこなせるけど C++ に飽きてきたから他の言語試してみたいみたいな場合には、使ってみると楽しいかもしれません。

どういうオンラインジャッジ/コンテストサイトで使えるの?

ちょっと調べました。意外にも結構対応してるところが多いですね。ちなみに現時点(2017/12/9)での最新バージョンは1.22.1です。

  • AtCoder : 1.15.1
  • Codeforces : 1.21
  • Aizu Online Judge : (バージョン不明?)
  • Sphere Online Judge : 1.14.0
  • HackerRank : 1.21.0 + いくつかの外部ライブラリが付属

以下は未対応のようです。…頑張れ!

どういった環境で使うべき?

Rust はクロスプラットフォームな言語なので Windows でも MacOS でも Linux でも使えます。インストールは容易です。

エディタについては、IDE はできればあった方が良いと思います。Rust and IDEs · The Rust Forge を見ると Vim, Emacs, Sublime, IntelliJ Idea, VSCode などの主要なエディタにプラグインが揃っているので、普段使用しているエディタにプラグインを入れれば快適な環境が整いそうです。

どうやって勉強したら良いの?

公式チュートリアルRust Book を読むのが良いです。

特徴的な言語機能

色々ありますがここでは競プロで役立ちそうな Rust の言語機能を C++ と比較しつつ紹介したいと思います。

for 文

とても基本的ですが、単に n 回ループを回したい時に REP マクロのような怪しいものに頼らずに済みます。

let n = 10;
for i in 0..n {
    solve(i);
}
型推論

型推論が強力で、宣言時に型を指定していなくても途中で型が決まるようなコードをコンパイルできます。

以下のコードだと、1行目では Vec<T> (C++ でいう std::vector<T> 相当のもの。vec![] は要素が空の Vec<T> を宣言するためのマクロ) を宣言しており、1行目の段階では T が何か決まっていません。 2行目を見ると要素に i32 (32ビット整数) を追加しているので、ここで T=i32 が決定されます。

let mut v = vec![];
v.push(1i32);

少ないタイプ数で書けるので便利。

タプル

C++ の std::pair などに比べ、値の組(タプル)についてかなり自然に扱うことができます。

以下のコードでは、値の組を返す some_function という関数に対し、その返り値を別々の変数で受け取る方法を示しています。C++std::tie などを使うより自然に受け取れるのが見て取れます。

fn some_function() -> (i32, i32) {
    (123, 456)
}

fn main() {
    let (x, y) = some_function();
    println!("x={}, y={}", x, y);  // => "x=123, y=456"
}
構造体

構造体のコンストラクタは key: value の形で行います。タイプ数が若干増えますが意味はより明示的になります。以下は円を表す構造体の定義とそのインスタンスを作るコードです。

struct Circle {
    x: f64,
    y: f64,
    r: f64,
}

fn main() {
    let my_circle = Circle {
        x: 1.23,
        y: 4.56,
        r: 7.89,
    };
}

毎回 key: value の形で書くのは冗長ですが、もし value が変数で、その変数名が key と一致しているなら、"key: " 部分の記述を省略することができます。(ただしコンパイラのバージョンがある程度新しくないと使えない模様…。)

    let x = 1.23;
    let y = 4.56;
    let r = 7.89;
    let my_circle = Circle { x, y, z, };

便利機能として、構造体の宣言時に #[derive(Debug)] というアノテーションを付けておくと、println! などで変数のインスタンスを指定した時にそのインスタンスの内容をそのまま出力できるようになります。 この機能はデバッグ時にかなり便利です。

#[derive(Debug)]
struct Circle {
    x: f64,
    y: f64,
    r: f64,
}

fn main() {
    let my_circle = Circle {
        x: 1.23,
        y: 4.56,
        r: 7.89,
    };
    println!("{:?}", my_circle);  // => "Circle { x: 1.23, y: 4.56, r: 7.89 }"
}
配列のスライス

部分列への参照に簡単にアクセスできます。以下は v という可変長配列の1番目から2番目までの部分列への参照を取っています。

let v = vec![0, 100, 200, 300, 400];
let subseq = &v[1..3];
println!("{:?}", subseq);  // => "[100, 200]"
列挙型

C++ やその他の多くの言語の列挙型 (enum) は単に定数を並べて定義するものに過ぎませんが、それに比べて Rust の列挙型は強力なものになっています。列挙型の項はそれぞれ独自の値の組を持つことができます。

以下はよく使われる Option<T> 型です。何か値を指定したいときには Some(T) を持つ(T はその値の型)けど、何も指定したくないときには None にしておくといった使い方をします。

enum Option<T> {
    None,
    Some(T),
}

競プロの文脈で使うなら、例えばメモ化計算の際に、メモ配列に上記Option<T> 型を用いて、計算済みの要素は Some(T) を割り当て、まだ計算が済んでいない要素には None を割り当てると言った用途がありえそうです。

パターンマッチ

列挙型の項の値 (T) は if letmatch といった構文で取り出せます。以下は Option<T> 型を用いてフィボナッチ数をメモ化再帰で計算する例。

fn fib(i: usize, memo: &mut Vec<Option<i64>>) -> i64 {
    if i <= 1 {
        return 1;
    }
    if let Some(x) = memo[i] {  // もし memo[i] が Some(T) だったら、
                                // x に T を代入して if ステートメント内を実行する
        return x;
    }
    let retval = fib(i - 1, memo) + fib(i - 2, memo);
    memo[i] = Some(retval);
    retval
}
変数名の再利用

同じスコープ内であっても変数名の上書きができます。これにより、似たような機能の変数だけど名前が被っているせいで別の名前を付けないといけない、みたいなことがなくなります。

let mut data;  // 何かのデータを表す変数 data
data.push(100);
// ...
let data = convert(data); // data に変換をかけたものを data という名前にする
代入文での if

代入文で if が使えます。三項演算子と違って、if ステートメントの内部で処理を行えるのが特徴的です。 以下では変数 some_important_flag が真のときには1つ目の if ステートメントの返り値(12345)がxに代入され、そうでないときは2つ目のものが代入されます。

let x = if some_important_flag {
    12345
} else {
  let mut val = 0;
  for i in 0..10 { val += i; }
  val
}

使用頻度は多くないですがいざというときに便利かもしれない。

ツールチェーン

言語の機能だけでなく、どういうツールが使えるのかもプログラミング言語の重要な要素です。

外部ライブラリのインストール

ローカル実行のできるコンテスト(Google Code Jam, Facebook Hacker Cup 等)に限られますが、Cargo というインストール時に標準で入ってくるバイナリを使うと外部ライブラリを簡単にインストールできます。python 使っている人なら pip のようなものだと思うとわかりやすいです。

例えば多倍長整数ライブラリである num をインストールするには、Cargo.toml というプロジェクトファイルに以下のような文字列を1行追加して cargo build のようなコマンドを叩くだけで良いです。

num = "0.1.41"
コードのフォーマット

Rust にはコードを自動で整形するツールが標準で入っています。rustfmtcargo fmt がそれに相当します。例えば以下のようなコードがあったとして、

let x=3 as f64;
let y=4 as f64;
let r=(x*x+y*y).sqrt();
println!("{}",r);

整形すると以下のようになってくれます。

let x = 3 as f64;
let y = 4 as f64;
let r = (x * x + y * y).sqrt();
println!("{}", r);

こういった標準の整形ツールが存在することで、スペースの空け方や改行位置の調整といったような表面的なことにあまり拘らなくて済むようになるのはありがたいかもしれない。

入力処理

Rust には C++ と違って scanf や std::cin のような手軽に競プロっぽいフォーマットの入力を標準入力で受け取る関数が無いため、ある程度自分でスキャナー相当のものを書いておいたほうが便利になります。

ここでは自分が使っているものを紹介します。read を呼び出すとトークンを文字列から所望の型に変換して返して暮れます。トークンの前後に余分なスペースや改行などがあっても使えます。

use std::io::{stdin, Read, StdinLock};
use std::str::FromStr;

struct Scanner<'a> {
    cin: StdinLock<'a>,
}
 
impl<'a> Scanner<'a> {
    fn new(cin: StdinLock<'a>) -> Scanner<'a> {
        Scanner { cin: cin }
    }
 
    fn read1<T: FromStr>(&mut self) -> Option<T> {
        let token = self.cin.by_ref().bytes().map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        token.parse::<T>().ok()
    }
 
    fn read<T: FromStr>(&mut self) -> T {
        self.read1().unwrap()
    }
}

以下のような感じで使えます。

fn main(){
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);  // スキャナの定義

    let n: i32 = sc.read();  // 普通にトークンを1つ読みたいとき
    while let Some(n) = sc.read1() {  // こっちはICPC形式などでEOFで入力が終わるとき用
        // ...
    }
}

もしかすると他にももっと効率の良い実装方法があるかもしれません。

標準ライブラリ

入力が取れれば後はなんでもできます。C++の標準関数やSTLで代表的なものと Rust の標準ライブラリとの対応を貼っておきます。

ライブラリ C++ Rust
入出力関数 cstdio std::io
数学関数 cmath std::f64 など
可変長配列 std::vector Vec
キュー std::queue VecDeque
優先度付きキュー std::priority_queue BinaryHeap
文字列 std::string String から Vec<char> などに変換して扱うのが無難そう
連想配列 std::map std::collections::BTreeMap
集合 std::set std::collections::BTreeSet
ペア、タプル std::pair, std::tuple タプル
アルゴリズム std::algorithm 色んな所に散らばっている(next_permutation, lower_bound など一部関数は未実装)
関数オブジェクト std::functional クロージャ
ビットセット std::bitset BitSet, BitVec (ただし Unstable)
乱数 rand, std::random 標準では未実装、外部ライブラリの rand が有名
複素数 std::complex 標準では未実装、外部ライブラリの num が有名

このように、主要なものはだいたい標準ライブラリでカバーしているものの、一部は未実装だったり外部ライブラリが必要だったりするのは注意が必要かもしれません。

その他

let mut とか毎回書くのは面倒そう

競プロでもコードを書いてると変数が実は定数でいい(let だけでよい)ことは結構あるので、毎回 let mut と書かないといけないわけではないです。

コンパイラが厳格で大変そう

所有権まわりの制約は結構厳しそうに見えますが、理不尽なコンパイルエラーに遭遇することはそこまで多くない印象です。 もちろん、コードを書いてて何度か意味を理解するのが難しいコンパイルエラーに遭遇したことはあります。ただ、ちょっとややこしい状況でややこしいコンパイルエラーが出るのは C++ でも同じなので、Rust だけ理不尽かというとあまりそんなことはない気がします。

とはいえもちろん Rust もまだまだ開発中の言語なので、かなりトリッキーな例は存在するようです。例えば Rust Book の最後の章ではそういった例が紹介されています。注意をするに越したことはありません。

Rust で書かれた競プロのライブラリとかって無いの?

ちょっと調べた感じだと EbTech 氏のライブラリはとてもまとまっている印象を受けました。 ただ、これもまだまだ実装は部分的で、例えば Spaghetti source ほどの充実性は無いように見えます。

逆に言えば、今なら Rust で充実したライブラリ集を出せば大いに注目を浴びる可能性はあります。

まとめ

Rust で競プロする話について書きました。面白い言語だと思うので競プロでも普及すると良いですね。

京都旅行

ちょうど木曜が祝日で良い感じだったので、金曜と月曜を有給にして5連休を取ったので京都旅行をエンジョイした。以下はローカルな話が多い日記。

1日目

  • 朝は比較的だらだらしていたので、昼過ぎに東京を出発する。駅でいくら丼を買ったので移動中に新幹線で食べる。美味しい。
  • 京都に着くともう日が暮れていたので宿に荷物を置いて、北白川の四川料理屋である駱駝に行く。辛くて美味しい。
  • この日は特に何もせず終了。

2日目

  • 昼頃に起きたので鴨川沿いのオシャレっぽいカフェで朝飯を食べる。昨日はあまりちゃんと見れなかったが、この時期は葉っぱが赤色、黄色、緑色などのグラデーションになっていて、綺麗。
  • 京大がちょうど学園祭中だったので、中を通り過ぎて雰囲気だけ味わう。途中で生協に寄ってなんとなく教科書とかを眺める。昔読んでた本の改訂版などが置いてあったりして懐かしい。
  • 京都動物園に行く。モルモットの群れが一心不乱に餌を食べている様子が可愛かったので結構長時間眺める。
  • 知り合いの家に行って協力ゲームの Overcooked を遊ぶ。どうすれば効率をよく出来るかを話し合いながら進めるのが面白いけど、微妙に仕事っぽさがあって疲れるような気もする。

3日目

  • 昼頃に起きる。目当てのレストランが開いてなかったので仕方ないので近くにあったハイライトに入る。なぜか突然チャレンジ精神が芽生え、カラフルジャンボチキンカツを頼む。しかしもう僕はハイライト適正の年齢では無いので、食事を楽しめたとは言い難かった。
  • 銀閣寺付近の通りを経て大文字山を登った。観光シーズンだったので人が多い。大文字山は結構気軽に登れる割に達成感もあるので良い。この日を含めて2回しか登ったことないけど。
  • 夕方以降はサークルのOB/OG会があったので宴会に行った。

4日目

  • 昼頃に起きる。百万遍モダン焼きフジに行く。
  • 宇治に向かう。特に下調べなしで行ったので何があるのかよく知らなかったのだが、街は観光地としてかなり賑わっていた。神社、喫茶店、土産屋、平等院鳳凰堂あたりを周る。全体的に抹茶推しが強くて、抹茶たこ焼きなんてのもあった。

5日目

  • 10時チェックアウトなので早起きした。下鴨神社をうろうろした後でカナート洛北に行った。
  • カナート洛北付近は数年前あたりからパチンコ店の建設を進めようとする業者とそれに猛反対する近隣住民達の闘いが繰り広げられていたようなのだが、最近になって住民側の勝利で終わったらしく、建設予定地だった広大な土地が高いフェンスで囲われただけの何もない場所となっていた。
  • 荷物が重かったためあまり遠出する気にはならなかったのでその後は百万遍付近の松ノ助で昼飯を食べて新幹線に乗って帰宅した。

最高落下速度環境で動くテトリスのゲームAIを作った

「最高落下速度(20G)」かつ「クラシック方式の回転法則」という高難易度環境のテトリスで良い感じに動くゲームAIを作りました。以下はそのデモです。

ソースコードgithubで公開しています:https://github.com/ir5/tetris20g-ai

ゲームのルール

テトリスは知っている方が多いと思いますが改めて説明すると、10x20くらいのフィールドで次々に空から降ってくるピースを操作して地面に固定させ、横一列にブロックが揃ったら消える、というのを繰り返すゲームです。

”普通の設定”で動くテトリスのゲームAIは世の中にたくさんあるようですが、今回はよりタフな設定でゲームAIを作りたいと思ったので以下のような高難易度要素を取り入れました。

落下速度:20G

普通のテトリスではピースは1マスずつ落下していきますが、これを加速させて最高のスピードにするとフィールドの上部に現れたピースが即座に地面に接地した状態で現れることになります。このような環境を20Gと呼びます。1フレームの間にブロックが20段落ちることからこのような名前が付いています。
即座に地面に接地すると全く動けなくてゲームにならないような気がしますが、実際には接地してから固定されるまでには時間があり、地面の上を転がるように動かすことでピースを所望の位置に運ぶことが出来ます。
20G下ではピースの可動範囲に大幅な制約が加わることになります。例えば以下のような盤面では水色ピースは真ん中に落下した後そこに埋もれてしまい、左右の端に移動することができません。

f:id:ir5:20171105123645p:plain

このような状況に陥らないためには、常に中央を高くした状態でブロックを積んでいくことが重要になります。また、そのため中央付近には穴を作ってしまわないことも重要です。

回転法則:ARS

20Gのような高速設定では回転法則が重要になってきます。回転法則とはピースをどのように回転させるかを記述したルールのことです。
2002年以降のテトリスはすべてワールドルールと呼ばれるガイドラインに沿ったものになっており、Tスピンなどを代表するようにかなり柔軟性の高い回転が可能になっています。
しかし今回はワールドルールが制定されるより以前のARSと呼ばれる柔軟性の低い回転法則を用います。ARSは「結構工夫しないと思い通りに回転できない厳しいルール」だと思って下さい。
また、当時の情勢に合わせてネクストブロックは1つしか見れないものとします。

ツモ順:完全ランダム

テトリスには7種類のピースがあり、どれがどの順番で来るかはランダムに設定されていますが、通常は種類がなるべく偏らないような工夫がされています。
しかし今回ゲームAIを作るにあたって問題設定をシンプルにしたかった*1ため、敢えて毎ターン完全にランダムなピースの種類が来るように設定しました。
このため「長棒を待っているのに全然来ない」「S字のピースが4回連続で来た」といったようなことが平気で起きます。

これらの要素により、普通よりもタフな環境になっています。

手法

今回ゲームAIを作るために試した手法は一言で言うと「2マス関係による線形関数で評価関数を表現し、手でアノテーションしたデータを使ってランク学習で評価関数を最適化し、テスト時には2手まで探索して評価値が最も高いものを選ぶようにした」となります。
それぞれの要素について説明していきます。

評価関数

評価関数とはゲームの盤面に対してそれがどれくらい”良い”ものかを表す値を返す関数のことです。テトリスのようなゲームでは精度の高い評価関数があれば探索系の手法と組み合わせることで良い手を選ぶことができます。
落下速度が低速の場合は単純な評価関数だけで十分上手くいくようです。例えばこのブログ記事によると、4つの手製の特徴量について重み付き和を取るだけでほぼ完璧なゲームAIが出来上がったそうです。
しかし今回の設定では地形の判断をそれなりに精密に行う必要がありそうだったので、このような単純な特徴量だけではうまくいかないだろうと判断しました。評価関数で地形の情報を詳細に盛り込むために、今回は以下のような異なる2マスの関係に着目するような評価関数を使うことにしました。

\[
v(f) := \sum_{i,j} w_{ij}\cdot\mathbf{1}[f_i=1, f_j=0]
\]

ここで、$v$ は評価関数、$f$ はフィールド、総和の $i,j$ はフィールドの各マスを表す変数、$w_{ij}$ は評価関数の重みパラメータ、$\mathbf{1}[f_i=1, f_j=0]$ はマス $i$ にブロックがありかつマス $j$ にはブロックがないようなときに1になりそうでないなら0になる関数とします。
この評価関数により、パラメータ $(w_{ij})_{i,j}$ は 200^2=40000 個生まれることになりますが、この中には明らかにどうでもいいものも含まれています。例えばフィールドの右上と左下の関係などどうでもいいに決まっています。よって実際には $i,j$ ペアとしては位置が近いものだけを考えることにすることで、パラメータを8184個に絞っています。

評価関数をこのような形にしようと思ったのは、将棋でn駒関係のような特徴量が結構良い感じに効いているというのをどこかで聞いたことがあったり、ぷよぷよのAIでも2駒関係が使われていたりしたので参考にできそうと思ったためです。

学習

評価関数の形を決めたので、次にそのパラメータ $(w_{ij})_{i,j}$ をどうやって探すのかについて考えます。
今回はランク学習という方法を用いて人間(=僕)のアノテーションデータを使ってパラメータを最適化することにします。
ランク学習とは一般には対象物の順位付けを求めるために用いられる手法ですが、今回のような評価関数を求める目的にも使えます。
いま、人間のアノテーションログがあって、その中にフィールド $f$ から1手打って $f'$ に移ったログがあったとします。これは次のようにも解釈できるはずです:$f$ から次に取りうるフィールドとして $f'$ 以外にも $f'_1,...,f'_n$ があったとき、各 $i$ について $v(f') > v(f'_i)$ が成り立っている。
そこで、各 $(f', f'_i)$ について、$(v(f') - v(f'_i))$ がマイナスならそれに応じたペナルティをかけて、プラスならそんなにペナルティをつけないような損失関数を取るようにして、それで全体を最適化すればうまくいきそうな気がします。
ランク学習ではこのような損失関数として $L(x) := \log(1+\exp(-x))$ のような形の関数が用いられます*2。これは以下のような形状の関数です。

f:id:ir5:20171105153204p:plain

この損失関数で、全ての $(f', f'_i)$ ペアの平均値を取ったものを最小化するようにパラメータ $(w_{ij})_{i,j}$ を最適化することにします。式で書くと以下のような雰囲気です。($N$ は総データ件数)

\[
\frac{1}{N} \sum_f \sum_i L(v(f') - v(f'_i)) \rightarrow minimize
\]

これは非線形最適化問題なので、確率的勾配法(SGD)を使って最適化することができます。

なお、上の説明では1手打った後のフィールド同士を比較するとしましたが、テトリスではネクストを見て打つ手を変えるということをよく行うため、実際には2手打ったフィールド同士を比較しています。

探索

評価関数ができたので、それを使って実際に打つ手をどう選ぶかについて考えます。
今回のテトリスではネクストブロックが1つだけ見えているので、今操作しているピースと次のピースの種類とで2手先まで可能な手を列挙することができます。
単に2手先まで見て評価値が一番高かったものを選ぶことにします。

実験と結果

実装はほぼすべて rust を使って行いました。評価関数パラメータの学習部分のみ非線形最適化で若干面倒そうだったので python (+Chainer) を用いています。

学習には約7000手分のアノテーションデータを使い、そのうちの10%を検定に用いました。
これだけの学習データでも2手先読みをすると平均で200~300個くらい異なる候補がありうるので、学習用のデータをナイーブに作ると 8184bits*6000*300*2≒3.6GBくらいになって量が膨大になるので、データのうち80%はランダムに間引きました。
学習には Chainer の MomentumSGD を使いました。学習率は 1e-2 (デフォルトと同じ) です。

性能の評価のために、ゲームオーバーになるまで実行して何手まで生き残れたのかについて見ました。30回試行したところ、結果は以下のようになりました。

  • 平均: 7240.7
  • 標準偏差: 6103.3
  • 最小: 977
  • 最大: 26295

ツモを完全ランダムにしたせいで運要素が強いゲームになっているのですが、比較的頑張ってるような気がします。たまに4ライン消しも狙いに行きます。

計算速度に関しては、1秒間に52手ほどの手を選ぶことができました*3

試したけど上手くいかなかったこと

  • 最適化には最初 MomentumSGD ではなく(特に理由なく) Adam を使用していたのですが、最初の数 epoch 以降 validation loss がどんどん上がっていくという現象が発生しました。正則化として weight decay を入れてみたりしたものの効果無し。何が原因なのかいまいちよく分からずじまいです。
  • 80%も間引くなら比較候補はランダムよりも判断に悩む手の方が学習に良いのでは?と思い、評価関数が得られた後で、評価値の上位20%の $f'_i$ だけを学習データに入れて再学習させるということをしたのですが、結果はそんなに良くなりませんでした(というか若干悪化しました。) 人が打った手にも悪手が混じっているので、あまり特化させすぎるのも良くない?よく分かりませんが。

まとめ

テトリスのAIを実装した話をしました。今回試した手法は比較的素朴なものであり、以下のような改善点があると思います。

  • アルゴリズムを動かしているとある決まったパターンの”愚形”が現れることがある。これは今の評価関数が捉えきれていないパターンがあるということなので、これを補えるようなパターンを特徴量に追加してやることで、性能が向上する可能性がある。
  • 人間のデータを使っている限り、人間の性能は越えられないかもしれないので、何らかの自己学習の仕組みを導入する。特に、今は人間の手を真似ているだけで「4ライン消し」のような得点を狙う仕組みが何も入っていない。

とはいえど、これでもまぁまぁ動いていて割と満足してしまったような気もします。

*1:しかし結果的にはあんまりシンプルになってなくて単にゲームが難しくなっただけという感じも。

*2:本当は若干違いますが重要ではないので割愛します。

*3:記事のトップに貼ったgif画像は可視化のために大幅にスローダウンしています。

AlphaGo と AlphaGo Zero の自己対戦による学習部分の違い

流し読みだとちゃんと分からなかったのでメモ。

準備(AlphaGo)

  • policy network : 盤面とその特徴量を入力として受け取り、各マスに打つ確率を返すニューラルネット
  • value network: 盤面とその特徴量を入力として受け取り、その盤面での勝率を返すニューラルネット

AlphaGo ではまず policy network をプロの棋譜データから教師あり学習で事前学習させ、その後自己対戦による強化学習によってさらに改善させていく。

AlphaGo の強化学習パート

  • 教師あり学習後の policy network のパラメータ $\rho_0$ から学習をスタートする。自己対戦の結果から policy network のパラメータは随時更新されていく。それらを $\rho_1, \rho_2, \cdots$ とする。$t$ 回目の自己対戦では、現在のパラメータ $\rho_t$ と、それより以前のパラメータ $\rho_{t'}$ と対戦が行われる。
    • 実際には、毎試合ごとにパラメータを保存していたら量が膨大になって大変なので、パラメータの保存は一定反復ごとに行われる。
  • パラメータの更新は REINFORCE アルゴリズムによって行われる。パラメータの更新幅 $\Delta\rho$ は以下の式で表される。ここで、$\alpha$ は学習率、$T$ は自己対戦が終了するまでにかかったステップ数、$a^i$ と $s^i$ はそれぞれ自分が $i$ ステップ目に取った行動値と状態、$p_\rho(\cdot \mid \cdot)$ は $\rho$ をパラメータとする policy network の出力値、$z$ はその対局で自分が勝利したなら $+1$、敗北したなら $-1$ となるような報酬値、$b^i$ は分散を小さくするために用いられるベースラインと呼ばれる値。

\[
\Delta\rho = \alpha \sum_{i=1}^{T} \frac{\partial\log{p_\rho(a^i \mid s^i)}}{\partial\rho}(z - b^i)
\]

  • 自己対戦中に打つ手は、policy network での確率をからそのままサンプリングしている:$a^i \sim p_\rho(\cdot \mid s^i)$. つまり、自己対戦中には探索を行っていない。
  • REINFORCE により policy network が学習できた後は、自己対戦の棋譜データを元に value network を教師あり学習の要領で学習させる。
  • テスト時には、MCTS による探索中の評価関数としてこれらの policy network と value network を用いる。

Zero の学習方法

次に Zero について。自己対戦部分に関連する違いとして、AlphaGo では policy network と value network は別々のものだったが、Zero ではこれらが1つのネットワークに統一され、ニューラルネットの構成に変更が加えられている。したがって、AlphaGo では policy network と value network の訓練は別々の段階で行われたのに対して、Zero では同一の訓練ループ内で最適化される。

Zero でも自己対戦を行うが、以下のような点が AlphaGo と異なっている。

  • 自己対戦中にも MCTS による探索を行う。これにより、MCTS による各マスに打つ確率値のベクトル $\pi$ が得られる。
  • パラメータを更新する際の更新式が変わっている。ニューラルネットの出力値を $(p, v)$ とする。以下の要素をロス関数としてパラメータを最適化する。

考察

ちょっと自信が無いけど次のような理解で合っているだろうか?

  • AlphaGo では自己対戦中に打つ手はサンプリングによるものだったため更新時の分散が大きそうだったが、Zero では探索結果を直接教師データみたいにして $p$ を学習しているため分散が小さそう。これにより、安定したパラメータの更新をするのに必要なサンプル数が少なくて済みそう。
  • $v$ の学習についても、サンプリングよりも探索結果の方が判断としての質が高いので、初期の段階から確度の高い情報を教師データに用いられるというメリットがありそう。
  • AlphaGo では policy network の学習部分と探索アルゴリズム部分は分離していた(研究の流れ的にも、根本となるアルゴリズムMCTS がありその評価関数としてできるだけ質の良いものを作りたいというモチベだったように思う)が、Zero になって学習の過程に探索アルゴリズムが直接入るようになった。これにより、よりテスト時に一貫性のある方策を取れるようになってそう。

余談

「Zero は4つの TPU だけを使って学習された」と言われているのを見かけるがこれはテスト時の話であり、学習時には 64 個の GPU と 19 個の CPU パラメータサーバーが使用されたと書かれている。"""Each neural network fθi is optimized on the Google Cloud using TensorFlow, with 64 GPU workers and 19 CPU parameter servers."""

日記

Rust でなんか書く

せっかく Rust がちょっと書けるようになってきたので何か書こうと思い、テトリスの AI を作ってみることにしました。2週間くらいちまちまコード書いてシステムの土台だけ作りました。以下は動作確認のためにCUIで表示&手動操作してるもの。

ゲーム AI を作るにあたってどういうアルゴリズムにするかは大体決めているのであとは2週間くらいで第一弾みたいなものを作りたいところ。上手く動くかは分からないけども。

これを書くにあたって色々外部ライブラリ(具体的にはcurses、乱数、シリアライズ、時刻、argparse等)を利用していますが、cargo のおかげでこういうのが気楽に使えるのはありがたい。 Rust は配列とか Vec のインデックスアクセスに usize 以外実装する気がなさそうなのが個人的に意味不明なのですがそれ以外は結構使いやすくて良いと思います。

写像の組 f,g:Z→Z で f,g,(f+g) が3つとも全単射になるようなものはあるか?

タイトルまんまですが、ちょっとおもしろかったので。

本筋とは必ずしも関係ない考察

もし $f,g,(f+g)$ が全部 $\mathbb{Z} \rightarrow \mathbb{Z}$ の全単射だとすると、任意の全単射 $\pi$ について \[ \begin{align} \pi(x) &= (f+g)\circ(f+g)^{-1}\circ\pi(x) \\ &= f\circ(f+g)^{-1}\circ\pi(x) + g\circ(f+g)^{-1}\circ\pi(x) \\ &= F(x) + G(x) \end{align} \] となる。ここで $F := f\circ(f+g)^{-1}\circ\pi$、$G := g\circ(f+g)^{-1}\circ\pi$ とした。$F,G$ は全単射なので、任意の全単射は2つの全単射の和で書けることになる。

これより、例えば $(f+g)(x) = x$ となるようなものについてだけ考えれば良いことが分かる。

構成

実はタイトルの条件をみたすような $f,g$ は作ることが出来る。 便宜上、整数は $0<1<-1<2<-2<3<-3<...$ みたいな順序付けがされているものとする(0が最小)。 $f(x),g(x)$ の値が記されたテーブルを考える。最初、テーブルには何も書かれていない。このテーブルでは $f(x)+g(x)=x$ が全 $x\in\mathbb{Z}$ について成立ち、かつ $f(x)$ と $g(x)$ が全単射になっていなければならない。そうなるようにテーブルに値を埋めていくことを考える。(↓イメージ図)

x f(x) g(x)
0 ? ?
1 ? ?
-1 ? ?
2 ? ?
... ... ...

(↑これの ? のところを埋めたい)

以下のようにすればこのテーブルを条件を満たすように埋めつくせる。

  1. $y<y'$ で、$y'=f(x')$ となるような $x'$ は存在するが $y=f(x)$ となるような $y$ が存在しない時、十分大きい $x$ を取ってきて $f(x):=y, g(x):=x-y$ とできる。このような $(y,y')$ ペアが存在しなくなるまでこれを行う。
  2. $g$ についても同様のことを行う。
  3. $x<x'$ で、$f(x')$ の値は決まっているが $f(x)$ の値は決まっていないような時、十分大きい $y$ を取ってきて $f(x):=y,g(x):=x-y$ とできる。このような $(x, x')$ が存在しなくなるまでこれを行う。
  4. $g$ についても同様のことを行う。
  5. 1-4 を繰り返す。もし1-4を一通り行ってもテーブルに値を埋められなかった場合、ある $x$ が存在して、$f,g$ は $\{0,1,-1,...,x\}$ 上での全単射になっている。その場合は、順序上での $x$ の次の数を $x'$ として、$f(x')$ と $g(x')$ の値を適当に決めると良い。

手順 1,2 によって $f,g$ が全射であること、また手順 3,4 によって $\mathbb{Z}$ 上の全ての範囲で写像の値が定義され、かつ埋める方法によって $f,g$ は単射でかつ $(f+g)(x)=x$ が満たされることがわかります。

感想

どうせ存在しないんだろうなぁと思ってたら存在してびっくりした。

日記

Rust Book (Second Edition) 続き

Rust Book Second Edition を読み終えたので、練習がてら AtCoder で数問解いて遊んでいました。

  • 10章(Generic Types, Traits, and Lifetimes): 内容はタイトルの通り。ジェネリクスとトレイトは C++ とか Java を知ってれば難なく理解できる。ライフタイムは Rust 独自の機能という感じで理解するのが難しい。というか実はまだあまりちゃんと理解できていないような気もする。
  • 11章(Testing): テストは #[test] とか assert! とかを使ってそれっぽく書く。rust標準のツールチェーンである cargo にテスト用の機能が予め備わってるのは良い。単体テストは書くソースファイルに書いて tests ディレクトリ以下には結合テストしか置いてはダメというのがしっくり来なかった。自分が python のスタイルに慣れているせいかもしれないが。
  • 12章(An I/O Project: Building a Command Line Program): 簡単な grep もどきを作ろうというシンプルなプロジェクトで、コードを具体的に書いていって、それをどのようにリファクタリングして整理するとよいかといったことが書かれている。とてもわかり易くて良い。
  • 13章(Functional Language Features in Rust): クロージャーとかの説明。最初の節のコード例はあまり良くない気がする(関数をクロージャーに置き換えてるけど、それだけだと何がしたいのか謎)。
  • 14章(More about Cargo and Crates.io): Cargo について。あまり大したことは書いていない。プロジェクト内でも cargo new でサブプロジェクトみたいなものを作れるので、大規模なプロジェクトになってくると便利そう。
  • 15章(Smart Pointers): 難しくてあまりちゃんと理解できていない。Box と Rc をどう使い分けるかあまり良くわかってない。あと RefCell が出てきたあたりで頭が動かなくなった。
  • 16章(Fearless Concurrency): スレッドを立てる話。スレッドと通信方法にはチャンネルを介してメッセージを送る方法と mutex を使う方法の2つがある。
  • 17章(Is Rust an Object-Oriented Programming Language?): オブジェクト指向らしい機能についての話。State パターンはあまりちゃんと知らなかったので勉強になったけど、やろうとしていること(要件自体は小さい)に対して重実装すぎないかと思わなくもなかった。trait はただのインターフェースの要件を書いたものに過ぎないのかと思いきや、trait object なるものを作れたり、trait のメソッドにデフォルトの実装を記述できたりして、思ったより色々できる。C++ でいう基底クラスと大差ない感じ?。あと、最後のほうで Post::new() を呼び出したときに Post 型ではなく別の型の変数を返すような実装方法が書かれていて、色々紛らわしくなるだけで微妙じゃないかと思ったのだけど rust だとそういうのも推薦されているのだろうか…?
  • 18章(Patterns Match the Structure of Values): パターンマッチはとても便利。while let を使ってキューが空になるまで pop し続ける処理が綺麗に書く例が面白かった。
  • 19章(Advanced Features): 細かい話が多そうだったのであまりちゃんと読んでない。
  • 20章(Final Project: Building a Multithreaded Web Server): マルチスレッドの簡単な http サーバーを作ろうというプロジェクト。例題として面白い。最後の方で rust がまだ開発途上にあることを示唆する内容があったのは正直で良いとは思ったけど、直し方が特殊すぎて意味不明なのでなんとかして欲しい。

次に実際にコードを書きたくなったので練習がてら AtCoder の問題を何問解きました。解くものはどれでも良かったので適当に ARC 069 を選びました。以下はそのときのコード。 競プロでは標準入力を受け付ける必要があるのでスキャナーに相当するクラスを tubo28 さんの qiita の記事を参考にしつつでっち上げています。

最後の問題だけは強連結成分分解などをする必要があって実装がちょっと面倒でした。以下は感想です。競プロ程度の用途ならあまり困ることもなさそうな印象です。

  • 型推論がかなり強力なので、let で変数を宣言する時に型を省略して書けることがかなり多くて便利。デフォルトで変数が const なのも良い。
  • 変数のシャドーイングやパターンマッチのおかげでコードを簡潔に書ける。
  • コンパイルエラーに遭遇して原因がよく分からなくてもコンパイラのヒントに従ったり、適当に色々試してると意外と直せる。
  • 書いてて楽しい。
  • やはり開発中の言語なこともあって新機能はガンガン入るので、例えば BTreeSet の range (C++ でいう std::set の lower_bound みたいなもの) は半年前とかなり最近なので、オンラインジャッジでは使えないことがある。

競プロは満足したので次は中規模くらいのコードを書いてなんか遊んでみたいところ。

「情報幾何学の基礎」の輪読

2.3節まで読みました。多様体における接ベクトルの定義が巧妙で面白いしそれがちゃんとベクトル空間を成しているのもよくできているなぁと思った。

その他

  • 和文論文の JAIST Repository: 落下型パズルゲームの定石形配置法とぷよぷよへの適用 を読んだ。ぷよぷよみたいなゲームでは大連鎖を起こすために長期的な計画を立てる必要があって難しそうなのだが、どういう手法が取られているのかふと気になったので調べているとこの論文に当たった。手法としては単純で、(i). 8連鎖程度のパターンのデータベースを手で20種類くらい作っておいて、(ii). 盤面の評価関数を、2駒間の一致関係がデータベースのそれとどれくらい合うかを元にして作り、(iii) 実際に手を選ぶ時には3手くらいまで先読みして、ヒューリスティックで枝刈りしつつ評価値が高くなるものを選ぶ といったことを行う。実験によると、この手法で8連鎖程度ができる火種を構成した後に既存の探索手法に切り替えてさらに火種が大きくなるような工夫を入れたところ、平均で11連鎖程度できるアルゴリズムが出来上がったとのこと。
  • この手法をモンテカルロ探索系の手法を用いるものに拡張する試みもあったようだが、計算時間が膨らみすぎて満足のいくものにはならなかった模様。

日記

最近twitterのアカウントを消してしまって*1 アウトプットする場所が無くなったので、代わりに日記を書いていくことにします。できれば毎週~隔週くらいのペースで。

Rust Book (Second Edition) 読んでる

Introduction - The Rust Programming Language

Rust は身の周りやウェブ上で使っている人をちらほら見かけて気になっていたので、新しい言語で取り入れられている考え方をほんのちょっとだけでも理解できたらいいなぁと思い勉強し始めました。 実は Rust は半年くらい前に勉強しようと思いチュートリアル(Rust book)を読んでいたものの途中でよくわからなくなって挫折した経緯があるのですが、その後チュートリアルが全体的に刷新されていたようで、新しい気持ちで読み進めることができました。 全20章構成。

  • 1章(Introduction): セットアップとかそういうの。VSCodeプラグインの保管が神という話も聞きますが、前に試したときにうまく設定できなくてよく分からなくなったので vim に Rust.vim だけ入れて書くことにしてます。最初は多分何でもいいんだと思います。
  • 2章(Guessing Game Tutorial): 数当てゲームによるチュートリアル。cargo の使い方とか、パターンマッチ構文が他の言語に比べて独特な感じがするけどそれ以外は特に難なく読める。
  • 3章(Common Programming Concepts): mutabiilty, データ型、関数、制御フローについて。割と普通。
  • 4章(Understanding Ownership): Rust の大きな特徴である変数の所有権に関する話。メモリ上でデータがどのように格納されているのかについて詳細に述べられており、第一版に比べると格段に説明が詳細になっている印象を受けました。所有権に関するルールを羅列していただけという印象が強かった第一版に比べて、こちらは「なぜそのような制約を設けているのか」について見通しが良くなっているように感じます。
  • 5章(Using Structs to Structure Related Data): 構造体について。メンバ変数の定義とメソッドの定義を別のブロックで書くことになっているのが特徴的?内容自体は割と普通。
  • 6章(Enums and Pattern Matching): 列挙型(enum)について。列挙型がリッチなのも Rust の特徴の1つと言えそう。
  • 7章(Using Modules to Reuse and Organize Code): ファイル分割によるモジュール管理について。「サブモジュールを持つモジュールは、ディレクトリを新規に作ってそこで管理しなければいけない」という仕様を見て少しびっくりしたのだけどなんでそんなことにしてるのだろう?利点がいまいち見えないと思った。
  • 8章(Common Collections): C++だとコンテナとか呼ばれてる類のモジュールについて。String の項目は「UTF-8は大変」みたいなことばっかり書いていて具体的にどう使えばいいのかよく見えてこなくて不満でした。そもそもモジュールとしても使い勝手があまり良くなさそうで、例えば String の部分文字列を取る方法についてググるこういう Stackoverflow の回答が出てくるのですが、普通に面倒で分かりづらい。基本的に String は immutable で使うことが前提っぽいので、それぞれの文字に頻繁にアクセスするようなコードを書く(例えば Suffix Arrayアルゴリズムを書くといったような)用途では別のデータ構造に変換してから使った方がという意図は見えるのですが、チュートリアルでは明示的にはそう書いてないし、そもそも何に変換すると一番良いのかもよく分からない。
  • 9章(Error Handling): エラー処理。Rust では例外ではなく、戻り値を使ってエラー処理する。適当にコードを書きなぐりたい時には panic! を用いて、ちゃんとしたものを作りたいときは Result をちゃんと処理すると良い。Result をパターンマッチで毎回律儀にチェックするのは面倒極まりないけど、"?" 記号などを使えば楽に記述することができる。

第二版は第一版に比べると、構成の見通しが良くなっていたり章末に軽い練習問題が乗っていたりしてチュートリアルの質は上がっていたような気はします。 気になる点も多少ありましたが、まだドラフトということなので完成版に期待したいです。 チュートリアルのあと半分も1~2週間くらいあれば読めそうなので、読み終わったら何か小~中規模のものを作って感触を掴んでみたいところ。


そういえば、コードを書いて色々試していると自動デリファレンス周りで少しハマったことが。

fn main() {
    let mut x = 1;
    {
        let xref = &mut x;
        f(xref, 1);
    }
}

fn f(x: &mut i32, y: i32) {
}

このコードは mainf に渡している引数(xref)がインターフェースとマッチしていないが、自動デリファレンスが働くので正常にビルドできる。しかし、f(...); を代入演算子に替えた以下のコードだと、

fn main() {
    let mut x = 1;
    {
        let xref = &mut x;
        xref += 1;
    }
}

エラーで落ちてしまう。

error[E0368]: binary assignment operation `+=` cannot be applied to type `&mut {integer}`
 --> src\main.rs:5:9
  |
5 |         xref += 1;
  |         ^ cannot use `+=` on type `&mut {integer}`

error: aborting due to previous error

何のことかよく分からなかったので周りの詳しい人に聞いたところ、自動デリファレンスはメソッド呼び出しで使えることは第一版に書いているがそれ以外については何も言っていないこと、またかなり最近の pull request で演算子でも自動デリファレンスできるようにする提案がされていたものの色々理由があって却下されていたことがわかりました。 うーん、何だかなぁ…。

「情報幾何の基礎」読んでる

情報幾何というストイックそうな分野の輪読会に特に理由無くなんとなく参加してたらいつの間にか発表担当になっていたので、色々予習してました。 使用している教本は数理情報科学シリーズの「情報幾何学の基礎」です。

とりあえず復習/予習した内容:

  • 学部1年レベルの解析学の内容 (だいぶ忘れていたので10年前のノートを引っ張ってきて復習した)
  • 双対ベクトル空間、テンソル
  • 微分幾何の入門っぽい話(ゆるふわ)

まだ準備ばかりで情報要素が皆無ですが、今後話がどういう風に盛り上がるのか(そもそも、盛り上がるのか)に期待です。

*1:最近の凍結騒ぎを見てかなり萎えたのと、最近はそもそもほとんど使ってなかったので他の場所を探すことにしました。