PV表示はいろんなことを教えてくれる…かもしれない
記憶モードだがWikipediaのネガアルファ法のページにはこんな感じのコードが載っていた。
これは評価値しか出力しないが、正しく動く
template<int end_ab> int NegaAlpha(int rdepth, int alpha, int beta) { EnumContext& node = nodes[rdepth]; if (rdepth <= 0) { int v = (end_ab != 0) ? node.GetEvalOnA(alpha, beta) : -node.GetEvalOnA(-beta, -alpha); return v; } while (node.MoveNext()) { TPMove curMove = node.GetLastMove(); int v = -NegaAlpha<end_ab>(rdepth - 1, -beta, -alpha); // (1) if (v > alpha) { alpha = v; if (alpha >= beta) { node.Reset(); return alpha; } } } node.Reset(); return alpha; } int Search(int sdepth, int end_ab) { return (end_ab != 0) ? NegaAlpha<1>(sdepth, -INFINITE, INFINITE) : NegaAlpha<0>(sdepth, -INFINITE, INFINITE); }
これに能天気なGMA0BNが天の啓示を受けてPVの記録コードを追加しようとした↓
template<int end_ab> int NegaAlpha(int rdepth, int alpha, int beta, TPVElem* ppv) { EnumContext& node = nodes[rdepth]; ppv = pv_alloc(0); if (rdepth <= 0) { int v = (end_ab != 0) ? node.GetEvalOnA(alpha, beta) : -node.GetEvalOnA(-beta, -alpha); return v; } while (node.MoveNext()) { TPMove curMove = node.GetLastMove(); TPVElem* ppv2; int v = -NegaAlpha<end_ab>(rdepth - 1, -beta, -alpha, ppv2); if (v > alpha) { alpha = v; if (alpha >= beta) { // βカット node.Reset(); return alpha; } pv_free(ppv); ppv = pv_alloc(curMove); ppv = pv_join(ppv, ppv2); } else { pv_free(ppv2); } } node.Reset(); return alpha; } int Search(int sdepth, int end_ab, TPVElem* ppv) { return (end_ab != 0) ? NegaAlpha<1>(sdepth, -INFINITE, INFINITE, ppv) : NegaAlpha<0>(sdepth, -INFINITE, INFINITE, ppv); }
だがこれではたまに正常に動かないのじゃ
なぜなら、上のコードではβカットされたらPV記録しない仕様だが、このロジック一本槍ではうまくいかないケースが存在する。
すわなち、相手を詰ませたとき、Search()→NegaAlpha()→-NegaAlpha()の最後のNegaAlpha()が -INFINITEを返すが、すると上記コードのβカット判定if文において、INFINITE >= INFINITEということで必ずβカット様の動きになってしまう。すると、相手を詰ませたのだから本当は勝ち確定だからPVとしては大いにアリなのに、ppvには何も残らない。最善手をPVの第一手から持ってくるような作りにした場合、勝ち確定でいきなり投了するからびっくりだ
そもそも理論上は探索の根ノードでβカットが起きるはずは無い（∵自明）*1
というわけで、こうしたら良くなった↓*2
template<bool root, int end_ab> int NegaAlpha(int rdepth, int alpha, int beta, TPVElem* ppv) { EnumContext& node = nodes[rdepth]; ppv = pv_alloc(0); if (rdepth <= 0) { int v = (end_ab != 0) ? node.GetEvalOnA(alpha, beta) : -node.GetEvalOnA(-beta, -alpha); return v; } while (node.MoveNext()) { TPMove curMove = node.GetLastMove(); TPVElem* ppv2; int v = -NegaAlpha<false, end_ab>(rdepth - 1, -beta, -alpha, ppv2); if (v > alpha) { alpha = v; if (!root && alpha >= beta) { // βカット；ただし根ノードではβカットは有り得ない node.Reset(); return alpha; } pv_free(ppv); ppv = pv_alloc(curMove); ppv = pv_join(ppv, ppv2); // まだまだ飛べるぜよ！ } else { pv_free(ppv2); } } node.Reset(); return alpha; } int Search(int sdepth, int end_ab, TPVElem* ppv) { return (end_ab != 0) ? NegaAlpha<true, 1>(sdepth, -INFINITE, INFINITE, ppv) : NegaAlpha<true, 0>(sdepth, -INFINITE, INFINITE, ppv); }
だがこれでもまだ問題がある。このコードでは、Search()→NegaAlpha()→-NegaAlpha()の最後のNegaAlpha()が-INFINITEを返しても、もう起こりえないalphaの更新を求めて最後までループを回ろうとする。
勝ち確定したのにその後も延々考え続けてtimeupして負けるからびっくりだ*3
これが正解らしいいい↓
template<bool root, int end_ab> int NegaAlpha(int rdepth, int alpha, int beta, TPVElem* ppv) { EnumContext& node = nodes[rdepth]; ppv = pv_alloc(0); if (rdepth <= 0) { int v = (end_ab != 0) ? node.GetEvalOnA(alpha, beta) : -node.GetEvalOnA(-beta, -alpha); return v; } while (node.MoveNext()) { TPMove curMove = node.GetLastMove(); TPVElem* ppv2; int v = -NegaAlpha<false, end_ab>(rdepth - 1, -beta, -alpha, ppv2); if (v > alpha) { alpha = v; if (!root && alpha >= beta) { // βカット；ただし根ノードではβカットは有り得ない node.Reset(); return alpha; } pv_free(ppv); ppv = pv_alloc(curMove); ppv = pv_join(ppv, ppv2); if (root && alpha == INFINITE) { // 根ノードでINFINITEならもうおk やめてくれもう十分だ node.Reset(); return alpha; } } else { pv_free(ppv2); } } node.Reset(); return alpha; } int Search(int sdepth, int end_ab, TPVElem* ppv) { return (end_ab != 0) ? NegaAlpha<true, 1>(sdepth, -INFINITE, INFINITE, ppv) : NegaAlpha<true, 0>(sdepth, -INFINITE, INFINITE, ppv); }
■ 結論
αβ探索はﾁｮｰﾑｽﾞｲﾏｼﾞﾔﾊﾞｲ；
