IndexedDB でつくる連珠棋譜検索
連珠というゲームをご存知でしょうか？
簡単に言えば五目並べのルールを競技として成立するように整えたもので、次のようなことが定められています。
- 15x15の盤を使う
- 黒 (先手) のみ三三・四四・長連が禁手になり打つことができない
- 上級者向けに、序盤の均衡を保つため着手に制約を設ける開局規定が存在する
昨今の世情により自宅で過ごすことが増えた結果、私はなぜかこのゲームにドハマりしてしまい、こんな記事を書いています。
連珠の序盤事情
連珠は序盤の比重が極めて大きいゲームです。例えば序盤3手までのこの局面、
「花月」と呼ばれる作戦ですが、実は白が4手目をどこに打っても黒が勝てることが解明されている、つまり黒必勝の局面となります。
実際は前述の開局規定のおかげで、上級者の対局では黒がこの作戦を採用しても必勝手順通りに進めることはできません。 しかしその場合も「制約がなければこの局面が黒必勝である」ことを前提としてゲームが進行するため、上位クラスで戦うには必勝局面とその手順についての知識をある程度身につけておく必要があります。
ではこうした知識をどこから得るのか、ですが、連珠は将棋や囲碁などに比べて定石の指導書やオンラインコンテンツがそれほど充実していません。 そこでよく用いられる手段が、ひとつはいわゆるAIを使った研究、もうひとつが実戦例を参考にした研究です。 今回は後者についての話になります。
連珠は国内での競技人口こそ少ないですが、驚くほど国際化と棋譜のデータ化が進んでおり、連珠国際連盟が運営する RenjuNet というサイトで世界中の公式戦の棋譜を閲覧することができます。
The Renju International Federation portal - RenjuNet
このサイト自体は機能が限定的で、任意の序盤局面から実戦例を検索することはできないようです。 その代わりに全棋譜の一括アーカイブをXML形式で提供しており(!)、有志によってアーカイブを検索するための専用ソフトが公開されています。
ただし残念ながら既存のソフトのほとんどは Windows でしか動作しません。 そこで今回、Webブラウザで動作する局面検索機能付き棋譜アーカイブビューワを自分で作ってみました。
ブラウザで数万局の棋譜を検索する
というわけでやっと本題に入ります。ここからはプログラミング寄りの話です。
RenjuNet が提供する棋譜アーカイブは、利用規約上転載や再配布が許可されていません。 よって、棋譜をDBサーバに保存しておいて検索機能をWebサービスとして提供する、といったやり方はできません。 そのため取りうる選択肢は、棋譜アーカイブをユーザ各自が RenjuNet からダウンロードし、それをブラウザで開いて閲覧・検索できるようにする、ということになります。
最新の棋譜アーカイブは7万局超の棋譜を含む20MB程度のXMLデータとなっており、局面を入力するたびに全棋譜との一致判定を行うのは流石にパフォーマンスが気になります。 そこで思いついたのが IndexedDB を使う方法です。
IndexedDB はWeb標準に含まれる技術で、ブラウザ上のストレージにオブジェクトのインデックスを構築することができます。 このインデックスは範囲検索・複合キー検索や multi-value に対応しており、 LocalStorage よりも柔軟な用途に対応できます。 また JavaScript ライブラリではなくWeb標準としてネイティブに実装されているので、高いパフォーマンスが期待できそうです。
今回の「局面から棋譜を検索する」という要件は、局面を符号化したものをキー・棋譜IDをバリューとする multi-value インデックスがあれば実現できるので、 IndexedDB はうってつけの技術といえます。
それでは早速、実際に作ったものを紹介します。
入力した局面に追従して棋譜を検索できているのがわかると思います。 このWebアプリは少し前に「連珠ノート」という名前で私が公開したもので、今回の実装はその一機能として組み込んであり、以下のURLから誰でも使えるようになっています。
機能の利用方法は以下の動画でも解説しています。
なお、今のところ棋譜アーカイブの読み込み処理がSafari系のブラウザで動作しないようです。 XMLのパースに DOMParser を利用しているのですが、 WebKit の DOMParser はサイズの大きいファイルを扱えないのかもしれません。
実装の詳細
検索機能の実装は次のような構成になっています。
コードは全て GitHub で公開しているので、興味があればご覧ください。
GitHub - renju-note/renju-note
以下に主要箇所の簡単な説明を書いておきます。
XMLをパースして棋譜を抽出する
XMLから抽出したデータは、以降の処理で扱いやすくするため一旦そのまま IndexedDB に投入しています。 ここではまだ局面の符号化はしていません。 なお IndexedDB のAPIを直接触るのではなく、 Dexie.js というラッパーを使用しています。
https://github.com/renju-note/renju-note/blob/v2.0.0/src/database/rif.ts#L238-L276
局面を符号化する
黒石・白石を1bitとして盤面を1列につき2個の整数、全部で15x2個の整数で表現し、16進数で文字列化して結合したものを局面符号としています。 今の用途では単なるハッシュ値を局面符号としてもよいのですが、一応局面を再現できる方式をとっています。 また、回転・反転して一致する局面は同一の符号で表現されるよう工夫しています。
https://github.com/renju-note/renju-note/blob/v2.0.0/src/database/encoding.ts
局面符号と棋譜IDをインデックスする
こちらが棋譜検索を実現するためのコアロジックです。 棋譜数x10手分の局面を扱うので、最も計算負荷が高い箇所でもあります。 手元のMacBook(2018モデル)でChromeを使うと7万局のインデックスに2分程度かかりました。
https://github.com/renju-note/renju-note/blob/v2.0.0/src/database/analyzed.ts#L50-L77
局面から棋譜を検索する
上で作成したインデックスを利用して棋譜を検索しているところです。 このメソッドをUIコンポーネントから呼び出して利用しています。 IndexedDB のおかげで1回の検索のレスポンスタイムは1~2秒となっています。
https://github.com/renju-note/renju-note/blob/v2.0.0/src/database/analyzed.ts#L79-L117
おわりに
勢いで作ったWebアプリですが、ありがたいことに海外も含めて多くの連珠家の方々に使っていただいており、今後も開発を継続していこうと思います。
また機能のテストには複数人の高段者の方にご協力いただきました。皆様快く引き受けてくださり、とても感謝しております。今後ともよろしくお願いいたします。
IndexedDB を使ってブラウザ上である程度の規模のデータを検索可能にする方法は、ボードゲーム分野にとどまらず様々な応用ができそうなので、何かの参考になれば幸いです。
