A* completing the first screen in Pitfall


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.

Advertisements
Tagged

6 thoughts on “A* completing the first screen in Pitfall

  1. Michael Littman says:

    Thanks for the update… anything I should be thinking about? It didn’t look very A*-ish to me. And the tripping on the log seemed wrong. And the inconsistency of playback is worrisome.

  2. hut3 says:

    Hm there are a lot of ands…

    What makes it not like A*? I’ve implemented it once a while ago in a simple domain so I’m not really sure what I should be expecting.

    I think the log is ok actually, it keeps walking into it and then walking away from it from the left and the opposite from the right. As it does that his height is changing. Remember also that it is saving and loading states every time it executes an action for just 4 frames(which is very fast), so it does a fair bit of what looks like jumping around.

    Yes the playback issue is strange. I’m going to try and see if there is anything I can figure out about it.

    As far as what you should be thinking about – not sure yet I suppose. I’d like to sort out at least the second screen first before figuring out what to do next…

  3. Michael Littman says:

    Hi,

    Well, I didn’t say it was not like A*. I said it didn’t look like A*. It’s possible that I’m misunderstanding the visualization. I was imagining we were seeing all the transition evaluations in the temporal sequence that A* queries them. If that’s right, I would have expected a lot more jumping around… What did you use for a heuristic? Something keyed off the x coordinate only? If so, I’m surprised there weren’t states at the fringe at different altitudes but roughly the same x coordinate (so Harry appeared to be experimenting with different moments to jump).

    As for the log, it looks like he runs through it instead of jumping over it.

  4. hut3 says:

    Yes the value is based on x-coordinate only, but everything is really done in terms of the how much reward has actually been accrued and then the optimistic expected reward from then on. In the first two screens where there is nothing to kill Harry, this can be though of as just how many steps have already been taken, and then whats the best case number of steps that need to be taken.

    Based on this, the priority queue always wants to go right, and the farthest right location in the least amount of time, so the fringe is always the farthest right locations that have been reached the soonest. Thats why the video doesn’t show him all over the place (at least in terms of left and right).

    As far as altitudes, the reason this isn’t explored is because falling down, climbing down a ladder, or jumping in place is a waste of time (in that it doesn’t move Harry to the right), so actions that don’t lead to movement toward the right aren’t investigated as long as something else reasonable can be done instead.

    And yes, the video is of states and transitions as they are popped off the priority queue.

    Oh, and with the log in the original hi res version its easier to see that Harry is crouching at the log. I think Youtube makes it a little harder to see. From what I’ve seen, the game doesn’t seem to get corrupted, but as I pointed out the emulator just tends to crash altogether sometimes.

  5. Michael Littman says:

    We’re talking across each other a bit, sorry about that.

    Yes, I realize A* would make it so that left and down and staying put would not be considered. But, the video clearly shows jumping right and moving right. If neither is these is a definite winner, then I’d expect to see all different jumping points considered.

    As for the log, I can’t imagine that crouching at the log is better than jumping over the log. The video does not show A* considering jumping over the log.

  6. hut3 says:

    In both cases, I see your point.

    As far as jumping, it may be the case that since Harry’s body configuration changes during the jump that it is actually considered further to the right than it would be if he was just walking, as the walking pose of the body is only that stretched out at the very end of the stride. The program tries to find the x-center of Harry, so sticking the arms out may slide that to the right a bit – I’m not sure though.

    For the log you are correct, it is definitely sub-optimal to do what it did. A possibility is that my heuristic value is a bit off. I can look into it more.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: