読者です 読者をやめる 読者になる 読者になる

/home/cympfh/

はてなブログはクソなのでやめます => https://hackmd.io/s/SyQBwu6Kg#

Can't Stop の戦略

考えてみる.

ルール概要

  • 2-4人ゲーム
  • 盤面
    • $i$-th レーンがある
      • $i=2,3,\ldots,11,12$
      • レーンとは $m_i = 13 - 2 \times |i-7|$ 個のマスが一列にならんだもの
        • 端がスタートでもう端がゴール
    • 人数に対応した色の が十分な数ある
    • 3つの がある
      • ではない
    • 初め盤面には石も駒も置かれてない
  • ターン制で手を行う
    • 1人の1ターンは好きなだけ次を繰り返す
      1. 4つのサイコロを振る
      2. 出目を2つと2つに分け、それぞれの和を $m, n$ とする
      3. $m$-th レーンと $n$-th レーンのそれぞれについて、駒をスゴロクの要領で一つ進める
        • 駒を一つ進める とは次によって定められる手続きのこと
          • そのレーンに既に駒があるなら、それを一マスだけゴール方向に動かす
            • 既にゴールのマスにあるなら何もしない
          • そのレーンに駒が無く、
            • 使用していない駒が余っているとき (駒は3つしかないことに註意)、
              • そのレーンに自分の色の石が置いてある時、その次のマスに駒を置く
              • 石も置いてないとき、スタートのマスに駒を置く
            • 駒が余っていないなら「駒を進めることに失敗」
          • ただし後述するが、レーンは使用不可という状態になる場合がある
            • そのようなレーンについては駒を進めることはできない
            • これは「駒を進めることに失敗」
        • 上で定めた手続きに於いて 失敗 を定めた
          • $m, n$ のいずれか一方で失敗するとき、成功する方だけ行う
          • $m, n$ の 両方で 失敗するとき、
            • バーストと言ってその人のターンは終了する
            • その際に、その人が進めた駒は盤面から取り除かれる !!
      4. バーストしなかった場合、ターンを自ら終わることが出来る
        • この場合、駒を自分の色の石に置き換え、次の人のターンに移る
          • 駒を置いてたマスに石を置いて、駒を取り除く
        • 終了を選択しないなら、サイコロを振るところから、再び繰り返す
    • 各レーンのゴールのマスに石を置かれた場合、そのレーンはその色の人のものになる
      • 石が置かれた直後からそのレーンは使用不可になる
      • 従ってこれはバーストを誘発する
    • ある一人のプレイヤーが3つのレーンを得るとゲームは終了し、その人の勝利となる

出目の確率

サイコロを振る前に私が考えることと言えば

「4個サイコロを振って出目の2個の組み合わせ (和) で $m$ が作れるか?」

ということである. すなわち、 すでに駒を置いた $m$ のレーンがある場合には、 $m$ を出しさえすればいいのである. そうすれば何度でもターンが続けられるので、それ以上の戦略は不要に思える.

4個のサイコロ中2個の和で $m$ を作る確率を計算する.

# 出目のリスト dices から2つ選んで m を作れるか?
def make?(dices, m)
  dices.combination(2).any? { |a, b| a + b == m }
end

# m-th lane
(2..12).each do |m|
  count = 0
  # 4個のサイコロの出目を全列挙
  (1..6).to_a.repeated_permutation(4) do |a, b, c, d|
    count += 1 if make?([a, b, c, d], m)
  end
  pr = count.to_f / 6 / 6 / 6 / 6
  puts "#{sprintf("%2d", m)} => #{pr}"
end

結果

 2 => 0.13194444444444445
 3 => 0.2330246913580247
 4 => 0.35570987654320985
 5 => 0.44753086419753085
 6 => 0.5609567901234568
 7 => 0.6435185185185185
 8 => 0.5609567901234568
 9 => 0.44753086419753085
10 => 0.35570987654320985
11 => 0.2330246913580247
12 => 0.13194444444444445

大凡予想通りである.

  1. $1 \leq m \leq 7$ では単調増加
    • $m \geq 7$ は対称
  2. $6,7,8$-th レーンだけが $50$ % を超える
  3. 雑な覚え方としては、端から $10, 20, 30, 40, 50, 60, 50, \ldots$ %

$6,7,8$-th の3つのレーンに駒を置いている場合にバーストする確率は、

0.06871499254944341

すなわち、93%くらいでセーフ.

速度

$m$-th レーンを考える. 4つのサイコロを振って駒を進める 1 ステップ で $m$-th レーン上の駒を平均でどれだけ進められるだろうか? これを 速度 と呼ぶことにする. ただし初めにスタートに駒を置くという行為も1マス進めると見なして良いのはいいでしょう.

N.B. 先ほどの確率は4つの出目の内の2つの和で $m$ を作れるか? しか考慮してないのでここでは使わない. 今は残り2つの和でも進めるところまで考慮する. すなわち、 $m$ と $m$ を作れるなら2マス進めることが出来るから.

速度を計算するプログラムは次の通り.

# 出目のリスト dices から2つ選んで n を作れるか?
def make?(dices, n)
  dices.combination(2).any? { |a, b| a + b == n }
end

# m-th lane
(2..12).each do |m|
  count = 0
  # 4個のサイコロの出目を全列挙
  (1..6).to_a.repeated_permutation(4) do |a, b, c, d|
    sum = [a, b, c, d].inject :+
    if make?([a, b, c, d], m)
      if sum == m + m
        count += 2
      else
        count +=1
      end
    end
  end
  average = count.to_f / 6 / 6 / 6 / 6
  puts "speed(#{sprintf("%2d", m)}) = #{average}"
