人は駒得のみに生くるにあらず その7
静止探索、実装しました。ひよこ将棋v0.06としてfloodgateに投入しました。私は開発環境でのデバッグはほとんどしていないので例によって何かバグってるかも知れませんが。
評価が安定してきたのは良いのですが、探索深さを8まで読んでも0のままです。0,0,0,0,…。
本当に強くなっているのか甚だ疑問ではありますが。
今度こそれさぴょんに勝ちたいところです。
ここまでのまとめ。
・killer move
・置換表
・純粋αβ
・静止探索 + 1手詰み判定
・駒得だけの評価関数(持ち駒も盤上の駒も同じ価値!)
私が一昨日、このブログに貼りつけておいたコードを良く見た人はお気づきかも知れませんが、置換表の指し手もkiller moveの指し手もその後の指し手生成から除外もせず、再度検索しています。まったく探索エネルギーの無駄使いとなっております。地球に優しくない、電力の無駄遣いです。
あと、今日書いた静止探索のコードも貼りつけておきます。これはひよこ将棋フレームワークの一部となるはずです。どこかで見たコードだなとかそういう苦情は受け付けておりません。
コードについてアドバイス等がありましたらよろしくお願いします。
// 静止探索 Score Search::search_quies( Tree * RESTRICT tree, Score alpha, Score beta, Ply qui_ply ) // qui_ply : 現在の静止探索深さ。 // 静止探索は再帰的に呼び出されるのでこの探索深さを持っていて、限界を超えると打ち切るようになっている。 { // 現局面の評価値を受け取る用。 Score value; // この局面でそのまま評価関数を呼び出したときの値。 Score stand_pat; // 探索したノード数のカウント tree->node_searched ++; // 取り合いをしない現在の評価値をstand_patとして、これを基準に考える。 stand_pat = EVAL_FUNCTION(tree); // 指し手を動かさなくとも最低値を更新したので、alpha値更新。 // 指し手側の手番だから、何もしないという選択肢がある。 // どの駒も取らなければ取り返されないわけで、stand_patより下回ることはないと考えられる。 // すなわち、stand_patとは最低保証値である。 // 手番の価値があるから、stand_pat + 手番の価値、となるはずで、手番を生かしてこのstand_patの値を // 超えることが出来るはずだという仮定のものに成り立っている。 if ( alpha < stand_pat ) { // β値を超えていればhigh fail..こんなことってあるんか? if ( beta <= stand_pat ) { // PASSして、何も指さなくても(手番の価値を生かさなくても)βcutが起きるほどいいよー。 return stand_pat; } alpha = stand_pat; } Turn turn = TURN; // 1手ずつ取る手を調べていく。 tree->anext_move[ply].next_phase = next_quies_gencap; while ( true ) { Move move = gen_next_quies( tree, alpha, qui_ply ); // 指し手がなくなったのか? if (move == MOVE_NA) break; // make_moveしてみる。非合法手ならば局面を進めずcontinue if (MakeMove::make_move_for_ques(tree,move)) continue; tree->inc_ply(); // 静止探索を再帰的に呼び出す value = -search_quies( tree, -beta, -alpha , qui_ply+1 ); tree->dec_ply(); MakeMove::unmake_move( tree , move); // alpha値を更新した。 if ( alpha < value ) { // beta cutまで発生した。 if ( beta <= value ) return value; // alpha値を更新した alpha = value; } } return alpha; } Move Search::gen_next_quies( Tree* RESTRICT tree, Score alpha, Ply qui_ply ) { Ply ply = PLY; switch ( tree->anext_move[ply].next_phase ) { // 捕獲する手(と成る手)を生成するフェーズ case next_quies_gencap: { GenMove::captures(tree); /* set sort values */ // 生成した指し手バッファの先頭 Move * RESTRICT pmove = MOVE_LAST; // 点数をつけてソートをするので、そのために使うテンポラリ配列 Score * RESTRICT psortv = tree->sort_value; // 生成した指し手の数 s32 n = (u32)( MOVE_CURRENT - pmove ); Score diff ; // スコアの差分評価値 Score value; // スコアを代入するテンポラリ変数。 Move move; s32 i,j; // insertion sortで使うので符号型でないとまずい。 // 生成した指し手のうちSEE>=0の指し手の数。 s32 nqmove = 0; Turn turn = TURN; for ( i = 0; i < n; i++ ) { move = pmove[i]; // 静止探索の限界深さを超えているなら、 // 1. 歩を取る手で成りを伴わない手 // 2 駒を取らず歩以外を成る手(歩は成ると大きいのでこれは無視できないが他の駒はたいして // 価値が変わらないので無視できる) // を生成しない。 if ( qui_ply >= 7 /*QUIES_PLY_LIMIT*/ && ( ( Moves::Cap(move) == pawn && ! Moves::IsPromote(move) ) || ( ! Moves::Cap(move) && Moves::PieceMove(move) != pawn ) ) ) { continue; } // 指し手の大雑把な見積り。 // とりあえず最初にcapする駒の価値で考えれ。 diff = Materials::piece_value[Moves::Cap(move)]/4; { // SEEの値が0以上のものに対して。MT_CAP_SILVERを超えることはそうそうないだろうし、 // そういうのはもう一律同じ扱いで構わない。 value = SEE( tree, move, -1, Material::MT_CAP_SILVER, turn ); if ( -1 < value ) { // SEEの値 + 指し手の差分評価値を加算。それでソート。 psortv[nqmove] = value + diff; pmove[nqmove++] = move; } } } /* insertion sort */ psortv[nqmove] = -score_bound; // 番人 for ( i = nqmove-2; i >= 0; i-- ) { // sortvの値でソート。これ…64bit化して、scoreと指し手とまとめて // ソートしたほうが速い。あとで書きなおす。 value = psortv[i]; move = pmove[i]; for ( j = i+1; psortv[j] > value; j++ ) { psortv[j-1] = psortv[j]; pmove[j-1] = pmove[j]; } psortv[j-1] = value; pmove[j-1] = move; } // --- ソート、ここまで。 MOVE_CURRENT = MOVE_LAST + nqmove; // SEE>=0だったので使った指し手分。SEE<0の指し手は返さない。 tree->anext_move[ply].move_last = pmove; // == MOVE_LAST // 次のフェーズ tree->anext_move[ply].next_phase = next_quies_captures; // ↓ fall through } // 生成した手を1手ずつ返すフェーズ case next_quies_captures: if ( tree->anext_move[ply].move_last != MOVE_CURRENT ) { return *tree->anext_move[ply].move_last++; } } // 指し手がもう無いんですけど。 return MOVE_NA; }