Move ordering using SEE

[algerbrex]

I've seen in several engines SEE being used for move ordering, and this seems like a good idea. More accuracy in good captures being searched first. Of course, SEE isn't free either, and this may be where I'm running into issues using any sort of SEE move ordering scheme.

The scheme I tried with SEE was the following:

• Hash move
• Winning captures (determined w/ SEE)
• Equal captures (determined w/ SEE)
• Killer moves
• History heuristic
• Losing captures (determined w/ SEE)

Which made sense in my mind, but actually resulted in Blunder becoming slower while searching. As I said, I suspect the trade-off between the overhead of using SEE over MVV-LVA and the accuracy gained is a losing one. I also tried putting losing captures before the history heuristic with similar results.

In my next couple of tests, I'm going to try only using SEE in QSearch for move ordering, and visa versa. And also putting losing captures at different places.

I'm curious if anyone else has found some success using a very different scheme than the one outlined above? Right now it just seems that SEE is too slow to compensate for the accuracy gained, which may just be the case.

[tcusr]

I've seen in several engines SEE being used for move ordering, and this seems like a good idea. More accuracy in good captures being searched first. Of course, SEE isn't free either, and this may be where I'm running into issues using any sort of SEE move ordering scheme.

The scheme I tried with SEE was the following:

• Hash move
• Winning captures (determined w/ SEE)
• Equal captures (determined w/ SEE)
• Killer moves
• History heuristic
• Losing captures (determined w/ SEE)

Which made sense in my mind, but actually resulted in Blunder becoming slower while searching. As I said, I suspect the trade-off between the overhead of using SEE over MVV-LVA and the accuracy gained is a losing one. I also tried putting losing captures before the history heuristic with similar results.

In my next couple of tests, I'm going to try only using SEE in QSearch for move ordering, and visa versa. And also putting losing captures at different places.

I'm curious if anyone else has found some success using a very different scheme than the one outlined above? Right now it just seems that SEE is too slow to compensate for the accuracy gained, which may just be the case.

are you using the recursive SEE? there's a faster iterative one
https://github.com/olithink/OliThink/bl ... ink.c#L684

[algerbrex]

I've seen in several engines SEE being used for move ordering, and this seems like a good idea. More accuracy in good captures being searched first. Of course, SEE isn't free either, and this may be where I'm running into issues using any sort of SEE move ordering scheme.

The scheme I tried with SEE was the following:

• Hash move
• Winning captures (determined w/ SEE)
• Equal captures (determined w/ SEE)
• Killer moves
• History heuristic
• Losing captures (determined w/ SEE)

Which made sense in my mind, but actually resulted in Blunder becoming slower while searching. As I said, I suspect the trade-off between the overhead of using SEE over MVV-LVA and the accuracy gained is a losing one. I also tried putting losing captures before the history heuristic with similar results.

In my next couple of tests, I'm going to try only using SEE in QSearch for move ordering, and visa versa. And also putting losing captures at different places.

I'm curious if anyone else has found some success using a very different scheme than the one outlined above? Right now it just seems that SEE is too slow to compensate for the accuracy gained, which may just be the case.

are you using the recursive SEE? there's a faster iterative one
https://github.com/olithink/OliThink/bl ... ink.c#L684

Ah no actually, I'm using the one based off the pseudo-code from the CPW, which looks similar to the code you posted. But I'll take a closer look at the link you posted to be sure, thanks.

[tcusr]

it was just a wild guess, i don't know how much difference there is between the two since i haven't implemented it yet

[algerbrex]

Cool no problem, appreciate the help.

[tcusr]

i've been reading see.go and maybe you should check if toSq is not attacked at all and immediately return
https://github.com/lucasart/Demolito/bl ... ion.c#L578

[Rebel]

I've seen in several engines SEE being used for move ordering, and this seems like a good idea. More accuracy in good captures being searched first. Of course, SEE isn't free either, and this may be where I'm running into issues using any sort of SEE move ordering scheme.

The scheme I tried with SEE was the following:

• Hash move
• Winning captures (determined w/ SEE)

What helped me in case there are multiple moves with an equal SEE value is to try the capture with the lowest piece value first. So, if a queen and a pawn safely can capture a piece try the pawn move first.

[*] Equal captures (determined w/ SEE)

I order them from high to low, so QxQ first, RxR second, etc.

[algerbrex]

i've been reading see.go and maybe you should check if toSq is not attacked at all and immediately return
https://github.com/lucasart/Demolito/bl ... ion.c#L578

Ah, good point, I'll try that. That alone might be a gain.

[algerbrex]

I've seen in several engines SEE being used for move ordering, and this seems like a good idea. More accuracy in good captures being searched first. Of course, SEE isn't free either, and this may be where I'm running into issues using any sort of SEE move ordering scheme.

The scheme I tried with SEE was the following:

• Hash move
• Winning captures (determined w/ SEE)

What helped me in case there are multiple moves with an equal SEE value is to try the capture with the lowest piece value first. So, if a queen and a pawn safely can capture a piece try the pawn move first.

[*] Equal captures (determined w/ SEE)

I order them from high to low, so QxQ first, RxR second, etc.

That makes sense, thanks. I'll try that too.

[Mike Sherwin]

I've seen in several engines SEE being used for move ordering, and this seems like a good idea. More accuracy in good captures being searched first. Of course, SEE isn't free either, and this may be where I'm running into issues using any sort of SEE move ordering scheme.

The scheme I tried with SEE was the following:

• Hash move
• Winning captures (determined w/ SEE)
• Equal captures (determined w/ SEE)
• Killer moves
• History heuristic
• Losing captures (determined w/ SEE)

Which made sense in my mind, but actually resulted in Blunder becoming slower while searching. As I said, I suspect the trade-off between the overhead of using SEE over MVV-LVA and the accuracy gained is a losing one. I also tried putting losing captures before the history heuristic with similar results.

In my next couple of tests, I'm going to try only using SEE in QSearch for move ordering, and visa versa. And also putting losing captures at different places.

I'm curious if anyone else has found some success using a very different scheme than the one outlined above? Right now it just seems that SEE is too slow to compensate for the accuracy gained, which may just be the case.

You could give this a try if depth > 3 (or 4).

Code: Select all

  hashMove = GetHashMove();
  
  if (hashMove) {
    score = ScoreHashMove(...);
    // process score
  }
  
  // anything else one wants to try first
  
 // shallow search to order the remaining moves 
  if (depth > 3) {
    for (mi = 0; mi < n; mi++) {
      mov = m + mi;
      MakeMove(t, mov);
      UpdateHash(t, mov);
      mov->score = -Search(t, m + n, -beta - 100, -alpha + 100, 1);
      UpdateHash(t, mov);
      TakeBack(t, mov);
    }
  }