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.

JStellAI Mark 1

So I’ve been working on improving the efficiency of the screen scraping for JStellAI.  Its been brought up to about 1/4 real time speed on my laptop, so on a powerful machine like Dice, my guess it will be somewhere between 1/2 speed to real time.  This is much faster than Stella AI, but of course the object recognition here is much more primitive.

I don’t think there is any way to make the screen scraping much more efficient than it currently is.  It currently just makes one copy of the video buffer, iterates over it once, from each location starting a bounding box if there isnt already one of the color at that point.  The only other thing I can think of is using the boolean arrays for each color, and making threads that do the bounding boxes on all the squares, but being that I expect the other cores to be busy with other duties for Moola, I think there are diminishing returns to be found there.  Aside from that, I’m going to look into other parts of the emulator and see if there is anything that is artificially slowing the clock or anything like that.

Additionally, I added some Pitfall-specific code to screen out the black border on the bottom and left side of the screen.  This is necessary since otherwise a black bounding box is made over the entire screen which makes it impossible to identify holes.   Aside from that there is nothing specifically for pitfall.

I’ve changed the display code to draw just the outlines of the rectangles because its the easiest way to see whats going on.  Another video below:

There are still a few frames that look a little funny – I need to inspect the log to see if its the java video tearing or an actual problem in the logging.  Aside from that I think this is more or less done.

As I’ve said before, I’m a bit concerned about the type of features this is producing. For example, I think that with this implementation, the ladder and the floor look like the same object, so learning the difference between the two seems like it may be tough, but I guess we can address that when/if it is actually an issue.

Next step is to get the input hacked up so I can actually control JStellAI programatically and output the proper logs that contain the actual actions.  And then once that is together I have the task of getting all of this together under Moola.

That being said, there is a pretty practical question to ask here, which is “Are we going to use this instead of the other stuff?”  I’d hate to keep putting time into this only to have it not being used in the end.