Hatena::ブログ(Diary)

まめめも このページをアンテナに追加 RSSフィード

2017-02-11

[][][] どうぶつしょうぎ名人

どうぶつしょうぎ AI を作りました。絶対に勝てません。無力感を味わってください。

ref: http://mame.github.io/dobutsu-shogi-master

どうぶつしょうぎとは

3 マス x 4 マスの単純化された将棋です。ライオン(王相当)、ぞう(1 マスしか進めない角行)、キリン(1 マスしか進めない飛車)、ひよこ(歩相当、にわとりに成ったら金相当)の 4 種類の駒を動かして、相手のライオンを取るか、トライ(ライオンを一番奥の行まで運ぶ、ただし直後に取られる場合はだめ)に成功すれば勝ちです。詳しくは Wikipedia の記事を見てください。

どうぶつしょうぎは後手必勝であることが知られています(研究報告)。つまり、後手が正しくプレイする限り、先手は絶対に勝てません。どうぶつしょうぎ名人は常に正しくプレイするので、先手のあなたは絶対に勝てません。

なんで作ったのか

将棋の AI が何かと話題になる近今ですが、ぼくはトッププロに勝てるかどうかにはあんまり興味がありません。自分より強いことは確実だし。

そんなことより、先手必勝なのか後手必勝なのかという事実の方が面白いですよね。どうぶつしょうぎはすでに完全解析されていたので、それを体感してみたいと思ったので作りました。やってみると、素人の直感では不利そうな感じの手が一番生き延びる手だったりして、意外に楽しかったです。

(あと、いらすとや人工知能イラストを使ってみたかったというのも)

実装の概要

AI とは名ばかりで、後手盤面ごとに指すべき手を事前計算してあります。「なーんだ」という感じですが、単純やると 2 億個の盤面を覚えないといけない。単純に作ると、手の選択のたびにサーバに問い合わせることになりますが、それはなんとなく嫌だった(ネットワークがなくても動く方がかっこよく感じる)ので、ちょっと工夫してあります。

指すべき手の事前計算

まず、前述の研究報告の解析を再現しました。初期盤面から到達可能な盤面を全列挙します。それから、末端局面から逆にたどって(後退解析)、各盤面の深さ(そこから終局までにかかる最短手数)を求めました。

8 年前の研究報告では盤面列挙に 19 分、後退解析に 5.5 時間かかったそうですが、ちょっとした工夫*1で、ノート PC でもそれぞれ 5 分、15 分弱でできました。盤面数などが論文と一致したので、バグってはないと思います。*2

最短勝利手順データベースの生成

初期盤面から到達可能な全盤面の深さが決まりました。この時点では、後手必勝の盤面だけで約 2 億個あります*3が、これを全部データベースに入れる必要はありません。というのも、後手(AI)は常に最善手(最短で終局に向かう手)を選ぶので、理論上到達可能でも実際には到達しなくなる盤面が出てくるからです。

ということで、「先手は任意の手を選ぶ、後手は最善手を選ぶ」というルールで初期盤面から辿りなおして、覚えるべき盤面を絞り込んでいきます。*4

このとき、最善手が複数ある(どっちを選んでも終局までの手数が同じ)場合があります。どれを選んでもいいのですが、覚える盤面数に影響があります。覚える盤面数を最小化する最善手を選ぶのは、単純な 0-1 整数計画問題に直せます*5。これは NP 困難ですが、人類の英知を結集したソルバ(CPLEX 殿とか Gurobi 殿とか)を使えば、わりとよい近似解が得られます。

CPLEX 自体は有償なので、CPLEX をオンラインで無償で使わせてくれる NEOS サーバを使います。投稿用の LP ファイルを生成しました。が、NEOS サーバは問題サイズが 16 MB までという制限があったので、LP ファイルゴルフをしました*6。ギリギリ 16 MB を下回ることができたので投稿してみると、CPLEX はすぐにメモリ不足で止まるので使えない子だったのですが、SCIP というソルバがそこそこの近似解を出してくれました。

これを元にデータベースを作ったら、およそ 10 万盤面程度を覚えればいいことになりました。2 億件が 10 万件に。

データベースの圧縮

10 万件ならバイナリで 1 MB 程度なのでブラウザでも扱えます。ただ、あんまりかっこよくない気がしたので、完全ハッシュ関数を実装しました(有名な論文)。これでバイナリで 200 KB 程度。

