Submission #8149: eien86 & mscroggs's NES Pac-Man (Namco) "single level" in 00:44.18

This movie solves the very first level of NES Pac-Man as fast as possible. I based the optimal route described in Matthew Scroggs' publication on chalkdust magazine. There, he maps the pellet layout to a connected graph (a pac-graph) and calculates the optimal route, based on the starting position, by reducing the problem to that of the Chinese postman problem. I truly recommend reading his article.

The ideal path derived by Matthew does not consider ghost behavior. Indeed, at any point, your traversal of the ideal path can be interrupted by a ghost -- either by killing you or by being eaten by you (stealing half a second). To solve the ghost problem, I first mirrored the proposed solution horizontally, to avoid the initial two ghosts who immediately turn left. This turn sacrifices, in theory, a single frame. Next, I transcribed the pellet order into JaffarPlus to solve the level by having a reward function (r) with the following shape:

r = #PelletsInPathEatenInOrder * 1000.0 + distanceToNextPellet

The PelletsInPathEatenInOrder rewards the bot for every pellet eaten in the (reversed) optimal path, and not for any other pellet which is out of order in the optimal route. The distance to the next pellet is the manhattan distance from the center of pacman and the position of the next pellet in the route.

The result is pretty satisfactory. However, the run might be improved by traversing one of the long straight lasts, so that the last input happens way before the last pellet is eaten. But I refuse to go for this, as it goes against the beauty of the graph theory used by Matthew. I believe Frame-To-Last pellet should be preserved as criterion for movie length in this case.

Rom: Pac-Man