end

結果

speed( 2) = 0.13271604938271606
speed( 3) = 0.2376543209876543
speed( 4) = 0.3703703703703704
speed( 5) = 0.4753086419753086
speed( 6) = 0.6080246913580247
speed( 7) = 0.7129629629629629
speed( 8) = 0.6080246913580247
speed( 9) = 0.4753086419753086
speed(10) = 0.3703703703703704
speed(11) = 0.2376543209876543
speed(12) = 0.13271604938271606
  1. 先ほどの確率と一見似てるがちょい大きくて $m=7$ に近づくほど大きくなる具合が大きい
  2. $1 \leq m \leq 7$ では単調増加
    • $m \geq 7$ は対称

速度と、レーンの長さが分かっているので、$m$-th レーンについて、平均で何ステップの試行がゴールに必要かが分かる.

結果

steps( 2) = 22.604651162790695
steps( 3) = 21.03896103896104
steps( 4) = 18.9
steps( 5) = 18.935064935064936
steps( 6) = 18.091370558375633
steps( 7) = 18.233766233766236
steps( 8) = 18.091370558375633
steps( 9) = 18.935064935064936
steps(10) = 18.9
steps(11) = 21.03896103896104
steps(12) = 22.604651162790695
  • 想像以上に、どのレーンであっても、まあまあバランスが取れている
  • しかしやっぱり $m=7$ 付近が有利で、端っこに比べて 4 ステップ程度早くゴールできる
  • 不思議なことに $m=7$ が最小というわけでもなく
    • $step(6) < step(7) < step(4) < step(5) < step(3) < step(2)$
    • となっている ($m \geq 8$ は対称性があるので)
    • 全然単調じゃない!!
広告を非表示にする

Kindle pdf 日本語 表示されない問題

くだらない記事を書きます:

昨年末くらいに Kindle Paperwhite を買いました. Kindle でマンガを400冊程度買ってたりよくpdfを読むので. arxiv で興味ありそうな論文をとりあえず send-to-kindle (電子メール) で端末に入れておく、という積ん読が割と捗る.

それはそうと、 日本語フォントが埋め込まれてない pdf を表示しようとすると日本語文字が空白で代替されて、全然読めないという問題があります.

関連ページ:

ようはあとからフォントを埋め込めばいい. 自分は Mac 環境なので、プレビューの「pdf書き出し機能」で埋め込みました. pdf を Preview.app で開いて pdf 出力です. フォントが埋め込まれた分、ファイルサイズが増えているのが確認できます.

f:id:cympfh:20170106165756p:plain

お疲れ様でした.

Rust Advent Calendar 2016 - 11日目

この記事は Rust Advent Calendar 2016 - Qiita 11日目のために書かれました.

qiita.com

requirements

box シンタックス及びパターン (box_syntax box_patterns) を使いたいので、 rustc 1.15.0-nightly 処理系を用います.

rustlearn

色々ありました. 色々あって 12/11 の記事を18日の夜に書いています. 予告では 「rustlearnで遊びます」 としていました. 12/10 の方が Rust による機械学習フレームワークである rusty-machine を紹介していたので、その流れで同じく機械学習フレームワークの rustlearn を紹介するつもりでした.

機械学習がしたいです (あるいは他の解決方法がわかりません). しかし世の中の機械学習フレームワークはとかく、猫も杓子も Python です. 場合に依っては恐ろしいことに Python2 で書かれたものもあります. 恐ろしいですね. Python が大好きな人間が世の中に大勢いらっしゃるのは承知ですが、できれば Rust のような、型安全でメモリ安全な言語で書きたいです. その点で leaf は本当に残念です. ディープラーニングフレームワークはどうせ大体、コアな部分は C言語でそして CUDA なので、Python なのはガワの部分だけなので速度は関係なくて、あとは書きやすければなんでもいいんでしょう. だからってなんでPythonなのかはしらんが.

rusty-machine ではディープラーニングをすることは出来ませんが、それ以外の有名どこの機械学習な分類器やクラスタリング手法が多く実装が揃っていてメンテナンスもされてるようなので、有用なフレームワークの一つ (ほとんど唯一つある内の一つ).

個人的にはとにかくRust で機械学習がしたい (他にすることがない) のですが、とにかくフレームワークが全然無いのでこんなものを紹介するつもりでした.

github.com

個人で作られてるものなので、あんまりメンテナンスが期待できないですが.

rustlearn も rusty-machine と同様に、ディープナントカ以外の定番の手法の実装をもりもり盛り込んだフレームワークという感じです. ただ、こちらには Factorization machines (FMs) という良さ気な予測器の実装が入ってます. というわけでこれを使った例を示してアドベントカレンダーにするつもりだったのですが、あんまり良い例と気力がないのと興味が巨大数に移ってしまったのがあって、アドベントカレンダーへの投稿を拒絶して早一週間...

予習事項

まずはこれを読んで下さい.

comic.pixiv.net

今回触れるのはこの中の 002 に出てくる B関数です.

B関数

B関数は次のような関数です

  •  B: (N, N) \to N
  •  B(0, n) = f(n)
    •  f は適当な簡単な関数. ここでは「寿司 虚空編」と同様に  f(n) = n + 1 とする
  •  B(m, 0) = B(m-1, 1)
  •  B(m, n) = B(m-1, B(m, n-1))

