Вместо мотания героев туда-сюда можно попробовать подготовить сильных 3-4 героя, один с войском, три с магией и послать в разные стороны захватывать всё нейтральное. А когда обнаружится живой противник, то надо собирать уже силы в один кулак и ехать его бить. Если он сам едет к тебе за тем же, то встречать
Важно - нужно иметь БЫСТРЫХ в движении героев - хоть от логистики, хоть от артефактов, хоть от заклинаний, иначе пока твой герой доедет до вражьих рубежей, его герои твою страну уже из края в край разорят.