このくらいならメモリに載せてもいいけど、通信量的はもうちょっと頑張りたい(あとできれば ajax 使いたくない)と思ったので、Range coder で圧縮しつつテキスト形式にしました*7。これで、テキストで 170 KB 程度になりました。あとはこの文字列JavaScript に埋め込んで、実行時に解凍するだけ。

実装に使った言語

主に事前計算と Web クライアントの開発なので、どちらも Ruby には向いていません。せっかくの機会なので、使ったことがない言語を使ってみるようにしました。

Rust

事前計算は明らかに実行速度が重要だったので、Rust で書くことにしました。が、型システムが煩わしくてしょうがないので、一旦 C で書いて動作確認してから Rust に移植しました。そして、当然ながら C より遅いという*8。うーん、不毛。

LP ファイルゴルフの方も Rust でやりたかったのですが、どうも Rust でグラフ構造を扱うのは鬼門なようで*9、後半はあきらめて Ruby で書きました。

Rust 、どうなんでしょうね。(1) 実行速度重要、(2) メモリ管理重要、(3) 高度なアルゴリズムは非重要*10、なユースケースには向いているのかな。でも、OCaml に比べるとたくさんの人がすでに使っているようなので、みんな賢いなあすごいなあ、という印象。

TypeScript

クライアント側の実装には TypeScript を使ってみました。JavaScript のスーパーセットということで、いろいろ妥協の産物という感じです。型システムも適当なので、「通ったら安心」というたぐいのものではないです*11。それでも、JavaScript を直接使うよりはだいぶ幸せでした。

ただ、型チェックに数秒程度もかかるのはつらい。vim が保存時に毎回固まる。UI のための JavaScript はちょっとした変更を繰り返すものなので、忍耐力が必要です。コードサイズに応じて遅くなっていく(いまは 1000 行弱)ので、大規模なものを書くのは厳しいかも。

なお、npm を中心としたエコシステムは立派だなあと思いました(小並感)。流行ってるようだったので webpack を使ってみましたが、一年後にはどうなっているのでしょうか。

まとめ

どうぶつしょうぎが後手必勝であることを実感できるデモでした。将棋 AI が人間に勝つかどうかとかいう世俗的なことより、オセロが後手必勝なのかどうかのような理論上のことにみんな興味を持つといいなと思います。

今後の課題としては、人間が後手を取ったときでも指してくれるようにしたいなと思っています。覚えないといけない範囲が一気に広がるので、サーバ問い合わせが必要なんですよね。サーバ持ってないのですぐにはできない。

*1:後退解析では、深さ n の盤面から深さ n+1 の盤面を特定していきます。具体的には、単純に深さ n の盤面から直前の盤面を逆計算するアプローチと、深さ未決定の盤面のうちで深さ n の盤面に進めるものを絞り込むアプローチがあります。深さ n の盤面数と、深さ未決定の盤面数を比べて、早そうなアプローチを選択することで、大幅に高速化できました。

*2:実はバグ再現するのに結構手間取ったんですが、こういうのって初めて研究する人はどうやって解析の正しさに確信を持つんだろう。

*3:左右反転して同一になる盤面は含んでいません。

*4:あと、深さ 3 以下の盤面は覚えないことにしました。JavaScript でも実行時に一瞬で探索できる深さなので。

*5:ある盤面 x を覚えるかどうかを変数 x で表すことにします(x は 0 または 1)。後手盤面 w から先手盤面 b1, b2, ..., bn に遷移可能なとき、b1+b2+...+bn >= w という制約を与えます(w を覚えるなら b1 から bn のどれかを覚えなくてはならない)。また、先手盤面 b から後手盤面 w1, w2, ..., wn に遷移可能なとき、w1+w2+...+wn >= n*b という制約を与えます(b を覚えるなら w1 から wn のすべてを覚えなくてはならない)。これらの制約の下で、すべての後手盤面 w の合計(Σw)を目的関数とし、これを最小化する変数割当を求めます。

*6:やったのは、(0) 簡単な実験で明らかに望みがなさそうな枝をアドホックに刈る、(1) 覚えることが確定している盤面に関する制約を除去する、(2) 目的関数に寄与しない制約を除去する、(3) 一本道になっている手順をマージする、(4) 変数名をゴルフ的に圧縮する。簡単なグラフ処理と文字列処理です。

*7:表示可能文字 95 文字からダブルクォートとバックスラッシュを除いた 93 進数で出力した。

*8:主に重いのは HashSet の読み書きでした。「デフォルトが SipHash だから遅い」と言うのはよく見かけるのですが、FnvHash にしても遅かった。HashSet の実装自体も遅いんじゃないだろうか。キーを u64 限定として、khash.h を参考に再実装したら C の 2 倍くらいになりました。その後もこまごま調整したら 1.5 倍くらいにはなったようです。

