Is chess-like AI really inapplicable in turn-based strategy games?

Question

Obviously, trying to apply the min-max algorithm on the complete tree of moves works only for small games (I apologize to all chess enthusiasts, by "small" I do not mean "simplistic"). For typical turn-based strategy games where the board is often wider than 100 tiles and all pieces in a side can move simultaneously, the min-max algorithm is inapplicable.

I was wondering if a partial min-max algorithm which limits itself to N board configurations at each depth couldn't be good enough? Using a genetic algorithm, it might be possible to find a number of board configurations that are good wrt to the evaluation function. Hopefully, these configurations might also be good wrt to long-term goals.

I would be surprised if this hasn't been thought of before and tried. Has it? How does it work?

Answer 1

It depends on the mechanics of the game. Game tree min-max may be inapplicable overall, but maybe it applies in some areas. It's common that some locations on a map are strategically important. Min-max may apply at a strategic level for which of those locations to control. At a tactical level, for the x squares around each strategic location, min-max might be used to decide how units deploy to capture and defend it.

Answer 2

This isn't a minimax algorithm, however the guys responsible for the Killzone AI released a paper based on position evaluation functions which some chess AI also uses.

It's very simple in that all it does is picks a position on the board based on the agent's current knowledge. So if the agent is low on health, then positions further away from its enemy will be awarded a higher score as it is more desirable to be out of the enemy's range.

The paper can be found in AI Game Programming Wisdom 3 and has the title Dynamic Tactical Position Evaluation.

A draft of the paper can be found online here:
http://www.cgf-ai.com/docs/straatman_remco_killzone_ai.pdf

Hope that helps.

Answer 3

I don't think that it would be good enough. Choosing the specific N configurations, how many and which ones, would be virtually impossible in something that complex. Remember that if your game features infinite resources or something similar, then there may be circles in how it can be played, making exploiting such an AI relatively easy.

Answer 4

I would suggest at least implementing min-max with alpha-beta pruning.

Without trying it and deciding it is impractical (i.e. terrible performance), and without more background on the game mechanics, I don't see why you think min-max is inapplicable.

The size of the board is potentially an issue, but with pruning, discarding losing pathways enables a deeper search with the same amount of computation, so perhaps the larger board areas will not be an issue when pruned? Additionally, assuming the board size itself is an issue may be premature, it is not so much the size of the board as the complexity of the mechanics and how many moves are possible from each board position. If your game has a large but sparsely populated area, the number of possible moves from each board state may not be much different than if the board was just large enough to fit all the pieces. Of course if you have a gigantic board that is 90% full and everything can move anywhere every turn, that's going to require a lot of searching. One of the reasons Go is so difficult to write AI for is that there is so much freedom of movement, although it is also a very difficult game to write an evaluation function for.

I'm also not sure why simultaneous movement is inherently a problem. As long as you transition from one discreet board state to another, and have an evaluation function, the algorithm ought to apply.

I assume you need to have an evaluation function anyway, and regardless of the search you use, the evaluation function is where most of the work is likely to go. The min-max algorithm with pruning is itself very simple to implement, something you can probably do in an hour or two and much of the infrastructure work like board state storage, evaluation, move generation, is likely going to be the same regardless of the search you settle on.

Answer 5

The winner of the 2011 Google AI challenge used min-max (of depth 1). Another top contestant used random sampling. This contestant mentioned that a mix of min-max and random sampling, which is basically what I described in my question, performed poorly. This settles it, I guess.

On the other hand, it does show it's possible to use min-max in large games. It seems it was however necessary to limit it to small-ish groups of ants, working with the full set of all ants would have probably been too slow. Another interesting observation is that a depth of 1 was enough. We (humans) have become pretty good at playing chess, and an AI for this game needs much deeper search trees to be challenging. New more complex games haven't been played and studied for so long, and dumber AIs may have sufficient entertainment value.

Answer 6

The basic idea of a chess AI is to make a list of all possible moves from the currently estimated best move, then to rate them and to repeat the process. It drops those with too little chance as they won't be taken (or can be assumed not to be taken as they do not appear to give an advantage).

The basic idea requires you to make a list of all possible moves, and to repeat that process for all those moves etc. This is possible in chess (where the list of likely next moves is effectively enumerable; a starting chess board has 20 possible moves) and up to a point for other things such as backgammon, checkers and solving a Rubik's cube.