コンピュータ科学に馴染みのある人に取っては、アッカーマン関数の亜種程度に見えると思います. 私はそう思っています.

B関数の計算

「寿司 虚空編」の 002 では例として  B(3,3) を計算するのに無茶苦茶導出が長い、という説明が為されています. 実際にプログラムシてみたいと思います.

式の定義

計算の対象は式です. 式を記述する必要があります. そのために記述出来る式を定義します.

扱うべき式は、値 (i32) と足し算と関数 B です. 足し算は2つの値の和と求めるような二項関数だとします B は定義から二項関数です.

次は式の定義です.

#[derive(Clone, Debug)]
enum Expression {
    Value(i32),
    Add(Box<Expression>, Box<Expression>),
    B(Box<Expression>, Box<Expression>),
}

use Expression::{Value, Add, B};

これを用いて具体的な式を定義してみます. Debug を導いてもらってるので {:?} でフォーマット出力ができます.

let e = Value(1);
println!("{:?}", e);
// => Value(1)

let f = B(box Add(box e.clone(), box e.clone()), box Value(2));
println!("{:?}", f);
// => B(Add(Value(1), Value(1)), Value(2))

式の計算

式を計算する手続き eval を書いてみたいと思います. 何をやってるかはソースコードが語っているので日本語での説明は蛇足だと思います.

fn eval(e: &Expression) -> i32 {
    match *e {
        Value(x) => x,
        Add(box ref x, box ref y) => eval(&x) + eval(&y),
        B(box ref e1, box ref e2) => {
            let m = eval(e1);
            let n = eval(e2);
            if m == 0 {
                f(n)
            } else if n == 0 {
                eval(&B(box Value(m - 1), box Value(1)))
            } else {
                eval(&B(box Value(m - 1), box B(box Value(m), box Value(n - 1))))
            }
        }
    }
}
let e = B(box Value(3), box Value(3));
let result = eval(&e);
println!("=> {}", result);
// => 61

 B(3,3)=61 なので合ってます. 「寿司 虚空編」 002 では「こんだけやって61か!」と呆れられています.

さてしかし、この eval には味わい深さがありません. 「こんだけやって」の「こんだけ」を知らないからです.

「こんだけ」の出力

式の簡約を小さな単位でステップ実行して毎回出力させる. 具体的には次のルールを実装した手続きをステップとします.

  1. 構成性原理に従って外側から再帰的に式を読む
  2. 読んだ式が Value(_) なら、何もしない
    • 何もしない、とは、読んだ式を置き換えない、そのままにしておくこと
    • 「簡約できなかった」「失敗した」というニュアンス
  3. 読んだ式が Add(Value(m), Value(n)) なら数 m n からAdd を具体的に計算して式を計算結果で置き換える
    • これは確かに式を置き換えるので「簡約に成功した」
  4. 読んだ式が上以外の Add(e1, e2) なら、e1 e2 の簡約して置き換える
    • ただし、e1e2 もどちらも簡約されなかった (式の置き換えが行われなかった) 場合は、Add(e1, e2) の簡約も失敗する
  5. 読んだ式が B(Value(m), Value(n)) なら数 m n からB を具体的に計算して式を計算結果で置き換える
    • これは確かに式を置き換えるので「簡約に成功した」
  6. 読んだ式が上以外の B(e1, e2) なら、e1 e2 の簡約して置き換える
    • ただし、e1e2 もどちらも簡約されなかった (式の置き換えが行われなかった) 場合は、B(e1, e2) の簡約も失敗する

Add のルールと B のルールは同じなので、やや冗長.

例えば B(B(0,1), 2)B(2, 2) に展開される ( f(n)=n+1).

簡約という操作は所詮、式というデータの置換にほかならない. マクロ展開を連想してしまう (C言語とかのマクロじゃなくて、Lisp で使えるような本物のマクロのこと).

Rust には本物のマクロがあるので、なんとかマクロで表現できないか調べてたが特に無さそう. つまり、マクロなデータを標準出力する方法と、1ステップだけマクロを展開する手続きというのが無い.

以上のルールを実装したのが次の expand 手続き.

fn expand(e: &Expression) -> Option<Expression> {
    match *e {
        Value(x) => None,
        Add(box ref e1, box ref e2) => {
            match (expand(&e1), expand(&e2)) {
                (Some(Value(m)), Some(Value(n))) => Some(Value(m + n)),
                (Some(f1), Some(f2)) => Some(Add(box f1, box f2)),
                (Some(f1), None) => Some(Add(box f1, box (*e2).clone())),
                (None, Some(f2)) => Some(Add(box (*e1).clone(), box f2)),
                _ => None
            }
        },
        B(box Value(x), box Value(y)) => {
            if x == 0 {
                Some(Value(f(y)))
            } else if y == 0 {
                Some(B(box Value(x - 1), box Value(1)))
            } else {
                Some(B(box Value(x - 1), box B(box Value(x), box Value(y - 1))))
            }
        },
        B(box ref e1, box ref e2) => {
            match (expand(&e1), expand(&e2)) {
                (Some(f1), Some(f2)) => Some(B(box f1, box f2)),
                (Some(f1), None) => Some(B(box f1, box (*e2).clone())),
                (None, Some(f2)) => Some(B(box (*e1).clone(), box f2)),
                _ => None
            }
        }
    }
}

B(3,3) がやばいのは分かってるのでまず B(1,1) で実験

let mut e = B(box Value(1), box Value(1));
while let Some(f) = expand(&e) {
    println!("=> {:?}", &f);
    e = f;
};

出力は以下の通り.

B(Value(1), Value(1))
=> B(Value(0), B(Value(1), Value(0)))
=> B(Value(0), B(Value(0), Value(1)))
=> B(Value(0), Value(2))
=> Value(3)

まあ、こんなもんでしょう.

次は一つ大きくして B(2, 2) を試してみます.

B(Value(2), Value(2))
=> B(Value(1), B(Value(2), Value(1)))
=> B(Value(1), B(Value(1), B(Value(2), Value(0))))
=> B(Value(1), B(Value(1), B(Value(1), Value(1))))
=> B(Value(1), B(Value(1), B(Value(0), B(Value(1), Value(0)))))
=> B(Value(1), B(Value(1), B(Value(0), B(Value(0), Value(1)))))
=> B(Value(1), B(Value(1), B(Value(0), Value(2))))
=> B(Value(1), B(Value(1), Value(3)))
=> B(Value(1), B(Value(0), B(Value(1), Value(2))))
=> B(Value(1), B(Value(0), B(Value(0), B(Value(1), Value(1)))))
=> B(Value(1), B(Value(0), B(Value(0), B(Value(0), B(Value(1), Value(0))))))
=> B(Value(1), B(Value(0), B(Value(0), B(Value(0), B(Value(0), Value(1))))))
=> B(Value(1), B(Value(0), B(Value(0), B(Value(0), Value(2)))))
=> B(Value(1), B(Value(0), B(Value(0), Value(3))))
=> B(Value(1), B(Value(0), Value(4)))
=> B(Value(1), Value(5))
=> B(Value(0), B(Value(1), Value(4)))
=> B(Value(0), B(Value(0), B(Value(1), Value(3))))
=> B(Value(0), B(Value(0), B(Value(0), B(Value(1), Value(2)))))
=> B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(1), Value(1))))))
=> B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(1), Value(0)))))))
=> B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), Value(1)))))))
=> B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), Value(2))))))
=> B(Value(0), B(Value(0), B(Value(0), B(Value(0), Value(3)))))
=> B(Value(0), B(Value(0), B(Value(0), Value(4))))
=> B(Value(0), B(Value(0), Value(5)))
=> B(Value(0), Value(6))
=> Value(7)

そこそこ計算が大きくなりました.

ではいよいよ B(3, 3) で実行します.

$ ./run.exe | head -n 30
B(Value(3), Value(3))
=> B(Value(2), B(Value(3), Value(2)))
=> B(Value(2), B(Value(2), B(Value(3), Value(1))))
=> B(Value(2), B(Value(2), B(Value(2), B(Value(3), Value(0)))))
=> B(Value(2), B(Value(2), B(Value(2), B(Value(2), Value(1)))))
=> B(Value(2), B(Value(2), B(Value(2), B(Value(1), B(Value(2), Value(0))))))
=> B(Value(2), B(Value(2), B(Value(2), B(Value(1), B(Value(1), Value(1))))))
=> B(Value(2), B(Value(2), B(Value(2), B(Value(1), B(Value(0), B(Value(1), Value(0)))))))
=> B(Value(2), B(Value(2), B(Value(2), B(Value(1), B(Value(0), B(Value(0), Value(1)))))))
=> B(Value(2), B(Value(2), B(Value(2), B(Value(1), B(Value(0), Value(2))))))
=> B(Value(2), B(Value(2), B(Value(2), B(Value(1), Value(3)))))
=> B(Value(2), B(Value(2), B(Value(2), B(Value(0), B(Value(1), Value(2))))))
=> B(Value(2), B(Value(2), B(Value(2), B(Value(0), B(Value(0), B(Value(1), Value(1)))))))
=> B(Value(2), B(Value(2), B(Value(2), B(Value(0), B(Value(0), B(Value(0), B(Value(1), Value(0))))))))
=> B(Value(2), B(Value(2), B(Value(2), B(Value(0), B(Value(0), B(Value(0), B(Value(0), Value(1))))))))
=> B(Value(2), B(Value(2), B(Value(2), B(Value(0), B(Value(0), B(Value(0), Value(2)))))))
=> B(Value(2), B(Value(2), B(Value(2), B(Value(0), B(Value(0), Value(3))))))
=> B(Value(2), B(Value(2), B(Value(2), B(Value(0), Value(4)))))
=> B(Value(2), B(Value(2), B(Value(2), Value(5))))
=> B(Value(2), B(Value(2), B(Value(1), B(Value(2), Value(4)))))
=> B(Value(2), B(Value(2), B(Value(1), B(Value(1), B(Value(2), Value(3))))))
=> B(Value(2), B(Value(2), B(Value(1), B(Value(1), B(Value(1), B(Value(2), Value(2)))))))
=> B(Value(2), B(Value(2), B(Value(1), B(Value(1), B(Value(1), B(Value(1), B(Value(2), Value(1))))))))
=> B(Value(2), B(Value(2), B(Value(1), B(Value(1), B(Value(1), B(Value(1), B(Value(1), B(Value(2), Value(0)))))))))
=> B(Value(2), B(Value(2), B(Value(1), B(Value(1), B(Value(1), B(Value(1), B(Value(1), B(Value(1), Value(1)))))))))
=> B(Value(2), B(Value(2), B(Value(1), B(Value(1), B(Value(1), B(Value(1), B(Value(1), B(Value(0), B(Value(1), Value(0))))))))))
=> B(Value(2), B(Value(2), B(Value(1), B(Value(1), B(Value(1), B(Value(1), B(Value(1), B(Value(0), B(Value(0), Value(1))))))))))
=> B(Value(2), B(Value(2), B(Value(1), B(Value(1), B(Value(1), B(Value(1), B(Value(1), B(Value(0), Value(2)))))))))
=> B(Value(2), B(Value(2), B(Value(1), B(Value(1), B(Value(1), B(Value(1), B(Value(1), Value(3))))))))
=> B(Value(2), B(Value(2), B(Value(1), B(Value(1), B(Value(1), B(Value(1), B(Value(0), B(Value(1), Value(2)))))))))


