Heroes III was indeed a very, very nice game indeed. I remember happening upon it due to a friend of my little brother's, who had brought it with him on one occasion. I think me and my little brother spent hours upon hours in Hot Seat mode competing with each other and the computer. We never actually finished one of those games - somehow we liked building up an army more than losing any of them.
Aaah, the memories
