ぷよぷよのプレイ動画を解析して棋譜を生成する

この記事は KMC アドベントカレンダー の 3 日目の記事です。 昨日は PrimeNumber さんの PEZY-SC/SC2を使った話 でした。

背景と問題

ぷよぷよの上達を阻む問題として「自分の手が良いのか悪いのかわからない」という問題があります。 ツモが毎回ランダムであるため、仮に悪い手を指したとしてもその後のツモに救われて何とかなる場合もありますし、仮に良い手を指したとしてもその後のツモが悪いと形が崩れてしまう場合もあります。 ある手が良いか悪いを知るためには、何度も試行を重ねて統計的に判断しなければなりません。 これは非常に時間がかかります。

幸いなことに、現在多くの上級者が YouTube にプレイ動画をアップロードしています。 プレイ動画を解析して上級者がある局面でどういう手を指したかどうかを知ることができれば、それを使って自分のプレイを評価できるのではないでしょうか?

しかし、プレイ動画はそのまま統計処理できる形式ではありません。 統計処理に適した形式、つまり棋譜(= 手順をテキストとして書いたもの)に変換する必要があります。

そこで今回、ぷよぷよのプレイ動画を解析して棋譜を生成するプログラムを作ったので、その紹介をしていきます。

解析に用いた動画

このプログラムを作るにあたり『ぷよぷよクロニクル 第2回おいうリーグ S級リーグ ようかん vs まはーら 50先』 をサンプルとして利用させていただきました。

使用した言語/ライブラリ

今回の動画解析は PythonOpenCV を使いました。Jupyter notebook で作業すると動画のフレームやメトリクスのグラフなどをインラインで描画できて便利でした。

↓ Jupyter notebook で動画の1フレーム目を描画している図:

f:id:nojima718:20181203204416p:plain

フィールド上のぷよの認識

フィールドの枠の位置は時刻にかかわらず一定なので、今回は given ということにしました。 フィールドには横に6個、縦に12個のマスが等間隔で並んでいるため、枠の位置が決まればマスの位置も自動的に決まります。

次に、マスの状態(空、赤、黄、青、緑、紫、おじゃまの7状態)を判定します。 これは単純に状態ごとに予めパターン画像を用意しておいて、マスの画像とパターン画像との差分が最も小さかった状態を選ぶというアルゴリズムにしています。

下図の上の画像が (4, 4) に位置するマスの画像で、下の画像が赤のパターン画像との差分を取った画像です。 全体的に黒くなっていてそれっぽい感じがしますよね?

f:id:nojima718:20181203205637p:plain

下図は実際のフィールドに対してフィールド認識した結果です。 左が与えられたフィールドの画像で、右が認識結果を使って作った画像です。 地面に設置しているぷよは正しく認識できていることがわかると思います。 一方で操作中のぷよは正しく認識できていません。 これは認識アルゴリズムがマス目単位で判定しているからです。

f:id:nojima718:20181203205933p:plain

ぷよを置いた瞬間かどうかの判定

ぷよぷよ棋譜を生成したいという目的において、操作中のぷよが空中にある状態のフレームは不要です。 ぷよが接地し、場所が確定した瞬間のフレームこそが重要です。 ではどうやってぷよを置いた瞬間のフレームを識別すればよいでしょうか?

ぷよを置いたとき、次に起こりうることは次の3通りです。

  1. 次のぷよをツモる
  2. ぷよが消える
  3. おじゃまぷよが降る

そこで1から順に考えていきます。

1. 次のぷよをツモる瞬間の判定

あるフレームが次のぷよをツモる瞬間かどうかは、ネクスト欄およびダブルネクスト欄を見れば判定できます。

これらの欄はツモの瞬間にぷよがスライドし、次のぷよが表示されます。 これ以外のタイミングでは動きません。 したがって、これらの欄に変化があるかどうかを調べればぷよをツモったかどうかがわかります。

次のグラフはネクストぷよ表示欄について、1フレーム前とのピクセル差分の合計値を表しています。 x軸は時刻です。ツモったタイミングに合わせて値が跳ねているため、これの変化率を見ればツモの瞬間がわかります。

f:id:nojima718:20181203220412p:plain

