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.
I'm bad at this, I should ask the internet.
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.