Python国际象棋残局引擎最优解计算异常，寻求Bug排查

我正在开发一款追求完美最优的国际象棋残局引擎，规则为：胜方需尽可能快地将死对手，负方则尽可能拖延将死时间。但在处理初始FEN为8/8/8/4k3/2K4R/8/8/8 w - - 0 1的局面时，引擎得出需27回合（plies）将死的结果，而正确结果应为23回合，恳请帮忙排查代码中的Bug。

当前实现代码 #

import chess

def simplify_fen_string(fen):
    parts = fen.split(' ')
    simplified_fen = ' '.join(parts[:4])  # Zachováváme pouze informace o pozici
    return simplified_fen

def evaluate_position(board):
    #print(f"Position: {board.fen()}")
    if board.is_checkmate():
     ###   print(f"Position: {board.fen()}, return -1000")
        return -1000  # Mat protihráči
    elif board.is_stalemate() or board.is_insufficient_material() or board.can_claim_draw():
     ###   print(f"Position: {board.fen()}, return 0")

        return 0  # Remíza
    else:
        #print(f"Position: {board.fen()}, return None")
        return None  # Hra pokračuje


def create_AR_entry(result, children, last_move):
   return {"result": result, "children": children, "last_move": last_move, "best_child": None} 


def update_best_case(best_case):
    if best_case == 0:
        return best_case
    if best_case > 0:
        return best_case - 1
    else:
        return best_case + 1


def update_AR_for_mate_in_k(board, AR, simplified_initial_fen, max_k=1000):
    
    evaluated_list = []
    #print(f"")
    
    for k in range(1, max_k + 1):
        print(f"K = {k}")
        changed = False
        for _t in range(2):  # Zajistíme, že pro každé k proběhne aktualizace dvakrát
            print(f"_t = {_t}")
            for fen in list(AR.keys()):
                
                
                #print(f"Fen = {fen}, looking for {simplified_initial_fen}, same = {fen == simplified_initial_fen}")
                board.set_fen(fen)
                
                if AR[fen]['result'] is not None:
                    if fen == simplified_initial_fen:
                        print(f"Finally we found a mate! {AR[fen]['result']}")
                        return
                    continue  # Pokud již máme hodnocení, přeskočíme
                
                # Získáme výchozí hodnoty pro nejlepší a nejhorší scénář
                best_case = float("-inf")
                #worst_case = float("inf")
                nones_present = False
                best_child = None

                    
                for move in board.legal_moves:
                    #print(f"Move = {move}")
                    board.push(move)
                    next_fen = simplify_fen_string(board.fen())
                    #AR[fen]['children'].append(next_fen)
                    
                    if next_fen not in AR:
                        AR[next_fen] = create_AR_entry(evaluate_position(board), None, move)
                        evaluated_list.append(next_fen)
                        if ((len(evaluated_list)) % 100000 == 0):
                            print(f"Evaluated: {len(evaluated_list)}")
                        
                    board.pop()
                    
                    #for child in AR[fen]['children']:
                    next_eval = AR[next_fen]['result']
                    if next_eval is not None:
                        if (-next_eval > best_case):
                            best_case = max(best_case, -next_eval)
                            best_child = next_fen
                        
                        #worst_case = min(worst_case, -next_eval)
                    else:
                        nones_present = True
                
                
                
                if nones_present:
                    if best_case > 0:
                        AR[fen]['result'] = update_best_case(best_case)
                        AR[fen]['best_child'] = best_child
                        changed = True
                else:
                    # Aktualizace hodnocení podle nejlepšího a nejhoršího scénáře
                    #if worst_case == -1000:
                        # Pokud všechny tahy vedou k matu, hráč na tahu může být matován v k tazích
                    #    AR[fen] = -1000 + k
                    #    changed = True
                    #elif best_case <= 0:
                        # Pokud nejlepší scénář není lepší než remíza, znamená to remízu nebo prohru
                    #    AR[fen] = max(best_case, 0)  # Zabráníme nastavení hodnoty méně než 0, pokud je remíza možná
                    #    changed = True
                    #elif best_case == 1000:
                        # Pokud existuje alespoň jeden tah, který vede k matu protihráče, hráč na tahu může vynutit mat v k tazích
                    #    AR[fen] = 1000 - k
                    #    changed = True
                    AR[fen]['result'] = update_best_case(best_case)
                    AR[fen]['best_child'] = best_child
                    changed = True
                    
             ###   print(f"Position = {fen}, results = {best_case} {nones_present} => {AR[fen]['result']}") 
                if (fen == "8/8/3R4/8/8/5K2/8/4k3 b - -" or fen == "8/8/3R4/8/8/5K2/8/5k2 w - -"):
                    print("^^^^^^^^")

            
            # remove here
            #break
            
            #if not changed:
                #break  # Pokud nedošlo k žádné změně, ukončíme smyčku

        #if not changed:
            #break  # Ukončíme hlavní smyčku, pokud nedošlo ke změně v poslední iteraci
    


