How Should Beyond Earth Handle AI Difficulty Scaling?

[stealth_nsk]

In general how's this: 2 separate difficulty levels. Economy difficulty would be the gold and hammer bonuses we're used to from other games. Combat difficulty would gradually add in a sort of library of tactics. E.g. "Private" = units just walk towards nearest enemy. "Corporal" = units use terrain. "Sergeant" = AI builds army composition tailored to its war target. "Captain" = Uses suicide worker decoys or whatever

This would work in game like XCOM (and was actually suggested for it by fans). For game with Civ5 tactical combat even the best combat AI will be no match to human player. Making it even more stupid is not a good idea.

 

[JokerJace]

Yes, sounds nice in theory. Now apply that to a decision making routine for moving units such that you get 5 different AIs in equal increasing steps of difficulty.

No problem at all. You know what Alpha–beta pruning is? The search depth for a local positioning optimization could be determined by the difficulty. For example.

 

[Biz_]

i can't say what it should do without knowhing much about the game, but it definitely shouldn't get a 200% bonus to everything (i.e. civ 5) and still be completely incompetent at providing a challenge

 

[Trias]

No problem at all. You know what Alpha–beta pruning is? The search depth for a local positioning optimization could be determined by the difficulty. For example.

And what are the current values of those parameters? Is varying around them even a realistic option?

Search depth in typical civ AI routines is usually exactly one move (i.e. the one being considered). So that was a rather naive example.

I'll elaborate why search depth algorithms are not really feasible for civ-like games.

Suppose for the moment that:
a) combat in civ is deterministic (it is not adding additional complications)
b) You have a robust method of localizing decision making to a single "combat theatre" contain 10 friendly and 10 enemy units. (It is not obvious that this can even be done.)

For simplicity of the argument assume that all units have two movement points and all terrain is flat. Consequently, each unit has 19 valid moves. Suppose that you can prune this down to 5 viable moves per unit (again not that simple). This means that a single turn of civ already consists of 5^10 =~10 million possible moves. At this, point you have not even considered the possible responses of the opponent.

As you can see the combinatorics quickly spiral out of control even for a single turn in a very controlled situation. In reality, you do not control the number of involved units that well. A big risk of implementing a depth search is that in the late game the combinatorics even for one turn blow up turn times to unacceptable levels.

In practice what the AI routines do instead is that moves are evaluated in sequence one an individual basis. A context based heuristic is used to determine the best move for a unit. The move is executed and the routine moves to the next units with an updated heuristic. The AI will only play as well as the heuristic logic. It is really hard to write a heuristic that is slightly worse than another in all situations. It is easy to find one that is consistently a lot worse, but a heuristic that is slightly worse in one situation may quite well end up being slightly better in another.

Note that some attempt was made to make the civ5 decision making scale with difficulty: (from one of the prerelease podcasts)

I think one thing the AI is going to do is – we have it set up so when the AI is trying to make a decision – so it's trying to decide what to build in the city, trying to decide what technology to pursue next – we go ahead and we look at all the possibilities based on where they are in the tech tree right now and we rank them according to which ones we think are the best choice for a strong Civ player at that given point in time. Now what happens is when you're playing on the higher difficulty levels we almost always pick one of those top choices just because we want that civilization to be as competitive as possible with you. When you're at a lower difficulty, one of the things that we do is we start opening that up to some of those other lower ranking choices and we pick from those choices as well. We're also looking at kind of a different depth of analysis in terms of the military and tactical game when you go and you have a higher difficulty setting. So rather than just looking in the immediate area of a city when you're playing on the higher difficulty levels the AI is gonna be thinking a little bit deeper, looking further across the map and using that to kind of come up with decisions like, “oh wow I'm actually 10 tiles away. Maybe I have 3 or 4 units that can reinforce the situation.” I'll pull those in and that will strengthen my military right in the nick of time here.

Either this didn't work and was dropped, or it is still implemented and has hardly any noticeable effect.

 

[stealth_nsk]

Note that some attempt was made to make the civ5 decision making scale with difficulty: (from one of the prerelease podcasts)

Either this didn't work and was dropped, or it is still implemented and has hardly any noticeable effect.

I'll skip the large post I agree with and will comment just on this. The AI scaling was implemented for lowest difficulty levels only. Starting from Prince (if I'm not mistaken) and up AI is the same. That's for the reasons stated here multiple times. However, this info could be outdated - in later patches developers could skip scaling and just implement best algorithms as it's much easier.

 

