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 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 6

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.