You start with an almost fully functional base, so make some minor tweaks and constructions here and there to get it up to full capacity. You start with a decent attack group of ghouls, abominations and heroes so head to the west and destroy the two human buildings you find there. North of that there is an archmage (not one of the ones you're looking for) who has a health stone on his person. I never use health stones, the regeneration effect is nice and with Arthas already improving regen having both heroes with 1 health stone is pretty helpful.

East of your base is a merchant where you can purchase scrolls of healing. Using one of these before a battle within the damagine field can ensure your units are at full health for the action. Now, take that force you started with and go slay the first Archmage. Hopefully this is happening while your base is producing its first frost wyrm. When you've eliminated the first Archmage the first barrier will drop and your unit should stop taking damage from it. I now sacrificed an acolyte to make a shade and sent it to explore inside the castle. Near the first archmage to the southeast there is a room with two riflemen and a defense tower. I eliminated them for good measure and was attacked from the north by a weakling archmagi and a few sorceresses. Nothing too challenging, just scout ahead with your shade.

Your overall destination isn't a big secret, as the location of the second archmagi is revealed to you. However you should be on the lookout for a few sorceresses guarding some big crates. Destroy the crates (after the sorceresses) and you'll release two rock golems. These can be pretty helpful to you as you might have guessed. They're not quite as powerful as abominations but hey, they're free! I encountered an entire human base in here and it wasn't too hard to wipe it off the map, but it was somewhat time consuming.

When you're ready to take on the second archmage, take the right path as this is a sort of maze. They just want to slow you down a little before you get to the archmage. But on that right path there is a fountain of health where you can very slowly regenerate your health if Arthas has the unholy regeneration skill at full. Note that units with low hit points (crypt fiends) will die slowly even near this fountain as they just don't regenerate fast enough. I do recommend healing some here, if it's feasible. You can push forward more with fewer losses and progress is nice.

The second archmagi is a joke like the first one. I found a pair of boots of elvenkind +6 which increases agility and gave it to Arthas. There is another crate here which you should destroy as it releases an ogre magi who will join your cause.

Now, do some more scouting with your shade. There isn't a whole lot of scouting to be done however, but, as they say, knowledge is power. There is a magic vault to the northeast of the fountain of health and a blue (human) base you'll need to conquer. The cannon tower should be eliminated by some meat wagons while your other units crack open that magic vault and the guards around it. Inside you'll find various treasures including an item which improves mana regeneration for all the units around the hero, a tome of intelligence and another item which gives the hero +300 mana. I gave it all to Arthas as he is always running out of mana using death coil. He's really powerful with this stuff and a maxed out death coil attack.

Now, once the blue base is destroyed, you'll have a very short distance to go to get to Antonidas. I used my shade to have a look as far as I could and it managed to make it almost all the way before it died. I chose to go in and fight a small skirmish then leave and heal up a bit as, at first there are several sorceresses and a knight guarding two cages. Upon breaking open the southermost cage you can discover two flying sheep which turn into blue drakes.

Take all your undead out of the barrier and let them heal while the units unaffected break open the second cage to reveal five large spiders. Use the spiders as a distraction while your other forces rush toward Antonidas. That is, send the spiders in first and get them to draw the fire of the guard units. Antonidas is level seven but he should fall pretty quickly if you have an attack group with abominations and drakes as well as your heroes. With Antonidas dead the final barrier collapses and you reign victorious.