AI minimax proposal

[gladoscc]

Civilization is a pretty deterministic game. There is still luck involved in combat, but we can ignore it for a minimax AI. Given enough processing power, the AI will be able to make the best moves, every single time. It will be able to handle whatever promotions you throw at it, as long as the combat simulator is correct. The biggest downside to minimax is speed.

However, this can be improved in many ways:

1) Alpha beta pruning significantly reduces branches taken
2) Quick evaluation (combat simulator) - the sim will forget about luck. (The game still has luck, the algorithm just discards it)

Even if those two features were implemented, it would still be far too slow, as the time taken is also based on the amount of enemy units. So, I propose the following:

1) Current AI - when there is no hostile unit (at war) within 5 tiles of the unit
2) Minimax - when there is a hostile unit within 5 tiles of the unit

The current AI could be substantially optimized (ie make it forget about combat, since it the minimax will take over) and it will not impact the military effectiveness of the AI much.

With the improvement in AI war tactics, this should mean that fewer units will be needed by the AI. You should be able to expect the AI to only need 20% or 30% more firepower than you to have a tie in battle, compared to the current 100% or so.

TL;DR:

Pros:
AI will make nearly the best tactical choice
AI is very adaptive and only relies on combat simulator.
AI will need far fewer production bonuses
Speed of the AI should not change significantly
Minimax is GREAT for multicore processors. 8 cores, (roughly) 8 turns AI speed.

Cons:
AI will not position units as well in advance of combat.
AI will need to able to see through fog, only 5 tiles away through.
Players will need to move down a difficulty level or two.

Just my 2 cents, feedback is welcome

 

[sparkyal]

I'm not sure what "alpha beta pruning" is. Could you explain your algorithm in more detail?

In general, i do like the idea of an AI that handles combat better and if they get reduced bonuses. however, i do not think that combat is the only factor in this. I think some changes in diplomacy may also be required too.

oh, and i don't like the AI being able to see through the fog..

 

[RD-BH]

flat 5 ... no.
visible 5 ... maybe.

visible unit, 8 tiles down a road, is also a threat.

Seems exploitable by player unless additional AI changes are made.

references:
Minimax
Alpha-beta

 

[col]

Tree algorithms like this are Ok in chess where there is a relatively small number of choices. They dont work in 15x15 Go where the tree becomes unmanageable very quickly. I cant see they will therefore be much use in Civ where the number of squares and pieces is so much larger still.

 

[RogerN]

Not only does Civ involve a larger number of pieces then chess, but each player can also choose to move *all* of their units on *every* turn. That's an insane number of permutations compared to a game like chess.

If I've got 10 units and each unit could potentially move to 10 different tiles, that's 10^10 positions to evaluate. Alpha-beta pruning can't help yet because we're talking about a single turn with no look-ahead. We haven't even started to consider the enemy's moves.

So the minimax algorithm is already impractical with just 10 units, and a game of Civ has many, many more than just 10 units...

 

[gladoscc]

Not only does Civ involve a larger number of pieces then chess, but each player can also choose to move *all* of their units on *every* turn. That's an insane number of permutations compared to a game like chess.

If I've got 10 units and each unit could potentially move to 10 different tiles, that's 10^10 positions to evaluate. Alpha-beta pruning can't help yet because we're talking about a single turn with no look-ahead. We haven't even started to consider the enemy's moves.

So the minimax algorithm is already impractical with just 10 units, and a game of Civ has many, many more than just 10 units...

Oh, crap, I forgot about all units being able to move

 

[joncnunn]

One thing:
Those algorithms were all designed around 2 player games:

In my turn I make the best move for me; in my opponents turn he makes the worse move for me.
In a two player game worst move for me is his best move, but that breaks down when you add a 3rd player.

 

[qemist]

Civilization is a pretty deterministic game. There is still luck involved in combat, but we can ignore it for a minimax AI. Given enough processing power, the AI will be able to make the best moves, every single time. It will be able to handle whatever promotions you throw at it, as long as the combat simulator is correct. The biggest downside to minimax is speed.

However, this can be improved in many ways:

1) Alpha beta pruning significantly reduces branches taken
2) Quick evaluation (combat simulator) - the sim will forget about luck. (The game still has luck, the algorithm just discards it)

Even if those two features were implemented, it would still be far too slow, as the time taken is also based on the amount of enemy units. So, I propose the following:

1) Current AI - when there is no hostile unit (at war) within 5 tiles of the unit
2) Minimax - when there is a hostile unit within 5 tiles of the unit