*9unsafe でない双方向リンクリストが話題になるくらい。

*10:といっても今どきグラフも気軽に扱えないのでは、OSブラウザのようなシステムプログラミングにも厳しいのではないか。そのへんはとても賢い人が書いたライブラリを使う、というのでどうにかなる?

*11:この点 Rust は、型システムを通れば安心、かと思いきや、型システムを通すために参照を避けて配列インデックス番号にするインセンティブが働くので、index out of bounds 遭遇率が高まるという。「それはそうするお前が悪い」という声が聞こえてきそうですが、グラフ構造の実装では「アリーナ」とかいってまさに同様の手法ノードを集めたでっかい配列を用意して、参照のかわりにインデックス番号を使う)を提案している人が結構いるようですよ。ポインタがない N88-BASIC みたいな世界。

2017-01-18

[] 『Ruby で学ぶ Ruby』非公式あとがき

ref: http://ascii.jp/elem/000/001/230/1230449/

RubyRuby を作りながら Ruby を学ぼう!」という ascii.jp の連載、おかげさまでほぼ予定通りに無事に終わりました。執筆の経緯を書いておきます。

昨年の 6 月ごろ、「抽象によるソフトウェア設計」や「型システム入門」のときにおせわになった編集者の鹿野さんに声をかけて頂きました。「ふつうの Ruby 入門はもうたくさんあるので、ちょっと変わった Ruby 入門を書けないか」という話でした。

それを聞いた瞬間、「Ruby インタプリタの開発を通して Ruby を学ぶ」という構想が湧きました。Ruby は主に Web やテキスト処理を対象としているので、言語処理系や記号処理を題材にした入門は目新しそうだし、なによりそういうのに興味を持つ Ruby ユーザがもっと増えてほしい。

「○○言語で○○言語のインタプリタを作る入門」は、LispML ではわりと普通のことです*1。「インタプリタの実装」というと何やら難しそうですが、言語のサブセットの切り出しさえうまくやればそんなに難しくないのです。

とはいえ、さすがにプログラミング言語をまったく知らない人向けの題材としては重すぎるかな?という不安はあったので*2、まずは自分でインタプリタを書いてみました。言語のサブセットの取り方を試行錯誤しながらでしたが、数時間くらい、ソースコードにしてたった 100 行強でブートストラップできたので、大丈夫な気がしてきました。個人的に盛り上がってきたので、そこから 1 週間で全 8 回(当時)の原稿をすべて書き上げました(なおこの時点では連載は決まっていない)。

それから無事に 1 か月後くらいに連載が決まり、9 月中旬に連載開始となりました。連載は隔週で、すでに書き上げた原稿を鹿野さんが膨らませ、@hirekoke さんが挿絵を入れて出す、自分はそれを見守る、という体制。のはずでしたが、説明方法や説明順序を調整したのでそんなに楽ではありませんでした。ちょっと説明方法や構文木を変えただけのつもりでも、後から整合性を取るのが苦しくなるとか。関数の回を前後編に分けることになったので当初より全 9 回になりましたが、それでも基本的には予定通りに進むことができました。

少し心残りなのは、字句構文解析を完全に省いてしまったところです。言語処理系の教科書と言うと、まずは字句構文解析の小難しくて面白くない説明(※個人の感想です)がダラダラ続くんですよね。そこより先に言語処理系のおもしろさがあるのに、多くの人が脱落してしまうのはもったいないと思っていました。ただ、字句構文解析がないとオレオレ言語の開発はできないし、ブートストラップも完全とは言い難い。まあ、この連載は言語処理系開発の入門ではなく、あくまで Ruby 入門の題材として言語処理系を扱うということで、妥協しました。いちおう MinRuby の再帰下降解析のパーサ(これだけで 100 行強)は書いたので、そのうちどこかで書きたい。

ということで、『Ruby で学ぶ Ruby』を楽しんで頂けたなら幸いです。公開が停止するわけではないのでまだ読んでないなら今からでもぜひ。

あと、「これで Ruby はだいたいわかった!」という気になったら、拙著もどうぞあわせて読んでください。Ruby プログラムのサンプルがいっぱい載っています。

あなたの知らない超絶技巧プログラミングの世界
遠藤 侑介
技術評論社
売り上げランキング: 3,000

*1:むしろ自分の中で Lは「LispLisp インタプリタを作る入門」のための専用言語くらいの位置づけです

