|
On November 23 2012 11:25 monkybone wrote: Maybe a layman explanation why polynomial time is so significantly preferable to exponential time would benefit the thread?
a classic example of this is the postman problem.
imagine we have 5 houses in a small town. as the postman, we want to do the least work possible, so we want to take the shortest route that delivers all the mail.
to model this: take a piece of paper, draw 5 random dots on it. now, connect all the dots to all the other dots using straight lines. go on, do it, ill wait
ok, for each straight line we have, we'll give it a time (a value between 1 and 10 for simplicity sake).. for even further simplicity we'll assume the time between letterboxes is the same in both directions (often in these types of problems, the time (or weight) of each line is different in different directions, in some cases they will be unreachable too).
so, the question is, how do we work out what the shortest route is?
before you answer "ill pick somewhere to start and follow the shortest route from each node", try that for a few different starting nodes, and see how you go.
the correct answer is, the only way to work out which is shortest, is to add up every single damn permutation possible. and then, and only then, can we evaluate what the shortest route is. this is what NP means. it means, there's absolutely no way we can cheat. we simply have to do the work.
now, consider the same problem for when we have 100,000 letterboxes.... yeah. see the problem?
now consider a similar problem, with 200 vs 200 food armies, at 20 minutes into a game, with a large play area (100k x 100k possible positions say) .. and the concept of trying to "solve" sc2 becomes immediately, obviously improbable.
oh, its possible, but the universe will suffer heat death well before you've actually derived all possible permutations for something as complicated as starcraft 2. assuming of course that you dont run out of atoms in the universe trying to store your results.
|
On November 23 2012 16:36 Matt_D_ wrote:Show nested quote +On November 23 2012 11:25 monkybone wrote: Maybe a layman explanation why polynomial time is so significantly preferable to exponential time would benefit the thread? the correct answer is, the only way to work out which is shortest, is to add up every single damn permutation possible. and then, and only then, can we evaluate what the shortest route is. this is what NP means. it means, there's absolutely no way we can cheat. we simply have to do the work.
This isn't really accurate. NP means non-deterministic polynomial time, which in short means that one should be able to check whether a solution is correct in polynomial time for the problem to be in NP. What this of course means also is that problems solvable in polynomial time are also in NP. When you are referring to the traveling salesman problem you are in fact talking about a problem that is NP-hard, meaning that the problem is not even in NP (if you are indeed interested in finding the shortest route, and not just interested in whether a route shorter than some length exists). It is a problem which all problems in NP can be reduced to, but is not itself in NP.
And even if a problem is NP-complete (meaning that it is NP-hard and it is itself in NP) or even NP-hard, certainly going through every possible combination is not all one can do. Sure, to our knowledge there are no polynomial time algorithms for those classes of problems, but still better algorithms exist than going through every possible combination.
To the problem at hand itself: The game tree one would have to consider in sc2 is so enormous that I doubt finding an optimal strategy somehow is feasible (at least in any sort of near future) because of the time and memory requirements. To my knowledge the best poker AIs currently work by abstracting the original game to a game of simpler form which they can optimally solve, and then mapping the optimal solution back to the original game. An example would be that you restrict the possible actions you can do and the actions you react to, and just play the simpler game. Obviously the quality of such a solution would depend on the loss we incur when doing the abstraction, but nevertheless if the goal is to find strategies that are optimal even in some sense, settling with them being optimal for a far simplified game and not necessary for entire sc2 would be perhaps more feasible.
|
On November 23 2012 17:16 spudde123 wrote: To the problem at hand itself: The game tree one would have to consider in sc2 is so enormous that I doubt finding an optimal strategy somehow is feasible (at least in any sort of near future) because of the time and memory requirements. To my knowledge the best poker AIs currently work by abstracting the original game to a game of simpler form which they can optimally solve, and then mapping the optimal solution back to the original game. An example would be that you restrict the possible actions you can do and the actions you react to, and just play the simpler game. Obviously the quality of such a solution would depend on the loss we incur when doing the abstraction, but nevertheless if the goal is to find strategies that are optimal even in some sense, settling with them being optimal for a far simplified game and not necessary for entire sc2 would be perhaps more feasible.
But you don't have to have the "perfect" (read:most cost efficient) engagement. To win it is enough to have a cost efficient engagement. If you sustain cost efficient engagements all game long you should at least be able to not lose the game.(Given the enemy doesn't outexpand the PC heavily).
You could even weaken the condition if you consider possible runbys: If you do enough eco-damage you can trade cost inefficient as long as you don't die to the counterpush.
E: I know that in theory this can produce the same fallacy as the "nearest neighbor method" in the salesman problem. It could be interesting if such strats would win against this kind of algorithm in a reproducable way. Or if these strats exist in a "competitional" environment.
|
On November 24 2012 00:34 Hryul wrote:Show nested quote +On November 23 2012 17:16 spudde123 wrote: To the problem at hand itself: The game tree one would have to consider in sc2 is so enormous that I doubt finding an optimal strategy somehow is feasible (at least in any sort of near future) because of the time and memory requirements. To my knowledge the best poker AIs currently work by abstracting the original game to a game of simpler form which they can optimally solve, and then mapping the optimal solution back to the original game. An example would be that you restrict the possible actions you can do and the actions you react to, and just play the simpler game. Obviously the quality of such a solution would depend on the loss we incur when doing the abstraction, but nevertheless if the goal is to find strategies that are optimal even in some sense, settling with them being optimal for a far simplified game and not necessary for entire sc2 would be perhaps more feasible.
But you don't have to have the "perfect" (read:most cost efficient) engagement. To win it is enough to have a cost efficient engagement. If you sustain cost efficient engagements all game long you should at least be able to not lose the game.(Given the enemy doesn't outexpand the PC heavily). You could even weaken the condition if you consider possible runbys: If you do enough eco-damage you can trade cost inefficient as long as you don't die to the counterpush. E: I know that in theory this can produce the same fallacy as the "nearest neighbor method" in the salesman problem. It could be interesting if such strats would win against this kind of algorithm in a reproducable way. Or if these strats exist in a "competitional" environment.
Yes I definitely agree, I just talked about the concept of solving something "optimally" (if even possible here) because it was brought up. Indeed even a great AI doesn't have to have an optimal solution to something, but instead for example a solution that is better than humans can currently achieve. Still these sort of "optimality" considerations can be interesting from a theoretical perspective
|
even a solution that a human can achieve (or even one below top human play) is great because it is consistently going to perform at that level... no fatigue, no jet lag, no having a bad day
|
Deep Blues is not a perfect chess AI by any means. Even the most advanced AIs today, that have a substantial edge over the strongest grandmasters, have not come close to solving chess. So... why then is all the discussion focused on the impossibility of solving Starcraft 2? Deep Blue doesn't come even close to solving Chess... The 'Deep Blue' of SC2 would be defined by defeating the strongest human player in a widely publicized match. Such an SC2 AI could be achieved within a matter of months imo, if the right people were involved in its creation.
Is there anyone in this thread who dares dispute this? Please stop banging your head against the wall of 'SC2 Too many permutations Oh noes!!!'. Chess possibilities also number over the total atoms in the universe. Deep Blue is not a perfect chess machine, its a machine that can beat the best humans.
|
man this brings me back to kasparov vs deep blue... kasparov was able to take i think 1 game off the machine and it was clear that he was frustrated and slowly building up fatigue as the match went on...
|
i wonder if you could at least automize battle micro in a machine highly trained on battle micro in a AxB grid... then just instantiate that grid in parallel with all your battle fronts.... you will get machine perfect micro in 4 locations... they will gg ragequit
addition: what kind of hacking into sc2 would this require btw
|
|
France9034 Posts
On November 24 2012 08:24 mishimaBeef wrote: man this brings me back to kasparov vs deep blue... kasparov was able to take i think 1 game off the machine and it was clear that he was frustrated and slowly building up fatigue as the match went on...
This, plus all the controversy with "the move" Deep Blue made, that Kasparov couldn't believe a machine could do. Then, was refused access to Deep Blue's logs, thus building mental fatigue on paranoia, and loosing concentration...
I still don't know how to consider this historical event...
|
On November 24 2012 10:00 Ragnarork wrote:Show nested quote +On November 24 2012 08:24 mishimaBeef wrote: man this brings me back to kasparov vs deep blue... kasparov was able to take i think 1 game off the machine and it was clear that he was frustrated and slowly building up fatigue as the match went on... This, plus all the controversy with "the move" Deep Blue made, that Kasparov couldn't believe a machine could do. Then, was refused access to Deep Blue's logs, thus building mental fatigue on paranoia, and loosing concentration... I still don't know how to consider this historical event...
That's just creepy man...
I'm about to read it:
http://en.wikipedia.org/wiki/Deep_Blue_versus_Garry_Kasparov
|
your Country52796 Posts
Humans are able to "trick" lesser computers by disguising a build, compromising the efficiency of it, to counter the computer's scout, but the computer has perfect mechanics, and more perfect computers can include the possibility of this.
Theoretically, a computer will win every game that is based on micro/macro/multitask. In a game of tactics the human should nearly draw even.
|
You might be able to create an AI that could beat people by sheer force of micro, but writing an AI that beats people by making good strategic decisions is unlikely. The top chess AIs can consistently win against human opponents, but they work by analyzing as many moves as possible using costly searching algorithms that take a long time to determine the best move. Real-time strategy offers no time for thinking, and the number of possible moves is more or less infinite compared to chess. 20 vs 20 blink stalkers on a typical SC2 map would be a more complicated game to calculate than chess is, so imagine what it would be like to put the rest of the game in too.
|
|
Let's restrict our analysis to mirror matchups on completely balanced maps only.
The good news: Starcraft II, under the restrictions above, is zero-sum (if I win you lose, if we tie neither loses) so it falls under the space of games in which a nash equilibrium exists. This means there exists a mixed strategy (policy of which decisions to make in all possible game situations, where decisions can be randomly selected with some bias) which cannot lose more games than it wins IN EXPECTATION against any other mixed strategy. So basically for every balanced map, there exists some master strategy that is better than any other strategy (including strategies that would be executed by humans that do meta-reasoning!)
The bad news: Starcraft II is such a complex game that computing such a master strategy is nearly impossible given the techniques AI currently has to offer and computational power we have available. And as an AI researcher I can tell you that we are very, very far from being able to compute the master strategy.
If we throw in the ability to choose one of the three races, choosing your race at the beginning is a new choice to be made by the strategy and the result above still holds.
But if we throw in map imbalance, all of this goes out the window.
Hopefully someone experienced in game theory can confirm/deny what I've written.
|
On November 24 2012 08:04 JeanLuc wrote:
Deep Blues is not a perfect chess AI by any means. Even the most advanced AIs today, that have a substantial edge over the strongest grandmasters, have not come close to solving chess. So... why then is all the discussion focused on the impossibility of solving Starcraft 2? Deep Blue doesn't come even close to solving Chess... The 'Deep Blue' of SC2 would be defined by defeating the strongest human player in a widely publicized match. Such an SC2 AI could be achieved within a matter of months imo, if the right people were involved in its creation.
Is there anyone in this thread who dares dispute this? Please stop banging your head against the wall of 'SC2 Too many permutations Oh noes!!!'. Chess possibilities also number over the total atoms in the universe. Deep Blue is not a perfect chess machine, its a machine that can beat the best humans. I dispute this. Chess is turn-by-turn, StarCraft is real time. You win this game by having more stuff than the other guy. Strategy is irrelevant in a 50 supply deficit. I don't think anyone could dispute that with sufficient R&D, there could be a bot that could micro (already exists) and macro (dunno about this one yet) far better than any human could possibly do, the rest could follow, and it'd be near unbeatable.
EDIT: I am an idiot and read your post wrong. I do not dispute you at all. In fact, I heartily agree. Whoops.
|
Caelestis, I'm not going to quote your entire post, but thanks for posting it.
|
On November 24 2012 11:12 Ruscour wrote:Show nested quote +On November 24 2012 08:04 JeanLuc wrote:
Deep Blues is not a perfect chess AI by any means. Even the most advanced AIs today, that have a substantial edge over the strongest grandmasters, have not come close to solving chess. So... why then is all the discussion focused on the impossibility of solving Starcraft 2? Deep Blue doesn't come even close to solving Chess... The 'Deep Blue' of SC2 would be defined by defeating the strongest human player in a widely publicized match. Such an SC2 AI could be achieved within a matter of months imo, if the right people were involved in its creation.
Is there anyone in this thread who dares dispute this? Please stop banging your head against the wall of 'SC2 Too many permutations Oh noes!!!'. Chess possibilities also number over the total atoms in the universe. Deep Blue is not a perfect chess machine, its a machine that can beat the best humans. I dispute this. Chess is turn-by-turn, StarCraft is real time. You win this game by having more stuff than the other guy. Strategy is irrelevant in a 50 supply deficit. I don't think anyone could dispute that with sufficient R&D, there could be a bot that could micro (already exists) and macro (dunno about this one yet) far better than any human could possibly do, the rest could follow, and it'd be near unbeatable. EDIT: I am an idiot and read your post wrong. I do not dispute you at all. In fact, I heartily agree. Whoops.
Starcraft is also turn-by-turn (see previous post as to why and how the transformation is done). Strategy is what got you to a 50 supply deficit in the first place.
|
On November 11 2012 12:53 AbideWithMe wrote: Perfect mechanics and micro with predefined build orders yes ofc.
Perfect strategies and scouting with dynmaic BOs not so much.
With certain pefectly executed timing pushes A.I. could beat every human for sure though. Predefined build orders defeats the purpose, deep blue reacted. No such thing as strategy, it is a balance of risk and reward. The computer will know regardless of scouting what the opponent is doing and the best possible solution to counter. Also there is no such thing as a timing push because the computer can simply balance army composition and army potential at any given point. Factors such as force fields and storm are difficult to measure
|
On November 24 2012 13:46 DanceSC wrote:Show nested quote +On November 11 2012 12:53 AbideWithMe wrote: Perfect mechanics and micro with predefined build orders yes ofc.
Perfect strategies and scouting with dynmaic BOs not so much.
With certain pefectly executed timing pushes A.I. could beat every human for sure though. Predefined build orders defeats the purpose, deep blue reacted. No such thing as strategy, it is a balance of risk and reward. The computer will know regardless of scouting what the opponent is doing and the best possible solution to counter. Also there is no such thing as a timing push because the computer can simply balance army composition and army potential at any given point. Factors such as force fields and storm are difficult to measure Sorry but this is not true. Both Deep Blue and modern day chess programs have opening libraries as well as end game libraries. They can play these openings perfectly (given the modern development/knowledge of chess). They only start their own computations once the library ended. Also: We were talking about "real" computer players not the Blizzard AI which cheats.
|
|
|
|