Principle:Iamhankai Forest of Thought BFS Forest Solving
| Knowledge Sources | |
|---|---|
| Domains | Search_Algorithms, Game_Solving |
| Last Updated | 2026-02-14 03:00 GMT |
Overview
A multi-tree breadth-first search algorithm that decomposes Game of 24 puzzles into three staged arithmetic reductions with LLM-guided proposal generation and value-based pruning.
Description
BFS Forest Solving applies the Forest-of-Thought principle to the Game of 24 domain. The algorithm decomposes each 4-number puzzle into three stages (4 to 3 numbers, 3 to 2 numbers, 2 to 1 number), generating arithmetic proposals via LLM prompting at each stage and pruning via LLM value estimation. Multiple trees operate on shuffled input orderings for diversity, and the first valid solution (expression evaluating to 24) is returned.
Key differences from benchmark FoT:
- Fixed 3-stage decomposition instead of open-ended tree depth
- Deterministic final stage: 2-number arithmetic is computed directly
- Expression validation: Solutions are verified by expression evaluation, not string matching
Usage
Use this principle for Game24 task solving. It is the primary solver used in scripts/game24/run.py with forest_solve() for multi-tree search and naive_solve() for single-tree CoT baseline comparison.
Theoretical Basis
The 3-stage decomposition maps to a fixed-depth BFS tree:
# Stage 1: 4 numbers -> 3 numbers (LLM proposes arithmetic operations)
# Stage 2: 3 numbers -> 2 numbers (LLM proposes arithmetic operations)
# Stage 3: 2 numbers -> 1 number (deterministic computation)
# At each stage:
candidates = generate_proposals(current_numbers)
values = evaluate_candidates(candidates)
selected = top_k(candidates, values, k=n_select_sample)
Input diversity via shuffling provides ensemble benefit:
- Different number orderings lead to different proposal biases in the LLM
- Multiple trees explore different decomposition paths