handling draw by insufficient material

[ymatioun]

I'm thinking about the best way to add logic for draw by insufficient material to my engine, and i cannot think of a good way to do it. Here are my thoughts:

Say you have a board with KB+kp. Here white cannot win. But he should still try to take black pawn, to avoid it being promoted. So, what score should we give to current position, as well as to position after black pawn is taken? If we only modify the KB+k score, and not the KB+kp score, then taking the pawn reduces white's score and white will do nothing, leading to either draw by repetition, or by loss due to black pawn getting promoted. To avoid that behavior, we have to give negative score to KB+kp. But then white may be better off by losing the bishop, which is certainly undesired behavior.

This gets even more complicated for KBP+kp, where loss of white pawn essentially turns score negative from apparent advantage of +2.

The only way i see to make this work is to ignore draw by insufficient material completely, and let positions like KB+kp end up in unexpected draw after loss of black pawn. But this seems a suboptimal solution, and i hope there is a better way to handle situations like this.

Any ideas?

Thanks.

[bob]

I'm thinking about the best way to add logic for draw by insufficient material to my engine, and i cannot think of a good way to do it. Here are my thoughts:

Say you have a board with KB+kp. Here white cannot win. But he should still try to take black pawn, to avoid it being promoted. So, what score should we give to current position, as well as to position after black pawn is taken? If we only modify the KB+k score, and not the KB+kp score, then taking the pawn reduces white's score and white will do nothing, leading to either draw by repetition, or by loss due to black pawn getting promoted. To avoid that behavior, we have to give negative score to KB+kp. But then white may be better off by losing the bishop, which is certainly undesired behavior.

This gets even more complicated for KBP+kp, where loss of white pawn essentially turns score negative from apparent advantage of +2.

The only way i see to make this work is to ignore draw by insufficient material completely, and let positions like KB+kp end up in unexpected draw after loss of black pawn. But this seems a suboptimal solution, and i hope there is a better way to handle situations like this.

Any ideas?

Thanks.

You can divide the score by N for such drawish positions. Still leaves a vestigial score remnant to keep you playing normal chess, but if you trade into such an ending the score will drop significantly.

[hgm]

Fruit uses a system of multipliers (smaller than 1) on the 'naive' evaluation when the side that seems to be ahead by naive counting will have a hard time winning because of lack of mating potential. I generalized and simplified this system in a derivative of Fairy-Max ('Pair-o-Max') to investigate the value of mating potential on unorthodox pieces.

The system kicks in when the leading side has fewer than two Pawns, and the multiplier goes progressively closer to zero as the situation gets more hopeless. KBK and KNK are obviously completely hopeless, and the multiplier for those can be zero.

In Chess, with the classical piece values 1, 3, 3, 5, 9, you have in general no forced mate in the absence of Pawns when you are <= 3 ahead. Such positions thus get a very severe discount. Pair-o-Max divides their score by 8, but 16 would probably be better. Actually it only does that when the remaining number of pieces of the strong side is <= 2. So it does not cover cases like KBBNNKQ or KBBNNKBNN (which never occur in practice anyway). I frankly don't know if these are drawish or not; if a large number of pieces makes the situation less drawish, it would make sense to taper the multiplier towards 1 in that case, like dividing by 4 in stead of 8 when the leading side has 3 pieces, and by 2 when he has 4 pieces.

This can be refined by making use of the specifics of the pieces; in Chess there already is the exception of the 'deficient pair' of minors: two Knights have no mating potential. Also possible (but quite uncommon) is two color-bound pieces on the same color. In Pair-o-Max I also recognize the cases 'mating minor' (a piece worth <= Knight, which can force checkmate), 'color-bound major' (which obviously would never have mating potential, no matter how strong it is) and 'tough defender' (a minor that can hold out against K+Q, such as the non-royal King).

Other positions without Pawns for the leading side get their scores divided by 2, to bring their score on par with positions with Pawns that require about the same effort to win.

Then there are the cases with only a single Pawn 'in jeopardy', meaning that the defender has a piece he can spare to sacrifice for it (i.e. after sacrificing his least-valuable piece, you the leading side is left with a pawnless 'minor ahead' situation. The score of those positions is divided by 4 (because they are obviously less bad as when the last Pawn would already have been sacrificed away; there can always be hope you can shield the Pawn).

A special class is unlike Bishops with <= 2 Pawns ahead; Their scores also deserve to be divided by 2.

An efficient way to implement this is through the material table. In Spartacus I keep a material key, which uniquely represents the material on the board (counting light and dark Bishops as different). The table normally contains a value to be added to the eval score (e.g. the B-pair bonus, the Pawn-dependent B-N difference, and gradients to encourage trading material when you are ahead), but I set apart a number of codes as 'special' (201-255). When Eval() encounters such a special code it uses it as an index in a table of multipliers, or as an index in a table of functions to do special evaluations. With the latter you can make evaluations that do not only depend on material, but also on its location on the board (e.g. KBPK, to test if you have a Rook Pawn of the wrong color, a KPK table or the notoriously difficult KQKP case).

[ymatioun]

Thank you very much, this is very helpful. I'll try to implement something like this.

Thanks again!