One of the things we looked to do in CK2 is make the traits and abilities of the commanders become as important as possible. To this end we removed dice rolls and replaced them with combat tactics. Combat tactics affect the power of the unit types in either attack or defence. Before you ask, yes, they are fully modable.
The random factor in combat is all in the selection of the tactics. The combat tactics use the same scripting logic as events. You first have the trigger block that determines when a tactic is selected. One use we put for this feature is to restrict certain tactics until combat has run a certain amount of time (the transition from skirmish to melee phase is one example of this)
The real magic is in the next part; the “mean time to happen”. This is the weight that each valid tactic gets. The game will then roll a dice to select the tactic. Here we can do neat things like weight the tactic selection looking at the flank force composition and also my military ability and traits of the commander. This gives us structured randomness; yes, sometimes your amazing general will not pick the right tactic, but more often than not he will.
The other nice thing is that instead of rolling a dice roll you get a name. So instead of Robert the Bruce rolling a 9, Robert the Bruce unleashes an awesome charge sweeping the English off the battlefield. I don’t know but the second just sounds so much better.
Anyway, there is a brief rundown on combat tactics. I just leave you with one last lesson, check to see if your bastard offspring are not imbeciles before legitimising them, otherwise you need to have a handy bishopric empty.