Finding the best sequence of choices is difficult because there are too many low-quality paths to explore. It becomes overwhelming to calculate every possible outcome.
It looks for the best path by only exploring routes that meet a specific reward score. It ignores low-probability options early on to save time.
It allows for faster decision-making by ignoring paths that are unlikely to lead to a good result.
It was run in the sandbox and it failed. run output shows an error/traceback — the artifact does NOT run clean.
$ python3 path_weighting_mcts.py Best action: (0, -1)
No screenshot — there is nothing working to show. This is recorded as an unfinished sketch so the attempt stays visible instead of being quietly dropped.
All of it — 168 lines, one file, standard library only.
# Path-Weighting MCTS with Pruning Analytics Tracker
import random
import math
from collections import defaultdict
class MCTS:
pruned_count = 0 # Class-level counter for pruning analytics
pruned_depths = [] # Track depths where pruning occurs
def __init__(self, parent=None, action=None, reward=0, is_terminal=False):
self.parent = parent
self.action = action
self.children = []
self.visits = 0
self.reward = reward
self.is_terminal = is_terminal
self.cumulative_density = 0.0 # Track reward density
self.depth = 0 if parent is None else parent.depth + 1
def path_weighting_score(self, threshold=0.5):
# Calculate reward density and apply threshold
if self.depth > 0:
reward_density = self.cumulative_density / self.depth
return reward_density > threshold
return True # Root node always expanded
def select(self, threshold=0.5):
# Selection: Prune if below threshold
if not self.path_weighting_score(threshold):
Node.pruned_count += 1 # Increment pruning counter
Node.pruned_depths.append(self.depth) # Track depth of pruned node
return None
if not self.is_expanded():
return self
# UCB1 for children
best_score = -math.inf
best_node = None
for node in self.children:
if node.visits > 0:
score = (node.reward / node.visits) + math.sqrt(2 * math.log(self.visits) / node.visits)
else:
continue # Never visited
if score > best_score:
best_score = score
best_node = node
return best_node
def expand(self, possible_actions, env):
# Expand node with reward density check
if not self.path_weighting_score():
return None # Pruned
for action in possible_actions:
if action not in [child.action for child in self.children]:
# Calculate reward from environment
reward = env.step(action)
is_terminal = env.is_terminal()
child = Node(parent=self, action=action, reward=reward, is_terminal=is_terminal)
child.cumulative_density = self.cumulative_density + reward
self.children.append(child)
return self.children[-1]
return None
def simulate(self, env):
# Simulation: Run until terminal
current_node = self
total_reward = 0
while not current_node.is_terminal:
action = random.choice([a for a in env.actions if a != current_node.action])
reward = env.step(action)
total_reward += reward
is_terminal = env.is_terminal()
# Create new node for simulation trace
new_node = Node(parent=current_node, action=action, reward=reward, is_terminal=is_terminal)
new_node.cumulative_density = current_node.cumulative_density + reward
current_node = new_node
return total_reward
def update(self, reward):
self.visits += 1
self.reward += reward
# Do not update cumulative_density with simulation rewards
if self.parent:
self.parent.update(reward)
def is_expanded(self):
return len(self.children) > 0
class Environment:
def __init__(self):
# Simple grid environment example
self.position = (0, 0)
self.grid = {
(0,0): 1, (1,0): 2, (2,0): 3,
(0,1): 4, (1,1): 5, (2,1): 6,
(0,2): 7, (1,2): 8, (2,2): 9
}
self.actions = [(1,0), (-1,0), (0,1), (0,-1)]
self.goal = (2,2)
def step(self, action):
# Simple reward: distance to goal
new_position = (self.position[0] + action[0], self.position[1] + action[1])
if new_position in self.grid:
self.position = new_position
if self.position == self.goal:
return 10 # Reward for reaching goal
# Reward based on distance to goal
distance = abs(new_position[0]-self.goal[0]) + abs(new_position[1]-self.goal[1])
return 1 / (distance + 1e-6) # Reward density example
return -0.1 # Penalty for invalid move
def is_terminal(self):
return self.position == self.goal
def main(env, iterations=1000, threshold=0.5):
root = Node()
for _ in range(iterations):
node = root
# Selection
while node and node.is_expanded() and node.path_weighting_score(threshold):
node = node.select(threshold)
# Expansion
if node and not node.is_terminal:
expanded_node = node.expand(env.actions, env)
if expanded_node:
node = expanded_node
else:
# If no expansion, use current node for simulation
pass
# Simulation
if not node.is_terminal:
reward = node.simulate(env)
else:
reward = env.step(node.action) if node.action else 0
# Backpropagation
node.update(reward)
# Find best path
best_action = None
best_reward = -math.inf
for child in root.children:
if child.reward > best_reward:
best_reward = child.reward
best_action = child.action
# Pruning Analytics Report
print("\nPruning Analytics:")
print(f"Total nodes pruned: {Node.pruned_count}")
if Node.pruned_depths:
avg_prune_depth = sum(Node.pruned_depths) / len(Node.pruned_depths)
print(f"Average depth of pruned nodes: {avg_prune_depth:.2f}")
print(f"Maximum depth of pruned nodes: {max(Node.pruned_depths)}")
print(f"Minimum depth of pruned nodes: {min(Node.pruned_depths)}")
print(f'Best action: {best_action}')
return best_action
if __name__ == '__main__':
env = Environment()
best_action = main(env)