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.

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);
    }
  }

That's an interesting approach, Michael, thanks. I'm really curious to try this out as well. Have you done any testing how much this helps you out?

[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);
    }
  }

That's an interesting approach, Michael, thanks. I'm really curious to try this out as well. Have you done any testing how much this helps you out?

It has been in RomiChess since 2005. It gains ~2 ply search depth. I tried it in TSCP with ~1.5 ply gain. I hope it will work for you!

[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.

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);
    }
  }

That's an interesting approach, Michael, thanks. I'm really curious to try this out as well. Have you done any testing how much this helps you out?

It has been in RomiChess since 2005. It gains ~2 ply search depth. I tried it in TSCP with ~1.5 ply gain. I hope it will work for you!

Thanks, sounds promising! I'll be trying it next since another test just wrapped up. I'll experiment to see the best way to combine this with what I have.

[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);
    }
  }

That's an interesting approach, Michael, thanks. I'm really curious to try this out as well. Have you done any testing how much this helps you out?

It has been in RomiChess since 2005. It gains ~2 ply search depth. I tried it in TSCP with ~1.5 ply gain. I hope it will work for you!

Thanks, sounds promising! I'll be trying it next since another test just wrapped up. I'll experiment to see the best way to combine this with what I have.

Also beta-cuts can be counted and the position hard pruned based on remaining depth and number of beta-cuts. So let's say at depth n 4 beta-cut moves are needed and the number of beta-cuts is 5. Then do a deeper search just on those 5 moves and if at least 4 of those moves remain >= beta then return beta.

[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.

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);
    }
  }

That's an interesting approach, Michael, thanks. I'm really curious to try this out as well. Have you done any testing how much this helps you out?

It has been in RomiChess since 2005. It gains ~2 ply search depth. I tried it in TSCP with ~1.5 ply gain. I hope it will work for you!

Thanks, sounds promising! I'll be trying it next since another test just wrapped up. I'll experiment to see the best way to combine this with what I have.

Also beta-cuts can be counted and the position hard pruned based on remaining depth and number of beta-cuts. So let's say at depth n 4 beta-cut moves are needed and the number of beta-cuts is 5. Then do a deeper search just on those 5 moves and if at least 4 of those moves remain >= beta then return beta.

Thanks for the idea. That sounds vert similar to multi-cut, of which I've wanted to try again recently too.

[gaard]

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.

My experience has been similar to yours. Using SEE in move ordering has always been a loss for me due to the slow down. I assumed it was because of my mailbox approach and that the slow down might be negligible if I was using bitboards. Maybe not. I see a couple of ideas in this thread that I will probably experiment with.

[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.

My experience has been similar to yours. Using SEE in move ordering has always been a loss for me due to the slow down. I assumed it was because of my mailbox approach and that the slow down might be negligible if I was using bitboards. Maybe not. I see a couple of ideas in this thread that I will probably experiment with.

Yeah, slow down has always been my reasoning for why SEE wouldn't work for me, since the theory seems pretty solid. Glad you got some ideas to try though. I'm going to be going through here over the next couple of days and test most of the ideas myself to what helps and what doesn't, and I can report back.

[hgm]

Note that standard ordering for good and equal captures is MVV/LVA, and SEE should only be used to determine that they are not bad. Sorting by SEE gives you poor move ordering. Putting equal captures after good ones is thus also bad; Q x protected Q should be searched before PxN.