*2:あと、いつのまにか鹿野さんが ASCII.jp に企画提案していたので。

2016-12-22

ELVM を使った multiquine

言語間を自由に行き交うことができる Quine の集合のことを multiquine と言います。例えば mq.rb と mq.py が multiquine であるとは、

  • ruby mq.rb rb と実行すると mq.rb が出てくる(普通の Quine)
  • python mq.py py と実行すると mq.py が出てくる(普通の Quine)
  • ruby mq.rb py と実行すると mq.py が出てきて、逆に python mq.py rb と実行すると mq.rb が出てくる(相互に出力する)

という感じです。5 言語で普通に書かれた multiquine の図がわかりやすいでしょう。ぼくの本でもちょっと言及されています。

あなたの知らない超絶技巧プログラミングの世界
遠藤 侑介
技術評論社
売り上げランキング: 3,000

なお、拙作の Quine リレーウロボロス Quine とも)とは別のものです。Quine リレーは言語の進む方向が固定の輪ですが、multiquine は自由に行き来できるという自由度があります。

multiquine の難しさ

実のところ、「普通」の言語に限定すれば、multiquine はそんなに難しくありません(Quine リレーよりは難しいですが)。特に、「C 風の文字列リテラルがある言語」に限れば、極端に簡単になります(25 言語の例)。

しかし、この言語の中に Brainfuck や Lazy K が入ったとしたら、極端に難しくなります。Quine 自体が難しいわけではありません。Brainfuck で他 N-1 言語のコード生成器を書かなきゃならない、というところが辛いです。言語を増やしていくごとに、O(N^2) で実装タスクが増えていきます。

multiquine を効率的に実装する方法

これを解決する構想は昔からありました。こんなのです。

  1. 中間言語を設計する
  2. 中間言語で、Quine を書く
  3. 中間言語で、中間言語から各言語へのコード生成器を書く
  4. 各言語で、中間言語処理系を書く

これらを組み合わせれば multiquine が作れます。2 で Quine (in 中間言語) を生成し、それを 3 で好きな言語に吐き出します。これらはすべて 4 の上で動かします。吐き出す先を実行時に変えれば、multiquine になります。

この方法の良い所は、言語を追加したいと思ったときに必要なのが

だけとなることです。つまり、言語同士が独立になるので、N 言語 multiquine の実装量が O(N) になります。

ただ、中間言語の設計が辛くて実現してませんでした。中間言語を簡素にするとコード生成器の実装が辛くなり、中間言語を複雑にすると処理系の実装が辛くなるというバランスが取りきれなかった。

ELVM の登場

などとグダグダ言っていたら、shinh さんが ELVM とかいうものを爆誕させてくれました。わーい。上の 1 から 4 のタスクのうち 2 以外が黙っていたらできてしまった格好です。

ためしてみた

ということで、2 の部分だけ作って multiquine を作ってみました。

https://gist.github.com/mame/53fb5cf7b448b3249270ea771ef89655

詳しくはコメントを見てもらいたいですが、次のような感じで動きました。

$ ruby mq-gen.rb
$ gcc -o mq mq.c

$ echo c | ./mq > mq2.c
$ diff -s mq.c mq2.c
Files mq.c and mq2.c are identical

$ echo rb | ./mq > mq.rb
$ echo rb | ruby mq.rb > mq2.rb
$ diff -s mq.rb mq2.rb
Files mq.rb and mq2.rb are identical

$ echo c | ruby mq.rb > mq2.c
$ diff -s mq.c mq2.c
Files mq.c and mq2.c are identical

一応 bf も動くはずなのですが、とんでもなく遅いので動作は未確認。うーん、できたはできた(と思う)んだけど、現実的には Brainfuck と Lazy K の multiquine は無理そうだし(ていうかよく見たら ELVM が Lazy K をサポートしてなかった)、すっきりしないので未完。

2016-11-17

[] 二分探索サンプルコード集(コピペ用)

二分探索は、感覚的なわかりやすさに反してバグが入りやすいことで有名なアルゴリズムです。20 の教科書のうち 15 でバグっていたという報告もあるそうです。

実際、自分も書くたびにバグに苦しんできました。変な値を返すだけでなく、out of bounds アクセスや無限ループもよく起きます。一旦動いたと思っても、後になってバグ発症することも多く、たちが悪いです。

そこで、きちんとテストした二分探索のサンプルコードを自分のコピペ用に作ってみました。

動作仕様 (境界探索版)

