Stein wrote: ↑Thu Mar 12, 2020 5:33 am
Hi,
I am interested in finding the paths to checkmate given best possible play by both sides.
Do you know about a good open source implementation of that?
Ken Thompson's paper has a good description.
Essentially it is a one-directional tree which is reconstructed working backwards starting from the leaves of the tree (checkmate positions) with a link between node x to node y if node y is one of the best moves from node x in terms of shortest checkmate.
Essentially creating a series of FENs that lead to checkmate.
There should be some decent implementations out there, after all this is how the TBs were created.
Which one do you recommend?
Cheers!
Stein
I tried to implement it using python-chess module. Just mate in 1, example from mate position.
[d]1k6/1Q6/1K6/8/8/8/8/8 b - - 0 1
Invert the side to move and now generate moves for the side to move except when it attacks the black king and capture the black king.
Example generated positions.
[d]1k6/7Q/1K6/8/8/8/8/8 w - -
then we can add captured piece too.
[d]1k6/1p5Q/1K6/8/8/8/8/8 w - -
and so on.
[d]1k6/1n5Q/1K6/8/8/8/8/8 w - -
Then Qg7 move.
[d]1k6/6Q1/1K6/8/8/8/8/8 w - -
Then other queen move to empty squares with or without captured piece at from square.
So the saved epds are:
1k6/7Q/1K6/8/8/8/8/8 w - -
1k6/1p5Q/1K6/8/8/8/8/8 w - -
1k6/1n5Q/1K6/8/8/8/8/8 w - -
1k6/1b5Q/1K6/8/8/8/8/8 w - -
1k6/1r5Q/1K6/8/8/8/8/8 w - -
1k6/1q5Q/1K6/8/8/8/8/8 w - -
1k6/6Q1/1K6/8/8/8/8/8 w - -
1k6/1p4Q1/1K6/8/8/8/8/8 w - -
1k6/1n4Q1/1K6/8/8/8/8/8 w - -
1k6/1b4Q1/1K6/8/8/8/8/8 w - -
1k6/1r4Q1/1K6/8/8/8/8/8 w - -
1k6/1q4Q1/1K6/8/8/8/8/8 w - -
[d]1k6/5Q2/1K6/8/8/8/8/8 w - -
1k6/1p3Q2/1K6/8/8/8/8/8 w - -
1k6/1n3Q2/1K6/8/8/8/8/8 w - -
1k6/1b3Q2/1K6/8/8/8/8/8 w - -
1k6/1r3Q2/1K6/8/8/8/8/8 w - -
1k6/1q3Q2/1K6/8/8/8/8/8 w - -
1k6/4Q3/1K6/8/8/8/8/8 w - -
1k6/1p2Q3/1K6/8/8/8/8/8 w - -
1k6/1n2Q3/1K6/8/8/8/8/8 w - -
1k6/1b2Q3/1K6/8/8/8/8/8 w - -
[d]1k6/1r2Q3/1K6/8/8/8/8/8 w - -
1k6/1q2Q3/1K6/8/8/8/8/8 w - -
1k6/3Q4/1K6/8/8/8/8/8 w - -
1k6/1p1Q4/1K6/8/8/8/8/8 w - -
1k6/1n1Q4/1K6/8/8/8/8/8 w - -
1k6/1b1Q4/1K6/8/8/8/8/8 w - -
1k6/1r1Q4/1K6/8/8/8/8/8 w - -
1k6/1q1Q4/1K6/8/8/8/8/8 w - -
1k6/8/1KQ5/8/8/8/8/8 w - -
1k6/1p6/1KQ5/8/8/8/8/8 w - -
1k6/1n6/1KQ5/8/8/8/8/8 w - -
1k6/1b6/1KQ5/8/8/8/8/8 w - -
1k6/1r6/1KQ5/8/8/8/8/8 w - -
1k6/1q6/1KQ5/8/8/8/8/8 w - -
1k6/8/QK6/8/8/8/8/8 w - -
1k6/1p6/QK6/8/8/8/8/8 w - -
[d]1k6/1n6/QK6/8/8/8/8/8 w - -
1k6/1b6/QK6/8/8/8/8/8 w - -
1k6/1r6/QK6/8/8/8/8/8 w - -
1k6/1q6/QK6/8/8/8/8/8 w - -
1k6/8/1K6/3Q4/8/8/8/8 w - -
1k6/1p6/1K6/3Q4/8/8/8/8 w - -
1k6/1n6/1K6/3Q4/8/8/8/8 w - -
1k6/1b6/1K6/3Q4/8/8/8/8 w - -
1k6/1r6/1K6/3Q4/8/8/8/8 w - -
1k6/1q6/1K6/3Q4/8/8/8/8 w - -
1k6/8/1K6/8/4Q3/8/8/8 w - -
1k6/1p6/1K6/8/4Q3/8/8/8 w - -
1k6/1n6/1K6/8/4Q3/8/8/8 w - -
1k6/1b6/1K6/8/4Q3/8/8/8 w - -
1k6/1r6/1K6/8/4Q3/8/8/8 w - -
1k6/1q6/1K6/8/4Q3/8/8/8 w - -
1k6/8/1K6/8/8/5Q2/8/8 w - -
1k6/1p6/1K6/8/8/5Q2/8/8 w - -
1k6/1n6/1K6/8/8/5Q2/8/8 w - -
1k6/1b6/1K6/8/8/5Q2/8/8 w - -
[d]1k6/1r6/1K6/8/8/5Q2/8/8 w - -
1k6/1q6/1K6/8/8/5Q2/8/8 w - -
1k6/8/1K6/8/8/8/6Q1/8 w - -
1k6/1p6/1K6/8/8/8/6Q1/8 w - -
1k6/1n6/1K6/8/8/8/6Q1/8 w - -
1k6/1b6/1K6/8/8/8/6Q1/8 w - -
1k6/1r6/1K6/8/8/8/6Q1/8 w - -
1k6/1q6/1K6/8/8/8/6Q1/8 w - -
1k6/8/1K6/8/8/8/8/7Q w - -
1k6/1p6/1K6/8/8/8/8/7Q w - -
1k6/1n6/1K6/8/8/8/8/7Q w - -
1k6/1b6/1K6/8/8/8/8/7Q w - -
1k6/1r6/1K6/8/8/8/8/7Q w - -
[d]1k6/1q6/1K6/8/8/8/8/7Q w - -
That is only mate in 1, to go for next ply, from each generated position we can do similar method but this time it is black to move, so the black king can move to empty square, it can move into check, but not close to white king. This will take time when there are many pieces on the board of course, there could be rules to observe on promotion, castle and even e.p capture and pawn 2-step moves.
Here is the python code for mate in 1.
retro.py
Code: Select all
# -*- coding: utf-8 -*-
"""
mate in 1 chess retrograde
Needed:
python 3.7
requirements:
python-chess v0.30.1
Tests:
system: windows 10
status: OK
"""
import chess
def main():
# Enter your fen here
fen = '1k6/1Q6/1K6/8/8/8/8/8 b - - 0 1'
b = chess.Board(fen)
print(b)
print(f'initial pos: {b.epd()}\n')
epds = []
# Change turn because we will generate from other side
b.turn = not b.turn
# Find position by generating moves
for m in b.legal_moves:
last_board = b.copy()
try:
b.push(m)
# (1) Don't save fen if the move checks opp king
if b.is_attacked_by(not b.turn, b.king(b.turn)):
b.pop()
continue
# (2) Don't generate capture moves
if last_board.is_capture(m):
b.pop()
continue
b1 = b.copy()
b1.turn = not b1.turn
epds.append(b1.epd()) # Save epd
# Get epd when a piece is added on the from square
for pt in [chess.PAWN, chess.KNIGHT, chess.BISHOP, chess.ROOK, chess.QUEEN]:
# If pawn it should not be in 1/8 ranks
if pt == chess.PAWN:
rank = chess.square_rank(m.from_square)
if rank == 0 or rank == 7:
continue
# Now add the piece on copied board
cp = chess.Piece(pt, not b1.turn)
b1.set_piece_at(m.from_square, cp)
epds.append(b1.epd()) # Save epd
except:
pass
b.pop() # Undo and try other moves
# Save the epds to a file
with open('retro.epd', 'w') as f:
for epd in epds:
f.write(f'{epd}\n')
if __name__ == '__main__':
main()