$ ./run.exe | tail
=> B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), Value(52))))))))))
=> B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), Value(53)))))))))
=> B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), Value(54))))))))
=> B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), Value(55)))))))
=> B(Value(0), B(Value(0), B(Value(0), B(Value(0), B(Value(0), Value(56))))))
=> B(Value(0), B(Value(0), B(Value(0), B(Value(0), Value(57)))))
=> B(Value(0), B(Value(0), B(Value(0), Value(58))))
=> B(Value(0), B(Value(0), Value(59)))
=> B(Value(0), Value(60))
=> Value(61)

$ ./run.exe | wc -l
2433

お疲れ様です. こんだけやって 61 でした.

SECCON 2016 予選

いつも通り negainoido チームにお邪魔して参戦した. いつも通り私は、バイナリ解析といった王道な問題は全然なので、ちょっと邪道な問題に手を付けていた.

SECCON TOWER

問題は次の動画を読み取って PNG 画像を得よ、ということらしい.

www.youtube.com

(問題を知らない人は↑この動画の最初の2分くらいは我慢して見て下さい)

考えたこと

ロボット? (よく見ると伏せた紙コップの中にラズパイを仕込んで作ってある) がどうも手旗信号みたいなのを振っている. 最初の 70秒程度は、チュートリアルである. ロボットの動きに対して人間がノートに "WELCOMETO..." とペンで書き込む. ロボットの一つのポーズが一つのアルファベットに対応してることが推測できる. だとしてもいくつかのアルファベットが欠けているので完璧な対応表をここだけで得ることはできない.

以降50分に渡って、ロボットがひたすらポーズを取っていくので、対応する文字を列にして、何かしらの方法でバイナリにデコードすると PNG 画像になるのだろう.

ポーズとポーズとの間隔はほぼ、1秒であった. おそらく、ぴったり1秒になるように調整されてるのだと願い、フレームを切り出して、機械的に振り分けることにした. はじめは画像をピクセルのベクトルに変換して、コサイン類似度を取って、高かったら2つの画像は同じポーズを示している、、、、で分類することにした. ココらへんに関しては後述.

結局大事だったのは、とりあえず、ロボットの一つのポーズを一つの文字だと思って (それが実際には何の英字や数字に対応してるかは気にせず) 最初の100文字程度を手でアノテートしてみたこと.

ロボットの腕の形は、中心が固定されてぐるぐる廻る長い棒と、その両端に関節がある小さい棒の三本で構成される. 長い棒は、地面に対して、0度、45度、90度、135度の四通り. 小さい棒は、長い棒に対して、90度未満程度、右、左、または長い棒と重なった状態の三通り. 以上から、 4x3x3 で 36 通りありえる. これをラーメン屋でチームの皆に話した所、BASE36というのがあるらしい. 英字+数字で表現するらしい. しかし自分は36通りの内、35通りしか切り出したフレーム (ロボットのポーズの瞬間を取った画像) から発見できなかった (これについても後述). BASE36 なら 36 文字全てが出てこないのは怪しい.

フレームの切り出し

ポーズは1秒間隔で、動画は50分なので、ポーズ、すなわち読むべき文字は3000文字. 最悪、人間が全部読み取るのも覚悟しつつも、とりあえずの方針は、機械的にフレームを切り出して機械的に判別させることとした. 人が見るにしても、フレームの切り出しは必要. 何番目のポーズの文字は何々、という情報を共有するのに、動画を初めから睨んで、そのポーズが何番目かなんてカウントしたくないので.

最初、自分は次のように単純な方法でポーズ画像を得ることにした. あ、動画は YouTube にあるが、どうにかこうにかして手元に input.mp4 としてあるものとする.

# 動画 -> ポーズ
ffmpeg -ss 75.5 -i ./input.mp4 -f image2 -vcodec png -r 1 "./pose/%05d.png"

75.5秒を起点に、1秒に1枚、スクリーンショットを取って保存する. これはロボットがぴったり一秒ごとにポーズを取ってくれることを期待している. ついでに、画像全体だと無駄が多い. ほしいのはロボットの腕部分だけだし、ついでにいうとカラー画像である必要はない. HDD を圧迫するし.

for f in pose/*.png; do
    g=crop/${f#*/}
    convert -crop 400x400+520+20 -type GrayScale $f $g;
done

f:id:cympfh:20161211210810p:plain

こんな感じ. 最初の方はいいんだが、後半、なんだかロボットの動きが鈍くなってく気がする. 動きがたま〜に、遅いんだか、まだ腕を動かしてる途中のフレームを切り出してしまうことがある.

f:id:cympfh:20161211210925p:plain

躍動感がある. ちょっと腕がブレてるぐらいならいいが、実際と違うポーズに見える瞬間を切り取ってしまったことがあった. 先程、35通りのポーズを確認したと言ったがそれは嘘で、これが原因だった.