def print_draw_positions(AR):
    """
    Vytiskne všechny remízové pozice (hodnota 0) zaznamenané v slovníku AR.
    """
    print("Remízové pozice:")
    for fen, value in AR.items():
        if True or (value > 990 and value < 1000):
            print(f"FEN>: {fen}, Hodnota: {value}","\n",chess.Board(fen),"<\n")

def find_path_to_end(AR, fen):
    if AR[fen]['result'] is None:
        print(f"Unfortunately, there is no path that is known to be the best")
    
    fen_i = fen
    print(chess.Board(fen_i),"\n<")
    path = fen
    while AR[fen_i]['best_child'] is not None:
        fen_i = AR[fen_i]['best_child']
        print(chess.Board(fen_i),"\n<")
        
        path = path + ", " + fen_i
    
    print(f"Path is: {path}")
    
 
            
def main():

    initial_fen = "1k6/5P2/2K5/8/8/8/8/8 w - - 0 1"
    initial_fen_original = "8/8/8/8/3Q4/5K2/8/4k3 w - - 0 1"
    initial_fen_mate_in_one_aka_one_ply = "3r1k2/5r1p/5Q1K/2p3p1/1p4P1/8/8/8 w - - 2 56"
    initial_fen_mate_in_two_aka_three_plies = "r5k1/2r3p1/pb6/1p2P1N1/3PbB1P/3pP3/PP1K1P2/3R2R1 b - - 4 28"
    initial_fen_mated_in_two_plies = "r5k1/2r3p1/p7/bp2P1N1/3PbB1P/3pP3/PP1K1P2/3R2R1 w - - 5 29"
    
    mate_in_two_aka_three_plies_simple = "8/8/8/8/3R4/5K2/8/4k3 w - - 0 1"
    mated_in_one_aka_two_plies_simple = "8/8/3R4/8/8/5K2/8/4k3 b - - 1 1"
    mate_in_one_aka_one_ply_simple = "8/8/3R4/8/8/5K2/8/5k2 w - - 2 2"

    initial_fen = mate_in_two_aka_three_plies_simple
    
    
    initial_fen = "1k6/5P2/2K5/8/8/8/8/8 w - - 0 1"
    initial_fen = "1k6/8/2K5/8/8/8/8/8 w - - 0 1"
    initial_fen = "8/8/8/8/8/7N/1k5K/6B1 w - - 0 1"
    initial_fen = "7K/8/k1P5/7p/8/8/8/8 w - - 0 1"
   
    simplified_fen = simplify_fen_string(initial_fen)
    
    board = chess.Board(initial_fen)
    AR = {simplified_fen: {"result": None, "last_move": None, "children": None, "best_child": None}}  # Inicializace AR s počáteční pozicí
    
    update_AR_for_mate_in_k(board, AR, simplified_fen, max_k=58)  # Aktualizace AR
    
    #print_draw_positions(AR)
    print(f"AR for initial fen is = {AR[simplified_fen]}")
    find_path_to_end(AR, simplified_fen)


main()

核心Bug排查方向 #

1. 评估值语义与反转逻辑混淆 #

• 当前evaluate_position中，将死返回-1000，代表"对手被将死"，但后续代码通过-next_eval反转值，导致胜方/负方的视角完全混乱：比如子节点是将死局面（-1000），反转后得到1000，再经过update_best_case减1变成999，这和实际"mate in 1"的计数逻辑完全不符。
• 没有正确处理负方的拖延策略：负方会选择让将死回合数最多的走法，但当前代码只取max(best_case, -next_eval)，忽略了负方视角下需要选择对胜方最不利的路径。

2. update_best_case计数逻辑错误 #

• 函数中直接对best_case做加减操作，完全脱离了迭代轮次k的实际意义。正确逻辑应该是：如果子节点是"mate in m"，当前节点的胜方回合应该是"mate in m+1"，而不是基于子节点值递减。

3. 迭代终止条件失效 #

• 代码中注释掉了changed变量的判断逻辑，导致即使没有新局面被评估，仍会继续迭代，引入错误的计数；同时初始局面结果一出来就直接return，可能错过更优路径的更新。

4. FEN简化丢失关键信息 #

• simplify_fen_string只保留前4部分，忽略了50步规则和吃过路兵信息，这会导致错误地将可判和的局面当作可将死局面处理，从而增加不必要的回合数。

修复建议 #

1. 修正评估值语义：

   • 将evaluate_position中，当前玩家将死对手返回1000，被对手将死返回-1000，反转后逻辑更清晰；用1000 - N表示"当前玩家能在N步内将死对手"，-1000 + N表示"当前玩家会在N步内被将死"。

2. 重构计数逻辑：

   • 去掉update_best_case，直接基于迭代轮次k和子节点值计算：如果子节点是1000 - m，当前节点胜方回合值为1000 - (m+1)；负方回合则选择最大的-next_eval（即拖延最久的路径）。

3. 恢复迭代终止条件：

   • 取消changed判断的注释，当一轮迭代中没有任何局面结果更新时，终止循环，避免无效迭代。

4. 完善FEN处理：

   • 保留FEN中的50步计数和吃过路兵信息，避免忽略判和规则导致的错误计算。

内容的提问来源于stack exchange，提问作者user22758952