99 lines
2.5 KiB
Julia
99 lines
2.5 KiB
Julia
# Pathfinding Problem - MCTS Example
|
|
|
|
This example shows how to use MCTS for a pathfinding problem where the goal is to reach a target location.
|
|
|
|
```julia
|
|
using LLMMCTS
|
|
|
|
# Grid-based pathfinding state
|
|
struct Position
|
|
x::Int
|
|
y::Int
|
|
end
|
|
|
|
# State transition function for pathfinding
|
|
function pathfinding_transition(state::Dict, args::NamedTuple)
|
|
current_pos = Position(state[:pos_x], state[:pos_y])
|
|
target_pos = Position(args.target_x, args.target_y)
|
|
|
|
# Generate possible moves (up, down, left, right)
|
|
moves = [
|
|
(0, 1), # up
|
|
(0, -1), # down
|
|
(1, 0), # right
|
|
(-1, 0) # left
|
|
]
|
|
|
|
# In a real scenario, LLM would select which move to try
|
|
# For this example, we'll try all moves
|
|
move_idx = state[:move_idx] % length(moves) + 1
|
|
dx, dy = moves[move_idx]
|
|
|
|
new_x = current_pos.x + dx
|
|
new_y = current_pos.y + dy
|
|
|
|
# Calculate distance to target
|
|
distance = abs(new_x - target_pos.x) + abs(new_y - target_pos.y)
|
|
|
|
# Reward: negative of distance (closer is better)
|
|
reward = -distance
|
|
|
|
# Progress value: LLM estimate (here we use inverse distance as heuristic)
|
|
progressvalue = 10 - distance
|
|
|
|
newstate = Dict(
|
|
:pos_x => new_x,
|
|
:pos_y => new_y,
|
|
:move_idx => state[:move_idx] + 1,
|
|
:reward => reward,
|
|
:isterminal => (new_x == target_pos.x && new_y == target_pos.y) ||
|
|
(state[:move_idx] >= args.max_moves)
|
|
)
|
|
|
|
return Dict(
|
|
:newNodeKey => "pos_$(new_x)_$(new_y)",
|
|
:newstate => newstate,
|
|
:progressvalue => progressvalue
|
|
)
|
|
end
|
|
|
|
# Initial state
|
|
initialstate = Dict(
|
|
:pos_x => 0,
|
|
:pos_y => 0,
|
|
:move_idx => 0,
|
|
:reward => 0,
|
|
:isterminal => false
|
|
)
|
|
|
|
# Target position
|
|
target_x, target_y = 3, 2
|
|
|
|
# Transition arguments
|
|
transitionargs = (
|
|
target_x = target_x,
|
|
target_y = target_y,
|
|
max_moves = 10
|
|
)
|
|
|
|
# Run MCTS
|
|
result = runMCTS(
|
|
initialstate,
|
|
pathfinding_transition,
|
|
transitionargs;
|
|
maxiterations = 20,
|
|
explorationweight = 1.5,
|
|
maxSimulationDepth = 5,
|
|
horizontalSampleExpansionPhase = 4
|
|
)
|
|
|
|
# Display results
|
|
println("Target: ($target_x, $target_y)")
|
|
println("Best final position: (",
|
|
result.bestTerminalState[:pos_x], ", ",
|
|
result.bestTerminalState[:pos_y], ")")
|
|
println("Final distance: ", abs(result.bestTerminalState[:pos_x] - target_x) +
|
|
abs(result.bestTerminalState[:pos_y] - target_y))
|
|
println("Root node visits: ", result.root.visits)
|
|
```
|