人は駒得のみに生くるにあらず その4
一晩明けて、floodgateの対戦結果を見ると、ひよこ将棋0.03はpishogiにしか勝ててませんでした。pishogiには、最初の操作ミスを除くと全戦全勝。他の相手には全戦全敗。R1359。
pishogiにさえ勝てればR1359になるという、誰も知りたくもない結果がわかりました。
pishogiはわざと手加減してくれているようですので(終盤が異様に弱い)、ひよこ将棋0.03はfloodgate最弱と言って過言ではないでしょう。
そこで、早速置換表を実装してみました。
1) 置換表の指し手
2) killer move
3) 捕獲する手
4) それ以外の指し手
を順番に試します。
しかし…これまた弱いです。
弱い理由は、置換表を実装しても、駒得しか評価しないのでほとんどの局面で評価が0でして、探索深さが伸びないからだと思います。10秒ぐらい使って、9手読めるか読めないかぐらいの探索速度です。もう少し探索深さが深くならないことには置換表のありがたみがありません。
あと、指し手を逐次生成型に変更したことと、置換表を参照/置換表に保存するように変更したので、これによってnpsが若干低下しました。終盤でも8Mnpsぐらいしか出てません。
ということで、むしろ弱くなってしまいました。一応、floodgateにhiyoko_shogi_v0.04として投入しておきますが、pishogi以外に勝てそうにありません。
弱い原因のうち、一番大きなものはおそらく静止探索をしていないというのがあります。静止探索をしていないので駒の最後の取り合いが読めておらず、1手深く読むごとに、+200,-200,+200,…のように評価値が揺れ動きます。駒得しか評価していないのに、その駒得自体が適当な評価なわけですから、これで勝てるはずがありません。
あと、持ち時間も制御しておらず反復深化で0.4秒を超えたら次のiterationで指すという適当さ加減です。
この二点を次に改良しようと思っています。
あと現時点のソースをぺたぺた貼っておきます。ひよこ将棋フレームワーク(将来的にはオープンソースにするつもり)を用いればこれだけ書けば将棋プログラムが作れちゃうということで。
// αβ探索。depth = 探索残り深さ
// 現在の探索深さ自体は、PLY(tree->ply)に入っている。
Score AlphaBetaSearch(Tree* RESTRICT tree , Score alpha,Score beta,Ply depth)
{
if (depth == 0)
{
tree->node_searched++; // 探索ノード数を加算
return TURN == black ? tree->board.material : - tree->board.material; // 現在の駒割
}
bool isMate = true; // この局面が詰んでいるのか。
// 置換表に指し手があるかどうかを調べる。あればtree->amove_hash[PLY]に格納される。
HASH_MOVE = MOVE_NA;
StateNode state_node;
switch (Hashes::hash_probe(tree,depth,alpha,beta,&state_node))
{
// 置換表上に以前βcutしたときの手が登録されていた。
case value_lower:
{
// このあと、最初に試して。
}
break;
// 置換表上に以前の最善手が登録されていた。
case value_upper:
{
// このあと、最初に試して。
}
break;
// 置換表上に詰みが登録されていた。
case value_exact:
{
tree->pv[PLY] = HASH_MOVE; // これがbest move..のはず..
return HASH_VALUE;
}
}
// 置換表の指し手を試すところから順番に生成していく。
// 王手がかかっているなら回避する手を生成するフェーズから。
tree->anext_move[PLY].next_phase =
CHECKED ? next_move_evasion : next_move_hash;
// α値に更新があったかを調べるために元の値を保存しておく。
Score oldAlpha = alpha;
while(true)
{
// 1手生成して返す関数
Move move = GenNextMove(tree);
// 指し手がなかったので終わり。
if (move == MOVE_NA)
break;
// 現局面は王手がかかっているか？
if (CHECKED)
{
// 回避手のみを生成しているのでこれが王手になっていることは有り得ない。
MakeMove::make_move_checking(tree,move);
isMate = false; // 合法な指し手が一つ以上見つかったのでmateではない。
} else {
if (MakeMove::make_move_pin_check_checking(tree,move))
continue;
// 空き王手を食らった == 非合法手
// なので、局面を進めずに次の手に。
}
tree->inc_ply(); // 手番反転、指し手生成バッファを次の深さに。
Score score = -AlphaBetaSearch(tree, -beta , -alpha , depth - 1);
tree->dec_ply(); // inc_plyの逆操作。
MakeMove::unmake_move(tree,move);
if ( score > alpha)
{
alpha = score;
tree->pv[PLY] = move; // これがbest move..のはず..
if ( alpha >= beta )
{
// この手を置換表に格納しておく。
if (alpha > score_mate)
{
// 詰む手なら、これ正確な評価値として登録しておく。それがvalue_exact
Hashes::hash_store(tree,depth,HashValueType::value_exact,alpha,move,0);
} else {
// value_lowerは、この値より本当はもっといい値があるはずだけど、
// beta cutしたから本当の値はわからない、の意味。
Hashes::hash_store(tree,depth,HashValueType::value_lower,alpha,move,0);
}
killer_moves[PLY] = move;
return alpha; // beta cut
}
// pvを最後に見つけた探索深さ+1。要するにtree->pvが有効な範囲。
if (tree->pv_depth <= PLY)
tree->pv_depth = PLY+1;
}
}
// 現局面に王手がかかっているにも関わらず、
// 生成された指し手が1つもなかったので詰みとしての評価値を返す。
if (CHECKED && isMate)
{
return -score_mate1ply + (PLY - 1);
// Hashes::hash_store(tree,depth,HashValueType::value_exact,alpha,0,0);
// ここで置換表に登録するのはまずい。何故なら、この局面は詰んでいるので
// 指し手はないからだ。置換表は、次の手を指す場合にしか登録できない。
}
// 深い手数で詰まされるほうが評価値としては良い値である。
// この局面の1つ前の局面(ply - 1)にて詰んでいるわけだから、
// 加算する値は (ply - 1)
// α値の更新があった == 指し手が一つはいいやつが見つかった
if (oldAlpha != alpha )
{
// 最善手を置換表に格納しておく。
// value_upperは、この値が見つけた最高値で、他の指し手はこれより低いの意味。
Hashes::hash_store(tree,depth,HashValueType::value_upper,alpha,tree->pv[PLY],0);
}
return alpha;
}
// 1手指し手を生成して返す。
// 指し手がなければMOVE_NAを返す。
// coroutineになっているので初期化が必要。
Move GenNextMove(Tree* RESTRICT tree)
{
Move move;
switch ( tree->anext_move[PLY].next_phase )
{
// 置換表の指し手を試す
case next_move_hash:
{
move = HASH_MOVE;
if (move != MOVE_NA)
{
// 次にこの関数に戻ってきたときは、駒を捕獲する手を生成するフェーズ
tree->anext_move[PLY].next_phase = next_move_gen_capture;
break;
}
}
// breakは書かない。↓にfall throughする。
// 駒を捕獲する手を生成するフェーズ
case next_move_gen_capture:
{
// killerもここで生成して指し手生成バッファに追加。最初に試しておく。本当はオーダリングすべき。
Move killer_move = killer_moves[tree->ply];
if (killer_move!=MOVE_NA
&& Valid::is_move_valid(tree,killer_move))
{
*MOVE_CURRENT++ = killer_move;
}
// 捕獲する手を生成
GenMove::captures(tree);
tree->anext_move[PLY].move_last = MOVE_LAST; // 生成した指し手の先頭
tree->anext_move[PLY].remaining = (s32)(MOVE_CURRENT - MOVE_LAST); // 生成した指し手の数
tree->anext_move[PLY].next_phase = next_move_capture;
}
// breakは書かない。↓にfall throughする。
// 駒を捕獲する手を1手ずつ返すフェーズ
case next_move_capture:
{
// 本当は置換表の指し手とkiller moveを除外しなきゃいけないんだけど、
// あとで書こう。
if (--tree->anext_move[PLY].remaining >= 0)
{
move = *tree->anext_move[PLY].move_last++;
break;
}
else
{
// 指し手がなくなったので打つ手と駒を取らない手を生成する。
GenMove::drop(tree);
GenMove::no_cap(tree);
tree->anext_move[PLY].move_last = MOVE_LAST; // 生成した指し手の先頭
tree->anext_move[PLY].remaining = (s32)(MOVE_CURRENT - MOVE_LAST);
tree->anext_move[PLY].next_phase = next_move_misc;
}
}
// ↓fall throughで。
case next_move_misc:
{
label_next_move_misc:
if (--tree->anext_move[PLY].remaining >= 0)
move = *tree->anext_move[PLY].move_last++;
else
move = MOVE_NA; // 指し手が尽きた
break;
}
case next_move_evasion:
// 王手回避のときは置換表の手は使わないんだ。
{
// 王手を回避する指し手をすべて生成。
GenMove::evasion(tree);
tree->anext_move[PLY].move_last = MOVE_LAST; // 生成した指し手の先頭
tree->anext_move[PLY].remaining = (s32)(MOVE_CURRENT - MOVE_LAST); // 生成した指し手の数
// 次にこの関数に戻ってきたときは、1手ずつ返すフェーズ
tree->anext_move[PLY].next_phase = next_move_misc;
goto label_next_move_misc;
}
}
return move;
}
// killer move
Move killer_moves[PLY_MAX];
MyShogi(HiyokoShogiFramework& f) : fw(f) {}
private:
HiyokoShogiFramework& fw;
};
