USIプロトコルのponderhitについて
将棋所のponderについて
http://d.hatena.ne.jp/hiyokoshogi/20111027/1319696413
私が思うに、ponderhitが送られてきたときに持ち時間情報が付与されていないのとかどうなんでしょう。
自分の持ち時間はgo ponderのときに送られてきているのを保存しておけってことですか？それをしないで済むようにponderhitのときに送ってくる仕様には出来なかったのでしょうか。
それに相手の持ち時間はどうなんです？相手はこちらがponderしている間にどれだけ時間を消費したのでしょう？もしかしてgo ponderされたときからタイマーで自前で計測しろってことですか？
通信対局だとサーバー側の時間を返してもらわないとローカルで計測してもズレてきちゃうのですが…。
どうも見てもponderhitは欠陥仕様です。
将棋所はUIとしての完成度が高いだけにUSIプロトコルのこういう欠陥が目につきますね。
あっ。あとUSIプロトコルには、null moveのPVを表示するための記法も欲しいですけども。
合法手じゃない合法手のこと
■ はじめに
Bonanzaの指し手生成/合法手判定は結構ややこしく、ややこしい原因は将棋用語にいくつかの用語が不足しているからなのですが、ここではその不足している用語を新たに定義しながら、自分自身のためのメモを書き残しておきます。
自分用のメモですので文章は著しく読みにくいと思います。(すみません。)
■ 王手がかかっているか、いないのかで分類する
まず、将棋には
1) 自玉(手番側)に王手がかかっている局面
2) 自玉(手番側)に王手がかかっていない局面
の2つがあり、あらゆる局面はこの2つに分類できます。
ちなみに、
3) 敵玉(非手番側)に王手がかかっている局面
4) 敵玉(非手番側)に王手がかかっていない局面
のような分類は不可能で、3)は手番側がその敵玉を取れるはずで、すなわち、敵は直前の王手を無視して回避する手を指さなかったということなのでその直前の指し手が非合法手であると言えます。
では、1),2)について考えを進めていきます。
1)の場合、make_move(指し手によって盤面を次の状態に更新する)のときに、
・動かした駒による直接王手 and/or 動かした駒の影の利きによる間接王手
という動かした駒に連動する王手が発生します。つまり、敵玉に王手になるかどうかは、動かす駒に着目すれば、処理を少し端折れます。
2)の場合、王手を回避する指し手を選ばなくてはなりません。この王手を回避する指し手のことをここでは「回避手」と呼ぶことにします。(この用語が将棋用語として欲しいですね。)
回避手はBonanzaではevasionという名前がついており、GenEvasionならば回避手のみを生成します。
■ 自殺手とは
つまり、1)で自玉が指し手のあとに王手になるパターンは、自殺手を指した場合のみで、ここで言う「自殺手」とは、
A) pinされている駒をpinされていない方向に動かす(空き王手)
B) 王を敵の利きに移動させてしまう
の2通りです。どちらも非合法手です。
■ 回避手とは
同じく2)で自玉が指し手のあとに王手になるパターンは、回避手を指さなかったときです。ところがこの回避手というのは分類がすこぶる難しいです。
・玉が敵の利きのないところに移動する
・王手している駒を取る(両王手の場合はこれでは回避不可)
・合駒を打つ(両王手の場合はこれでは回避不可。また、合駒を打つためには攻撃駒と玉との間に空間がなければならない)
・移動合(移動させて合いをする。ただし、移動させる駒をpinされていない方向に動かすわけにはいかない)
この4パターンにわかれます。
この4パターンのいずれかに該当するのかを調べるぐらいなら、回避手をすべて生成して、そのなかにその指し手が含まれるかどうかを判定するのとさほど変わりません。
よって2)のパターンである指し手が合法手かどうかを判定する簡単な方法は無いと言えます。
1)のパターンですと、ある指し手が合法手かどうかを判定するには、二歩になっていないかだとか、移動できる場所への移動なのかだとか、駒打ちなら打つ先のマスが空いているのかだとか、大駒の移動であれば、移動元と移動先の経路のマスがすべて空いているかだとか…、まあ、Bonanzaのis_move_valid関数の解説のときに解説したことですね。
要するに、Bonanzaのis_move_validは
1)のパターンでpinされている駒かどうかは判定してくれません。自殺手かどうかも判定してくれません。
2)のパターンでの回避手になっているかどうかは判定してくれません。
まず、この2つが大事です。
■ 一般的にpin_checkと言うと..
一般的にpin_checkと言うとA),B)のことで、要するに1)のケースで合法かどうかをチェックすることです。私はpin_check付きのmake_move(pinされていればリタイアする)で高速化を図っているのですが、それは、A),B)のケースを検出して、リターンするという意味で、回避手になっているかのチェックをするわけではありません。すなわち2)のケースではpin_check付きのmake_moveは意味がないわけです。
それでどうするかというと、2)のケースでは実際にmake_moveして、手番側が王手がかかっている状態かを(InCheck関数で)調べて、王手がかかっていればunmake_moveで戻すという方針になります。
■ 合法手生成アルゴリズム
つまり、本当の合法手のみを生成するアルゴリズムは次のようになります。
C) 1)のケースならばpinされている駒をpinされていない方向に動かす指し手を除いて指し手生成。また玉は敵の利きのないところへの移動のみを生成。
D) 2)のケースならば回避手のみを指し手生成
D)はともかくC)でpinされていない方向に動かす指し手なのかどうかを判定するのはとても大変なのでBonanzaではこれらも生成してしまっています。将棋の指し手のほとんどは悪手なので生成してもmake_moveされることもないまま終わるケースが大半ですから、実際にmake_moveして自玉が王手がかかっていればやめよう、という方針です。
■ is_move_validは実は合法手判定ではない
何が言いたいかというと、is_move_validは合法手判定ではなく、make_moveする最低限の条件(必要条件)を満たしているかを判定する関数だということです。is_move_validで非0が返ってくればそのあとmake_moveしていいですが、ただしmake_move後に自玉に王手がかかっていたら、それは非合法手だったということなのでunmake_moveしてくださいね、という使い方をします。
is_move_validはkiller moveなどがその局面で合法かどうかを判定するのに使います。
その局面で合法とはすなわち、
1) is_move_validが非0
2) make_move後に自玉に王手がかかっていない
という2つの条件が必要です。
Bonanzaは、そういう感じのコードが書かれています。
ところで、これをpin_check付きのmake_moveを使うなら、次のようになります。
1) is_move_validが非0
2a) 現局面に王手がかかっていないなら、make_move_pin_check(移動後にその移動させた駒に関連することで王手になったならリタイアする)で動かす
2b) 現局面に王手がかかっているなら、これを動かさずに合法手かどうかを判定しにくいのでmake_moveで実際に動かして、そのあと自玉に王手がかかっていないことを確認する
というようなアルゴリズムになります。
なにせ、合法手判定というのは、結構難しいということです。
■ make_moveのときに相手に王手がかかるか判定しよう!!
次に、make_moveのときに相手に王手がかかったかどうかを判定するという技があります。これは実は簡単で、make_moveする前は相手に王手はかかっていないはずです。王手がかかっていれば王を取られるわけですから、直前の指し手が非合法手であったことになり、非合法手を指した局面から、さらにmake_moveすることはありえないからです。
※ ちょっと説明が前後しますが、is_move_validの条件を満たすならば非合法手であってもmake_moveすることは出来ます。ところが、その局面からさらにmake_moveすることは出来ません。make_moveして、自玉に王手がかかっているとわかればその局面をunmake_moveして戻す作業が必要になります。
さて、make_moveする前の局面では敵玉に王手はかかっていないことはわかりましたので、make_moveによって敵玉に王手がかかるパターンというのは、この動かす駒による直接王手と間接王手のみです。まじめに検出するより条件を端折れるわけです。
■ make_moveのときに敵玉に王手がかかるかどうかを判定するのはそこそこ良いアイデア
すなわち、make_moveのときに、敵玉に王手がかかるかどうかを同時に調べてしまうのはそこそこ良いアイデアだと思います。
ただし、killer moveの場合などでmake_move前の局面で王手がかかっている場合は、make_move後に自玉に王手がかかっていないことを確認して、確認後に王手がかかっていれば即座にunmake_moveするかも知れないので、その場合は、敵玉に王手がかかるかどうかを調べていたのは無駄になります。ゆえに、killer move用のmake_moveなんかも必要だったりして、私のプログラムは複雑怪奇になっていくのでした。
■ make_moveの前で自玉に王手がかかっているかを判定して場合分け
結局、make_move前の局面で自玉に王手がかかっているか、そうでないかで場合わけするのが賢いです。
Bonanzaでは、make_move前の局面で王手がかかっているときに指し手を1つずつ生成する関数はgen_next_move、王手がかかっているときに指し手をひとつずつ生成する関数はgen_next_evasionとなっています。これらはnext.cに記述されており、これらの関数は擬似的なcoroutineとなっています。
3駒関係のパラメーターを計算式で割り出す実験
Bonanzaの3駒関係ですが、このパラメーターを棋譜から学習させたこと、すなわちボナメソがコンピューター将棋のブレークスルーであるように言われていますが、まあ、実際にもBonanzaに関してはその通りなのですが、私は、それより3駒関係という評価関数というシンプルながらそこそこ有効に機能する評価関数を設計したこと自体が偉大なる発明だと思っています。
3駒関係でそこそこ強いということが証明されているわけですから、あとはどうやってこのパラメーターを学習させるのかという話になります。
fv.binのパラメーターを隈無く観察すれば、3駒関係で(大きな)評価点がつくポイントというのは、実はいくつかの法則があることに気づきます。
その法則を分類するとだいたい10個ぐらいの評価因子から成ることがわかります。
その10個の評価因子からfv.binを再構成して、fv.binとの二乗誤差が最小になるようにします。
どれくらい二乗誤差が小さくできるかによって、それらの人間が恣意的に選んだ評価因子が適切に選ばれているのか、評価因子の正当性が証明できるという仕組みになっています。
棋譜からの学習と違い、パラメータ自体は10個程度しかないのですぐに結果が出るところが面白いです。
まあ、そうやってfv.binを全く新たに再構成しようといま私は思っていまして、これが成功すれば棋譜からの学習自体が不要になり、かつ、現状のfv.binでは実践例が少なすぎて点数がついていないようなところにも適切な点数がつきます。
まあ、それでいまのfv.binと比べて強くなるのかどうかはわかりませんが。
というか、いまのfv.bin相当のものが棋譜からの学習以外によって作れたなら、それはそれでボナメソ級の発明ではあると思います。
そういう実験をいま、ビール片手に枝豆をつまみながらやっています。←全然期待できない
そんなわけで、このブログはしばらくお休みします。
Bonanzaの駒の価値はどこに書かれているのか その5
それでは、make_moveでいつ駒割が変動するか考えてみましょう。
指し手を大別すると次の4つに分類されます。
1. 駒を取らない、成らない移動
2. 駒を取らない、成る移動
3. 駒を取る、成らない移動
4. 駒を取る、成る移動
1.は駒割は変動しません。
2.は、成り駒と非成り駒との価値の差の分だけ増えます。
これこそがp_value_pmであり、MT_PRO_XXX マクロが使えることはすでに説明しました。
3.は、相手の駒を自分の手駒にするのですから、交換値(駒の価値の2倍)の分だけ変動します。
これはp_value_exであり、MT_CAP_XXX マクロが使えることはすでに説明しました。
4. は、2.と3.の合わせ技ですね。
結局、make_moveのときは、MT_PRO_XXXとMT_CAP_XXXだけあればいいことがわかりました。
また、unmake_moveのときにこの逆の操作をしても良いのですが、探索時にmake_moveした場合はほぼ必ずunmake_moveで元の局面に戻ってきますから、make_moveする前の駒割の値をどこかに保存しておき、unmake_moveのときにはそれを復元することが考えられます。
駒割を保存するなら、それは探索深さごとに保存してやる必要があります。Bonanzaでは次のような配列を用意して現在の探索深さのところに保存してやる実装になっています。
// 駒割保存用の配列 shogi.h(735): short save_material[ PLY_MAX ]; // make_moveのときに駒割の値を保存する処理 makemove.c(70): ptree->save_material[ply] = (short)MATERIAL; // unmake_moveのときに元の値に戻す処理 unmake.c(29): MATERIAL = ptree->save_material[ply];
また、ここに出てきたMATERIALというマクロは、次のように定義されていて、実体は探索木(treeというstruct)のメンバー変数materialです。
shogi.h(173): #define MATERIAL (ptree->posi.material) shogi.h(658): int material;
このmaterialの型はintになっていて、save_materialのほうはshortの配列となっていますが、これについてはまたの機会に。
Bonanzaの駒の価値はどこに書かれているのか その4
p_value , p_value_ex , p_value_pmについて一通り説明が終わったところで、これらの変数がどう使われているかについて見ていきましょう。
基本的には、盤面初期化(CSA形式のファイルを読み込んだときや、平手盤面で初期化したときなど)に、ini_game関数(debug.cに書かれています)が呼び出されます。
このini_game関数のなかから、eval_material関数(evaluate.cに書かれています)が呼び出されます。この関数は、盤面の駒の数を数えて、p_valueの値を掛け算することで駒割を計算します。例えば、歩に関する駒割であれば次のように計算してあります。
itemp = PopuCount( BB_BPAWN ) + (int)I2HandPawn( HAND_B ); itemp -= PopuCount( BB_WPAWN ) + (int)I2HandPawn( HAND_W ); material = itemp * p_value[15+pawn];
PopuCountは1になっているbitの数を数える関数です。このブログではおなじみですね。
BB_BPAWNは先手側の歩を表現しているBitboard盤面です。BB_WPAWNは後手側。
HAND_Bは先手の手駒。HAND_Wは後手の手駒。
I2HandPawnは、手駒から歩の枚数を得るマクロです。
ここまで、難しいところはありませんね。
すべての駒種に対してこのような処理をしていけば、現在の盤面の駒割が確定します。これがeval_material関数です。
ところが、探索のときに各ノードでこの関数を呼び出すのはすこぶる無駄なので、Bonanzaでは、探索時にはmake_moveとunmake_moveのときに駒割の差分を計算するようになっています。
つづく
Bonanzaの駒の価値はどこに書かれているのか その3
p_value,p_value_exの解説は終わりまして、今回はp_value_pmという配列についての解説です。
だいたい、Cで書かれたプログラムというのは、型がどれもこれもintになっていたりして、型を見ても何をする変数なのかさっぱりわからないのが実情なんですよね。
じゃあその変数が何をする変数なのかを解釈しようと思うと、まず
1.変数名を見て、その意味を考える
2.その変数がどこでどのように使われているかをgrepなどで調べていく
というアプローチになります。
これって、考古学者が昔の言葉を調べるプロセスにとても似ていますね。
言葉は、辞書のようなものがあって、そこで定義されるのでなければ、その言葉が実際にどう使われているかに頼らざるを得ないわけです。意味論的に決定されるのでなければ、語用論によって決定すべしとでも言いましょうか。
まあ、そんなわけでまずp_value_pmという変数名からは、piece value(駒に関する価値)であることは容易に想像がつきますが、最後のpmが少しわからない。
1. promte piece material = 成り駒の価値
2. promote piece - material = 成駒と素の駒(非成駒)との価値の差
だとか、いろんな想像が出来ます。名前からですと1.のように見えますが、この配列がshogi.hで以下のように使われているのを見れば、これが2.の意味であることがわかります。
#if defined(MINIMUM) (中略) # define MT_PRO_PAWN ( DProPawn - DPawn ) # define MT_PRO_LANCE ( DProLance - DLance ) # define MT_PRO_KNIGHT ( DProKnight - DKnight ) # define MT_PRO_SILVER ( DProSilver - DSilver ) # define MT_PRO_BISHOP ( DHorse - DBishop ) # define MT_PRO_ROOK ( DDragon - DRook ) (中略) #else (中略) # define MT_PRO_PAWN ( p_value_pm[ 7 + pawn ] ) # define MT_PRO_LANCE ( p_value_pm[ 7 + lance ] ) # define MT_PRO_KNIGHT ( p_value_pm[ 7 + knight ] ) # define MT_PRO_SILVER ( p_value_pm[ 7 + silver ] ) # define MT_PRO_BISHOP ( p_value_pm[ 7 + bishop ] ) # define MT_PRO_ROOK ( p_value_pm[ 7 + rook ] )
例によってオフセットとして7を足してあるのは、absを避けるためですね。また、p_value_pmの添字としては成駒の値(8以上)は渡さないので、この配列のサイズは15となっています。
この配列の値の初期化は次のようになっています。
for ( i = 0; i < 15; i++ ) { p_value_pm[i] = 0; }
(中略)
p_value_pm[7+pawn] = p_value[15+pro_pawn] - p_value[15+pawn];
p_value_pm[7+lance] = p_value[15+pro_lance] - p_value[15+lance];
p_value_pm[7+knight] = p_value[15+pro_knight] - p_value[15+knight];
p_value_pm[7+silver] = p_value[15+pro_silver] - p_value[15+silver];
p_value_pm[7+bishop] = p_value[15+horse] - p_value[15+bishop];
p_value_pm[7+rook] = p_value[15+dragon] - p_value[15+rook];
(中略)
p_value_pm[7-pawn] = p_value_pm[7+pawn];
p_value_pm[7-lance] = p_value_pm[7+lance];
p_value_pm[7-knight] = p_value_pm[7+knight];
p_value_pm[7-silver] = p_value_pm[7+silver];
p_value_pm[7-bishop] = p_value_pm[7+bishop];
p_value_pm[7-rook] = p_value_pm[7+rook];p_value_exのときと同様なので難しくないと思います。
また、p_value_pmは、非負の値なので後手番ならばマイナスの値にしたい場合などは、次のように手番で場合分けして、マイナス符号をつけてやる必要があります。
evaldiff.c(207): diff += turn ? -p_value_pm[7+ipc_move] : p_value_pm[7+ipc_move];
つづく
Bonanzaの駒の価値はどこに書かれているのか その2
p_valueに関しては、そこから派生する2つの配列があります。p_value_exとp_value_pmです。
p_value_exは、p_valueの値を2倍したものです。歩を相手に取られたときには、p_value_ex[pawn]分だけ駒割のスコアが変動します。「自分の駒を失った損」+「相手がその駒を獲得した得」で、駒の価値の2倍のスコアが変動するからです。この値は「交換値」と呼ぶこともあるようです。
set_derivative_param(ini.c)で次のように代入してあります。
p_value_ex[15+pawn] = p_value[15+pawn] + p_value[15+pawn]; p_value_ex[15+lance] = p_value[15+lance] + p_value[15+lance]; p_value_ex[15+knight] = p_value[15+knight] + p_value[15+knight]; p_value_ex[15+silver] = p_value[15+silver] + p_value[15+silver]; p_value_ex[15+gold] = p_value[15+gold] + p_value[15+gold]; p_value_ex[15+bishop] = p_value[15+bishop] + p_value[15+bishop]; p_value_ex[15+rook] = p_value[15+rook] + p_value[15+rook]; p_value_ex[15+king] = p_value[15+king] + p_value[15+king]; p_value_ex[15+pro_pawn] = p_value[15+pro_pawn] + p_value[15+pawn]; p_value_ex[15+pro_lance] = p_value[15+pro_lance] + p_value[15+lance]; p_value_ex[15+pro_knight] = p_value[15+pro_knight] + p_value[15+knight]; p_value_ex[15+pro_silver] = p_value[15+pro_silver] + p_value[15+silver]; p_value_ex[15+horse] = p_value[15+horse] + p_value[15+bishop]; p_value_ex[15+dragon] = p_value[15+dragon] + p_value[15+rook]; p_value_ex[15-pawn] = p_value_ex[15+pawn]; p_value_ex[15-lance] = p_value_ex[15+lance]; p_value_ex[15-knight] = p_value_ex[15+knight]; p_value_ex[15-silver] = p_value_ex[15+silver]; p_value_ex[15-gold] = p_value_ex[15+gold]; p_value_ex[15-bishop] = p_value_ex[15+bishop]; p_value_ex[15-rook] = p_value_ex[15+rook]; p_value_ex[15-king] = p_value_ex[15+king]; p_value_ex[15-pro_pawn] = p_value_ex[15+pro_pawn]; p_value_ex[15-pro_lance] = p_value_ex[15+pro_lance]; p_value_ex[15-pro_knight] = p_value_ex[15+pro_knight]; p_value_ex[15-pro_silver] = p_value_ex[15+pro_silver]; p_value_ex[15-horse] = p_value_ex[15+horse]; p_value_ex[15-dragon] = p_value_ex[15+dragon];
また、MT_CAP_XXXXというマクロが次のようにshogi.hで定義されています。MTはおそらくMaterial(駒の価値)の意味で、CAPはcapture(捕獲)の意味です。「駒を捕獲したときのスコアがいくら変動するか」という意味がこめられています。
#if defined(MINIMUM) # define MT_CAP_PAWN ( DPawn + DPawn ) # define MT_CAP_LANCE ( DLance + DLance ) # define MT_CAP_KNIGHT ( DKnight + DKnight ) # define MT_CAP_SILVER ( DSilver + DSilver ) # define MT_CAP_GOLD ( DGold + DGold ) # define MT_CAP_BISHOP ( DBishop + DBishop ) # define MT_CAP_ROOK ( DRook + DRook ) # define MT_CAP_PRO_PAWN ( DProPawn + DPawn ) # define MT_CAP_PRO_LANCE ( DProLance + DLance ) # define MT_CAP_PRO_KNIGHT ( DProKnight + DKnight ) # define MT_CAP_PRO_SILVER ( DProSilver + DSilver ) # define MT_CAP_HORSE ( DHorse + DBishop ) # define MT_CAP_DRAGON ( DDragon + DRook ) # define MT_CAP_KING ( DKing + DKing ) #else # define MT_CAP_PAWN ( p_value_ex[ 15 + pawn ] ) # define MT_CAP_LANCE ( p_value_ex[ 15 + lance ] ) # define MT_CAP_KNIGHT ( p_value_ex[ 15 + knight ] ) # define MT_CAP_SILVER ( p_value_ex[ 15 + silver ] ) # define MT_CAP_GOLD ( p_value_ex[ 15 + gold ] ) # define MT_CAP_BISHOP ( p_value_ex[ 15 + bishop ] ) # define MT_CAP_ROOK ( p_value_ex[ 15 + rook ] ) # define MT_CAP_PRO_PAWN ( p_value_ex[ 15 + pro_pawn ] ) # define MT_CAP_PRO_LANCE ( p_value_ex[ 15 + pro_lance ] ) # define MT_CAP_PRO_KNIGHT ( p_value_ex[ 15 + pro_knight ] ) # define MT_CAP_PRO_SILVER ( p_value_ex[ 15 + pro_silver ] ) # define MT_CAP_HORSE ( p_value_ex[ 15 + horse ] ) # define MT_CAP_DRAGON ( p_value_ex[ 15 + dragon ] ) # define MT_CAP_KING ( DKing + DKing )
上の引用部分に出てくるMINIMUMというシンボルについては解説を要するでしょう。
普通のリリース用の実行ファイルを作るときにはこのシンボルを定義しておくことになっています。そうすると、上のようにこのマクロを使った場合、コード上に定数が埋め込まれることになり、少々高速化します。
では、いつMINIMUMというシンボルを定義しないのかというと、それは棋譜からの学習時です。(以下、単に「学習」と記する。) 学習のときには駒の価値は徐々に変動しますから、定数であってはまずいわけです。常に配列の中身を参照するコードになっていなければなりません。
また逆に、MINIMUMというシンボルが定義されているなら、p_valueやp_value_exのような配列を用意しなくともいいんじゃないかと言われるかも知れませんが、そうではありません。
敵の駒を捕獲したとき、敵の駒の番号(歩なら1,香なら2,…)はすぐにわかりますが、その駒の番号によってswitch〜caseで場合分けして交換値をスコアに足し算するよりは、p_value_exのような配列が用意されていたほうが、処理は単純化できます。
ゆえに、
・駒の価値を表現する定数と配列
・駒の交換値を表現する定数と配列
のように、定数と配列と二つ必要で、かつ、学習時には定数ではなく配列のほうを使わなければならないという制約があるので、このようなdefineによるマクロが使われているわけです。
こういう処理をdefineによるマクロを使わずに書こうと思うと案外大変で、高速化のためにはdefineのような文字列置換型の処理は欠かせないと私は思います。世間ではdefineマクロを前時代の遺物のように言われることもありますが、最先端のプログラム(Bonanza)にdefineマクロが多用してあるという事実を我々は直視すべきではないでしょうか。
つづく
