Craftyの概略。並列化の手法。YSSの最近の改良点について。2003/07/12 山下 1. Crafty 17.9解析メモ（2000/02/17版） 2. YSSの最近の改良点 1. Crafty 17.9解析メモ（2000/02/17版） Crafty ... 作者 Robert M. Hyatt、コンピュータチェスの1983年頃のチャンピオンのCray Blitzの作者でもある。 データ構造にBitBoardを採用するなど高速化。最新のチェスソフトの技術がふんだんに取り入れられている。 ソースが公開されていて、コメントが詳しく勉強になる。 ---> BitBoardだから高速、というわけではないらしい。 Pentium3M-730MHzで探索速度は Crafty 109,000 leaves/s 308,000 nodes/s ... YSSの3倍も速い。 YSS 71,000 leaves/s 111,000 nodes/s (leaves/sは評価関数を毎秒呼んだ回数、nodes/sは途中の手も含む） 「並列化」 YSSではCraftyの並列化の方法をそっくり真似しています。 PVS(Princiapl Variation Splitting、コンピュータチェス（サイエンス社）に載ってる方法。 通常のPVSはSearchを意味するので混乱しやすい)で探索しています。 前回の最善手だけは1CPUで探索して、その他の手を並列に行う、という手法です。YSSの実装はCraftyとまったく同じです。 Craftyではスレッドが待機するだけのループ、を持っていて、1つのスレッドが 親にも子にも（マスターにもスレーブにも）なる構造になっており、能率よくスレッドを使うようになっています。 並列に探索するには盤面データ構造を複数持つ必要がある。 CraftyではCで書いているせいもあるが、全てをtreeという構造体上に持ち、 構造体のポインタを各関数へ渡すことで並列化を行っている。 YSSでは盤面、利きなどのテーブルを全部C++のクラスの中に放り込んでいる。 クラスにした場合、thisポインタを渡すロスがあるがVC++ではレジスタで渡されるせいも あってか速度低下は1〜2%程度ですんだ。 盤面の構造体を tree local[64]; // 最大64個の盤面構造体を持てる。 として、local[0] に探索開始局面のデータが入るとします。 2つに分割する場合には local[1]、local[2] に local[0] の内容を丸ごとコピーします。 （1つだけコピーすれば良さそうですが、「2つ」コピーするところが味噌です） そして、自分自身も「子」と同じ身分になって並列探索に参加します。 local[0]のはそのまま探索が終わるまで変化しません。 仮に、local[1] が先に探索を終了して、local[2] がまだ探索中の場合、 local[2]は、local[3],local[4] というコピーを作って、自分も「子」になって local[3],local[4] の2つで探索を続けます。 このように再帰？構造の並列探索になります。 余っているスレッドが常に残りのスレッドに協力できるため能率よく 探索することができます。 （片方だけ先に終わって長時間待ち続ける、ということがない） 分割する条件は、Craftyでは残り3以上探索する場合、YSSでは4以上です。 また、Craftyではα値が更新された場合でも、それを兄弟ノードに 伝えていません。非効率だと思ったのですが、YSSで伝えるようにしてみたものの あまり勝率は変わりませんでした。 「並列化のための関数の説明」 int ThreadWait(int tid, TREE *waiting); 探索開始前に、余っているスレッドの個数分だけこの関数が呼ばれます。（waiting=NULL、の親はなし、で) この関数はスレッドに「仕事」が割り当てられるまで無限ループに入ります。 また探索途中で分割する場合、分割した「親」は最後にこの関数を呼んで自分の「子」になります。 ループを抜けるのは ・並列に探索していた子が全部終了したので親が復活 ・最初に呼び出されたスレッドを終了させる場合（全ての探索終了時） の２つです。 void ThreadStop(TREE *tree); スレッドを停止させる。自分に子供がいる場合は、その子供も全て停止させる。つまり再帰になる。 時間切れやα>βとなった場合に呼ばれる。 int Thread(TREE *tree) { // tree は親の盤面構造体。 αβ探索の途中で並列探索したいときにここに来る。（1手以上探索した後で、スレッドが余っている場合） ThreadWait()で待っているスレッドを動作させた後、このスレッド自身もThreadWait()を呼び出して 同じ身分の「子」になり、すぐさまSearchSMP()を呼び出し並列探索を開始する。 このスレッドは「親」を持つ「子」スレッド、という情報を持ってThreadWait()に入るため このスレッドが並列探索を終了してアイドル状態になって、かつ他の子スレッドが 全部探索を終了していたときにだけ、ThreadWait()ループを抜けることが出来る。 そして再び探索を開始するわけである。 他の子スレッドは終了しても「親」である情報を持っていないため、抜けることはできない。 int SearchSMP(TREE *tree, int alpha, int beta, int value, int wtm, int depth, int ply, int threat) { 唯一、並列に探索する関数。この部分でのみ、複数のスレッドが同時に走る。 tree ... 盤面構造体へのポインタ alpha ... α beta ... β value ... αと同じ wtm ... 手番を示す。0,1 と交互になる。 depth ... 残り探索深さ。depth = 0 で末端。 ply ... 現在の探索深さ threat ... パスしたときに「詰む」場合にONになる。 int Search( TREE *tree, int alpha, int beta, int wtm, int depth, int ply, int do_null) { 通常の探索関数（αβ値をひっくり返すnegamaxなので一つだけ） do_null ... NullMoveCutをここに来るまでに一度でも行った場合にON。 NullMoveCutを同一探索手順中に2回以上行わないために。 Craftyでは手の生成はいっぺんに10手、とか生成するのではなく、1手ずつ生成する。 このため、並列探索中は各スレッドが探索が終わった順に1手ずつ生成して探索する。 手を生成する唯一の関数は親の構造体をロックして書き込んでいる。 「同時に2つのスレッドがアクセスしないようにするためのLock()関数」 __inline void Lock (volatile int *hPtr) // volatile は外部から書き換えの可能性があるので { // コンパイラに最適化しないように指定するキーワードです。 __asm { mov ecx, hPtr la: mov eax, 1 xchg eax, [ecx] ; このレジスタとメモリを交換する命令は複数CPUでも動作保障されている test eax, eax jz end lb: #ifdef SMP_HT pause ; HyperThreadingを使う場合、ビジーループの中にこの命令を挟むと良いらしい。 #endif mov eax, [ecx] test eax, eax jz la jmp lb end: } } #define UnLock(v) ((v)[0] = 0) // ロックの解除は0を代入するだけ 「ロックしないハッシュ」 ハッシュにアクセスする際に、ロックをかけると時間がかかります。YSSの場合だとロックをかけると4〜7%遅くなります。 Craftyではこれを解決するために、ロックをかけずにハッシュへの読み書きを可能にする技法が使われています。 詳細はICGAジャーナルを http://www.cs.unimaas.nl/ICGA/journal/contents/content25-1.htm hashのサイズを128bitとして、CPUが64bit単位のread/writeしか出来ない、とします。 hashに登録するデータを W1 W2 (W1がhash値、W2は情報。共に64bit）とした場合に、 登録する時は、 table.W1 = W1 ^ W2 table.W2 = W2 読み込む場合は tW1 = table.W1; tW2 = table.W2; tW1 = tW1 ^ tW2 if ( W1 == tW1 ) 同一局面 ・書き込む場合は、hash値を全てのhashの情報とXORを取って保存。 ・読む場合は、hashの全部の情報を読み出してから、hash値をXORで復元して比較。 こうしておけば、読み込み中に別のスレッドが違うデータを書き込んで 一部分が壊れてもエラーチェックが出来る、ということらしいです。 x86系では32bit単位ですがうまく動作するようです。 例えば、1局面のハッシュで32バイトを使う場合、32byte= 4byte*8 なので 32bitのデータが8つあります。そしてhashのKeyが32bitだとすると、 「書き込み」 data0, data1, ... data7 data7 = data0 ^ data1 ^ data2 ^ data3 ^ data4 ^ data5 ^ data6 ^ data7; HashStore(data0,data1, ... data7); 「読み出し」 data0 = hash_table[entry+0]; data1 = hash_table[entry+1]; ... data7 = hash_table[entry+7]; data7 = data0 ^ data1 ^ data2 ^ data3 ^ data4 ^ data5 ^ data6 ^ data7; if ( hash_key == data7 ) hash値がtableと一致した。同一局面のデータ。 つまり、全てのデータに対してXORをかけてデータが破損していないか調べれば エラーはありえない、ということです。 「2つあるハッシュ表」 Craftyはハッシュが6万局面程度でもそれほど性能が低下しない？ようです。 特徴としてhashテーブルを2つ持っています。 hash_a hash_b ... 容量はhash_aの2倍です。 の2つを持ちます。hash_aが基本で、読むときはa,bの順番で見ます。 hash_aが重要で、より深く探索した結果であるか、または 古い反復深化の結果であれば上書きされます。 すでに別の局面が登録されている場合は、hash_bに情報をコピーして新しい局面を書き込みます。 「基本は全幅探索」 前向き枝刈りなんかはまったくしていません。 全ての手をどかっと全部生成しているだけである。 その代わり、KillerMoveとかHistoryMoveとかで順番を細かく設定しています。 末端では単に駒取り用の関数を呼んで終了。 BitBoardを採用してるため探索速度は非常に速い。駒の利き、といったデータは常には持っていない。 「+0.7手、といった小数点の手の延長（fractional extension）」 手の特性（駒取り、王手など）による小数点の延長（＋のみ）をしています。 1手を60に分けて、60分の1の精度で小数点の延長をかける。(INCPLY = 60) full_extension = (ply <= 2*iteration_depth); 深さ7の探索中には、深さ14まではfull_extensionフラグが立つ。 PVノードでハッシュに手がないなら、1手浅い探索で最善手を求める。 多重反復深化（internal iterative deepening） NULL MOVEは null_depth=(depth > 6*INCPLY) ? 4*INCPLY : 3*INCPLY; 深さが7以上の場合はR=3,6以下ではR=2 NULL MOVEで、放っておくと詰む場合には、 extensions+=(full_extension) ? threat_depth : threat_depth>>1; 通常は-60 +(45) が足される。3/4というかなり大きな延長である。0.75手延長される。 取って、取り返す、という手の場合にはこれも extensions+=(full_extension) ? recap_depth : recap_depth>>1; 0.75手延長される。（駒の種類には関係なく） ポーンを動かしてクイーンになりそうな時は1手延長。 王手をかける手は1手延長。最低でも相手が王手を避けれる手を指せるように？ ---> 疑問 可能な手が1手だけなら、1手延長。 「手の生成の順番」 1. ハッシュの手 2. ＋になる駒を取る手を全部（駒得の順にソートして） 3. Killer手を2手（現在の探索深さで好手になった手（枝刈りが起きた手）を上位2手まで記憶して） 4. HistoryMove 2手（深さに関係なく、今までに好手になった手を上位2手まで） 5. 残りの手を全部 History() 枝刈りが発生した場合、それが他の局面でも好手の可能性が高いために from、to、どこからどこに移動したか、だけを記録していく。 駒を取ったり、ポーンが成る場合は無視。既に駒をとる手は探索しているため。 KillerMoveも同様に格納される。本質的に同じものだから。 history_w[index]+=depth*depth; 探索した深さが深いほど、この手の価値が上がる。 局面の深さ、は関係ない。ただ単に、AからBに移動した手が好手、という情報だけが入る。 例えば、将棋だと25銀(26)と、ぼんやり銀が上がる手が好手だ、とした場合、 あらゆる深さで25銀を試す。乱暴なようだが有効・・・らしい。 探索した深さが深いほど好手の得点が上がる。 KillerMoveは2手まで持つ。更新するたびに入れ替える。 Historyと違って、ある探索深さのみ、での枝刈りが起きた手を記録していく。 ---> 駒取り、を無視しているので落ち着いたKiller手である可能性が高い。 駒を捨てて、すぐに取り返す手、とかはKiller手にはならない。 NullMove枝刈り 1手パスして見込みがない手を無理やりカットする。 2手浅い探索（パスを1手、とすれば1手浅い）でこれを実行し、 かつ(alpha,beta)を(beta-1,beta)というNULL Windowで枝刈りするために 極めて高速に実行される。 あんまり検証していない。もちろん見落とす場合も多数。要はバランスの問題。 Futility Cut Off (Ver. 17.1では未実装) くだらない手を枝刈りする？ 1手（数手？）指しても、局面の評価値に大きな影響を与えない手を枝刈り。 ---> かなり乱暴 ---> これは現在のα値と実際の評価値の差が大きい場合に、変動が少ない手を読まない （PASSなどは読まない）ようにする手法のようです。つまり派手な駒得に繋がる手を読まないと 現在のα値を更新する可能性が薄いためです。 「コンパイルの仕方」 コンパイル時に NT_i386 を定義するようにする。コンパイル時に SMP を定義すれば、Dualで動く。 さらに CPUS=2 を定義すること。しないと最大CPU数が1になる。 __beginthreadex を動かすために 「C/C++」のコード生成で使用するランタイムライブラリを「マルチスレッド」に選択。 crafty.exe smpmt=2 で2CPUで起動。 WinBoardで使う。ftp://gatekeeper.dec.com/pub/GNU/winboard/winboard-4_2_6.exe "C:\Program Files\WinBoard\winboard.exe" /cp /fcp="Crafty mt=2" /fd="C:\prg\Crafty" /scp="crafty mt=1"/sd="C:\prg\Crafty" 2. YSSの最近の改良点 ・並列化。 同じ局面を探索させた場合、思考時間は1.5倍ほどに高速化されたが 並列の場合、何度も実行させると異なる最善手を返す場合があり、1.5倍の高速化が 棋力の向上に直結はしていない。 自己対戦では0.54〜0.56程度の勝率向上にすぎなかった。 2倍の時間を使えば0.66近く出るのとは対照的である。ただ、対激指2に対しては 1CPU 156勝143敗 勝率 0.521 2CPU 649勝351敗 勝率 0.649 と、極めて効果が出ていると思われる。（まだ検証不足ですが）なお、YSSではrootでの分割は行っていません。 ・駒を捨てる詰めろ、王手で有効な手の生成 ただの王手、をとった場合にn手で詰む手を生成 王手ではないが王の8マスに利きをつけるただ捨ての手で、取ればn手で詰む、手の生成 自己対戦で6割の勝率Up。 ただ捨て詰めろの方がただ捨て王手より計算量が3.6倍ほどかかるのでバランスよく組み込む必要あり。 ・NULL MOVE CUTは6割近く勝率Up R=2,つまりPASSして、かつ1手浅い深さで行っている。（残り深さ6以上ではR=3、なども試したが効果は小さく不明） 自己対戦では YSS NullCut - なし (Nullあり の246勝174敗) 勝率=0.586 勝率 0.58と効果が高いようである。 市販ソフト相手だと、 東大５ NullCutなし T5 の324勝241敗 勝率=0.44 (YSS 3245分 T5 5241分 1.62倍) NullCutあり T5 の161勝181敗 勝率=0.53 (YSS 1943分 T5 3057分 1.57倍) 勝率0.60ほど強くなっているようである。 しかし激指1とでは NullCutなし Geki の203勝208敗 勝率=0.506 (YSS 4662分 激指 4607分) 1.01倍 NullCutあり Geki の248勝213敗 勝率=0.473 (YSS 4978分 激指 4755分) 1.05倍 逆に弱くなっている。 （思考時間には市販ソフト側に1手2秒の＋があるのでYSSの方が時間を使っている） ・LAN経由での連続対戦機能。ノート1台でも寝ている間の検証が楽になった。 ・残りの探索深さで生成する手の個数を修正（昔のソースは15手とか読むことを考慮していなかったので） ・確率探索と0.5手延長の類似点。 激指では25%の確率で反復深化を行って、最善手が更新した場合、50%の延長をかけている。 今のYSSに確率探索を組み込むと、1回ごとの反復を25％ずつにしたら、 50％の延長はまさに0.5手延長と完全に同一になる。（Log4を取った場合と同じに） だから最善応手手順はYSSの2n-1、と同じ長さが保障される。 ただそれ以外に、確率の低い手で探索値が上昇してこない場合はすぐに枝刈り されるし逆に確率が50％以上の手はより深く探索される、という2点がYSSの 0.5手と大きく異なる。 Log2 log4 100% Log() = 0 0 50% -1 -0.5 25% -2 -1.0 12% -3 -1.5 YSSでも部分的に確率探索を試しているが速度が10％ほど低下する（駒の取り合いテーブルを常時更新するため） のだが勝率は5割近くなる。もっと調整すれば恐らく確率探索が0.5手延長を抜くと思われる。 ・ちょっとした高速化技法。 手を指す場合に、実際に盤面を動かして同時に利きデータも動かす move() と、利きデータは変更せずハッシュ値を調べる目的のみの hash_move() の２つがあり、それぞれ使い分けている。 ・単純な1手のひもが外れることによる駒取りを防ぐ手。相手の狙いを未然に避ける手 攻め、の手を指すと喰らう反撃要素を取り除く。駒取り、駒当たりをかけて駒を取られる場合。 今までに生成した（実際に指した）手をhash_moveで動かして、その時の最善手を求める。 PASSした時と同じ最善手は無視（既に受けを読んでいるので）王が素抜かれる場合はhashにはない。 11回大会でのHyper-IS戦の△24角。 △21飛と指した時の最善手▲13角成が△PASSした場合の最善と違うので未然に防ぐ△24角、△22角を生成する。 後手：ＩＳ将棋 後手の持駒：角　 　９ ８ ７ ６ ５ ４ ３ ２ １ +---------------------------+ |v香v桂 ・ ・ ・ ・ 角 ・ ・|一 | ・v玉v金 ・ ・ ・ ・ ・ ・|二 | ・v歩v銀v歩v歩v金v桂v飛v香|三 |v歩 ・v歩 ・v銀 ・ ・ ・v歩|四 | ・ 歩 ・ 歩 ・v歩v歩v歩 ・|五 | 歩 ・ 歩 ・ 銀 ・ ・ ・ 歩|六 | 香 ・ 桂 金 歩 歩 歩 歩 ・|七 | ・ 飛 ・ ・ ・ 金 玉 銀 香|八 | ・ ・ ・ ・ ・ ・ ・ 桂 ・|九 +---------------------------+ 先手：COM1 先手の持駒：なし 手数＝77　▲９七香　まで その他には、 「PASSした時の相手の最善手が駒当たりの時は、先に逃げる、ひもをつける、逃げ場所を作る」 「両当たりの場合は、そのどちらも逃げる、ひもをつける」 などがあります。 2001年選手権のIS-KCC戦。△45歩と取れるようにするための △52飛、△61飛、△71銀を見つけれるか。 後手：KCC 後手の持駒：なし ９ ８ ７ ６ ５ ４ ３ ２ １ +---------------------------+ |v香 ・ ・ ・v飛 ・ ・v桂v香|一 | ・ ・ ・v銀 ・v銀v金v玉 ・|二 | ・ ・v桂v歩 ・v金 ・v歩v歩|三 | ・ ・v歩v角 ・v歩v歩 ・ ・|四 |v歩v歩 ・ ・v歩 桂 ・ 歩 ・|五 | ・ ・ 歩 歩 ・ 歩 歩 角 ・|六 | 歩 歩 銀 金 歩 銀 ・ ・ 歩|七 | ・ 玉 金 ・ ・ ・ ・ ・ 香|八 | 香 桂 ・ ・ 飛 ・ ・ ・ ・|九 +---------------------------+ 先手：ＩＳ将棋 先手の持駒：なし 手数＝50 △４二銀 まで 実際の最善手順は▲65歩を未然に避けての△31銀、▲？、△52飛、と指してから△45歩を狙う。 △31銀は未然の駒当たりの逃げで生成され、△52飛は△45歩の攻め、を未然に防ぐで生成される。 コンピュータ将棋の進歩２の問題。48問。 AthlonMP2000+ 正解数=29 max_threads=2 全探索局面数=248349487,(213133/s),1165.2秒。1問あたり24秒。 恐らく問題6は▲13銀だけでなく▲13金も正解。 ▲13金△13王▲21龍△22金打▲25桂打△25歩▲25桂△24王▲46馬△35桂打▲35歩 これで受けなしか。