しかし、実際にやってみるとうまくいかない場合があります。 例えば下図のようなケースです。 連鎖光がネクスト欄に重なっており、ナイーブに判定するとツモったとみなされてしまいます。 今回はネクスト欄とダブルネクスト欄両方に連鎖光が重なることは少ないだろうということで、両方の欄で独立にツモ判定を行い、両方が true だった場合にツモったと判定することにしました。 しかし、絶妙な軌道で連鎖光が発射されると誤判定しそうなので、この判定の改善は将来の課題です。

f:id:nojima718:20181203220800p:plain

また、ゲームのせいなのか動画のせいなのかわからないのですが、たまに連続する2フレームが全く同じ画像になっていることがあります。このときに1フレーム前とのピクセル差分を取るとゼロになってしまって誤判定します。今回は3フレーム前と比較することで回避しました。

2. ぷよが消える瞬間の判定

ぷよが消える瞬間はスコアを見れば簡単に判定できます。 ぷよが消えるときだけスコアは「数値×数値」という表示になります(普段は一つの数値です)。 なので×マークがあるかどうかをパターンマッチで判定することにしました。

f:id:nojima718:20181203221454p:plain

x軸を時刻、y軸をピクセル差分としてグラフにプロットしてみました。 800フレーム目のあたりから13連鎖しているのが見てとれると思います。

f:id:nojima718:20181203223806p:plain

3. おじゃまぷよが降る

実はおじゃまぷよが降る場合は特に判別しなくても後処理で何とかできるので、処理していません。

情報を集約して棋譜を作る

これでぷよをツモる瞬間のフィールドの状況、ぷよが消える直前のフィールドの状況が時刻情報付きでわかったことになります。 後は連続する2つのイベントの間のフィールドの差分を取れば、どこにぷよを置いたのかがわかりますし、ぷよの消滅が連続して何回起こったのかを数えれば何連鎖したのかがわかります。

実際にある試合の様子を棋譜として出力してみたら以下のようになりました(1Pのみです)。 結構それっぽい棋譜ができました。

   33:  ▲1一黄  ▲2一青
   59:  ▲3一青  ▲3二紫
   85:  ▲2二紫  ▲2三青
  108:  ▲2四黄  ▲2五赤
  135:  ▲4一紫  ▲4二赤
  160:  ▲3三黄  ▲4三紫
  186:  ▲1二青  ▲1三黄
  209:  ▲3四赤  ▲3五青
  237:  ▲5一赤  ▲6一赤
  261:  ▲1四黄  ▲1五赤
  288:  ▲5二黄  ▲5三赤
  316:  ▲6二黄  ▲6三黄
  339:  ▲1六赤  ▲2六青
  364:  ▲6四赤  ▲6五赤
  389:  ▲5四黄  ▲5五赤
  412:  ▲5六紫  ▲6六紫
  435:  ▲6七紫  ▲6八赤
  458:  ▲4四青  ▲4五黄
  479:  ▲1七青  ▲1八青
  499:  ▲3六赤  ▲3七赤
  520:  ▲5七黄  ▲5八紫
  538:  ▲3八青  ▲3九青
  560:  ▲4六赤  ▲4七黄
  581:  ▲5九紫  ▲6九赤
  601:  ▲4八黄  ▲4九青
  622:  ▲5十青  ▲5十一紫
  642:  ▲6十青  ▲6十一赤
  661:  ▲6十二黄
  681:  ▲2七黄  ▲2八赤
  700:  ▲1九赤  ▲2九赤
  718:  ▲1十黄  ▲2十紫
  759:  ▲4十紫  ▲4十一紫
  777:  ▲4十二青  ▲5十二黄
  804:  ▲3十赤  ▲2十一黄
  832:  ▲3十一紫  ▲2十二青 発火
  873:  2連鎖
  914:  3連鎖
  956:  4連鎖
  996:  5連鎖
 1038:  6連鎖
 1082:  7連鎖
 1122:  8連鎖
 1162:  9連鎖
 1203:  10連鎖
 1244:  11連鎖
 1286:  12連鎖
 1327:  13連鎖
 1397:  ▲3一黄  ▲3二紫
 1463:  ▲3三黄  ▲3四赤
 1529:  ▲投了

661 フレーム目でぷよを1個しか置いていないことになっていますが、これは片方のぷよが画面外に置かれたからです。 また、おじゃまぷよの落下はこの棋譜には書かれていませんが、プログラムの中のデータとしては取得できています。

Future work

今のところ PoC レベルなので、実用にはまだまだ全然足りません。

