Schema-Guided MCTS Path Scorer

The problem

It is difficult to find the most accurate path through a complex web of data when you need the final result to follow a specific structure.

What it does

It explores multiple possible paths through a graph and ranks them based on how well they match a target data format.

Why it matters

It automates the process of finding the most relevant path while ensuring the output stays consistent with the required data rules.

Validation

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

$ python3 schema_guided_mcts_path_scorer.py
Traceback (most recent call last):
  File "/work/schema_guided_mcts_path_scorer.py", line 75, in <module>
    best_path = mcts.search(iterations=1000)
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/work/schema_guided_mcts_path_scorer.py", line 24, in search
    return self.best_path()
           ^^^^^^^^^^^^^^^^
  File "/work/schema_guided_mcts_path_scorer.py", line 59, in best_path
    return max(self.root.children, key=lambda child: child.reward).move
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ValueError: max() iterable argument is empty

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 — 76 lines, one file, standard library only.

import random
import math
from collections import defaultdict
class Node:
    def __init__(self, parent, move, outcome):
        self.parent = parent
        self.move = move
        self.outcome = outcome
        self.children = []
        self.visits = 0
        self.reward = 0.0

class SchemaGuidedMCTS:
    def __init__(self, graph, schema):
        self.graph = graph
        self.schema = schema
        self.root = Node(None, None, None)

    def search(self, iterations=1000):
        for _ in range(iterations):
            node = self.selection()
            reward = self.simulation(node)
            self.backpropagate(node, reward)
        return self.best_path()

    def selection(self):
        node = self.root
        while node.children:
            node = max(node.children, key=lambda child: child.reward + 2 * math.sqrt(math.log(node.visits) / child.visits) if child.visits > 0 else float('inf'))
        return node

    def simulation(self, node):
        path = self._get_path(node)
        return self._schema_scorer(path)

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

    def _get_path(self, node):
        path = []
        while node:
            path.append(node.move)
            node = node.parent
        return path[::-1]

    def _schema_scorer(self, path):
        score = 0
        j = 0
        for node in path:
            if j < len(self.schema) and node == self.schema[j]:
                score += 1
                j += 1
        return score

    def best_path(self):
        return max(self.root.children, key=lambda child: child.reward).move

# Example usage
if __name__ == '__main__':
    # Define graph as {node: [adjacent nodes]}
    graph = {
        'A': ['B', 'C'],
        'B': ['D'],
        'C': ['D'],
        'D': []
    }
    
    # Define target schema as sequence of nodes
    schema = ['A', 'B', 'D']

    mcts = SchemaGuidedMCTS(graph, schema)
    best_path = mcts.search(iterations=1000)
    print(f'Optimal path aligned with schema: {best_path}')