After you complete the Super Mario Bros. 2 portion of Super Mario Advance, a new variation of the game becomes available. This is known as Yoshi's Challenge. In Yoshi's Challenge, two eggs are hidden in the Sub-space of each level, for a total of 40 eggs. While they are usually found in similar places as the mushrooms, they're often not in the exact same locations, so you must do some hunting, even if you know precisely where all of the mushrooms are.
In addition to the challenge of finding these eggs, you must do so without dying. If you die during the level, any eggs that you have found will be lost. You can collect them once again after you die, but you will only get credit for finding eggs as long as you complete the stage you found them in. Contrary to popular belief, you are not required to find both eggs in one run. You can find one egg and complete the stage to get credit for that egg, and then return to the stage to find the second egg at a later time.
A couple of things to note about Yoshi's Challenge:
Your saved score will continue to accumulate as you play through Yoshi's Challenge.
Your remaining lives will similarly be recorded, whether they increase or decrease.
You can choose any stage, and collect the eggs in any order that you like.
You are not required to find all 100 A-coins in order to unlock the challenge.
You can collect any missing A-coins along the way, but it is recommended that you do not focus on finding A-coins as they can cause you to take some unnecessary risks, and potentially lose any eggs you found.
The eggs will replace two of the mushrooms. As a result, the most number of health units you can possess in any one level is three; the two you start with and one mushroom if one is available in the stage. Most, but not all stages have one mushroom in Yoshi's Challenge.
As stated above, you must collect any eggs and complete the stage, including defeating any bosses, in order to earn credit for finding an egg.
There's very little guesswork involved with this egg; it's found right where the first Mushroom was found.
Super Mario Advance added a potion at the top of a set of ladders in the middle of the tower. Grab the potion and use it at the bottom of those ladders to find an egg.
The first egg is very close to where you found a Mushroom on the tail of the far left whale.
Similarly, the second egg is pretty close to where the newly added third Mushroom is located. Just pick up the potion in between the whales, and drop it.
The first egg is positioned right where you found the first Mushroom. However, eggs are a little taller than Mushrooms so you may need to use a power-jump.
Like the second Mushroom, this egg is found on one of the turrets at the edge of the tower. Unlike the Mushroom, the egg is found on the left side.
Similar to how you found the newly added Mushroom in the middle of the waterfall section, you'll find the egg up on the higher platform.
To get this egg, you must be familiar with the method to collect the second Mushroom at the end of the stage. Only instead of removing the right Mushroom Block, you must remove the left one.
Look for the first egg right near the dangerous Panser plant between the two Hoopsters. Remember that the Panser plant now sits on top of a potion.
Once you collect the potion from underneath one of the Snifits on the right side, you must get a lift from Hoopsters in order to reach the top where the egg can be found.
Instead of finding the first Mushroom just to the left of where you collect the potion, you'll find the first egg just to the right.
After climbing down the ladder, use the Bob-ombs to blast a hole to the ground below, grab the potion, and make sure you can access the ground above in order to collect the egg.
There isn't a whole lot of land for the eggs to hide in this stage. The first egg is right next to the middle platform with the potion.
You'll need to grab the potion a second time from the center platform, and carry it all the way to the end. Drop it off near the exit to find the second mushroom.
Whereas the first Mushroom sat atop one of these short cactus plants, the egg will fall directly between them and start sinking in the quicksand if you don't rescue it.
The second egg is in the same location as the newly added hidden Mushroom. Explore the jar, grab the potion, exit the jar, and use it as soon as you return.
Rather than finding the first Mushroom on the grassy hilltop, you'll find it closer to the potion on the bridge. Just watch out for the Bob-ombs.
Grab the potion just below the door that leads to the boss. Instead of dropping down with it to find a new Mushroom, stay right there to find the second egg.
World 7-2 is the one stage where you will be REQUIRED to take both paths to get the Yoshi eggs. The first egg you should go for is right near where you found one of the Mushrooms. To get there, take the path at the very end of the first hallway. Keep going until you reach a door midway through the climbing section, then fall to the door below. Use the potion. Climb back up the ladders and return to the Sparky and Chain room. Now, tread carefully to the next egg, for if you should lose a life, you'll lose it, which will require you to backtrack here.
The second egg may seem pretty close, but you'll have to backtrack through several rooms to get here. If you are following along with the guide, you should be in the room with Sparkies and chains. Carefully make your way back down to the first hallway. Once you're there, head left, climb down the chain and avoid the Sparkies while throwing mushroom blocks to go down. It is recommended that you go for this egg last since you cannot go back up (even Luigi's super jump doesn't reach high enough) at the end of this room. Keep going until you see a door next to the lone tuft of grass. Enter, then grab the potion. You just have to drop the potion a bit more to the right, in order to find this egg which is higher up on the ledge. When you get it, once again, tread carefully. Lose a life, and you'll lose both eggs, which will require EXTENSIVE backtracking. Use extreme caution fighting Birdo for the key, the door leading to Wart and the big frog himself. If you can use the ladder jump speedrunning technique, you can save a LOT of time by jumping on the ceiling to get to Birdo faster. Congratulations! Enjoy having a Red Yoshi on the Title Screen!
Every time you obtain a complete set of egg for each world (six in most cases, except for World 7 which only has four), the eggs will hatch into baby Yoshis which quickly grow to full-sized Yoshis. Once you have collected all four Yoshis, you will receive the "PERFECT" screen shown to the left. After you accomplish this, a full-grown Yoshi will replace the Yoshi egg that was added to the lower right corner of the title screen. (Note that the change in sky color from blue to tan is a function of finding all 100 A-coins.)