まず、まだ 1P 側しか取れないので 2P 側も取る必要があります。 ゲームオーバー判定が背景に依存しているので背景が変わると動きません。 ぷよクロじゃなくてぷよスポにも対応したいです。 全消しの場合、パターンマッチが誤爆するかもしれません(試してない)。

暇を見つけてぼちぼちやっていきたいです。

まとめ

はじめての動画処理でしたが、意外と泥臭い力技で何とかなりました。 やってみるものですね。

明日は utgwkk さんの「レコード多相についてお話します」です。お楽しみに。

NLL のおかげで Rust で平衡二分木を実装できた

Rust で平衡二分木を書くのは何となく難しいイメージがありました。 unsafe を使わずに実装できるものなのか気になったので、試しに実装してみました。

結論から言うと、unsafe を使わなくても平衡二分木は実装できました。また、unsafe だけでなく、RcRefCell も使っていません。 ただし NLL がないとコンパイルが通りませんでした。NLL は神機能ですね。

Splay

今回実装した平衡二分木は Splay 木というものです。

Splay 木は、search や insert などの典型的な操作を償却 O(\log n) 時間で実行できます。 また、Splay 木は最後にアクセスしたノードを木のルートに持ってくる性質があるため、アクセスに局所性がある場合によい性能が出るそうです。

平衡二分木といえば何と言っても赤黒木ですが、赤黒木は実装が大変すぎるので今回は却下しました。

アルゴリズム

Splay 木のアルゴリズムについては、Wikipedia に図付きで書いてあるので、こちらを参照下さい。

Splay tree - Wikipedia

重要なのは Splay 操作 という操作で、これは特定のキーを持つノードをルートに持ち上げていく操作です。 この持ち上げていく過程でその周辺のノードが何となく平衡状態に近づくようになっています。

search や insert は Splay 操作を使って簡単に実装できます。

実装

BinaryNode

ノードは key と左右のノードを保持します。今回は簡単のため value は保持しませんでした。 ノードは左右のノードを 所有 していることに注意してください。

struct BinaryNode<K: Ord> {
    key: K,
    left: Option<Box<BinaryNode<K>>>,
    right: Option<Box<BinaryNode<K>>>,
}

SplayTree

SplayTree は単に木のルートを保持しているだけです。 ノードが一つもない場合もあるので Option になっています。

pub struct SplayTree<K: Ord> {
    root: Option<Box<BinaryNode<K>>>,
}

rotate

データ構造の準備ができたので、Splay 操作の実装に入ります。 まずは rotate_right です。

rotate_right は下図のように与えられた部分木のルートの左側のノードが新たなルートとなるように木を回転させる操作です。 もちろん、回転させるときにノードの順序関係は保つ必要があります。

f:id:nojima718:20181120012345p:plain

rotate_right の実装は以下のようになりました。

// root の左側のノードが新たな根となるように木を回転させ、新たな根を返す。
fn rotate_right<K: Ord>(mut root: Box<BinaryNode<K>>) -> Box<BinaryNode<K>> {
    let mut new_root = root.left.unwrap();
    root.left = new_root.right;
    new_root.right = Some(root);
    new_root
}

まず、引数としてルートとなるノードの を取ります。参照ではありません。 つまり、rotate_right はルートノードの所有権を要求するということです。 そして、戻り値として新しいルートノードを所有権付きで返しています。

所有権が必要なのはノードの親子関係を弄るからです。 ノードの親子関係を変えるためには move する必要があり、move するにはそのノードを所有していないといけません。

また、関数の中身についてですが、実はこれ、NLL を有効にしないとコンパイルが通りません。 3行目でコンパイルエラーになります。

こういういかにも borrow check が難しそうなコードもちゃんとコンパイルしてくれる NLL は素晴らしいですね。

splay

rotate ができれば後は場合分けして splay 操作を実装するだけです。 key が左側にある場合と右側にある場合の2通り書かないといけないので、左側にある場合のみを示します。

// root を根とする部分木に対してスプレー操作を実行し、新たな根を返す。
// key を持つノードが部分木に存在する場合、それが新たな根となる。
// key が部分木に存在しない場合、最後にアクセスしたノードが根となる。
// 部分木は破壊的に変更される。
fn splay<K: Ord>(key: &K, root: Option<Box<BinaryNode<K>>>) -> Option<Box<BinaryNode<K>>> {
    if root.is_none() {
        return None;
    }
    let root = root.unwrap();

    let new_root = match key.cmp(&root.key) {
        Ordering::Less => splay_left(key, root),
        Ordering::Greater => splay_right(key, root),
        Ordering::Equal => root,
    };
    Some(new_root)
}

