Search bug? (Stockfish)

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

Rein Halbersma
Posts: 741
Joined: Tue May 22, 2007 11:13 am

Re: Search bug? (Stockfish)

Post by Rein Halbersma »

Eelco de Groot wrote:Probably I'm not being very efficient in coding it but all that new stuff with templates is just too complicated for a C amateur. If Marco types something like

Code: Select all

/// Endgames class stores in two std::map the pointers to endgame evaluation
/// and scaling base objects. Then we use polymorphism to invoke the actual
/// endgame function calling its apply() method that is virtual.
I'm completely lost there :shock: It must be C+++ or something?
The Endgames class in Stockfish is an example of an object factory. It stores pointers to a whole range of specific instances of a template class Endgame. Each of these templates inherits a common interface EndgameBase. During startup, you register all implemented endgames to the factory by storing a pointer and an identifier string. During evaluation, you determine the specific endgame class of the current position, then lookup the corresponding identifier string and the pointer that sits in that entry of the map. De-referencing the pointer will call the apply() function of the specific endgame, and the proper code will be executed.

There is also another layer of abstraction because of the template in front of it: for C programmers that is effectively the same as adding e.g. a suffix _KRK to a function (the C++ compiler does this effectively; it's called name-mangling). But you can save a lot of typing of common code with templates if things get more complicated. Also, instead of an apply() function, some C++ programmers use an application operator()() for that (structs with such operators are called function objects), which can also be a little confusing the first time you read this as a C programmer.

As Marco indicated, the advantage is that the factory registry is open to extension for new endgames (i.e. meaning that you only have to add new code, but don't have to edit any existing code).

You can read more about this design pattern at e.g. this site: http://sourcemaking.com/design_patterns/factory_method
mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 9:17 pm

Re: Search bug? (Stockfish)

Post by mcostalba »

Rein Halbersma wrote: Also, instead of an apply() function, some C++ programmers use an application operator()() for that (structs with such operators are called function objects), which can also be a little confusing the first time you read this as a C programmer.
Thanks for the hint, I like the idea but unfortunately the actual calling of the function is not so elegant because we are talking of pointers:

Code: Select all

-  ScaleFactor sf = scalingFunction[c]->apply(pos);
+  ScaleFactor sf = (*scalingFunction[c])(pos);
   return sf == SCALE_FACTOR_NONE ? ScaleFactor(factor[c]) : sf;
 }
 
 inline Value MaterialInfo::evaluate(const Position& pos) const {
-  return evaluationFunction->apply(pos);
+  return (*evaluationFunction)(pos);
 }
Rein Halbersma
Posts: 741
Joined: Tue May 22, 2007 11:13 am

Re: Search bug? (Stockfish)

Post by Rein Halbersma »

mcostalba wrote:
Rein Halbersma wrote: Also, instead of an apply() function, some C++ programmers use an application operator()() for that (structs with such operators are called function objects), which can also be a little confusing the first time you read this as a C programmer.
Thanks for the hint, I like the idea but unfortunately the actual calling of the function is not so elegant because we are talking of pointers:

Code: Select all

-  ScaleFactor sf = scalingFunction[c]->apply(pos);
+  ScaleFactor sf = (*scalingFunction[c])(pos);
   return sf == SCALE_FACTOR_NONE ? ScaleFactor(factor[c]) : sf;
 }
 
 inline Value MaterialInfo::evaluate(const Position& pos) const {
-  return evaluationFunction->apply(pos);
+  return (*evaluationFunction)(pos);
 }
On closer examination, your factory is not used for object creation, but more for context-dependent behavior, such as in the Strategy or State design patterns. Because of that, the return type is not a pointer to a base class, but a type with value semantics.

In the object creation factory, one normally stores pointers to creation functions (which call private constructors behind the scenes). In this case, I still like the operator()() syntax because it lets you hide arbitrary names such as apply().

If you want nicer syntax, you could store pointers to a member function apply(), and a member function scale(), and then simply de-reference these.
User avatar
Eelco de Groot
Posts: 4568
Joined: Sun Mar 12, 2006 2:40 am
Full name:   

Re: Search bug? (Stockfish)

Post by Eelco de Groot »

Thanks for the explanations, Rein, Marco! I promise to study this some more when I want to do something with the endgame code again. I agree that for the coding of endgames, classes and Object Orient Programming seem the appropriate tool and it becomes clearer when to use the different methods by studying how this is done in Stockfish. But when they implemented all that in Pascal(or Delphi) it all quickly became very complicated and very abstract. No fun at all to read about and for things like numerical mathematics there did not seem much point in learning any of that, but this seems more suited and a good way to get better acquainted with OOP.

