[PaoloZ]

I agree with Graeme. It is not a hard task. A* should solve the problem quickly as the adjacency graph of the map is quite simple. The destination of an army is already stored, so it has to be changed the way the value is used and kept between turns (at the moment it is wasted every turn).

How the AI plans an attack?
I mean: if the AI has to attack your lands with an army assembled at their home province (assuming a distance greater than 1 between their home land and your lands), doesn't it plan a course?
Is this not pathfinding (maybe it's a greedy algorithm)?

The AI does not seem to push its armies around in a random pattern.