Implementation of chess endgame engine without Endgame Tablebases

Question

I'm interested in creating an chess endgame solving engine.

The endgames in chess are usually solved using the endgame table-bases generated by retrograde algorithm. However, before starting the implementation I wanted to find out whether the chess endgames can be played without the endgame table-bases?

If yes, then what are the pros and cons of these alternatives to endgame tables?

Answer 1

Preface: you don't state in your question how knowledgable you are about computer chess in general. This answer uses some jargon that may or may not be unfamiliar; in general, looking up the term on the excellent Chess Programming Wiki will be helpful.

Introduction to Heuristics

Chess engines without endgame tablebases play the endgame the same way they play the rest of the game; using a search algorithm such as minimax with alpha-beta pruning to optimise a set of heuristics. A simple heuristic for the endgame could be to score positions as better when the enemy king is on the edge of the board and your pieces are close to it, especially strong pieces like the queen. This alone will be sufficient for "obvious" endgames such as KQK (king and queen vs. lone king); the search will favour lines of play that force the opposing king toward the edge of the board. Eventually a forced checkmate will come into the horizon of the search, and that's that.

This won't work very well for anything else, however. Consider the KNBK (king, knight and bishop vs. lone king) endgame. A forced mate is always possible (unless the lone king can capture one of the pieces in the start position), but it takes dozens of moves to achieve it and the mate only works when the king is forced to a corner that the bishop can attack. Our naive heuristic would struggle to get anywhere without taking a prohibitive amount of time to search the position. The solution is to have a custom heuristic that is applied only in this endgame.

KNBK Heuristic Walkthrough

The following is the KNBK heuristic from my own chess engine, translated into pseudocode:

evalKNBK(winningKingSquare, winningBishopSquare, losingKingSquare){
    int baseScore = 600
    int distance

    if the bishop's square is white {
        distance = Manhattan distance of losing king's square from closest of a8/h1
    } else {
        distance = Manhattan distance of losing king's square from closest of a1/h8
    }
    baseScore -= (25 * distance)

    int kingDistance = 12 * Manhattan distance between the kings
    baseScore -= kingDistance

    if Black is to play {
        baseScore *= -1
    }

    return baseScore
}

The baseScore is measured in centipawns, a common unit for the worth of a position. Don't worry too much about the precise numbers for the moment, just focus on the algorithm. First, we penalise the position if the lone king is far away from a corner that the bishop can attack. This encourages the engine to drive the lone king towards such a corner.

Next, we penalise the position if our king is far away from the lone king. This is because in KNBK, the king has to support the bishop and knight in order to make progress. It is not weighted as strongly in order to make the engine prefer forcing the king toward a good corner over keeping the king close.

Finally, we multiply the score by -1 if it's Black to play. This is for the minimax search; White seeks to maximise the score of a position, while Black seeks to minimise it. A score of -600 is therefore better for Black than a score of -450 (say), and the heuristic reflects this.

My chess engine is general-purpose, so it only implements these customised heuristics for particularly common endgames (KNBK is probably the least common endgame that is covered; some others include KRK, KPK, KBKB and KNNK). In a special-purpose endgame engine, you would want a much larger range of endgames covered by a heuristic like this one, and only let especially weird endgames fall through to the default evaluation.

Scoring a Position

Now, regarding those numbers. When using heuristics, these numbers must be finely tuned to prevent the engine making weird-looking moves that, while eventually winning, miss a much easier method. For example, if your engine has KQNB against lone K, the best winning method is probably just mating with king and queen, ignoring the knight and bishop unless there's a risk of stalemate. In practice, the engine may make odd moves such as sacrificing the knight and bishop to reduce the game to KQK, and only then getting on with the checkmate process. Tuning the numbers to prevent this is a bit of an imprecise art, and extensive testing is necessary to ensure the worst blunders are avoided.

Recognising Types of Endgames

The other problem to solve when using heuristics is efficiently recognising which endgame you actually have. This is highly dependent on the data structure you're using to represent the current position, so I won't go into too much detail here, but I'll talk about the solution I chose for my engine. I compute what I like to call an "endgame signature", based on the quantity of each type of piece. This is then used in a switch statement and compared to named constants. It looks a little messy, but because I store the number of each piece type and update it as I go, this is very quick to compute. There are many other ways of achieving the same effect; the only way to know which is best is to implement each and see for yourself.

Summary

• Determine what endgame the current board position represents
• Compute a score for each position using an appropriate heuristic - aspects of this endgame that tend to be good (or bad)
• Use this score to compare positions and select the move leading to the best one, using the minimax search algorithm

I know this answer might be a bit of an infodump, but I hope it gets the point across okay. As I mentioned above, the Chess Programming Wiki is an excellent resource for any further questions you might have. There are also many forums with a generally friendly and active community who will be happy to help. Good luck with your engine!

Answer 2

You can........ but the math to do this is Discrete Math and it is a pain..... While your engine will be more dynamic at solving problems the amount of code is almost as bad as living the world of Discrete Math until it is done unless you like that stuff.

On the other hand if you do it you will become a know the kung fu of Discrete Mathematics like the back of your hand and you coding ability will grow exponentially.

The program will also be a memory hog since the best way to figure out most of the calculations will be recursion and depending on the computer you may get a stack over flow.