Retrograde analysis - TBs move sequences to checkmate

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

Stein
Posts: 5
Joined: Sun Sep 22, 2019 8:30 am
Full name: Hedinn Steingrimsson

Retrograde analysis - TBs move sequences to checkmate

Post by Stein »

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
Top
Dann Corbit
Posts: 12537
Joined: Wed Mar 08, 2006 8:57 pm
Location: Redmond, WA USA

Re: Retrograde analysis - TBs move sequences to checkmate

Post by Dann Corbit »

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.
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.
Top
jp
Posts: 1470
Joined: Mon Apr 23, 2018 7:54 am

Re: Retrograde analysis - TBs move sequences to checkmate

Post by jp »

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
Comments suggest this is no longer active.
Top
User avatar
hgm
Posts: 27787
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Retrograde analysis - TBs move sequences to checkmate

Post by hgm »

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.)
Top
Ferdy
Posts: 4833
Joined: Sun Aug 10, 2008 3:15 pm
Location: Philippines

Re: Retrograde analysis - TBs move sequences to checkmate

Post by Ferdy »

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()
Top
Stein
Posts: 5
Joined: Sun Sep 22, 2019 8:30 am
Full name: Hedinn Steingrimsson

Re: Retrograde analysis - TBs move sequences to checkmate

Post by Stein »

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.)
Thank you H.G. Muller,

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
Top
Stein
Posts: 5
Joined: Sun Sep 22, 2019 8:30 am
Full name: Hedinn Steingrimsson

Re: Retrograde analysis - TBs move sequences to checkmate

Post by Stein »

Ferdy wrote: ↑Fri Mar 13, 2020 4:19 am
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()

Thank you Ferdi,

Very interesting.
Making your approach recursive would be really great.

Thanks,
Hedinn
Top
User avatar
hgm
Posts: 27787
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Retrograde analysis - TBs move sequences to checkmate

Post by hgm »

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

Return to “Computer Chess Club: Programming and Technical Discussions”