Rustで将棋棋譜変換ライブラリを作った

将棋棋譜の形式色々
- KIF
- CSA
- USI/SFEN
- 文字表記
- その他
JSON棋譜フォーマット(JKF, json-kifu-format)
自作parser, converter
クレート公開

Rustでjson-kifu-format互換の将棋棋譜変換ライブラリを書き始めていて、ついに分岐までちゃんと対応した.kifファイルのparserを正規表現など使わずnom parser combinatorだけで実装できたぞ…https://t.co/QuXJp0ikbN
— すぎゃーん💯 (@sugyan) July 30, 2022

というわけで作った記録

将棋棋譜の形式色々

プロ対局、コンピュータ将棋、対戦アプリ、…と様々な将棋対局についてのデータが世の中には存在しているが、その形式は様々だったりする。

KIF

将棋ソフト「柿木将棋」で使われている形式だそうで、現在でも多くの将棋ソフトなどで使われているようだ。プロ対局の中継サイトなどでもこの形式が使われている。

例:

# ---- Kifu for Windows95 V3.53 棋譜ファイル ----
開始日時：1999/07/15(木) 19:07:12
終了日時：1999/07/15(木) 19:07:17
手合割：平手
先手：先手の対局者名
後手：後手の対局者名
手数----指手---------消費時間-- # この行は、なくてもいい
1 ７六歩(77) ( 0:16/00:00:16)
2 ３四歩(33) ( 0:00/00:00:00)
3 中断 ( 0:03/ 0:00:19)

初期盤面や指し手など日本語で記述されていて、人間が読むぶんには直感的に分かりやすい。

が、コンピュータで解析するにはなかなか厄介…。書式の定義については以下のリンクだけが存在している状態のようで、これを頼りに解析していくしかない。しかし「省略できる」「任意のものを追加できる」などなかなか自由な項目が多くて対応するのは大変。

http://kakinoki.o.oo7.jp/kif_format.html

優れている点としては、上記リンクでは言及されていないが「指し手の変化・分岐が表現できる」、という点で、枝分かれしたものも含めてすべて記録として残せるようになっているようだ。自分は柿木将棋などのシリーズ製品を持っていないけど、おそらくこれらがちゃんと分岐を含む棋譜も読み取って再現できるようになっていると思われる。

CSA

これは Computer Shogi Association で定めている形式のようで、KIFと比較すると圧倒的にコンピュータで解析しやすい形になっている。

例:

'----------棋譜ファイルの例"example.csa"-----------------
'バージョン
V2.2
'対局者名
N+NAKAHARA
N-YONENAGA
'棋譜情報
'棋戦名
$EVENT:13th World Computer Shogi Championship
'対局場所
$SITE:KAZUSA ARC
'開始日時
$START_TIME:2003/05/03 10:30:00
'終了日時
$END_TIME:2003/05/03 11:11:05
'持ち時間:25分、切れ負け
$TIME_LIMIT:00:25+00
'戦型:矢倉
$OPENING:YAGURA
'平手の局面
P1-KY-KE-GI-KI-OU-KI-GI-KE-KY
P2 * -HI *  *  *  *  * -KA * 
P3-FU-FU-FU-FU-FU-FU-FU-FU-FU
P4 *  *  *  *  *  *  *  *  * 
P5 *  *  *  *  *  *  *  *  * 
P6 *  *  *  *  *  *  *  *  * 
P7+FU+FU+FU+FU+FU+FU+FU+FU+FU
P8 * +KA *  *  *  *  * +HI * 
P9+KY+KE+GI+KI+OU+KI+GI+KE+KY
'先手番
+
'指し手と消費時間
+2726FU
T12
-3334FU
T6
%CHUDAN
'---------------------------------------------------------

主にASCII文字で表現されるようになっていて駒種は2文字、場所を示すのも2桁の数字、といった一定の決まりがあるので解析しやすい。これと同様の表現を用いたCSAサーバプロトコルがあり、世界コンピュータ将棋選手権などではこれが使われているらしい。

http://www2.computer-shogi.org/protocol/record_v22.html

USI/SFEN

これは棋譜形式とはちょっと違うかもしれないけど、将棋GUIソフト「将棋所」で使われて広く普及しているUSIという通信プロトコルがある。 GUIと思考エンジンの間の通信をするために局面情報や指し手の情報を SFEN(Shogi Forsyth-Edwards Notation)という形式で表現していて、これによって棋譜を再現できる。

例:

position sfen lnsgkgsnl/9/ppppppppp/9/9/9/PPPPPPPPP/1B5R1/LNSGKGSNL w - 1 moves 5a6b 7g7f 3a3b

http://shogidokoro.starfree.jp/usi.html

文字表記

そもそもコンピュータで扱われる前は文字情報だけで記録が残っているはずで、これは指し手をそれぞれ数字と駒種と相対位置や動作で表現している。KIF形式はこれらの表現をカスタマイズした形式といえる。