ソートした配列 a に対して、「値が c 以上になる範囲のうちの一番左のインデックス」を返す関数 bsearch_min を書きます。

a = [0, 1, 1, 1, 2, 2, 2, 3]
p bsearch_min(a, 2) #=> 4

値が c 以上になる値がない場合は a.size を返します。空配列の場合は 0 を返します。

p bsearch_min(a, 4)  #=> 8 (a.size と同じ)
p bsearch_min([], 0) #=> 0 (a.size と同じ)

よって、bsearch_min の返り値は 0 以上 a.size 以下です。

なお、「値が c 未満になる範囲のうちの一番右のインデックス」が欲しくなることもありますが、この場合は bsearch_min の返り値から 1 を引けば OK です(その場合の返り値は必然的に -1 以上 a.size 未満になります)。どちらかというと、「左端」と「右端」のどちらが欲しいのかを混乱しないことが重要です。

区間を使う bsearch_min

def bsearch_min(a, c)
  l, r = 0, a.size - 1
  while l <= r
    m = l + (r - l) / 2
    if a[m] < c
      l = m + 1
    else
      r = m - 1
    end
  end
  l
end
  • l と r の扱いが対称的で美しい。
  • 終了時、l - 1 == r となっている。よって、「左端」ではなく「右端」が欲しくなったときは全く同じコードで r を使えばよい。
  • 除算の丸めに対してロバスト。つまり m = l + (r - l + 1) / 2 としても正常に動作する。
  • l = m + 1 と r = m - 1 から、イテレーションのたびに範囲が狭くなることが見た目に明らか。二分探索は無限ループバグを入れやすいので重要。
  • m が求めるインデックスだった場合にも r = m - 1 を実行して大丈夫なのか不安になる。つまり、求めているインデックスを i としたとき、i が (l..r) の範囲外になることがある。たとえば bsearch_min([1, 2, 3], 2) を実行すると、求めるインデックスは 1 なのに、(l..r) は (0..2) → (0..0) になるので、1 は範囲外になる。その後で l が r を追い越して (l..r) = (1..0) になり、l を返すので、バグではない。

半開区間を使う bsearch_min

def bsearch_min(a, c)
  l, r = 0, a.size # 変更点 (1)
  while l < r # 変更点 (2)
    m = l + (r - l) / 2
    if a[m] < c
      l = m + 1
    else
      r = m # 変更点 (3)
    end
  end
  l
end
  • 違いは、(1) r = a.size - 1 から r = a.size になった、(2) ループ条件が l <= r から l < r になった、(3) r = m - 1 から r = m になった、の 3 点。
  • l と r の扱いが対称的でない。半開区間だから当然だけど。
  • 終了時に l == r になっている。混乱しないという意味では利点? ただし、「右端」が欲しくなったら l - 1 を計算する必要がある。
  • 除算の丸めは floor でないといけない。(半開区間なので、すでに r に 1 足されてるようなもの)
  • r = m なので、無限ループバグが怖くなる。ループ中は l < r なので、除算が floor なら必ず m < r になる、よって範囲は確実に狭まる。というように考えれば大丈夫だとわかるんだけど、二分探索は脳力を使うところが多いので疲れる。
  • 求めているインデックスは必ず (l..r) の範囲にある。ただし、半開区間を閉区間として解釈すれば、という話なので余計にややこしい気もする。

動作仕様 (有無判定版)

ソートした配列 a に対して、「値 c を含むかどうか、含む場合はそのインデックス」を返す関数 bsearch_any を書きます。

a = [0, 1, 1, 1, 2, 2, 2, 3]
p bsearch_any(a,  2) #=> 4 or 5 or 6
p bsearch_any(a, -1) #=> nil
p bsearch_any(a,  4) #=> nil

該当する値が複数ある場合は、どれかのインデックスを返します。

区間を使う bsearch_any

def bsearch_any(a, c)
  l, r = 0, a.size - 1
  while l <= r
    m = l + (r - l) / 2
    return m if a[m] == c # c と等しい要素を見つけたら return
    if a[m] < c
      l = m + 1
    else
      r = m - 1
    end
  end
  nil # 見つからなかった
end

境界探索版との違いは、return 文を入れたことと、最後に nil を返すところだけです。

半開区間を使う bsearch_any

def bsearch_min(a, c)
  l, r = 0, a.size
  while l < r
    m = l + (r - l) / 2
    return m if a[m] == c # c と等しい要素を見つけたら return
    if a[m] < c
      l = m + 1
    else
      r = m
    end
  end
  nil # 見つからなかった
