What's Strelka's Secret Sauce?

[jarkkop]

As you have reviewed Strelka's code is there anything that you are going to give a thought considering improvements in Crafty. There has to be something that this beast is doing better than Crafty

- Jarkko

[Uri Blass]

I have to admit I became curious and had a look at the qsearch.
From looking at it, I had the impression that Strelka uses pseudo-legal move generation Crafty-style. Correct?
I have to say, I like the readability of the code. However, some stuff is to complex for me. i.e. What does the following code from qsearch achieve? It is some kind of delta pruning, but I dont understand it.

Code: Select all

else if (pos_info_entry->value < (alpha - 250)) {
    // delta pruning: если оценка позиции хуже alpha,
    // то из взятий убираем "слабые" взятия через маски mask_w и mask_b
    best_value = pos_info_entry->value + 250;
    mask_w ^= Board->mp[WhitePawn];
    mask_b ^= Board->mp[BlackPawn];
    // В оригинальной версии Стрелки исключались только взятия пешек
    // Следующие исключения - Белка 1.8.12 (+13 пунктов !!!)
    if (pos_info_entry->value < (alpha - 450)) {
      best_value = pos_info_entry->value + 450;
      mask_w ^= Board->mp[WhiteKnight];
      mask_b ^= Board->mp[BlackKnight];
      mask_w ^= Board->mp[WhiteBishop];
      mask_b ^= Board->mp[BlackBishop];
      if (pos_info_entry->value < (alpha - 650)) {
        best_value = pos_info_entry->value + 650;
        mask_w ^= Board->mp[WhiteRook];
        mask_b ^= Board->mp[BlackRook];
        if (pos_info_entry->value < (alpha - 1050)) {
          best_value = pos_info_entry->value + 1050;
          mask_w ^= Board->mp[WhiteQueen];
          mask_b ^= Board->mp[BlackQueen];
        }
      }
    }
  }

Any suggestions?

It looks at what is the minimal materail needed to get the score above alpha. Any piece which has too little value to increase that score gets masked off the capture bitmap. Then only captures of those peices get generated. Simple and clever. And easy with a bitmap program.

Mark

That would seem to have a significant hole, in that sometimes removing a knight can raise the score beyond the value of a queen, assuming (say) that the knight being captured is the last opponent piece so that your passer is now free to run...

This is not a significant hole because the importance of knowledge of unstoppable passed pawns when the opponent has no pieces is very small
and it even does not mean throwing that knowledge but only that you may see unstoppable pawns later in the search.

Uri

Depends on your definition of "significant". I consider _anything_ that a human opponent can exploit to be significant. And this would fall into that category. A hole here and a hole there, and before long you have nothing but "hole"...

I think every weakness has to be fixed as it is exposed...

1)I see no way that an human can exploit that weakness.
It is not weakness in the evaluation but something that is only about the qsearch.

If the unstoppable passed pawns is small number of plies from the root
the relevant position is going to be in the search so this is not relevant and if it is big number of plies from the root the human will usually not be
able to calculate a trap that is so deep.

I think also that you think too much in past terms.

In the past knowledge about unstoppable pawns in the endgames was
important against humans.

Today things are different when the hardware is faster and the search is better and even without special knowledge it is harder for humans to get advantage from the fact that a program has no knowledge about unstoppable passed pawns.

reasons are:
1)It is easier for programs to win before the endgame relative to the past
2)It is easier for the search to detect problems with unstoppable passed pawns and avoid a mistake thanks to the fact that the search is deeper.

Uri

[bob]

As you have reviewed Strelka's code is there anything that you are going to give a thought considering improvements in Crafty. There has to be something that this beast is doing better than Crafty

- Jarkko

I have not looked at it any. I was responding to something about the thing posted here and discussed by others...

[bob]

I have to admit I became curious and had a look at the qsearch.
From looking at it, I had the impression that Strelka uses pseudo-legal move generation Crafty-style. Correct?
I have to say, I like the readability of the code. However, some stuff is to complex for me. i.e. What does the following code from qsearch achieve? It is some kind of delta pruning, but I dont understand it.

Code: Select all

else if (pos_info_entry->value < (alpha - 250)) {
    // delta pruning: если оценка позиции хуже alpha,
    // то из взятий убираем "слабые" взятия через маски mask_w и mask_b
    best_value = pos_info_entry->value + 250;
    mask_w ^= Board->mp[WhitePawn];
    mask_b ^= Board->mp[BlackPawn];
    // В оригинальной версии Стрелки исключались только взятия пешек
    // Следующие исключения - Белка 1.8.12 (+13 пунктов !!!)
    if (pos_info_entry->value < (alpha - 450)) {
      best_value = pos_info_entry->value + 450;
      mask_w ^= Board->mp[WhiteKnight];
      mask_b ^= Board->mp[BlackKnight];
      mask_w ^= Board->mp[WhiteBishop];
      mask_b ^= Board->mp[BlackBishop];
      if (pos_info_entry->value < (alpha - 650)) {
        best_value = pos_info_entry->value + 650;
        mask_w ^= Board->mp[WhiteRook];
        mask_b ^= Board->mp[BlackRook];
        if (pos_info_entry->value < (alpha - 1050)) {
          best_value = pos_info_entry->value + 1050;
          mask_w ^= Board->mp[WhiteQueen];
          mask_b ^= Board->mp[BlackQueen];
        }
      }
    }
  }

