世界コンピュータ将棋選手権のアピール文書はいつから必要になったのか
ちょうどいま世界コンピュータ将棋選手権が開催されているのでアピール文書のことを書いてみたい。
世界コンピュータ将棋選手権のアピール文書はその将棋ソフトのオリジナリティを主張する部分であるが、上位ソフトのアピール文書には革新的なアイデアも多数盛り込まれているので非常に将棋ソフトの開発において参考になることは言うまでもない。
このアピール文書の提出が義務づけられたのは2010年のWCSCからである。2009年1月にBonanzaのソースコードが公開され、様々なソフトがこのソースコードに影響を受け、場合によってはこのソースコードを丸パクリするようなソフトが出るのではないかと懸念されたためである。
…かどうかは知らないが、まあ、そんなところだと私は想像する。
例えば、Spear自体は2009年5月の段階でBonanzaのfv.binと同じ評価関数(パラメータの値は異なる)を用いている。
Spearがfv.binを同梱している件
http://d.hatena.ne.jp/LS3600/20091217
私は上の記事を書いたとき、その経緯は知らなかったが、Spearの作者であるグリムベルゲン博士の以下の自戦記を読むともう少し詳しいことがわかる。
http://www2.teu.ac.jp/gamelab/SHOGI/CSA2009/19csa.html
・もともとSpearはCrafty(チェスの強豪ソフト)を参考にしていた
・BonanzaのソースコードもCraftyを参考にしていた
・そこで(博士は)楽々Bonanzaのソースコードを読み解くことができた
・Spearのデータ構造等はCraftyのものと同じなのでその結果としてBonanzaと非常にソースコードが似ている
という状況があって、その上で、評価関数の形とBonanzaメソッドで学習する部分だけ移植してきたのだと思う。
しかし、翌年の2010年5月のWCSCのアピール文にはこう書いてある。
http://www.computer-shogi.org/wcsc20/appeal/SPEAR/SPEAR.txt
> However, the evaluation function used in Spear is completely different from Bonanza
2010年には評価関数(の形自体)をBonanzaとは全く違うものに変更しているようだ。
ちなみにWCSCでのSpearの成績は2009年は9位、2010年で15位。順位が落ちている。
※ 他のソフトが強くなっていることもあるので、評価関数を変えたから棋力が弱くなり、順位が落ちたとは言い切れないが…。
ちなみに2011年以降、SpearはWCSCには出場していない。評価関数を独自のものに変更したら去年のものより弱くなったし、Bonanzaと探索部が似すぎていて独自性も見いだせないから開発するモチベーションが保てなくなったのかなぁと私は思うのだが、真相は定かではない。
そのへんの経緯はともかく、アピール文書の提出が義務付けられるようになったことは将棋ソフト全体にとって喜ばしいことであるということでこの記事を終りにしたい。
Bonanzaは何故未知の局面に対して弱いのか
どちらも強いプログラムなのに、未知の局面への対応力に差が生じるのは不思議ですね。
棋譜からの学習は、いわゆる「機械学習」の考えを用いていますが、この機械学習にはL1正則化だとかL2正則化だとかがあります。簡単に言ってしまえば、出現しなかった評価項目はゼロするという縛りみたいなものです。この縛りを入れないと、出現頻度が低かった因子(評価項目)に対して棋譜との一致率を上げるためにどこまでも大きな値がつく(発散する)ことがありえます。これを回避したいというのがL1/L2正則化を行う主な動機です。
ところが、このような正則化をしますと、棋譜に現れなかった因子はすべてゼロになってしまいます。Bonanzaで入玉の評価が著しく下手なのも、入玉棋譜が足りていないため、おかしな値しかついていない(もしくは値がつくべきところなのにゼロになってしまっている)のが原因です。
逆に言えば、棋譜に現れないものはゼロになるのでそれを見越した形に評価関数を変形しておくのが、ひとつのテクニックと言えます。
例えば、王の右隣に金がいる形を評価(スコアリング)することを考えてみるとします。
GPS将棋は、王と周辺の駒との相対的な位置関係によるスコアリングもしていますから、ここに仮に50点をつけたなら、88玉78金 = 50点、78玉68金 = 50点 、68玉58金 = 50点…。のように、位置をスライドした形にも同じように点数が与えられたことになります。
もちろん、スコアリングは相対的な位置関係によるスコアリングだけではないので、最終的には、もっとバランスの取れた形になります。
ここで２つの疑問が出てくるかと思います。
1つ目。何故このようになっていると未知の局面に対してうまく適応できるのか。
上のようになっていれば、98玉88金のような棋譜にはほとんど出てこない形に対しても50点というスコアがついているわけで、この形に対して0点がつくよりはいいスコアリングだと言えることはおわかりいただけるでしょう。すなわち、未知の形に対してもうまく対応できることが多いです。
2つ目。何故、このようになっているとL1/L2正則化の影響を受けにくいのか。
L1正則化というのは、評価因子のスコアの絶対値を合計したものをなるべくゼロに近づけようという外的な圧力であると言えます。L2正則化は評価因子のスコアの二乗の合計をゼロに近づけるという意味です。どちらがコンピューター将棋に使う機械学習において適切なのかという問題はありますが、L1であろうとL2であろうとL1.5(1.5乗)であろうと、あるいは他の方法であろうと、基本的な考え方において大差はありません。出現頻度の少ないものをゼロ方向に引っ張りたいだけです。
そこで、ここではL1正則化のときについて考えてみます。
「8段目の玉の絶対位置とその右隣の金」という二駒関係に「玉の右隣の金のスコア」という評価因子を追加した場合を考えてみます。
L1正則化でゼロに引っ張るのは、全評価因子のスコアの絶対値の合計ですから、次の合計が最小化する方向に引っ張ります。
sum = abs(玉の右隣の金のスコア) + abs(98玉88金のスコア) + abs(88玉78スコア) + abs(78玉68金のスコア) + ... 【 minimize → 0 】
このとき、「玉の右隣の金のスコア」と「98玉88金のスコア」等にはゼロへ均等の引っ張られかたをしています。(それぞれに変な係数がかかっていないため) また、「玉の右隣の金」は出現頻度は「98玉88金型」よりははるかに高いため、棋譜との一致率を上げる方向に「玉の右隣の金のスコア」と「98玉88金のスコア」の値を調整しようとしたとき、後者はともかく、前者をゼロにするわけにはいきません。そこで前者に何らかの値がつき、後者は(L1正則化の影響で)おそらくはゼロに向かいます。
このように出現頻度が高く、ゼロでないことが予測されうる因子を分離するというのも、この手の学習に機械学習を用いる上での重要なテクニックと言えます。そんなわけでして、このように因子を細かく分離してあるGPS将棋のほうがBonanzaより未知の局面に対する適応力が高い(期待損失が低い)と言えます。
USIプロトコルへの様々な疑問にお答えします
USIに文句を言うだけ言う
http://d.hatena.ne.jp/merom686/20111217
まあ、USIプロトコルがいろいろアレであることは、いまさら言うまでもないことなのですが、なぜこんなプロトコルがコンピューター将棋の標準になっているかと言うと、将棋所という素晴らしいUIが採用したからに他なりません。
その将棋所の作者はコンピューター将棋を自らは作っておらず、何が必要かあまりよくわかっていないのだと私は理解しています。
まず、将棋所のサンプルについているLesserKaiのソースもかなりでたらめなコードです。例えば、将棋所のサンプルのLesserKaiのソースで、時間をparseしているコードは次の部分です。
void USIUtil::ParseAllTimes(const char *buf, int SorE)
{
string goStr = buf;
if (goStr.find("infinite") != string::npos) {
isInfinite = true;
} else {
isInfinite = false;
int pos = goStr.find(" btime ") + 7; // 7 = strlen(" btime ")
int senteTime = ParseTime(buf + pos);
pos = goStr.find(" wtime ") + 7; // 7 = strlen(" wtime ")
int goteTime = ParseTime(buf + pos);
remainTime = SorE == SELF ? senteTime : goteTime;
pos = goStr.find(" byoyomi ") + 9; // 9 = strlen(" byoyomi ")
byoyomiTime = ParseTime(buf + pos);
}
}驚くべきことに"byoyomi"という文字列が必ず書かれていることを期待しており、"byoyomi"という文字列が書かれていない場合のことは全く考えてもありません。"byoyomi"という文字列がない場合、findは-1を返し、-1 + 9でpos == 8となり、なんと"btime"の直後の数字を"byoyomi"の数値として解釈してしまいます。
まるで、「"byoyomi"は必ず書くものであり、書かなかったときの動作はどうなっても知らんよ」と言いたげです。
将棋所もこれと同じぐらいひどいコードが書かれていることは想像に難くなく、思考エンジン側から少し変な文字列を送るだけで将棋所がクラッシュするのは、このようなエラーチェックの甘さに起因するものでしょう。
解釈できない文字列が来たら、警告を出した上でデバッグ用のログには書き出すだとか、そういう配慮がないので、思考エンジンのデバッグ時に非常に使いにくいです。将棋所はユーザーフレンドリーではありますが、思考エンジンの開発者フレンドリーでは決してありません。
自分で思考エンジンを書いている人ならば、こんなひどい仕様にはしないと思うのですが。
さて、以下では冒頭で挙げたmerom686さんのUSIプロトコルへの不満に対して私の理解を書いておきます。
ponder（先読み）は、それ自体をUSIの仕様から削除すべきだと思う。
予測読みのやり方は、エンジン作者が考えるべき問題だ。
そのやり方を1種類に決めてGUIがサポートしてはならないと思う。
これは使いやすさ以前の問題だ。
ponderの仕様が非常にまずいことは私が以前書きました。( http://d.hatena.ne.jp/LS3600/20111029 ) 結論としては、ponderを使うなってことです。USIプロトコルから削除すべきは私もそう思います。
setoptionで、エンジン側で設定を保存する必要があるのがおかしい。
ファイルに設定を保存するというのは、それだけで相当な手間である。
USI_PonderとUSI_Hashだけ保存しなくていいというのも一貫性がなく面倒だ。
そもそもハッシュサイズを1MB単位で指定するという仕様も変だ。
1MB単位ではなく1byte単位で指定できるようになっているべきということですかね？
単位がMBになっているのは文字数を少しでも減らす、みたいな意図はあるのかも知れません。
1MB単位ではなく2**N byteのNを指定させろという意味でしたら、それは私は反対です。置換表は、通常探索用・詰将棋探索用など複数の置換表を持つことがあり、それぞれを適当な配分で確保したいことがあるので2**Nしか指定できないと困ります。
position
毎回全ての指し手を書く必要があるのは糞。
N手の将棋でやり取りされるpositionのデータ量がO(N^2)になる時点でキモい。
これはまあ、そうですね。入玉模様で1000手ぐらいの将棋ですと特に…。
USIでは、棋譜をSFENという方式で表す。
これは、USIがUCI（チェス用のプロトコル）を元にしているので仕方ないのだが、
日本人は8hがどの升を表すかわからないし、パーサを書くのもプチめんどくさい。
飛車がRookのrで表されるのも、チェスの知識を要求される。
Bonanzaのソースコード上で飛車はRookとなってて、Bonanzaのソースコードに慣れ親しんでいるとそのへんはどうってことはないですが、升の表記がわかりにくいのは同感です。思考エンジンをデバッグしているときに、すごく困ります。
merom686 「対局ごとに必要な初期化」はgameover直後にするのがいいと思うのです。最初のisreadyでは「起動時」「対局ごと」両方やるとして。
対局ごとに必要な初期化はisreadyでやって全然構いませんけどね。isreadyに数時間かかろうと問題ないようなので。isreadyは対局のたびに送られてきますし、連続対戦であればgameoverのあと即座にisreadyが送られてきますので。
go infinite
次にstopが送られてくる前にbestmoveを返してはいけません。
将棋所：USIプロトコルとは
細かいところだけど、不安になるエンジン作者がいたらいけないので。
勝ちを読み切った場合などは当然bestmoveを返していいはず。
返してはいけません。
例えば、次の問題です。(将棋所付属のLesserKaiのソースコードのコメントより抜粋。)
// 人間対エンジンで、エンジンが予想した手を人間が指すとponderhitが送られ、
// その後、まだエンジンが継続して思考している時に「すぐ指させる」ボタンを押すと、
// stopが送られてくる。このように、ponderhitとstopが続けて送られてきた場合、
// ここでは何も返さず、その次のstopに入ったところで手を返す。
実は、上記のコメントに書かれているようなことはうまく実装できません。
ponderhitが起きたときに、ponderのときに指定されていた思考時間設定のまま思考を継続しているわけで、ちょうど思考が終了してbestmoveを返す瞬間にstopが送られてきたからと言って、「何も返さず」というのが無理な話で、「もう返してしまっている」こともありますし、次のstopでもbestmoveを返すのですが、それがそのstopに呼応するbestmoveを返していることにはならないケースがあります。
たとえば次のようなシーケンスを考えてみましょう。
ホスト側 思考エンジン側
go ponder
ponderhit※ 思考エンジン側はponderhitして、思考が終了したのでbestmoveを返す
bestmove XXXX
stop※ ホスト側には思考エンジン側が返したbestmove XXXXが、stopに呼応したもののように見える。
position XXXX
go
bestmove XXXX※ 思考エンジン側はstopコマンドが来たようなのでbestmoveを返すが、これが、ホスト側からすればgoコマンドに対する応手のように見える。
とまあ、bestmoveを返して良いコマンド(ponderhit,stop)を思考エンジン側からの応答を待たずにホスト側が2つ続けて送信してしまうのは、プロトコル上の欠陥であり、シーケンス的に見て破綻しています。
要するにponderhitに続けてstopを送ることがあるというのは仕様上の欠陥だと私は思います。
同様の理由により、"go infinite"で「次にstopが送られてくる前にbestmoveを返して」しまいますと、bestmove返すのと同時にstopが送られてくるとホスト側にはstopに呼応するbestmoveのように見え、次の局面図を思考エンジン側に送信するかも知れないですが、思考エンジン側はそのあとstopコマンドを解釈し、bestmoveを再度返しまして、これがホスト側からすると次の局面図に対するbestmoveのように見えます。
ゆえに、いかなるときであっても「次にstopが送られてくる前にbestmoveを返して」は、いけません。
usinewgame
このコマンドの意味するところがよくわからない。
異なる対局を始めるからハッシュをクリアしたほうがいいとか、
対局が始まったからsetoptionなどのコマンドを受け付ける義務がなくなったとか、
いくつか考えられるが、仕様に明示されていないと使えない。
ぶっちゃけ、なくてもいいコマンドなので、その辺りの説明は欲しい。
対局中に(思考中に)setoptionで置換表サイズを変更されても困りますし、ponder有りから無しに変更されても困ります。対局中に、それらのコマンドが来ないことを保証するために、対局中と非対局中とでは別の状態(決定性有限オートマトン的な意味で)でなくてはなりません。usinewgame〜gameoverはそういう意図だと思います。このへんはまあよく考えてあるなぁとは思うのですが。USIのドキュメントに有限オートマトンで状態遷移図を書いて、この仕様についてもう少し明確にしてあったほうがいいような気は私もします。
以上、ざっとUSIプロトコルについての疑問に答えてみました。思考エンジンを実装する人の参考になれば幸いです。
指し手オーダリングのための高速ソート手法の提案(下書き)
めちゃんこすんごいろんぶんのしたがき
著者 : LS3600 & ひよこ
■ 概要
指し手のオーダリングを行なうために、生成した指し手に対して何らかの手法で点数をつけて、その点数によってソートしなければならない。これをオーダリングと呼ぶ。
本提案は、このオーダリングのときのソートの高速化のための手法を提案するものである。
■ Bonanzaでのオーダリング
Bonanzaでは、gen_next_moveがco-routineになっていて、この関数で指し手を逐次生成するが、駒を捕獲する指し手のあとはhistoryの指し手を生成するフェーズとなっている。
historyとは、指し手の移動元、移動先、駒種、手番の情報を元にうんぬんかんぬん(中略)
Bonanzaではhistoryの指し手はスコアの上位2手しか生成せず、残りの指し手は何のオーダリングもされていない。これは、たいていのノードではhistory2までにbeta cutが生じるし、そこまでにbeta cutが生じなければall node(すべての指し手がalpha値を下回るノード)であることが多いので、オーダリングのためにソートするコストに見合わないとBonanzaの作者が判断したためだと思われる。
しかし著者らの実験によれば、ここでstd::sortをしても自己対戦での勝率はほぼ変わらない。すなわち、オーダリングのためのソートがもっと高速に出来るならば導入する価値はあると言える。
そして、ここで指し手が適切にオーダリングされているなら、それを利用した枝刈り(そのノードであとのほうの指し手ほどreductionの幅を大きくするなど)がしやすくなる。
つまり、ここでソートをなるべく追加コストの少ない形で実現できればうんぬんかんぬん(中略)
■ ソートの要件
ここでは完全にソートされている必要はないと言う点に着眼する。そもそもhistoryの値自体がそこまで信頼できる値ではないので、全体的にそこそこ妥当な並びになっていれば良く、厳密な大小関係を守らなくとも良い。[要検証データ]
ここでのスコアはBonanzaに倣い、その指し手の試行回数tried , その指し手がbestであった回数 good (もう少し詳しく書くべき)とを使って次のように決定する。
score = (good + 1) / (tried + 2)
このscoreの順に指し手をソートしたい。
そこで、高速にソートする手法としてbin sortをすることを考える。
■ bin sortとは
bin sortとは(中略。ググレカス)
いまscoreを0〜65535の範囲にスケーリングするとして、bin sortを適用するには、このscoreからbinのindexへマップしなければならない。
これは、たとえば、次のようにして端数を切り捨ててしまう方法が考えられる。
index = score / 1024;
しかし、この方法だと、小さなスコアばかりのときに適切にオーダリングされない。
そこでscoreの対数をとる方法が考えられる。2を対数の底にするならば、これはbsr(BitScanReverse)が使える。bsrとは(中略。ググレカス)
index = bsr(score);
(中略)
■ 割り算をやめる
割り算は一般的にlatencyの大きな命令で、scoreの計算のときにこれを無くす方法を考える。
(中略)
ゆえに、
index = bsr(good + 1) - bsr( tried + 2 ) + 16;
のように引き算をすることにより、うんぬんかんぬん(中略)
この場合、good,triedが0〜65535の範囲であれば、indexのとりうる値の範囲は、うんぬんかんぬん(中略)
■ 具体的な効果
Bonanza 6をこのbin sortを用いてhistoryの指し手1,2以外もすべてソートするように変更し、また、そのノードで生成された指し手の順番(中略)reduction深さを(中略)したところ、自己対戦では勝率X割になった。これはレーティングで言えばXXXに相当する。
ここに比較のための資料etc(略)
■ 結論
指し手オーダリングのためにソートするコストが見合うかどうかというのは、コンピューター将棋の探索部において非常に大きな課題であり、ソートすることにより可能になる枝刈りもあるが、ソートのコストが見合わないために導入をためらっていた開発者も多い。
しかし、今回、ソートするコストを限りなく小さく抑える手法を開発できたことは著者らの喜びであり、なんやかや(略)
お前らどんどん使ってたもれ(あとで別の言葉で書き換える)
置換表に経路に依存する局面のスコアを書き込まない
将棋では連続王手の千日手は王手をしている側が負けです。だからと言って連続王手のループを見つけた時点で攻め方の負けと判断したのではGHI問題を引き起します。
さて、いま、定跡を自動構築することを考えます。ここで言う定跡とはプロ棋士の棋譜の何手目までという話ではなく、与えられた局面を通常探索で探索した結果をそのまま定跡として書きだすわけです。
これを定跡と呼ぶにはいささか精度の問題があるかも知れませんが、それでも事前に10分でも20分でもその局面についてじっくり考えられるわけですから、その結果をファイルに書きだしておけば、コンピューター側が実戦でその局面に遭遇したときにノータイム(1手1秒)で指せるわけで、これの効果がないと唱える人は居ないでしょう。(プロ棋士の棋譜から構築する定跡DBは別途持っているものとします。)
ところが、このように局面の情報を書きだすときに経路(そこまでの手順)に依存する場合があります。例えば、その局面に至る前の手順を含めると連続王手の千日手が成立してしまうので次の一手が指せないが、しかしその局面に至る前の手順さえなければ、この局面は攻め方の勝ちという場合です。
定跡ファイルに書き出すときに、経路に依存する情報は書き出すべきではなく、その局面自体の勝ち/負けを書き出したいのです。これはどうすればいいのでしょうか？
実は通常使用している置換表に関しても同じ問題があります。普通、置換表には経路に依存する局面のスコアも書きだしてしまっています。千日手で循環していたので、「この局面は互角」だとか書きだしてしまっています。実際は千日手で循環するのは特定の手順でその局面に到達したときだけです。要するに嘘の情報です。
こういう嘘の情報を書きだしてしまうと、置換表に書いてある評価値を信じていいのかという話になってきます。そこで、置換表の値はあまり信じずに、置換表に書きだしてある指し手だけを信じたほうが勝率が上がったりします。
例えばBonanzaでは、non PV node(α==β-1のnode)でしかhashcut(置換表の値を信じてそのノードの探索を打ち切ること)はしません。PV nodeではhashcutしません。
これは置換表の値が信用できないという問題以外の要因もあるのかも知れませんが、ここでは深く追求しないことにします。
ともかく、置換表にどうやればそれが千日手絡みのスコア(評価値)かどうかを書き出せるのかを考えてみます。
まず、α値を更新したときに、それが置換表絡みのスコアであれば、スコアの上位bitを使って「これは千日手絡みのスコアですよ」(本当のスコアは不明ですよ)とフラグを立てます。次にα値を更新したときにも、直前のα値のこのbitが立っていれば、さきほどの千日手絡みのスコアが、本当はもっといい値かも知れないので、この更新されたαも信用できる値ではないという理由で同じく、このbitを立てる必要があります。(細かい議論は割愛)
このようにしてあれば、千日手絡みのスコアが出てきた場合、それが上位ノードに伝播されていきます。
千日手絡みのスコアであれば、置換表に書き出すときに、スコアは書き出さずに指し手のみ書きだすだとか、まあ何かそういうことは出来ます。
ところがこうやって千日手絡みのスコアを置換表に書き出さないと千日手のスコアに汚染されて、ほとんど置換表にスコアが書き出せない状況が起こりえます。こうなると探索効率は悪化します。
そこで、この方法はおそらくまずいのだと思います。(私はこの方法は実際に実装して試していないのでよくわかりませんが、おそらくあまり効率がよろしくないはずです)
よって、千日手によってスコアが汚染される範囲をもっと明確にすることを考えます。
例えば、次のように局面X,A,B,Cがあったとして、Aの局面へ循環している場合を考えてみます。
X→A→B→C→D→A
Dの局面からAへの指し手は千日手を引き起こす手です。3手前の局面と循環しているからです。ゆえに、ここでは「3手前」(-3)という値をDで得られた評価値の上位bitに格納しておくことにします。
Dの上位ノードであるCではスコアが伝播されてきたときに、ここをインクリメント(たとえば上位8bitを用いるならば0x01000000を加算)し、「2手前」(-2)になります。
Cの上位ノードであるBでは同様に「1手前」(-1)
Aでは同様に「0手前」(0)
Xでは同様にインクリメントして 0 になります。つまり、Xの局面ではスコアはこれ以前の手順に依存していないので、Xの局面のスコアとしてはこれは信頼できる値だということです。逆にBの局面でのスコアは1手前の局面と手順が循環しているのでこの値は信頼できる値ではなく、置換表および定跡DBにはスコアは書きだしてはならないと言えます。(Aの局面については正しいスコアだと私は思うのですが、自信はありません。)
循環しているかどうかの判定は、スコアのMSB(最上位ビット)を見れば一発でわかるという仕組みです。
また、この実装はGHI問題を引き起こしません。
定跡DBを自動構築するときにはこのような実装が必要で、また、実戦において通常探索した結果を定跡DBに書き出すことを考えているなら、千日手に依存する局面のスコアを書きだすわけにはいかないので、このように実装してなければなりません。(たぶん)
df-pnの詰将棋ルーチンにもこの方法が応用できるかどうかについてはいずれまた。
「入玉指向の将棋プログラムの作成」の改善案
GPWSで発表された田中哲郎先生の「入玉指向の将棋プログラムの作成」について思うところがありまして、以下にだらだらと書いておきます。なお、本論文は以下のURLから読めるようです。
元の論文のアイデアは、「王の入玉に関する機動性(?)を評価して評価関数に加点しよう」というものでして、玉は左上・真上・右上にのみ進めて、相手の利きおよび自駒がある場所には移動できず、入玉できる経路があるかどうかを調べるというものです。
入玉に関して、入玉を阻止している駒で評価するのではなく玉の入玉経路の有無を評価関数に反映させたところが元の論文の目新しいところで小さな計算量で済む、面白い特徴因子だと思います。
疑問点1) この入玉経路を調べるコストはゼロに近いのか？ゼロに近くなければ、滅多に出現しない入玉将棋のために評価関数の計算コストが増大するので勝率自体は下がるのではないか。
疑問点2) 入玉する場所がどこでもいいというのはおかしいのではないか。盤面の左上とか右上のような隅のほうがポイントが高くなっているべきではないのか。
まず疑問点1)を解消するために、以下ではこの経路探索の発見がすこぶる小さなコストで出来る擬似コードを示し、また疑問点2)を解消するために、疑問点1)で示した擬似コードに基づく改善案を提案します。
■ 入玉経路の探索の高速化
敵の利きは事前にmake_moveのときに利きを表現するBitboardに反映しているものとします。
いま、玉が7段目の中央(5筋)にいるとします。6段目のうち、玉のいける場所は次図のようになります。
□□□■■■□□□
■ = 行ける場所
□ = 行けない場所
これは、ビットパターンで言うと、
次段 = ( (前段<<1) | 前段 | (前段>>1) ) & 0x1ff ;
のようなパターンです。最後の1ffは、演算結果を9マス(9bit)に制限するためのマスクです。
この計算は、テーブルをlook upしても良いでしょう。こうなります。
次段 = next_table[前段];
// next_tableは512byte × sizeof u16 = 1MBのサイズ。
あとは簡単ですね。これをループで回して、入玉できるか見るだけです。
i = 1 << 現在の玉の筋(0..8);
foreach 現在の玉の次の段から入玉だとする段まで
{
i = next_table[i];
i = i & (move_to >> その段のビットパターンが得られるシフト回数 ) & 0x1ff;
if (i==0) break;
}
// iに入玉できる場所を示すビットパターンが得られた
これだけですね。極めて小さな計算量で入玉だとする段のどこの筋に到達できるのかまで調べることが出来ます。
また玉が最下段のときはこのような加点せず、2段目(8段目)より上にいるときにのみ評価関数に加点するならば、調べる段は3〜9段目のみですみますから、これは64bitに収まり、私が以前提案したRBBを用いると片側64bitの盤面を見るだけです。
ゆえに上の処理はBonanza6の評価関数の1〜2%程度のコストで済むのではないかと思います。
■ 入玉できる場合、どう加点するか
仮に最上段まで入玉できるとして、そのときに入玉できる場所によって点数は異なるべきです。
すなわち、さきほど求めた入玉できる場所を示すビットパターンをそのまま加点したいわけです。
score += 入玉評価テーブル[i];
これで済めば簡単この上ないのですが、問題は512通りきちんと棋譜から学習できるかということです。
しかしよく考えると
a) ■□□□□□□□□
b) ■□■□□□□□□
c) ■■■□□□□□□
d) ■□□■□□□□□
a)よりはb)のほうが優れていることは自明であり、a) < b)のような順序関係がなりたちます。同様に b) < c)ですが、b) と d)の関係についてはよくわかりません。隅のほうが評価値が高くなるべき!という原則からすれば4筋よりは3筋のほうが価値が高いはずで b) > d)でしょうか。
まあ、このような半順序関係を利用していけば、棋譜から学習させられなくはないのかも、と思います。(よくわかりません…)
続きは誰かお願いします…(←人任せ)
USIプロトコルのponderの仕様と稲庭対策のこと
昨日の記事に対して将棋所の作者様から直々にコメントをいただいたのでお答えします。
相手の正確な残り時間がわからないということですが、そもそも何のために知りたいのでしょうか。相手の残り時間を知って、それをどういうふうに使うのか、少し考えてみましたが使い道がわかりませんでした。
将棋所の作者様は、非常にクレバーな、頭のいい方だと私は理解しています。将棋所は、必要ならば取り入れるし、自分が不要だと思うものは誰かがいくら要望したところで一切取り入れない。そういうポリシーだと理解しています。一流のソフトウェアというのはそのような頑な意志の存在なくして成立しません。
そこで、私のほうとしましても「いるから、いるのだ!!」ではなく、何故必要なのかについて、納得していただけるような、論理的な説明をしなくてはなりません。しかし、それは結構大変なことで、非常に長文となりますが、お許しいただきたく思います。
まず、コンピューター将棋界には稲庭戦法という相手の時間切れを狙う戦法がウイルスのように流行しております。私は最初、単なるウケ狙いの戦法かと思ったのですが、Bonanza4にも通用しており、世界コンピュータ将棋選手権の決勝でもちらほらと見かけるようになりました。(例えば、今年の大会でのponanza vs 激指)
そこで大会で決勝で勝ち残るためには、すべてのコンピューター将棋の開発者にはこの稲庭戦法への対策を余儀なくされているのが実情です。例えばBonanza6では、稲庭対策のコードが追加されております。普段はオフにしてあるのですが、大会出場用に(コンパイルオプションを変えて)ビルドすれば、稲庭対策を発動します。
このときの前提条件が、「20手を過ぎて相手が歩を一切進めていない」(iterate.cに記述)というものでして、そしてこの条件に当てはまったときには、稲庭用の特別な評価関数(evaluate.cのinaniwa_score)が呼び出されます。この評価関数で、中央に向かって跳ねて行った桂と、5筋の歩が進んでいくことに対して加点してあります。要するに5筋を突破しやすくするための対策ですね。
Bonanza6に対して稲庭対策のコードが入っていることについては、もしかしたら私がこのブログで書くのが初めてかも知れません。あまり話題にはなっていないと思います。しかしコンピューター将棋開発者ならば、みんな稲庭対策には苦慮していて、たとえばBonanzaの稲庭対策の発動条件がわかっているのでわざと20手目まで自陣の歩を突かず、無駄に桂を跳ねさせて、この桂をタダ取りしてしまおうという「稲庭対策の対策」みたいなものも成立するかも知れません。
ともかく、そのように稲庭対策が決勝で勝ち残るコンピューター将棋のための必須課題となっているのが現状です。このときに、(大会に将棋所を使って参加しているとして)相手の正確な残り時間を調べたいということは十分考えられます。
「相手が残り時間を消費しているなら稲庭戦法ではないな」だとか、「相手が自分より残り時間を残していないならば稲庭戦法で来られても大丈夫だな」だとか、そういう相手の持ち時間を考慮に入れた思考時間制御がしたいかも知れません。(このへんはそれぞれの開発者ごとに考え方が違うと思いますが、そういうことをしたい人もいるかも知れないという話です。)
そのときにサーバータイム(サーバー側の計測値)で相手が直前の指し手で何秒使ったのかというのを知りたいというのは十分に考えられます。
あと将棋における思考時間制御は非常に難しく、一言で言うと現在のノードが安定しているノード(取り合いなどが少なく、探索することによって評価値が変わりにくい)なら早めに思考を切り上げ、さもなくば思考時間を投入するというのが基本方針ではあるのですが、このときに相手の残り時間との正確な差がわかれば、「これくらい形勢が開いていれば、こちらのほうが思考時間も少ないことだし少しぐらい早く指して形勢互角ぐらいに戻ったとしても仕方ないだろう」のような判断が出来ます。そういうタイプの思考時間制御をしたい人がどれくらい開発者のなかに居るのかはわかりませんが、ともかく、そういう形の思考時間制御もアリです。(私はそういうタイプの思考時間制御をしようと思っています。)
これは、チェスクロックを用いて人間vs人間で将棋を指すのに慣れている人ならば、そういう感覚を理解してもらいやすいと思うのですが、相手のほうが時間を残している場合、終盤で逆転されかねないので、同じぐらいの棋力であれば、序盤はサクサク指したほうが得だというのはあります。(序盤でそこまで致命的には形勢を損ねにくいので)
同様に、コンピューター将棋の思考時間制御においても、相手の持ち時間を見て、それをもとに自分の考慮時間を決めるという方式は結構理にかなっていると思います。
これらがサーバータイムでの相手の消費時間を知り合いという理由です。
以下、USIプロトコルについての要望。
それはそうと、ひよこ将棋やSunfishの作者が書いている、「現局面からponderさせてもらえる機能」みたいなものは欲しいです。「bestmove XXX ponder YYY」のYYYを省略した場合、現局面を思考エンジンに送ってきてもらって、go ponderコマンドが送られてくると非常に良いのですが。(そのあと相手が指したときに、stopコマンドとその局面とgoコマンドが送られてくれば。)