[JokerJace]

For simplicity of the argument assume that all units have two movement points and all terrain is flat. Consequently, each unit has 19 valid moves. Suppose that you can prune this down to 5 viable moves per unit (again not that simple). This means that a single turn of civ already consists of 5^10 =~10 million possible moves. At this, point you have not even considered the possible responses of the opponent.

As you can see the combinatorics quickly spiral out of control even for a single turn in a very controlled situation. In reality, you do not control the number of involved units that well. A big risk of implementing a depth search is that in the late game the combinatorics even for one turn blow up turn times to unacceptable levels.

In practice what the AI routines do instead is that moves are evaluated in sequence one an individual basis. A context based heuristic is used to determine the best move for a unit. The move is executed and the routine moves to the next units with an updated heuristic. The AI will only play as well as the heuristic logic. It is really hard to write a heuristic that is slightly worse than another in all situations. It is easy to find one that is consistently a lot worse, but a heuristic that is slightly worse in one situation may quite well end up being slightly better in another.

I agree with the illustrated combinatorics per se. But just as a good chess AI, you have to "prune" the paths of the search tree as soon as you can savely discard them. To do this, you have to apply your knowledge of the game. This should result in an acceptable width per level and allow for more depth. This is the precise challange of writing good AI for a game. It is definitely possible to write a good and fast combat AI. It just needs more developer ressourcers dedicated to it. And of course you have to have a good understanding of your own combat system.

 

[Biz_]

civ 5's AI skills from absolutely idiotic (chieftan) to very stupid (diety)

i think people's point is that the higher end of the scale should be actually intelligent

 

[Jman5]

I still believe that the AI could be smartened up quite a bit by simply designing better build order priorities for whichever win condition the AI chooses. I think they sort of do it in Civ 5, but the problem is that they do it poorly. By default an AI should not be racing down the military part of the tech tree while delaying universities if the AI's plan is to win a space race.

 

[Trias]

I agree with the illustrated combinatorics per se. But just as a good chess AI, you have to "prune" the paths of the search tree as soon as you can savely discard them. To do this, you have to apply your knowledge of the game. This should result in an acceptable width per level and allow for more depth. This is the precise challange of writing good AI for a game. It is definitely possible to write a good and fast combat AI. It just needs more developer ressourcers dedicated to it. And of course you have to have a good understanding of your own combat system.

Recall that the quoted combinatorics is for search depth of half a turn. This is the width of a single level, already allowing for very aggressive pruning. The AI for a civlike games probably has more in common with the AI for RTS games than it has with chess.

Note that I am not saying that writing a good AI is impossible. With enough developer resources it certainly can be done (whether it ever will be done is another question). What I was saying that writing scalable AI for civlike games is very hard, and a waste of the scarce developer resources assigned to AI development. I rather have them get near to creating a single competent AI, and then scale difficulty with bonuses for the human or AI, than have scalable AI ranging from completely idiotic to incompetent.

 

[cakes]

i don't care as long as it's consistent

 

[JokerJace]

Recall that the quoted combinatorics is for search depth of half a turn. This is the width of a single level, already allowing for very aggressive pruning. The AI for a civlike games probably has more in common with the AI for RTS games than it has with chess.

Note that I am not saying that writing a good AI is impossible. With enough developer resources it certainly can be done (whether it ever will be done is another question). What I was saying that writing scalable AI for civlike games is very hard, and a waste of the scarce developer resources assigned to AI development. I rather have them get near to creating a single competent AI, and then scale difficulty with bonuses for the human or AI, than have scalable AI ranging from completely idiotic to incompetent.

