Exploration Strategies

Analysis of different exploration strategies. Particularly strategies that assume minimal knowledge of the game.

TODO: What is the plateau for each strategy? TODO: Make a plot.

Random Wander

Randomly bounce around until time runs out. Occasionally makes it out of Red's house. If you wait a few hours this strategy will eventually find Route 1.

Random Incomplete and Gotohere

Search the navmesh graph for nodes with less than 4 outgoing edges. Go there before wandering.

Can't get through the gate house at the south entrance to Viridian Forest. Too many "incomplete" nodes with no new edges -> run out of time and "get stuck" before finding the way through.

Straight Line Bias

Prefer to walk in a straight line rather than completely random directions. 5/8 continue in same direction, 1/8 in every other direction.

Gets stuck at Viridian Forest. It is far enough from the start location that there isn't enough time left in the job to do a random walk effectively.

Emucache

Save a copy of the emulator state at each unique location. Randomly select the starting emulator from this cache when generating new jobs.

Gets stuck at Pweter City. Can't make it through the small step in the ledge by Youngster Joey aka "I like shorts. They're comfy and easy to wear.".

All Hail the Dark Lord

Looks like we got stuck at the Super Nerd in front of the fossils. Time to flip some bits in memory and go again.

(Insert tangent about pokered and the memory map here)

"Grab" the dome fossil by fiddling with memory in the emulator.

Drop the learning rate

Until this step, we have been adding every node we explicitly visit to a "nogo" list for future batches. This meant that we had to get the next step right on the first try for narrow gaps, ultimately getting stuck a bunch of times on route 3 on the way to mt moon. Instead, we can drop the learning rate to 5%. Now we have to explictly choose to go to a node 20 times before adding it to the nogo list. This still captures places not worth visiting like Oak's lab, but gives us many more chances to find our way through the narrow gaps in the map.