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?
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.
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.
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.
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.
