Well, when playing a random map game, first select all your villagers and make a house, after completing construction, send them all to gather wood and make more villagers from your town center and make them gather food from sheep. Continue till you have enough resources to make a mill and a barracks. Then advance to the Feudal age. In the Feudal age, you can concentrate on making your army. Your goal should be to advance ages as soon as possible while building your army. Also, don't forget to research technologies.
Also, while your villagers are gathering stuff/constructing stuff, send your Scout Cavalry to scout the surrounding areas. A quick way to do this is by selecting your scout cavalry, hold shift and right click all around the mini map randomly (and a lot) then right click on the main map. The scout cavalry will follow every point you clicked and keep going while you concentrate on building your base. Take note on whenever the scout cavalry makes enemy contact and retreat if possible, cause if you lose your scout cavalry in the dark age, you cannot make another one till the feudal age. If you lose your scout cavalry, you will have to use your Militia to explore the map.
Edit : This is only a startup plan, you will have to develop your own strategy according to the situation.