ひよこカルロ将棋v0.15を公開しました。
・5〜10%程度高速化しました。
・モンテカルロシミュレーションの速度を高速化し、また精度面を少し改善しました。
・futilityがうまく機能しないケースがあったので修正しました。
・LMR用のhistory用の値がうまく計測できていなかったので修正しました。
futilityとLMRのバグを修正したらiterationがあまり回らなくなりました。これは多分バグだと思うのですが、元のソースから大幅に書き換えてしまっているのでこの原因を突き止めるのは大変なのであとまわしにします。
いまのままでも前のバージョンよりは終盤が少し強くなっているのは間違いないので、これをいったん公開しておきます。前のバージョンと対戦させるとそこそこ勝ち越すようでしたのでR1850相当だとは思います。
力戦形ですとアマ初段ぐらいの人だと苦戦すると思います。ひよこカルロ将棋が序盤でもたもたしているうちに穴熊に囲っていいのであればアマ五級ぐらいの人でも勝てると思いますが。
そのへんアンバランスなのが見ていて面白いですね。
コンピューター将棋にだけ通用するソフト、それがひよこカルロ将棋です。
ひよこカルロメソッド
ひよこカルロ将棋v0.16が、やっと初手で76歩を4割ぐらい指すようになりまして、2割ぐらいは26歩で、あとは96歩とか18香とかそういう手も混じっていたりしますが、まあ前よりは格段にマシになったのでどこを改善したのかを以下にざっと書いて、あとモンテカルロシミュレーション部分の全ソースを貼っておくので
・誰か代わりにもっといいものを書いてください
・たぶんどこかバグっているのだと思うので気づいた人は教えてください
というお願いしますメソッドです。(なにがメソッドだ、なにが…)
改善した箇所
・200手までで終局するかしないかを見ていたのを120手にした。あまり長い手数の終局は、指し手の意味がぼやけて、現実的ではないシミュレーションになっていると思ったから。
・120手で終局しないときは無試合として、指し手の試行回数を増やさないようにした。終局していないものはノイズであって、そこから情報を取得しようとするべきではないと思ったから。
・勝った試合に対して、探索開始局面から21手目までの自分の指し手のみを加点した。負けたときには減点しようかとも思ったが、減点とUCTって相性が良くないのではないかと思ってやめた。よくわからない。
・また加点するときは探索開始局面に近いほど大きな重みを掛けるようにした。具体的には、21手目なら1,19手目なら2,17手目なら3,…というような重みを掛けるようにした。探索開始局面から遠いほどその手の探索開始局面への貢献度は低いと思ったから。
以下、モンテカルロシミュレーション部の全ソース。試行錯誤しながら書いているので、デバッグのためのシンボルとか、使っていないコードとかそういうのがいっぱい残っていますが、消すのも面倒なのでそのまま貼っておきます。
#include <math.h> // logとかsqrtとか namespace hiyoko_shogi { // モンテカルロシミュレーションによるLMR historyの初期化 void MonteCarloSimulation::SIM1(Tree* RESTRICT tree , USIListener* listener, s32 timeForMonte) { // USIに情報出力 printf("info string Monte-Carlo simulation start,reserved %d[ms]\n",timeForMonte); tree->init_hist(); // 毎回クリアしたほうが新鮮でいいのではなかろうか。 // 終局までやった回数 u32 playout=0; // 詰みがあった回数 u32 mate_count = 0; // root局面ですべての指し手を生成。 tree->gen_start(); GenMove::gen_all(tree); u32 move_count = (u32)(MOVE_CURR_PTR - MOVE_LAST_PTR); // 生成された指し手の数 // こいつを0〜move_count-1までぐるぐる回す。 // 指し手が100あるとして..基本10回ずつ。んでよさげな手をさらに回数増やして…。 // って話。 // リピート回数。開始局面で指し手を選択して、ひとつ指し手を選び、それを // この回数だけ繰り返す。 const u32 repeat = 10; // const u32 repeat = 1; // デバッグのときは1回で u32 move_index = 0; u32 key; // 指し手のphashのkey s32 good,tried; // keyに対するgoodとtried while(true) { if (playout < move_count * repeat) { // 最初のrepeat回×指し手数 回のシミュレーションにおいては、 // どれを選ぶ必要もなく均等に選べば良い。 move_index = playout / repeat; } else { if ((playout/repeat & 63)==0) // 64*10回=640回ごとに時間をチェックして超えていたら終了。 //if (++playout == 2) // for debug { // このシンボルを定義すると延々とシミュレーションを行ない、その結果を出力する。 // #define MONTE_UCT_DEBUG2 #ifndef MONTE_UCT_DEBUG2 if ((s32)listener->timer->elapsed() >= timeForMonte) #endif { // 一番勝率の良かった指し手を選ぶべきか、 // 一番期待できる指し手を選ぶべきか、 // 一番探索していた指し手を選ぶべきか float max_score = -1; for(u32 i = 0; i < move_count ; ++i) { MOVE_CURR = MOVE_LAST_PTR[i]; if (MOVE_CURR == MOVE_NA) continue; key = Moves::phash(MOVE_CURR,TURN); good = tree->history[key].good; tried = tree->history[key].tried + 1; #ifdef MONTE_UCT_DEBUG2 // デバッグ用に勝率表示。 Moves::print(MOVE_CURR); printf(" : %d / %d \n",good,tried); #endif /* // 一番期待できる枝を選ぶのがいいように思う。ゆえに..UCB1で… float score = good/(float)tried + sqrt(2 * log((float)playout) / (float)tried); */ // 勝率が一番いいものを選ぶ。同じ勝率であれば試行回数が多いものを選ぶ。 float score = 1000000*good/(float)tried + tried; // なんかそこそこ改善された気がする。 if (max_score < score) { max_score = score; move_index = i; } } Move move = MOVE_LAST_PTR[move_index]; #ifdef MONTE_UCT_DEBUG2 Moves::print(move); getchar(); #endif // 置換表の第一エントリーに書きこんでしまう。 Hashes::hash_store(tree,1,value_lower,0,move,0); #ifndef MONTE_UCT_DEBUG2 break; #endif } } // その後は確率のいい指し手を選び10回ずつ試行 float max_score = -1; for(u32 i = 0; i < move_count ; ++i) { // Pi + sqrt( (2 log N) / Si ) // N : そのノードでのplayoutの回数 // Pi : ノードのなかのi番目の指し手のプレイアウト時の勝率 // Si : ノードのなかのi番目の指し手のプレイアウトの回数 // N == playout // Piがそれぞれの指し手の勝率 // Siがその指し手の試行回数 // これを信じて、このまま実装。 MOVE_CURR = MOVE_LAST_PTR[i]; if (MOVE_CURR == MOVE_NA) continue; key = Moves::phash(MOVE_CURR,TURN); good = tree->history[key].good ; tried = tree->history[key].tried + 1; // 0割防止のための+1 #ifdef MONTE_UCT_DEBUG // デバッグ用に勝率表示。 if ( ((playout/repeat) % move_count ) == 0) { Moves::print(MOVE_CURR); printf(" : %d / %d \n",good,tried); } #endif float score = good/(float)tried + sqrt(2 * log((float)playout) / (float)tried); if (max_score < score) { max_score = score; move_index = i; } } #ifdef MONTE_UCT_DEBUG // デバッグ用に回数表示 if ( ((playout/repeat) % move_count ) == 0) { printf("playout = %d\n",playout); } #endif } //printf("playout = %d",playout); MOVE_CURR = MOVE_LAST_PTR[move_index]; key = Moves::phash(MOVE_CURR,TURN); // 駄目な手か? if (MOVE_CURR == MOVE_NA) { assert(false); continue; // この手が選ばれるのはおかしいのだが…。 } // この手で進めてみる。 MakeMove::make_move(tree,MOVE_CURR); if (Attack::InCheck(tree,TURN)) { // 王手が回避できていない // 局面を戻す MakeMove::unmake_move(tree,MOVE_CURR); MOVE_LAST_PTR[move_index] = MOVE_NA; // もうこの手が選ばれることはないようにする。 // MOVE_NAの手は選ばないようになっているからこれで問題ない。 continue; // repeat回のループは抜ける。repeat回まわっても全部MOVE_NAなわけで。 } // この局面から10回playoutさせてみる tree->inc_ply(); for(int simu = 0; simu < repeat ; ++simu) { Move moves[150]; // playoutまでの150手分の指し手 // ルート局面で詰んでいないことはUSIクラスが保証する。 // 直前の局面で1手詰め判定しているので、進めていく局面自体が詰みであることはないことも // 保証される。ゆえに、合法な指し手が存在しないということはありえない。 s32 mated = 0; // 詰んだら5,詰まなかったら駒の多いほうに加点するために1。 Ply& ply = tree->ply; // 2手目からだろう。 for(ply=1+1; ply < 120 ; /* inc_ply()で加算するのでplyを足しては駄目 */) { // Mate判定(現局面に王手がかかっていないときだけね) if (!CHECKED && Mate::IsMateIn1PlyNoMove(tree)) { // 詰んだ if (TURN == tree->root_turn) mated = +1; // あっちの詰み else mated = -1; // こっちの詰み // 詰みが発生した回数を計測。 mate_count++; goto next_playout; } // 200手以内に終局しなかった場合はあまり意味のあるシミュレーションではないので // それについては無視。 // すべての指し手を生成して、合法手を探す。合法手が存在しないことはありえない。 // SSE < 0の手はなるべく指さない。 tree->gen_start(); GenMove::gen_all(tree); // 指し手をランダムに30個選んでSEEの一番高いものを選択。 // 非合法手であれば抽選を繰り返す。詰んでいるかも知れないので注意。 u32 giveup = 0; // 一定回数リタイアしたら、この局面は負け扱いで。 while(true) { // 生成された指し手の数 u32 num = (u32)(MOVE_CURR_PTR - MOVE_LAST_PTR); // これが0ではないことが保証されている。 // 回避手 == 詰みである場合があるのか。 // 通常探索ルーチンだと回避手はすべて生成するから気づかなかった…。 // あと生成されている指し手が1個だけでそれが自殺手とかのケースもあるのか。 // give up用のカウンタを用意した。 if (num==0 || ++giveup > 10) { // 詰んでいたのでシミュレーション終了。指し手を巻き戻す。 if (TURN == tree->root_turn) mated = -1; // こっちの詰み else mated = +1; // あいての詰み // 詰みが発生した回数を計測。 mate_count++; goto next_playout; } Score bestscore = score_min; // このシミュレーション、質が悪いのかな…。 u32 bestnum = 0; // num == 1のときに↓のループがまわらずにそのあとに抜ける可能性がある // numに比例する回数のシミュレーションであるべき。 // あまり大きな値にしたくはないが、仕方ない意味もあるか…。 // 5/8だと1000回poぐらい。 // 2/8だと2000回poぐらい。 // このループが支配的。Randをもう少し軽いものに置き換えることは出来るが…。 // このループ減らすとpoの精度が悪くなるから嫌。 // Randの精度下げて、poもう少し増やすとか、並列化するだとか // そういうアプローチかな。 // たぶんいまの精度のまま1500回はいけるだろうから4コアで6000回ぐらいか。 for(u32 i=0; i<num*12/8; ++i) { u16 r = Rand16N(num); // これSEEだけでなく駒が取られるとかも大事なんだけどな…。 Score score = Search::SEE( tree, MOVE_LAST_PTR[r] , -1, Material::MT_CAP_SILVER, TURN ); if (bestscore < score) { bestscore = score; bestnum = r; } } // 指し手が決まった。 Move move = MOVE_LAST_PTR[bestnum]; // この指し手で局面を進めてみる。pinされているならやめる。 // 現局面で自玉に王手がかかっているなら回避手が生成されていることは保証されている。 if (MakeMove::make_move_pin_check_checking(tree,move)) continue; // 王手がかからなかったので、これで局面を進める。 { /* // 局面を進める前に、ここで生成した指し手すべてのhistoryのtriedを加算しておく。 for(u32 k = 0; k<num ; ++k) { Move move2 = MOVE_LAST_PTR[k]; u32 key = Moves::phash(move2,TURN); tree->hist_tried[key]++; } */ } moves[ply] = move; tree->inc_ply(); break; } //tree->print(); // 終局するまで } // 駒得を評価するならここ。 /* // 終局しなかった。駒損しているなら.. if ( Eval::evaluate_test1(tree) < 0) mated = -1; // 手番側が損している。 else mated = +1; // 非手番側が損している。 if (TURN != tree->root_turn) mated = -mated; // root_turn側が損していればマイナスがつくようにしなくてはならない。 */ // 決着がつかなかった場合は、無試合とする。 goto skip_playout; next_playout: /* tree->print(); printf("mated %d \n",mated); */ // playoutが終了した。指し手を巻き戻す。最後の局面で詰んでいた場合は、 // 加点/減点していく。 // UCBでは減点はよろしくないな。加点だけにしよう。 // 勝っていたのなら最初の3手目,5手目,…も加点しておこう。 // それらは勝率と相関があるはず。 if (mated > 0) { // moves[1]がルートの指し手moves[3]が3手目。 for(Ply i=1;i<=21 && i<ply;i+=2) { // 出現した手数が探索ルートから遠いほど比重を小さくする。 u32 weight = (23 - i)/2; // 加点する key = Moves::phash(moves[i],tree->root_turn); tree->history[key].good += weight; // あと、そのときに生成した指し手の試行回数をカウントしておく。 for(Move* RESTRICT pmove = tree->move_last[i-1] ; pmove < tree->move_last[i] ; ++pmove) { key = Moves::phash(*pmove,tree->root_turn); tree->history[key].tried += weight; tree->hist_update(key); // ある程度大きくなっていたらtriedとgoodを2で割る。 } //Moves::print(tree->move_last[i-1] ,tree->move_last[i]); //Moves::print(moves[ply); util_assert( tree->history[key].good <= tree->history[key].tried ); } } skip_playout:; // ルート局面のひとつ手前まで巻き戻す。 while(ply>1+1) { tree->dec_ply(); MakeMove::unmake_move(tree,moves[ply]); } playout++; } // 指し手選択のループ tree->dec_ply(); MakeMove::unmake_move(tree,MOVE_CURR); } // USIに情報出力 printf("info string simulation end. %d/%d playouts,time = %d[ms]\n", mate_count,playout,listener->timer->elapsed()); }
Lesserkai vs ひよこカルロ将棋v0.16c
floodgateに投入しているひよこカルロ将棋v0.16cですが、よく対戦中に落ちます。
この原因わからずに困っております。落ちた局面を読み込ませてみて、go ponderしても落ちないようですし、再現性がないので困ります。
あとは深いiteration中に落ちる場合も、デバッグビルドでテストするとそんなに深いiterationに到達するのに30分ぐらいかかるのでこれまたデバッグしづらいです。
理想は数回目のiterationで落ちる局面データがあればいいのですが、そう都合よくはないものです。
それで、ローカル環境でのデバッグしなきゃなーと思い、floodgate参戦用のマシンでLesserkaiと50局連続対局させてみました。持ち時間双方1分設定なのですが、将棋所では最速で指し手を返しても1手は1秒として計測されるため、120手を超えると1分をオーバーしてしまいます。
まあ、双方、1手1秒で指せているようですので、そこは無視して…気になる結果は。
ひよこカルロ将棋v0.16cの49勝1敗
となりました。
ちなみにひよこ将棋v0.01は、Lesserkaiに10局やって1勝もできていませんでした。ずいぶんひよこ将棋も成長したものです。
また、1分将棋はLesserkai側のiterationが回らず、圧倒的に不利なのでしょうね。
それはともかく、50戦する間にひよこカルロ将棋v0.16cは一度も落ちませんでした。
ちなみに、負けた1局は、193手もの将棋になって、ひよこカルロ将棋は持ち時間がなくなると一手0.1秒未満で指す仕様にしていたのですが、これが短すぎたようです。どうせ一手1秒と計測されるなら時間がオーバーしていたら0.8秒ぐらい使わないと損なような気はします。
あと、floodgateでのひよこカルロ将棋の対局を見ているとひよこカルロ将棋側が不利な局面だと落ちやすい気がするのですが、おそらく、1手詰め判定などに問題があって詰み筋が生じてくると落ちるのだと思います。
このあとデバッグのためLesserkaiとは持ち時間設定を5分にしてローカル環境にて連続対局させてみようと思います。
勝敗のほうはまたのちほど。ちなみにひよこカルロ将棋v0.16cはこのブログの上のダウンロードのところからダウンロードできるようにしておきました。