I am pretty certain that 80% - 90% of all the possible combination of actions per turn can be evaluated to "absurdity" by common sense. So you already have a pretty strong cut - and limiting factor to the exponantial possibility growth - there. And that is only the beginning. I would not be suprised if there exists an algorithm that runs in O(nm) where n is the number of turns you want to look ahead and m is the number of units associated. (at least if we're only speaking of the combat AI and it is somehow possible to find a clever local restriction) I know it is possible to find such algorithm for almost all board games. Even those that are more complicated than a medium sized "war situation" in CiV. This way we would have a perfectly scalable AI. We would simply have to scale how many turns it can look ahead (n). And the running time would also scale, since it has a linaer growth. The bigger challange would be to find a way to universalize the combat AI into a general AI. But since combat is the most complicated aspect of the game (speaking in computational requirements) this should be also possible.

 

[Trias]

I am pretty certain that 80% - 90% of all the possible combination of actions per turn can be evaluated to "absurdity" by common sense. So you already have a pretty strong cut - and limiting factor to the exponantial possibility growth - there. And that is only the beginning. I would not be suprised if there exists an algorithm that runs in O(nm) where n is the number of turns you want to look ahead and m is the number of units associated. (at least if we're only speaking of the combat AI and it is somehow possible to find a clever local restriction) I know it is possible to find such algorithm for almost all board games. Even those that are more complicated than a medium sized "war situation" in CiV. This way we would have a perfectly scalable AI. We would simply have to scale how many turns it can look ahead (n). And the running time would also scale, since it has a linaer growth. The bigger challange would be to find a way to universalize the combat AI into a general AI. But since combat is the most complicated aspect of the game (speaking in computational requirements) this should be also possible.

I believe it when I see it.

In the mean time, I am less optimistic than you are. I think you may be forgetting about some ways civ (and other similar computer games) is different then most board games:
1) In civ games you get to move all your pieces each turn not just one each turn. This means evaluating one turn in civ is more like evaluating n (=number of units) in other board games.
2) Friendly unit moves in civ have relatively little positive or negative effects on each other. This makes the aggressive elimination of move combinations you suggest very hard. The big effects come from move combinations leaving opportunities for strong moves for the opponent. See either you have to delay pruning the option tree until after evaluating the opponents turn (with the crazy combinatorics of just one player turn), or you needed a heuristic that recognizes these opportunities for the opponent (and that in itself would be a huge improvement over the current civ AI).

 

[bhavv]

Deity players in Civ4 already blasts through the tech-tree. So the increased cost is really needed.

Highly incorrect. They blast through by using bulbing and tech trading with the super AIs superior tech rate, plus espionage tech steal. In fact, teching on Deity in Civ 4 becomes easier due to being able to exploit the AIs superior tech rate.

Handicapping the human player isn't fun nor balanced at all while the AI gets almost a 100% improvement to everything.

Also in Civ 4, on Deity settling just 6 cities breaks your economy, while the AI can continually expand without repercussion. This is a daft mechanic all around.

 

[Aeson]

I am pretty certain that 80% - 90% of all the possible combination of actions per turn can be evaluated to "absurdity" by common sense. So you already have a pretty strong cut - and limiting factor to the exponantial possibility growth - there. And that is only the beginning. I would not be suprised if there exists an algorithm that runs in O(nm) where n is the number of turns you want to look ahead and m is the number of units associated. (at least if we're only speaking of the combat AI and it is somehow possible to find a clever local restriction) I know it is possible to find such algorithm for almost all board games. Even those that are more complicated than a medium sized "war situation" in CiV. This way we would have a perfectly scalable AI. We would simply have to scale how many turns it can look ahead (n). And the running time would also scale, since it has a linaer growth. The bigger challange would be to find a way to universalize the combat AI into a general AI. But since combat is the most complicated aspect of the game (speaking in computational requirements) this should be also possible.

The tactical combat AI isn't really that hard compared to interfacing it with economics and overarching strategy. It's a relatively simple problem to get a few pieces in a good formation if you have the pieces and a little room to work in. It's an extremely hard problem to plan out how to tech to, find resources for, build, and get those few pieces in a good formation 50 turns down the road.

That of course pales in comparison to getting an AI that can decide if they should even try to do that, and is flexible enough to understand situations that might arise that determine they should take another approach entirely.

 

[ptoss1]

It'll be the same as CiV.

normal difficulty and then bonuses for each level

 

[Lieu]

Trias, I don't think move-all-pieces-per-turn is particularly special in terms of combinatorics. One civ piece's move is the same as, say, one chess piece's move. If in chess potential moves are in the order of set A then set B then set A and so on then it doesn't make much difference that in civ it's set A -> A -> A -> .... -> B -> B -> B. The search tree takes the same form. The differentiation between "you" and "enemy" doesn't matter for the sake of move order; you're evaluating the board state between moves either way.

It even seems you could take advantage of the fact that in many move series order doesn't matter and that the pieces remaining to move(or to wait - that's a move) shrinks during each "turn". Maybe transpositions are more common, I don't know.