Units don't move, players do. So every possible combination of unit moves and build orders and research orders and tile improvement orders must be considered, with ordering of unit moves significant. This would be too hard. I suggest decoupling by assuming independence of unit moves, build orders, research orders and tile improvements, and hierarchical decomposition of unit moves by grouping units into formations (armies, if you like). Formations would be groups of units close to one another with a common purpose. Notional army commanders would decide the moves of units in their formation with a top level AI allocating units to formations and issuing general policies (such as "attack A"). This would correspond to real armies where operational decisions are made by local commanders.

 

[gladoscc]

Units don't move, players do. So every possible combination of unit moves and build orders and research orders and tile improvement orders must be considered, with ordering of unit moves significant. This would be too hard. I suggest decoupling by assuming independence of unit moves, build orders, research orders and tile improvements, and hierarchical decomposition of unit moves by grouping units into formations (armies, if you like). Formations would be groups of units close to one another with a common purpose. Notional army commanders would decide the moves of units in their formation with a top level AI allocating units to formations and issuing general policies (such as "attack A"). This would correspond to real armies where operational decisions are made by local commanders.

This is for unit AI, not for building AI. You can't do minimax with building AI.

 

[qemist]

This is for unit AI, not for building AI. You can't do minimax with building AI.

Why not?

 

[schmop]

How about very localized minimax? A first pass would try to identify "arenas" on the map, each with no more than a few units, and run a best move search on each of them separately. Of course, the search would not take into account units entering the arena (ie. units that were far from a battle center at it's start, but join it a small number of turns later)...

Or a database with billions of precomputed responses to specific situations. A querry would be sent to the database by sending it the state of the surrounding hexes of a given unit, and it would reply the best move for that unit. There would also be a problem here with the amount of information involved: the more surrounding hexes the database takes into account, the more entries it must contain. But at least it's now a storage issue and not a computing one. And the number of entries can be reduced by simplifying the information given for a hex:
-instead of using unit types, it should use the general categories (melee, ranged...) accompanied by their relative strength (stronger, weaker...)
-instead of hit points, just 'helthy', 'wounded' or 'critical'
-units on distant patches of hexes could be aggregated into a single logical unit (a more strategic kind of information)
Actually, the more I think about it, the more this seems like it could work well... Ok, now I'm sure, this is the utlimate approach. Defintely. End of discussion. Get to work firaxis.

 

[Camikaze]

Moderator Action: Moved to Ideas & Suggestions.

 

[glider1]

How about very localized minimax?

Yeah I agree that it would be possible. You would have to somehow build an algorithm that can determine the tactical hotspot areas on the map as they are dynamically forming, and then apply some limited depth algorithms to that reduced area. I think a hybrid solution like this makes sense, but there is a lot of computer science to make it work. With multiple processes working in the background, there is a lot that could be done. Outside of these hotspot areas, the unit AI would fall back to it's current implementation, which seems be the traditional unit AI.

Cheers

 

[Hail]

AI's thinking should be goal-oriented. setting goals and creating plans to achieve them is imho where the AI's competence will increase the most

making moves for the sake of making moves is pointless imho. a lot of the branching being talked about will be eliminated since those branches will not advance the AI toward it's goal

on second thought the branching factor can be further decreased by using a different representaion of the world's state and/or by decomposition(city AI for city management, combat AI for combat, etc.)

 

[schmop]

Yes, the AI should be goal oriented but I would argue that there are two levels of AI: strategic and tactical. The strategic level is mostly concerned with goals on the long term and I'm under the impression that the current AI implementation isn't too bad at this: it chooses a path to victory, identifies obstacles on this path and even tries to recognize other player's strategies.
The tactical level however is more about micro management of units. This is where CivV sucks and where minimax could potentially come in. And minimax is not incompatible with goals. A typical minimax implementation will stop it's in-depth search of moves at some point, and will try to give a score to the resulting state of the map. You just need to include your goals in the score calculation. Say you want to capture a city, then the lower it's defenses at the end of the search, the higher the score (a lot more stuff is needed in the score calculation to avoid crazy behaviors though).

 

[qutsemnie]

A lot of the criticism to a minimax approach hold kernels of validity, but personally I think it could be done. It couldn't be done in a scripting language. This absolutely requires a optimized compilation.

In regards to the criticism:
1) Regarding the entire world: only the AI units near the human need special treatment. AI never has an advantage versus the AI. The reason for the advanced technique is to offset human strategic insight.
2a) Regarding branching factor of go: the issue there is that a go move can be played anywhere and it is difficult to heuristically pick out moves to explore early in the tree.
2b)The other issue is that the goal there is to be as good as humans; not merely be better then a rule based AI. Here the goal is to be better then a rule based AI; not to be as good as humans.