// key が root の左側にあるときのスプレー操作を行う。新たな根を返す。
fn splay_left<K: Ord>(key: &K, mut root: Box<BinaryNode<K>>) -> Box<BinaryNode<K>> {
    if root.left.is_none() {
        return root;
    }
    let mut left = root.left.unwrap();

    if key < &left.key {
        // zig-zig

        // left-left の部分木の根に key を持ってくる
        left.left = splay(key, left.left);
        root.left = Some(left);

        // 右回転を2回行って left-left を根に持ってくる
        let new_root = rotate_right(root);
        if new_root.left.is_some() {
            rotate_right(new_root)
        } else {
            new_root
        }
    } else if key > &left.key {
        // zig-zag

        // left-right の部分木の根に key を持ってくる
        left.right = splay(key, left.right);

        // 左回転と右回転を行って left-right を根に持ってくる
        root.left = if left.right.is_some() {
            Some(rotate_left(left))
        } else {
            Some(left)
        };
        rotate_right(root)
    } else {
        // zig
        root.left = Some(left);
        rotate_right(root)
    }
}

insert とか search とか

長くなってきたので、ここでは省略します。GitHub に全体のソースコードを上げているので、そっちを参照してください。

workspace/splay_tree.rs at master · nojima/workspace · GitHub

まとめ

NLL は最高。

テストクラスを継承するとインターフェイスのテストが捗る

User オブジェクトの永続化を行う UserRepository というインターフェイスがあるとします。 また、それを実装した2つのクラス InMemoryUserRepositoryMySqlUserRepository があるとします。 これらのクラスのテストはどのように書けばよいでしょうか? (テストフレームワークは JUnit5 です)

普通に考えると InMemoryUserRepositoryMySqlUserRepository の2つのテストを個別に書かないといけないように思います。 しかし、これらのクラスはどちらも UserRepository として振る舞うはずなので、UserRepositoryインターフェイスのみを使ってテストを書けば1回テストを書くだけで2つの具象クラス両方をテストできます。

UserRepository が以下のようなインターフェイスだったとします。 (パスワードをそのままデータベースに保存するのはアウトですが、例なので許してください)

interface UserRepository {
    // 指定した id を持つユーザーを取得する。
    // 存在しないときは null を返す。
    fun getUser(id: UserId): User?

    // 名前とパスワードを指定して新しくユーザーを作成する。
    fun createUser(userName: UserName, password: Password): User
}

実装として、InMemoryUserRepositoryMySqlUserRepository があります。

class InMemoryUserRepository : UserRepository {
    private var nextUserId = 1L
    private val users = HashMap<UserId, User>()

    override fun getUser(id: UserId) = users[id]

    override fun createUser(userName: UserName, password: Password): User {
        val id = UserId(nextUserId)
        nextUserId += 1

        val user = User(id, userName, password)
        users[id] = user

        return user
    }
}
class MySqlUserRepository(
    private val dataSource: DataSource
) : UserRepository {

    override fun getUser(id: UserId): User? {
        // 略
    }

    override fun createUser(userName: UserName, password: Password): User {
        // 略
    }
}

まずは、インターフェイスである UserRepository に対してテストを書きます。 テストクラスは abstract class にしておき、テスト対象である UserRepository は abstract val として宣言します。

internal abstract class UserRepositoryTest {

    abstract val sut: UserRepository

    @Test
    @DisplayName("getUser - 正常系")
    fun getUser() {
        // Setup
        sut.createUser(UserName("alice"), Password("open sesame"))

        // Exercise
        val user = sut.getUser(UserId(1))

        // Verify
        val expected = User(UserId(1), UserName("alice"), Password("open sesame"))
        assertThat(user).isEqualTo(expected)
    }

    @Test
    @DisplayName("getUser - 存在しないユーザーを取得すると null が返る")
    fun getNonexistentUser() {
        // Exercise
        val user = sut.getUser(UserId(100))

        // Verify
        assertThat(user).isNull()
    }

    @Test
    @DisplayName("createUser - 正常系")
    fun createUser() {
        // Exercise
        val user = sut.createUser(UserName("bob"), Password("secret"))

        // Verify
        val actual = sut.getUser(user.id)
        val expected = User(user.id, UserName("bob"), Password("secret"))
        assertThat(actual).isEqualTo(expected)
    }
}

