Bonanza Feliz 中途半端解析ブログ
全国のファン待望のあのBonanza Felizがついに公開!というわけで私も一ユーザとして早速DLしてみました。余の辞書に完全などという文字はどこにもありませんが、まあざっと目を通してみて気のついたことをつらつら書いてみます。
まずはソースを見る前に浪速ともあれ、ということで自己対戦。1手10秒でFelizがv4.1.3に29-15で勝ち越します。暗算勝率検定器によると有意かそうでないかぎりぎりくらい?でもまあ将棋界においては「7戦して4勝した方が強い」という定理が証明されているので、Felizの方が強くなってる、と判断します。
それでは差分を見てみましょう。bashだと
for xxx in *.[ch] ; do
echo "#### $xxx" >> $OUT
diff $BNZ413DIR/$xxx . >> $OUT
done
みたいなスクリプトを実行して出力を印刷します。ざっと見て変更の多いところは
1. 合議関連
2. genchk, mate3
3. hash
4. history
あたり。このうち1.合議は、クラスタ並列派の私としては興味ないし使わないので丸ごとスルー。2.は、あまりちゃんと見てないんですがどうやらLS3600氏ブログでやってた三手詰とか中合いとかあの辺の話らしい。保木さんも「ボナに入れます」とかコメントしてるし、Felizの謝辞にも入ってるのでたぶんそうなんでしょう。この辺も私が個人的にあまり興味ある部分でないので、自分じゃ読まないけど強くなってることを信じて採用決定です。というわけで3.hashと4.historyを読んでみます。
またまたhash_storeを読みだしますが、…あれ?何か変わってる…v4ではpreferに書くときに旧preferの内容をalwaysにコピーしてたんですが(以前の記事 参照)、Felizではやってないですね。う、う~ん…いいのかな?これだとたとえば同じ深さのデータを何回か書くとき、preferのみ、又はalwaysのみ使うことになり、実質1wayに近い動作になるような気がするんですが。ルートに近い深さでいったんpreferにストアしたらその後ずっと居座り続けるし。うーん私の第一感だとv4方式の方がよさそうに思えるんですが。でもやっぱ、自己対戦したらこっちの方が強かった、なのかな。…なんて言ってるなら自分でやれよ、ということで、hash.cをFeliz版と旧v4ベースbonasse版で自己対戦してみましたが、ほぼ互角ですね。なので今は、若干疑問はあるながらもとりあえずFeliz版hash.cのままにしてます。
hash_probeの方もいろいろ変わってますが、変更のポイントがいまいちわかりませんでした。どうでもいい重箱の隅ですけど、l.357はntrans_exactですよね。
次history。私は去年のGPW行ってませんが、棋理の佐藤さんの論文の方式なんでしょうかね。
- βカット/α更新の回数そのものでなく、使用回数に対する比率をみる
- その比率によって、オーダリングだけでなくリダクションの深さも制御する
ということのようです。GPWの後あちこちのブログ等でこの関連の話があって、私もその辺読んではいましたがいまいち何言ってんのか具体的にわかってなかったんですが、やっとわかった気がします。これは言われてみるとたしかにナイスアイデアですね。さすが論文賞。v4->Felizでボナ単体が強くなった要因の八割方はこれではないかな、と思います。
さて、以上を読んで。とりあえずv4->bonasseの変更とかぶるところはなさそうなので、Felizベースにv4->bonasse相当の変更を適用する、というのをやってみました。けっこう量ありそうなので1、2週間くらいかかるかなー、と最初思ったんですが、diff -cとpatchを駆使したら1日でできてしまいました。5/16-19に流していた felizze980x[16]cがそれです。いちおうFelizより(v4ベース)bonasseより強くなってるのでまあおk。
1cは激指とほぼR同じになりました。大会のあたりでは激指が明らかにR的に優位に立ってましたが、今回でほぼ並んだと言ってよさそうです。8コアは私はマシン持ってないし激指も最近出てませんが、8コアどうしでもたぶん追いついてるでしょう。
また、稲庭対策を復活させてまして、1度だけですが当たりました。勝利。ひょっとしてボナンザブラザーズの中で対稲庭初勝利?1度だけではありますが、対稲庭だとほぼワンパターンなので、今後もたぶん勝てるんじゃないかと思います。
その後もう1点高速化ネタを考えついたので入れまして、これが5/21-22バージョン。これも自己対戦で入れる前より強くなってます。これは並列化のときのみ効く変更で、1コア時は影響ありません。この変更でSSEのsfence命令を使ってるため、SSE必須になりました。Pentium IIIより前のCPUでは動かなくなりましたのであしからず。またIntelアーキ以外への移植にも注意が必要です。まあたとえばSPARCならstbar命令みたいな、相当する命令がだいたいありますんでそう困らないはずですが。
話がそれますが、前に会社のSPARCマシンでこっそりボナンザを動かしてみたことあるんですが^^; 動かなかったです。動く動かないの確認だけで、原因調査はしてませんが。今年の対清水さん戦はT2KでOpteronだからいいですが、来年ペタコン使うとかなったらSPARCですよね。いいのかな?ちょっといじれば動くようになるんですかね。
そういうわけで、Felizベース版の現状ソースをここに置きます。ざっと動かしてはみたつもりですが、ちゃんと検証したわけではないので、問題等ありましたらお知らせください。
« Windows対応版うpしました | トップページ | bonasseサポート掲示板 ~ 動作環境について »
「将棋プロセサ」カテゴリの記事
- ボンクラーズの開発過程について書いた記事が掲載されました(2019.03.07)
- 「浅い評価値を深い評価値に近づける学習法」誕生の背景(2016.10.06)
- 塚田九段の対ボンクラーズ練習棋譜を公開します(2013.09.07)
- Puella α ソース公開(2013.08.28)
- クラスタ並列の解説記事を公開します(2013.08.22)
ソース公開ありがとうございます。
1手1秒1コアで100局対局した結果は
bonasse1.2 : Feliz0.0 = 62勝 : 38勝
となりました。(Windows VC++ 32ビット)
NPS値は以下のようになりました。
1. Feliz0.0 : 110K
2. bonasse1.2 SSEなし : 156K
3. 同 SSEあり : 166K
4. 同 PGO後 : 177K
SSE以外の部分(評価関数の差分計算?)が一番寄与が大きいようです。
PGOの方法は以前のBonanzaのMakefileにありましたが、Makefileに以下の文を入れます。
cl-pgo:
$(MAKE) bonanza.exe CC="cl" LD="link"\
CFLAGS="$(FLAG) /nologo /Ox /GL"\
LDFLAGS="/nologo /out:bonanza.exe /LTCG:PGI"
bonanza.exe < runprof
del bonanza.exe
$(MAKE) bonanza.exe CC="cl" LD="link"\
CFLAGS="$(FLAG) /nologo /Ox /GL"\
LDFLAGS="/nologo /out:bonanza.exe /LTCG:PGO"
コマンド"nmake cl-pgo"を行うとPGOされたbonanza.exeが出来ます。
ここでrunprofは以下のようなスクリプトです。
book off
limit time strict
limit time 0 10
tlp num 1
problem 1
quit
問題の局面problem.csaは例えばBonanzaのreadme.txtから取った以下のような局面です。
$ANSWER:+0087KY:+0088KY
P1-OU-KE * * * * * +GI *
P2-KY-KI * * * * * * *
P3-FU-HI * -KI * * -GI * *
P4 * * -KE * * * * * -FU
P5 * +GI * -FU-FU-FU-FU-FU *
P6+FU+HI-FU * * * * * *
P7 * * * +FU * * * * +FU
P8 * * +OU+KI+KI * * * *
P9+KY+KE * * * * * +KE+KY
P+00KA00GI00KY00FU00FU
P-00KA00FU00FU00FU00FU00FU
+
実行プログラムもこちらのブログで公開されてはどうでしょうか。
ユーザーにとってわかりやすいと思います。
私のサイトに実行プログラムだけ置くのも不自然な話ですので。
投稿: bonta | 2010年5月23日 (日) 17時04分
bontaさん、いつもありがとうございます。
バイナリはたしかにここに置くのがベストなんでしょうが、私自身がWin環境知らないしWin自体ほとんどソフト開発では使わないので、検証等ができないんです。変なものを置くのもかえってまずいので私からWinバイナリ公開はしません。ご了承ください。
そもそも、この後は何かきっかけがないかぎりbonasseの新バージョンは出さないと思います。もともとv1.0で終わりのつもりだったのが、Win版の需要があったため対応し、すぐFelizが出たのでまた対応し、となっただけですんで。
投稿: A級 | 2010年5月23日 (日) 19時15分
了解しました。
bonasse 1.2 Windows 32ビット版を下記に置きました。
http://www.geocities.jp/shogi_depot/
投稿: bonta | 2010年5月23日 (日) 19時46分
bonasse__v1.2をcygwinでビルドしてみたんですが、スタックダンプを吐き出しました。
あと、ここに書くのもどうかとは思いますが、bontaさん版のbonasse v1.2は稲庭対策はきってあるのかどうか、うちの不安定な「なんちゃって稲庭」に普通に切れ負けしました。
投稿: floodgate観測員 | 2010年5月24日 (月) 00時10分
floodgate観測員さん、情報ありがとうございます。
cygwinは試してなかったですね。ちょっと調べてみます。稲庭対策はREADME.txtに書いてあるとおりで、Linuxのネット対戦でないと発動しません。
投稿: A級 | 2010年5月24日 (月) 06時19分
> うーん私の第一感だとv4方式の方がよさそうに思えるんですが。
私もそんな気がしますが、細かすぎて計測不可能でした。良く分からない場合は、簡単な方を採用です。
> l.357はntrans_exactですよね。
その通りでした
> 棋理の佐藤さんの論文の方式なんでしょうかね。
佐藤さんには、BonanzaではHistory Pruningが有効だと教えて頂きました。因みに、彼の論文の方式とは異なります。佐藤さんのGPWの内容は、探索結果が良くなるリダクション深さの自動発見を目指すものでした。しかし、Felizでは私が気合いで手動調整しました(汗)。
> sfence
この効果をもう少し詳しく教えて頂けないでしょうか。
xchg命令はフェンスを張ったことになっていないのですか?
それとも、sfenceをあらかじめ使うことによってlock()関数のスピンロックが効率良くなるのでしょうか。
よろしくお願いします。
> SPARC
こいつはbig-endianでは。。。
手元にSPARCがないのですが、ファイルの読み書きで失敗すると思います。
投稿: hoki | 2010年5月25日 (火) 15時21分
sfenceは3つありますが、コンサバめに安易に作ってますんで1つめと3つめは不要かもしれないです。肝は2つめで、これは他のCPUが「hist_triedは半減し、hist_goodは大きいまま」という状態を見ないようにします。これがあるとhist_goodが不相応に大きくなっちゃうので。
SPARCはやっぱだめですか。
投稿: A級 | 2010年5月25日 (火) 22時51分
お返事ありがとうございます。
> 肝は2つめで、
なるほど、だんだんわかってきました。
hist_goodary と hist_tried を 32 ビットの上位と下位にパックするのとだいたい同じということですか?
投稿: hoki | 2010年5月26日 (水) 11時09分
triedとgoodを一つのストアでやる、ってこと?それならもうストアの順序も何もないのでw キャッシュアクセス的にもその方がいいかもですね。
投稿: A級 | 2010年5月26日 (水) 19時11分
ありがとうございます、了解しました。
選手権前に、メモリ共有型並列探索で単一の history テーブルをもつ方法は試してみたのですが、なかなかうまくいきませんでした。PV かベータカットするサブツリーのヒストリーテーブルだけを親に伝播させた方が良いのかと思っていましたが、A 級様が成功されたということなので、暇を見つけてもう一度挑戦してみます。
ここ最近、暇を見つけて Bonasse を弄っています。評価値の差分生成を evaluate() 内で行ったのがとても良いアイディアだったと思いました。過去に差分に挑戦した時には、makemove.c で差分を計算したのですがなかなかうまく行かなかったです。
差分計算で速くなると聞いただけでは何のことか分からなかったのですが、実際にソースコードを示して頂くと本当に良く分かります。
SSE もだんだん使い方が分かってきました。整数型ではあまりご利益がないと勘違いしていたのですが、確かに 128 bit 単位で演算させると速くなりますね。
A 級さんのアイディアを取り入れた Bonanza を、これか作っていきます。ゆっくりと。。。
投稿: khoki | 2010年5月27日 (木) 00時46分
>PV かベータカットするサブツリーのヒストリーテーブルだけを親に伝播させた方が良いのかと思っていましたが
あ、そういう背景があったんですか。元ボナでは、一つのノードに複数スレッドが張り付いてるとき、一つの子スレッドのhistoryしか親に戻らないじゃないですか。あれが前から不思議だったんですよね。今回diffを見ていて目についたので変えてみた、というのも実は動機としてあるんですが。
>過去に差分に挑戦した時には、makemove.c で差分を計算したのですがなかなかうまく行かなかったです
evaluate.cの方でやったのはたまたまというか、makemoveの方もいじるのがめんどかったという怠け心からそうなったんですがw ehashにヒットするケースでの差分計算が減るので結果的にはよかったんでしょうかね。
今の差分計算はkppの二重ループのとこだけ差分化してて、make_listは毎回やっています。実はmake_listも差分計算するコードも作ってみたんですが、効果はいまいちでした。phenomIIでは一割弱速くなったんですが、core i7では5%ほど遅くなってしまったという謎な結果に。このコードではlist0/1をtree_tに持って、makemove.cで差分計算してました。makemoveで毎回やってるとオーバーヘッドが大きい、ということなんでしょうかね。
投稿: A級 | 2010年5月29日 (土) 18時05分
私も ehash にヒットした場合には差分計算を一切行っていないのが良いのだと思いました。
また、list0/1 をソートされたまま更新していくのは難しいという感触を得ています。unmake するたびに list0/1 を巻き戻したり、list0[PLY_MAX][52] 等となって頻繁にアクセスするメモリサイズが増えるのも良くなかったです。
投稿: hoki | 2010年5月29日 (土) 23時24分