Endgame woes

[silentshark]

So.. how do other engine authors stop their programs slipping into obviously drawn endgames?

An example for my engine is KRB vs KR. This is often drawn (I think - anyhow my engine can't win it). The problem I have is that this endgame might be drawn or might be a win (e.g. if the opponent's rook is en prise).

I think my engine is missing some ELO by slipping into drawn endgames when it may had a win. Other engines seem to have this nailed. From their evals, for example, sometimes I will see my engine at +5 and the opponent somewhere around +0 in endgames like the above.

Mine's a 'mailbox' engine (I think that's what it's called these days, i.e. not bitboard), so I'm after hints to help sort this

Thanks all,

Cheers,
Tom

[xr_a_y]

I use some endgame knowledge hard coded as WIN/LOST FIDE_DRAW HARD_TO_WIN ALMOST_DRAW

and divide (or multiply) the score by some factor when this happens also taking into account 50-moves rule.

Code: Select all

          if      ( MEntry.t == MaterialHash::Ter_WhiteWinWithHelper || MEntry.t == MaterialHash::Ter_BlackWinWithHelper ) return (white2Play?+1:-1)*(MaterialHash::helperTable[matHash](p,winningSideEG,score[sc_Mat][EG]));
          else if ( MEntry.t == MaterialHash::Ter_Draw)         { if (!isAttacked(p, kingSquare(p))) return context.drawScore(); }
          else if ( MEntry.t == MaterialHash::Ter_MaterialDraw) { if (!isAttacked(p, kingSquare(p))) return context.drawScore(); }
          else if ( MEntry.t == MaterialHash::Ter_WhiteWin || MEntry.t == MaterialHash::Ter_BlackWin) score.scalingFactor = 5 - 5*p.fifty/100.f;
          else if ( MEntry.t == MaterialHash::Ter_HardToWin)  score.scalingFactor = 0.5f - 0.5f*(p.fifty/100.f);
          else if ( MEntry.t == MaterialHash::Ter_LikelyDraw) score.scalingFactor = 0.3f - 0.3f*(p.fifty/100.f);

[JohnWoe]

I scale down the closer to 50 move rule it gets.

And I scale down also when material is close and looks drawish.
https://github.com/SamuraiDangyo/Sapeli ... li.c#L2302

Code: Select all

static void Eval_drawish()
{
  if ( ! (BRD->white[0] | BRD->black[0])) // No pawns
    EVAL_DRAWISH_FACTOR = 2;
  else if (POPCOUNT(BRD->white[1] | BRD->white[2] | BRD->white[3] | BRD->white[4]) == 1 // Both have only 1 minor/major left
       &&  POPCOUNT(BRD->black[1] | BRD->black[2] | BRD->black[3] | BRD->black[4]) == 1)
    EVAL_DRAWISH_FACTOR = 3;
}

[Ferdy]

So.. how do other engine authors stop their programs slipping into obviously drawn endgames?

An example for my engine is KRB vs KR. This is often drawn (I think - anyhow my engine can't win it). The problem I have is that this endgame might be drawn or might be a win (e.g. if the opponent's rook is en prise).

krbkr is indeed very difficult to win. Here are the conditions to win.
1. The IK (inferior king - materially inferior side) must be driven to the edge of the board.
2. The SK (superior king) must be very close to the IK.
3. The SR (superior rook) must guard the rank so that the IK cannot escape from the edge of the board, and drive out the IR.

If those conditions are present, give some bonus otherwise scale down the score by a factor of 8 or so.

Sample position that was already known in the 18th century, analyzed by Philidor.

[d]3k4/4r3/3K4/3B4/8/8/8/5R2 w - - c0 "KRBvKR, Philidor position, white wins";


Even when IK is already at the edge of the board, it is not enough to win if SK is far from IK and IR is actively preventing SK to get closer to IK.

[d]4k3/6R1/8/4K3/4B3/8/4r3/8 w - - c0 "KRBvKR, Cochrane defence position, black can draw";


Ref: 100 Endgames You Must Know, by Jesus de la Villa
I have the 3rd Edition. Good book for players and programmers who likes to implement endings on their engine.

[hgm]

I always use a method I learned from Fruit: multiply the naive eval by a factor < 1 when the material combination is recognized as drawis. There are several classes of drawishness: without Pawns and not more than a minor ahead is divided by 8, and end-games that can convert to it by sacrificing away the last Pawn (so with 1 Pawn for the leading side and an extra minor for the lagging side) get a factor 0.5. When after the sacrifice a dead draw (like KNK) would result, it gets a factor 0.25. Dead draws get a factor 0, and also cut off the search. Other end-games where the leading side has no Pawns get a factor 0.5, as do unlike-Bishop end-games with not more than 2 Pawns difference. I usually make an exception for known wins against a bare King; KQK, KRK, KBBK and KBNK are not drawish.

Except for the draws the search is not affected, so if the position is not quiet and quickly converts to a more favorable one, the search will discover it.

[silentshark]

This is cool feedback, thanks guys.

One challenge I have is that it's not cheap to calculate the material position (i.e. how many pieces each side has). Maybe I should look at material tables etc.

[Henk]

Piece square table is all you need to create a bad engine. I added material points to values of piece square table as well

[jdart]

I always use a method I learned from Fruit: multiply the naive eval by a factor < 1 when the material combination is recognized as drawis

I do something like that. See adjustMaterialScore and adjustMaterialScoreNoPawns in https://github.com/jdart1/arasan-chess/ ... coring.cpp. I also support tablebases, though, which of course are more accurate for configurations that result in a hit.

--Jon

[xr_a_y]

This is cool feedback, thanks guys.

One challenge I have is that it's not cheap to calculate the material position (i.e. how many pieces each side has). Maybe I should look at material tables etc.

Gull material table is the way to go I think, with incremental material update.

[silentshark]

I always use a method I learned from Fruit: multiply the naive eval by a factor < 1 when the material combination is recognized as drawis

I do something like that. See adjustMaterialScore and adjustMaterialScoreNoPawns in https://github.com/jdart1/arasan-chess/ ... coring.cpp. I also support tablebases, though, which of course are more accurate for configurations that result in a hit.

--Jon

I will take a look, thanks. @hgm, when you write 'naive eval' I assume you mean the material + positional eval, and that's what gets adjusted?