ちゃんとロボットが動きを止めてることを確認して、フレームを切り出さなければならなかったのだ. ここはチームメイトにタスクを投げたので私はやってないが、次のようなことをやってもらった.

  1. 全フレームを切り出す (動画は12fps)
  2. 隣接する2フレームの cos 類似度を取る
    • i 番目と i+1 番目のそれを k[i] とする
  3. 変数 i に初期値を与える
  4. i+12 の周辺 (そのプラスマイナス2程度) で k[j] が最大となる j を探す
  5. j 番目のフレームをポーズとして出力
  6. ij で更新 (i <- j)

+12 周辺を見るのは、やはり基本的にポーズの次のポーズは 1 秒後、すなわち 12 フレーム後であるはずというヒューリスティック.

これできれいなポーズ画像が 3000 枚手に入る.

自動識別

きれいなポーズ画像が 3000 枚、手に入り、それまでにやってたアノテーションは誤りを多く含むことがわかった. 先程、 36 種類の文字を表現できるのに 35 種類しか発見できなかったと述べたが、実は誤りで、35 どころか 32 種類しか無いことが発覚した. ここらへんで @autotaker1984 さんが chappe system なるものを見つけ、加えて BASE32 であることを推理したので話が一気に簡単になった.

いくつかすぐ気づく例外として、chappe system の "&" (アンパサンド) が SECCON TOWER の "J" である. あとあと、動画の最初のチュートリアルでは、次のポーズ、

f:id:cympfh:20161211210747p:plain

は "." (ピリオド) に対応しそうな雰囲気だったが、BASE32に "." などない. 本番のスタートもこのポーズからスタートしているが、途中で一切出てこないので、気にしない (存在しない) ことにした. ちなみに padding の "=" というつもりでもないらしい. 動画の最後は "A" で終わっているので.

で、さて、自動識別であるが、フレームの切り出しにも利用した画像のコサイン類似度は、まるで使い物にならないことは結構初めに気づいていたので (今回これがダメな理由は CTF SECCON TOWERに挑んでみました - WGGの活動log にある通りです. でももっと工夫すれば頑張りの余地はありそう)、MNIST と同じ要領で簡単なCNNで32に分類させることにした.

コード自体は全然なんということもなく、chainer でちゃちゃっと書いた.

import chainer
import chainer.functions as F
import chainer.links as L


class SecconTowerClassifier(chainer.Chain):

    def __init__(self):
        super().__init__(
            bn0=L.BatchNormalization(3),
            bn1=L.BatchNormalization(8),
            c1=L.Convolution2D(3, 8, 3),
            c2=L.Convolution2D(8, 32, 5, stride=2),
            c3=L.Convolution2D(32, 64, 5, stride=2),
            out=L.Linear(None, 32)
        )

    def forward(self, x, train=False):
        h = x
        h = F.average_pooling_2d(h, 3)
        h = self.bn0(h)
        h = F.dropout(h, 0.5, train=train)
        h = self.c1(h)
        h = self.bn1(h)
        h = self.c2(h)
        h = F.elu(h)
        h = self.c3(h)
        h = F.max_pooling_2d(h, 3)
        h = self.out(h)
        return h

    def __call__(self, x, t):
        h = self.forward(x, train=True)
        loss = F.softmax_cross_entropy(h, t)

        # Acc
        n = x.data.shape[0]
        _i = chainer.cuda.cupy.argmax(h.data, axis=1).reshape((n, ))
        acc = chainer.cuda.cupy.sum((_i == t.data)) / n

        chainer.report({'loss': loss, 'acc': acc}, self)
        return loss

学習も何十分何時間も回していない. 何と言っても学習データは自分一人で作っていたので、そんなに数が無くすぐに収束するので. 学習を回しながら学習データを増やしてって、ちょっと溜まったら学習をリスタートさせるというサイクルを30分位?繰り返していた.

以下、作ったデータセット. 行の頭がラベル (chappe system ならぬ seccon tower におけるポーズが表すシンボル) で、続く数字の列が、何番目のポーズであるか. 例えば 1 番目のポーズは "R". 2 番目は "F".

A 12 14 15 17 18 27 28 29 30 33 34 35 36 40 53 54 55 56 57 58 61 67 68 69 70 1137 1388
B 9 40 47 50 1520 1512 2427
C 23 63 88 2311 2594
D 1017 1032 2485 2469
E 4 24 49 1351 1348 1452 1386 2474 2452
F 2 37 60 698 703 2450 2407 2312
G 19 1040 402 1521 1517
H 52 71 1020 1665 1587 1387 2463 2421 2408
I 3 10 26 65 1015 1022 403 1952
J 91 1012 456 373 2025 1779
K 25 1005 1352 590 617 2835 2697 2655
L 77 1009 1029 1044 822 651 589 2974 2905 2263
M 42 79 1353 2252 2120 2042 1975 1903 1855 920
N 8 11 1025 1028 219 1156
O 89 1019 1003 1350 2253 1940 1924
P 1031 1042 400 1045 1273 1357 1930 2722
Q 39 1018 1033 2231 2324
R 1 6 90 999 1002 1034
S 21 22 1382 968 1065 1141 1207 1382
T 51 62 1041 1354 856 1875
U 13 20 64 66 82 94 1026 1027 1030 1035
V 48 1004 1036 1379 1362
W 31 38 78 1014 404 1108 1181 1330 1413 1522 1660 1960 2102 2175
X 1000 1010 1319 1672 1971 2864
Y 7 1021 1364 2264 2131 684 603 543
Z 1001 1013 1125 2266 303 412 494
2 32 76 855 2817 2546 2270 2198
3 81 1043 1380 1349 278 279 1446 1696
4 5 93 1016 1023 1363
5 1006 1039 1361 1356 401 405
6 1024 1383 2219 1570 1857 2333
7 72 73 74 75 80 95 96 97 98 530 522 256 788 1072 1088

