API tools faq
paste
Advertisement
max2201111

excellent

max2201111
Apr 9th, 2025
433
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 15.28 KB | Science | 0 0
raw download clone embed print report
  1. MATE_SCORE = 10000
  2. INF = 10000000
  3.  
  4. # Parse FEN string into board matrix and side to move
  5. def parse_fen(fen_str):
  6.     parts = fen_str.split()
  7.     rows = parts[0].split('/')
  8.     side_to_move = parts[1]
  9.     board = []
  10.     for rank in rows:
  11.         row = []
  12.         for ch in rank:
  13.             if ch.isdigit():
  14.                 row.extend(['.'] * int(ch))
  15.             else:
  16.                 row.append(ch)
  17.         board.append(row)
  18.     # Ensure 8 columns per rank
  19.     for i in range(len(board)):
  20.         if len(board[i]) < 8:
  21.             board[i].extend(['.'] * (8 - len(board[i])))
  22.     # Ensure 8 ranks
  23.     while len(board) < 8:
  24.         board.append(['.'] * 8)
  25.     return board, side_to_move
  26.  
  27. # Directions for moves of each piece type
  28. king_dirs   = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
  29. rook_dirs   = [(-1,0), (1,0), (0,-1), (0,1)]
  30. bishop_dirs = [(-1,-1), (-1,1), (1,-1), (1,1)]
  31. knight_moves = [(-2,-1), (-2,1), (-1,-2), (-1,2), (1,-2), (1,2), (2,-1), (2,1)]
  32.  
  33. # Generate all pseudo-legal moves (not filtering self-check yet) for the given side
  34. def generate_pseudo_legal_moves(board, side):
  35.     moves = []
  36.     # Find opponent king position (to avoid moving king adjacent to it)
  37.     opp_king_char = 'K' if side == 'b' else 'k'
  38.     opp_king_pos = None
  39.     for r in range(8):
  40.         for c in range(8):
  41.             if board[r][c] == opp_king_char:
  42.                 opp_king_pos = (r, c)
  43.                 break
  44.         if opp_king_pos: break
  45.     for r in range(8):
  46.         for c in range(8):
  47.             piece = board[r][c]
  48.             if piece == '.':
  49.                 continue
  50.             # Skip pieces of the opposite side
  51.             if side == 'w' and not piece.isupper():
  52.                 continue
  53.             if side == 'b' and not piece.islower():
  54.                 continue
  55.             p = piece.lower()
  56.             if p == 'k':  # King moves
  57.                 for dr, dc in king_dirs:
  58.                     nr, nc = r + dr, c + dc
  59.                     if 0 <= nr < 8 and 0 <= nc < 8:
  60.                         dest = board[nr][nc]
  61.                         # Cannot move onto own piece
  62.                         if side == 'w' and dest.isupper():
  63.                             continue
  64.                         if side == 'b' and dest.islower():
  65.                             continue
  66.                         # Cannot move adjacent to opponent king
  67.                         if opp_king_pos and abs(opp_king_pos[0] - nr) <= 1 and abs(opp_king_pos[1] - nc) <= 1:
  68.                             continue
  69.                         moves.append((r, c, nr, nc))
  70.             elif p in ('r', 'b', 'q'):  # Rook, Bishop, Queen moves (sliding pieces)
  71.                 dirs = []
  72.                 if p == 'r':
  73.                     dirs = rook_dirs
  74.                 elif p == 'b':
  75.                     dirs = bishop_dirs
  76.                 elif p == 'q':
  77.                     dirs = rook_dirs + bishop_dirs
  78.                 for dr, dc in dirs:
  79.                     nr, nc = r + dr, c + dc
  80.                     while 0 <= nr < 8 and 0 <= nc < 8:
  81.                         dest = board[nr][nc]
  82.                         if side == 'w' and dest.isupper():
  83.                             break
  84.                         if side == 'b' and dest.islower():
  85.                             break
  86.                         # Stop if hitting any king (cannot capture king, treat as block)
  87.                         if dest.lower() == 'k':
  88.                             break
  89.                         moves.append((r, c, nr, nc))
  90.                         # Stop if we captured an opponent piece (can't go further)
  91.                         if dest != '.':
  92.                             break
  93.                         nr += dr
  94.                         nc += dc
  95.             elif p == 'n':  # Knight moves
  96.                 for dr, dc in knight_moves:
  97.                     nr, nc = r + dr, c + dc
  98.                     if 0 <= nr < 8 and 0 <= nc < 8:
  99.                         dest = board[nr][nc]
  100.                         if side == 'w' and dest.isupper():
  101.                             continue
  102.                         if side == 'b' and dest.islower():
  103.                             continue
  104.                         if dest.lower() == 'k':  # cannot capture king
  105.                             continue
  106.                         moves.append((r, c, nr, nc))
  107.             elif p == 'p':  # Pawn moves (just in case, though default FEN has none)
  108.                 if side == 'w':
  109.                     # one step forward
  110.                     if r-1 >= 0 and board[r-1][c] == '.':
  111.                         moves.append((r, c, r-1, c))
  112.                         # two steps from starting rank 2
  113.                         if r == 6 and board[5][c] == '.':
  114.                             moves.append((r, c, 4, c))
  115.                     # captures
  116.                     for dc in (-1, 1):
  117.                         nr, nc = r-1, c+dc
  118.                         if 0 <= nr < 8 and 0 <= nc < 8:
  119.                             if board[nr][nc] != '.' and board[nr][nc].islower():
  120.                                 if board[nr][nc].lower() != 'k':  # not capturing king
  121.                                     moves.append((r, c, nr, nc))
  122.                 else:  # side == 'b'
  123.                     if r+1 < 8 and board[r+1][c] == '.':
  124.                         moves.append((r, c, r+1, c))
  125.                         if r == 1 and board[2][c] == '.':
  126.                             moves.append((r, c, 3, c))
  127.                     for dc in (-1, 1):
  128.                         nr, nc = r+1, c+dc
  129.                         if 0 <= nr < 8 and 0 <= nc < 8:
  130.                             if board[nr][nc] != '.' and board[nr][nc].isupper():
  131.                                 if board[nr][nc].lower() != 'k':
  132.                                     moves.append((r, c, nr, nc))
  133.     return moves
  134.  
  135. # Check if the king of the given side is in check
  136. def is_in_check(board, side):
  137.     king_char = 'K' if side == 'w' else 'k'
  138.     kr = kc = None
  139.     # Find this side's king
  140.     for r in range(8):
  141.         for c in range(8):
  142.             if board[r][c] == king_char:
  143.                 kr, kc = r, c
  144.                 break
  145.         if kr is not None:
  146.             break
  147.     if kr is None:
  148.         # King not found (should not happen in normal play)
  149.         return True
  150.     opp_side = 'b' if side == 'w' else 'w'
  151.     # Opponent king (to check adjacency threat)
  152.     opp_king_char = 'K' if opp_side == 'w' else 'k'
  153.     opp_kr = opp_kc = None
  154.     for r in range(8):
  155.         for c in range(8):
  156.             if board[r][c] == opp_king_char:
  157.                 opp_kr, opp_kc = r, c
  158.                 break
  159.         if opp_kr is not None:
  160.             break
  161.     if opp_kr is not None:
  162.         if abs(opp_kr - kr) <= 1 and abs(opp_kc - kc) <= 1:
  163.             return True  # adjacent enemy king (illegal position)
  164.     # Knights
  165.     for dr, dc in knight_moves:
  166.         rr, cc = kr+dr, kc+dc
  167.         if 0 <= rr < 8 and 0 <= cc < 8:
  168.             piece = board[rr][cc]
  169.             if piece.lower() == 'n':
  170.                 # If an opponent knight is at (rr,cc)
  171.                 if opp_side == 'w' and piece.isupper():
  172.                     return True
  173.                 if opp_side == 'b' and piece.islower():
  174.                     return True
  175.     # Pawns
  176.     if opp_side == 'w':
  177.         # White pawn attacks downwards (from its perspective)
  178.         attack_deltas = [(kr+1, kc-1), (kr+1, kc+1)]
  179.         for (pr, pc) in attack_deltas:
  180.             if 0 <= pr < 8 and 0 <= pc < 8 and board[pr][pc] == 'P':
  181.                 return True
  182.     else:
  183.         # Black pawn attacks upwards
  184.         attack_deltas = [(kr-1, kc-1), (kr-1, kc+1)]
  185.         for (pr, pc) in attack_deltas:
  186.             if 0 <= pr < 8 and 0 <= pc < 8 and board[pr][pc] == 'p':
  187.                 return True
  188.     # Rooks, bishops, queens
  189.     directions = rook_dirs + bishop_dirs
  190.     for dr, dc in directions:
  191.         rr, cc = kr + dr, kc + dc
  192.         while 0 <= rr < 8 and 0 <= cc < 8:
  193.             piece = board[rr][cc]
  194.             if piece != '.':
  195.                 if opp_side == 'w' and piece.isupper():
  196.                     # opponent (white) piece
  197.                     if dr == 0 or dc == 0:  # along rank/file
  198.                         if piece.lower() in ('r', 'q'):
  199.                             return True
  200.                     else:  # diagonal
  201.                         if piece.lower() in ('b', 'q'):
  202.                             return True
  203.                 if opp_side == 'b' and piece.islower():
  204.                     if dr == 0 or dc == 0:
  205.                         if piece.lower() in ('r', 'q'):
  206.                             return True
  207.                     else:
  208.                         if piece.lower() in ('b', 'q'):
  209.                             return True
  210.                 break  # stop at first piece encountered
  211.             rr += dr
  212.             cc += dc
  213.     return False
  214.  
  215. # Move ordering priority function (helps the search prune faster)
  216. def move_priority(board, move, side):
  217.     fr, fc, tr, tc = move
  218.     piece = board[fr][fc]
  219.     target = board[tr][tc]
  220.     if side == 'b':
  221.         # Black (the mating side in default position) prioritizes moves:
  222.         # 1. Avoid moves that place the rook next to the enemy king unprotected (risk immediate capture)
  223.         if piece.lower() == 'r':
  224.             # Check if rook's destination is adjacent to white king
  225.             wk_r = wk_c = None
  226.             for r in range(8):
  227.                 for c in range(8):
  228.                     if board[r][c] == 'K':
  229.                         wk_r, wk_c = r, c
  230.                         break
  231.                 if wk_r is not None:
  232.                     break
  233.             if wk_r is not None and abs(wk_r - tr) <= 1 and abs(wk_c - tc) <= 1:
  234.                 # Rook moves adjacent to white king
  235.                 # Check if black's own king is *not* also adjacent to that square (meaning rook would be unprotected)
  236.                 bk_r = bk_c = None
  237.                 for r in range(8):
  238.                     for c in range(8):
  239.                         if board[r][c] == 'k':
  240.                             bk_r, bk_c = r, c
  241.                             break
  242.                     if bk_r is not None:
  243.                         break
  244.                 if not (bk_r is not None and abs(bk_r - tr) <= 1 and abs(bk_c - tc) <= 1):
  245.                     return 5  # low priority (likely bad move)
  246.         # 2. Capturing any opponent piece (if any existed) is good
  247.         if target != '.' and target.isupper():
  248.             return 0
  249.         # 3. Moves by high-value pieces (rook/queen) first
  250.         if piece.lower() in ('r', 'q'):
  251.             return 1
  252.         # 4. King moves last
  253.         if piece.lower() == 'k':
  254.             return 3
  255.         return 2
  256.     else:
  257.         # White (defending side) prioritizes moves:
  258.         # 1. Capture the opponent's rook if possible (to force draw)
  259.         if target != '.' and target.islower():
  260.             if target.lower() in ('r', 'q'):
  261.                 return 0
  262.             else:
  263.                 return 1
  264.         # 2. Other moves considered equal
  265.         return 2
  266.  
  267. # Cache for transposition table: maps (state, depth) -> (score, best_line)
  268. cache = {}
  269.  
  270. # Negamax search with alpha-beta pruning and iterative deepening
  271. def negamax(board, side, depth, alpha, beta, visited, ply):
  272.     state_key = (side, tuple(tuple(row) for row in board))
  273.     # Transposition table lookup
  274.     if (state_key, depth) in cache:
  275.         return cache[(state_key, depth)]
  276.     # Prevent cycles (threefold repetition or perpetual chasing)
  277.     if state_key in visited:
  278.         return 0, []
  279.     if depth == 0:
  280.         # Horizon reached, no static eval -> assume draw (0)
  281.         return 0, []
  282.     # Generate moves and filter legal moves (those not leaving own king in check)
  283.     moves = generate_pseudo_legal_moves(board, side)
  284.     legal_moves = []
  285.     for move in moves:
  286.         fr, fc, tr, tc = move
  287.         piece = board[fr][fc]
  288.         captured = board[tr][tc]
  289.         # Make the move
  290.         board[fr][fc] = '.'
  291.         board[tr][tc] = piece
  292.         if not is_in_check(board, side):
  293.             legal_moves.append(move)
  294.         # Undo move
  295.         board[fr][fc] = piece
  296.         board[tr][tc] = captured
  297.     if not legal_moves:
  298.         # No moves: check terminal condition
  299.         if is_in_check(board, side):
  300.             # Checkmate: current side has no moves and is in check -> losing
  301.             return -(MATE_SCORE - ply), []
  302.         else:
  303.             # Stalemate
  304.             return 0, []
  305.     # Order moves to improve pruning
  306.     legal_moves.sort(key=lambda m: move_priority(board, m, side))
  307.     visited.add(state_key)
  308.     best_score = -INF
  309.     best_line = []
  310.     next_side = 'w' if side == 'b' else 'b'
  311.     for move in legal_moves:
  312.         fr, fc, tr, tc = move
  313.         piece = board[fr][fc]
  314.         captured = board[tr][tc]
  315.         # Apply move
  316.         board[fr][fc] = '.'
  317.         board[tr][tc] = piece
  318.         score, line = negamax(board, next_side, depth-1, -beta, -alpha, visited, ply+1)
  319.         score = -score
  320.         # Undo move
  321.         board[fr][fc] = piece
  322.         board[tr][tc] = captured
  323.         if score > best_score:
  324.             best_score = score
  325.             best_line = [move] + line
  326.         alpha = max(alpha, best_score)
  327.         if alpha >= beta:
  328.             # Alpha-beta cutoff
  329.             break
  330.     visited.remove(state_key)
  331.     # Distance-to-mate scoring: ensure shorter mate is better
  332.     cache[(state_key, depth)] = (best_score, best_line.copy())
  333.     return best_score, best_line
  334.  
  335. # Print board in ASCII
  336. def print_board(board):
  337.     for r in range(8):
  338.         print(" ".join(board[r]))
  339.  
  340. # Main execution
  341. if __name__ == "__main__":
  342.     # Starting FEN: K+R vs K endgame position
  343.     start_fen = "8/1K2k3/r7/8/8/8/8/8 b - - 0 1"
  344.     board, side = parse_fen(start_fen)
  345.     final_score = None
  346.     final_line = []
  347.     # Iterative deepening search
  348.     for depth in range(1, 51):
  349.         score, line = negamax(board, side, depth, -INF, INF, set(), 0)
  350.         final_score = score
  351.         final_line = line
  352.         # Prepare score display
  353.         if abs(score) >= MATE_SCORE - 100:
  354.             # If score indicates a checkmate sequence
  355.             mate_dist = MATE_SCORE - abs(score)
  356.             if score > 0:
  357.                 score_str = f"Mate in {mate_dist} half-moves"
  358.             elif score < 0:
  359.                 score_str = f"-Mate in {mate_dist} half-moves"
  360.             else:
  361.                 score_str = "Mate"
  362.         else:
  363.             score_str = str(score)
  364.         # Prepare principal variation moves display
  365.         pv_moves = []
  366.         for (fr, fc, tr, tc) in line:
  367.             pv_moves.append(chr(ord('a') + fc) + str(8 - fr) + chr(ord('a') + tc) + str(8 - tr))
  368.         print(f"Depth {depth}: Score = {score_str}, PV = {' '.join(pv_moves)}")
  369.         if abs(score) > 9000 or score == MATE_SCORE or score == -MATE_SCORE:
  370.             # Stop when a checkmate is found
  371.             break
  372.     # Execute the best sequence of moves found
  373.     print("\nExecuting best sequence:")
  374.     print_board(board)
  375.     print(f"Side to move: {'White' if side == 'w' else 'Black'}")
  376.     current_side = side
  377.     for (fr, fc, tr, tc) in final_line:
  378.         piece = board[fr][fc]
  379.         board[fr][fc] = '.'
  380.         board[tr][tc] = piece
  381.         current_side = 'w' if current_side == 'b' else 'b'
  382.         print()  # blank line between moves
  383.         print_board(board)
  384.         print(f"Side to move: {'White' if current_side == 'w' else 'Black'}")
  385.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!