I can maybe add the way I implemented the same bishop code without using Marco's recommended way of fabricating a new function KBBPsK, but changing the KXK code so that this does not give VALUE_KNOWN_WIN anymore in the case of same colored bishops (and edge pawn(s) of the wrong color):

Code: Select all

/// Mate with KX vs K. This function is used to evaluate positions with
/// King and plenty of material vs a lone king. It simply gives the
/// attacking side a bonus for driving the defending king towards the edge
/// of the board, and for keeping the distance between the two kings small.
template<>
Value Endgame<KXK>&#58;&#58;apply&#40;const Position& pos&#41; const &#123;

  assert&#40;pos.non_pawn_material&#40;weakerSide&#41; == VALUE_ZERO&#41;;
  assert&#40;pos.piece_count&#40;weakerSide, PAWN&#41; == VALUE_ZERO&#41;;

  Square winnerKSq = pos.king_square&#40;strongerSide&#41;;
  Square loserKSq = pos.king_square&#40;weakerSide&#41;;

  Value result =   pos.non_pawn_material&#40;strongerSide&#41;
                 + pos.piece_count&#40;strongerSide, PAWN&#41; * PawnValueEndgame
                 + MateTable&#91;loserKSq&#93;
                 + DistanceBonus&#91;square_distance&#40;winnerKSq, loserKSq&#41;&#93;;

  if (   pos.piece_count&#40;strongerSide, QUEEN&#41;
      || pos.piece_count&#40;strongerSide, ROOK&#41;
      || &#40;pos.piece_count&#40;strongerSide, BISHOP&#41; == 2
	  && opposite_colors&#40;pos.piece_list&#40;strongerSide, BISHOP&#41;&#91;0&#93;, pos.piece_list&#40;strongerSide, BISHOP&#41;&#91;1&#93;)))
      // TODO&#58; check for more than two equal-colored bishops!
      result += VALUE_KNOWN_WIN;
  else if &#40;pos.piece_count&#40;strongerSide, BISHOP&#41; == 2
	  && !opposite_colors&#40;pos.piece_list&#40;strongerSide, BISHOP&#41;&#91;0&#93;, pos.piece_list&#40;strongerSide, BISHOP&#41;&#91;1&#93;)
	  && pos.non_pawn_material&#40;strongerSide&#41; == 2*BishopValueMidgame&#41;
  &#123;
	  result = VALUE_DRAW;
	  if &#40;pos.piece_count&#40;strongerSide, PAWN&#41;)
	  &#123;
		  result = pos.non_pawn_material&#40;strongerSide&#41; + pos.piece_count&#40;strongerSide, PAWN&#41; * PawnValueEndgame;
		  Bitboard pawns = pos.pieces&#40;PAWN, strongerSide&#41;;
		  File pawnFile = file_of&#40;pos.piece_list&#40;strongerSide, PAWN&#41;&#91;0&#93;);
		  
		  // All pawns are on a single rook file ?
		  if (   &#40;pawnFile == FILE_A || pawnFile == FILE_H&#41;
			  && &#40;pawns & ~file_bb&#40;pawnFile&#41;) == EmptyBoardBB&#41;
		  &#123;
			  Square bishopSq = pos.piece_list&#40;strongerSide, BISHOP&#41;&#91;0&#93;;
			  Square queeningSq = relative_square&#40;strongerSide, make_square&#40;pawnFile, RANK_8&#41;);
			  Square kingSq = pos.king_square&#40;weakerSide&#41;;
			  
			  if (   opposite_colors&#40;queeningSq, bishopSq&#41;
				  && abs&#40;file_of&#40;kingSq&#41; - pawnFile&#41; <= 1&#41;
			  &#123;
				  // The bishop has the wrong color, and the defending king is on the
				  // file of the pawn&#40;s&#41; or the neighboring file. Find the rank of the
				  // frontmost pawn.
				  Rank rank;
				  if &#40;strongerSide == WHITE&#41;
				  &#123;
					  for &#40;rank = RANK_7; &#40;rank_bb&#40;rank&#41; & pawns&#41; == EmptyBoardBB; rank--) &#123;&#125;
					  assert&#40;rank >= RANK_2 && rank <= RANK_7&#41;;
				  &#125;
				  else
				  &#123;
					  for &#40;rank = RANK_2; &#40;rank_bb&#40;rank&#41; & pawns&#41; == EmptyBoardBB; rank++) &#123;&#125;
					  rank = Rank&#40;rank ^ 7&#41;;  // HACK to get the relative rank
					  assert&#40;rank >= RANK_2 && rank <= RANK_7&#41;;
				  &#125;
				  // If the defending king has distance 1 to the promotion square or
				  // is placed somewhere in front of the pawn, it's a draw.
				  if (   square_distance&#40;kingSq, queeningSq&#41; <= 1
					  || relative_rank&#40;strongerSide, kingSq&#41; >= rank&#41;
					  result = VALUE_DRAW + pos.piece_count&#40;strongerSide, PAWN&#41; * rank;
			  &#125;
		  &#125;		  
	  &#125;
  &#125;
  return strongerSide == pos.side_to_move&#40;) ? result &#58; -result;
&#125;
Maybe it can be done simpler but it seemed to me little enough code for a patch. Almost all of this code already existed for the KBPsK class. I think it will work in the Stockfish master branch without any changes. Note that there is a little change from the result as I had given in the post above where Rainbow Serpent just gave away the pawns; even if the theoretical result is a draw Stockfish will still try to improve the rank of the edge pawn(s) now, and give a smal plus for the stronger side, if he still has pawns. The same colored bishops are not counted though :) If Stockfish has eight of them or two or just one makes no difference for the evaluation, only the rank of the pawn or pawns on the edge.


Thanks again, will go study classes a bit later!
Eelco

Small typo further in endgame.cpp:

Code: Select all

/// KBPsKScalingFunction scales endgames where the stronger side has king,
Added a s behind the P here as that seemed to be missing. (No functional change it was just a comment :lol: )
Debugging is twice as hard as writing the code in the first
place. Therefore, if you write the code as cleverly as possible, you
are, by definition, not smart enough to debug it.
-- Brian W. Kernighan
User avatar
Eelco de Groot
Posts: 4568
Joined: Sun Mar 12, 2006 2:40 am
Full name:   

Re: Search bug? (Stockfish)

Post by Eelco de Groot »

What seems to be missing still is if the heoretical result is not a draw, one or more bishops of the same color and pawns, you would like to evaluate all the pawns at least basically as the passed pawns that they are, and if they are of the right color queening square they should get a bonus. At the moment I don't think Stockfish or for that matter Rainbow Serpent is giving any bonus in that case! Maybe I'm missing something but to me that seems a little buggy...

Regards, Eelco

If there is more than one pawn and these pawns are not on the same edge you might still get a good enough evaluation by just giving a bonus for the rank of the foremost pawn, not regarding the color of the promotion square. In that case maybe this small change is enough but I still would like to have a bonus for the right color promotion square especially if there is just one bishop (in the KBPsK code). Can KBPsK really rely on just seeing a promotion in time by brute force?

Code: Select all

/// Mate with KX vs K. This function is used to evaluate positions with
/// King and plenty of material vs a lone king. It simply gives the
/// attacking side a bonus for driving the defending king towards the edge
/// of the board, and for keeping the distance between the two kings small.
template<>
Value Endgame<KXK>&#58;&#58;apply&#40;const Position& pos&#41; const &#123;

  assert&#40;pos.non_pawn_material&#40;weakerSide&#41; == VALUE_ZERO&#41;;
  assert&#40;pos.piece_count&#40;weakerSide, PAWN&#41; == VALUE_ZERO&#41;;

  Square winnerKSq = pos.king_square&#40;strongerSide&#41;;
  Square loserKSq = pos.king_square&#40;weakerSide&#41;;

  Value result =   pos.non_pawn_material&#40;strongerSide&#41;
                 + pos.piece_count&#40;strongerSide, PAWN&#41; * PawnValueEndgame
                 + MateTable&#91;loserKSq&#93;
                 + DistanceBonus&#91;square_distance&#40;winnerKSq, loserKSq&#41;&#93;;

  if (   pos.piece_count&#40;strongerSide, QUEEN&#41;
      || pos.piece_count&#40;strongerSide, ROOK&#41;
      || &#40;pos.piece_count&#40;strongerSide, BISHOP&#41; == 2
	  && opposite_colors&#40;pos.piece_list&#40;strongerSide, BISHOP&#41;&#91;0&#93;, pos.piece_list&#40;strongerSide, BISHOP&#41;&#91;1&#93;)))
      // TODO&#58; check for more than two equal-colored bishops!
      result += VALUE_KNOWN_WIN;
  else if &#40;pos.piece_count&#40;strongerSide, BISHOP&#41; == 2
	  && !opposite_colors&#40;pos.piece_list&#40;strongerSide, BISHOP&#41;&#91;0&#93;, pos.piece_list&#40;strongerSide, BISHOP&#41;&#91;1&#93;)
	  && pos.non_pawn_material&#40;strongerSide&#41; == 2*BishopValueMidgame&#41;
  &#123;
	  result = VALUE_DRAW;
	  if &#40;pos.piece_count&#40;strongerSide, PAWN&#41;)
	  &#123;		  
		  Bitboard pawns = pos.pieces&#40;PAWN, strongerSide&#41;;
		  File pawnFile = file_of&#40;pos.piece_list&#40;strongerSide, PAWN&#41;&#91;0&#93;);
		  
		  // Find the rank of the frontmost pawn.
		  Rank rank;
		  if &#40;strongerSide == WHITE&#41;
		  &#123;
			  for &#40;rank = RANK_7; &#40;rank_bb&#40;rank&#41; & pawns&#41; == EmptyBoardBB; rank--) &#123;&#125;
			  assert&#40;rank >= RANK_2 && rank <= RANK_7&#41;;
		  &#125;
		  else
		  &#123;
			  for &#40;rank = RANK_2; &#40;rank_bb&#40;rank&#41; & pawns&#41; == EmptyBoardBB; rank++) &#123;&#125;
			  rank = Rank&#40;rank ^ 7&#41;;  // HACK to get the relative rank
			  assert&#40;rank >= RANK_2 && rank <= RANK_7&#41;;
		  &#125;
		  result = pos.non_pawn_material&#40;strongerSide&#41;
			     + pos.piece_count&#40;strongerSide, PAWN&#41; * &#40;rank + PawnValueEndgame&#41;;
		  
		  // All pawns are on a single rook file ?
		  if (   &#40;pawnFile == FILE_A || pawnFile == FILE_H&#41;
			  && &#40;pawns & ~file_bb&#40;pawnFile&#41;) == EmptyBoardBB&#41;
		  &#123;
			  Square bishopSq = pos.piece_list&#40;strongerSide, BISHOP&#41;&#91;0&#93;;
			  Square queeningSq = relative_square&#40;strongerSide, make_square&#40;pawnFile, RANK_8&#41;);
			  Square kingSq = pos.king_square&#40;weakerSide&#41;;
			  
			  if (   opposite_colors&#40;queeningSq, bishopSq&#41;
				  && abs&#40;file_of&#40;kingSq&#41; - pawnFile&#41; <= 1&#41;
			  &#123;
				  // The bishop has the wrong color, and the defending king is on the
				  // file of the pawn&#40;s&#41; or the neighboring file. 
				  // If the defending king has distance 1 to the promotion square or
				  // is placed somewhere in front of the pawn, it's a draw.
				  if (   square_distance&#40;kingSq, queeningSq&#41; <= 1
					  || relative_rank&#40;strongerSide, kingSq&#41; >= rank&#41;
					  result = VALUE_DRAW + pos.piece_count&#40;strongerSide, PAWN&#41; * rank;
			  &#125;
		  &#125;		  
	  &#125;
  &#125;
  return strongerSide == pos.side_to_move&#40;) ? result &#58; -result;
&#125;
Debugging is twice as hard as writing the code in the first
place. Therefore, if you write the code as cleverly as possible, you
are, by definition, not smart enough to debug it.
-- Brian W. Kernighan
Uri Blass
Posts: 10322
Joined: Thu Mar 09, 2006 12:37 am
Location: Tel-Aviv Israel

Re: Search bug? (Stockfish)

Post by Uri Blass »

zamar wrote:
UncombedCoconut wrote: Any other explanation?
Late move pruning. It might be that for example black's moves Kf6, Kf7, Kf8 have a high history score (Because we have a position where almost any move draws such oddities may happen). Now if black's king is on g7, it may happen that the search will only consider moves Kf6, Kf7, Kf8 and prunes the rest. And because history scores are global this may occur in practically every branch of the tree. [In reality I assume it is more complicated than this, fx. razoring might give a big boost to this behaviour, but you get the idea]

P.S. Again this is only a guess
If this is the case then there may be a solution to the problem
I guess that Kf6 Kf7 Kf8 reduce the evaluation function by a big margin so you can have a rule to allow pruning only after you found a move that does not reduce the evaluation function so you do not allow pruning after Kf6 Kf7 Kf8.