end

こちらも同様。

講評

「閉区間より半開区間を使う方がプログラムが綺麗になることが多い」という経験則を持ってる人は多いと思いますが、こと二分探索に関しては閉区間に分があるように思いました。

二分探索というと、境界探索より有無判定を指すことが多いようです。が、個人的には二分探索を使いたい場合には境界探索をしたいことが多い気がする。特に、「複数ある場合はどれでもいい」というケースは出会った記憶がない(重複がないとわかってる場合に使う?)。あと、境界探索版を有無判定版にするのはミスしにくいんだけど、逆は脳力を要する(a[m] == c の場合に l と r のどちらを変えるべきか、最終的な返り値は l と r のどちらか)ので、やはり境界探索版をベースだと思っておいたほうが良いと思う。

なお、Ruby なら組み込みの Array#bsearch や Range#bsearch を使うべきです。この記事はあくまで、何かやむを得ない事情で自力実装が必要になったとき用の備忘録です。

以下、テストに使ったコード。隣同士の差が 0 から 2 になる配列を長さ 0 から 8 まで網羅的に試しています。

def bsearch_min_closed(a, c)
  l, r = 0, a.size - 1
  while l <= r
    m = l + (r - l) / 2
    if a[m] < c
      l = m + 1
    else
      r = m - 1
    end
  end
  l
end

def bsearch_min_half_open(a, c)
  l, r = 0, a.size
  while l < r
    m = l + (r - l) / 2
    if a[m] < c
      l = m + 1
    else
      r = m
    end
  end
  l
end

def bsearch_any_closed(a, c)
  l, r = 0, a.size - 1
  while l <= r
    m = l + (r - l) / 2
    return m if a[m] == c
    if a[m] < c
      l = m + 1
    else
      r = m - 1
    end
  end
  nil
end

def bsearch_any_half_open(a, c)
  l, r = 0, a.size
  while l < r
    m = l + (r - l) / 2
    return m if a[m] == c
    if a[m] < c
      l = m + 1
    else
      r = m
    end
  end
  nil
end

0.upto(8) do |nn|
  [0, 1, 2].repeated_permutation(nn) do |diff|
    next if diff.last != 0
    a = []
    n = 0
    diff.each do |d|
      a << n
      n += d
    end
    p a
    -2.upto((a.max || 0) + 2) do |c|
      answer = a.find_index {|v| v >= c } || a.size
      raise if bsearch_min_closed(a, c) != answer
      raise if bsearch_min_half_open(a, c) != answer
      if a.include?(c)
        raise if a[bsearch_any_closed(a, c)] != c
        raise if a[bsearch_any_half_open(a, c)] != c
      else
        raise if bsearch_any_closed(a, c) != nil
        raise if bsearch_any_half_open(a, c) != nil
      end
    end
  end
end

2016-09-20

[] Quine Tweet: 自分自身へのリンクを持つ再帰ツイート

「このツイートはありません」となっていますが、URL をクリックすれば自分自身に飛べます。

以下、このツイートが生まれるまでの経緯を長々と書きます。

問題設定

そのツイート自身の URL を埋め込んだツイートを作ります。ツイートURLツイートをした後でないと決まらないし、ツイート文面を後から更新する手段はない(と思う)ので、単純ですが意外に難しい問題です。

調査

ご存知のように、現在のツイートURL は次のような形式です。

https://twitter.com/<username>/status/<id>

username はそのままなので、id を事前に予測できれば解決です。*1

調べてみるとこの id は、snowflake という分散ナンバリングシステムで決められているようでした。いくつかの解説記事によると、id は以下のような 64 ビット整数であるようです。

+--------------------+--------------------+-------------------+
| timestamp (42 bit) | worker-id (10 bit) | sequence (12 bit) |
+--------------------+--------------------+-------------------+

それぞれの意味は以下の通り。細かいことは snowflake のソースコード*2を見て確かめました。

  • sequence: 同じミリ秒枠内での衝突を回避するためのシーケンス番号(ミリ秒ごとに 0 リセット)
  • worker-id: この id を発行したサーバ固有の番号 *3
  • timestamp: System.currentTimeMillis() - 1288834974657L の値。(2010-11-04 10:42:54 頃からの経過ミリ秒)

上位ビットが timestamp なので、この番号はおおよそ時間順に増えていきます。

アプローチ

それぞれの値を予測して id を作り、ツイートを投げてみて、外れたらツイ消し。Quine ツイートに成功するまで、延々とこれを続けます。各ツイート試行は独立と仮定すれば、典型的なベルヌーイ試行ですね。

