This time around it won’t be to solely focus on movement, but all of the game elements. The first step will be to weigh the worth of making both land and sea units or just land. As it stands now sea units are more likely to be lost in a noncombat way and would take away useful resources. The next step is to apply a strategy used in the game that can be used against other strategies without causing a lack of decisions to be made.
The safest way to play this would most likely to have the AI discover the world and from there focus cities when found and enemies when near. The overall plan is simple but the implementation could be difficult. There is a possibility to use a pathfinding algorithm to start off the movement, then a sorting algorithm to find the furthest spot and what is most useful. A behavior tree or state machine could work well in how the AI responds to the multitude of events that may occur.
More planning will happening as the actual code is written where upon completion of one aspect more must be thought out. It will be a time consuming step by step process that will take a decent amount of care when considering the game this ai is for.