Quiescence Search doesn't improve strength

[lithander]

When I wrote RomiChess the eval was done before Qsearch was written. It ran slow. The node rate was great but it did not search very deep at all. As soon as I added Qsearch it was the deepest single thread searcher that I knew of at the time of its release. Even today it is not bad.

But when you finally added QSearch you probably had not only a pretty good evaluation function but also several sophsticated pruning methods in addition to just alpha beta, right?

I have nothing but MVV-LVA implemented at this point which doesn't profit of a good the evaluation. Or should it? Could it...? I guess you could score a move by the difference in the static evaluation it causes instead of the MVV-LVA value of the captured peaces. It's worth a try.

You example of how a changing PV hurts the pruning of the following iteration requires something like history heuristics or a hashtable or something comparable? Otherwise, how would the previous PV be relevant to the AB search?

By now I think that I was a little early to implement QSearch and that it really unleashes it's power in combination with a very good eval *and* pruning techniques that rely on a very good evaluation and getting rid of the horizon effect. And I don't have these, yet.

For Context:

The current development branch of my engine is basically having the same features as Rustic Alpha. For the upcoming release of version 0.3 I'm trying to implement all features suggested by Marcel and Sven in this thread as essential for a minimal engine.

• Board representation
• Move generator
• Alpha/Beta search
• QSearch
• MVV-LVA move sorting
• Evaluation: Material count and PST
• Iterative deepening
• Time controls

The bold things are features that were not present in version 0.2 (1050 ELO on CCRL) and that I'm adding right now. I'm just trying to make sure there are no bugs hidden in there but for that assessment I need to form realistic expectations of what these features, correctly implemented, should do for me. I think I can expect 1500-1600 ELO? (My move generator is very simple and thus a little slow) But the depths RomiChess64P3n achieves on the startpositon are waaaaaay out of reach in my situation, I think. With the above listed features 7-8 plys in one secodn of computation is a more realistic goal, or what would you say?

[Sven]

I get the impression that you might draw conclusions too early. Have you really sorted out that there is no bug involved? The most common reason for unusual behaviour is a bug ... That might be everywhere: in your search, move ordering, evaluation, especially PST implementation (since that one is new), ... A very common mistake (and one that I made often enough myself!) is to believe that something works as it should, without testing it.

Wrong signs, uninitialized data, typos that let you use a different but also existing variable, copy&paste stuff, ... So many ways to go wrong without seeing it when staring at the code.

In other words: I still believe what I already wrote ...

In general a PST should improve the search when applied correctly.

Do you search the best root move from the previous iteration as first move in the next iteration?

[Mike Sherwin]

When I wrote RomiChess the eval was done before Qsearch was written. It ran slow. The node rate was great but it did not search very deep at all. As soon as I added Qsearch it was the deepest single thread searcher that I knew of at the time of its release. Even today it is not bad.

But when you finally added QSearch you probably had not only a pretty good evaluation function but also several sophsticated pruning methods in addition to just alpha beta, right?

I have nothing but MVV-LVA implemented at this point which doesn't profit of a good the evaluation. Or should it? Could it...? I guess you could score a move by the difference in the static evaluation it causes instead of the MVV-LVA value of the captured peaces. It's worth a try.

You example of how a changing PV hurts the pruning of the following iteration requires something like history heuristics or a hashtable or something comparable? Otherwise, how would the previous PV be relevant to the AB search?

By now I think that I was a little early to implement QSearch and that it really unleashes it's power in combination with a very good eval *and* pruning techniques that rely on a very good evaluation and getting rid of the horizon effect. And I don't have these, yet.

For Context:

The current development branch of my engine is basically having the same features as Rustic Alpha. For the upcoming release of version 0.3 I'm trying to implement all features suggested by Marcel and Sven in this thread as essential for a minimal engine.

• Board representation
• Move generator
• Alpha/Beta search
• QSearch
• MVV-LVA move sorting
• Evaluation: Material count and PST
• Iterative deepening
• Time controls

The bold things are features that were not present in version 0.2 (1050 ELO on CCRL) and that I'm adding right now. I'm just trying to make sure there are no bugs hidden in there but for that assessment I need to form realistic expectations of what these features, correctly implemented, should do for me. I think I can expect 1500-1600 ELO? (My move generator is very simple and thus a little slow) But the depths RomiChess64P3n achieves on the startpositon are waaaaaay out of reach in my situation, I think. With the above listed features 7-8 plys in one secodn of computation is a more realistic goal, or what would you say?

Every Engine has its own peculiarities. Just the order in which moves are generated can affect all sorts of things. I don't know if you are aware but I have an engine at about the same point of development as yours and Marcel's called Bricabrac. Let's compare list.

• Board representation - yes
• Move generator - yes
• Alpha/Beta search -yes
• QSearch - yes
• MVV-LVA move sorting - yes
• Evaluation: Material count and PST - yes
• Iterative deepening - yes
• Time controls

