import subprocess import shogi import random import time import os import sys import copy from collections import defaultdict # ========================================== # Configuration # ========================================== # PLEASE CHANGE THE ENGINE PATH TO YOUR ENVIRONMENT ENGINE_PATH = r"C:\Users\takas\YaneuraOu\YaneuraOu_NNUE_halfkp_256x2_32_32-V900Git_AVX2.exe" TARGET_STEPS = 13 # Piece Count Limits PIECE_LIMITS = { shogi.ROOK: 2, shogi.BISHOP: 2, shogi.GOLD: 4, shogi.SILVER: 4, shogi.KNIGHT: 4, shogi.LANCE: 4, shogi.PAWN: 18 } PROMOTE_MAP = { shogi.PROM_ROOK: shogi.ROOK, shogi.PROM_BISHOP: shogi.BISHOP, shogi.PROM_SILVER: shogi.SILVER, shogi.PROM_KNIGHT: shogi.KNIGHT, shogi.PROM_LANCE: shogi.LANCE, shogi.PROM_PAWN: shogi.PAWN } RAW_TO_PROMOTE = { shogi.ROOK: shogi.PROM_ROOK, shogi.BISHOP: shogi.PROM_BISHOP, shogi.SILVER: shogi.PROM_SILVER, shogi.KNIGHT: shogi.PROM_KNIGHT, shogi.LANCE: shogi.PROM_LANCE, shogi.PAWN: shogi.PROM_PAWN } PROMOTE_TO_RAW = {v: k for k, v in RAW_TO_PROMOTE.items()} class USISolver: def __init__(self, engine_path): self.engine_path = engine_path self.process = None self.boot_engine() def boot_engine(self): self.close() if not os.path.exists(self.engine_path): print(f"[Error] Engine not found: {self.engine_path}") sys.exit(1) try: self.process = subprocess.Popen( self.engine_path, cwd=os.path.dirname(self.engine_path), stdin=subprocess.PIPE, stdout=subprocess.PIPE, stderr=subprocess.PIPE, text=True, encoding='utf-8', errors='replace', bufsize=1 ) except: sys.exit(1) try: self._send_raw("usi") self._wait_for("usiok", timeout=15) self._send_raw("setoption name MultiPV value 1") self._send_raw("isready") self._wait_for("readyok", timeout=15) self._send_raw("usinewgame") except: self.close() def _send_raw(self, command): if self.process: try: self.process.stdin.write(command + "\n") self.process.stdin.flush() except: pass def _read_line(self): try: if self.process: return self.process.stdout.readline() except: pass return None def _wait_for(self, keyword, timeout=10): start = time.time() while True: line = self._read_line() if not line: break if keyword in line: return True if time.time() - start > timeout: return False return False def close(self): if self.process: try: self.process.kill() except: pass self.process = None def solve(self, board, nodes=10000): if self.process is None or self.process.poll() is not None: self.boot_engine() return False, "Reboot", 0 try: self._send_raw(f"position sfen {board.sfen()}") self._send_raw(f"go nodes {nodes}") except: self.boot_engine() return False, "Error", 0 start_time = time.time() pv_moves = [] mate_found = False mate_steps = 0 while True: line = self._read_line() if not line: self.boot_engine() return False, "Lost", 0 if "mate " in line and ("score" in line or "info" in line): if "mate -" not in line: mate_found = True try: parts = line.split() if "pv" in parts: idx = parts.index("pv") pv_moves = parts[idx+1:] mate_steps = len(pv_moves) except: pass if "bestmove" in line: parts = line.strip().split() if len(parts) > 1: best_move = parts[1] if best_move == "resign": return False, "NoMate", 0 if not mate_found: return False, "NoMate", 0 if mate_steps == 0: mate_steps = 1 moves_str = " ".join(pv_moves) if pv_moves else best_move return True, moves_str, mate_steps return False, "Unknown", 0 if time.time() - start_time > 10.0: self.boot_engine() return False, "Timeout", 0 return False, "Unknown", 0 class FreshSolver(USISolver): def __init__(self, engine_path): super().__init__(engine_path) def check_alt_moves(self, board, correct_move_usi): try: legal_moves = list(board.generate_legal_moves()) alt_moves = [m.usi() for m in legal_moves if m.usi() != correct_move_usi] if not alt_moves: return False, None search_moves_str = " ".join(alt_moves) self._send_raw("usinewgame") self._send_raw(f"position sfen {board.sfen()}") self._send_raw(f"go nodes 2000000 searchmoves {search_moves_str}") except: return False, None start_time = time.time() is_mate = False while True: line = self._read_line() if not line: break if "mate " in line and ("score" in line or "info" in line): if "mate -" not in line: is_mate = True if "bestmove" in line: parts = line.split() if len(parts) > 1: best = parts[1] if best == "resign": return False, None if is_mate: return True, best return False, None if time.time() - start_time > 15.0: return False, None return False, None def solve_strictly(self, board, estimated_steps=11): try: total_nodes = 20000000 + (max(0, estimated_steps - 11) * 2000000) self._send_raw("usinewgame") self._send_raw(f"position sfen {board.sfen()}") self._send_raw(f"setoption name MultiPV value 1") self._send_raw(f"go nodes {total_nodes}") except: return False, "Error", 0 start_time = time.time() pv1_moves = [] mate_found = False while True: line = self._read_line() if not line: break if "mate " in line and ("score" in line or "info" in line): if "mate -" not in line: mate_found = True try: parts = line.split() if "pv" in parts: idx = parts.index("pv") pv_moves = parts[idx+1:] if pv_moves: pv1_moves = pv_moves except: pass if "bestmove" in line: if not mate_found: return False, "NoMate", 0 if pv1_moves: return True, " ".join(pv1_moves), len(pv1_moves) return False, "NoMate", 0 if time.time() - start_time > 90.0: return False, "Timeout", 0 return False, "Unknown", 0 # ========================================================================= # Generator: Evolution with Sacrifice Focus (Standard Rules) # ========================================================================= class DirectedEvolutionGenerator: def __init__(self): print(f"\n=== Evolutionary Tsume Shogi Generator (Target: {TARGET_STEPS} steps, Sacrifice Focus, Standard Rules) ===") print("* Criteria: Length > Sacrifice Count > Quality (Limited moves)") print("* Standard rules (Opponent has hand), aiming for puzzle-like sacrifice sequences.") self.ev_solver = USISolver(ENGINE_PATH) self.retry_count = 0 def run(self): while True: self.retry_count += 1 print(f"\n--- Challenge #{self.retry_count} ---") # 1. Create Random Seed seed_board = self._create_random_seed() solve_board = self._create_solve_board(seed_board) # 2. Simple Check is_mate, moves_str, steps = self.ev_solver.solve(solve_board, nodes=5000) if not is_mate: continue print(f" Seed found ({steps} steps)") # 3. Strict Inspection print(" [Strict Inspection...]", end="", flush=True) checker = FreshSolver(ENGINE_PATH) is_valid, _, _ = checker.solve_strictly(solve_board, steps) checker.close() if not is_valid: print(" -> False positive (Discarded)") continue print(" -> Passed! Starting Evolution") current_best_board = seed_board current_max_steps = steps # Get Sacrifice Count (sac) as well current_score, current_sac = self._calculate_sacrifice_score(solve_board, moves_str) # 4. Evolution Loop for generation in range(1, 1501): # Survival Log if generation % 100 == 0: print(f" [Gen {generation}] Current: {current_max_steps} steps (Sacs:{current_sac} Score:{current_score})", end="\r") child_board = self._mutate_with_hand(current_best_board) if not self._is_safe_board(child_board): continue solve_child = self._create_solve_board(child_board) is_mate, new_moves, new_steps = self.ev_solver.solve(solve_child, nodes=20000) if is_mate: if self._is_valid_tsume_simple(solve_child, new_moves): # Dual Solution Check (Required) if not self._is_yozume_free_fast(solve_child, new_moves): continue # Calculation with Sacrifice Focus new_score, new_sac = self._calculate_sacrifice_score(solve_child, new_moves) if new_score == -9999: continue update = False # === [PRIORITY LOGIC] === # 1. Length Increased: Adopt immediately if new_steps > current_max_steps: print(f"\n [Growth] {current_max_steps} -> {new_steps} steps (Sacs:{new_sac} Score:{new_score}) (Gen:{generation})") update = True # 2. Same Length, More Sacrifices: Adopt elif new_steps == current_max_steps and new_sac > current_sac: print(f"\n [Intensify] Steps maintained ({new_steps}), Sacrifices UP {current_sac}->{new_sac} (Gen:{generation})") update = True # 3. Same Length/Sacs, Better Quality: Adopt elif new_steps == current_max_steps and new_sac == current_sac and new_score > current_score: if new_score > current_score + 10: print(f"\n [Refine] Quality UP Score:{current_score}->{new_score} (Gen:{generation})") update = True if update: current_best_board = child_board current_max_steps = new_steps current_score = new_score current_sac = new_sac if new_steps >= TARGET_STEPS and update: if self._finalize_check(current_best_board, current_max_steps): return else: pass # ========================================================================= # New Evaluation: Highly rewards sacrifices (moving into attacked squares) # ========================================================================= def _calculate_sacrifice_score(self, board, moves_str): moves = moves_str.split() sim_board = copy.deepcopy(board) score = 0 sac_count = 0 try: for i, m_str in enumerate(moves): m = shogi.Move.from_usi(m_str) # --- Attacker's Turn (0, 2, 4...) --- if i % 2 == 0: dest = m.to_square # [Check] Is the destination attacked by the opponent (White)? # Moving into an attacked square = Sacrifice (Risk of capture) if sim_board.attackers(shogi.WHITE, dest): score += 50 # Huge Bonus: Sacrifices are great! sac_count += 1 # Small bonus for drops (fill space) if m.from_square is None: score += 5 # --- Defender's Turn (1, 3, 5...) --- else: # Standard logic: Fewer escape routes = Higher score legal_moves = list(sim_board.generate_legal_moves()) if len(legal_moves) == 1: score += 10 elif len(legal_moves) <= 3: score += 5 else: score -= 5 # Deduction for too many escape routes if not sim_board.is_legal(m): return -9999, 0 sim_board.push(m) except (ValueError, IndexError): return -9999, 0 return score, sac_count # ----------------------------------------------------------- # Helper Functions (Same as base) # ----------------------------------------------------------- def _is_yozume_free_fast(self, board, moves_str): moves = moves_str.split() if not moves: return False first_move_usi = moves[0] checker = FreshSolver(ENGINE_PATH) has_alt, _ = checker.check_alt_moves(board, first_move_usi) checker.close() return not has_alt def _finalize_check(self, board, estimated_steps): print(f"\n Target ({TARGET_STEPS} steps) Reached. Starting Final Check...") print(" Cleaning board for quality...", end=" ", flush=True) board = self._clean_board_pieces_strict(board, estimated_steps) print("Done") final_solve_board = self._create_solve_board(board) sfen_str = final_solve_board.sfen() clean_board = shogi.Board(sfen_str) print(" Booting verification engine...", end=" ") validator = FreshSolver(ENGINE_PATH) print("OK") print(f" Strict search ({estimated_steps} steps)...", end=" ") is_mate, moves, steps = validator.solve_strictly(final_solve_board, estimated_steps) validator.close() if not is_mate: print("Failed (No Mate)") return False if steps < TARGET_STEPS: print(f"Failed (Shortened to {steps} steps)") return False if not self._is_valid_tsume_strict_no_surplus(final_solve_board, moves): print("Failed (Surplus Pieces)") return False print("OK") print(" Exhaustive check for dual solutions (yozume)...", end=" ", flush=True) if not self._validate_yozume_tree(validator, final_solve_board, moves): print("Failed (Dual solution or Error)") return False print("Passed!") print("\n========================================") print(f" Final Completed Work ({steps} steps, Perfect, Sacrifice Focus)") print("========================================") print(f"Moves: {moves}") print("--- Board ---") print(clean_board) print(f"\nSFEN: {clean_board.sfen()}") print("\n[Verification Simulation]") self._simulate_game(final_solve_board, moves) return True def _clean_board_pieces_strict(self, board, org_steps): protected = self._get_protected_squares(board) checker = FreshSolver(ENGINE_PATH) current_hand = board.pieces_in_hand[shogi.BLACK] for pt in list(current_hand.keys()): while current_hand[pt] > 0: current_hand[pt] -= 1 solve_temp = self._create_solve_board(board) is_mate, moves, steps = checker.solve_strictly(solve_temp, org_steps) if (is_mate and steps >= org_steps and self._is_valid_tsume_strict_no_surplus(solve_temp, moves)): print("h", end="", flush=True) else: current_hand[pt] += 1 break for sq in reversed(range(81)): p = board.piece_at(sq) if p and p.color == shogi.WHITE: continue if sq in protected: continue if p and p.piece_type != shogi.KING: board.remove_piece_at(sq) solve_temp = self._create_solve_board(board) is_mate, moves, steps = checker.solve_strictly(solve_temp, org_steps) if (is_mate and steps >= org_steps and self._is_valid_tsume_strict_no_surplus(solve_temp, moves)): print(".", end="", flush=True) else: board.set_piece_at(sq, p) checker.close() return board def _validate_yozume_tree(self, validator, start_board, moves_str): moves = moves_str.split() temp_board = copy.deepcopy(start_board) try: for i, move_usi in enumerate(moves): if i % 2 == 0: has_alt, alt = validator.check_alt_moves(temp_board, move_usi) if has_alt: print(f"\n ! Dual solution found at move {i+1}: {alt}") return False print(".", end="", flush=True) m = shogi.Move.from_usi(move_usi) try: if not temp_board.is_legal(m): return False temp_board.push(m) except IndexError: return False except ValueError: return False return True def _simulate_game(self, board, moves_str): sim_board = copy.deepcopy(board) moves = moves_str.split() try: for i, m_str in enumerate(moves): m = shogi.Move.from_usi(m_str) print(f"{i+1}: {m_str} ... ", end="") if not sim_board.is_legal(m): print("[Illegal Move]") return sim_board.push(m) print("OK") print("Checkmate Confirmed.") except (ValueError, IndexError) as e: print(f"Error: {e}") def _create_solve_board(self, board): solve_board = copy.deepcopy(board) counts = self._get_total_piece_counts(board) for pt, total in PIECE_LIMITS.items(): remainder = total - counts[pt] if remainder > 0: solve_board.pieces_in_hand[shogi.WHITE][pt] = remainder return solve_board def _get_total_piece_counts(self, board): counts = defaultdict(int) for sq in range(81): p = board.piece_at(sq) if p and p.piece_type != shogi.KING: pt = p.piece_type if pt in PROMOTE_MAP: pt = PROMOTE_MAP[pt] counts[pt] += 1 for pt, num in board.pieces_in_hand[shogi.BLACK].items(): counts[pt] += num return counts def _get_piece_counts(self, board): return self._get_total_piece_counts(board) def _create_random_seed(self): board = shogi.Board() board.clear() s_king_pos = random.choice([72, 80]) board.set_piece_at(s_king_pos, shogi.Piece(shogi.KING, shogi.BLACK)) deflectors = [73, 64, 63] if s_king_pos == 72 else [79, 70, 71] for pos in deflectors: board.set_piece_at(pos, shogi.Piece(shogi.PROM_PAWN, shogi.BLACK)) kx = random.randint(2, 6) ky = random.randint(0, 2) k_pos = ky*9 + kx board.set_piece_at(k_pos, shogi.Piece(shogi.KING, shogi.WHITE)) near_squares = [] for f in range(kx-1, kx+2): for r in range(ky-1, ky+2): if 0 <= f <= 8 and 0 <= r <= 8: sq = r*9 + f if sq != k_pos: near_squares.append(sq) random.shuffle(near_squares) num_guards = random.randint(0, 2) def_pieces = [shogi.GOLD, shogi.SILVER, shogi.LANCE] for _ in range(num_guards): if not near_squares: break sq = near_squares.pop() available = [p for p in def_pieces if self._get_piece_counts(board)[p] < PIECE_LIMITS[p]] if available: pt = random.choice(available) board.set_piece_at(sq, shogi.Piece(pt, shogi.WHITE)) zone = self._get_extended_king_zone(board) valid_squares = [sq for sq in zone if board.piece_at(sq) is None and sq != s_king_pos and sq not in deflectors] random.shuffle(valid_squares) base_candidates = [ shogi.ROOK, shogi.BISHOP, shogi.GOLD, shogi.SILVER, shogi.KNIGHT, shogi.LANCE, shogi.PAWN ] atk_limit = random.randint(3, 5) current_atk = 0 while current_atk < atk_limit and valid_squares: if random.random() < 0.3: break current_counts = self._get_piece_counts(board) available_raw = [p for p in base_candidates if current_counts[p] < PIECE_LIMITS[p]] if not available_raw: break pos = valid_squares.pop() raw_pt = random.choice(available_raw) final_pt = raw_pt if raw_pt in RAW_TO_PROMOTE and random.random() < 0.5: final_pt = RAW_TO_PROMOTE[raw_pt] if final_pt == shogi.PAWN and self._is_nifu(board, pos%9, shogi.BLACK): continue board.set_piece_at(pos, shogi.Piece(final_pt, shogi.BLACK)) current_atk += 1 while current_atk < atk_limit: current_counts = self._get_piece_counts(board) available_raw = [p for p in base_candidates if current_counts[p] < PIECE_LIMITS[p]] if not available_raw: break pt = random.choice(available_raw) board.pieces_in_hand[shogi.BLACK][pt] += 1 current_atk += 1 return board def _get_extended_king_zone(self, board): k_sq = board.king_squares[shogi.WHITE] if k_sq is None: return [] kf = k_sq % 9; kr = k_sq // 9 zone = [] for f in range(kf - 3, kf + 4): for r in range(kr - 3, kr + 4): if 0 <= f <= 8 and 0 <= r <= 8: zone.append(r * 9 + f) return zone def _get_king_zone(self, board): k_sq = board.king_squares[shogi.WHITE] if k_sq is None: return [] kf = k_sq % 9; kr = k_sq // 9 zone = [] for f in range(kf - 2, kf + 3): for r in range(kr - 2, kr + 3): if 0 <= f <= 8 and 0 <= r <= 8: zone.append(r * 9 + f) return zone def _get_protected_squares(self, board): protected = [] if board.king_squares[shogi.WHITE] is not None: protected.append(board.king_squares[shogi.WHITE]) if board.king_squares[shogi.BLACK] is not None: k_sq = board.king_squares[shogi.BLACK] protected.append(k_sq) kf = k_sq % 9; kr = k_sq // 9 for f in range(kf-1, kf+2): for r in range(kr-1, kr+2): if 0 <= f <= 8 and 0 <= r <= 8: idx = r * 9 + f p = board.piece_at(idx) if p and p.color == shogi.BLACK: protected.append(idx) return protected def _mutate_with_hand(self, parent_board): board = copy.deepcopy(parent_board) protected = self._get_protected_squares(board) zone = self._get_king_zone(board) action = random.choice(["add", "remove", "move_board", "move_hand_to_board", "move_board_to_hand", "flip"]) base_types = [shogi.GOLD, shogi.SILVER, shogi.KNIGHT, shogi.PAWN, shogi.LANCE, shogi.ROOK, shogi.BISHOP] if action == "add": current_counts = self._get_piece_counts(board) available = [p for p in base_types if current_counts[p] < PIECE_LIMITS[p]] if available: pt = random.choice(available) if random.random() < 0.5: # To Hand board.pieces_in_hand[shogi.BLACK][pt] += 1 else: # To Board pos = random.choice(zone) if pos not in protected and board.piece_at(pos) is None: color = shogi.BLACK if random.random() < 0.4 else shogi.WHITE final_pt = pt if color == shogi.BLACK and pt in RAW_TO_PROMOTE and random.random() < 0.5: final_pt = RAW_TO_PROMOTE[pt] if not (final_pt == shogi.PAWN and self._is_nifu(board, pos%9, color)): board.set_piece_at(pos, shogi.Piece(final_pt, color)) elif action == "remove": targets = [] for pt, num in board.pieces_in_hand[shogi.BLACK].items(): if num > 0: targets.append(("hand", pt)) for sq in range(81): if board.piece_at(sq) and sq not in protected: targets.append(("board", sq)) if targets: t_type, val = random.choice(targets) if t_type == "hand": board.pieces_in_hand[shogi.BLACK][val] -= 1 else: board.remove_piece_at(val) elif action == "move_board": squares = [sq for sq in range(81) if board.piece_at(sq) and sq not in protected] if squares: src = random.choice(squares) p = board.piece_at(src) board.remove_piece_at(src) dst = random.choice(zone) if dst not in protected: if board.piece_at(dst) is None: if not (p.piece_type == shogi.PAWN and self._is_nifu(board, dst%9, p.color)): board.set_piece_at(dst, p) else: board.set_piece_at(src, p) else: board.set_piece_at(src, p) elif action == "move_hand_to_board": hand_pieces = [pt for pt, num in board.pieces_in_hand[shogi.BLACK].items() if num > 0] if hand_pieces: pt = random.choice(hand_pieces) dst = random.choice(zone) if dst not in protected and board.piece_at(dst) is None: if not (pt == shogi.PAWN and self._is_nifu(board, dst%9, shogi.BLACK)): board.pieces_in_hand[shogi.BLACK][pt] -= 1 board.set_piece_at(dst, shogi.Piece(pt, shogi.BLACK)) elif action == "move_board_to_hand": squares = [sq for sq in range(81) if board.piece_at(sq) and board.piece_at(sq).color == shogi.BLACK and sq not in protected] if squares: src = random.choice(squares) p = board.piece_at(src) pt = p.piece_type if pt in PROMOTE_MAP: pt = PROMOTE_MAP[pt] board.remove_piece_at(src) board.pieces_in_hand[shogi.BLACK][pt] += 1 elif action == "flip": squares = [sq for sq in range(81) if board.piece_at(sq) and sq not in protected] if squares: sq = random.choice(squares) p = board.piece_at(sq) pt = p.piece_type new_pt = None if pt in RAW_TO_PROMOTE: new_pt = RAW_TO_PROMOTE[pt] elif pt in PROMOTE_TO_RAW: new_pt = PROMOTE_TO_RAW[pt] if new_pt: if new_pt == shogi.PAWN and self._is_nifu(board, sq%9, p.color): pass else: board.set_piece_at(sq, shogi.Piece(new_pt, p.color)) return board def _is_valid_tsume_simple(self, board, moves_str): try: temp_board = copy.deepcopy(board) moves = moves_str.split() if not moves: return False for i, move_usi in enumerate(moves): m = shogi.Move.from_usi(move_usi) if not temp_board.is_legal(m): return False temp_board.push(m) if i % 2 == 0 and not temp_board.is_check(): return False return True except (ValueError, IndexError): return False def _is_valid_tsume_strict_no_surplus(self, board, moves_str): try: temp_board = copy.deepcopy(board) moves = moves_str.split() if not moves: return False for i, move_usi in enumerate(moves): m = shogi.Move.from_usi(move_usi) if not temp_board.is_legal(m): return False temp_board.push(m) if i % 2 == 0: if not temp_board.is_check(): return False if not temp_board.is_checkmate(): return False hand_sum = sum(temp_board.pieces_in_hand[shogi.BLACK].values()) if hand_sum > 0: return False return True except (ValueError, IndexError): return False def _is_safe_board(self, board): if board.king_squares[shogi.BLACK] is None: return False if board.king_squares[shogi.WHITE] is None: return False for i in range(9): if self._is_nifu(board, i, shogi.BLACK): return False if self._is_nifu(board, i, shogi.WHITE): return False return True def _is_nifu(self, board, file_index, color): for rank in range(9): sq = rank * 9 + file_index p = board.piece_at(sq) if p and p.piece_type == shogi.PAWN and p.color == color: return True return False if __name__ == "__main__": gen = DirectedEvolutionGenerator() gen.run()