観察と見積

TL に流れているツイートをいくつか集めて、それぞれの値の傾向を観察して、成功までにかかりそうな時間を見積もりました。

  • sequence はミリ秒ごとにリセットされるので、0 と予想するのが鉄板です。実際、TL に流れているツイートの sequence をいくつか拾ってみると 0 が多めでした。1 日にツイッターに流れる全ツイート数は数億で、1 日は 8640 万ミリ秒なので、時間帯の偏りを考えればこんなものでしょう。
  • worker-id は原理的には 2^10 = 1024 通りの値を取りえます。いくつかのツイートを観察しても特に傾向はつかめませんでした。
  • timestamp は、なんとなく ±500 ミリ秒くらいの精度で当てられるんじゃないかなーと考えました。

これらの観察から、値が一致する確率(ヒット率と呼ぶことにします)をそれぞれ 50 % 、0.1 % 、0.1 % と仮定しました。それぞれの値が一致する確率は独立と仮定して、Quine ツイートが生まれる確率は 50 % × 0.1 % × 0.1 % = 0.00005 % 、期待値で言うと 200 万回のツイートで 1 回成功する計算になります。

ツイッター API のレートリミットを調べると、1 時間に 100 ツイート程度が許されるそうです。少し余裕を見て、40 秒に 1 回ツイートすることにしました。200 万回のツイートをするには 3 年弱かかる計算になります。

事前見積
sequence ヒット率50 %
worker-id ヒット率0.1 %
timestamp ヒット率0.1 %
必要なツイート数期待値2M 個
所要時間の見込み 3 年

心が折れそうになりましたが、3 年がかりの Quine というのもロマンがあっていいだろう*4、と前向きに考え、とりあえずやってみることにしました。

簡易版での試行

専用の Twitter アカウントを作成し、次のような適当な予測で挑戦しました。

  • sequence は 0 固定。
  • worker-id は「前回の失敗ツイートの worker-id をそのまま送る」という戦略。ナンバリングサーバが常時 1024 台起動してはなさそうですし、ロードバランサの振り分け先にも偏りあるんじゃないかと期待。
  • timestamp は単純に、前回の失敗ツイートから 40,000(40 秒)を足して作ります。ただし、ローカルの時計と前回の失敗ツイートの timestamp のズレを見て、ツイート発射タイミングは調整します。

これで半日走らせてみましたが、まあ、当たりませんでした。

失敗データの分析

試行によって 1000 ツイート分くらいの失敗データが溜まったので、それぞれの値のヒット率を評価してみました。

事前見積簡易版
sequence ヒット率50 % 80 %
worker-id ヒット率0.1 % 7.0 %
timestamp ヒット率0.1 % 0.05 %
必要なツイート数期待値2M 個 35k 個
所要時間の見込み 3 年 17 日

worker-id は予想よりもかなり当てやすいことがわかりました。

timestamp は、1000 ツイート程度では 1 回もヒットしませんでした。事前見積から言っても、1000 ツイートで timestamp がヒットする期待値は 1 なので、ヒットなし自体は想定範囲です。しかし、誤差分布を見てみると ±1500 ミリ秒くらいで広がっていて、予想よりも厳しそうです。誤差分布をカーネル密度推定してヒット率を見積もったところ、0.05 % でした。ネットワーク越しだとこんなものか。

しかし worker-id のヒット率がだいぶ楽観視できるようになったので、所要時間の期待値を計算しなおすと、約 17 日になりました。3 年に比べたら全然行けます。ロマンはなくなりましたが。

改良版での挑戦

17 日なら待ってもいいんですが、せっかくなので予測方式を改良しました。

  • sequence は変わらず 0 固定。
  • worker-id は、「直近 5 つの失敗ツイートの worker-id を多数決して選ぶ」としました。*5
  • timestamp のタイミング補正に PID 制御を導入しました。

これでヒット率を見てみました。(2 日ほど走らせた時点)

事前見積簡易版改良版
sequence ヒット率50 % 80 % 75 %
worker-id ヒット率0.1 % 7.0 % 9.8 %
timestamp ヒット率0.1 % 0.05 % 0.08 %
必要なツイート数期待値2M 個 35k 個 15k 個
所要時間の見込み 3 年 17 日 8 日

sequence が若干悪化しましたが、簡易版でデータ採取したときは Twitter が混雑していない時間帯だったのかも。(そういうときは sequence の衝突が生じにくい)

