Chep
Emperor
This is my strategy, that I successfully used to win a UHV-victory with Arabia before the spawn of the Ottomans (with the old download-version of RFCE and also a current SVN-version):
With your starting units you should be able to take both Byzantine cities just north of your starting area. Once this is done send all available archers to defend them and your remaining horse archers to take Alexandria.
Jerusalem (Yafa) should only (!) built spearmen. It is tempting to build a house of wisdom or a heroic epic here. Don't. (Well, you can, once you have ~4-6 spearmen and feel safe enough)
I usually use the additional settler you have upon start to found Al-Quahira just north of the marble in Egypt. While this city doesn't have many workable tiles, it has lots of floodplains which each give +5 food when improved with a farm! (also the marble is nice for the heroic epic and maybe later the mezquita)
in the north it is all about defending the status quo, so build some walls and defenders:
I also always use Tyre to build some ships (1st: war galley, 2nd: galley) to explore. With some luck you meet Bulgaria and France and can trade some techs. Especially meeting Bulgaria around the time you have Ghazi (or earlier) is important!
Your remaining horse archers from the conquest of Alexandria can now move along the North African coastline. Depending on how many you have, you might be able to take the Byzantine city there and/or Tunis.
Now make peace with Byzantium. Alexandria/Al Quahira can easily build the settler you need for the last city in Arabia, but first them grow a little.
You should focus on building troops (spearmen, mostly) and walls in your cities for now. Alexandria and Al Quahira can also build houses of wisdom, granaries and other improvements, but all other cities should focus solely on units and walls untill you get Ghazis. Careful, once you research Farriers, some barbarian Ghazi will attack south of Jerusalem, they will probably kill most/all of your spearmen, but this should give you enough time to build some Ghazi of your own.
I always give them the flanking (retreat) promotions but combat (strength) also works.
Also: keep your eyes open for the great Nubian mercs (they're basically longbowmen!)
Once you have 3+ Ghazi to defend Jerusalem against the barbs, you can send your next few along the North African shore to capture Tunis.
By ~900 AD you should get lucky and Byzantium declares war on someone who isn't you (you've been nice to them after the initial conquests, right?), so join them and get open borders (yeah!).
I always send 3 Ghazi to cross the Byzantine lands (who know how long the cooperation will last, after all) and try to meet the "Europeans" (Hungary, Germany, etc).
3 Ghazi are usually enough to take some independent city somewhere:
(the Polish capitol is also a great city to conquer just after they found it)
As you can see on the minimap, I haven't expanded beyond the UHV1-area but my ships have explored most of Europe.
But from the time the Byzantines open their borders to the moment my European city/cities are ready to pump out missionaries, Tarabalus and Dimashq have almost non-stop been building missionaries and kept sending them to all the Byzantine cities. Byzantium will eventually remove Islam, but if you keep sending them in you should get at least 2/3 of their cities to embrace your religion
Once my European city is ready, it takes over production and Tarabalus/Dimashq build Ghazi/Workers to send to Europe.
I always try to get Hungary and the Norse to open their borders to me and send in some missionaries, often they will convert
Of course your presence in Europe won't be well liked and some idiot will declare war on you...just don't fight them but send your Ghazi towards another juicy target and gift the endangered city to some civ close by.
Milan is a great target, Genoa can be (though you will need more like 5 Ghazi here) or any other independend city you encounter.
Although it is really easy to accomplish, you shouldn't forget UHV2, usually Alexandria & Al Quahira are enough to produce settlers and Ghazi for this, you just shouldn't forget it
I recommend placing the settlers in their positions and settling 1 turn before the time limit is up, and then gifting all North African cities but Tunis to Cordoba (Tunis can produce a galley and join in in the missionary-spam)
Once you reach the 30-32%, you should try to get either Germany or France to open their borders to you (usually by joining in on of their current wars). Et voila.
So far, I've won in 1320 and 1323 respectively
With your starting units you should be able to take both Byzantine cities just north of your starting area. Once this is done send all available archers to defend them and your remaining horse archers to take Alexandria.
Jerusalem (Yafa) should only (!) built spearmen. It is tempting to build a house of wisdom or a heroic epic here. Don't. (Well, you can, once you have ~4-6 spearmen and feel safe enough)
I usually use the additional settler you have upon start to found Al-Quahira just north of the marble in Egypt. While this city doesn't have many workable tiles, it has lots of floodplains which each give +5 food when improved with a farm! (also the marble is nice for the heroic epic and maybe later the mezquita)
in the north it is all about defending the status quo, so build some walls and defenders:
I also always use Tyre to build some ships (1st: war galley, 2nd: galley) to explore. With some luck you meet Bulgaria and France and can trade some techs. Especially meeting Bulgaria around the time you have Ghazi (or earlier) is important!
Your remaining horse archers from the conquest of Alexandria can now move along the North African coastline. Depending on how many you have, you might be able to take the Byzantine city there and/or Tunis.
Now make peace with Byzantium. Alexandria/Al Quahira can easily build the settler you need for the last city in Arabia, but first them grow a little.
You should focus on building troops (spearmen, mostly) and walls in your cities for now. Alexandria and Al Quahira can also build houses of wisdom, granaries and other improvements, but all other cities should focus solely on units and walls untill you get Ghazis. Careful, once you research Farriers, some barbarian Ghazi will attack south of Jerusalem, they will probably kill most/all of your spearmen, but this should give you enough time to build some Ghazi of your own.
I always give them the flanking (retreat) promotions but combat (strength) also works.
Also: keep your eyes open for the great Nubian mercs (they're basically longbowmen!)
Once you have 3+ Ghazi to defend Jerusalem against the barbs, you can send your next few along the North African shore to capture Tunis.
By ~900 AD you should get lucky and Byzantium declares war on someone who isn't you (you've been nice to them after the initial conquests, right?), so join them and get open borders (yeah!).
I always send 3 Ghazi to cross the Byzantine lands (who know how long the cooperation will last, after all) and try to meet the "Europeans" (Hungary, Germany, etc).
3 Ghazi are usually enough to take some independent city somewhere:
(the Polish capitol is also a great city to conquer just after they found it)
As you can see on the minimap, I haven't expanded beyond the UHV1-area but my ships have explored most of Europe.
But from the time the Byzantines open their borders to the moment my European city/cities are ready to pump out missionaries, Tarabalus and Dimashq have almost non-stop been building missionaries and kept sending them to all the Byzantine cities. Byzantium will eventually remove Islam, but if you keep sending them in you should get at least 2/3 of their cities to embrace your religion
Once my European city is ready, it takes over production and Tarabalus/Dimashq build Ghazi/Workers to send to Europe.
I always try to get Hungary and the Norse to open their borders to me and send in some missionaries, often they will convert
Of course your presence in Europe won't be well liked and some idiot will declare war on you...just don't fight them but send your Ghazi towards another juicy target and gift the endangered city to some civ close by.
Milan is a great target, Genoa can be (though you will need more like 5 Ghazi here) or any other independend city you encounter.
Although it is really easy to accomplish, you shouldn't forget UHV2, usually Alexandria & Al Quahira are enough to produce settlers and Ghazi for this, you just shouldn't forget it
I recommend placing the settlers in their positions and settling 1 turn before the time limit is up, and then gifting all North African cities but Tunis to Cordoba (Tunis can produce a galley and join in in the missionary-spam)
Once you reach the 30-32%, you should try to get either Germany or France to open their borders to you (usually by joining in on of their current wars). Et voila.
So far, I've won in 1320 and 1323 respectively