What's Strelka's Secret Sauce?

[bob]

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.

You are wrong.

You have one knight left. With that knight, my pawn is not unstoppable. Just because capturing that knight won't bring the score back up to alpha, you omit that capture, and fail to see that taking the knight not only brings the score above alpha, but probably even above beta because you are now winning the game. The same logic applies to outside passed pawns, outside candidates, even basic passed pawns...

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

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

1)I think that today the situation is different than the past and today if you are good at beating other programs then you are also good at the same time at beating humans(I do not know about a single program at toga's level or better than it that cannot beat every human most of the time).

I practically tested movei only against other programs because I believe that it is better to test against programs in order to learn about weaknesses of the program.


2)I can add that I plan to make a rewrite of movei to bitboards so I am probably not going to test movei in the near future because before rewriting it to bitboards I plan to try to understand more of strelka.

3)I decided to share some knowledge that I found about what I consider to be a bug in strelka when I tried to understand the exact meaning of
search_parm.

I found that strelka has no condition of not having more than one null move in a row and practically can play some null moves one after the other.

I am not sure if it can practically play 4 null moves in a row and return repetition score but I found that it can practically play 3 null moves in a row.

I guess that the programmer thought that it is impossible because of the condition eval>=beta but it does not work because strelka has a bonus
of 0.03 for the side to move so it is possible that
eval=100 beta=100 when later eval=-94 beta=-99 and in both cases eval>=beta

My conclusions about search_parm so far(I hope that I have no mistakes):

1)search_parm=7 after making a null move
2)search_parm is xored by 1 after making a move
3)search_parm=3 when starting iid
4)search_parm=0 after researching(can happen after reduced move failed high or in verification of null move.
5)search_parm=search_parm&6 after making move that improve the best score but does not fail high and it is not improving alpha because there is no alpha.
6)search_parm has to be 3 or 7 in order to allow null move

Note about the code of strelka:
It seems to me more simple to have
((search_parm&3)==3) and not
(search_parm & 1) && (search_parm & 2)


Uri

[jdart]

I haven't seen this mentioned before, but Strelka has a very aggressive use of null move. It does null move pruning with R=3. Null move verification is done only if depth > 5 and then is done with a reduction factor of 4. So at depth 3 it will reduce down to the q-search and will never verify.

Code: Select all

      (pos_info_entry + 1)->mob[0] = pos_info_entry->mob[1];
      (pos_info_entry + 1)->mob[1] = pos_info_entry->mob[0];
      (pos_info_entry + 1)->value = 6 - (pos_info_entry->value);
      pos_info_entry++;
      if (depth <= 4) new_value = -qu_search(-beta, 1-beta, 0, new_pv);
                 else new_value = -full_search(1-beta, depth-4, 7, new_pv);
...
     if (depth > 5 && new_value >= beta) new_value =                     
       full_search(beta,depth-5,0,new_pv);

I have fooled around with some null move parameters lately, but mostly whatever I do comes out worse than my current implementation, which will go to only R=2 at low depths, always verifies in the late endgame, and does the same degree of reduction when verifying as the original R factor.

[Uri Blass]

I haven't seen this mentioned before, but Strelka has a very aggressive use of null move. It does null move pruning with R=3. Null move verification is done only if depth > 5 and then is done with a reduction factor of 4. So at depth 3 it will reduce down to the q-search and will never verify.

Code: Select all

      (pos_info_entry + 1)->mob[0] = pos_info_entry->mob[1];
      (pos_info_entry + 1)->mob[1] = pos_info_entry->mob[0];
      (pos_info_entry + 1)->value = 6 - (pos_info_entry->value);
      pos_info_entry++;
      if (depth <= 4) new_value = -qu_search(-beta, 1-beta, 0, new_pv);
                 else new_value = -full_search(1-beta, depth-4, 7, new_pv);
...
     if (depth > 5 && new_value >= beta) new_value =                     
       full_search(beta,depth-5,0,new_pv);

I have fooled around with some null move parameters lately, but mostly whatever I do comes out worse than my current implementation, which will go to only R=2 at low depths, always verifies in the late endgame, and does the same degree of reduction when verifying as the original R factor.

Note that I also use R=3 in movei and I do not consider R=3 to be aggresive.

I did not test R=2 at low depths but
I read that R=3 works better for people who do checks in the qsearch.

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

1)I think that today the situation is different than the past and today if you are good at beating other programs then you are also good at the same time at beating humans(I do not know about a single program at toga's level or better than it that cannot beat every human most of the time).

I practically tested movei only against other programs because I believe that it is better to test against programs in order to learn about weaknesses of the program.

If you only test like that, you will never see a Trojan Horse attack. And humans will beat you over the head with it. If you only test like that, you won't see many good kingside attacks because programs are not as good as humans at developing them correctly. In short, if you only play against programs, you are not learning much about how to handle strong humans that tend to try to block things up and then positionally squeeze you until you choke.

2)I can add that I plan to make a rewrite of movei to bitboards so I am probably not going to test movei in the near future because before rewriting it to bitboards I plan to try to understand more of strelka.

3)I decided to share some knowledge that I found about what I consider to be a bug in strelka when I tried to understand the exact meaning of
search_parm.

I found that strelka has no condition of not having more than one null move in a row and practically can play some null moves one after the other.

I am not sure if it can practically play 4 null moves in a row and return repetition score but I found that it can practically play 3 null moves in a row.