- yes (just seconds per move so far)

Bric also has of yesterday Principle variation search using the pvs[ply][ply] and pvl[ply] triangular array. This allows the principle variation to be searched and displayed. That is the extent of Bric right now. Just added the zero window part of pvs search. Running test against TSCP1.81 is so far Bric +2, -1, =5. Some of those draws are 3 fold reps in which Bric had a winning position. Three fold rep is next on the todo list. Then Bric will be a minimal engine in my opinion.

So you are aiming for 7 to 8 ply. In how long? I'll do a 60 second search of the original position with Bric as it is now, brb. Okay back.
FEN: rnbqkbnr/pppppppp/8/8/3P4/8/PPP1PPPP/RNBQKBNR b KQkq d3 0 1

Bricabrac:
1 00:00 20 20 +0.36 g1f3
2 00:00 87 87 0.00 g1f3 g8f6
3 00:00 701 701 +0.35 g1f3 g8f6 d2d4
4 00:00 4k 4k 0.00 g1f3 g8f6 d2d4 d7d5
5 00:00 9k 9k +0.33 g1f3 g8f6 d2d4 d7d5 b1c3
6 00:00 16k 16k 0.00 g1f3 g8f6 d2d4 d7d5 b1c3 b8c6
7 00:00 59k 59k +0.28 g1f3 g8f6 d2d4 d7d5 b1c3 b8c6 c1e3
8 00:00 197k 19,684k 0.00 g1f3 g8f6 d2d4 d7d5 b1c3 b8c6 c1e3 c8e6
9 00:00 3,094k 9,981k +0.29 e2e4 b8c6 g1f3 g8f6 b1c3 d7d5 e4d5 f6d5 d2d4
10 00:00 5,071k 10,142k +0.09 e2e4 e7e5 g1f3 b8c6 b1c3 g8f6 d2d4 e5d4 f3d4 f8d6
11 00:14 144,410k 9,959k +0.23 d2d4 d7d5 g1f3 b8c6 b1c3 g8f6 c1f4 c8e6 e2e3 f6e4 f1d3
12 00:19 204,401k 10,707k +0.02 d2d4 d7d5 g1f3 g8f6 b1c3 c8f5 c1e3 b8c6 f3e5 f6e4 c3e4 c6e5
13 00:35 365,906k 10,244k +0.25 d2d4 d7d5 g1f3 b8c6 b1c3 c8f5 c1f4 g8f6 e2e3 f6e4 c3e4 f5e4 f1d3

Ply 14 was started but did not finish in time. So bric finished ply 13 in 35 seconds. PVS adds a ply or maybe more. Maybe someone else can tell us how much. Anyway, your 7 to 8 ply expectation is very conservative. I do have one move ordering trick that I use in my engines that others do not use. And the idea has been extended in Bric but I don't know if the extension is any good. So to answer the question, I think that you can raise your expectations just a bit.

Bric's search function.

Code: Select all

s32 Search(Thread* t, Move* m, s32 alpha, s32 beta, s32 depth) {
  s32 mi, j, count = 0, goodness = 0;
  u64 n;
  Move* mov;

  if (depth == 0) return Qsearch(t, m, alpha, beta);

  if (clock() > end) return alpha;

  pvl[ply] = ply;

  n = GenMoves(t, m);

  if (!n) return -ILLEGAL;

 if (depth > 3) {
    for (mi = 0; mi < n; mi++) {
      mov = m + mi;
      MakeMove(t, mov);
      mov->score = -Qsearch(t, m + n, -beta - 1000, -alpha + 100);
      TakeBack(t, mov);
      goodness += (move->score >= beta);
    }
  }

 if (fpv) {
   for (mi = 0; mi < n; mi++) {
     mov = m + mi;
     if (mov->fs == pvs[0][ply].fs && mov->ts == pvs[0][ply].ts && mov->type == pvs[0][ply].type) {
       mov->score = 1000000;
       break;
     }
   }
  }

  for (mi = 0; mi < n; mi++) {
    Sort(t, m, mi, n);
    mov = m + mi;
    MakeMove(t, mov);
    if (goodness && mov->score >= beta) {
      mov->score = -Search(t, m + n, -beta, -beta + 1, depth - 3);
      if (mov->score < beta)
        mov->score = -Search(t, m + n, -beta, -alpha, depth - 1);
    }
    else {
      if (fpv) {
        mov->score = -Search(t, m + n, -alpha - 1, -alpha, depth - 1);
        if (m->score > alpha) mov->score = -Search(t, m + n, -beta, -alpha, depth - 1);
      }
      else {
        mov->score = -Search(t, m + n, -beta, -alpha, depth - 1);
      }
    }
    TakeBack(t, mov);
    fpv = false;
    if (mov->score == ILLEGAL) continue;
    count++;
    if (mov->score > alpha) {
      if (mov->score >= beta) return beta;
      alpha = mov->score;
      pvs[ply][ply] = *mov;
      for (j = ply + 1; j < pvl[ply + 1]; j++) pvs[ply][j] = pvs[ply + 1][j];
      pvl[ply] = pvl[ply + 1];
    }
  }
  if (!count) {
    if (InCheck[wtm](t, king[wtm])) {
      return -(MATE - ply);
    }
    else return STALEMATE;
  }
  return alpha;
}

