Optimize algorithm: finding all possible moves for a turn based game

Question

I am working on the ai for a turn based game. To illustrate my problem this are the simplified rules of the game:

The game takes place on a tiled map with obstacles (black quads) like this:

• The player has several tokens (like the two colored dots in the example picture)
• The player can move all his tokens in his turn
• the tokens move in a straight line until they hit an obstacle, the border of the map or another token
• each token could move two times in each turn.
• the player can move his tokens in any order he likes

The AI needs a list of all possible turns it could make of one game state. My first attempt was to recursively go through all tokens and move them in any possible direction and order. that works of course but the problem is that with just four tokens there are several millions of possible turns (if each token could move two times). Most of the outcomes of these turns are the same (the tokens end in the same place). In the example above the tokens could move like this:

No matter in which order the four move actions (A,B,C,D) are made, the end positions of the tokens are the same. I am only interested in the possible end turn situations. So I implemented a transposition table in the turn generation algorithm to negate all of the equal turns. That works and in the end I have only several hundred of possible turns with four tokens rather than several millions. The problem is that the algorithm takes too much time because it has to calculate every possible turn. Does anybody has a hint how to prune the turn generation tree? Or any other idea how to calculate only the different possible turn outcomes?

Note: In the real game the map is slightly bigger (30-40 free cells) and there are up to 6 tokens.

Answer 1

I don't have a complete answer for you, just a few lines of thought...

1) Construct a dependency graph

As you consider each move each token can make, store a reference to that move with each cell it passes through.

When a later move ends in one of the marked cells, we've identified a potential new dependency: performing move B before move A can change the outcome of move A. Then you can recursively check the outcome of the modified move A...

This requires some care to ensure you don't follow cycles of mutually-exclusive moves (ie. performing move A first modifies the outcome of move B which modifies the outcome of move A... but no it doesn't, because A already happened!)

Hypothetically this could get you some savings in the event that your tokens are separated from each other, so that many of the outcomes are independent of one another (your dependency graph ends up sparsely-connected). You can separate a turn into clusters, where each cluster contains multiple mutually-affecting moves (where you need to consider order, but of a smaller subset of moves) and clusters minimally affect one another (so you can ignore order between clusters, or consider fewer ordering cases).

However, my suspicion is that mutual interactions are much more common, and that you'd be introducing a lot of complexity to the algorithm for comparatively little pruning.

2) Consider a goal-based approach

A human player won't visualize every possible move. They'll usually have a strategy in mind, like "I want to get my red token in position to do X" then they'll look for a sequence of moves that accomplish this goal, often by working backwards from the goal state and considering only interactions that move them towards it.

So if your aim is to get a reasonable-performing adversary rather than one which always finds the best possible move, structuring it around goal-seeking behaviours rather than minimax tree search may reduce your problem space to a more manageable size.

Since I don't know much about the rules of your game, I can't speculate on what your goal logic might be, and generally they require more sophisticated AI design than search-based approaches.

You can even try a hybrid approach, where you do a minimax search over a set of goals rather than individual moves, pruning goals which turn out to be unfeasible once their move sequence is examined.

3) Consider sampling

If none of the above work, a fallback is to just try to search as much of the tree as you can within your available time & performance budget. This means trying to optimize your exhaustive search inner loop as much as possible, making sure you're using your transposition table to save redundant work on intermediate states and not just final configurations.

You'll want to randomize the order in which you consider moves, to avoid biasing the AI to search moves for the first token more exhaustively than the last, for example.

Whenever you hit your limit, stop, and use the best result you've found so far. You'll likely want to frame this limit in terms of steps rather than realtime, so that players on faster machines don't have to contend with stronger AI than those closer to the minimum spec. ;)

---

Overall, my algorithmic spidey sense is giving me that tingly feeling that there might not be any easy shortcuts here, and that a good approximation that's achievable with clear and maintainable code and scalable performance might be a better target to aim for than a complex algorithm that's provably optimal.

Answer 2

I would start from the end positions, because this is what matters.

There are 2 tokens and 21 blank squares in your example, which means that in the worst case (all ordered pairs of squares represent reachable outcomes) there are 420 valid outcomes.

Check each of these possible outcomes to look for one valid way of reaching it, once you find one way of moving your tokens there mark the outcome as valid and move to the next possible outcome to check. If you don't find any, mark it as invalid and move on.

At the end of the process you have your list of reachable outcomes and you have avoided computing duplicate ways of reaching the same outcome.

No free lunch though, of course. Now the problem becomes how to search for one way of taking all tokens in each ordered set of end positions. But you have a lot of information to use for making the algorithm smarter than "Check all possible moves and turns and verify whether they end up there". For instance, no need to turn left if the required end position is on the right; or, in your example, the green end position cannot be reached in any other way than coming from the left.

It's going to be tough but it's feasible IMHO. And a fun algorithm to code.

Answer 3

For such problem I'd rather go for a Montecarlo algorithm. For each possible move make N random plays and count the number of computer wins. Let the computer do the move with the higher number of wins.

N should be sufficiently large. The larger that number, the strongest the computer will be

Doing this way the computer will force the game into the ''path'' in which it has the best chances of winning.

No need to implement a minmax algorithm nor to explore all the possible branches. Just pick a random move, do the simulation until either the human wins, the computer wins or it is a draw. Repeat.