Bonanzaの駒の価値はどこに書かれているのか その1
Bonanzaで駒割を計算するときの、駒の価値はどこに書かれているのかというのは、簡単なようで少しトリッキーです。今回はこの問題について説明します。
まず、駒自体の価値は、param.hでdefineされています。
#define DPawn 87 /* 174 */ #define DLance 232 /* 464 */ #define DKnight 257 /* 514 */ #define DProPawn 534 /* 621 */ #define DProLance 489 /* 721 */ #define DSilver 369 /* 738 */ #define DProKnight 510 /* 767 */ #define DProSilver 495 /* 864 */ #define DGold 444 /* 888 */ #define DBishop 569 /* 1138 */ #define DRook 642 /* 1284 */ #define DHorse 827 /* 1396 */ #define DDragon 945 /* 1587 */ #define DKing 15000
param.hというファイル自体は、実は自動生成されるファイルで、棋譜からの学習時に、学習した駒の価値を書きだすコードが書かれています。(learn2.c)
ゆえに、param.hというファイルを直接編集したところで次回の学習のときに上書きされてしまいます。
さて、これらの値はどこで使われているかと言うと、ini関数(ini.c)で次のようにp_valueの初期化に使われています。
p_value[15+pawn] = DPawn; p_value[15+lance] = DLance; p_value[15+knight] = DKnight; p_value[15+silver] = DSilver; p_value[15+gold] = DGold; p_value[15+bishop] = DBishop; p_value[15+rook] = DRook; p_value[15+king] = DKing; p_value[15+pro_pawn] = DProPawn; p_value[15+pro_lance] = DProLance; p_value[15+pro_knight] = DProKnight; p_value[15+pro_silver] = DProSilver; p_value[15+horse] = DHorse; p_value[15+dragon] = DDragon;
見ての通り、p_valueが駒の価値が入っている配列です。p_valueのpはpieceの頭文字で、valueは「値」ではなく、「価値」の意味でしょう。こうやって、変数名の意味を正しく理解するとソースの読解がしやすくなります。
さて、15というオフセット値が加算されているのは、Bonanzaでは駒をsigned(符号型)で表現するため、先手の駒は1〜15であり、後手の駒は-1〜-15という負の数になります。ゆえに、本来なら p_value [ abs(piece) ]と書くべきところですが、保木さんは、このabsにかかるコストが許せなかったのでしょう。ゆえに、absをせずとも、先手と後手の駒の価値を直接求められるように 15というオフセット値を加算するようにしてあるわけです。
ちなみに、後手の駒に対するp_valueの値も符号はマイナスではなく、プラスです。
このことは、set_derivative_param関数(ini.c)を見ればわかります。
p_value[15-pawn] = p_value[15+pawn]; p_value[15-lance] = p_value[15+lance]; p_value[15-knight] = p_value[15+knight]; p_value[15-silver] = p_value[15+silver]; p_value[15-gold] = p_value[15+gold]; p_value[15-bishop] = p_value[15+bishop]; p_value[15-rook] = p_value[15+rook]; p_value[15-king] = p_value[15+king]; p_value[15-pro_pawn] = p_value[15+pro_pawn]; p_value[15-pro_lance] = p_value[15+pro_lance]; p_value[15-pro_knight] = p_value[15+pro_knight]; p_value[15-pro_silver] = p_value[15+pro_silver]; p_value[15-horse] = p_value[15+horse]; p_value[15-dragon] = p_value[15+dragon];
一見すると、(pawnの値は1ですから) p_value[15]の値がセットされていないかのように見えますが、int関数で最初に次のようにゼロ初期化されているので心配ありません。
for ( i = 0; i < 31; i++ ) { p_value[i] = 0; }
つづく
SEEの高速化について
私は最近何をしているかと言うと…正直、あまりコンピューター将棋の開発はやっていないのですが、まあビールを飲みながらテレビで野球観戦をするような程度の軽いノリでソースコードをいじくりまわして、ああだこうだ言いながら鑑賞(?)するのが趣味です。
最近のマイブームは、Bitboardで利きを計算するコードについての研究でして、どうもうまくやれば、Bitboardでやる利きの計算は非常に軽くて済み、これを利用した評価関数や、SEE(Static Exchange Evaluation : 駒の取り合いの静的な評価)の高速化など、さまざまな恩恵があるようです。
例えば、生成したすべての指し手に対してオーダリングのためにSEEの値を計算するコストって結構馬鹿にならないのですが、
1) 敵の利きのないところへの移動・駒打ちはSEEの値 = 0 なので、利きのBitboardがあれば指し手生成のときに
・gen_drop_SEEisZero
・gen_drop_SEEisNotZero
のようにして指し手生成関数を分離たりして、高速化を図ることができます。
2) 類似局面のSEE値の計算を簡略化。
これについては解説が長くなるので別の機会にでも。
どうも、指し手のオーダリングのためのSEEの計算は、うまくやれば10倍ぐらい速くなりそうです。特にモンテカルロ型のコンピューター将棋では、SEEオーダリングのコストが馬鹿にならないので、この部分が高速化できればplay outの回数が劇的に増やせ、レーティングを押し上げることが出来るのではないかと思っています。
CSA形式のデータ書き出し部 解説
さて、今回からはCSAファイルの書き出し部について解説していきます。
と言っても、「CSAファイルの書き出し」の記事は誰も期待してませんよね。
CSAファイルの読み込みにしても、棋譜からの学習のときにCSAファイルを読み込むのにいる程度。
LAN対戦はUSIプロトコルに対応させて将棋所を使うほうが楽でしょうし、CSAファイルの書き出しもデバッグのときに局面を出力できればいいかな程度。市販の将棋ソフトでなければサポートしなくても全然困りません。
ということで、Bonanzaの「CSAファイルの書き出し」の解説は、誰も期待していないと思うのでささっと終わらせます。
BonanzaのCSAファイルの読み込みのときに解説しましたが、CSA_headerというのは記録されている開始局面のことでして、out_CSA_header (csa.cに実装がある)とは、すなわち現在の局面をCSAファイルに出力する関数になります。
そのあと、指し手をCSAの指し手文字列に変換する関数が str_CSA_move( move ) でして、これで変換した文字列をfprintfで書きだしていけば、それでCSAファイルが完成します。
csa.cにあるout_CSAという関数の実装がちょうどそんな感じになっていて、この関数を見れば使い方がわかるんじゃないかなぁということで、CSA書き出し部の解説はおしまい！
探索木のvalidatorを書こう!! その7
前回の問題の解答を。
配列、Board[sq]上に先手玉が二つあるとき、1)〜10)のどこに引っかかるでしょうか。
Bonanzaでは、玉のBitboardというのは存在しなくて(BB_HDKのように他の駒と合成されたBitboardは存在する)、先手玉の位置はSQ_BKINGという変数(実体はdefineマクロですが)が保持しています。
ということは、盤上に先手玉が二つあっても、前回の10)の
if ( BOARD[SQ_BKING] != king ) { DOut( "SQ_BKING" ); }このチェックは抜けてしまいます。
また、7)でBitboard同士の冗長性を確認しようにも、そもそも玉はBitboardとして持っていないのでこのチェックにも引っかからず…。
また同様にBitboardとBoard[sq]との整合性をチェックする8)もすり抜けてしまいそうです。それ以外にはチェックに引っかかりそうな項目はありません。
困ったようですが、8)に一つトリックがあって、BB_BKINGという玉の位置を表現するBitboardを即席で作ります。
次のマクロが用意されています。
#define BB_BKING (abb_mask[SQ_BKING])
ゆえに、8)のチェックで、王のBitboardとBoard[sq]との整合性がチェックできるということです。
自分でvalidatorを書くときに王が二つあるかのチェックは忘れてしまいがちなので注意を促すために書きました。
以上でBonanzaのvalidatorの解説は終わりです。
探索木のvalidatorを書こう!! その6
今回はexam_bb(debug.cのなかに書かれている)を見ていきます。
exam_bbのbbとはBitboardのことで、Bonanzaの保持しているBitboard盤面の正当性をチェックする関数です。
チェックしている項目は以下のものです。
1) 手番が0か1であること
2) 持ち駒の使っていないビットが0であること
3) 盤面を表現するBitboardにおいて、使っていないビットが0であること
4) 先手の歩が1段目(後手なら9段目)にないこと
5) 先手の桂が1,2段目(後手なら8,9段目)にないこと
6) 駒数のチェック。盤上のX + 手駒のX = 駒Xの最大数 - 駒箱のなかのX が成り立つか。
7) 冗長に持っているBitboardの内容が正しいか。例えば、BB_HDK(馬+龍+王のBitboard)は、それぞれのBitboardを合成(bitwise or)したものに等しいか。
8) Board[sq] (81マスそれぞれの駒を格納している配列)の値は、Bitboardの内容と矛盾していないか。
9) 駒割が正しいか。
10) 局面のハッシュ値は正しいか。
4),5)だと香が1段目(後手なら9段目)にないかというチェックが抜けているようですが、実際抜けています。書き忘れだと思います。
6)は、次のように書かれていて、PopuCount(1になっているbitの数を数える)を使ってあるのでそこそこ高速です。このようにexam_bbはそこそこ高速性を意識した書き方になっていて、デバッグ時に、全探索ノードから呼び出すことも視野に入っています。
/* number of pieces */ BBOr( bb, BB_BPAWN, BB_WPAWN ); BBOr( bb, BB_BPRO_PAWN, bb ); BBOr( bb, BB_WPRO_PAWN, bb ); npawn = I2HandPawn(HAND_B) + I2HandPawn(HAND_W) + PopuCount(bb); CheckNum( pawn );
9)の駒割は、Bonanzaではmake_moveのときについでに駒割も差分更新しているので、9)では駒割を再計算したものと一致するかを確認しています。10)についても同様です。
exam_bbで行なっている処理は以上ですべてです。
さて問題。
配列 Board[sq] 上に先手玉が二つあるとき、1)〜10)のどのチェックに引っかかるでしょうか。
探索木のvalidatorを書こう!! その5
少し話が脱線してしまいました。
だいたいにして、大学の輪講や、勉強会なんかでは1時間ぐらいでやっちゃうようなことをこのブログでは10回ぐらいに細切れに分けてお送りしております。スローペースすぎてすみません。
毎日10分〜15分程度、こうやって少しずつ記事を書くことによって私は自分のコンピューター将棋開発のためのモチベーション維持などに役立てております。
原則的にこのブログの記事は書きなぐり状態なので読み返してもいませんし、誤字脱字はもとより、内容的な間違いも多々あるでしょうけども、まあ誰かのお役に立てていればと思い、公開しています。(内容的な間違いはコメント欄で教えていただけると幸いです。)
それでは今回はexam_tree (valid.cのなかに書かれています) 関数をざっと見ていきます。
この関数は、探索木の正当性をチェックするための関数です。
駒の枚数を数えたりするのですが、飛車のトータルの枚数は2とは限りません。飛車落ちのような場合1になります。足りない1枚はどこに行くのかというと、駒箱であります。
ということは、駒落ちに対してもきちんと正当性をチェックする関数を書こうと思うと、盤面の初期化時に事前に手合いを確認して、駒箱に何枚の駒が入っているのかをカウントして記録しておく必要があります。
npawn_max ← 駒箱の駒を含めた歩の枚数(4)
npawn_box ← 現在、駒箱に入っている歩の枚数
※ "pawn"のところには、駒の名前が入ります。銀ならsilver、金ならgoldと言った感じです。
盤面初期化時(ini.c)にて、npawn_boxを更新しているのは、そういう理由によるものです。
しかしexam_treeのほうでは、アバウトなチェックしか行なっていません。これは先にも申しましたように、exam_bbのほうが指し手生成などのバグをチェックするためのvalidatorで、exam_treeは、外部から読み込んだファイルなど、外部要因による不正な盤面をチェックするためのvalidatorという性格から来るものだと思います。
よって、exam_treeのほうでは、npawn_maxを超えていないことはチェックするのですが、そのときnpawn_boxは考慮されていません。つまり飛車落ちで飛車が2枚あっても、exam_treeのチェックには引っかからないということです。
あとnpawn_boxはグローバル変数になっています。
本当は、ここをグローバル変数にしてしまうと思考ルーチンを複数同じプロセス空間で走らせるときに問題になったりするのですが、「まあそんなことはしないからどうでもいいや」ということなんだと思います。気になる人は、Treeクラスに含めればいいと思いますが、その分速度が犠牲になります。
私はnpawn_boxなどは盤面クラスのメンバー変数に持たせていますが、リリース時には、その部分のコードはコメントアウトされるように #ifdef で書いています。
ともかくexam_treeで行なっているチェックは
1) 手駒の歩+盤上の歩が npawn_maxを超えないか。
というようなチェックをそれぞれの駒種に対して。
2) 2歩になっていないか。
3) 行き場のないところに駒がないか。1段目の歩、1,2段目の不成の桂
4) 手番側が相手の玉を取れる(直前の指し手が非合法手であったということになる)
の4つです。
また、exam_treeは探索中に呼び出すためのものではなく、局面読み込み時にしか呼び出してありません。
デバッグしたいときにexam_treeを明示的に呼び出すことはあるとは思うのですが、しかし上記4)のチェックのために次のコードが書かれていて、
if ( InCheck( Flip(root_turn) ) )
{
str_error = str_king_hang;
return -2;
}このコードですと、root_turnは探索開始局面を意味しますから、root_turnが適切に設定されている状況、すなわち、探索開始局面からしか呼び出せないことになります。(探索中は、Bonanzaは明示的には手番を持っておらず、先手用のコードと後手用のコードが分かれているので現在プログラムのどこを走っているかという状態が、現在の探索ノードの手番を表現していることになります。)
もし探索ノードでのデバッグのためにexam_treeを呼び出したいならば、
1) exam_treeを先手用と後手用のコードを用意するか
2) root_turnを一時的に書き換えてからexam_treeを呼び出すか
3) あるいはexam_bbで我慢するか
という3択になります。
まあ… 3) で我慢してください。だいたいはそれで事足ります。
exam_treeの解説は以上ですべてです。
次回はexam_bbの解説をします。
駒はsignedがいいのかunsignedがいいのか
Bonanzaでは駒を表現する型はs8(singed char)になっています。
さて、問題です。私のように設計した場合、 -(int)UToCap(move) に相当する部分はどう書けるでしょうか？なるべく速いコードを求みます！
私が書いたコードは、次のコードでした。
( ( Cap(move) + (piece_enemy - 1) ) & piece_enemy) | Cap(move)
Cap(move) > 0のときに(piece_enemy - 1)を足せば、piece_enemyのbitが1になるので、Cap(move) > 0のときだけpiece_enemyのbitをもらってこれるなぁというコードです。
これが最速かどうかはよくわかりませんが、そこそこ優秀なコードではないでしょうか。
駒をu8(unsigned char)で持つほうがいいのかs8で持つほうがいいのかは難しいところで、s8で持っていると、駒種を得るときにabsで絶対値を求める必要があったりして、どちらが良いとは一概には言えません。私はBonanzaのソースの全体を通して、トータルではu8のほうがわずかに得かと思ってu8にして設計しています。
u8にする上で問題だったのが上の部分のコードでして、ここが上記のようなコードを書くことで解決できたので、それほど悪くないとは思います。
u8で設計したときに必要になるその他のテクニックをいくつか書いておきます。
u8とs8との比較のため、両者のコードを掲載します。
[先手の駒を後手の駒に]
u8) piece |= piece_enemy;
s8) piece = -piece;
[後手の駒を先手の駒に]
u8) piece ~= piece_enemy;
s8) piece = -piece;
[先手・後手の駒の駒種を求める]
u8) piece ~= piece_enemy;
s8) piece = abs(piece)
[駒種から、手番を考慮した駒に変換したいとき]
// turnは先手なら0,後手なら-1になっている。
u8) piece |= turn & piece_enemy;
s8) piece = turn==black ? piece : -piece;
[先手の駒なら後手の駒、後手の駒なら先手の駒にしたいとき]
u8) piece ^= piece_enemy;
s8) piece = -piece;
[先手・後手の駒を強制的に先手の駒にしたいとき]
u8) piece &= ~piece_enemy;
s8) piece = abs(piece);
[先手・後手の駒を強制的に後手の駒にしたいとき]
u8) piece |= piece_enemy;
s8) piece = - abs(piece);
[0なら0、先手の駒なら後手の駒にしたいとき] ←今回の問題
u8) piece |= (piece + (piece_enemy - 1)) & piece_enemy;
s8) piece = -piece;
[0なら0、先手の駒なら後手の駒、後手の駒なら先手の駒にしたいとき] ← 今回の問題の応用。先後のコードを場合分けして書いていれば、これが必要になることはないのだが…。
u8) piece ^= (piece + (piece_enemy - 1)) & piece_enemy); ← 右辺は、piece > 0のときだけpiece_enemyが得られ、piece > 0のときだけpiece ^= piece_enemyされる。
s8) piece = - piece;
先後のコードを場合分けして書くのであれば、一番最後のは使いませんし、s8のほうはabsが結構出てくるのでちょっと不利かなぁというのが私の判断でした。みなさんはどう思われますでしょうか。