見たら分かるように、「ディープラーニング」をするにはあまりにも事例数が足りない. 一応訓練事例において正解率 97% を超えてたことにはなった時点で学習を終了した.

たった 10 の文字に分類する MNIST ですら、100% の精度を出したという報告はない. すなわち多少の誤りは諦めるしかない. @autotaker1984 のアドバイスにより、機械学習の識別でポーズ画像をディレクトリに分けて、あとは人間の目でチェックすることにした. 基本的に分類はほぼ成功しており、人間がすべきコトは、多くの同じポーズの中に、別なポーズが混じっていないかを確認するだけなので、そんなに難しくはなかったし、誤りは 3000 ポーズ中、10 程度しかなかった.

f:id:cympfh:20161211213322p:plain

10程度誤ったと言ったが、それらは全て、UとV、QとM の取り違いであった. 次にそれぞれのポーズを示す.

U

f:id:cympfh:20161211213448p:plain

V

f:id:cympfh:20161211213507p:plain

Q

f:id:cympfh:20161211213524p:plain

M

f:id:cympfh:20161211213538p:plain

まあ、似てる. しょうがない. 人間の手で修正したあと、base32 列になおしてバイナリに直したところ、次の画像を得た.

f:id:cympfh:20161211213730p:plain

Macのプレビューでは強引に開けるものの、いまブログにアップロードしようとすると「未対応のファイル形式です」と怒られたし、明らかに最後の方、壊れてる. でもカメラでは読み取ることが出来た. 読み取るとフラグ及びスペシャルサンクスを得る. よかった.

明日も一日!!

f:id:cympfh:20161211214743j:plain

広告を非表示にする

Google Code Jam 2016 - Qualification Round

GCJ 2016 予選

解法

  • A: シミュレーション
  • B: 数える
  • C: 力技 (乱択)
  • D: 読んでない

A. Counting Sheep

0がINSOMNIAなのは自明. 1-2000で手元で実験. どれも最大 75step で終了するので、2000より大きな数字もみんなそんな感じで、短いステップで終了すると信じてシミュレーションする.

gets.to_i.times {|cx|
  n = gets.to_i
  if n == 0
    puts "Case ##{cx+1}: INSOMNIA"
  else
    memo = [false] * 10
    k=0
    i=1
    while k < 10 do
      (n*i).to_s.chars.each{|s|
        kc = s.ord - '0'.ord
        if memo[kc] == false
          memo[kc] = true
          k += 1
        end
      }
      if k == 10
        puts "Case ##{cx+1}: #{n*i}"
      end
      i += 1
    end
  end
}

B. Revenge of the Pancakes

連続した +- をひと塊に扱って良い. 例えば -+++--+- と同様に扱え、こちらだけを考える. ボトムが - で長さが n...-+-end_with_minus(n) ボトムが + で長さが n...+-+end_with_plus(n) と呼ぶ.

問題が求めるものを f とする.

でまあ、なんか適当に考察すると

  • f(end_with_plus(n)) = n-1
  • f(end_with_minus(n)) = n

である.

  • f(end_with_plus(n)) = f(end_with_minus(n-1))
    • ..-+ \rightarrow^* ..++
  • f(end_with_minus(n)) = f(end_with_plus(n-2)) + 2
    • ..-+- \rightarrow^* ..++- \rightarrow ..--- \rightarrow ..+++

みたいな感じ.

def nub(xs)
  ys = []
  if !xs.empty?
    for x in xs do
      ys << x if ys[-1] != x
    end
  end
  ys
end

gets.to_i.times {|cx|
  xs = nub gets.chomp.chars.map{|s| s == '+'}
  ans = xs.length
  ans -= 1 if xs[-1]
  puts "Case ##{cx+1}: #{ans}"
}

C. Coin Jam

smallは32桁、largeは64桁の二進数であって、最上位ビットと最下位ビットが1のものを、ランダムに生成して、素数かどうかをチェックした.

次は実際に用いた、1個の数を生成して、jam coin なら、求められる出力をするだけのものだけど、本当はよくない.

require 'prime'

N = 64

def powmod(a,k,m)
  return 1 if k == 0
  t = powmod(a,k/2,m)
  t = (t * t) % m
  t = (t * a) % m if k%2==1
  t
end

def test(n)
  return false if n<2
  return true if n<4
  return false if n%2==0
  d = n-1
  while d%2 == 0
    d /= 2
  end
  100.times {
    a = rand(n-1) + 1
    y = powmod(a, d, n)
    t = d
    while t != n-1 && y!=1 && y!=n-1
      y = (y * y) % n
      t *= 2
    end
    return false if y!=n-1 && (t%2==0)
  }
  true
end

def factor(x)
  i = 2
  while i * i <= x
    return i if x % i == 0
    i += 1
  end
  return 1
end

