The first time you encounter the Mad Batter is in the Mysterious Woods. Once you have the Power Bracelet from Bottle Grotto, find the area of the woods that has a Moblin armed with a sword and shield. There is a lone stone nearby; pick up the stone to reveal an underground passage.
The passage leads directly to Mad Batter’s altar.
For the first upgrade, I recommend selecting Bombs. If you get the upgrade immediately after finishing Bottle Grotto, you will be glad to have the extra bombs as you travel through Ukukku Prairie, Kanalet Castle, and especially Key Cavern.
The second location is a bit trickier to reach than the first. Directly east of Toronbo Shores, there is an area with many of bushes surrounding an underground path. You are separated from the bushes by several holes in the ground.
The easiest to get across is to use the boomerang to cut the bushes from a distance. You can then use the Pegasus Boots and Roc’s Feather together to jump across the holes. This method requires that you first retrieve the Hookshot from the nearby Catfish’s Maw because you cannot get the boomerang without the Hookshot.
It is possible to get the upgrade before entering Catfish’s Maw, but it requires a little more work. Equip Roc’s Feather and your sword and try to jump across the holes without the Pegasus Boots. You will fall in one of the holes, but before you do swing your sword. If done correctly, you will cut one of the bushes and give yourself enough landing space to use the Pegasus Boots and Roc’s Feather to jump across.
Once you’re in the underground tunnel, you will need the flippers to swim to the exit. You will emerge in a small closed off area northwest of where you began. Head west (you cannot go any other way) to find the entrance to Mad Batter’s altar.
For the second upgrade, I recommend arrows. After you complete Catfish’s Maw, your next destination are the South and North Face Shrines. In the South Face Shrine, you will fight many Armos and one Armos Knight all of whom are weak against arrows. Likewise, the North Face Shrine contains Wizzrobes and Pols Voice: two enemy types that are weak against arrows.
Tal Tal Mountain Range
The last upgrade is on the path to Turtle Rock and directly west of the Wind Fish’s Egg. You can reach this area as soon as you have the Hookshot, but it will be very out of the way. The most convenient time to pick up this upgrade is when you are ready to explore Turtle Rock.
The entrance to Mad Batter’s altar is underneath a stone on the peak of one of the mountains. To reach it, you will have to travel east through the Mountain Range and then cross the bridge that leads west. On the western side of the bridge, there is an underground passage hidden under a bush.
The underground passage will lead you to the base of the western mountains. Follow the stairs leading up the mountain, and be careful to avoid the falling boulders. At the top of the mountain, there is a treasure chest, two Mini-moldorms and several stones. The westernmost stone hides the entrance to Mad Batter’s altar.
I recommend saving the Magic Powder upgrade for last. The Magic Powder can be a fun item to experiment with, but it is rarely required and is never required in large amounts.