Envelopment with horse archers is also pretty much exactly what I would have done. I wonder if a working skirmish function with HA makes it easier for the AI to handle these units.

The fact that they fire at the most vulnerable unit instead of the closest one is good, too.

You would have won that battle easily in R:TW.