If I take a simple turn-based game (Civilization 2) as an example, each of your guys can move to a total of 8 squares (or 24) in a single turn. If you have 10 guys (which isn't a lot, you typically have more by the time it starts to get somewhat interesting) the total number of possible "moves" from the current state (so a single level) is already 8^10 or about 4 billion. Even if you prune 99.99% of those, you still can't go deep on the tree as the number of possible moves explodes really quickly.

Add to that that the game is a bit like the Rubik's cube problem, where you only see progress after some 10 or 12 moves, the problem explodes to a point where the advantages of a standard min/max are only prevalent at a memory capacity of more than your typical computer will have.

In other words, the strategies it will find will be reproducible but bad.

For the actual problem, how to make a decent AI, I would go in the direction of basically steered random movement (move each guy with a bit of basic intelligence), evaluation and tuning. Do this in parallel for 100 or 1000 different ones and pick the one that ends up being the best. You can feedback the results from this into the original intelligent steering to tune it again. A bit like monte-carlo simulation.

Answer 7

To successfully apply min/max to a turn based strategy game, you need to correctly apply all available chess-techniques...

Evaluation function

Even chess engines have a very bad strength, if your evaluation functions is bad. The most simple version of a evaluation function is: 1=game won by white, -1=game won by black, 0 = all other cases; But, this would give you a very bad performance. The same happens to your turn based game! If you want to use min/max (with alpha/beta pruning and stuff) like in chess, you must also implement a reasonable evaluation function! Else, you cannot compare those algorithms performance when being applied to your strategy game to the case it's applied to chess.

What evaluation functions of chess engines do, is evaluating stuff like:

• How well is a position of a piece on the board?
• How many times is a piece attacked?
• How many times is the piece protected?
• How well can each piece freely "move" on the board? (or: How many tiles does it "control")

Those parts of the evaluation function must first be "translated" to your game:

• Position of piece: Is it e.g. on a hill, which is extending its shooting range?
• Attacked: How much is each piece in danger? (e.g. sum of attack values of units able to attack a special unit multiplied by some probability to be attacked by it; probability increases, if the unit is already damaged; decreases if many other units are in range of the attacking unit)
• Own Attack: How many units can be attacked by this each unit?
• Protection: How much own pieces are next to it (to help)? Maybe a unit may not attack units under a minimum distance and its preferable to protect it by unit having the possibility to attack nearby units.
• Mobility: How mobile is your unit? (can it flee?)

The different ratings must be summed up by weighting function (factor_a * rating_a + factor_b * ranting_b + ...) for all units...

In strategy games also the resources (gold, wood, ...) left must be taken into account.

If your evaluation function is well enough, you do not need to really search "deep" into the tree for most cases. So you probably only need to take a closer look at the 3 or 10 most promising choices. See next chapter...

Possible moves at each position

The most problematic thing about using min/max for strategy games is that you can command multiple units in one turn, whereas in chess you are only be allowed to command one unit (except for castling, but this is a clearly defined move combination). This causes 5^N possible moves for N units for each "position" (chess term), if you would only decide between "move north, south, west, east OR stop" for each unit. You could solve this by breaking down the complex command into the low level commands: e.g. choose action for unit A, go into depth and decide for unit B.... decide for unit N ... and then end this turn. But, this alone doesn't change the complexity! You must optimize the order in which actions are assigned to units (e.g. first unit B, C, D and then unit A). You could record the impact of the decision for each unit during the last calculation and then sort by importance. This way alpha-beta pruning can be used to cut away any bad combination from the search tree very early. The highest priority should always be "do nothing more and end your turn" (null move pruning) in each iteration. This way you can "skip" assigning most tasks to most units and let them just continue what they did before. This way the search will go into depth quickly by just taking a look at the "critical" units (e.g. the ones really in combat right now). Make sure to only command each unit once... You can also use some randomness to make sure that the "important" units are getting a command from time to time, too. Especially, units finishing some job (e.g. harvesting - or having no enemy assigned anymore) should slightly increase in importance.

Iterative Deepening + Caching/Hash Table

Then, you can "interative deepening" to go into depth more and more until some time limit has been reached. So you will search deeper if there are less units, and you have always some "result" if you stop searching for a better solution. Iterative deepening would require to use a hash table to cache former results of searches. This also enables to reuse some of the results from the last turns search (the branch of the search tree that covers the commands that were actually executed in the last turn). To implement this, you need a very good hashing function (have a look at the "zobrist key"), which is able to be iteratively updated. Updating the hash key means, that you can just take the hash key of the old "position" and can just kick in the change in the position (e.g. take away unit at position x and put it at position y). This way calculating the hash key is quick and you don't need to process the whole boards situation to calculate it, just to check if the hash contains a former entry for this position. In a way you must make sure that no hash collisions happen.

Non-deterministic Behaviour

Non-deterministic behaviour is a problem for min/max searches. This means, it isn't sure if you will hit an attacked target (e.g. probability is 10%). Then you can not just plan this happens. In that case you need to modify the algorithm and put a "probabilty" layer in between. It's a bit like "its the probabilities turn". Each independent result must be regard separately. The evaluation through this depth "layer" must then be sampled (monte carlo sampling) and the result of the in-depth evaluation must be weighted by the probabilty of occurance. Different results of the probability layer must be regarded like different opponenent moves (but instead of min/max the "average" must be calculated). This will of course increase the complexity of the search tree. So this would in fact be something like min/max/avg-search (not min/max-search anymore).

Summary

When applying all those techniques (which are all used by current chess engines) to a deterministic game, you will surely be able to achieve reasonable results for a game, too. For non-deterministic games, this will be probably more complicated, but I think still manageable.

A good resource for explanation of those techniques (for chess) is http://chessprogramming.wikispaces.com/

You can even implement some sort of directed randomness in min/max searches. Instead of deterministically investigate the best results first in each iteration, you can just randomize this and let its order be decided by a probability distribution that is based on the current evaluations...