[hgm]

I think you worry too much about a little slowdown for a given search depth. You have tested yourself that QS + PST gave you about 500 Elo at fixed depth. It would take an enormous slowdown to take that 500 Elo back. (Like a factor 100 or so.) I don't think you can ever be too early implementing QS.

You will gain a lot of depth once you implement null-move pruning. But I would not start with that right now.

Micro-Max 1.6 doesn't have more than you have now, but it has one thing: Internal Iterative Deepening. This does the iterative deepening you now do in the root in every node of the tree. The purpose is to find the best move, and then search that first at the next-higher depth.

The point is that the static move ordering you have now (MVV/LVA + non-captures in random order) will very often not pick the best move first. Not even if there is a capture. But if all pieces are sufficiently protected, (or no captures are possible at all), the engine is completely clueless. The chances that it will try a poor move first become very high in the face of a threat. By first trying the moves at lower depth, you weed out the blunders cheaply. Some times the deepening is done in steps of 2 ply, for IID. Doing a search of a single move at the requested depth is typically as expensive as searching all moves 2 ply less deep. So if on average the IID prevents you search 1 hopeless move before you find the cut move, you already break even.

Once you have a Transposition Table, the best move for one ply less deep than the currently requested search can usually be found in there, and this removes the need for finding it through IID. But even then, the IID will be helpful in the cases there is no hash move. So it is always useful to have it.

[mvanthoor]

Ply 14 was started but did not finish in time. So bric finished ply 13 in 35 seconds. PVS adds a ply or maybe more. Maybe someone else can tell us how much. Anyway, your 7 to 8 ply expectation is very conservative. I do have one move ordering trick that I use in my engines that others do not use. And the idea has been extended in Bric but I don't know if the extension is any good. So to answer the question, I think that you can raise your expectations just a bit.

If you reach ply 14 already without even having a hash table, what are you doing in the move ordering; putting the best move of the first iteration at the front I assume?

[mvanthoor]

Do you search the best root move from the previous iteration as first move in the next iteration?

What I've been wondering: as the best move is always in the hash table, do you actually NEED to search the best root move from the previous iteration, if you (eventually) will add a hash table anyway? The best move from the previous iteration will be in the PV; the hash table can be used to build a PV; so it stands to reason that the best move of the previous iteration has to be in the hash table, and thus if you have hash move ordering, you wouldn't need to order on the previous iteration's best move. They should be the same. (Or at least, most of the time; they wouldn't be the same if the PV changes.)

[Mike Sherwin]

Ply 14 was started but did not finish in time. So bric finished ply 13 in 35 seconds. PVS adds a ply or maybe more. Maybe someone else can tell us how much. Anyway, your 7 to 8 ply expectation is very conservative. I do have one move ordering trick that I use in my engines that others do not use. And the idea has been extended in Bric but I don't know if the extension is any good. So to answer the question, I think that you can raise your expectations just a bit.

If you reach ply 14 already without even having a hash table, what are you doing in the move ordering; putting the best move of the first iteration at the front I assume?

yes, I sort the root after each iteration. And if depth > 3 every move of the search is ordered by a preliminary one ply plus quiesce search with an open window for each move. There is more but man right now I need a quiescent knap!

[Ras]

What I've been wondering: as the best move is always in the hash table

You can't rely on that because no matter what replacement strategy you do, there will be some "replace always" final branch, and that can overwrite the root move. Also, you don't just want the root move, you'll want the whole PV from the previous iteration as leftmost path first, all of which are at the same risk.

I even have a root move refutation table to get the expected opponent reply for every root move so that I can try this first even when it isn't in the hash table. That doesn't do much with 256M for hash tables, but works nicely under low memory conditions.

[hgm]

It is very conceivable you will not have a hash move in the root: the user could have just loaded the position (or you came there through a book line), and set you thinking. If you never alter the move order in the root between iterations, you will be stuck with your initial ordering for the entire search.

[mvanthoor]

It is very conceivable you will not have a hash move in the root: the user could have just loaded the position (or you came there through a book line), and set you thinking. If you never alter the move order in the root between iterations, you will be stuck with your initial ordering for the entire search.

Hm. Maybe I should do my releases in episodes:

Rustic Alpha 1: Look ma, no features!
Rustic Alpha 2: Making a hash of it
Rustic Alpha 3: Getting your shit ordered

(I've been testing the hash-table, but it's disappointing when only using transpositions. It cuts off a lot of nodes, but the actual access is so expensive that time to depth is slower then without the hash table. But let's not hijack this topic.)