みんなが大好きな咳さんの発表です。
ご本人のブログに記事があります。 発表資料もこちらから見れます。
「検索エンジンを作りました。」という発表です。 全文検索をやろうとすると、たいてい次のような課題をクリアしないと着手できません。
ポケモンカードゲームだとこの部分が終わっているので、いきなり検索の実装の話に入れとのことでした。 いつも通り目の付け所が面白いです。
ポケモンカードゲームのデッキ検索エンジンをつくるには、デッキの類似度を決める必要があります。 類似度は、デッキの特徴を表現するベクトルを作って内積を計算すれば数値に出来ます。 数値にすると大小がきまるので、あるデッキに似たデッキが見つかります。
デッキのベクトルをどうやって決めるのでしょうか？ 素朴に考えるとカードの種類を次元として含まれる数を特徴量とすれば良さそうです。 使い勝手がよく、よく使われるカードは、どんなデッキにも含まれます。 デッキの特徴を強調するために、こういカードは特徴量を小さくしたいです。 ここで使うのがIDF（inverse document frequency）です。 カードの使用頻度の逆数です。 これを特徴量に掛けると、デッキの特徴を目立つようにします。
カード情報は正規化されていると言いましたが15000件あるので手作業では作れません。 公式のカード検索サイトから取得します。 15000種類ありますが柄違いの同じカードもあるので、この正規化は必要です。 ここの正規化の仕方も何か説明していましたが、聞きそびれました。
この辺からだんだんわからなくなってます。
- 公式のカード検索サイトが時々間違っているので目検してる
- 特徴ベクトルの比較ではマージソートと同じように比較する
- エネルギーカード*1はたくさん入るから特別扱いする
- Herokuにデプロイしたので、インスタンスが定期的に死ぬ。dRubyが使えなかった
みたいな話もしてたと思います。
話を聞いていたら、（珍しく）自分でもできるかも？みたいな感想を持ちました。 で、あらためてまとめてみると、めちゃ色々やってて大変じゃないですかー。
参考
*1:マジック・ザ・ギャザリングの土地カードみたいなもの？
