Re:A way to deal with enormous branching factors in strategy...
by AstralStorm on Friday March 25, 2016 @04:03PM
(#11362286)
The problem of pool is not that bad for the search (range searches such as R trees work), but then you end up with a variant of packing problem to pick optimal options and order. That alone is NP-complete.
But the real hard problem is evaluation of moves. Even for simple games encoding of positional and temporal advantage is hard. This is really important for things such as build and research orders. Once weights are known, you may use any number of asymptotically optimal scheduling algorithms.
But the real hard problem is evaluation of moves. Even for simple games encoding of positional and temporal advantage is hard. This is really important for things such as build and research orders. Once weights are known, you may use any number of asymptotically optimal scheduling algorithms.