4 ms·
same with starcraft: "Suppose the two players have bases on different islands, player B has a strong ground army but no income and no way to reach player A, wh
by icepotato 15y ago
same with starcraft:
"Suppose the two players have
bases on different islands, player B has a strong ground army but no income and no way to reach player A, while player A has no units and needs exactly x resources to train an army and barely defeat B. Player A starts with just enough resources to train a worker. In yet another un-
reachable island, there are n locations, each of which has a main building of A (to which workers must bring the resources they collect) and x=n resources. There is also a worker in each location, but it is "trapped" behind some resource batches, and cannot reach the main building. On each path connecting two locations, there is a turret (or other static defence) of B, positioned in such a way that a lone worker traversing the path isbound to be killed, but if two workers traverse it, exactly one survives.
B hopes for a draw, while A has only one strategy: Train a worker at some location, collect the resources, thus setting the second worker free, traverse a path with both workers to reach another location, and repeat.
A cannot waste resources into training more than one worker, and can win if and only if the (planar) graph of locations has a Hamiltonian path."
which raises the question - what is a game? is it the collection of all possible permutations of states allowed by the rules, as in the Pac-Man generalization or this extremely weird corner case SC scenario that requires extended amounts of sub-optimal play? If I -can- construct such a bizarre and entrenched StarCraft position, is it part of "the game", or is it a weird theoretical custom map whose sole purpose is proving starcraft is np-hard to "solve"
- Cushman 15y agoWhy try so hard? Just make a UMS map that implements Tic-Tac-Toe. StarCraft: solved!
- rictic 15y agoIt is also possible that on any legally-sized starcraft map the number of nodes in the graph would be so small that the solution would be trivial. But at the same time it's fascinating that they were able to embed this sub-problem within a starcraft scenario, such that any optimal player would have to solve this NP-hard problem. This sort of argument is a classic in the field, and always fun to read.