http://web.archive.org/web/200404270138 ... ing/pv.htm
At the very top of my pvs-search I return immediately (without TT updating or pv updating) whenever I detect a draw by repetition. Whenever alpha is improved, I update the pv array as per Moreland's method.
Now for the bug: whenever there is a repetition present in the pv, the pv itself continues for a few more plies, even though the search never continues beyond the repetition! Somehow moves can be copied into the pv from different nodes, but I have a hard time understanding why. Furthermore, I can get the problem to go away by moving the declaration of the pv array inside the loop over moves (rather than before the start of the loop, as per Moreland's method).
Any insights would be welcomed!
Below the code for which the problem manifests itself. Note that I use a std::vector as the container to hold the pv. I clear this vector every time before it is updated. The squeeze and stretch functions around the alpha, beta parameters and search results are used to adjust mate scores. I use a scheme where scores are counted from their terminal positions, not from the root (Miguel Ballicora explained this here a while ago, except that he does this adjustment at the very beginning and end of his search).
Code: Select all
typedef std::vector<int> Sequence;
typedef std::vector<int> Order;
// principal variation search (PVS)
template<typename Rules, typename Board> template<int NodeType>
int Root<Rules, Board>::pvs(const Position<Board>& p, int ply, int depth, int alpha, int beta, Variation& parent_node)
{
if (is_interrupted())
return alpha;
statistics_.update(ply);
// check for a legal draw
if (is_draw<Rules>(p))
return draw_value();
// return evaluation in leaf nodes with valid moves
if (depth <= 0)
return !Successor<successor::Legal, Rules>::detect(p)? loss_value(0) : Evaluate<Rules>::evaluate(p);
BOOST_ASSERT(depth > 0);
BOOST_ASSERT(alpha >= -infinity());
BOOST_ASSERT(beta <= infinity());
// mate distance pruning
if (alpha >= win_value(1))
return alpha;
if (beta <= loss_value(0))
return beta;
BOOST_ASSERT(
( is_pv(NodeType) && alpha < beta - 1) ||
(!is_pv(NodeType) && alpha == beta - 1)
);
// TT cut-off for exact win/loss scores or for deep enough heuristic scores
auto TT_entry = TT.find(p);
if (TT_entry && (is_mate(TT_entry->value()) || TT_entry->depth() >= depth) && TT_entry->is_cutoff(alpha, beta))
return TT_entry->value();
// generate moves
Stack moves;
moves.reserve(32);
Successor<successor::Legal, Rules>::generate(p, moves);
// without a valid move, the position is an immediate loss
if (moves.empty()) {
const auto value = loss_value(0);
// we can only have an upper bound or an exact value at this point
BOOST_ASSERT(value < beta);
const auto bound = (value <= alpha)? Transposition::upper_bound : Transposition::exact_value;
TT.insert(p, Transposition(value, bound, depth, Transposition::no_move()));
return value;
}
// internal iterative deepening
if (!(TT_entry && TT_entry->has_move())) {
const auto IID_depth = is_pv(NodeType)? depth - 2 : depth / 2;
if (IID_depth > 0) {
pvs<NodeType>(p, ply, IID_depth, alpha, beta, parent_node);
TT_entry = TT.find(p);
BOOST_ASSERT(TT_entry);
}
}
// move ordering
std::vector<int> move_order;
move_order.reserve(moves.size()); // reserve enough room for all indices
iota_n(std::back_inserter(move_order), moves.size(), 0); // generate indices [0, moves.size() - 1]
if (TT_entry && TT_entry->has_move()) {
const auto TT_move = TT_entry->move() % moves.size();
std::swap(move_order[0], move_order[TT_move]);
}
// search moves
const auto original_alpha = alpha;
auto best_value = -infinity();
auto best_move = Transposition::no_move();
int value;
int i;
Variation child_node; // moving this declaration inside the loop will cure the "repetition along the pv" problem
for (auto s = 0; s < static_cast<int>(move_order.size()); ++s) {
i = move_order[s];
// TODO: TT singular extension
// TODO: futility pruning
// copy-make the next move
auto q = p;
q.attach(p);
q.template make<Rules>(moves[i]);
if (is_pv(NodeType) && s == 0)
value = -squeeze(pvs<PV>(q, ply + 1, depth - 1, -stretch(beta), -stretch(alpha), child_node));
else {
// TODO: late move reductions
value = -squeeze(pvs<ZW>(q, ply + 1, depth - 1, -stretch(alpha + 1), -stretch(alpha), child_node));
if (is_pv(NodeType) && value > alpha && value < beta)
value = -squeeze(pvs<PV>(q, ply + 1, depth - 1, -stretch(beta), -stretch(alpha), child_node));
}
if (value > best_value) {
best_value = value;
best_move = i;
if (best_value >= beta)
break;
if (best_value > alpha) {
alpha = best_value;
parent_node.set_pv(best_move, child_node.pv());
}
}
}
// we must have found a best move with a finite value
BOOST_ASSERT(is_finite(best_value));
BOOST_ASSERT(best_move != Transposition::no_move());
// determine the bound type of the value
const auto bound =
best_value <= original_alpha ? Transposition::upper_bound :
best_value >= beta ? Transposition::lower_bound : Transposition::exact_value;
TT.insert(p, Transposition(best_value, bound, depth, best_move));
return best_value;
}
class Variation
{
public:
// views
const Sequence& pv() const
{
return pv_;
}
int best_move() const
{
return *pv_.begin();
}
// modifiers
void set_pv(int first_move, const Sequence& continuation)
{
pv_.clear();
BOOST_ASSERT(pv_.size() == 0);
pv_.push_back(first_move);
BOOST_ASSERT(pv_.size() == 1);
pv_.insert(pv_.end(), continuation.begin(), continuation.end());
BOOST_ASSERT(pv_.size() == 1 + continuation.size());
}
private:
// representation
Sequence pv_;
};
