どうぶつしょうぎ名人

どうぶつしょうぎ 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 倍くらいにはなったようです。

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

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

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