これでテストケースの定義が書けました。では、このクラスを継承してテストの実体を作ります。 まずは InMemoryUserRepositoryTest から。

internal class InMemoryUserRepositoryTest : UserRepositoryTest() {
    override val sut: UserRepository = InMemoryUserRepository()
}

たった3行でした。

次は、MySqlUserRepositoryTest を書きます。

internal class MySqlUserRepositoryTest : UserRepositoryTest() {
    private val dataSource = /* テスト用 MySQL の DataSource を作成する処理 */
    override val sut: UserRepository = MySqlUserRepository(dataSource)

    init {
        val flyway = Flyway.configure()
            .dataSource(dataSource)
            .load()
        flyway.clean()
        flyway.migrate()
    }
}

MySQL を使う場合は DataSource を作ったり、テストケースごとにデータベースを初期化したりする必要があるので、InMemory よりもちょっとコードが増えています。 この例では Flyway を使ってデータベースの初期化を行っています。

この状態でテストを実行すると InMemory と MySQL それぞれに対して UserRepositoryTest で定義した3つのテストケースが実行されます。 2つの具象クラスに対するテストを共通化できたというわけです。

以上、テストクラスを継承することでインターフェイスのテストを行う例でした。

rust-protobuf で読み書きしてみる

rust-protobuf を使ってみる。

大まかな流れ

  1. protoc をインストールする
  2. cargo build 時に proto をコンパイルするようにする
  3. コンパイルによって生成された struct を使って読み書きする

protoc をインストールする

Ubuntu ならこんな感じ:

sudo apt update
sudo apt install protobuf-compiler

cargo build 時に proto をコンパイルするようにする

まず、コンパイルすべき proto ファイルを用意する。 以下のファイルを src/person.proto に置く:

syntax = "proto3";

message Person {
  uint64 id = 1;
  string name = 2;
}

次に、Cargo.toml に以下を追加する:

[build-dependencies]
protoc-rust = "2.0"

build.rs というファイルを Cargo.toml を同じディレクト に以下の内容で置く:

extern crate protoc_rust;

use protoc_rust::Customize;
use std::error::Error;

fn main() -> Result<(), Box<Error>> {
    let proto_files = vec!["src/person.proto"];

    protoc_rust::run(protoc_rust::Args {
        input: &proto_files[..],
        out_dir: "src/protos",
        includes: &[],
        customize: Customize {
            ..Default::default()
        },
    })?;
    Ok(())
}

ここで out_dirsrc/protos というディレクトリを指定したので、作成しておく。

mkdir src/protos

これで proto をコンパイルする準備が整った。あとは cargo build すればコンパイルされる。

cargo build

# person.rs が生成されていることを確認
ls src/protos

コンパイルによって生成された struct を使って読み書きする

まず、Cargo.toml に以下の dependency を追加する:

[dependencies]
protobuf = "~2.0"

次に生成されたモジュールを use できるようにする。src/protos/mod.rs を以下の内容で作成:

pub mod person;

次に main.rs に以下を追加:

mod protos;
use protos::person::Person;

これで準備は整ったのでいよいよ読み書きしていく。

書き込み

以下のように、Person::new() で入れ物を作り、set_* で値を入れ、write_to_writer で書き出す。

use protobuf::Message;
use std::fs::File;

...

let mut person = Person::new();
person.set_id(42);
person.set_name("Yusuke Nojima".to_string());

let mut file = File::create("/tmp/person.bin")?;
person.write_to_writer(&mut file)?;

読み込み

シリアライズしたいスライスを merge_from_bytes に渡すと読み込んでくれる。

use protobuf::Message;
use std::fs::File;
use std::io::Read;

...

let mut file = File::open("/tmp/person.bin")?;

let mut buffer = vec![];
file.read_to_end(&mut buffer)?;

let mut person = Person::new();
person.merge_from_bytes(&buffer[..])?;

サンプルコード

サンプルコード全体は GitHub にアップロードしたので、断片じゃなくて動作するコードが読みたい人はこっちを参照してください:

workspace/rust-protobuf-sample at master · nojima/workspace · GitHub

参考にしたページ

rust-protobuf 自体にはあまりドキュメントがないけど、C++版と使い方がかなり似ているので、本家の C++ のドキュメントが参考になった。

Protocol Buffer Basics: C++  |  Protocol Buffers  |  Google Developers

Transactional Database を作りたい

