If anybody remembers "PlayFun" by Tom7 (http://www.cs.cmu.edu/~tom7/mario/), which learns playing NES games by locally trying to optimize a bunch of objective functions based on lexicographical ordering of the bytes of the NES Ram. That system probably would've found the easter egg, because it can look into the future to find the best moves. Tom7 did try Punch-Out, but his AI-player lost the game before reaching the bosses mentioned in the easter egg: https://youtu.be/YGJHR9Ovszs?t=4m39s
The easter egg isn't the fact that there's a moment when you can knock out your opponent with one hit, that was already known. The easter egg is the small visual cue in the background that indicates when to punch. I assume that this program would learn when to punch, but if it's running the simulation forward to figure it out then it would just be doing it because it works, not because of a visual cue.
If I remember correctly, my favorite part of his program was how it couldn't figure out how to remove rows in Tetris, so it simply paused the game right before GAME OVER to maximize its score over time. :D
