So doing lots of random rollouts where the backward/left actions aren’t allowed lets you get through pitfall pretty easily. Almost every screen can be finished in under 1000 rollouts.
I tried using simple hillclimbing, but at Sergiu’s recommendation I turned it off. Turns out this works better as hillclimbing seemed to get stuck in local optima. Not sure how to present this for the paper, and whether I should play with other optimization methods, but for now I’m pretty happy.