End Game Heuristics

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
lauriet
Posts: 198
Joined: Sun Nov 03, 2013 8:32 am
Contact:

End Game Heuristics

Post by lauriet » Thu Mar 20, 2014 3:58 am

Hey Guys,

My program is now playing pretty good (certainly not top class). But it is showing typical endgame problems. It was two pieces up against my Fedility excellence, but didn't know what to do after that.
I don't want to put in endgame tables (that seems like cheating) I want it to calculate. So can anyone suggest some heuristics to help 'teach' my program so endgame principles :?:

Thanks
Laurie

Isaac
Posts: 265
Joined: Sat Feb 22, 2014 7:37 pm

Re: End Game Heuristics

Post by Isaac » Thu Mar 20, 2014 4:47 am

I would take a look at other programs' code. For example Stockfish's code: https://github.com/mcostalba/Stockfish/ ... ndgame.cpp .
There you can find some heuristics for some finals (like KBNK, KRKN, KRKB, etc.)

User avatar
hgm
Posts: 25076
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: End Game Heuristics

Post by hgm » Thu Mar 20, 2014 7:42 am

If there are still Pawns: give higher bonus for advancing pawns, and in particular passers.

In a Pawnless ending: make sure trading equal material increases the evaluation when you are ahead.

Against bare King: make sure the distance of the bare King to the corner becomes the dominant evaluation term (e.g. by multiplying the normal end-game Piece-Square Table for it by 5 or 10.

tpetzke
Posts: 686
Joined: Thu Mar 03, 2011 3:57 pm
Location: Germany
Contact:

Re: End Game Heuristics

Post by tpetzke » Thu Mar 20, 2014 8:12 am

Hi,
I don't want to put in endgame tables
For KPK a endgame table is useful, you don't have to put it in. You can calculate it when the engine starts. There was a recent thread here about it. My implementation takes less than 100 ms for all 3men tables in total and this is a rather slow implementation. Rupert's and HGM's are much faster.

Thomas...
Thomas...

=======
http://macechess.blogspot.com - iCE Chess Engine

AlvaroBegue
Posts: 925
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: End Game Heuristics

Post by AlvaroBegue » Thu Mar 20, 2014 1:34 pm

Your program needs to know what is insufficient material, so it doesn't think it will win KNK or KNNK (or KNKP with a knight, etc.).

For situations where a win is possible but tricky, it is important to write specific evaluation functions for specific endgames. The two most important ones are probably KPK (because it happens often and it's either easily won or a draw, with little in between) and KBPK (because the computer looks really stupid when it thinks it will win with a rook-column pawn and a bishop of the wrong color against a king waiting near the promotion square). After that, you should probably write KNBK (push the enemy king towards a corner where the bishop can attack it) and KBBK (push the enemy king towards any corner).

One more very important heuristic for endgames is that positions with only pawns plus different-color bishops are very drawish. I divide the score by 3 in those situations, which seems to help a lot, although I haven't tuned this.

And another one: If you are ahead but you don't have any pawns, you should reduce your score (not sure by how much), because it's much harder to win without a pawn to promote.

User avatar
hgm
Posts: 25076
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: End Game Heuristics

Post by hgm » Thu Mar 20, 2014 3:46 pm

A factor 2 would be about right. With Pawns +2 is usually an easy win, without them +3 is a dead draw, and +4 (Q vs R) just makes it.

But I think all these things are way too subtle for the problem of the OP: he says the program does not know how to win when two pieces up. OK, for KBNK that might be excusable, but normally it should quickly mate with such an advantage, even without Pawns. I assume the complaint was not that it could not win KNNK.

AlvaroBegue
Posts: 925
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: End Game Heuristics

Post by AlvaroBegue » Thu Mar 20, 2014 3:50 pm

hgm wrote:A factor 2 would be about right. With Pawns +2 is usually an easy win, without them +3 is a dead draw, and +4 (Q vs R) just makes it.
I'll try with a factor of 2. Thanks!

But I think all these things are way too subtle for the problem of the OP: he says the program does not know how to win when two pieces up. OK, for KBNK that might be excusable, but normally it should quickly mate with such an advantage, even without Pawns. I assume the complaint was not that it could not win KNNK.
Yes, he didn't explain what two pieces he was talking about. I did address KBNK and KBBK in my earlier post. If there is a rook or a queen involved, you shouldn't have to do anything, but pushing the lonely king to the edges of the board will help programs with shallow searches.

Henk
Posts: 6560
Joined: Mon May 27, 2013 8:31 am

Re: End Game Heuristics

Post by Henk » Thu Mar 20, 2014 4:26 pm

Do you think there is something wrong with the end game playing of Skipper. 59. Ke3 ?? I think I better call my program Crappy Duck.

[Edit] 59 Kd2 would loose also I guess.

[pgn]
[Site "http://lichess.org/CfykIzpW"]
[Date "2014.03.20"]
[White "Anonymous"]
[Black "AI-level-7"]
[Result "0-1"]
[WhiteElo "?"]
[BlackElo "?"]
[PlyCount "122"]
[Variant "Standard"]

1. Nc3 d5 2. d4 c5 3. e3 Nc6 4. dxc5 Nf6 5. Bb5 e6 6. Qd4 Nd7 7. Bxc6 bxc6 8. Nf3 Nxc5 9. O-O Qf6 10. Qb4 h5 11. Qa5 Ba6 12. Rfe1 Bb7 13. e4 Nxe4 14. Nxe4 dxe4 15. Rxe4 Qd8 16. Qc3 c5 17. Re5 Qb6 18. Be3 Bxf3 19. gxf3 O-O-O 20. Bxc5 Qc7 21. Bd4 Qxc3 22. Bxc3 Bd6 23. Rg5 Rhg8 24. Rxh5 Rgh8 25. Rg5 Bxh2+ 26. Kg2 Bc7 27. Rxg7 Rhg8 28. Rxg8 Rxg8+ 29. Kh1 Rg5 30. Rg1 Rf5 31. Rg8+ Kb7 32. Kg2 a6 33. Re8 Kc6 34. Re7 Kd6 35. Bb4+ Kc6 36. Bd2 Rc5 37. c3 Ra5 38. a3 Rd5 39. Be3 Rd7 40. Rxd7 Kxd7 41. f4 Bd8 42. Bd4 a5 43. Kg1 Kc6 44. c4 a4 45. Kf1 Bc7 46. Be3 e5 47. f5 e4 48. Bd4 Bb6 49. Bc3 Kd6 50. Bb4+ Kc6 51. c5 Bxc5 52. Bc3 Kd6 53. f6 Kd5 54. Kg1 Kc4 55. Kg2 Bxa3 56. Kf1 Kb3 57. bxa3 Kxc3 58. Ke2 Kb2 59. Ke3 Kxa3 60. Ke2 Kb3 61. Ke3 Kb2 0-1
[/pgn]

Henk
Posts: 6560
Joined: Mon May 27, 2013 8:31 am

Re: End Game Heuristics

Post by Henk » Thu Mar 20, 2014 4:55 pm

51. c5 ??

User avatar
hgm
Posts: 25076
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: End Game Heuristics

Post by hgm » Thu Mar 20, 2014 4:57 pm

Fairy-Max also plays 59. Ke3. Upto 20 ply it prefers Kd2 with score -2.5. But at 21 ply its score for this move drops to -6.9, and it switches to Ke3.

So indeed it seems a lost position.

Post Reply