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.
Software + Hardware
Rom Information
Rom: Pac-Man
headerless rom hash: SHA1:92C3361B9E3B28A51FD30E7845C988A6D576EE65
headerless rom hash: MD5:CA606BD8A875A396D52735C3BB84FA67
Joined: 10/12/2011
Posts: 6437
Location: The land down under.
Don't care if I'm in the minority opinion on this one.
Firstly it fails to be faster than something that exists back in 2008.
Which has been converted: User movie #49844826068076307
Secondly. Pac-Man's NES has a loop which has a speed and enemy speed cap (and aggression).
It's not hard to figure out where your input can be repeated as you can clone your input.
And if my memory serves me correctly it's at key, which is Maze 13.
This movie is not complete.
No vote.
WebNations/Sabih wrote:
+fsvgm777 never censoring anything.
Disables Comments and Ratings for the YouTube account.Something better for yourself and also others.
Don't care if I'm in the minority opinion on this one.
Firstly it fails to be faster than something that exists back in 2008.
Which has been converted: User movie #49844826068076307
Secondly. Pac-Man's NES has a loop which has a speed and enemy speed cap (and aggression).
It's not hard to figure out where your input can be repeated as you can clone your input.
And if my memory serves me correctly it's at key, which is Maze 13.
This movie is not complete.
No vote.
Hi Spikestuff, thanks for the feedback.
I was curious to try the movie you reference, but I just couldn't make it work. Seems like the initial two starts 'S' do not initially start the game with the rom file I used. When I try to play that movie, it tells me 'Movie hash does not match the ROM'. Could you please check?
Regarding This movie is not complete, I believe this rule was relaxed as of late, to allow publications like this. It's up to the judges tho.
[Update]: It seems like the movie above was done with the Tengen version, whereas I used the Namco version. I tried cross-copying the solutions to one another at the point of level start, and both desync -- meaning that the game mechanics are also different (perhaps only on RNG). I will nevertheless test the Randil route on the Namco version to see if it achieves a faster solution than our proposed one. If so, we'll rework the math/routing to see if we can improve it. Until then, I suppose this movie is the fastest solution so far for the rom version I used.
I love bot optimization but understand if it doesn't fit other site rules.
Does eating a pill 'out of the way' (one instance around frame 1550) or the occasional 1-pixel forays into a side tunnel (e.g., one around frame 486) not lose frames? The frame 1550 pill-eating seems especially surprising as that part of the maze is traversed again a little bit later, so the pill would be eaten anyhow.
I love bot optimization but understand if it doesn't fit other site rules.
Hi Jeff, thanks! Yes, it's true that TASvideos traditionally accepts full movies. However, I've been following the site developments closely and this rule has been relaxed in some instances to enable some really entertaining movies to be published in a special category.
jeff_town wrote:
Does [...] the occasional 1-pixel forays into a side tunnel (e.g., one around frame 486) not lose frames?.
The 'forays' might be pure Ghost manipulation, to get them out of the way.
jeff_town wrote:
The frame 1550 pill-eating seems especially surprising as that part of the maze is traversed again a little bit later, so the pill would be eaten anyhow.
I'm investigating this right now because it seems some of the pathing might be superfluous, given how the pac-man moves in this game. I'll be working on a new version soon so stay tuned.
Cancelling submission for the following reasons:
- There exists another version of the game (Tengen) which is equivalent to this (Namco) but allows starting faster. This movie needs to be re-done on another rom.
- Spikestuff pointed to us that a previous work exists that I missed from Randil. This work faster in its routing.
- Our calculations failed to observed some of the particulars of the game (in particular, the ability of Pac-man to quick-grab pellets around the corners). We need to go back to the drawing board and re-calculate the routing with this in mind.
- Based on how busy my co-author and me are, this might take a while -- more than a 'delayed' submission can sensibly take.
We'll be back, but for now let's remove this sub from the workspace. Thanks for the feedback to all!