７６歩
５２銀右上成

https://www.shogi.or.jp/faq/kihuhyouki.html

その他

その他にも幾つかの形式があるようで、どれがどのくらい普及しているのかよく分からない…。おそらく多くはKIFかCSAが使われていると思われる。CSAはむしろコンピュータ将棋の人にしか使われていないか…？

GUIソフトや将棋ソフトの開発者はそれぞれこれらの形式を読み書きできるように対応していくしかない、という状況のようだ…

JSON 棋譜フォーマット(JKF, json-kifu-format)

上述した棋譜形式はそれぞれ読みやすさや表現できる情報が違っているわけだが、実際のところ指し手には多くの情報が必要で、単独の指し手の表記だけを取り上げたときに「どの駒が」「どこから動いて」「どうなったか」などの情報をすべて知ることは出来ない。直前の指し手や現在の盤面の情報がないと分からないものが多かったりする。

そこで、json-kifu-formatという形式が提案されて公開されている。

github.com

READMEに書かれている通り、各指し手について必要な情報をすべて含めたJSON形式で表現し、また分岐にも対応している。

例:

{
  "header": {
    "先手": "na2hiro",
    "後手": "うひょ"
  },
  "moves": [
    {},
    {"move":{"from":{"x":7,"y":7},"to":{"x":7,"y":6},"color":0,"piece":"FU"}},
    {"move":{"from":{"x":3,"y":3},"to":{"x":3,"y":4},"color":1,"piece":"FU"}},
    {"move":{"from":{"x":8,"y":8},"to":{"x":2,"y":2},"color":0,"piece":"KA","capture":"KA","promote":false}},
    {"move":{"from":{"x":3,"y":1},"to":{"x":2,"y":2},"color":1,"piece":"GI","capture":"KA","same":true}},
    {"move":{"to":{"x":4,"y":5},"color":0,"piece":"KA"}},

    {"special": "CHUDAN"}
  ]
}

さらにこの形式の提案だけでなく、KIFやCSAからJKF形式に変換するためのparserと、JKFを再生するためのプレイヤーも同梱している。

実装としてはそれぞれの棋譜形式を一度parseしたのち、初期局面から一手ずつ実際に進めて足りない情報を補っていくことで最終的なJKFを生成しているようだ。

自作parser, converter

上記 json-kifu-parser はJavaScriptで実装されているが、自分は最近はRustで将棋関連のものを作っていてRustでも同様のものが欲しいと思った。

具体的には、自作の詰将棋ソルバに色々な問題を食わせてみようと思ったときにKIFファイルが多かったり自分で書くにはCSAで書いたりで色々な入力に対応したいというのがあった。

CSAのparseには csa crateが既に存在していて問題ないが、KIFは自力でやるしかなく、いちおう自前である程度のparseできるところまで作っていたが、折角だから分岐もちゃんと対応してJKFに互換のデータを作れるParserを作ってみよう、という気持ちになった。ので作ることにした。

github.com

KIFのparseには csa と同様に nom というparser combinators libraryを使って頑張って実装した。opt や many0 が多くてなかなか大変だったが、どうにか様々なケースに対応できたと思う。パフォーマンス的にちょっと問題があるかもしれないけど… 大量の棋譜を食わせて高速に処理をしなければならない、という場面でない限りは大丈夫か。

分岐は一度最後まで読み込んでstackに積んでおいてから後で forks に詰め替えていく必要があってなかなか頭を使った。

CSAのparseはcsa crateに任せてparse結果からJKFに変換する処理だけを書いて作ったが、csa crateは指し手のコメントなどを捨ててしまっていて復元できなかったりもあるので、こちらも自分で実装しなおしても良いのかもしれない。

それぞれparseして結果を JsonKifuFormat に詰めたら、足りない情報を補うために normalize() を呼ぶ。この中で実際に局面を動かして確かめる必要があるので内部で shogi_core crateを使った。forks は再帰的に処理していく。

また、 relative 情報は他の同種駒と比較して相対的なものを調べる必要があり、計算が大変めんどう…なので shogi_official_kifu crateで表記結果から取り出して詰めることでお茶を濁した。本来ならこの棋譜表記を作成するための情報なので本末転倒な感もあるが…。そもそも relative はそういった棋譜表記をするときくらいにしか使わない(棋譜変換などでは必要ない)ので計算もoptionalで良いのかもしれない。

一度 JsonKifuFormat が作れれば、そこからKIF形式やCSA形式に書き出すのは比較的容易にできる。(KIFの分岐はまだ対応できていないが…)。また shogi_core::Position にも変換できるし shogi_core::ToUsi traitを利用してUSIで書き出すのもやりやすい。

ので、もし対応する棋譜形式を増やそうと思ったらそれぞれ JsonKifuFormat と相互変換するためのparser/converterだけを用意していけば良い、ということになる。記事冒頭に載せた図の通りで、変換の中継のための形としてとても良いデータ型になっていると思う。