This question was asked so long ago that I think it deserves a better response now. In general, for reinforcement learning, this problem is called the "sparse rewards problem". This Medium article covers the problem and some solutions, but you can find a lot more solutions just by running a search.
Instead of going into the details of algorithms that solve this problem, I'll instead point you to a few key successful applications of solutions to this problem along with short, general descriptions:
AlphaStar by Deepmind
StarCraft II is nearly exactly like Age of Empires, and AlphaStar was able to beat some of the best players in the world at the game.
Here, they created a tournament system for the AIs playing the game, and also generated different playing styles and strategies that the AIs would follow. Then, they used a genetic algorithm to modify the top AIs so that they slowly improved, making sure that the best AIs played against all different types.
OpenAI Five by OpenAI
(Here's a cool clip showing OpenAI Five outsmarting one of the top players in DOTA.)
OpenAI Five plays the game of DOTA, which is nearly exactly the same game as League of Legends. Here, they preprogrammed some of the more decision-tree options that would drastically change gameplay, such as what items the heroes buy, but then let the AI choose the rest of the options. (Though, note that the premade build options meant that it didn't understand / didn't expect some combos of heroes + items that you could play against it.)
To get the the five different heroes to play together, they let copies of the same AI control each of the heroes, and rewarded each of those AIs for how well the team did in addition to how well each individual hero did. This allowed the training to start at the individual level and then eventually expand to group play.
The OpenAI Five model is also nice because it's fairly general. They used the same training process in order to create Dactyl, which can manipulate a cube in a hand.
Other than these two, I haven't seen too many other AIs that play complex games with many different options for making moves. My guess is that it requires tons of compute power, and OpenAI and Deepmind are the only ones with that sort of compute power. This article argues that this may be due to the tree representation often times used by computer scientists.