Starting with quiescence search

[Sven]

Sven answer read!

Is what I was understood except one thing I understand I´m not sure if it is what you is saying.

You said that if some capture not improve the score (cause for example the value of the piece you captured is less than the score yor lost cause the worst position you reach after did it) you could stop the search as there was not capture to do?
Sounds good no matter actualy for my evaluation that just consider material has not relevance.

I have only a vague idea what your question is. The algorithm for quiescence search without alpha-beta is basically like this:

Code: Select all

QS(pos) {
    score := StaticEvaluation(pos)
    for (all captures and promotions) {
        makeMove()
        score := max(score, -QS(pos))
        unmakeMove()
    }
    return score
}

where StaticEvaluation() returns a score from the viewpoint of the moving side.

After adding alpha-beta it looks like this:

Code: Select all

QS(pos, alpha, beta) {
    score := StaticEvaluation(pos)
    if (score >= beta) return beta;
    alpha := max(alpha, score)
    for (all captures and promotions) {
        makeMove()
        alpha := max(alpha, -QS(pos, -beta, -alpha))
        unmakeMove()
        if (alpha >= beta) return beta
    }
    return alpha
}

You need to understand this to understand QS. You also need to understand how recursion works. QS is not much different from regular full-width search, the main difference is that you assume that all "quiet" moves do not make the position weaker so that the static eval can be taken as the minimum score that the moving side has "safe", and tries to improve by capturing. If none of the captures you try improve the score then the score is the static eval score, so in this case it looks as if you "did not make a move". This is necessary since usually capturing is not forced so you must not assume that you are losing if your best capture is losing.

[Luis Babboni]

...
If none of the captures you try improve the score then the score is the static eval score
...

The evaluation is make after each capture or just, as in non QS search,after all posible consecutevely captures end?
I´d asume just after all possible captures, specially now that I know that QS nodes needed to be visited use to be similar in amount than non QS search nodes that is not what I guessed before starting think in it.

May be this is obviously shown in the code you posted but I still not undersntand it so much.

By the way, could be possible that if the engine is too slow the QS is not a good idea?
I´m still not sure if I did some bug but in the first test I did, the withoutQS version is far better than the withQS version. The problem seems to be that in 40/4 the without QS use to reach 6 or 7 plies depth while the withQS use to reach 2 plies less in the non QS search so miss some combinations that not have captures in its first/s 1/2 move/s.

[AlvaroBegue]

My [mediocre] engine Ruydos has a very clean implementation of the basic quiescence search, so perhaps you can use it to learn from it.

I removed delta pruning for simplicity. Other than that, this is the actual code.

Code: Select all