As usual it probably comes down to board evaluation techniques as the most challenging part. Chess engines sure didn't surpass humans by chewing through ~10^40 different positions.

I really don't see such a tactical AI as being unfeasable - and that's after considering board evaluation complications. In fact, I would happily work on it. Such a thing could be an excellent complement to the higher level combat AI and we could tone down some of that extreme AI handicap asymetry.

 

[Trias]

Trias, I don't think move-all-pieces-per-turn is particularly special in terms of combinatorics. One civ piece's move is the same as, say, one chess piece's move. If in chess potential moves are in the order of set A then set B then set A and so on then it doesn't make much difference that in civ it's set A -> A -> A -> .... -> B -> B -> B. The search tree takes the same form. The differentiation between "you" and "enemy" doesn't matter for the sake of move order; you're evaluating the board state between moves either way.

The difference comes in eliminating branches of the search tree. Friendly moves in civ do not impact each other much. Consequently, your rarely encounter situations where move (a) for unit (1) implies that there are no decent moves for unit (2), and therefore the AI can stop considering move (a). In contrast, considering enemy moves are very likely to reveal bonehead moves because they lead to unacceptable loss.

Without sufficient pruning of the search tree during the own turn, combinatorial hell will be reached before you can even start factoring in the opponent moves. Consequently, there is little benefit from expanding all that computing power.

My general feeling is that any depth search of the moves in civilization is not cost effective in terms of computation time. Of course, I may be wrong about that, and there may be very clever ways to get around the combinatorial obstacles. However, it seems unlikely that those would be achievable with the limited developer resources that Firaxis seems willing to expand on AI.

 

[Malachi256]

I desperately hope they improve the military AI. Higher difficulty levels of CiV just aren't fun for me because all the difficulty is in playing catchup to a moronic, over-handicapped AI. Otherwise CiV is a fantastic game... here's hoping.

 

[Lieu]

The difference comes in eliminating branches of the search tree. Friendly moves in civ do not impact each other much. Consequently, your rarely encounter situations where move (a) for unit (1) implies that there are no decent moves for unit (2), and therefore the AI can stop considering move (a). In contrast, considering enemy moves are very likely to reveal bonehead moves because they lead to unacceptable loss.

Yes, I see your principle there... though the flipside seems to be that transpositions are much greater in number. Given that moves are more independent and must be taken, you tend to end up in the same positions if your evaluation is remotely consistent. That's a really big deal. There's also the question of how harsh the overall number of sensible moves is but right now that doesn't stand out to me as being particularly bad. I certainly can see a turn being heavily reliant on transposition tables though.

And don't forget that the reason those bonehead moves are revealed is because the evaluation By the same token your evaluation should be working on your own moves. It can see those attack/defend tables and knows it's a material loss. It's already looking less important to search, before any enemy moves are even explicitly tested.

You know, I might have a go at it. Too many burning questions

 

[Trias]

Yes, I see your principle there... though the flipside seems to be that transpositions are much greater in number. Given that moves are more independent and must be taken, you tend to end up in the same positions if your evaluation is remotely consistent. That's a really big deal. There's also the question of how harsh the overall number of sensible moves is but right now that doesn't stand out to me as being particularly bad. I certainly can see a turn being heavily reliant on transposition tables though.

I agree that if the order in which the player makes his moves was very significant, the combinatorics would be even worse. Note that, in the rough "back of the envelope" calculation I did above, I already assumed that the order in which the friendly moves were taken did not matter. I guess it would be even better if most units were identical, since that would mean a large number of combinations of moves would end up exactly equivalent. However, experience, promotions and hitpoints make that almost all units on the map are unique.

And don't forget that the reason those bonehead moves are revealed is because the evaluation By the same token your evaluation should be working on your own moves. It can see those attack/defend tables and knows it's a material loss. It's already looking less important to search, before any enemy moves are even explicitly tested.

If your board evaluations are good enough to sniff out this type of bonehead move, that would already be a huge improvement over the current board evaluations in civ5. It them becomes the question if you need to do a deep move search at all.

You know, I might have a go at it. Too many burning questions

I agree. The problem of creating good AI for civlike games is very interesting. (precisely because it is very non-trivial) If I had time to waste, I might look at it as well.