Any suggestions?

It looks at what is the minimal materail needed to get the score above alpha. Any piece which has too little value to increase that score gets masked off the capture bitmap. Then only captures of those peices get generated. Simple and clever. And easy with a bitmap program.

Mark

That would seem to have a significant hole, in that sometimes removing a knight can raise the score beyond the value of a queen, assuming (say) that the knight being captured is the last opponent piece so that your passer is now free to run...

This is not a significant hole because the importance of knowledge of unstoppable passed pawns when the opponent has no pieces is very small
and it even does not mean throwing that knowledge but only that you may see unstoppable pawns later in the search.

Uri

Depends on your definition of "significant". I consider _anything_ that a human opponent can exploit to be significant. And this would fall into that category. A hole here and a hole there, and before long you have nothing but "hole"...

I think every weakness has to be fixed as it is exposed...

1)I see no way that an human can exploit that weakness.
It is not weakness in the evaluation but something that is only about the qsearch.

If the unstoppable passed pawns is small number of plies from the root
the relevant position is going to be in the search so this is not relevant and if it is big number of plies from the root the human will usually not be
able to calculate a trap that is so deep.

I think also that you think too much in past terms.

In the past knowledge about unstoppable pawns in the endgames was
important against humans.

Today things are different when the hardware is faster and the search is better and even without special knowledge it is harder for humans to get advantage from the fact that a program has no knowledge about unstoppable passed pawns.

reasons are:
1)It is easier for programs to win before the endgame relative to the past
2)It is easier for the search to detect problems with unstoppable passed pawns and avoid a mistake thanks to the fact that the search is deeper.

Uri

Sorry, but remove your unstoppable passed pawn code, and outside passed pawn code, and majority code, and see how you do against strong players...

Unstoppable passed pawns are just one exception. My positional scores for distant passed pawns and such also can offset the loss of a pawn or even minor piece, making excluding such captures a potential way to miss trading into a won or lost ending...

[Edsel Apostol]

Hi Bob,

That would seem to have a significant hole, in that sometimes removing a knight can raise the score beyond the value of a queen, assuming (say) that the knight being captured is the last opponent piece so that your passer is now free to run...

I think that what you had in mind is not the case. Strelka is not removing the knight from the occupied bitboards but from the target bitboard of the captures so I think that it has no effect on the passer pawns.

Correct me if I am wrong.

[PK]

Speaking of all the pawn-related endgame terms and their influence on pruning: isn't it possible to switch off this quiescence delta pruning in the endgame, just as it is done with the null move pruning? This way you would have all the benefits of this technique at least for the first half or two-thirds of the game.

[Uri Blass]

Speaking of all the pawn-related endgame terms and their influence on pruning: isn't it possible to switch off this quiescence delta pruning in the endgame, just as it is done with the null move pruning? This way you would have all the benefits of this technique at least for the first half or two-thirds of the game.

I think that it is simply not important.
unlike null move pruning when you never can see something regardless of depth pruning in the qsearch has no effect except seeing the same thing at bigger depth.

computers already search many plies more than humans so my opinion is that it is simply unimportant even against humans when I believe that Bob is in minority of authors who care about human-computer games.

Most of the authors consider the problem uninteresting when we do not talk about games when the computer starts without a knight or at least without a pawn.

Uri

[bob]

I have to admit I became curious and had a look at the qsearch.
From looking at it, I had the impression that Strelka uses pseudo-legal move generation Crafty-style. Correct?
I have to say, I like the readability of the code. However, some stuff is to complex for me. i.e. What does the following code from qsearch achieve? It is some kind of delta pruning, but I dont understand it.

Code: Select all

else if (pos_info_entry->value < (alpha - 250)) {
    // delta pruning: если оценка позиции хуже alpha,
    // то из взятий убираем "слабые" взятия через маски mask_w и mask_b
    best_value = pos_info_entry->value + 250;
    mask_w ^= Board->mp[WhitePawn];
    mask_b ^= Board->mp[BlackPawn];
    // В оригинальной версии Стрелки исключались только взятия пешек
    // Следующие исключения - Белка 1.8.12 (+13 пунктов !!!)
    if (pos_info_entry->value < (alpha - 450)) {
      best_value = pos_info_entry->value + 450;
      mask_w ^= Board->mp[WhiteKnight];
      mask_b ^= Board->mp[BlackKnight];
      mask_w ^= Board->mp[WhiteBishop];
      mask_b ^= Board->mp[BlackBishop];
      if (pos_info_entry->value < (alpha - 650)) {
        best_value = pos_info_entry->value + 650;
        mask_w ^= Board->mp[WhiteRook];
        mask_b ^= Board->mp[BlackRook];
        if (pos_info_entry->value < (alpha - 1050)) {
          best_value = pos_info_entry->value + 1050;
          mask_w ^= Board->mp[WhiteQueen];
          mask_b ^= Board->mp[BlackQueen];
        }
      }
    }
  }

