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
Retrograde analysis - TBs move sequences to checkmate
Moderators: hgm, Rebel, chrisw
-
- Posts: 5
- Joined: Sun Sep 22, 2019 8:30 am
- Full name: Hedinn Steingrimsson
-
- Posts: 12542
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: Retrograde analysis - TBs move sequences to checkmate
You probably want the Nalimov tablebase files.
They have minimum distance to mate (there are some problems like the move counter and e.p. status, but they are usually not a problem for reasonable distances with the 100 ply counter and e.p. is rare in 6 man endgames.)
You can fool around with them online.
This site has a nice interface:
http://www.k4it.de/?topic=egtb&lang=en
Another possibility is the Lomonosov files. You can get access with this application:
https://play.google.com/store/apps/deta ... b&hl=en_US
but if you want windows live access to the files, I believe you have to pay for it.
The Syzygy files can also be used. But they will find a sure mate, but not necessarily the shortest mate.
I guess the bottom line is that there is no perfect solution today.
They have minimum distance to mate (there are some problems like the move counter and e.p. status, but they are usually not a problem for reasonable distances with the 100 ply counter and e.p. is rare in 6 man endgames.)
You can fool around with them online.
This site has a nice interface:
http://www.k4it.de/?topic=egtb&lang=en
Another possibility is the Lomonosov files. You can get access with this application:
https://play.google.com/store/apps/deta ... b&hl=en_US
but if you want windows live access to the files, I believe you have to pay for it.
The Syzygy files can also be used. But they will find a sure mate, but not necessarily the shortest mate.
I guess the bottom line is that there is no perfect solution today.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
-
- Posts: 1470
- Joined: Mon Apr 23, 2018 7:54 am
Re: Retrograde analysis - TBs move sequences to checkmate
Comments suggest this is no longer active.Dann Corbit wrote: ↑Thu Mar 12, 2020 7:59 am Another possibility is the Lomonosov files. You can get access with this application:
https://play.google.com/store/apps/deta ... b&hl=en_US
-
- Posts: 27822
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Retrograde analysis - TBs move sequences to checkmate
Do you want to do this for end-games with just a few pieces, or for solving checkmate puzzles with many pieces? I don't think retrograde analysis would be possible for the latter. (And in the other case, why do it? All the cases for which this is currently feasible have already been done.)
-
- Posts: 4833
- Joined: Sun Aug 10, 2008 3:15 pm
- Location: Philippines
Re: Retrograde analysis - TBs move sequences to checkmate
I tried to implement it using python-chess module. Just mate in 1, example from mate position.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
[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()
-
- Posts: 5
- Joined: Sun Sep 22, 2019 8:30 am
- Full name: Hedinn Steingrimsson
Re: Retrograde analysis - TBs move sequences to checkmate
Thank you H.G. Muller,hgm wrote: ↑Thu Mar 12, 2020 2:05 pm Do you want to do this for end-games with just a few pieces, or for solving checkmate puzzles with many pieces? I don't think retrograde analysis would be possible for the latter. (And in the other case, why do it? All the cases for which this is currently feasible have already been done.)
I want to do this for end-games with just a few pieces.
Currently I am focused on K and rook vs. K.
This is the method that TBs were created with so that I thought that there should be code for this somewhere out there although it might be a bit old.
I am currently working with Gaviota which has DTM and works with python chess (python chess does not handle Lomonosov). I am also comfortable with other programming languages.
My motivation is related to your writings, which I like about minimax: Why minimax is fundamentally flawed http://www.talkchess.com/forum3/viewtop ... 5&start=50 - feel free to send me a personal msg regarding that discussion -
If not given the solution with rescoring or TB lookup, modern engines do not handle even these simple endgames well ( mini max search based like Stockfish better than Monte Carlso search based like Leela though). My hypothesis is that it is because they lack the notion of making progress. Creating this dataset with optimal DTM paths is a step in understanding that phenomena.
Best,
Stein
-
- Posts: 5
- Joined: Sun Sep 22, 2019 8:30 am
- Full name: Hedinn Steingrimsson
Re: Retrograde analysis - TBs move sequences to checkmate
Ferdy wrote: ↑Fri Mar 13, 2020 4:19 amI tried to implement it using python-chess module. Just mate in 1, example from mate position.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
[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.pyCode: 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()
Thank you Ferdi,
Very interesting.
Making your approach recursive would be really great.
Thanks,
Hedinn
-
- Posts: 27822
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Retrograde analysis - TBs move sequences to checkmate
Well, there is code for a simple 3-men generator in JavaScript, powering http://hgm.nubati.net/rules/EGT.html . The description of an early version of FairyGen can be found at http://home.hccnet.nl/h.g.muller/EGTB.html ; FairyGen itself is public domain, and the source code is included in its download package. I also have a very simple 3+1-men generator that makes minimal assumptions on board and pieces (so that it can be used for non-square boards, and handle totally asymmetric pieces), which I never released.Stein wrote: ↑Mon Mar 16, 2020 7:05 amIf not given the solution with rescoring or TB lookup, modern engines do not handle even these simple endgames well ( mini max search based like Stockfish better than Monte Carlso search based like Leela though). My hypothesis is that it is because they lack the notion of making progress. Creating this dataset with optimal DTM paths is a step in understanding that phenomena.