# Determining the optimally scoring move on a probabilistically represented 2D grid in real time

I'm posting this to StackOverflow, cstheory.stackexchange.com, and math.stackexchange.com because I'm not really sure where it fits best. I hope that's OK.

I have a 2D grid (size varies per map, ranging from 10X10 thru 20X20, necessarily square) where each cell contains, among other things, the probability (0 thru 1) that each unit (10 thru 50 depending on map) is at that location.

There are 2 main types of unit, there are the big units whose behaviour is controlled by the algorithm you're hopefully going to help me with, and there are small units who can only move or have their (boolean) state changed with the help of big units. All units belong to teams but any big unit can move any small unit. A match is scored according to both the position and state of the smaller units. Each unit knows its own coordinates.

Points are awarded for having a small unit in any of a number of specified cells, with bonuses being awarded for the number of adjacent cells occupied - note adjacency does not necessarily mean adjacent cell coordinates and will be determined per map.

I already have a pathing system, so that is not an issue, nor is computing the time costs of moves, although this should be called minimally for performance reasons.

My intention is to have the planning system output a sequence of desired states/actions. For example, be at (9,4) at an angle of 43 degrees, then be at (12,4) at 12 degrees and enable the small unit there.

I am attempting to determine the optimal moves for each of ~5 competing main units to optimise their team's finishing position when the time runs out. The units have simulated sensors that populate the probabilistic positions, so gathering information is a valid move.

Ideally the algorithm would look a few moves ahead, and consider things like whether or not a particular move puts you in a good position to perform the next move - this "goodness" of a position would just be the inverse of the pathing cost.

Performance is fairly important here and I may well be willing to trade solution quality for significant performance gains.

Here are my thoughts so far:

• The most complete solution would be an exhaustive search, but performance rules this out.

• I should calculate the significance of each reasonably probable current state so I can determine what information is important to find out.

• Running time per unit on an average modern PC should be <= 25ms if possible - not set in stone - this is C++, so it's fairly fast.

• Adapting a chess algorithm may be a good approach.

• The best approach is almost certainly going to be an estimation.

• If there's a 10% chance that a move will get 20 times as many points as any other, then it's worth the risk - unless the other move pretty much guarantees a good finishing position and the time's nearly out.

• My question asking is somewhat verbose.

• I feel like I must have had more thoughts so far, but I can't for the life of me think what they are.

• That last point rhymed.

• If you're still reading this then I might be willing to marry you.

While it would be fantastic if someone were to offer a complete solution to this, I'm absolutely willing to accept any help/hints I can get and will accept the answer that gets me the furthest, however far or not that is. I'm interested in the algorithm rather than the code, which I can handle myself because I'm a big girl now.

• Just trying to get the hang of the info: when you say you can get the probabilistic info, does that mean you can't "see" the little units (just that, if you go there, there's a 75% chance one will be there), or maybe just their own small units? – tabstop Feb 19 '14 at 3:12
• Thanks for reading that thing! The probability is based on simulated vision, so can be pretty much 100%, but degrades over time when a unit cannot see an area - this is simulated in some detail. Vision simulation happens automatically as a unit moves around, so probabilities will change as new information becomes available. Probabilities are properly normalised. Worst case scenario: Evenly distributed probability 1/cells Ideal scenario: Single cell with probability of 1; – Melissa Feb 19 '14 at 3:56
• Random thoughts: I suspect the mix of offense/defense is not necessarily optimize-able, but a matter of style (or perhaps reading your opponent's style); speaking of, looking for "undefended" "hot spots" may be a good tactic once you're in the middle of the game (presumably the beginning will be some setup), assuming you can see opponents. – tabstop Feb 19 '14 at 4:03
• @tabstop - There's not a lot that can be done in defense other than undoing the action of an opponent so the offense vs defense thing shouldn't be that big of a deal. For now, and for the sake of simplicity - hah!, I'm just thinking in terms of what change to the board would have the greatest overall benefit to me in terms of either points gained or opponents points lost at any one point rather than planning for opposing moves. – Melissa Feb 19 '14 at 4:25