int Engine::quiescence_search(int alpha, int beta, int from_root) {
  ++nodes_searched;
  bool in_check = board.is_in_check();

  if (!in_check) {
    int stand_pat_score = evaluate(board);
    if (stand_pat_score > alpha) {
      alpha = stand_pat_score;
      if (alpha >= beta)
        return alpha;
    }
  }

  unsigned moves[256];
  int n_moves = board.generate_captures(moves);
  sort_MVV_LVA(board, moves, n_moves);
  if (in_check)
    n_moves += board.generate_noncaptures(moves + n_moves);
  else
    n_moves += board.generate_noncapturing_promotions(moves + n_moves);

  int legal_moves = 0;

  for &#40;int i=0; i<n_moves; ++i&#41; &#123;
    // Skip non-promising captures
    if (!in_check && board.SEE&#40;moves&#91;i&#93;) <= 0&#41;
      continue;

    int score = -7999 + from_root;
    board.make_move&#40;moves&#91;i&#93;);
    if (!board.is_king_exposed&#40;)) &#123;
      ++legal_moves;
      score = board.draw&#40;) ? 0 &#58; -quiescence_search&#40;-beta, -alpha, from_root + 1&#41;;
    &#125;
    board.undo_move&#40;);

    if &#40;score > alpha&#41; &#123;
      alpha = score;
      if &#40;alpha >= beta&#41;
        break;
    &#125;
  &#125;

  if &#40;in_check && legal_moves == 0&#41;
    alpha = -7999 + from_root;

  return alpha;
&#125;

Let me know if you have any questions.

[Luis Babboni]

Thanks Álvaro, but I do not know C++, I programming in FreeBasic.
I could try to understand it as a kind of pseudocode, but is not easy to do it for me.

[Sven]

...
If none of the captures you try improve the score then the score is the static eval score
...

The evaluation is make after each capture or just, as in non QS search,after all posible consecutevely captures end?
I´d asume just after all possible captures, specially now that I know that QS nodes needed to be visited use to be similar in amount than non QS search nodes that is not what I guessed before starting think in it.

May be this is obviously shown in the code you posted but I still not undersntand it so much.

By the way, could be possible that if the engine is too slow the QS is not a good idea?
I´m still not sure if I did some bug but in the first test I did, the withoutQS version is far better than the withQS version. The problem seems to be that in 40/4 the without QS use to reach 6 or 7 plies depth while the withQS use to reach 2 plies less in the non QS search so miss some combinations that not have captures in its first/s 1/2 move/s.

To directly answer your question: during QS you call the evaluation at the beginning of each node.

The problem is understanding the concepts of tree search in general and here especially quiescence search (QS). I suggest that you try to take a completely different perspective. Currently you are thinking in terms of a large sequence of operations that has to be performed to find the desired result. It will become much easier when looking at it the right way.

We solve the problem of searching a tree of chess variations (to find the best move that our engine shall play) by decomposing it into smaller sub-problems. The top-level problem is: find the best move at the root node (and its score). Among the other sub-problems which also include generating moves, making and unmaking them (thus traversing edges of the tree), and evaluating a position, we have the full-width search of an arbitrary chess position (node) to a desired depth and the quiescence search of a node which we apply at those nodes where the remaining depth for a full-width search has become zero (and at all nodes within a QS subtree, of course). Each node can be a terminal node (= leaf node) or an intermediate node (or whatever you call it). Now try to only think of what has to be done *at the current node*. By making a move you visit a new node, and there you solve a new sub-problem, the result of which will (or may) be used after unmaking that move and thus returning to the parent node. But don't mix these views into one, only look at one node at a time.

(This is about "recursion". It is possible to do it differently but in the beginning it might be more difficult to understand.)

If you ignore QS for a moment then tree search is very simple: your best move at each node is the move for which searching its subtree returns the best score from your perspective (which is the worst score from the opponent's view).

By adding QS you add a new type of node: the QS node. What do you do at a QS node? Usually the same as at a full-width node: you want to get back the best move and the score (but I would ignore the "best move" part for now), and you get it by searching all subtrees (of capture moves). The difference to full-width search is, at each QS node you start by calling the static eval to get a minimum score from viewpoint of moving side.

There is more, of course (and again I left out alpha-beta in the beginning), but the first goal should be to get a feeling of how tree search works.

[Luis Babboni]

Thanks for your time guys!

I´m working in it!

[thomasahle]

This is the QS from sunfish:

Code: Select all

    def quiescence(self, pos, gamma):
        if pos.score <= -MATE_LOWER&#58;
            return -MATE_UPPER
        score = pos.score
        for move in sorted&#40;pos.gen_moves&#40;), key=pos.value, reverse=True&#41;&#58;
            if score >= gamma&#58;
                break
            if pos.value&#40;move&#41; >= 150&#58;
                score = max&#40;score, -self.quiescence&#40;pos.move&#40;move&#41;, 1-gamma&#41;)
        return score

It's MTDf, so there is just one parameter gamma, rather than alpha and beta. Other that that it's very standard. It starts by checking if pos.score is already high enough to get a cutoff. Otherwise it sorts the moves by how much they improve the evaluation, and cuts off any moves that don't improve it by 150cp, which is all the captures.

For most people MVV/LVA ordering of the moves would probably work better, but in my case sorting this way seems to work just as well. My search also doesn't check that the moves are actually legal. If they are not, the reply will be a king capture, immediately refuting the illegal move.

[Karlo Bala]

This is the QS from sunfish:

Code: Select all

    def quiescence(self, pos, gamma):
        if pos.score <= -MATE_LOWER&#58;
            return -MATE_UPPER
        score = pos.score
        for move in sorted&#40;pos.gen_moves&#40;), key=pos.value, reverse=True&#41;&#58;
            if score >= gamma&#58;
                break
            if pos.value&#40;move&#41; >= 150&#58;
                score = max&#40;score, -self.quiescence&#40;pos.move&#40;move&#41;, 1-gamma&#41;)
        return score

It's MTDf, so there is just one parameter gamma, rather than alpha and beta. Other that that it's very standard. It starts by checking if pos.score is already high enough to get a cutoff. Otherwise it sorts the moves by how much they improve the evaluation, and cuts off any moves that don't improve it by 150cp, which is all the captures.

For most people MVV/LVA ordering of the moves would probably work better, but in my case sorting this way seems to work just as well. My search also doesn't check that the moves are actually legal. If they are not, the reply will be a king capture, immediately refuting the illegal move.

Not necessarily. It is a zero window search (with one parameter), a very common implementation in PVS.
https://chessprogramming.wikispaces.com ... %20+%20ZWS

[Luis Babboni]

Hi people!

actually it seems I have no bug in my withQS version of Soberango but there is no improve over withoutQS version, in fact is worse.

The point seems to me that the time needed in the selective search do not allow the engine to reach the same depth in complete search as withoutQS and this is a greater disavantage than the advantage of use QS.

Is a known possible problem or may be I´m doing something wrong?

Note: actually the QS search continues only with promotions or captures that improve the score respect the static evaluation.

Thanks for comment!

[Luis Babboni]

Question,

QS uses to start at depth 1 or is better to start just after some time/depth to not waste time in early depths?
I tried with different options and not find a better combination than directly not use QS.