Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I am interested in developing a program that generates an endgame table-base for the chess.

I have gone through the technical papers of the greats like Shannon and Ken Thompson. I have found that retrograde analysis is used for the generation.

How can I generate all positions in a KBBK chess endgame which are mates in 0?

share|improve this question
3  
Sharing your research helps everyone. Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see How to Ask –  gnat Dec 27 '13 at 16:05
add comment

4 Answers

The number of all possible possitions involving KBBK and a checkmate is not that great at all: 32 squares for the light-squared bishop * 32 for the dark-squared bishop * 62 for the White king (64 - 2 already taken by both bishops) * all squares where the Black king is checked by one of the bishops (it must be in check, otherwise it's not checkmate yet - or not a "mate in 0", if you prefer).

So - given that generating endgame tablebases is computationally intensive - you could easily find all the positions by brute force. It'll be super quick. It's a tiny fraction of total work you have to do anyway.

For all 63488 positions that KBB can occupy (and you could cut this number down because chessboard is symmetrical - 63448 / 2 (mirrored horizontally) / 2 (mirrored vertically) = 15862), so for every one out of these 15 thousands positions find all squares where Black king is checked by one of the bishops.

Now for each of these squares see if there is any square the Black king could go to to escape from check. If there isn't any - it's a checkmate position. Rinse and repeat.

share|improve this answer
1  
Because of promotion, I don't think that you can assume that the bishops are on different colored squares. –  RBarryYoung Dec 27 '13 at 23:43
2  
@RBarryYoung in this case you can, because if they are on same colored squares, checkmating is impossible. –  Konrad Morawski Dec 28 '13 at 10:59
1  
mind that one has to eliminate impossible positions (both kings next to each other) and there are unreachable positions (like white king B6 and bishops on A7 and H1, black king A8) –  johannes Dec 28 '13 at 14:30
2  
@johannes kings - yes, good point. and it's trivial to rule these cases out. as for unreachable positions in the second sense, I believe this could be left for later, for the retrograde analysis part - that's when you search for all positions that could have led to this particular checkmate, and discover that no legal prior positions exist. –  Konrad Morawski Dec 28 '13 at 14:56
    
Each bishop attacks up to 14 different squares, so this is actually about 444k positions to search (15862*28). We can do significantly better than that - see my answer. –  BlueRaja - Danny Pflughoeft Dec 30 '13 at 22:04
add comment

Already a good answer here, but I try to highlight the problem from a slightly different point of view. When you are going to implement a full retrograde analysis for KBBK, you have to generate all KBBK positions, which are less than 32*32*62*61*2. The "32" is the number of squares for the bishops, the "*2" takes into account which player moves next; and not all 32*32*62*61 theoretical placements of the four pieces are legal (obviously, you can exclude any positions where the kings have a positional distance <2).

For the analysis, take these positions as the vertices of a directed graph, and the edges are the legal transitions from one position to the next (according to the possible moves).

Now, mark the positions where white moves next and the black king could be captured by a white bishop. Technically, capturing the king is not legal according to the classic chess rules, but lets assume for a moment it were legal and call these positions "mate in -1". The "mate in 0" positions then are the vertices in the graph where black moves next, having only "mate in -1" sucessors, and where the black king is already checked (when there are just "mate in -1"-successors, and the black king is not checked, it is a remis situation).

More generally, a position where black moves next is a "mate in x+1", when x is the maximum of all y among the successors in the graph with a "mate in y" position, and there is no remis situation. When black moves next and there is at least one remis position amoung the successors, the current position is a remis situation, too. A position where white moves next is a "mate in x+1", when x is the minimum of all y among the successors with a "mate in y" position (regardless of remis positions). When white moves next, a position is only a remis position when all successors are remis positions, too.

So "mate in 0" positions can be simply identified by applying the first step of your retrograde analysis.

share|improve this answer
add comment

The "mates in 0" would be the positions that the king is in checkmate. Konrad gave a way to brute-force them through 444k positions, but we can do significantly better than that.

The black king must be on the edge of the board, so that gives 28 positions. One of the bishops must be giving it check; there are only 7 spots that's possible. The other bishop must be attacking one of the squares adjacent to the king, there are at most 15 positions for that. Finally, the opposing king must also be attacking an adjacent square, so there are up to 9 possible spots for it.

After accounting for horizontal- and vertical-symmetry (divide by 4), we get ~6.6k positions to search over.

share|improve this answer
add comment

Let's look at the problem in a more general way. You probably want to have tables for all combinations of pieces. Also, you probably have a chess engine that can generate possible moves, execute moves, detect check and checkmate situations, evaluate positions, etc. I have, and I use the following algorithm:

In 4 nested loops, generate all possible positions. Skip illegal positions. This nest is executed many times. In the first pass, detect all checkmate positions (= black has no moves and is in check). In following passes, execute all possible moves and see if they lead to a position already covered. Add passes until no more solutions are found. Table values must be consistent with the move evaluating system of your chess engine (probably with a conversion formula). I use one byte per table entry.

Table size for a 4-piece endgame is:

no pawns: 2*10*64*64*64 (using horizontal, vertical and diagonal mirroring)

with pawns: 2*32*64*64*64 (using horizontal mirroring only)

In a general algorithm, you can not use shortcuts, but have to use the brute force method. I generate my 4-piece tables in app. 1 minute each on a high end PC.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.