将棋AIは現在のほとんどの将棋ソフトはUSIプロトコルというプロトコルを採用している。これはチェスAIのプロトコルであるUCIプロトコルをそのまま将棋に転用したものであり、長年の運用により特に大きな問題がないことが実証されている。
ところがマイナーなゲームや、まだ誰もAIを作っていないような新規のゲームだと、このようなプロトコルが存在しなくてAI同士の対局をさせられないことが多々ある。
その都度、プロトコルを策定したり、対局サーバーを作ったり、レーティング計算部を作ったりするのは無駄な作業である。また、何らかのAIコンテストにおいては、そのような対局サーバーやレーティング計算部を作っている時間が惜しい場合も多々ある。
そこでお手軽に既存の(USIプロトコル用の)対局サーバーが、対局スクリプトが転用できるような標準通信プロトコルが望まれている。
本記事では、そのような通信プロトコルを提案し、実際にUSIプロトコル用の対局スクリプトを転用する方法について説明する。
提案プロトコル名
USI-X(Universal Standard Interface X)プロトコル
読み方 : ゆーえすあい えっくす
将棋のUSI(Universal Shogi Interface)に似た名前にしているのは、USIプロトコルをそのまま転用したいため、”USI”,”usi”という文字列がそのまま使う部分が出てくるのだが、「この”USI”の”S”は将棋のSじゃん」というツッコミに対し、「これは将棋のSではなく、StandardのSである」と言い返すためである。しかし、名前がUSIプロトコルそのままだと紛らわしいので、ここに「X」という文字を付与しておく。
提案プロトコルの内容
基本的には、USIプロトコルに準ずる。
USIプロトコル : http://shogidokoro.starfree.jp/usi.html
ここで将棋固有なのは、局面の表現文字列(sfenと呼ばれる)と、指し手文字列(moveと呼ぶことにする)である。
“sfen”は、Shogi Forsyth-Edwards Notationの略らしく、”s”はShogiの略なのだが、さきほども書いたように、これをStandardの略だと解釈しなおすことにする。ここをゲームに応じて、例えば、オセロ(リバーシ)であれば、”ofen”みたいに変更したい衝動に駆られるかも知れないが、このような変更は絶対にしないでいただきたい。
なぜなら、ここを変更さえしなければ、USIプロトコル用の対局スクリプトが無改造でそのまま動作するからである。こんなところを変更してはならないのである。
ということで、プロトコルの策定は以上である。つまりは、USIプロトコルを持ってきて、sfenとmoveを何らか定義すればそれで良いということある。
実際にリバーシ(オセロ)に適用する例
例えば、リバーシの開始局面であれば次のsfenになる。
sfen 8/8/8/3wb3/3bw3/8/8/8 b – 1
これは将棋の時の開始局面のsfen文字列(lnsgkgsn1/1r5b1/ppppppppp/9/9/9/PPPPPPPPP/1B5R1/LNSGKGSNL w – 1)に倣っていることがわかるだろう。w = white = 白、b = black = 黒の意味であり、末尾の b – 1 は黒の手番、1手目 という意味である。
また、リバーシの指し手文字列は、”f5″のように左上をa1とする普段使っている棋譜表現をそのまま使う。
これでリバーシの対局プロトコルが完成である。
// 上のリバーシ用のsfen文字列は、将棋のsfenに似せた場合にこうなるという例示にすぎず、本プロトコルで強制するものではありません。現実的には、リバーシはEdaxなど強豪ソフトが採用している局面文字列の形式を踏襲したほうが、それらのソフトが採用しているプロトコルとの互換性が高まって良いでしょう。
対局スクリプト
上の方式に従うなら、やねうら王の対局スクリプト(後述)などがそのまま無改造で使える。なぜなら、やねうら王の対局スクリプトは指し手の合法性をチェックしていないからである。
さて、この時、対局棋譜は、開始局面(startpos)から”position”コマンドでエンジン側に送られてくる。上のリバーシの例で考えてみよう。初期局面からf5を打った局面は次のように送られてくる。
position startpos moves f5
ここでエンジン側がd6をbestmoveとして返したとしよう。
bestmove d6
そうすると、もう片方のエンジンには、
position startpos moves f5 d6
が次の思考対象局面として送られてくる。
このように対局サーバー(対局スクリプト)にとっては、bestmoveで返された文字列を棋譜文字列(“position”コマンドで送る)の末尾に付与していくだけであり、その内容については何ら関知しないのである。
無論、対局スクリプトにゲーム名が指定されていて、それが既知のゲームであるなら、その指し手の合法性をチェックする機能が備わっているほうが好ましいが、いまそれについては考えないことにする。
逆に、将棋用に開発された対局スクリプトだと将棋としての指し手の合法性をチェックしてしまうがために、新たに追加されたゲームの対局スクリプトとして使えない可能性はある。その場合、対局スクリプトには、オプションで指し手の合法性をチェックしない機能は必要になるだろう。(そのような機能が備わっていないなら指し手の合法性のチェックをしているソースコードの該当部分をコメントアウトする必要がある。)
テトリスの場合
まず、テトリスの盤面の表現を考えるが、実は、テトリスではこのプロトコルはうまくいかない。何故なら、bestmoveでエンジン側が返した指し手は次に相手側のエンジンに与えられる棋譜の末尾に付与される想定だからだ。
しかし、エンジンの数 = 1の対局と考えれば(対局スクリプトの修正は必要であろうが)、USIプロトコルを援用すること自体は可能である。それについて考えてみよう。
まず盤面の表現だが、テトリスはブロックの種類が7つあり、それぞれ色が異なるので、すなわち盤面には7色の1×1の任意のブロックが存在することになる。しかしエンジン側にとっては盤面上にあるブロックの色は関心の対象ではないので(それによって消え方が変わるわけではないので)、存在するかしないかという単なるbit列で表現すれば良い。
ところで、この時、2つ大きな問題がある。まず、USIプロトコルでは連続する空き升を数字で表現していた。テトリスの場合、盤面(フィールド)は、横10×縦20升であるため、横の最大の連続する空き升の数は10になる。
ということは、開始局面は以下の文字列になる。手番は存在しないので、手番を表現する文字は削除する。
sfen 10/10/10/10/10/10/10/10/10/10/10/10/10/10/10/10/10/10/10/10 – 1
sfenのparserを書く時に、10という文字が使われる場合、”1″という文字を見つけても即座にこれが数字の1を意味するのではなく、次の1文字を先読みして、それが数字ならば…という処理が必要になってくる。このような先読みが必要な仕様にしてしまうとparserを書くのが少しだけ面倒になる。
だからテトリスの場合、10を使わずに16進数で考えて”a”を10の代わりにしようという風に考える人もいるかも知れない。
だけど、これはお勧めしない。ここで16進数を持ち出されるとフィールドサイズの横が16を越えた時にまたややこしい問題が発生して、それ用に異なるparserが必要になってしまう。そういうことはしたくないし、そういうことが必要な設計は良くない設計なのである。
そこで、「空き升の数を表現するために16進数とかを持ち出さない」というのを本プロトコルのルールとして追加しておく。
次に盤上のブロックの表現である。bit列であるから、何らか圧縮することも考えられる。単純には、例えば、アルファベット16文字あれば、それを16進数とみなすと4bit分(4升分)のbit表現となるので、文字数を減らすことはできる。
しかし、こういうのを過度にやると人間にとって可読性が下がる。人間が見ても、ある程度読めることが望ましいので何も考えずに”.”,”*”,”-“などで表すことをお勧めする。
この時、例えば初期盤面に対して、■のブロックを中央に落としたsfenは以下のようになる。
sfen 10/10/10/10/10/10/10/10/10/10/10/10/10/10/10/10/10/10/4..4/4..4 – 1
次に、指し手文字列を考える。
これは、ブロックを配置する座標と、回転角で表現する。(ブロックを上から落としてきて配置するまでのキー操作のようなもので表現しても良い) これについては各自考えてみて欲しい。
ところが、テトリスの場合、次のブロック(next)が見えている。これは、棋譜として表現されていなければならない。なぜなら思考エンジンは、このnextを思考に使うからである。そこで、”position”文字列として”next”が付与されていることを考える。nextとbestmoveの指し手が交互に付与されており、かつ、nextは2つのブロック見えているとする。
いま、初期盤面でnextとして赤いブロックが2つ見えていた(rr)とする。そして、その赤いブロックを(4,17)の地点に1回転させて配置したとする。この時、その次に送られてくる”position”文字列は次のようになる。nextには、赤と黄色のブロックが見えている(ry)とする。
position startpos moves rr r4-17-1 ry
bestmoveで返した指し手が、次にやってくるposition文字列の末尾に追加され、さらにnextが付与されてやってくる。
USIプロトコルではスペースを文字列の区切りに使うので、1つの指し手の途中にはスペースは含めないように仕様を策定されることをお勧めする。
麻雀について
麻雀についても同様に考えられる。
自分の開始時の牌譜をsfenで送り、そこからの指し手(どの牌を切ったか)をbestmoveで返していく。
ただし、対局の時の状況(東1局-親番など)やドラなどの条件を与える必要がある。これらの付加情報は、牌譜に含まれていて欲しいので、それらの情報をスペースを含めずに何らか表現して、sfen文字列に含めておく。
USIプロトコルでは、”position”コマンドは、startpos(開始局面)からのmoves(指し手)によって与えられる以外に、sfen(任意の局面)からのmovesによって与えても良いことになっている。
例えば、将棋の開始局面から76歩と指した局面は、次の2通りに表現できる。
position startpos moves 7g7f
position sfen lnsgkgsn1/1r5b1/ppppppppp/9/9/9/PPPPPPPPP/1B5R1/LNSGKGSNL w – 1 moves 7g7f
麻雀の場合、開始局面の牌譜は固定ではないので、必ず後者の形式が用いられることになる。
対局サーバー、対局スクリプトについて
さて、プロトコルだけ定義して、対局サーバーや対局スクリプトがないと何も便利ではないので、対局サーバーや対局スクリプトをいくつか紹介しておく。
USI対応エンジンの自己対局 – やねうら王Wiki
https://github.com/yaneurao/YaneuraOu/wiki/USI%E5%AF%BE%E5%BF%9C%E3%82%A8%E3%83%B3%E3%82%B8%E3%83%B3%E3%81%AE%E8%87%AA%E5%B7%B1%E5%AF%BE%E5%B1%80
自己対局サーバー、対局スクリプトを用いる利点について
このような対局スクリプトを用いる利点として、開始局面集を指定できるということである。開始局面集とは、1つの局面(棋譜)が1行に書いてあるテキスト形式で、例えば、将棋で開始局面から76歩と指した局面ならば、以下のいずれかになる。(さきほど上で書いたものから、”position”という文字列を取り除いたものである。)
startpos moves 7g7f
sfen lnsgkgsn1/1r5b1/ppppppppp/9/9/9/PPPPPPPPP/1B5R1/LNSGKGSNL w – 1 moves 7g7f
このような開始局面が指定できると何が嬉しいのかと言うと、例えば将棋では開始局面が平手の初期局面に固定化してしまうと、初期局面まわりでの戦型選択で、エンジン間の相性が出てしまう。このようなエンジンの相性に悩まされず、本当の棋力を計測したいので、初期局面からはいくらか進めた形勢が互角の局面を1万局面ほど用意して、そこから対局を開始させるのが普通である。
そのような機能が自己対局サーバー、自己対局スクリプトには備わっているのである。
2つ目の利点として並列対局の機能である。いまどき、CPUは64コア128スレッドとかが普通になってきているが、128スレッドあるなら128並列対局させたいわけで、対局スクリプトには普通、そのような機能が備わっているのである。これにより、128倍ぐらい早く計測が終わるのである。
将棋AIは、現代では、レーティングの計測結果を頼りにして探索部を調整するのが普通なのであるが、その時にわずかなレーティング差しかないことがあり、通常、3000局以上対局させるのである。そのためには並列対局は必要不可欠な機能なのであるが、これを自分で実装しようと思うとわりと骨が折れる。このためだけに新規のゲームAIでUSI-Xプロトコルを採用して、上で紹介したような自己対局スクリプトを用いる価値は十分にあると思う。
まとめ
USI-Xプロトコルを提案して、その実際のゲームAIに適用する方法、対局スクリプトなどを紹介した。
新規のゲームAIの対局プロトコルを考える時に参考にしてもらえればと思う。
またUSI-X対応の対局スクリプト、対局サーバーはまだ十分整っているとは言えない状態なので、もっといいものを作ってもらいたいし、新たに対局スクリプトや対局サーバーをつられた方は、そのURLをコメント欄でお知らせいただければと思う。
DVDのVがVideoからVersatileになったような感じのSですね 🙂
それだ!!
DVD-ROM, DVD-R, DVD-RW, DVD-RAM, DVD+R, DVD+RWにDLとか、訳わかんなくなってくる流れですか?(違w
ウォーゲーマーなので、1手番に複数の駒を動かせるか気になります。(バックギャモンもか)moves 句を複数書けばいいですか?
あと、ダイスやカードを中立サーバにもらいたい……とか?
人対人のウォーゲームやボードゲームではVASSALが標準になってますが、プロトコル仕様は存じません……。
ttp://wargamejapan.jp/vassal/
> 1手番に複数の駒を動かせるか気になります。
USIプロトコルでは 最善手は bestmove XXX ponder YYY (ponderというのは相手の予想手の意味)という形式で書くので指し手がスペースで区切られているとまずいです。(次のtokenと誤認したりして)
そこで、1手で複数の駒が動かせる場合は、スペースで区切らずに、ハイフンなどで区切ってやる必要があるかと思います。カンマで区切っても問題ないです。(スペースでなければ何でも良い)
例えば、バックギャモンであれば、
bestmove B12->W10,B12->W11 ponder YYY
みたいな感じで1手の指し手として「B12->W10,B12->W11」のように書いてしまうのが人間的にも読みやすいのではないでしょうか。
あ、でも、これだとparse少し面倒なので「B12>W10,B12>W11」とか「B12-W10,B12-W11」とかにしたほうが良いかもですね。
素晴らしい!