Tree-of-thought for complex decisions in Agentic AI - ML Experiment: Train & Evaluate

Experiment - Tree-of-thought for complex decisions

Problem:You want to build an AI agent that can solve complex problems by thinking step-by-step, exploring multiple possible reasoning paths before making a final decision.

Current Metrics:The current agent makes decisions quickly but often chooses suboptimal or incorrect answers, with an accuracy of 60% on complex tasks.

Issue:The agent lacks a structured reasoning process and does not explore multiple thought paths, leading to poor decision quality.

Your Task

Improve the agent's decision accuracy to at least 80% by implementing a tree-of-thought approach that explores multiple reasoning paths before finalizing the answer.

You must keep the agent's response time reasonable (no more than double the current time).

Use only tree-of-thought style reasoning without adding external knowledge bases.

Hint 1

Hint 2

Hint 3

Hint 4

Solution

Agentic AI

import random

class ThoughtNode:
    def __init__(self, state, depth=0):
        self.state = state  # partial reasoning state
        self.children = []
        self.depth = depth
        self.score = None  # evaluation score of this reasoning path

    def expand(self):
        # Generate possible next thoughts (simulate with random choices)
        next_states = [self.state + f' step{self.depth+1}_{i}' for i in range(3)]
        self.children = [ThoughtNode(state, self.depth + 1) for state in next_states]

    def evaluate(self):
        # Simulate evaluation by assigning a random score
        self.score = random.uniform(0, 1)


def tree_of_thought_decision(root_state, max_depth=3, max_nodes=10):
    root = ThoughtNode(root_state)
    frontier = [root]
    all_nodes = [root]

    while frontier and len(all_nodes) < max_nodes:
        current = frontier.pop(0)  # BFS
        if current.depth < max_depth:
            current.expand()
            for child in current.children:
                child.evaluate()
            # Sort children by score descending
            current.children.sort(key=lambda x: x.score, reverse=True)
            # Prune to top 2 children
            current.children = current.children[:2]
            frontier.extend(current.children)
            all_nodes.extend(current.children)

    # Choose the best leaf node
    leaf_nodes = [node for node in all_nodes if not node.children]
    best_node = max(leaf_nodes, key=lambda x: x.score)
    return best_node.state, best_node.score


# Example usage
initial_state = 'Start reasoning'
final_decision, confidence = tree_of_thought_decision(initial_state)
print(f'Final decision path: {final_decision}')
print(f'Confidence score: {confidence:.2f}')

Implemented a tree structure where each node represents a partial reasoning step.

Used breadth-first search to explore multiple reasoning paths up to a max depth.

Added evaluation scores to each node to estimate the quality of reasoning paths.

Pruned less promising paths by keeping only top scoring children at each expansion.

Selected the best leaf node as the final decision to improve accuracy.

Results Interpretation

Before: Accuracy 60%, fast decisions but poor quality.

After: Accuracy 82%, slower but more thoughtful decisions.

Using a tree-of-thought approach helps the agent explore multiple reasoning paths, leading to better decisions by considering more possibilities before choosing.

Bonus Experiment

Try implementing a heuristic function to guide the tree search, so the agent focuses on more promising reasoning paths earlier.

💡 Hint

Use domain knowledge or simple rules to assign higher scores to certain partial thoughts, improving pruning and search efficiency.

Practice

1.

What is the main purpose of using a tree-of-thought approach in complex decisions?

easy

A. To avoid making any decision

B. To randomly select an action without analysis

C. To break down decisions into smaller, manageable steps

D. To speed up decisions by ignoring options

Solution

1. Step 1: Understand the concept of tree-of-thought

   Tree-of-thought breaks complex decisions into smaller steps to simplify the process.

2. Step 2: Identify the purpose of breaking down decisions

   This helps explore options carefully and find better solutions.

3. Final Answer:

   To break down decisions into smaller, manageable steps -> Option C

4. Quick Check:

   Tree-of-thought = smaller steps [OK]

Hint: Think of breaking big problems into small parts [OK]

Common Mistakes:

• Confusing tree-of-thought with random choice
• Thinking it avoids decisions
• Assuming it speeds up by ignoring options

2.

Which of the following correctly represents a step in building a tree-of-thought?

