読者です 読者をやめる 読者になる 読者になる

daruma3940の日記

理解や文章に間違い等あればどんなことでもご指摘お願いします

Aperyの探索関数を理解しよう! (現在進行形)

コンピューター将棋

Aperyの探索関数を理解しよう!
(現在進行形)

SPNodeというのは無視

aperyの探索関数中の深さは減っていく方式!!

newDepth = depth - OnePly + extension;
//newdepthがONE_PLYより小さくなればqsearchが呼び出される。

探索関数
-------------------------------------------------------------------step1
まずは探索に必要な定数が初期化される

Thread* thisThread = pos.thisThread();
    moveCount = playedMoveCount = 0;
    inCheck = pos.inCheck();


    //分岐点??
    if (SPNode) {
        splitPoint = ss->splitPoint;
        bestMove = splitPoint->bestMove;
        threatMove = splitPoint->threatMove;
        bestScore = splitPoint->bestScore;
        tte = nullptr;
        ttMove = excludedMove = Move::moveNone();
        ttScore = ScoreNone;

        evaluate(pos, ss);

        assert(-ScoreInfinite < splitPoint->bestScore && 0 < splitPoint->moveCount);

        goto split_point_start;//step10へ
    }

    bestScore = -ScoreInfinite;
    ss->currentMove = threatMove = bestMove = (ss + 1)->excludedMove = Move::moveNone();
    ss->ply = (ss-1)->ply + 1;
    (ss+1)->skipNullMove = false;
    (ss+1)->reduction = Depth0;
    (ss+2)->killers[0] = (ss+2)->killers[1] = Move::moveNone();

    if (PVNode && thisThread->maxPly < ss->ply) {
        thisThread->maxPly = ss->ply;
    }

--------------------------------------------------------------------step2
千日手の確認と時間による探索停止と最大探索深さのチェック

