Pre-last post response:
Handling AI Calculations will depend on more than the number of tiles on the map. The time and space complexity of calculating AI is more influenced by the properties and attributes of units and tiles more than the size of the map. For example, I’m making a turn-based tactical game similar to Advance Wars. You have to consider terrain type, terrain defense, travel characteristics over that terrain (or not), attackability, mobile range, attack range, fog of war, unit cost, unit health, unit ammo, faction (enemy or ally), and whatever other features you’ll want in your game. You can consider caching some of this info in the background to save on calc time between turns, at the expense of RAM. And, it will also depend on how long you would like your player to wait until the turn is calculated. Maybe you wouldn’t want your player to wait more than 10 seconds to resolve a turn. Then set that as your benchmark, and see how much calculation you can get in that time. And continue to optimize the AI to fit within that benchmark. Every one of those subsystems will make your AI more complex, and will obviously take longer to implement, tune, and polish, which quickly becomes an issue of how much time you want to devote to make it fun.
Post-last post response:
Leaders, Loyalty, vices and virtues, alliances, diplomacy sound like more attributes to check against in AI. As I stated above, all of this will be factored into calculating the AI, and my general rule, for a small team, is that each feature you add increases the complexity of the implementation exponentially. So, as you get more complex, your programmers will have to prepare for the long haul, as fixing bugs and getting large test coverage for all the different possibilities and cases can get out of control easily. This also means you’ll need to eventually recruit QA to test these cases.
“What would this involve?”
There’s still not enough of a game design to throw out a proper estimate for one AI engineer to implement all that in a game. I could say that it could take an AI engineer 1 or more year(s) to do all that, but I couldn’t tell you how accurate that is.
The AI can involve many different sorts of algorithms. Some keywords are A* pathfinding, quadtrees, influence maps, decision trees, behavior trees, utility theory, fuzzy logic, etc.
Your AI engineer may implement some or all of these. He/she would have to then adapt those systems to the game logic itself, and the game itself will most likely have its own level of AI:
For example:
http://gamedev.stackexchange.com/questions/21519/complex-game-ai-for-turn-based-strategy-games
Tactical AI on the unit level
Operational AI on the war front
Strategic AI for the faction/empire
Grand Stategic AI for long term goals for winning
And once this gets to a satisfactory engineering implementation, you still have to make sure the game is actually fun! You may need to remove some sorts of features of the game that will affect the AI, which means you’ll have to go in and either gut them or change them, which is more time.
Let’s assume you get to a point that the AI systems work and the game is fun. But then you realize that it’s slow as hell. This is where your AI engineer will have to use a Profiler to investigate where the slow downs occur. Suppose you want 10 seconds max deliberation from your AI, and currently it runs at 35 seconds on the target machine. The AI engineer will determine where the slowdowns are in the profiler.
The engineer then investigates solutions for reducing this time to the target.
He/she will refactor those subsystems, implementing more code to help minimize calculation time.
One of those solutions, you may find that C# runs too slowly for doing mass calculations for one system. And the solution may be to have those calcs done in native code. The AI engineer will then standup a native dll that contains all the AI calcs, and hook it into the game.
Rinse and repeat until the game is fun and runs well!
So, all of that, you can set aside a certain amount of time for. In reality, reducing the number of features helps tremendously, especially since you personally don’t have any benchmarks for how long it will take.
Of course, your AI engineer will know better of the time and effort it will take to complete (or will he/she?). Typically, if you get an estimate from them, double the time, and that’s how long it will take, given the current feature set (That means, without changing the feature set later on, which almost always happens anyway).
Take a look at the Shattered Throne blog by Checkmark games. He has a series of AI videos about his implementation.
Good luck!
