Python / PyTorch 工业标准参考实现答案 (含测试验证与边界断言)
import math
import random
class MCTSNode:
def __init__(self, state: str, parent=None, action: str = None):
self.state = state
self.parent = parent
self.action = action
self.children = []
self.visits = 0
self.value_sum = 0.0
@property
def q_value(self) -> float:
return self.value_sum / (self.visits + 1e-6)
def is_fully_expanded(self) -> bool:
return len(self.children) > 0
def ucb1(self, c_param: float = 1.414) -> float:
if self.visits == 0:
return float('inf')
return self.q_value + c_param * math.sqrt(math.log(self.parent.visits + 1) / self.visits)
class MCTSReasoner:
"""MCTS Reasoning Tree Search for multi-step math/logic deduction."""
def __init__(self, exploration_weight: float = 1.414):
self.c = exploration_weight
def select(self, node: MCTSNode) -> MCTSNode:
"""Traverse tree using UCB1 until an unexpanded leaf is found."""
curr = node
while curr.is_fully_expanded():
curr = max(curr.children, key=lambda child: child.ucb1(self.c))
return curr
def expand(self, node: MCTSNode, candidate_steps: list[str]) -> None:
"""Expand node with candidate reasoning actions."""
for step in candidate_steps:
new_state = f"{node.state} -> [{step}]"
child = MCTSNode(new_state, parent=node, action=step)
node.children.append(child)
def backpropagate(self, node: MCTSNode, value: float) -> None:
"""Propagate evaluation score bottom-up to all ancestor nodes."""
curr = node
while curr is not None:
curr.visits += 1
curr.value_sum += value
curr = curr.parent
def search(self, root_state: str, num_simulations: int = 50) -> str:
root = MCTSNode(root_state)
# Mock candidate thought generation
actions = ["Identify key invariant", "Calculate subtotal", "Verify constraints", "Form final answer"]
for _ in range(num_simulations):
leaf = self.select(root)
if not leaf.is_fully_expanded() and leaf.visits > 0:
self.expand(leaf, actions)
leaf = leaf.children[0]
# Mock value estimate from PRM (Process Reward Model)
sim_score = random.uniform(0.5, 1.0) if "Verify constraints" in leaf.state else random.uniform(0.1, 0.7)
self.backpropagate(leaf, sim_score)
best_child = max(root.children, key=lambda c: c.visits)
return best_child.state
# --- Verification & Test Case ---
if __name__ == "__main__":
reasoner = MCTSReasoner()
best_path = reasoner.search("Problem: Find primes <= 10", num_simulations=40)
print("MCTS selected best reasoning path:", best_path)