//rootnodeではない
    if (!RootNode) {
        // step2
        // stop と最大探索深さのチェック
        switch (pos.isDraw(16)) {//千日手チェック??
        case NotRepetition      : if (!signals.stop && ss->ply <= MaxPly) { break; }//千日手ではないのでstopかMaxPlyで探索終る
        case RepetitionDraw     : return ScoreDraw;
        case RepetitionWin      : return mateIn(ss->ply);
        case RepetitionLose     : return matedIn(ss->ply);
        case RepetitionSuperior : if (ss->ply != 2) { return ScoreMateInMaxPly; } break;
        case RepetitionInferior : if (ss->ply != 2) { return ScoreMatedInMaxPly; } break;
        default                 : UNREACHABLE;
        }

-------------------------------------------------------------------step3
mate distance prunningを行う

    たとえ次の指し手で相手を詰ませることが出来て評価値がmate-(ply+1)になったとしても
    もしこのゲーム木の上でより短い手数での詰みが見つかっていてalpha値がすでにその値(mate-(ply+1))よりも大きくなっていれば
    現在のアルファ値を超えることは決してないのでコレ以上探索をする必要はない

    同じ論理(符号を反転させて)で詰みの代わりにつまされる場合を考えることができる。

    この場合fail-highの値を返す。

    (要約)4手詰めが見つかっている場合に5手詰めを探す必要はない
if (!RootNode) {
//alpha=max(-mate+ply,alpha) alphaの値は現在つまされている値よりも小さくは成れない つまりalphaは最小でも-mate+ply
            alpha = std::max(matedIn(ss->ply), alpha);
//beta=min(mate-ply,beta)  betaの値は次の指し手で詰む値よりも大きくはなれない つまりbetaは最大でもmate-(ply+1)
            beta = std::min(mateIn(ss->ply+1), beta);

        //現在のnodeの深さをplyとする
        //他のノードでn手詰みを見つけている場合alpha=mate-n
        //n<ply+1の場合はalpha>betaでここでreturn できる
    
            if (beta <= alpha) {
                return alpha;
            }
        }

-----------------------------------------------------------------------step4 
トランスポジションテーブルを参照する

ルートノードであればTTから差し手を受け取ったりはしない
そうでなくてこの局面のTTが見つかれば差し手を受け取る

評価値の値をttScoreとして受け取る

①もし
探索開始局面でなく
TTを発見でき
今の局面の深さがTTの深さよりも深く
TTの評価値は受け取られており
評価値のタイプが適切である
場合
TTの世代を更新??し
現在の差し手をttからの差し手に変更し

①’  
さらにもし  
TTからのScoreがBeta値を上回り  
TTの差し手がとる手や駒の成る手ではなければ  
killermoveを更新する  

TTの評価値を返して枝切りする

②もし
探索開始局面ではなく
王手がかけられていない局面であり
相手玉が一手積みの局面で
評価値があと数手で相手を積ませるような評価値の場合、
そのような差し手をTTの保存し
その手をbestmoveに入れてそのScoreを返す

excludedMove = ss->excludedMove;
    posKey = (excludedMove.isNone() ? pos.getKey() : pos.getExclusionKey());
    tte = tt.probe(posKey);
    ttMove = 
        RootNode ? rootMoves[pvIdx].pv_[0] :
        tte != nullptr ?
        move16toMove(tte->move(), pos) :
        Move::moveNone();
    ttScore = (tte != nullptr ? scoreFromTT(tte->score(), ss->ply) : ScoreNone);

    if (!RootNode
        && tte != nullptr
        && depth <= tte->depth()
        && ttScore != ScoreNone // アクセス競合が起きたときのみ、ここに引っかかる。
        && (PVNode ? tte->type() == BoundExact
            : (beta <= ttScore ? (tte->type() & BoundLower)
               : (tte->type() & BoundUpper))))
    {
        tt.refresh(tte);
        ss->currentMove = ttMove; // Move::moveNone() もありえる。

        if (beta <= ttScore
            && !ttMove.isNone()
            && !ttMove.isCaptureOrPawnPromotion()
            && ttMove != ss->killers[0])
        {
            ss->killers[1] = ss->killers[0];
            ss->killers[0] = ttMove;
        }
        return ttScore;
    }//TTの値を返す

#if 1
    if (!RootNode
        && !inCheck)
    {
        if (!(move = pos.mateMoveIn1Ply()).isNone()) {
            ss->staticEval = bestScore = mateIn(ss->ply);
            tt.store(posKey, scoreToTT(bestScore, ss->ply), BoundExact, depth,
                     move, ss->staticEval);
            bestMove = move;
            return bestScore;
        }//TTによる最善手と最善手のスコアを返す
    }

--------------------------------------------------------------step5

静的評価値をKPPなどによって計算する

①もし王手をかけられている場合は評価値をなかったことにしてstep10まで飛ぶ
②もしこの局面のTTを発見できた場合その評価値を使う
③もしこの局面のTTを発見できなかった場合はTTに先ほど計算した評価値を格納する

もし
前回の差し手はnullmoveでなく
前回の評価値がちゃんと存在し
前回が駒鳥や府の成る手ではなかった場合
gainの更新
//ToDo:Gainとはなに???

eval = ss->staticEval = evaluate(pos, ss); // Bonanza の差分評価の為、evaluate() を常に呼ぶ。
    if (inCheck) {//王手かけられてる
        eval = ss->staticEval = ScoreNone;
        goto iid_start;//step10 多重反復深化
    }
    else if (tte != nullptr) {//候補となるttがあった
    // 置換表に格納されている値に関して何も仮定しない。

     // 置換表にスコアが格納されているとは限らない。(PVにおいて指し手のみ格納されているだけかも知れない)

     // 置換表に格納されていたスコアがVALUE_NONEであれば、評価関数を呼び出してやる

        if (ttScore != ScoreNone
            && (tte->type() & (eval < ttScore ? BoundLower : BoundUpper)))
        {
            eval = ttScore;
        }
    }
    else {
        tt.store(posKey, ScoreNone, BoundNone, DepthNone,
                 Move::moveNone(), ss->staticEval);
    }

    // 一手前の指し手について、history を更新する。
    // todo: ここの条件はもう少し考えた方が良い。
    if ((move = (ss-1)->currentMove) != Move::moveNull()
        && (ss-1)->staticEval != ScoreNone
        && ss->staticEval != ScoreNone
        && !move.isCaptureOrPawnPromotion() // 前回(一手前)の指し手が駒取りでなかった。
        )
    {
        const Square to = move.to();
        //TODO gain statsとはなに? 
        gains.update(move.isDrop(), pos.piece(to), to, -(ss-1)->staticEval - ss->staticEval);
    }

--------------------------------------------------------------step6
razoringカットを行う

条件
一番いい読み筋ではない
残りdepthが4手未満
初めてきた局面
詰みにかかわるような局面ではない

これ以上の先読みは行わずnullwindow静止探索を行い 戻ってきた値がrbetaを超えられるようないい値ではなければこの局面は枝切り

    if (!PVNode
        && depth < 4 * OnePly
        && eval + razorMargin(depth) < beta
        && ttMove.isNone()
        && abs(beta) < ScoreMateInMaxPly)
    {
        const Score rbeta = beta - razorMargin(depth);
        const Score s = qsearch<NonPV, false>(pos, ss, rbeta-1, rbeta, Depth0);
        if (s < rbeta) {
            return s;
        }
    }

//ーーーーーーーーーーーーーーーーーーーーーーー step7
static null move pruning

条件
・もっともよい読み筋ではない
・nullmoveをした後ではない
・残りdepthが4手未満
・beta <= eval - FutilityMargins
次の深さ(相手番)のalpha値の正負反転させたものよりも(評価値)-(margin)が高い、つまり
-alpha<=eval-margin
-eval+margin<=alpha
であるのでつぎの局面の評価値の下界を超えられない(いやいやalphaカットをするのはおかしい よくわからん)
・ 詰みに関係しない局面 の場合

枝切り

    if (!PVNode
        && !ss->skipNullMove
        && depth < 4 * OnePly
        && beta <= eval - FutilityMargins[depth][0]
        && abs(beta) < ScoreMateInMaxPly)
    {
        return eval - FutilityMargins[depth][0];
    }

---------------------------------------------------step8 nullmove

*現在がbeta値を超えてしまっているとき
もしここでnullmoveという悪い指し手を指してしまったとしてもまだbeta値を超えてしまっているようならば
今後探索を深くしてもbeta値より下に下がってくることはないと考えられるのでここで枝切りをしてしまう?(多分そういうことだと思っている)

条件

PVNodeでなく
前回Nullmoveをしておらず 2 * OnePly <= depthであり
beta値を評価値が超えており、
beta値が詰みに関するスコアでない

現在思考中の差し手をnullmoveにする
探索深さを3* OnePly + depth / 4;だけ削減する
もしbeta < eval - PawnScoreであるほど評価値が大きすぎた場合はさらに一手分探索深さを削減する
nullmoveを指したとして削減された深さで探索を行う

①もしnullmove探索で得られた値(nullScore)がbeta値よりも大きかった場合

もしnullScoreが詰み関係のscoreであればnullScoreはbeta値まで引き下げる

depth < 6 * OnePlyの場合はそのままここで枝切りを行う

もしdepth > 6 * OnePlyの場合は
search(pos, ss, alpha, beta, depth - reduction, false);でもう一度探索させる
TODO:negaalphabeta法なのにalpha=-beta,beta=-alphaではない????なんで??

それでもbeta血を評価値が超えればそこで枝切り

②もしbeta値を下回った場合

depth < 5 * OnePlyかつ正常に探索されていれば
beta-1を返して枝切り

if (!PVNode
        && !ss->skipNullMove
        && 2 * OnePly <= depth
        && beta <= eval
        && abs(beta) < ScoreMateInMaxPly)
    {
        ss->currentMove = Move::moveNull();
        Depth reduction = static_cast<Depth>(3) * OnePly + depth / 4;

        if (beta < eval - PawnScore) {
            reduction += OnePly;
        }

        pos.doNullMove<true>(st);
        (ss+1)->staticEvalRaw = (ss)->staticEvalRaw; // 評価値の差分評価の為。
        (ss+1)->skipNullMove = true;
        Score nullScore = (depth - reduction < OnePly ?
                           -qsearch<NonPV, false>(pos, ss + 1, -beta, -alpha, Depth0)
                           : -search<NonPV>(pos, ss + 1, -beta, -alpha, depth - reduction, !cutNode));
        (ss+1)->skipNullMove = false;
        pos.doNullMove<false>(st);

        if (beta <= nullScore) {
            if (ScoreMateInMaxPly <= nullScore) {
                nullScore = beta;
            }

            if (depth < 6 * OnePly) {
                return nullScore;
            }

            ss->skipNullMove = true;
            assert(Depth0 < depth - reduction);
            const Score s = search<NonPV>(pos, ss, alpha, beta, depth - reduction, false);
            ss->skipNullMove = false;

            if (beta <= s) {
                return nullScore;
            }
        }
        else {
            // fail low
            threatMove = (ss+1)->currentMove;
            if (depth < 5 * OnePly
                && (ss-1)->reduction != Depth0
                && !threatMove.isNone()
                && allows(pos, (ss-1)->currentMove, threatMove))
            {
                return beta - 1;
            }
        }
    }

-------------------------------------------------step9
probcut
条件
PVnodeではなく
Nullmove直後ではなく
詰みに絡む局面ではない

実装
新しいbeta値と新しい探索深さを用意する
const Score rbeta = beta + 200;

    const Depth rdepth = depth - OnePly - 3 * OnePly;  

一手前で駒をとった差し手があればその差し手以上の価値があると考えられる差し手をTTから生成し
その指し手でnullwindow 深さreduce探索を行ったときにrbetaを超えるような評価値が却って来ればその局面は探索中止してもよい

if (!PVNode
        && 5 * OnePly <= depth
        && !ss->skipNullMove
        // 確実にバグらせないようにする。
        && abs(beta) < ScoreInfinite - 200)
    {
        const Score rbeta = beta + 200;
        const Depth rdepth = depth - OnePly - 3 * OnePly;

        assert(OnePly <= rdepth);
        assert(!(ss-1)->currentMove.isNone());
        assert((ss-1)->currentMove != Move::moveNull());

        assert(move == (ss-1)->currentMove);
        // move.cap() は前回(一手前)の指し手で取った駒の種類
        MovePicker mp(pos, ttMove, history, move.cap());
        const CheckInfo ci(pos);
        while (!(move = mp.nextMove<false>()).isNone()) {//ここで次の差し手が渡されている!
            if (pos.pseudoLegalMoveIsLegal<false, false>(move, ci.pinned)) {
                ss->currentMove = move;
                pos.doMove(move, st, ci, pos.moveGivesCheck(move, ci));
                (ss+1)->staticEvalRaw.p[0][0] = ScoreNotEvaluated;
                score = -search<NonPV>(pos, ss+1, -rbeta, -rbeta+1, rdepth, !cutNode);
                pos.undoMove(move);
                if (rbeta <= score) {
                    return score;
                }
            }
        }
    }

---------------------------------------------------step10
internal iterative deepening
多重反復深化を行う

singularExtensionNodeであるかの設定も行う
rootnodeではなく、Spnodeでもなく
8 * OnePly よりdepthは浅く
TTから受け取った指し手が存在し
場外する差し手がなく
TTの差し手の評価値の性質がBoundlower であり
depth - 3 * OnePly <= TTのdepth();
である場合にsingularExtensionNodeであると設定される。

if ((PVNode ? 5 * OnePly : 8 * OnePly) <= depth
        && ttMove.isNone()
        && (PVNode || (!inCheck && beta <= ss->staticEval + static_cast<Score>(256))))
    {
        //const Depth d = depth - 2 * OnePly - (PVNode ? Depth0 : depth / 4);
        const Depth d = (PVNode ? depth - 2 * OnePly : depth / 2);

        ss->skipNullMove = true;
        search<PVNode ? PV : NonPV>(pos, ss, alpha, beta, d, true);
        ss->skipNullMove = false;

        tte = tt.probe(posKey);
        ttMove = (tte != nullptr ?
                  move16toMove(tte->move(), pos) :
                  Move::moveNone());
    }

split_point_start://maltithread用?
    MovePicker mp(pos, ttMove, depth, history, ss, PVNode ? -ScoreInfinite : beta);//指し手生成
    const CheckInfo ci(pos);
    score = bestScore;
    singularExtensionNode =
        !RootNode
        && !SPNode
        && 8 * OnePly <= depth
        && !ttMove.isNone()
        && excludedMove.isNone()
        && (tte->type() & BoundLower)
        && depth - 3 * OnePly <= tte->depth();

-------------------------------------------------step11
Loop through moves(差し手の取り出し)
探索する差し手を一手取り出し
その指し手が除外されている差し手か
探索がrootnodeであればrootMovesの集合にちゃんと含まれているか
またSPnodeであればその指し手が仮の合法手かどうかチェックし、
もしそれらの条件を満たさなければその指し手は飛ばして次の差し手を取り出す。

またその指し手の性質もここで確認しておき、のちの探索時に用いる




------差し手の性質----
firstrootmoveかどうか
歩の成りか駒鳥か
王手をかける差し手であるか

while (!(move = mp.nextMove<SPNode>()).isNone()) {//次の差し手を取り出す

        //この指し手が除外する差し手であれば
        if (move == excludedMove) {
            continue;
        }

        //rootnodeではあるがrootMovesの集合の中にはその指し手は存在していない
        if (RootNode&& std::find(rootMoves.begin() + pvIdx, rootMoves.end(), move) == rootMoves.end())
        {
            continue;
        }

        if (SPNode) {
            if (!pos.pseudoLegalMoveIsLegal<false, false>(move, ci.pinned)) {
                continue;
            }
            moveCount = ++splitPoint->moveCount;
            splitPoint->mutex.unlock();
        }
        else {
            ++moveCount;
        }


        if (RootNode) {
            signals.firstRootMove = (moveCount == 1);

        }

        extension = Depth0;
        captureOrPawnPromotion = move.isCaptureOrPawnPromotion();
        givesCheck = pos.moveGivesCheck(move, ci);
        dangerous = givesCheck; // todo: not implement

ーーーーーーーーーーーーーーーーーーーーーーーーーstep12
singuler extension

*そのnode(局面)で有望な指し手が1つしかないときに、その指し手を延長して探索するというものです。
ベストの指し手の評価値 - singularのmargin値 以上の指し手が他にないかを少し浅い探索深さで調べて、それがなければ「有望な指し手が1つ」と判定します。
by やねうら王公式ブログ

王手かつ駒の取り合いでの評価値が正である場合は一手だけ拡張


条件  
singularExtensionNodeで
extentionがまだ0手
現在の差し手がTTによる指し手で
差し手は合法手であり
差し手の評価値はまだ勝ちが確定していなければ

rbetaとしてTTの差し手の評価値より少し低い値を設定し
TTの値をいったん除外し
nullmove探索はしないようにして
残り深さの半分の深さでnullwindow探索を行ってみて

もしrbetaの値よりも探索して出てきた値の方が小さければ
有望な指し手がTTによる指し手以外にはないということなので
extension = (beta <= rBeta ? OnePly + OnePly / 2 : OnePly
の分だけその指し手の探索を延長する

newDepth = depth - OnePly + extension;

if (givesCheck && ScoreZero <= pos.seeSign(move))
        {
            extension = OnePly;
        }

if (singularExtensionNode
            && extension == Depth0
            && move == ttMove
            && pos.pseudoLegalMoveIsLegal<false, false>(move, ci.pinned)
            && abs(ttScore) < ScoreKnownWin)
        {
            assert(ttScore != ScoreNone);

            const Score rBeta = ttScore - static_cast<Score>(depth);
            ss->excludedMove = move;
            ss->skipNullMove = true;
            score = search<NonPV>(pos, ss, rBeta - 1, rBeta, depth / 2, cutNode);
            ss->skipNullMove = false;
            ss->excludedMove = Move::moveNone();

            if (score < rBeta) {
                //extension = OnePly;
                extension = (beta <= rBeta ? OnePly + OnePly / 2 : OnePly);
            }
        }

        newDepth = depth - OnePly + extension;

-----------------------------------------------------step13

                futility pruning  

futility pruningが行われる条件は PVnodeではなく 駒を取る手歩の成る手ではなく 王手の掛けられているような悪い局面ではない場合。 この条件の内部でmove count based pruning  score based pruningの2つが呼び出されている

// move count based pruning depth < 16 * OnePlyであり 現在探索中の差し手の番号が FutilityMoveCounts[depth] であり 現在探索中の差し手はちゃんとした指し手であれば

その指し手はの探索は飛ばしてしまう

// score based pruning

     if (!PVNode
            && !captureOrPawnPromotion
            && !inCheck
            && !dangerous
            //&& move != ttMove // 次の行がtrueならこれもtrueなので条件から省く。
            && ScoreMatedInMaxPly < bestScore)
        {
            assert(move != ttMove);
            // move count based pruning
            if (depth < 16 * OnePly
                && FutilityMoveCounts[depth] <= moveCount
                && (threatMove.isNone() || !refutes(pos, move, threatMove)))
            {
                if (SPNode) {
                    splitPoint->mutex.lock();
                }
                continue;
            }

            // score based pruning
            const Depth predictedDepth = newDepth - reduction<PVNode>(depth, moveCount);
            // gain を 2倍にする。
            const Score futilityScore = ss->staticEval + futilityMargin(predictedDepth, moveCount)
                + 2 * gains.value(move.isDrop(), colorAndPieceTypeToPiece(pos.turn(), move.pieceTypeFromOrDropped()), move.to());

            if (futilityScore < beta) {
                bestScore = std::max(bestScore, futilityScore);
                if (SPNode) {
                    splitPoint->mutex.lock();
                    if (splitPoint->bestScore < bestScore) {
                        splitPoint->bestScore = bestScore;
                    }
                }
                continue;
            }

            if (predictedDepth < 4 * OnePly
                && pos.seeSign(move) < ScoreZero)
            {
                if (SPNode) {
                    splitPoint->mutex.lock();
                }
                continue;
            }
        }

        // RootNode, SPNode はすでに合法手であることを確認済み。
        if (!RootNode && !SPNode && !pos.pseudoLegalMoveIsLegal<false, false>(move, ci.pinned)) {
            --moveCount;
            continue;
        }

        isPVMove = (PVNode && moveCount == 1);
        ss->currentMove = move;
        if (!SPNode && !captureOrPawnPromotion && playedMoveCount < 64) {
            movesSearched[playedMoveCount++] = move;
        }

-----------------------------------step14
差し手で局面を進める

pos.doMove(move, st, ci, givesCheck);
(ss+1)->staticEvalRaw.p[0][0] = ScoreNotEvaluated;

-------------------------------step15
LMR

条件①  
3 * OnePly <= depthで 
PVnodeではなく
駒鳥または歩の成る手ではなく
現在探索中の差し手はTTによる指し手またはkillermoveではない場合

そんなにいい指し手であるとは言えないので
深さを削減しその深さでnullwindow探索を行ってみて
もしその結果の評価値がalpha値を超えればdoFullDepthSearchフラグをtrueにする

①の条件を満たさない場合
PVnodeである場合のみdoFullDepthSearchフラグをtrueにする

if (3 * OnePly <= depth
            && !isPVMove
            && !captureOrPawnPromotion
            && move != ttMove
            && ss->killers[0] != move
            && ss->killers[1] != move)
        {
            ss->reduction = reduction<PVNode>(depth, moveCount);
            if (!PVNode && cutNode) {
                ss->reduction += OnePly;
            }
            const Depth d = std::max(newDepth - ss->reduction, OnePly);
            if (SPNode) {
                alpha = splitPoint->alpha;
            }
            // PVS
            score = -search<NonPV>(pos, ss+1, -(alpha + 1), -alpha, d, true);

            doFullDepthSearch = (alpha < score && ss->reduction != Depth0);
            ss->reduction = Depth0;
        }
        else {
            doFullDepthSearch = !isPVMove;
        }

---------------------------step16
full depth search

doFullDepthSearchのフラグが立っていればnullwindow探索

PVnodeまたはnullwindow探索で出てきた評価値がalphaよりも大きければ通常窓の探索

if (doFullDepthSearch) {
            if (SPNode) {
                alpha = splitPoint->alpha;
            }

            //nullwindow探索
            score = (newDepth < OnePly ?
                     (givesCheck ? -qsearch<NonPV, true>(pos, ss+1, -(alpha + 1), -alpha, Depth0)
                      : -qsearch<NonPV, false>(pos, ss+1, -(alpha + 1), -alpha, Depth0))
                     : -search<NonPV>(pos, ss+1, -(alpha + 1), -alpha, newDepth, !cutNode));
        }

        // 通常の探索
        if (PVNode && (isPVMove || (alpha < score && (RootNode || score < beta)))) {
            score = (newDepth < OnePly ?
                     (givesCheck ? -qsearch<PV, true>(pos, ss+1, -beta, -alpha, Depth0)
                      : -qsearch<PV, false>(pos, ss+1, -beta, -alpha, Depth0))
                     : -search<PV>(pos, ss+1, -beta, -alpha, newDepth, false));
        }

----------------------------------step17
差し手で局面を戻す

pos.undoMove(move);//局面を戻す

----------------------------------step18

SPnode関連の処理

Rootnodeの差し手の探索であり、
PVまたはalpha値を超える評価値を持つ指し手であればそのrootmoveの評価値としてその値を代入(後でソートする為)

そうでないrootnodeの差し手であればrootmoveの評価値として-ScoreInfiniteを代入(ソートの速度を上げるため)

if (SPNode) {
            splitPoint->mutex.lock();
            bestScore = splitPoint->bestScore;
            alpha = splitPoint->alpha;
        }

        if (signals.stop || thisThread->cutoffOccurred()) {
            return score;
        }

        if (RootNode) {
            RootMove& rm = *std::find(rootMoves.begin(), rootMoves.end(), move);//rootmoveの集合の中から現在の差し手を探す
            if (isPVMove || alpha < score) {
                // PV move or new best move
                rm.score_ = score;//評価を新しい値に書き換え

                rm.extractPvFromTT(pos);

                if (!isPVMove) {
                    ++bestMoveChanges;
                }
            }
            else {
                rm.score_ = -ScoreInfinite;
            }
        }

        if (bestScore < score) {
            bestScore = (SPNode ? splitPoint->bestScore = score : score);

            if (alpha < score) {
                bestMove = (SPNode ? splitPoint->bestMove = move : move);

                if (PVNode && score < beta) {
                    alpha = (SPNode ? splitPoint->alpha = score : score);
                }
                else {
                    // fail high
                    if (SPNode) {
                        splitPoint->cutoff = true;
                    }
                    break;
                }
            }
        }

--------------------------step19
SPNode関連の処理
SPnodeというのが何かわからないためここでは回折はパスする。

if (!SPNode
            && threads.minSplitDepth() <= depth
            && threads.availableSlave(thisThread)
            && thisThread->splitPointsSize < MaxSplitPointsPerThread)
        {
            assert(bestScore < beta);
            thisThread->split<FakeSplit>(pos, ss, alpha, beta, bestScore, bestMove,
                                         depth, threatMove, moveCount, mp, NT, cutNode);
            if (beta <= bestScore) {
                break;
            }
        }
    }

    if (SPNode) {
        return bestScore;
    }

--------------------------step20
評価値によるbeta cut等の処理

この局面での差し手が生成できなければ後何手で積まされてしまうかの評価値を返す

beta cutされるような評価値であればTTにそれを保存しkiller手を更新し
historyを更新(?)し、評価値を返す

そのような差し手でなければTTにその情報を保存し、評価値を返す

 if (moveCount == 0) {
        return !excludedMove.isNone() ? alpha : matedIn(ss->ply);
    }

    if (bestScore == -ScoreInfinite) {
        assert(playedMoveCount == 0);
        bestScore = alpha;
    }

    if (beta <= bestScore) {
        // failed high
        tt.store(posKey, scoreToTT(bestScore, ss->ply), BoundLower, depth,
                 bestMove, ss->staticEval);

        if (!bestMove.isCaptureOrPawnPromotion() && !inCheck) {
            if (bestMove != ss->killers[0]) {
                ss->killers[1] = ss->killers[0];
                ss->killers[0] = bestMove;
            }

            const Score bonus = static_cast<Score>(depth * depth);
            const Piece pc1 = colorAndPieceTypeToPiece(pos.turn(), bestMove.pieceTypeFromOrDropped());
            history.update(bestMove.isDrop(), pc1, bestMove.to(), bonus);

            for (int i = 0; i < playedMoveCount - 1; ++i) {
                const Move m = movesSearched[i];
                const Piece pc2 = colorAndPieceTypeToPiece(pos.turn(), m.pieceTypeFromOrDropped());
                history.update(m.isDrop(), pc2, m.to(), -bonus);
            }
        }
    }
    else {
        // failed low or PV search
        tt.store(posKey, scoreToTT(bestScore, ss->ply),
                 ((PVNode && !bestMove.isNone()) ? BoundExact : BoundUpper),
                 depth, bestMove, ss->staticEval);
    }

    assert(-ScoreInfinite < bestScore && bestScore < ScoreInfinite);

    return bestScore;

以上!!

initSearchTable()で探索のパラメーターは決定される