セキュリティキャンプ2018のデータベースの講義に関するツイートがTLに流れてきたのを見て、自分もデータベース作ってみたいなぁと思ったので作り始めることにした。 データベースを作るのは初めてなので、まずは「トランザクションのあるデータベース」と言い張れる最小限のものを作りたい。

ということで「ぼくのかんがえたさいじゃくのデータベース」の仕様を作った。明日から頑張る。

概要

  • 表形式ではなく、key-value store にする
    • key も value も String 型
  • トランザクションをサポート
  • クライアントは逐次的に処理する
  • データの総量がメモリに収まると仮定する

コマンド

以下の4つのコマンドをサポートする。

read KEY
write KEY VALUE
commit
rollback

クライアントは TCP でデータベースサーバーに接続してコマンドを送りつける。

ACID

Atomicity

トランザクションの結果が、コマンドが全て実行された結果か、全く実行されなかった結果のどちらかになる性質。

Consistency

……このデータベースの場合、満たすべき制約は存在しない?

Isolation

トランザクションの過程が他のトランザクションから観測されない性質。 このデータベースではそもそも複数のトランザクションを同時に実行しないので自動的に満たされる。

Durability

成功したトランザクションの結果が(たとえデータベースやコンピュータがクラッシュしても)失われない性質。

設計

  • Rust で作る。
  • メモリ上に HashMap として key-value store を持つ。
  • ディスクに WAL を書く。
  • 起動時に WAL を先頭から全部読んで HashMap を再生する。
    • このとき、WAL の末尾の未コミットのレコード列は truncate する。
    • 中途半端に書かれた WAL のレコードは truncate する。このために WAL のレコードには CRC64 をつけておく。

O'Reilly の Kafka 本を読みました

会社の同僚の @ueokande さんから Kafka 本を献本して頂きました。 大体読み終えたので紹介記事を書こうと思います。

https://www.amazon.co.jp/dp/4873118492

Kafka と私

私は2015年ぐらいから2017年ぐらいまで会社のログ基盤を整備する仕事をしていました。

ログ基盤プロジェクト以前は、1日数百GBのログを一台の物理マシンに ssh で集約するという大変ナイーブな仕組みで運用されていました。 その物理マシンにはバッテリーバックアップ付きの RAID ボードが載っていてそれなりの IOPS が出るんですが、ログの増加に耐えきれず性能限界に達しようとしていました。

ueokande さんと一緒に作った新しいログ基盤では、一台の物理マシンにログを集約するのではなく、8台の Kafka ノードに分散してログを送信し、それを HBase に保存したり Presto で解析したりするようになっています。 Kafka は非常に高速で、ログ量がバーストしたときも楽々捌いていました。(昔のシステムではバーストがあると処理が追いつかず、大変なことになっていました)

ueokande さんによる詳しい解説記事: http://blog.cybozu.io/entry/2018/03/19/080000

Kafka を運用にのせるまで

Kafka を運用にのせるのは、簡単ではありませんでした。特に困ったのはドキュメントの不足でした。

Kafka の情報は当時公式ドキュメントぐらいしかなく、それだけでは不明な点がいろいろありました。 例えば、Kafka Broker の設定項目として、num.partitions という設定項目があるのですが、ドキュメントには「The default number of log partitions per topic」としか書いてありません。この値をどう決めるのがよいのでしょうか?

Consumer を書くときも、公式ドキュメントだけでは心もとないものがあります。 我々のログ基盤はログの at-least-once を保証するという要件があります。 Broker や Consumer が at-least-once を満たすように設定したりライブラリを利用したりしないといけないのですが、どのオプションをつけてどのようにメソッドを呼べばよいのでしょうか?

また、Kafka の内部の仕組みについての解説もあまり見当たりませんでした。 特に、Kafka が障害時にどのように振る舞うかの情報は公式ドキュメントにはほとんど書いてありません。 内部事情がよくわからないので、障害対応時にログに書かれている内容の意味が理解できずに困ったりしました。

Kafka 本を読みましょう!