とにかく、これで所要時間の期待値は約 8 日に。そこでちょうど帰省するタイミングになったので、モニタリングの仕組みだけ作ってそのまま放置しました。

結果

簡易版の実験を 9 月 13 日にやって、改良版を 9 月 14 日の 0 時ごろから改良版の実行を開始しました。9 月 20 日の朝 5 時ごろ、14377 ツイート目にして、ついに Quine に成功しました。苦節 6 日と 5 時間。だいたい予想通りですね。

正直、いろいろ不安でした。せっかく成功したのにスクリプトバグでツイ消ししてしまわないか*6とか、Twitter 側で完全に recursive なツイートはエラー扱いにするような処理が入っていないかとか。「開始から 5 日経ってるから、そろそろ当たってもおかしくない……」みたいな典型的なギャンブラーの誤謬に陥ったり。実際にうまくいくとホッとしました。この不安、3 年間は耐えられなかった気がする。

関連研究

やり始めた後で気づいたんですが、ネタ自体は既出でした。ショック。

これは 2009 年のツイートです。当時の Twitter では、id がただの連番で、一定間隔でツイートを投げれば番号がおよそ 200 増える(作者による解説の図を見ると、あんまりブレてない)ので、今よりだいぶ難易度が低かったようです。ミリ秒当てしなくていいのは大きい。

現在のナンバリングシステムになってからのものとしては、次のツイートがありました。

ただしこれはチートという噂です。TinyURL を作りかけの状態でツイートし、そのツイートURLTinyURL を完成させる、という手順でできるそうです。

まあ今より簡単だろうがチートだろうが既出ネタは既出ネタなんですが、楽しかったのでよいことにします。

今後の課題

もともと作りたかったのは「自分自身を埋め込んだツイート」だったのですが、残念ながら「このツイートはありません」となってしまいました。ツイート作成時点(自分自身がまだ作成されていない)でリンク先をフェッチして記録するようなので、当たり前ですね。普通の Twitter card のリンクなら 1 週間程度で再クロールしてくれるらしいですが、ツイートのリンクは Twitter card とは別の仕組みで埋め込まれているっぽいので、クロールし直してくれない予感がします*7。残念。何か手はあるかなあ。

予測的な改良の余地は 2 つ。まず、ツイート発射スクリプトRuby なので、発射タイミング自体がミリ秒単位では制御できていません。リアルタイム OS でもっときちんと制御して発射すれば、クライアント側のブレが減って timestamp のヒット率が上がる可能性があります(が、ネットワークTwitter サーバのブレは消せないので、大きく改善することはないと思っている)。それから worker-id は、プロダクションレベルのサービスやロードバランサの知識を持っている人が考えれば、もっと賢い予測方法を思いつくのかも知れません。

他に作りたいのは、相互再帰的なツイートのペアです。といっても同じような難易度で作れるはず(所要時間は倍になる)。今後も Quine Tweet の採掘を続けるためには、自宅 PC ではつらいので VPS などを借りたいところです。が、このためにお金は払いたくないなあ。。。*8

まとめ

Quine を作るには、データサイエンスや制御理論のちょっとした知識が役に立つこともあります*9。Quine 自体は何の役にもたちませんが、いろんな知識・技術を実践的に試すきっかけに最適なので、ぜひあなたも。

あなたの知らない超絶技巧プログラミングの世界
遠藤 侑介
技術評論社
売り上げランキング: 3,000

*1:余談ですが、username の部分は別の文字列に変えてもツイートは開けるようです(正しい username に転送される)。username を変えてもデッドリンクにならないようにこうなっていると思われますが、他人のツイートURL 上では偽装できるとも言えますね……。

*2GitHubリポジトリからは消えていますが、README にある通り、リリースは残っています。

*3:snowflake のソースコード内では、datacenter-id と worker-id という名前で、それぞれ 5 ビットずつのようです。

*4:3 年ならおそらく生きているうちには終わるだろうし、投稿スクリプトもほとんど sleep なので電気代はかからないし。

*5:同数の場合は適当。5 というパラメータは、1000 の失敗ツイートのデータでシミュレーションして一番ヒット率が高くなった値。

*6:実際、成功時の処理に typo があって例外になってました。ツイ消しには至らなかったものの、これだから Ruby は……(逆恨み)

*7:存在しなかったツイート URL が後から現れる可能性を考慮する必要は(普通は)ないので。

*8:他にも Twitter bot 作りたいネタはあるんですが、VPS をケチっているので話が進まない。

*9:大したことしてないのに偉そう。