ひよこカルロメソッド
ひよこカルロ将棋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());
}