ログ基盤プロジェクトをやっていた当時は本当に情報がなく、実験してみたりソースコードを読んだりしないといけませんでしが、Kafka 本が状況を変えてくれました。 上で挙げた疑問にはすべてこの本が答えてくれます:

  • num.partitions を決めるときに何を考慮すべきかは2章に書いてあります。また、num.partitions だけでなく多くの基本的な設定に関してそれが何なのか、その設定値を増やしたり減らしたりしたときにどのようなトレードオフがあるのか等が簡潔に書いてあり、とても参考になります。
  • at-least-once を保証するログ転送を作りたければ6章を読みましょう。公式ドキュメントでは断片的にしか書かれていなかった信頼性のあるデータ配信の方法が一箇所にまとめて書いてあります。いろいろ罠があるので at-least-once が必要な人は必ず読んでおいたほうがいいです。
  • Kafka のログの意味がわからなくて困ったら5章を読みましょう。リーダーエレクションがどのように動くのか、パーティションはどのように割り当てられるのか、インデックスとは何か、などを理解しておくと障害時にログを追うのが格段にやりやすくなるはずです。

Kafka はとにかく柔軟性が高く、何をやるにしても様々な選択肢があります。 しかし、要件に対して最適な選択肢を選ぶためには、Kafka の特性を理解して正しく Broker や Consumer を設定する必要があります。 Kafka は利用者に多くの知識を要求するシステムだと思います。

この本は、Kafka を本番環境で利用する人にとっては必読です。読みましょう!

ICFPC 2018 に参加しました

ICFPC 2018 にチーム「銀閣寺GOLD」として参加しました。 メンバーは以下の4人です。

また、チームのリポジトリhttps://github.com/seikichi/icfpc2018 にあります。

問題

今年の問題は小さなロボットたちを操って3Dプリンタ的な作業を行うことです。

R×R×Rの三次元の空間があって、その中に "nanobot" というロボットが配置されています。 ロボットは各ターンに移動したり分裂したり voxel を埋めたりできます。 ロボットをうまく操って、与えられた3Dモデルをプロットしてください。 ただし毎ターン、エネルギーが消費されていきます。 消費されるエネルギーをできるだけ小さくしてください。

プロットしている間、プロット済みの voxel が宙に浮いた状態になってしまってはいけません。 しかし、エネルギーを大量に消費することで High Harmonics 状態 (voxel が宙に浮いてもよい状態) にすることができます。

0日目

去年の ICFPC のブログに「C++ は飽きたので来年は Rust で」って軽い気持ちで書いたら、本当に Rust を使うことになってしまいました。 Rust は The Book を読んで AtCoder の問題を何問か Rust で解いたことがある程度の経験しかありません。 チームのメンバーも大体同じようなレベルでした。 こんな状態で ICFPC ができるのかと結構不安でしたが、当たって砕けろみたいな気持ちで ICFPC に突入しました。

1日目

深夜1時に ICFPC スタート。 問題を読んで役割分担を決めました。 この時点で深夜2時か3時ぐらいだったので就寝。

11時に起床。cosくんとペアプロすることになりました。 まずはトレースファイル(ロボットのコマンド列を並べたバイナリファイル)を出力できるようにライブラリを作り始めました。

このときたぶん初めて Rust でユニットテストを書いたんですが、#[test] でテスト関数を書いて cargo test するだけでテストが動くのに感動しました。 C++ の時代はまず gtest を用意して心のこもった Makefile を書かないとテストできませんでした。

トレースファイルのエンコーダーを作った後はコマンド群の挙動をシミュレートするシミュレータを作ってました。 シミュレータはコマンドを実行して状態を更新したり各ロボットの動きが不正じゃないかをチェックしたりするプログラムです。

シミュレータがチェックすべきものの中に「各 voxel が grounded かどうか」というものがあります。 毎ターンすべての voxel を舐めて grounded かどうかを調べていると滅茶苦茶遅そうなので、grounded 判定は UnionFind で連結成分を管理しておく方針でやることにしました。

「これ、2日目に Full な voxel を Void にできるコマンドが追加されたりしたら崩壊するよね…?」
「ははは、まさかね…」

一方、seikichi-qwerty 班がロボットをグリッド状に分裂させて、それぞれで並列にモデルを構築していく AI を作っていました。 ライトニングにはこれを提出。

↓ GridFissionAI の様子(ライトニング用じゃなくて Full 用なので並列度が違うけど動作はほぼ同じ)

f:id:nojima718:20180730002149g:plain

2日目

Void, GFill, GVoid コマンドが追加されました。 Void は full だった voxel を void にできるコマンドです。 見事にフラグが回収されて絶望が深い。

また、これまではモデルを構築する問題だけでしたが、構築済みのモデルを完全に削除する disassemble 問題と、構築済みのモデルから別のモデルを構築する reassemble 問題が追加されました。

