Play fast, thats all. Never go back with main hero, use scouts to bring army to him (you have 5 heroes by month 3, I had 25, all with expert estates and luck so they produce both resources and mithril daily, you have to plan those things in advance, map is getting harder and harder).

Get navigation soon. Get all fortresses before week 3, then get town portal and go for barbs. Then barbs are easy to kill if you or them are inside the castle walls. I bet you tried in open field and that is suicide.