(発表原稿です。できるだけそのまましゃべります。IT業界でない用語（カードゲーム）があるので、困ったら連絡ください。https://gist.github.com/seki/be96238b7bb65c437e9ee5d2c75aa375 @m_seki)
- (TCG -> 略さずTrading Card Gameと発音するようです)
- (WCS -> Pokémon World Championships)
- (toRuby, とちぎRubyの勉強会 -> Tochigi Ruby meetup)
こんにちは。 今日は自分ための検索エンジンをつくった話をします。
検索エンジンの仕組みを紹介する本やサイトはたくさんあって、学ぶ機会が多くなってますよね。
じゃあ次は？となると、 検索エンジンを作ろうか！とはならず、 既存のソフトウェアをインストールしてみる？ となることが多いんじゃないかなあ。
もしかすると、身近にちょうどよい規模の問題がないのかもしれない。
この時間は、私に必要な、手頃な問題を見つけて、作ってみた、というお話です。
私は、ポケモンカードゲーム「ポケカ」のデッキを検索するシステムを作りました。
ほんとうに自分のためのシステムです。
今日の話をきいて、自分のための、なにかを作りたくなってくれたら、うれしいです。
はい。システムの概要です。
ツイートから、ポケカのデッキを集めてきて、それを検索するシステムです。
このシステムの中心は、二つのデッキの類似度を計算する仕組みとデータ構造です。
今回の発表はポケカに特化したシステムですが、
デッキの類似度計算はポケカ以外のカードゲームでも利用できると思います。
ちょっとシステムを自慢しますね。
- ツイートから集めた新着デッキを見ることができます。
- 検索エンジンっていうと「探す」という目的をもって利用することが多いですが、特に探すことがなくても時間が潰せるのがすごい。
そして
- デッキを選ぶと、そのデッキの内容と、よく似ているデッキを表示して差分を見ることができます。
- みんながどんな工夫をしているのかわかります。
デッキのメモに使えます。
- 自分のツイートしたデッキを確認することができます。
- 自分のデッキコードを覚えておくのは面倒ですが、ツイートしておけば記録できるわけです。
- ツイートでgit pushしておく感じ。
便利！
変更履歴がわかります。
- デッキの各リビジョンをツイートしておけば、自分の変更履歴としても使えます。
この検索システムとTwitterを組み合わせると、 デッキを公開する、履歴がわかる、そして、forkして改造する、ことを支援します。 ちょっとgithub感があって、自分にとって最高に便利なシステムです。
カードの使用例も検索できます。
- あるカードを使用しているデッキも探せます。
- 「セキ」を使っているデッキを探しているところです。
他にも応用がたくさんあるのだけど、自慢はここまでです。
アジェンダです
- 自己紹介ぽいもの
- 背景となるポケカ
- デッキの類似度計算 - ここが一番喋りたい
- 全体の話は最後
の順に話します
では、私とRubyとポケカです。
プログラマの関です。
ポケカの最初のリリースは、1996年。この年にrubyも1.0がリリースされました。 開発の開始はポケモンの方が早いそうです。Rubyとポケカは同じくらいの歴史があるんですね。
dRubyを書いたのが1999年。20世紀ですね。
私がポケカを始めたのが2006年で、最初のRubyKaigiが開催された年ですね。 どっちもずっと続いてます。
2010年のワールドチャンピオンシップス日本代表決定大会で 栃木県代表になったのが唯一誇れる成績ですね。
ちなみに、来年のWCSは横浜で開催されます。 WCSが日本で開催されるのはこれが初めてです。 せっかくなので、みんな挑戦してみて！
昨年、私のポケカのゆるい活動についてインタビューを受けたので、 もうちょっと興味がある人はYouTubeを見てみてください。
30分くらいかな。
では、ポケカがどんなものか説明しますね。
ポケカは、ポケモンの世界をカードで再現した、二人で対戦するカードゲームです。
最近すごく流行っていて、入手するのも難しいです。
ポケカには、ポケモンのカードの他に、トレーナーズのカード、エネルギーのカードがあります。
これらのカードを60枚組み合わせてデッキを作って、二人で対戦します。
www.pokemon-card.com - card search
ポケカの公式サイトに、重要なサービスが二つあります。
一つは「カード検索」サービスです。 このサービスでは、カードに一意なIDを割り当てています。 このカードIDが今回は重要になってきます。
カードIDは10進の整数で、1から42091です。 カードIDには使われていない部分があり、実際の有効なカードIDは15717種類です。
www.pokemon-card.com - deck code
もう一つは「デッキ構築」サービスです。 プレイヤーが自分のデッキを登録できるサービスで、登録すると、デッキコードがもらえます。
kkFFfv-WaK14L-VkFkdv
これがデッキコードの例です。
デッキコードが分かれば、デッキの内容を表示することができるので、 デッキの情報をやりとりするのに便利です。
デッキがどのくらい登録されているのか知ることはできないのですが、 私がTwitterのタイムラインから抽出したデッキコードはおよそ26000です。 これらは、プレイヤーが公開したデッキ、と考えることができます。
- 毎日20くらい増えています。
- 私が作ったシステムが検索する対象は、タイムラインから抽出した26000のデッキです。
では、デッキ構築サービスでデッキがどのように表現されるか調べてみましょう。
ここ！カードIDと枚数が連結された文字列で格納されていますね。
カードIDと枚数のタプルの列で表現しているようです。
これをRubyで書くと右のような感じかな。
これ、...自然言語処理の教科書で見たことあるんですよ...
ベクトル化された文書がこんな感じだったんです。
「自然言語処理」では文書をBag-of-Words、単語のBagと考えて、ベクトル化することがあるんだけど、それを連想します。
あー、ここで、Bagとは順序なし重複ありのコレクションのデータ構造のことです。
デッキはカードの順序なし、重複ありのコレクションなので、Bag-of-Cardsですね。
似ていて当然かも！
というわけで次は、デッキの類似度の話です。
自然言語処理での「類似文書検索」をかなり端折って紹介します。
- 文書を単語に分割し、
- ベクトル化します。
- 内積を計算して、類似度をもとめます。
この類似度を使って検索するのが「類似文書検索」です。
単語のセグメンテーションやベクトル化、ベクトル間の演算には他にもやり方があると思うけど、 基本的な技法だけ、というか、今日使う技法だけを説明しました。
デッキは自然言語の文書のサブセットぽい、という話です。
自然言語の文書に比べて、デッキはすごく単純です。
デッキを文書だと思って観察すると、
- カードは単語に相当します。
- デッキの制約から最大でも60単語しか含まれない文書と言えます。
- さらに単語の出現順には意味がありません。
デッキは自然言語の文書のサブセットなわけです。
デッキのベクトル化はとても易しいです。
まず、一番めんどくさい単語分割が必要ないです。 語彙も非常に少なく、16000程度です。
単語の影響の重みを調整するのに、ベクトルの成分の大きさにTF-IDFという値を使うことがあります。
デッキの場合も同様です。 デッキでTF、IDFを説明すると、
- TFは、あるデッキの中のあるカードの採用枚数です。
- IDFは、全てのデッキの中で、あるカードの採用頻度の逆数です。あまり使われていないカードの値が大きくなります。
といった感じです。
ちなみに、IDFはベクトルの成分の大きさ以外にも活躍します。
デッキのタイトルを作るときに使います。
そのデッキの特徴となっているカードがタイトルになっているとうれしいです。
そのデッキだけが採用しているカード表示し、 他のデッキにも採用される汎用的なカードは隠す、 といった感じです。
この処理にIDFをキーにしたソートを使っています。
正規化の話です。
単語分割ほどではないですがデッキの場合ににもちょっとめんどくさい問題があます。
ポケカでは、同じ効果、同じ意味のカードが複数存在するので、正規化が必要です。
単語の活用形を正規化したり、異体字を正規化したり、そういうのにちょっと似ています。
たとえば、イラストが違うとか、ホイル加工してあるとか、そういうやつです。 これらは同じ意味であってもそれぞれ別のカードIDが割り当てられています。
このフルアート、めっちゃかわいい。
さらに同じ名前のカードが再録されることもあり、やはりそれぞれに違うカードIDがついています。
カードをコレクションする場合にはそれぞれを区別できる必要がありますが、
対戦中には、ホイル加工とかイラスト、レアリティの違いとか、そういうのは影響しませんから、 同じ意味のカードは同じカードIDとして扱うほうが都合が良いのです。
このため同じ意味のカードを同じカードIDへ正規化する必要があります。
カードが同じ意味かどうか、識別する方法を説明します。
カードの種類が、ポケモンかトレーナー、エネルギーかによって、識別する情報が異なります。
トレーナー、エネルギーのカードは、カードの名前だけで識別しますが、 ポケモンの識別は面倒です。
カードに書かれている、名前、HP、ワザの説明などなど、対戦に関係する属性を調べて、 内容が同じものをグルーピングします。
説明した規則で、カードIDを正規化する辞書を作ります。
- 事前に、カード検索サイトからカードのページをダウンロードしておき、
- 集めたページから属性を抽出し、ソートし
- 次のような辞書をつくります。
整数の組は、そのカードIDがどのカードIDへ正規化されるかを表しています。 正規化先のカードには、正規化先のカードIDの代わりに、そのカードの名前を書きます。
この辞書ファイルを処理して、正規化のためのHashと、カード名を表示するためのHashを作ります。
正規化すると、15717種類だったカードは9275種類になります。
辞書は実行中に変わらないので、この形式のままソースとしてgitに登録されています。
新しいカードがリリースされるたびに更新する必要がありますが、 その都度、開発環境で処理してpushしています。
ときどき公式サイトのデータが間違っていることもあるので、 完全な自動化は難しく、半自動で処理してます。
この書式で作っておくと、diff表示で差分を確認しやすくて便利です。
正規化の準備ができたので、デッキのベクトル表現について考えます。
カードは9275種類ですから、デッキは9275次元のベクトルと言えますが、 RubyのVectorでそのまま表すと大変なことになります。
ほとんどの成分の大きさは0ですね。
デッキのベクトルの実装を考えます。
ほとんど成分がゼロであることと、内積計算しかしないことに特化した実装にしました。
内積は二つのベクトルの各成分を掛け算して合計したものですが、 デッキの場合はほとんどの成分は0なので、多くの次元で計算する必要がありません。
カードIDと枚数の組を、カードIDでソートした配列を使ってベクトルを表現します。
さらに、計算が楽になるように、二つのHashを作っておきます。
- @idfはカードIDごとのIDF
- @normはデッキコードごとのベクトルの大きさ
内積の実装です。
内積は「両方に存在するカードの成分を掛け算して、合計する」処理ですよね。
つまり、インターセクションを求めるってことですね。
こういうときは要素をソートしておいて、 小さい方のカーソルを動かしながら探すと効率が良いです。
これマージソートのマージのときと同じですね。
ちなみに、デッキのdiffの計算も同じループで実現しています。
二つの配列を走査するカーソルが動くようすを示します。
- 注目した要素が一致した場合は、掛け算して合計して、両方のカーソルを進めます。
- 異なる場合は小さい方のカーソルを進めます。
この繰り返しを一方が尽きるまで続けると、内積が計算できます。
ちなみに、これは、咳マニア向け情報です。
二つの集合のインターセクションを求める話、The dRuby Bookでも説明していたのを、先日思い出しました。
これは計算部分です。
二つのデッキのTF、IDFの二乗を掛け算して合計しています。 （わかる？）
ちなみに、この計算に登場する数は全て整数となっていて、速度もメモリもお得です。
コサインを作ります。
内積の計算に適した表現がわかりました。
これを二つのベクトルの大きさ（ノルム）で割るとコサインになります。
def cos(a, b)
left = @deck[a]
right = @deck[b]
dot(left, right) / (@norm[a] * @norm[b])
end画像処理では単位ベクトルで持っておくことが多いんだけど、 今回のケースでは整数のベクトルと、ノルムを別に持ってます。
さて、cosの計算もできるようになりました。
ここまでの手法は、ポケカに限らず、どのカードゲームでも共通なデッキの表現ではないかと思いますが、
「基本エネルギーカード問題」というポケカ特有の調整の話をします。
デッキには同じ名前のカードは4枚まで入れられる、というルールがあります。 このルールには例外がって、基本エネルギーのカードだけは何枚でも入れることができるのです。
基本エネルギーのTFが他のカードに比べて極端に大きいので、 類似度に強く影響してしまう、という問題があります。
そこで計算時にカードの枚数を5以下に制限することしました。
やっと二つのデッキの類似度が計算できるようになりました。
類似度を使った検索は次のようになります。
全てのデッキに対して、ベクトルvとの類似度を計算し、ソートして、上位n件を返します。
ソートして、上位n件欲しいときはmax(n)を使うと良いのですね。 笹田さんに一昨日教えてもらいました。
全てのデッキに対して計算するわけですが、数万デッキの計算なら、あんまり待たされることはないです。
100万デッキになったらどうなるかわかりません。
ベクトルvを工夫することで、いろいろな検索が行えます。
似ているデッキを探すのは基本的な検索です。デッキのベクトル表現を与えます。
あるカードを採用しいているデッキを探す場合、 そのカードしか入ってないデッキのベクトルを作って、 検索します。
そのカードしか入ってないデッキっていうのは、カードIDと成分の大きさが1のみの配列ですね。
検索エンジンの中心となる処理ができました。 つぎは、システム全体での工夫を説明します。
Herokuは、toRuby（とちぎRubyの勉強会）ファウンダーの池澤さんの製品でたくさん使ってて、慣れているので選びました。矢板市で一番Heroku使ってると思う。
ちょっとしたサービスを始めるまでが簡単だし、Pgも使いやすいし、私はHeroku好きです。
HerokuはコンテナをDynoと呼んでます。
このシステムは、Free Dynoという無料プランで動いています。
そういえば、Free Dyno、終わっちゃうんですよね...。残念。
Dynoが実際にどんな性能なのかよくわからないし、いつも同じ性能のVMが借りられているのかわからないです。 なので、計測によるチューニングはしないで、体感速度の向上を狙いました。
我々庶民は、小さなメモリ、シングルコア環境で速く動かす必要があります。
庶民のクラウド環境にとって、 マルチコアの恩恵は、非常に安い、あるいは無料のVMが提供されるようになったことじゃないでしょうか。
Free Dynoは30分のアイドルで停止します。
また、それ以外にも24時間に一度はDynoの再起動が発生します。
つまり、Dynoがずっと動いていることをあてにしない方がよいってことです。
そういうものなら、それを利用してみようかと思いました。 たとえば、定期的なクリーンナップ処理をプロセス起動時に行なったり、 ほどほどの正確さでよい統計量（IDF）の計算を起動時にだけやるようにしています。
データはHobby BasicのPostgresを利用しています。 Herokuの無料枠だけで使うのが申し訳なくてデータベースは有料のものを選びました。
クローラはHeroku Schedulerで動きますが、 クローラのDynoの寿命とサービスのDynoの寿命は無関係です。
つまりクローラが新着デッキを伝えたい時にサービスは落ちつつあるかもしれない。
そこで、永続的なPostgresに、データを仲介してもらう、って感じで使っています。
最初に見せたシステムの全体像です。 これに関連するデータなどを載せて⭐︎ちょっと詳細にした図を示します。
ひとつひとつ説明しますね。
「開発フェーズの話」
カードの正規化辞書は既に説明した通りです。
ソースコードの一部として準備します。
「クローラーの話です」
クローラはTwitterのタイムラインから、デッキ構築サイトのURLを含むツイートを集めます。
クローラはHeroku Schedulerのタスクとして起動されます。 先ほども説明しましたが、クローラのDynoとサービスのDynoの寿命は無関係なので、 Heroku PGにデータを仲介してもらいます。
new dataは新着のデッキの情報です。
メタデータは、どのツイートから手に入れたのかを記録するものです。
「初期化フェーズの話です」
Heroku Appです。Heroku Appは主に三つのフェーズで考えます。
まずは初期化時フェーズです。
ここには二つの処理があります。
一つはデッキの一覧を更新する処理です。
Postgresの新着デッキと、S3の前回までに集めたデッキをマージして更新します。 マージが完了したら、次回の起動に備えてS3に書き戻します。
もう一つは、デッキのベクトル表現を作る処理です。 さっきマージしたデッキの一覧を、カードの正規化辞書を使って正規化して@deckに覚えます。 同時に@idfと@normも計算してメモリに覚えます。
これで検索に必要なデータはメモリの中に全て準備されたことになります。
つぎは検索時の話。
外部のデータに触れるのは初期化時までです。
初期化フェーズで検索に必要なデータはメモリの中に組み立てられているので、 外部のデータにアクセスすることはありません。 インメモリで検索が終わります。
そうそう。資料作ってるときに思いついたことがあります。
- keyがcard-idのHashがいくつかあるが、配列で十分ではないか？Keyはunsigned short以下だろ？
- きっとそう！必要ならちょっと速くできそう。
最後にWeb UI部分。
Heroku Appの最後のフェースはWeb UI部分で、検索結果の見た目を組み立てます。
検索結果を返すとき、Postgresにあるデッキのメタデータにアクセスします。
誰がどのツイートでこのデッキを公開したのか、などを調べます。
検索結果に必要な情報は少ないので、外部にアクセスしても性能に大した影響はありません。
これ、もしHerokuを使わなかったら、の話です。
現在はHerokuを使っているのですが ...
- Herokuを諦めるなら、クローラがPostgresに保存する必要がないかもしれません。
たぶん、こんな構成になるかな？と思います。
クローラはdRubyで直接伝えて、仲介のデータベースはなしですね。
Free Dynoがなくなるまであと2ヶ月あるので、どうするか考えなくちゃならないですね。
今日の話はおわりです。
自分に必要な検索エンジンを自分で作るお話しでした。
みなさんが自分用の「なにか」を作りたくなってくれたらうれしいです。