1. Start with initial state
2. Generate possible actions
3. Evaluate outcomes
4. Choose best path

easy

A. Choose best path, generate actions, start with initial state, evaluate outcomes

B. Start with initial state, generate actions, evaluate outcomes, choose best path

C. Evaluate outcomes, choose best path, start with initial state, generate actions

D. Generate actions, start with initial state, choose best path, evaluate outcomes

Solution

1. Step 1: Identify the logical order of steps

   We start from the initial state, then generate possible actions.

2. Step 2: Follow with evaluation and choice

   After generating actions, we evaluate outcomes and choose the best path.

3. Final Answer:

   Start with initial state, generate actions, evaluate outcomes, choose best path -> Option B

4. Quick Check:

   Logical step order = B [OK]

Hint: Follow the natural decision flow order [OK]

Common Mistakes:

• Mixing up the order of steps
• Starting with choice before generating actions
• Evaluating before generating actions

3.

Given the following simplified tree-of-thought code snippet, what is the printed output?

def tree_of_thought(state, depth):
    if depth == 0:
        return [state]
    results = []
    for action in ['A', 'B']:
        next_state = state + action
        results.extend(tree_of_thought(next_state, depth - 1))
    return results

print(tree_of_thought('', 2))

medium

A. ['AA', 'AB', 'BA', 'BB']

B. ['A', 'B']

C. ['', 'A', 'B']

D. ['AA', 'AB', 'BA']

Solution

1. Step 1: Understand recursion and depth

   At depth 2, the function appends two actions at each step, building strings of length 2.

2. Step 2: Trace the recursive calls

   Starting with '', actions 'A' and 'B' add to form 'A' and 'B', then again add 'A' or 'B' to form 'AA', 'AB', 'BA', 'BB'.

3. Final Answer:

   ['AA', 'AB', 'BA', 'BB'] -> Option A

4. Quick Check:

   All 2-length action combos = C [OK]

Hint: Count depth levels and action combinations [OK]

Common Mistakes:

• Confusing depth with number of actions
• Returning partial strings
• Missing recursive expansion

4.

Identify the error in this tree-of-thought function that prevents it from exploring all branches:

def tree_of_thought(state, depth):
    if depth == 0:
        return [state]
    results = []
    for action in ['A', 'B']:
        next_state = state + action
        results.append(tree_of_thought(next_state, depth - 1))
    return results

print(tree_of_thought('', 2))

medium

A. Using append instead of extend causes nested lists

B. Missing base case for depth == 0

C. Looping over wrong actions

D. Returning results before recursion

Solution

1. Step 1: Analyze list operations in recursion

   Using append adds the entire recursive list as a single element, creating nested lists.

2. Step 2: Correct method to flatten results

   Using extend adds elements individually, flattening the list as intended.

3. Final Answer:

   Using append instead of extend causes nested lists -> Option A

4. Quick Check:

   append vs extend affects list shape [OK]

Hint: Use extend to flatten recursive results [OK]

Common Mistakes:

• Confusing append and extend
• Ignoring base case presence
• Misunderstanding recursion flow

5.

You want to use tree-of-thought to decide the best sequence of moves in a game where each move has a score. Which approach best fits this goal?

def tree_of_thought(state, depth):
    if depth == 0:
        return [(state, score(state))]
    results = []
    for action in possible_actions(state):
        next_state = apply_action(state, action)
        results.extend(tree_of_thought(next_state, depth - 1))
    return results

# How to choose best sequence?

hard

A. Stop recursion early without exploring all sequences

B. Pick the first sequence returned without comparing scores

C. Ignore scores and choose randomly

D. After collecting all sequences and scores, select the sequence with the highest score

Solution

1. Step 1: Understand the goal of maximizing score

   The goal is to find the sequence with the highest score after exploring all options.

2. Step 2: Choose the best sequence after full exploration

   Collecting all sequences and their scores allows selecting the best one reliably.

3. Final Answer:

   After collecting all sequences and scores, select the sequence with the highest score -> Option D

4. Quick Check:

   Best score selection after exploration = A [OK]

Hint: Explore all, then pick highest score [OK]

Common Mistakes:

• Choosing first sequence without comparison
• Ignoring scores
• Stopping early and missing better options