Failure-Guided MCTS Path Selection

The problem

Standard AI reasoning can get stuck repeating the same mistakes because it doesn't always recognize when a path is failing. It lacks a way to learn from errors in real-time as it explores different options.

What it does

It combines a decision-making engine with a self-correction tool that simulates potential outcomes to learn from mistakes. This allows the system to evaluate paths by anticipating and learning from failures before committing to them.

Why it matters

It allows a system to reason through complex problems by actively learning from its own mistakes during the planning process.

Validation

It was run in the sandbox and it failed. run output shows an error/traceback — the artifact does NOT run clean.

$ python3 failure_guided_mcts.py
Traceback (most recent call last):
  File "/work/failure_guided_mcts.py", line 137, in <module>
    best_state = mcts.search(iterations=1000)
                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/work/failure_guided_mcts.py", line 90, in search
    reward = self.rollout(node)
             ^^^^^^^^^^^^^^^^^^
  File "/work/failure_guided_mcts.py", line 68, in rollout
    while not current.state.is_terminal() and depth < max_depth:
              ^^^^^^^^^^^^^^^^^^^^^^^^^
AttributeError: 'tuple' object has no attribute 'is_terminal'

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.

The code

All of it — 138 lines, one file, standard library only.

import random
import math
from abc import ABC, abstractmethod

class State(ABC):
    @abstractmethod
    def is_terminal(self):
        pass

    @abstractmethod
    def get_actions(self):
        pass

    @abstractmethod
    def take_action(self, action):
        pass

    @abstractmethod
    def get_reward(self):
        pass

class Node:
    def __init__(self, state, parent=None):
        self.state = state
        self.parent = parent
        self.children = []
        self.visits = 0
        self.reward = 0.0
        self.failure_count = 0

    def expand(self):
        if not self.state.is_terminal():
            for action in self.state.get_actions():
                new_state = self.state.take_action(action)
                self.children.append(Node(new_state, self))

    def is_fully_expanded(self):
        return len(self.children) == len(self.state.get_actions())

class MCTS:
    def __init__(self, root_state, c=1.0):
        self.root = Node(root_state)
        self.c = c  # Exploration parameter

    def select(self):
        node = self.root
        while node.is_fully_expanded() and not node.state.is_terminal():
            # UCB1 selection with failure penalty
            best_score = -float('inf')
            best_child = None
            for child in node.children:
                if child.visits == 0:
                    best_child = child
                    break
                failure_penalty = -child.failure_count * 0.5
                score = (child.reward / child.visits) + failure_penalty + self.c * math.sqrt(math.log(node.visits) / child.visits)
                if score > best_score:
                    best_score = score
                    best_child = child
            if best_child is None:
                break
            node = best_child
        return node

    def rollout(self, node, max_depth=10):
        current = node
        depth = 0
        while not current.state.is_terminal() and depth < max_depth:
            if current.state.get_reward() < 0:
                # Failure detected, penalize and backtrack
                current.failure_count += 1
                if current.parent:
                    current = current.parent
                    depth -= 1
                    continue
            action = random.choice(current.state.get_actions())
            current = Node(current.state.take_action(action))
            depth += 1
        return current.state.get_reward()

    def backpropagate(self, node, reward):
        while node:
            node.visits += 1
            node.reward += reward
            node = node.parent

    def search(self, iterations=1000):
        for _ in range(iterations):
            node = self.select()
            reward = self.rollout(node)
            self.backpropagate(node, reward)
        # Return best child based on win rate
        if self.root.children:
            best_child = max(self.root.children, key=lambda c: c.reward / c.visits)
            return best_child.state
        return self.root.state

class GridWorld(State):
    def __init__(self, rows, cols, goal, obstacles):
        self.rows = rows
        self.cols = cols
        self.goal = goal
        self.obstacles = obstacles
        self.position = (0, 0)  # Starting position

    def is_terminal(self):
        return self.position == self.goal

    def get_actions(self):
        # Possible actions: up, down, left, right
        return [(0, 1), (0, -1), (1, 0), (-1, 0)]

    def take_action(self, action):
        new_pos = (self.position[0] + action[0], self.position[1] + action[1])
        if (new_pos[0] < 0 or new_pos[0] >= self.rows or
            new_pos[1] < 0 or new_pos[1] >= self.cols or
            new_pos in self.obstacles):
            # Action leads to obstacle or out of bounds, which is a failure
            return self.position  # Stay in place, but for the purpose of reward, mark as failure
        return new_pos

    def get_reward(self):
        if self.position == self.goal:
            return 1.0
        elif self.position in self.obstacles:
            return -1.0  # Failure
        else:
            return 0.0

if __name__ == "__main__":
    # Create a grid world with obstacles
    obstacles = [(1, 1), (2, 2)]
    goal = (3, 3)
    world = GridWorld(rows=4, cols=4, goal=goal, obstacles=obstacles)
    
    mcts = MCTS(world)
    best_state = mcts.search(iterations=1000)
    print(f"Best path ends at: {best_state.position}")