6
\$\begingroup\$

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:

Game board with obstacles and tokens

  • 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:

The two tokens moved two times each

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.

Improve this question
\$\endgroup\$
6
  • 1
    \$\begingroup\$ Are you interested in "the best" solutions or simply "all the possible solutions"? \$\endgroup\$ – Vaillancourt♦ Jan 11 '16 at 17:10
  • \$\begingroup\$ all possible solutions \$\endgroup\$ – user77413 Jan 11 '16 at 17:59
  • \$\begingroup\$ The token collision makes this difficult. In the worst case, the order of the moves can create arbitrarily varied destinations, each of which must be checked. This is what makes it interesting as a puzzle, though. Even in your example the order changes the outcome. Consider CDBA: the 'B' motion stops in the tile you have written 'D' into, so the final 'A' motion should place the red tile one step to the left of where it is. You may need to settle for standard optimization techniques (data structures, memoization, etc.) rather than a smarter search algorithm. \$\endgroup\$ – Chris Mills-Price Jan 11 '16 at 23:10
  • \$\begingroup\$ Are the token identities significant? eg. If I move the green token right, then up (so it finishes in the top-right corner), and then move the red token right and right (second move colliding immediately and resulting in no movement - is that allowed? Or can a player move a token fewer than two times?) so it finishes in the middle-right, then the occupied cells are the same as the example above but the colours are interchanged. Is that a distinct game state from the example above, or are the two states equivalent? \$\endgroup\$ – DMGregory♦ Jan 11 '16 at 23:54
  • \$\begingroup\$ @Chris Yes the token collisions and the order of the moves are making the possible turns calculation complex. I want to use MiniMax for the AI. I only need a MiniMax search depth of 2-3. I optimized the algorithm quite a bit with several techniques but it still takes too much time. In the final game there are billions of possible turns (more tokens, each can perform several actions) but most of them have the same outcome. So I thought about a smarter algorithm for calculating the different turn outcomes without going through all possible turns. \$\endgroup\$ – user77413 Jan 12 '16 at 0:31
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ As a point of evidence that this problem may be excessively complex to expect a fast exact solution: Sokoban is a similar set of sliding token mechanics which is provably NP-Hard. I haven't found any similar analysis of games without a "pusher" avatar and blocks that slide until obstructed, so it's possible those elements make the problem easier, but my suspicion still leans toward NP-Hard. ;) \$\endgroup\$ – DMGregory♦ Jan 12 '16 at 18:59
  • 2
    \$\begingroup\$ In fact, problems of this nature are often PSPACE-complete (move sequences can be longer than polynomial) and some variants of this particular problem are as well: tizian.cs.uni-bonn.de/publications/ek-crrg-05.pdf has a proof. \$\endgroup\$ – Steven Stadnicki Jan 12 '16 at 22:47
  • \$\begingroup\$ @DMGregory Thanks for your great answer! I also think that no.1 results in a too complex algorithm. But it is a fine idea! I am implementing your no.3 because I can use my existing algorithm for it. I have the feeling that the AI would be good enough with this approach. In the end the AI has to be fun to play against and not to be a perfect playing unbeatable bastard. If that doesn't work I think your no. 2 could be the way to go. But in the real game each token has more possible actions than just moving and so it could be nontrivial to implement that approach. Thanks again! \$\endgroup\$ – user77413 Jan 13 '16 at 10:01
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
6
  • 1
    \$\begingroup\$ Thanks for your answer! I am not sure if this would save time. The example is a simplified one. In the real game the map is slightly bigger (30-40 cells) and there are up to 6 tokens. if the map has 35 blank cells there are 29^6 possible outcomes with 6 tokens. 29^6 are also way too many possibilities to check if they are valid. \$\endgroup\$ – user77413 Jan 12 '16 at 17:18
  • 1
    \$\begingroup\$ Its not quite 29^6, its actually (29!) / (23!). But the result is still a few hundred million. \$\endgroup\$ – Draco18s no longer trusts SE Jan 12 '16 at 17:22
  • \$\begingroup\$ I see. Question: how many of these outcomes do you expect to be invalid? Because my guess is that at least a million of those hundreds millions are, which means that the problem is that the tree is actually huge notwithstanding duplicate paths to the same node. If this is the case, anything you do with a MiniMax will be unmanageable. From a game design perspective, a game with such a broad choice at each turn is easily unmanageable for the human mind as well. Go has less than a few hundreds alternate moves per turn, chess less than a few dozens, bridge, backgammon or Carcassonne even less. \$\endgroup\$ – Mauro Vanetti Jan 12 '16 at 21:06
  • \$\begingroup\$ The actual result is 35 * 34 * 33 * 32 * 31 * 30 = (35!) / (29!), about 1.2 billion. It's a lot but it's much less than starting from the initial positions and checking all moves and turns, i.e. about ((6 + 6)!) * 4 * 4 * (average distance from wall or other token)^2 = 7.7 billion * (avg. dist. from wall or token)^2 = 30-50 billion in a 6x6 grid. Nice but you're right, not enough to make it feasible, and the computation per iteration would be much heavier anyway. \$\endgroup\$ – Mauro Vanetti Jan 12 '16 at 21:24
  • 2
    \$\begingroup\$ "Check each of these possible outcomes to look for one valid way of reaching it" Unfortunately as per the paper linked by Steven Stadnicki in a comment on another answer, checking whether a given configuration is reachable under these mechanics is proven to be NP-Hard. So in this case exhaustively enumerating all end states and checking for feasibility might not actually reduce the workload compared to naively searching forward from the starting configuration. :( \$\endgroup\$ – DMGregory♦ Jan 13 '16 at 5:47
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy