This is the video of A* running on the first screen in Pitfall in real time. All possible screens are considered unique states, since the game is not 1-step Markovian.
The value assigned to a state is a function of how many steps were done so far (a count of the number of actions taken in the trajectory that lead to a state) and a best-case estimate of the number of actions required to reach the goal from that state (which is based on the current location of Harry).
The algorithm finds a quick path through the screen (4 seconds, but actually 3 seems possible), so perhaps my heuristic for prediction is a little off and it is settling for something slightly sub-optimal.
Oddly, I tried to execute the actions that lead to the completion of the level, but this generally did not work; it seems there are slight variances in the ways actions are executed, or the timing, or something else that leads to inconsistent solutions across runs. Indeed, running the same series of actions mutliple times can lead to a number of different actual results, which is strange.
I tried running this algorithm on the second screen but so far have not met with success. Since that screen is more complicated, the solution is likewise more difficult. Unfortunately, the emulator is a little flaky with loads/saves so it often crashes before it has run for a long time, which so far has prevented a solution to the second screen.
I’m gonna keep working on it – hopefully I can sort out the crashing issue, and get at least the second screen solved as well. If this keeps taking too long on screen 2, I may also try some roll-out methods, as certain things (such as ladders) seem to cause A* a lot more trouble than I would have expected.