More on 2a) Chess can provide some insight. Back in the day it wasn't as feasible to explore every move everywhere that could be made deep into the tree. They were pruned early. The difference between go and chess is that chess admitted certain heuristics that made valuations fairly good. Material for example. Go you don't necessarily know material is lost or gained until you are deep in the tree. Civ 5 is more like chess in that regard in that 2 moves in you know material is lost. You can stop pretty safely if you are getting a bad exchange or drop other branches if they are not giving you as much human material as the current branch.

In the end, I know this: chess AI was horrible until people started to one up each other. Giving up to early on an AI problem is bad. I think this one could be done, but with significant engineering effort.

More on 2b) You don't even necessarily have to find the best attack. You can just use a look ahead to decide if the current attack is failed if your opponent plays like the AI in response. The current AI of civ doesn't even do that! For example, it will rule based move forward into range of archers, get attacked as the AI would, and then rule based retreat. That tells you that it isn't even checking to see what an AI would do to itself. That is basically a one level alpha-beta with a much reduced exploration of the branches. Embellishing on that theme to slightly mutate AI moves would improve it without having the lofty goal of being as tactically adept as the best humans.

 

[glider1]

1) Regarding the entire world: only the AI units near the human need special treatment. AI never has an advantage versus the AI. The reason for the advanced technique is to offset human strategic insight.

Gee that is a good idea. That is the single most positive way forward in my opinion for the tactical AI. After all we humans really do not care how one AI tackles another AI in the fog of war. So long as the AI is achieving it's tactical goals against another AI at a rate that we humans can accept, the current implementation for AI verses AI would be fine. We humans don't need to know the details. But when the AI comes into a human's visibility area, a scale-able minimax algorithm is switched in and applied to a limited area within that visibility (according to the processing resources available). The goal of the minimax algorithm is actually not to quantitatively improve the AI relative to the current AI (that is a side effect). The goal is to make the AI qualitatively more dynamic against humans. But always the minimax algorithm has the option to fallback to the current AI. There are distributed computing systems for doing massively deep minimax solutions such as the "Let's Check" feature of Fritz13 by Chessbase which can reach 30 ply in seconds! But that does not work for civ because it uses previously computed position searches (I am guessing). If we try to implement a complete minimax AI, for AI verses AI warfare in the fog of war, it is simply too inefficient and wasted computer cycles. If we wait another few years we will have exciting new technology (like cloud processing and/or new AI technologies), but can we wait that long? At the moment the balance in Civ5 is all wrong. The strategy layer is simplified on the assumption that the tactical layer is more complex, but there is little challenge building beautiful tactical formations against an AI that is currently unable to even remotely respond in kind. It's a bit like playing someone at darts in a pub, but they are blind and had to much to drink and they have trouble even hitting the dart board let alone the target. In that situation everyone has to pack up and go home.

EDIT: a simpler non-minimax idea that probably does not work, is to assume that the current AI does have some formation logic mechanism. After all we can see it forming at least one type of formation in preparation for attacking a city. Let's hope that this idea is extendable. For example you could build a big library of formations that are defined in XML. Modders could build XML libraries and over time they could get quite large. It would give the non-computer science community something useful to contribute to the AI. I know the problem is that the movement rates vary according to terrain and tactical distractions, and as such the formation cannot properly form, but perhaps if there is a library of 50 formations and the AI is able to attain one of those formations with a probability of 50% and with a purity of 75%, it's better than having chooks running around the barn floor like we have now, firing whenever they are scared of something.

Cheers

 

[schmop]

If someone wished to give it a shot, would the modding API allow him to? I've never modded for CivV but just looking through the popular modding guide it seems to be all about adding content and changing the interface...

 

[glider1]

Hi schmop. The Lua API does seem to have ways to assign combat flavors to units which can be programmed in Lua and probabilities assigned in Lua and the core would recognize it and add it to the calculations. The API documentation is really sketchy but Thalassicus over at VEM has noticed it. Therefore you could assign new behavior to siege for example. But modders are reluctant to do this because like qutsemnie said, AI work really needs to happen in the C++ where the real efficiency and power resides.
Cheers

 

[qemist]

In regards to the criticism:
1) Regarding the entire world: only the AI units near the human need special treatment. AI never has an advantage versus the AI. The reason for the advanced technique is to offset human strategic insight.

I think that idea is ugly, would offend human players, and doesn't make sense. It's equivalent to the AIs ganging up on the human player. It is (apparently) a combat tactics generator that is going to "offset strategic insight". If your opponent has better strategy then you do better by improving your own strategy, not by improving your tactics.