Any suggestions?

It looks at what is the minimal materail needed to get the score above alpha. Any piece which has too little value to increase that score gets masked off the capture bitmap. Then only captures of those peices get generated. Simple and clever. And easy with a bitmap program.

Mark

That would seem to have a significant hole, in that sometimes removing a knight can raise the score beyond the value of a queen, assuming (say) that the knight being captured is the last opponent piece so that your passer is now free to run...

This is not a significant hole because the importance of knowledge of unstoppable passed pawns when the opponent has no pieces is very small
and it even does not mean throwing that knowledge but only that you may see unstoppable pawns later in the search.

Uri

Depends on your definition of "significant". I consider _anything_ that a human opponent can exploit to be significant. And this would fall into that category. A hole here and a hole there, and before long you have nothing but "hole"...

I think every weakness has to be fixed as it is exposed...

1)I see no way that an human can exploit that weakness.
It is not weakness in the evaluation but something that is only about the qsearch.

If the unstoppable passed pawns is small number of plies from the root
the relevant position is going to be in the search so this is not relevant and if it is big number of plies from the root the human will usually not be
able to calculate a trap that is so deep.

Just because _you_ don't see how to exploit it does not mean others can not. I did not say it was a flaw in the evaluation, so I have no idea where that comment comes from. But certainly not from what I wrote. I _clearly_ said it was a hole in the q-search, where you omit making a crucial capture that will suddenly illuminate a large evaluation term, but you failed to do so because you assume that just winning a knight will not get you back above alpha. Where knight + positional score will easily do so.

I think also that you think too much in past terms.

I think you think too much without actually _thinking_.

In the past knowledge about unstoppable pawns in the endgames was
important against humans.

Today things are different when the hardware is faster and the search is better and even without special knowledge it is harder for humans to get advantage from the fact that a program has no knowledge about unstoppable passed pawns.

Just remove the terms and see how you do against strong players. These terms would include unstoppable passed pawns, outside/distant passed pawns, outside/distant candidate passed pawns, some king safety terms that are heavily material dependent, and several others that scale up/down as material is removed.

reasons are:
1)It is easier for programs to win before the endgame relative to the past
2)It is easier for the search to detect problems with unstoppable passed pawns and avoid a mistake thanks to the fact that the search is deeper.

Uri

I probably play as many games against IM/GM players as anyone on the planet, if not more. _many_ GM games reach the endgame. In fact, _most_ reach the endgame. Not always king and pawns only, but close enough that endgame threats influence the outcome. I have no idea how many GM games you have actually seen with your program, but I know what I had to fix with mine to give it reasonable chances in endgames where GMs are _very_ difficult to deal with.

You have once again zeroed in on a minute detail. I gave unstoppable passed pawns as an _example_, and not the _only case_ where this is an issue. In crafty, outside passed pawns greatly increase in value when material comes off, particularly the last piece. Ditto for king safety which goes completely away when the last piece comes off. There are others including normal passed pawn scoring, majority scoring, etc. Try to think in general terms, rather than looking at one example phrase and saying "that by itself is not a big deal" when I never said it was the _only deal_...

[bob]

Speaking of all the pawn-related endgame terms and their influence on pruning: isn't it possible to switch off this quiescence delta pruning in the endgame, just as it is done with the null move pruning? This way you would have all the benefits of this technique at least for the first half or two-thirds of the game.

Depends. My scores can be quite big for some features of the game. Some scale up/down slowly as material comes off. Some scale up/down rapidly near some sort of edge/boundary condition. If you just turn something on or off at a fixed point, you introduce a discontinuity in the evaluation that itself becomes a weakness...

[bob]

Speaking of all the pawn-related endgame terms and their influence on pruning: isn't it possible to switch off this quiescence delta pruning in the endgame, just as it is done with the null move pruning? This way you would have all the benefits of this technique at least for the first half or two-thirds of the game.

I think that it is simply not important.
unlike null move pruning when you never can see something regardless of depth pruning in the qsearch has no effect except seeing the same thing at bigger depth.

computers already search many plies more than humans so my opinion is that it is simply unimportant even against humans when I believe that Bob is in minority of authors who care about human-computer games.

Most of the authors consider the problem uninteresting when we do not talk about games when the computer starts without a knight or at least without a pawn.

Uri

Please think logically here. The evaluation is given positions that occur deep in the tree. If I have to make a move _now_ I have to rely on what my evaluation is seeing or not seeing _now_. I don't care what I will see in another ply or two, because by then I have already committed to the path of play the search is based on. So your "you can always go deeper" is meaningless in this context, when we have to move after a fixed search time limit, regardless of how much another ply or two will help us... Depth is not always the answer, because we do have real time constraints to play within.