I guess that the programmer thought that it is impossible because of the condition eval>=beta but it does not work because strelka has a bonus
of 0.03 for the side to move so it is possible that
eval=100 beta=100 when later eval=-94 beta=-99 and in both cases eval>=beta

My conclusions about search_parm so far(I hope that I have no mistakes):

1)search_parm=7 after making a null move
2)search_parm is xored by 1 after making a move
3)search_parm=3 when starting iid
4)search_parm=0 after researching(can happen after reduced move failed high or in verification of null move.
5)search_parm=search_parm&6 after making move that improve the best score but does not fail high and it is not improving alpha because there is no alpha.
6)search_parm has to be 3 or 7 in order to allow null move

Note about the code of strelka:
It seems to me more simple to have
((search_parm&3)==3) and not
(search_parm & 1) && (search_parm & 2)


Uri

I have not looked at the code and won't for a while due to the current rewrite for version 22.0... the above looks like a kludge left over from changing something and then changing it again. Most programs can be "read" carefully and lots of similar things can be collapsed or cleaned up. I'm finding plenty of that in Crafty as I eliminate all the white/black special-case code that was once scattered everywhere, but which now is almost all gone.

[Gerd Isenberg]

I have not looked at the code and won't for a while due to the current rewrite for version 22.0... the above looks like a kludge left over from changing something and then changing it again. Most programs can be "read" carefully and lots of similar things can be collapsed or cleaned up. I'm finding plenty of that in Crafty as I eliminate all the white/black special-case code that was once scattered everywhere, but which now is almost all gone.

Wow! Do you flip the board vertically plus color flip during make/unmake to keep all nodes white to move - as I do? If so, how do you update the hashkey? Or do you lookup some more arrays by color or side to move?

[bob]

I have not looked at the code and won't for a while due to the current rewrite for version 22.0... the above looks like a kludge left over from changing something and then changing it again. Most programs can be "read" carefully and lots of similar things can be collapsed or cleaned up. I'm finding plenty of that in Crafty as I eliminate all the white/black special-case code that was once scattered everywhere, but which now is almost all gone.

Wow! Do you flip the board vertically plus color flip during make/unmake to keep all nodes white to move - as I do? If so, how do you update the hashkey? Or do you lookup some more arrays by color or side to move?

I have all the bitboards indexed by wtm. IE pawns[wtm] and so forth. All other masks are indexed the same way in the evaluation. Random hash values are also done the same way... Makes things far cleaner since all the white/black stuff is replaced by one general case that will work with either side. I now have things like

score += EvaluateKnights(white) - EvaluateKnights(black)

same sort of thing for move generation, you just pass it the color and it uses the same code. Only tiny exception is for pawns since negative shifts won't work on the PC and I don't want to make it too ugly (yet). I am looking at ways to generate pawn moves without the special-case white/black code as well, although 99% of the pawn generation code is now not duplicated...

Bob

[Gerd Isenberg]

I have all the bitboards indexed by wtm. IE pawns[wtm] and so forth. All other masks are indexed the same way in the evaluation. Random hash values are also done the same way... Makes things far cleaner since all the white/black stuff is replaced by one general case that will work with either side. I now have things like

score += EvaluateKnights(white) - EvaluateKnights(black)

same sort of thing for move generation, you just pass it the color and it uses the same code. Only tiny exception is for pawns since negative shifts won't work on the PC and I don't want to make it too ugly (yet). I am looking at ways to generate pawn moves without the special-case white/black code as well, although 99% of the pawn generation code is now not duplicated...

Bob

I see, the generalized shift by rotate-and can be combined with the wrap 'and' for set-wise pawn attacks. Thus the additional cost for a generalized << +-8 is one read plus 'and'.

Code: Select all

// positve left, negative right shifts
int shift[8] = {9, 1,-7,-8,-9,-1, 7, 8};
 
U64 avoidWrap[8] =
{
   0xfefefefefefefe00,
   0xfefefefefefefefe,
   0x00fefefefefefefe,
   0x00ffffffffffffff,
   0x007f7f7f7f7f7f7f,
   0x7f7f7f7f7f7f7f7f,
   0x7f7f7f7f7f7f7f00,
   0xffffffffffffff00,
};
 
U64 shiftOne (U64 b, int dir8) {
   return rotateLeft (b, shift[dir8]) & avoidWrap[dir8];
}

#if defined X86INTRINSICS
U64 rotateLeft (U64 x, int s) {return _rotl64(x, s);}
#else
// likely translated to rol by "smart" compilers
U64 rotateLeft (U64 x, int s) {return (x << s) | (x >> (64-s));}
#endif

[jdart]

Well, it also appears from another post you made in the thread that it can do multiple null moves in a row .. that certainly counts as aggressive.

[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

Uri, can we _please_ come back down to planet earth? Computer chess is all about depth. Because you don't have an infinite amount to fime. I could care less about "analysis", I am only worried about playing real games, which almost always have a time control constraint to live with. And that means that you can't just assume that if this pruning rule makes me miss the move, if I can go a couple of plies deeper I will see it. Where do you get that extra time from? The time fairy leaves it under your pillow?

The shallower you see something, the better you will play, because as you gain more depth, you are seeing more tactically, without overlooking something positional.

I feel very comfortable when Crafty can solve something in 3 plies correctly, even though it can search to depth=20 in that position. I feel much less comfortable when it takes me the full 20 plies to find the solution, knowing that I might not quite have enough time, particularly in faster games...