Chess endgame engine built on my own with BFS algorithm and dictionary data structure

Question

I was using ChatGPT4 for creating a chess code for the problem stated below, but mostly I was not obtaining any results beyond "depth 0 up to depth 19" with the number of positions searched.The problem is definitely memory-wise manageable. The short description goes like this: I have a very few pieces on my ASCII board, D=3,4 or 5. I want to write a code which puts all reachable positions in a dictionary, call it A.Now I want to assign a (small) natural number to each key in A, 0 meaning the checkmate for black or white, together with a 2nd parameter parent, so I should end up with something like this: [initial_fen,None,None]. Here the first None means that the number of moves hasn't been determined yet. The second None means that the parent of initial_fen string doesn't exist (and won't exist for the rest of the computation, this being a unique exception, all other keys in A will have a Parent) Then, going up a bit, I want to assign 1 for all the keys in A such that there is a unique legal move for player in question to the other player with Label, i.e. the second entry, equal to 0. Then, going yet up, I want to apply any() and all() logic recursively to all other positions, eventually yielding Label for initial_fen, together with the path leading to a checkmate or draw, as optimal as theoretically possible for both players. Can someone spot a bug in it ?

import chess

def simplify_fen(fen):
    parts = fen.split(' ')
    return ' '.join(parts[:4])


def evaluate_position(board):
    if board.is_checkmate():
        return 1 if board.turn else -1  # 1 for White win, -1 for Black win
    elif board.is_stalemate() or board.is_insufficient_material():
        return 0  # Draw
    return None  # Game not ended

def assign_labels_and_parents(reachable_positions, board, depth):
    for fen in reachable_positions:
        board.set_fen(fen)
        result = evaluate_position(board)

        if result is not None:
            reachable_positions[fen]['label'] = result
        elif depth > 0:
            child_positions = generate_reachable_positions(board, depth - 1)
            if board.turn:  # White's turn, use 'any' logic
                reachable_positions[fen]['label'] = any(
                    child_positions[child_fen]['label'] == 1 for child_fen in child_positions)
            else:  # Black's turn, use 'all' logic
                reachable_positions[fen]['label'] = all(
                    child_positions[child_fen]['label'] == -1 for child_fen in child_positions)

def generate_reachable_positions(board, depth):
    reachable_positions = {}
    for move in board.legal_moves:
        board.push(move)
        fen = board.fen()
        reachable_positions[fen] = {'label': None, 'parent': board.fen() if board.move_stack else None}
        board.pop()
    assign_labels_and_parents(reachable_positions, board, depth)
    return reachable_positions

def main():
    initial_fen = "startpos"  # Replace with your specific starting position
    initial_fen = "8/8/8/8/8/7Q/3K4/k7 w - - 0 1"

    board = chess.Board(fen=initial_fen)
    depth = 5  # Modify as needed

    reachable_positions = generate_reachable_positions(board, depth)

    # Display the results
    for fen, data in reachable_positions.items():
        print(fen, data)

if __name__ == "__main__":
    main()

BUT I'm getting this

7Q/8/8/8/8/8/3K4/k7 b - - 1 1 {'label': False, 'parent': '7Q/8/8/8/8/8/3K4/k7 b - - 1 1'}
2Q5/8/8/8/8/8/3K4/k7 b - - 1 1 {'label': False, 'parent': '2Q5/8/8/8/8/8/3K4/k7 b - - 1 1'}
8/7Q/8/8/8/8/3K4/k7 b - - 1 1 {'label': False, 'parent': '8/7Q/8/8/8/8/3K4/k7 b - - 1 1'}
8/3Q4/8/8/8/8/3K4/k7 b - - 1 1 {'label': False, 'parent': '8/3Q4/8/8/8/8/3K4/k7 b - - 1 1'}
8/8/7Q/8/8/8/3K4/k7 b - - 1 1 {'label': False, 'parent': '8/8/7Q/8/8/8/3K4/k7 b - - 1 1'}
8/8/4Q3/8/8/8/3K4/k7 b - - 1 1 {'label': False, 'parent': '8/8/4Q3/8/8/8/3K4/k7 b - - 1 1'}
8/8/8/7Q/8/8/3K4/k7 b - - 1 1 {'label': False, 'parent': '8/8/8/7Q/8/8/3K4/k7 b - - 1 1'}
8/8/8/5Q2/8/8/3K4/k7 b - - 1 1 {'label': False, 'parent': '8/8/8/5Q2/8/8/3K4/k7 b - - 1 1'}
8/8/8/8/7Q/8/3K4/k7 b - - 1 1 {'label': False, 'parent': '8/8/8/8/7Q/8/3K4/k7 b - - 1 1'}
8/8/8/8/6Q1/8/3K4/k7 b - - 1 1 {'label': False, 'parent': '8/8/8/8/6Q1/8/3K4/k7 b - - 1 1'}
8/8/8/8/8/6Q1/3K4/k7 b - - 1 1 {'label': False, 'parent': '8/8/8/8/8/6Q1/3K4/k7 b - - 1 1'}
8/8/8/8/8/5Q2/3K4/k7 b - - 1 1 {'label': False, 'parent': '8/8/8/8/8/5Q2/3K4/k7 b - - 1 1'}
8/8/8/8/8/4Q3/3K4/k7 b - - 1 1 {'label': False, 'parent': '8/8/8/8/8/4Q3/3K4/k7 b - - 1 1'}
8/8/8/8/8/3Q4/3K4/k7 b - - 1 1 {'label': False, 'parent': '8/8/8/8/8/3Q4/3K4/k7 b - - 1 1'}
8/8/8/8/8/2Q5/3K4/k7 b - - 1 1 {'label': False, 'parent': '8/8/8/8/8/2Q5/3K4/k7 b - - 1 1'}
8/8/8/8/8/1Q6/3K4/k7 b - - 1 1 {'label': 0, 'parent': '8/8/8/8/8/1Q6/3K4/k7 b - - 1 1'}
8/8/8/8/8/Q7/3K4/k7 b - - 1 1 {'label': False, 'parent': '8/8/8/8/8/Q7/3K4/k7 b - - 1 1'}
8/8/8/8/8/8/3K3Q/k7 b - - 1 1 {'label': False, 'parent': '8/8/8/8/8/8/3K3Q/k7 b - - 1 1'}
8/8/8/8/8/8/3K2Q1/k7 b - - 1 1 {'label': False, 'parent': '8/8/8/8/8/8/3K2Q1/k7 b - - 1 1'}
8/8/8/8/8/8/3K4/k6Q b - - 1 1 {'label': False, 'parent': '8/8/8/8/8/8/3K4/k6Q b - - 1 1'}
8/8/8/8/8/8/3K4/k4Q2 b - - 1 1 {'label': False, 'parent': '8/8/8/8/8/8/3K4/k4Q2 b - - 1 1'}
8/8/8/8/8/4K2Q/8/k7 b - - 1 1 {'label': False, 'parent': '8/8/8/8/8/4K2Q/8/k7 b - - 1 1'}
8/8/8/8/8/3K3Q/8/k7 b - - 1 1 {'label': False, 'parent': '8/8/8/8/8/3K3Q/8/k7 b - - 1 1'}
8/8/8/8/8/2K4Q/8/k7 b - - 1 1 {'label': False, 'parent': '8/8/8/8/8/2K4Q/8/k7 b - - 1 1'}
8/8/8/8/8/7Q/4K3/k7 b - - 1 1 {'label': False, 'parent': '8/8/8/8/8/7Q/4K3/k7 b - - 1 1'}
8/8/8/8/8/7Q/2K5/k7 b - - 1 1 {'label': False, 'parent': '8/8/8/8/8/7Q/2K5/k7 b - - 1 1'}
8/8/8/8/8/7Q/8/k3K3 b - - 1 1 {'label': False, 'parent': '8/8/8/8/8/7Q/8/k3K3 b - - 1 1'}
8/8/8/8/8/7Q/8/k2K4 b - - 1 1 {'label': False, 'parent': '8/8/8/8/8/7Q/8/k2K4 b - - 1 1'}
8/8/8/8/8/7Q/8/k1K5 b - - 1 1 {'label': False, 'parent': '8/8/8/8/8/7Q/8/k1K5 b - - 1 1'}

Answer 1

OK but this is only a partial answer because I don't use or recognise that programming language and I can't be sure that my syntax is even right, let alone test it. These changes might put some of the failings right:

def generate_reachable_positions(board, depth):
reachable_positions = {}
parent = board.fen()
for move in board.legal_moves:
    board.push(move)
    fen = board.fen()
    reachable_positions[fen] = {'label': None, 'parent': parent if board.move_stack else None}
    board.pop()
assign_labels_and_parents(reachable_positions, board, depth)
return reachable_positions

Saving the FEN representation of the parent node before making each move should result in the table then being self consistent.

That should result in the parent node being displayed correctly in each of its children. Then you will need to see how it performs playing for black (it should prefer the move(s) which delay being mated the longest).

I strongly suggest that you do some manual testing on positions with blocked pawns and very few legal moves for testing purposes. You need to be able to mentally check that it is working correctly before running it on the wider problem. You will also need to verify that it works correctly to at least ply 3 or 4 before it is worth letting it run to completion. Working out a move tree manually even for 3^N or 4^N gets to 27 or 64 terminal nodes at ply 3. It is way to hard to check functionality by hand for branching factors above ~5.

Ultimately I reckon you will want to have the table indexed by a fast hash of the position and each parent only storing the winning or maximal delaying loss move (working back from the terminal nodes) and possibly moves to win/loss/draw. Your present data structures will be too big and slow for more difficult problems.