After few tries I realized that it only works well when used to prove that the first move of root move list is not worse than some bound (gamma) and other moves are not better than gamma. It works poorly when it is needed to find a new gamma. But finding true score is what PVS is made for, so I implemented a version of root_search that tries to verify that gamma does not change, but falls back to PVS whenever necessary.
MTD verification does not change the first move, so its only purpose is to speed up search and hopefully find a better move at higher depth PVS. I also made some changes to time management to reflect that it is good idea to save time when there is no change of gamma, so we could have more time to finish that higher depth PVS iteration.
I did not make any other optimizations, and I nearly did not test it at all. Now the search somewhat works, and does not look very ugly when watching it, but I have no idea if it is better or worse then pure PVS.
Anyway, here is what diff says, if you are interested.
Code: Select all
vrato@notas:~/Prg/stockfish-171-mtd/src$ diff -d search.cpp ../../stockfish-171-ja/src/search.cpp
283d282
< Value root_search_pv(Position& pos, SearchStack ss[], RootMoveList& rml, Value* alphaPtr, Value* betaPtr);
715,743d713
< // If we had successfull MTD verification, Iteration is a little ahead,
< // and we would need more time in case of PVS fallback,
< // so better idea is to save time for harder times.
< if (Iteration >= 7 && ValueByIteration[Iteration - 1] == ValueByIteration[Iteration]
< && current_search_time() > ((MaxSearchTime + ExtraSearchTime) * 70) / 128)
< stopSearch = true;
<
< // If we had 2 succesive MTD verifications, Iteration is high,
< // and we would need much more time in case of PVS fallback,
< // so better idea is to save time for harder times.
< if (Iteration >= 8 && ValueByIteration[Iteration - 1] == ValueByIteration[Iteration]
< && ValueByIteration[Iteration - 2] == ValueByIteration[Iteration - 1]
< && current_search_time() > ((MaxSearchTime + ExtraSearchTime) * 60) / 128)
< stopSearch = true;
<
< // And 3 succesive MTD verifications even more.
< if (Iteration >= 9 && ValueByIteration[Iteration - 1] == ValueByIteration[Iteration]
< && ValueByIteration[Iteration - 2] == ValueByIteration[Iteration - 1]
< && ValueByIteration[Iteration - 3] == ValueByIteration[Iteration - 2]
< && current_search_time() > ((MaxSearchTime + ExtraSearchTime) * 50) / 128)
< stopSearch = true;
<
< // 4 Succesive MTD verifications, that is max for now.
< if (Iteration >= 10 && ValueByIteration[Iteration - 1] == ValueByIteration[Iteration]
< && ValueByIteration[Iteration - 2] == ValueByIteration[Iteration - 1]
< && ValueByIteration[Iteration - 3] == ValueByIteration[Iteration - 2]
< && current_search_time() > ((MaxSearchTime + ExtraSearchTime) * 40) / 128)
< stopSearch = true;
<
768d737
<
807c776
< // root_search_pv() is the function which searches the root node. It is
---
> // root_search() is the function which searches the root node. It is
811d779
< // The original PVS version of root_search() used by MTD as a fallback.
813c781
< Value root_search_pv(Position& pos, SearchStack ss[], RootMoveList& rml, Value* alphaPtr, Value* betaPtr) {
---
> Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value* alphaPtr, Value* betaPtr) {
1038c1006
< } // End of root move list.
---
> }
1055,1276d1022
<
<
< // root_search() is the function which searches the root node. It is
< // similar to root_search_pv except that it only verifies that the first move score
< // stays at least at gamma and other move scores stay at most at gamma.
< // If not, root_search_pv() is called.
< // There are no fail high or fail low loops.
<
< // The experimental minimalistic MTD form of root_search() by Vratko Polak.
<
< Value root_search(Position& pos, SearchStack ss[], RootMoveList& rml, Value* alphaPtr, Value* betaPtr) {
<
< // MultiPV is Not Supported (MNS).
< // Also, at low Iterations it is for some reason not safe to do MTD.
< if (1 < MultiPV || Iteration <= 6)
< return root_search_pv(pos, ss, rml, alphaPtr, betaPtr);
<
< EvalInfo ei;
< StateInfo st;
< CheckInfo ci(pos);
< int64_t nodes;
< Move move;
< Depth depth, ext, newDepth;
< Value bound, gamma;
< bool isCheck, moveIsCheck, captureOrPromotion, dangerous;
<
< bound = - VALUE_INFINITE;
< // The natural choice for the initial gamma is the score from previous iteration.
< gamma = *alphaPtr / 2 + *betaPtr / 2;
< isCheck = pos.is_check();
<
< // Step 1. Initialize node and poll (omitted at root, but I can see no good reason for this, FIXME)
< // Step 2. Check for aborted search (omitted at root, because we do not initialize root node)
< // Step 3. Mate distance pruning (omitted at root)
< // Step 4. Transposition table lookup (omitted at root)
<
< // Step 5. Evaluate the position statically
< // At root we do this only to get reference value for child nodes
< if (!isCheck)
< ss[0].eval = evaluate(pos, ei, 0);
< else
< ss[0].eval = VALUE_NONE; // HACK because we do not initialize root node
<
< // Step 6. Razoring (omitted at root)
< // Step 7. Static null move pruning (omitted at root)
< // Step 8. Null move search with verification search (omitted at root)
< // Step 9. Internal iterative deepening (omitted at root)
<
< // Sort the moves before to (re)search
< rml.sort();
<
< // Step extra. Fail low loop (ommited at MTD root search).
< {
< // Step 10. Loop through all moves in the root move list
< for (int i = 0; i < rml.move_count() && !AbortSearch; i++)
< {
< // This is used by time management
< // Not much gain from finishing MTD iteration, better save time.
< FirstRootMove = true; // (0 == i);
<
< // Save the current node count before the move is searched
< nodes = TM.nodes_searched();
<
< // Reset beta cut-off counters
< TM.resetBetaCounters();
<
< // Pick the next root move, and print the move and the move number to
< // the standard output.
< move = ss[0].currentMove = rml.get_move(i);
<
< if (current_search_time() >= 1000)
< cout << "info currmove " << move
< << " currmovenumber " << i + 1 << endl;
<
< moveIsCheck = pos.move_is_check(move);
< captureOrPromotion = pos.move_is_capture_or_promotion(move);
<
< // Step 11. Decide the new search depth
< depth = (Iteration - 2) * OnePly + InitialDepth;
< ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous);
< newDepth = depth + ext;
<
< // Step 12. Futility pruning (omitted at root)
<
< bound = - VALUE_INFINITE;
<
< // Step extra. Fail high loop (omitted at MTD root search).
< {
< // Step 13. Make the move
< pos.do_move(move, st, ci, moveIsCheck);
<
< // Step extra. pv search (omitted at MTD root search).
< // But we treat the first move the special way, anyway.
< if (1 > i)
< { // First move.
<
< // Full depth PV search, done on first move or after a fail high
< // In MTD, it is full depth, but not pv.
<
< // We want gamma to be the lower bound here, so upper bound is gamma - 1.
< bound = -search(pos, ss, -(gamma - 1), newDepth, 1, true, 0);
<
< } else { // Non-first move.
<
< // Step 14. Reduced search
< // if the move fails high will be re-searched at full depth
< bool doFullDepthSearch = true;
<
< if ( depth >= 3 * OnePly
< && !dangerous
< && !captureOrPromotion
< && !move_is_castle(move))
< {
< ss[0].reduction = pv_reduction(depth, i - MultiPV + 2);
< if (ss[0].reduction)
< {
< // Reduced depth non-pv search using gamma as upperbound
< bound = -search(pos, ss, -gamma, newDepth-ss[0].reduction, 1, true, 0);
< doFullDepthSearch = (bound > gamma);
< }
< }
<
< // Step 15. Full depth search
< if (doFullDepthSearch)
< {
< // Full depth non-pv search using gamma as upperbound
< ss[0].reduction = Depth(0);
< bound = -search(pos, ss, -gamma, newDepth, 1, true, 0);
< }
< } // End of non-first move case.
<
< // Step 16. Undo move
< pos.undo_move(move);
< } // End of fail high loop would be here.
<
< // Finished searching the move. If AbortSearch is true, the search
< // was aborted because the user interrupted the search or because we
< // ran out of time. In this case, the return value of the search cannot
< // be trusted, and we break out of the loop without updating the best
< // move and/or PV.
< if (AbortSearch)
< break;
<
< // Remember beta-cutoff and searched nodes counts for this move. The
< // info is used to sort the root moves for the next iteration.
< int64_t our, their;
< TM.get_beta_counters(pos.side_to_move(), our, their);
< rml.set_beta_counters(i, our, their);
< rml.set_move_nodes(i, TM.nodes_searched() - nodes);
<
< assert(bound >= -VALUE_INFINITE && bound <= VALUE_INFINITE);
<
< // Step 17. Check for new best move
< if (bound <= gamma && i >= 1) // MNS
< rml.set_move_score(i, -VALUE_INFINITE);
< else
< {
< // PV move or new best move!
< // That means just bound > gamma or 0 == i
< // It is just a candidate for new best move OR the first move. We need if.
< if (0 == i)
< { // The first move.
<
< // Now, if the first move have failed low, (bound < gamma) we anticipate gamma will change.
< // So we happily leave the work of finding new gamma to PVS.
< if (bound < gamma)
< {
< // We are failing low, which is analogous to AspirationFailLow of PVS.
< AspirationFailLow = true;
< if (AspirationFailLow && StopOnPonderhit)
< StopOnPonderhit = false;
<
< // Update PV, but not score, to not change the move order.
< update_pv(ss, 0);
< TT.extract_pv(pos, ss[0].pv, PLY_MAX);
< rml.set_move_pv(i, ss[0].pv);
<
< // Print information to the standard output
< print_pv_info(pos, ss, gamma - 1, gamma, bound);
<
< // We to not touch the aspiration window.
< return root_search_pv(pos, ss, rml, alphaPtr, betaPtr);
< }
<
< } else { // Non-first candidate move.
<
< // We are failing high on a non-first move.
< // If we shift gamma, the first move might fail low, so it is like AspirationFailLow again.
< AspirationFailLow = true;
< if (AspirationFailLow && StopOnPonderhit)
< StopOnPonderhit = false;
<
< // We shift the aspiration window, so AspirationFailLow would stay true, if the first move does not improve.
< *betaPtr = Min(bound - 1 + 2 * AspirationDelta, VALUE_INFINITE);
< *alphaPtr = bound - 1;
<
< // Update scores
< rml.set_move_score(0, bound + 1); // So that the first move will stay first after sort.
< rml.set_move_score(i, bound); // And the candidate comes second, with a fail high score.
<
< // Update PV, but not score, to not change the move order.
< update_pv(ss, 0);
< TT.extract_pv(pos, ss[0].pv, PLY_MAX);
< rml.set_move_pv(i, ss[0].pv);
<
< // Print information to the standard output
< print_pv_info(pos, ss, gamma - 1, gamma, bound);
<
< return root_search_pv(pos, ss, rml, alphaPtr, betaPtr);
< }
< } // PV move or new best move
<
< } // End of root move list.
<
< } // End of fail low loop would be here.
<
< // So we have finally finished (or aborted) the MTD iteration. Let us sort and return.
< rml.sort(); // Perhaps redundant.
< return gamma;
<
< } // End of root_search().
<
