mate_override.py

1"""Exact legal AND/OR proof of the side-to-move's mate within at most 3 plies.
2
3Not an evaluation engine: incomplete searches return unknown, never a move.
4Iterative depths and lexical UCI order choose shortest mate then a stable tie.
5"""
6import time, math
7import chess
8
9class BudgetExceeded(Exception):
10    pass
11
12def forced_mate(board, *, adjudicate, max_plies=3, max_nodes=50000, seconds=1.0,
13                clock=time.monotonic):
14    if type(max_plies) is not int or not 1 <= max_plies <= 3:
15        raise ValueError('mate depth must be 1, 2, or 3 PLIES')
16    if type(max_nodes) is not int or max_nodes < 1 or not math.isfinite(seconds) or seconds <= 0:
17        raise ValueError('positive tactical budgets required')
18    if type(board) is not chess.Board or board.chess960 or not board.is_valid():
19        raise ValueError('valid standard chess board required')
20    work=board.copy(stack=True)
21    attacker=work.turn
22    started=clock(); deadline=started+seconds
23    nodes=0; completed=0; deepest=0
24    def guard():
25        if clock() >= deadline: raise BudgetExceeded('deadline')
26    def visit(remaining, ply):
27        nonlocal nodes,deepest
28        guard()
29        if nodes >= max_nodes: raise BudgetExceeded('node_budget')
30        nodes+=1; deepest=max(deepest,ply)
31        # Same immediate-claim policy as the game, including history-sensitive
32        # repetition and claim-by-declaring-a-move. Draws refute a mate proof.
33        end=adjudicate(work)
34        guard()
35        if end:
36            if end[1]=='checkmate' and work.turn != attacker:
37                return {'kind':'checkmate','fen':work.fen(),'mate_plies':0}
38            return None
39        if remaining==0: return None
40        moves=sorted(work.legal_moves,key=lambda m:m.uci())
41        guard()
42        attacking=work.turn==attacker
43        branches=[]
44        for move in moves:
45            guard(); work.push(move)
46            try: child=visit(remaining-1,ply+1)
47            finally: work.pop()
48            guard()
49            if attacking and child is not None:
50                return {'kind':'attacker_choice','fen':work.fen(),
51                    'mate_plies':1+child['mate_plies'],
52                    'branches':[{'move':move.uci(),'child':child}]}
53            if not attacking:
54                if child is None: return None
55                branches.append({'move':move.uci(),'child':child})
56        if not attacking and branches:
57            return {'kind':'all_defenses','fen':work.fen(),
58                'mate_plies':1+max(b['child']['mate_plies'] for b in branches),
59                'branches':branches}
60        return None
61    proof=None; status='no_forced_mate'; reason='exhausted_depth_bound'
62    try:
63        for depth in range(1,max_plies+1):
64            proof=visit(depth,0)
65            guard(); completed=depth
66            if proof is not None:
67                status='proven'; reason='forced_checkmate'; break
68    except BudgetExceeded as exc:
69        proof=None; status='unknown'; reason=str(exc)
70    return {'status':status,'reason':reason,'max_plies':max_plies,
71        'completed_depth_plies':completed,'deepest_visited_ply':deepest,
72        'mate_plies':proof['mate_plies'] if proof else None,
73        'move':proof['branches'][0]['move'] if proof and proof.get('branches') else None,
74        'nodes':nodes,'node_budget':max_nodes,'seconds':clock()-started,
75        'time_budget_seconds':seconds,'proof':proof}
76