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 みたいな世界。

fujihiro0fujihiro0 2017/02/12 09:10 サーバで動的にレスポンスしなくても、分割してハッシュをファイル名にしたスタティックなファイルをxhrで取得するのではダメですか?

ku-ma-meku-ma-me 2017/02/12 09:44 なるほどー、そのアイデアはありませんでした。それなら GitHub Pages でもできましたね。

ktanakaktanaka 2017/02/13 19:11 元論文(正確には論文ではなく研究報告)を書いた田中哲朗です.発表スライド
https://www.tanaka.ecc.u-tokyo.ac.jp/ktanaka/dobutsushogi/20090626.pptx.pdf
のP.19「初期局面の勝敗」で「最短勝利手順データベース」と同等のことをやっ
てみて覚えるのに必要な局面数が 2,431,444 になることを示したのですが,最
善手が複数ある時にどちらを選ぶかを IP solver で解くことまでは思い至りま
せんでした(NP-hard なのは明らかだったので).約10万局面というと20倍の差
がありますが,「深さ 3 以下の盤面は覚えない」というのも有効なのでしょう
ね.

なお,データベースの圧縮については,
「田中哲朗. "完全プレイのためのデータベースのサイズの削減." 研究報告ゲーム情報学 (GI) 2012.12 (2012): 1-6.(オープンアクセス)」
で,試みています.任意の局面を扱えるようにするため,54.8MB にしかなりませ
んでしたが,用いた手法は似ていますね.

「初めて論文を書く人はどうやって解析の正しさに確信を持つんだろう」という
のは,「発表する時は確信は持っていない」としか答えようがありません.普段
と違って,実行速度は考えずにバグが出にくいようにコーディングして,unittest
も書きますが,バグの可能性は排除できません.コードを公開して,追試する人
もいて,数年経っても声がでてこなかったら正しそうだという気になるという位
ですね.

ktanakaktanaka 2017/02/13 19:20 なお,「どうぶつしょうぎ」に先立っておこなった,「ボードゲームSIMPEI」
では局面検索アプレット
(https://www.tanaka.ecc.u-tokyo.ac.jp/ktanaka/simpei/simpei.html) を公
開しました.これは,データベースをWWWサーバ上の1つの大きなファイルにし
て,requestでRangeを指定することでランダムアクセスをおこなうというもの
です.ソースは
https://www.tanaka.ecc.u-tokyo.ac.jp/ktanaka/simpei/SimpeiApplet.javaに
あります.

データベースはサーバに置くだけで良いので,どうぶつしょうぎに関しても同
等のものは作れたのですが,影響が大きいと考えたので,コマンドラインから
実行するプログラムを
https://www.tanaka.ecc.u-tokyo.ac.jp/ktanaka/dobutsushogi/
で公開しただけに留めました.

ku-ma-meku-ma-me 2017/02/14 01:09 わあ、見ていただいて光栄です。まず、研究報告に直させていただきました。(どこかで論文と言及されていて、勝手に思い込んでいました)

「深さ 3 以下を覚えない」が効いているのはおっしゃるとおりです。あと、後手盤面しか覚えていないのも効いています。証明グラフの数はよくわかっていませんが、こちらの実験では
(1) 最善手をすべて残す方針で到達可能な盤面を列挙して 3,059,038 盤面(深さ 1 以下は除く。また、先手初手がライオン斜めの時にひよこを進める応手は無駄に盤面数を増やすようだったのでアドホックに除外)
(2) そこから後手番面のみを取り出して 1,602,867 盤面
(3) 深さ 3 以下を捨てて 618,924 盤面
(4) IP solver で最適化して 126,206 盤面
と減っていきました。倍率的に一番効いているのは IP solver ですが、たとえば深さ 3 以下を捨てなかった場合に IP solver の削減率がどうなっていたかは NEOS サーバが使えないので試していません。

完全プレイデータベースの方も研究されていたのは存じませんでした。深さの情報に大きな偏りがあるのでもったいないとは感じていたのですが、しかも実は PHF の前にウェーブレット行列で盤面データを保持する方法も試していたのですが、PHF とウェーブレット木を両方使う方法は思い至りませんでした。

解析の正しさも勉強になりました。後退解析に必要な直前盤面の列挙にバグがあって(成ったコマを取った場合を考慮漏れしていました)、報告と違う結果になったのでバグに気づけましたが、正解を知らなかったらバグに気づけなかったと思うので、非常に助かりました。ありがとうございました。

そもそも完全解析の結果がなかったらこれを作ろうというアイデアに至らなかったと思います。そういう意味でも、ありがとうございました。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証