とりあえず、reassemble 問題は disassemble 問題と assemble 問題をそれぞれ解いてくっつけると解けるので、まずはその方針を実装することに。

また、ライトニングに提出した AI は Harmonics が常に High の状態だったので、まずは Harmonics が Low で十分な問題は Low で解けるようにしようということで、

  1. Harmonics を Low のままにして問題を解いていく
  2. シミュレータで voxel が宙に浮いているか調べる
  3. 宙に浮いていたら Harmonics を High にする
  4. プロットしていって再び grounded になったら Harmonics を Low にする

というロジックを入れました(AI班が)。

自分は追加されたコマンドをシミュレータに実装し、崩壊した grounded の判定をナイーブなアルゴリズムで直したりしてました。 しかし、ナイーブな grounded 判定アルゴリズムは遅すぎて大きいサイズの問題が全然終わらないことが判明。 仕方がないので、Void、GVoid が来ない限りは UnionFind で効率的に判定、Void、GVoid が来たら全部再計算という方針にしつつ、典型的な Void では再計算を避けるために以下のヒューリスティックを実装しました。

Void の対象の voxel について、以下が成り立つとき、再計算は不要。

  • その真上が void かつ、
  • その真下が full かつ、
  • その周囲4つの voxel すべてについて「それが void または その真下が full」

3日目

qwerty さんが二次元 GVoid を使ってモデルを disassemble する AI を作ってました。

f:id:nojima718:20180730005450g:plain

また、cos くんが grounded である状態を保つように BFS で良い経路で voxel を埋めていく AI を作ってました。 ロボット同士がぶつからないように移動させるのがすごく大変だったようです。

f:id:nojima718:20180730010417g:plain

また、seikichi くんが grounded を維持しやすいように支柱を立てつつ GridFissionAI っぽいことをし、最後に支柱を消す AI を作ってました。 動きが楽しい。

f:id:nojima718:20180730021147g:plain

自分は GFill を使って assemble していく AI を作ろうとしました。 今回自分はずっとシミュレータをやっていたので、3日目で初めて AI に取り掛かったのですが、予想以上に難しい。 AI を分裂させたり、お互いにぶつからないように移動させたりといった、ぱっと見そんなに難しそうに見えない作業が普通に大変で、かなり手間取りました。 結局、コンテストの時間内に GFill AI を完成させることはできませんでした。

そしていよいよラスト1時間。 AWS で 72 コアマシンを借りて並列で AI をぶん回します。 複数個の AI があるので、すべての AI で各問題を解いて、最もエネルギー消費量が少ない解を提出するようにします。

流石に1時間もあれば余裕で提出できるだろうと思っていましたが、AI の計算が意外と終わらなかったり、途中で VM がディスクフルになって計算をやり直すはめになったりして、結局 zip を提出できたのは終了3分前でした。 めっちゃハラハラした……。

所感

  • Keep

    • Rust は最高でした。
      lifetimeとかでハマるかと思ってたけどそんなことはなく、むしろコンパイラのメッセージが超親切だし cargo が便利だし、実行速度・コンパイル速度共に申し分ありませんでした。 また、4人のメンバーの環境が Windows, WSL, Linux, Mac と見事にバラバラであったにもかかわらず、全くそれを意識することなく開発できました。

    • カンバンは便利でした。
      今年初めて GitHub の project 機能を使ってみました。 毎年三日目ぐらいになると、何をやっていいのかわからない、他の人が何をやっているのかわからない、という状況になっていましたが、今年は状況が把握しやすかったです。

  • Problem & Try

    • AI とシミュレータのインテグレーションがあまり上手くいきませんでした。 本来であれば、シミュレータが実装した関数を AI の実装に再利用できるべきですが、シミュレータのインターフェイスが微妙で AI とシミュレータの間で実装がかなり重複してしまいました。 重複を減らせれば AI をもっといっぱい書けたのではないかと思います。

      もうちょっと早くインテグレーションが上手くできないことに気付いていれば何とか対応できたと思うので、次からは1日目の後半ぐらいには AI とシミュレータをくっつけてみるべきだと感じました。

    • 三日目で、GFill AI に5~6時間ぐらい費やしましたが結局完成しませんでした。もうちょっと早く見限って提出準備の自動化など、インフラ的な作業をやっておくべきでした。

結果

9位だったようです。 初めてのトップ10入りです。嬉しい!