s = "1#{(1..(N-2)).map{|_|rand(2)==0?'0':'1'} * ''}1"
ok = true
evi = []
(2..10).each{|b|
  x = s.to_i(b)
  if test(x)
    ok = false
    exit 0
  end
  evi << factor(x)
}
if ok
  puts "#{s} #{evi * ' '}"
end

素数の判定はミラーラビン法を用いてるのに、因数を求めるのに、試し割りを行っているので、たまに、なかなか終わらないことがある. 上のコードをを main.rb として次を実行する.

: > out
for _ in `seq 500`; do
  timeout 2s ruby main.rb >> out
done

重複がないかをチェックして正しく欲しい個数が得られたのを確認したら、頭に Case #1: を付けて提出.

2-100 くらいで試し割りして、割り切れなかったら素数であると保守的に判定する. 合成数のときは因数も得られる.

smallで作った32bitを並べればいい. 因数もsmallでのそれを使える.

D. Fractiles

読んでない

No.355 数当てゲーム(2) - yukicoder

No.355 数当てゲーム(2) - yukicoder プロコン

Sat Apr 2 00:01:45 JST 2016

No.355 数当てゲーム(2) - yukicoder

いわゆるヒットアンドブローのAIを書くもの インタラクティブに結果を受け取るタイプの問題

この問題の註意すべき細かい点としては、

  1. 4桁は全て異なる
  2. 結果として返ってくる2つの数値は重ならない (たいていそうだけど)

難しくない解法

100回以内のトライで正答したい 私の解法は大きく2つのフェーズからなる

  1. 使われてる4文字をあてる
  2. 並び替える

並び替えが 24通りなので、4文字を当てるのを76回以内でやればok. ただ貪欲法でやればいい. 大雑把に言えば、各桁が10通りで、 4 \times 10 通り (4桁が全て異なる場合だけを使うこと) 試す. 詳細に言うと、返ってくる2つの値の和が「使われてる文字」の数なので、これについての貪欲法を行う.

4文字を当てられたら、もう24通り全部試すだけ

yukicoderのインタラクティブ系統は、ゲームが終わったらそれ以降にだらだら出力せずにさっさと終了しないとREだかTLEだかを食らう.

http://yukicoder.me/submissions/84671

def torai(a) # try
  puts a*' '
  STDOUT.flush
  gets.split.map(&:to_i)
end

a = [0,1,2,3]
n,m = torai(a)
exit 0 if n == 4
k = n+m

for i in 0..3 do
  for x in 0..9 do
    if not a.include?(x)
      b = a.clone
      b[i] = x
      n,m = torai(b)
      if n==4
        exit 0
      end
      if k < (n+m)
        k = n+m
        a = b
        break
      end
      if k > (n+m)
        break
      end
    end
  end
end

a.permutation(4) {|a,b,c,d|
  puts [a,b,c,d]*' '
  STDOUT.flush
  n,m=gets.split.map(&:to_i)
  if n==4
    exit 0
  end
}

D問題: トレジャーハント - AtCoder Beginner Contest 035 | AtCoder

プロコン

Sun Mar 27 00:37:32 JST 2016

ABC 035 - D問題

問題

枝に時間コストのある有向グラフが与えられる. ノードは 1 から N まであって、N は 1e5程度. ノード 1 からちょうど時間  T を掛けて枝を巡ってノード1に戻ってくることをする. ただし任意のノードでは0秒以上自由に滞在してよい. また各ノード i には 1 以上の滞在ポイント A_i があって、ノード i に時間 t だけ滞在したとき、滞在ポイントが t \times A_i だけ溜まって加算される. これの合計を最大化したい.

解法

いつも滞在時間をゼロにするなら、ただのパスを巡るだけの問題である. 二箇所以上に滞在するのは無駄だと分かる. それは例えば異なる二箇所に注目して

 A_i t_i + A_j t_j \leq \max(A_i,A_j) \cdot (t_i + t_j)

ということ. もちろんゼロ箇所に滞在するというのはおかしい. スタート地点でずっと滞在すれば少なくとも 1 より大きな滞在ポイントが得られるから.

以上から滞在箇所はちょうど 1 つである. ノード u だとする.

1 \rightarrow uu \rightarrow 1 を巡る最短時間を計算して、残り時間を一杯、ノード u で滞在したときの滞在ポイントを P_u とする. もちろん巡るだけで時間が足りない場合もあるのでそこは適当に処理. で、 \max_u P_u が答え.

一頂点から全頂点まで (1 \rightarrow u) の最短時間は、ダイクストラ法による. 一番素朴なダイクストラ { O(V^{2}) } で、これだと、今は遅い. 優先度付きキュー (あるいは二分ヒープ) を使うことで、O((E+V) \log V) になる. 問題の制約をよく見ると、E のサイズも 1e5 程度と制限されてるので、こちらで行けるのだと想定が出来る.

帰り際の時間を計算するために、「全頂点から一頂点」(u \rightarrow 1) の最短時間が必要であるが、本当に全頂点からダイクストラをすると頂点の自乗以上の時間が必要なので遅い. しかしゴールは決まってるのだから、逆辺を辿るダイクストラだと思えば良いだけ.

参考になるであろうリンク

解答

本質的でない所

入力を受け取る部分を自前で書いてたんだけど、それがおっそくて、 バッファなんてキューにすべきだと前から分かってたはずなのに調べるのを忘れててただのベクターにしてた (pop O(n) かけてた) のが原因でずっとTLEしてた. Vec の確保が遅いのか?と悩んでたけど、これは普通にヒープに領域確保するので遅くない.