|
On November 12 2012 15:33 Severus_ wrote:How does a AI beat a human on CS... that doesn't seem right I think no way in hell a bot team can beat teams like fnatic,ESC,Na'Vi..... Reaction time measured in nanoseconds, wallhacks and 100% perfect aim? Human players wouldn't stand a chance.
|
On November 13 2012 19:57 maartendq wrote:Show nested quote +On November 12 2012 15:33 Severus_ wrote:How does a AI beat a human on CS... that doesn't seem right I think no way in hell a bot team can beat teams like fnatic,ESC,Na'Vi..... Reaction time measured in nanoseconds, wallhacks and 100% perfect aim? Human players wouldn't stand a chance.
no wallhacks, they are not cheating.
|
On November 13 2012 09:45 Rassy wrote: Ok 100m year, i didnt see that part and in 100m year it might be possible if we could devellop computers that operate on a quantum level, the posibilitys wich have to be calculated realy are enormous though. Am not talking about good play btw, off course computers can play good. This is about perfect play. Moving a marine 1 pixel north can change everything, this all has to be calculated.
This would still not be enough, not even close. The number of possible move to calculate on a game like sc2 would be infinitely more than a game like chess. You could take the best current super-computer, increase his processing power by 1000000 and it would still be irrelevant.
Developing a decent AI for sc2 would be possible, but there is no way you could make one that operate with a brute-force approch like deep blue, which is the only way to have a perfect and real AI.
|
For CS, If there are physical limits (avatar rotation speed, aiming speed, bullet speed), maybe you could argue that there is a strategy/decision making that is difficult for the AI. If not, pure software woud get you a bot that spins at a few million times a sec while moving and kills "instantly" once you are in sight.
CS AI only becomes interesting if you consider the bot uses the same datastream as the player (sound/image processing to identify targets and to aim) and the same input tools (mouse/keyboard and robotic arms). Could probably still be done, but not easy at all.
Regarding starcraft2, beating any human player with more than a 50% ratio should be reasonnable. Getting 100% win ... map dependent. Getting a perfect game, I don't think so. Real time limits too much the amount of computing power available for each decision. I guess there would always be room for improvement with more computing power / a slower game speed.
|
SC2 would be a lot harder for computers than BW, simply because humans have a much harder time with BW mechanics. Do I think it's possible for a computer to beat humans most of the time? yes. Is it happening anytime soon? no. Is it possible for the computer to win 100% of the time? no.
|
On November 11 2012 14:34 Figgy wrote:Show nested quote +On November 11 2012 13:07 Ettick wrote: I mean it would probably take a while, but couldn't you program the AI to scout and build the correct units and buildings based on what they see, in addition to program it to have perfect macro and micro? Absolutely, 100% never. There is an impossible amount of variables to ever, ever take into account that an A.I. will simply never be able to handle. For example, protoss does a standard FFE and Zerg can't punish it. Zerg is either programmed to All In or get a 3rd hatch. Easy enough. What happens if the 3rd base is cannon rushed and the A.I. didn't scout it until it may or may not be too late to save. How does the A.I know what to do? Do you know how hard it is to program a response to something so simple that a human will be able to decide instantly just through practice? Do I let the hatch die? Do I build lings to save it? How many lings? Does it depend on the amount of cannons? What if my Zerglings get walled off AFTER they are already on the way or in production in a way that a computer cannot possibly forsee that makes it impossible to stop? Do they send the lings anyways? If I don't save it and I have no scouting information, how does the build proceed? What if I have zero scouting, when as a programmer do I set my A.I to rebuild that 3rd base with zero information? When do I build enough units to clear out the cannons? When is it plausable to take your 4th instead of the 3rd base location? Is it possible to make this move on every map? There are THOUSANDS of scenarios from the first 5 minutes of a game that can throw an A.I. off it's set pattern. Even the best of the best Chess computers don't determine their openings, they have a vast opening book with variations made by top GMs because the options early game are simply too vast for the computer to realistically figure it out. People can make these "Easy" decisions because of common sense. Computers can't. Why not? You made some examples why it can be "harder" for an AI than for a human but you never proved it cannot be done. About that 3rd hatch cannon rush. First of all AI should scout that. It's very easy to do either by ovi placement or by sending a drone scout. Secondly even if the AI missed that why would this minor incident throw it off completely? You are thinking about AI as a set of BOs that it can execute and thats all. It is like making a chess AI playing only by the book openings and having absolutely no opinion of a position of his own. Also there are not many decisions in that cannon rush scenario. Is there enough time to save the hatch? An algorithm should check if making lings or pulling workers is viable. If not just expo elsewhere or mass drones of 2bases. If yes get lings till cannons die or till it is clear the expo is doomed (pretty easy if statement). When you get lings launch an algorithm to determine the best use. If the hatch is being attacked clearly it would be to send them there. When they arrive to your army check if the amount of lings is enough to break cannons (take pathing into consideration). If yes attack. If no wait for more. If hatch is doomed resume drones and send lings to do something else.
|
If you are asking whether it is theoretically possible, the answer is yes. In fact, it's not hard to prove that any 1v1 RTS must provably have an optimal strategy if you recognize that is just a specific type of extensive-form game (in this case, one with imperfect knowledge and an infinite action space).
However, it isn't clear whether or not knowing this strategy (the nash equalibrium) has any value as it certainly cannot be reproduced by any human and more importantly, a method of approximating the nash equalibrium is different from how humans think. A Deep Blue will approximate the nash using heuristics and machine learning. A human plays SC2 based on case-based decision trees.
Computationally, it is certainly not feasible using today's technology. Chess has been solved because it's game tree is relatively simple. Even heads-up poker has been completely solved (i.e you cannot possibly beat Hyperborean more than 50% of the time). But Starcraft is different in that the action space is "somewhat" infinite. Actions are definitely finite (there are a finite number of pixels, but the time axis is hard to discretize). It will probably be a long time before we can approximate the nash equalibrium to a good enough degree that it actually wins games and even longer before a computer can execute perfect play.
|
so many people say computers use "brute force" in chess is simply not true. If computers would use brute force they would never ever beat humans at chess. There are way to much to calculate in any given possition that you could take the best supercomputer in the world times 1000 and if it used brute force it would still take thousands of years at least. Chess computers dont brute force. They calculate like 100k possitions a second but its not even close to brute force.
|
On November 21 2012 03:23 Caelestis wrote: If you are asking whether it is theoretically possible, the answer is yes. In fact, it's not hard to prove that any 1v1 RTS must provably have an optimal strategy if you recognize that is just a specific type of extensive-form game (in this case, one with imperfect knowledge and an infinite action space).
However, it isn't clear whether or not knowing this strategy (the nash equalibrium) has any value as it certainly cannot be reproduced by any human and more importantly, a method of approximating the nash equalibrium is different from how humans think. A Deep Blue will approximate the nash using heuristics and machine learning. A human plays SC2 based on case-based decision trees.
Computationally, it is certainly not feasible using today's technology. Chess has been solved because it's game tree is relatively simple. Even heads-up poker has been completely solved (i.e you cannot possibly beat Hyperborean more than 50% of the time). But Starcraft is different in that the action space is "somewhat" infinite. Actions are definitely finite (there are a finite number of pixels, but the time axis is hard to discretize). It will probably be a long time before we can approximate the nash equalibrium to a good enough degree that it actually wins games and even longer before a computer can execute perfect play.
Chess hasn't been solved though. Not even in a weak sense (only knowing the outcome of every possible position but not the perfect strategy). Maybe you meant checkers which was solved back in 2007?
|
On November 11 2012 12:56 shindigs wrote: There was an AI released that had perfect unit control that basically made marines super imbalanced. It could split near perfectly and avoid banelings like no one's business. Zerglings spread out to reduce splash damage from tanks and basically overran everything.
I think it'd be interesting if we could set a cap on what the AI can do with mechanics, and make it somewhat equatable to human play. Maybe a 300-400 APM limit? Someone in AI please let me know if this is possible.
I think there's a realm for super AI's to battle it out there. Does perfect zergling control or perfect marine control win out at the end of the day?
300 Apm with computer efficiency is equivalent to about 10,000 APM.
|
On November 13 2012 20:18 DertoQq wrote:Show nested quote +On November 13 2012 19:57 maartendq wrote:On November 12 2012 15:33 Severus_ wrote:How does a AI beat a human on CS... that doesn't seem right I think no way in hell a bot team can beat teams like fnatic,ESC,Na'Vi..... Reaction time measured in nanoseconds, wallhacks and 100% perfect aim? Human players wouldn't stand a chance. no wallhacks, they are not cheating.
When you think of a bot team like the bots that come standard in a game like CS:S or CS:GO, of course any competent player can probably 1v5 expert bots and win a match.
Now - have you ever played in a public server with someone who was aimbotting? Maybe not wallhacking, but instantly 1shotting everyone in the head as soon as a pixel appears on their screen? Maybe they were speedhacking as well. Now think of that without the speedhacking. The professional players (even fnatic, NiP, ESC, 51, and the likes) wouldn't be able to kill any of the opposing team besides using grenades or known spam spots. I would be surprised if a professional team would be able to get more than 4 rounds against a team of computers.
|
On November 21 2012 03:34 Legatus wrote:Show nested quote +On November 21 2012 03:23 Caelestis wrote: If you are asking whether it is theoretically possible, the answer is yes. In fact, it's not hard to prove that any 1v1 RTS must provably have an optimal strategy if you recognize that is just a specific type of extensive-form game (in this case, one with imperfect knowledge and an infinite action space).
However, it isn't clear whether or not knowing this strategy (the nash equalibrium) has any value as it certainly cannot be reproduced by any human and more importantly, a method of approximating the nash equalibrium is different from how humans think. A Deep Blue will approximate the nash using heuristics and machine learning. A human plays SC2 based on case-based decision trees.
Computationally, it is certainly not feasible using today's technology. Chess has been solved because it's game tree is relatively simple. Even heads-up poker has been completely solved (i.e you cannot possibly beat Hyperborean more than 50% of the time). But Starcraft is different in that the action space is "somewhat" infinite. Actions are definitely finite (there are a finite number of pixels, but the time axis is hard to discretize). It will probably be a long time before we can approximate the nash equalibrium to a good enough degree that it actually wins games and even longer before a computer can execute perfect play.
Chess hasn't been solved though. Not even in a weak sense (only knowing the outcome of every possible position but not the perfect strategy). Maybe you meant checkers which was solved back in 2007?
I'm using the word "solved" in the sense that you can produce an epsilon-approximation of the optimal strategy for any epsilon in finite time. Obviously you can pursue this agenda by simply enumerating the 10^123 game-tree states but that would take a long, long, (...long) time.
EDIT: According to wikipedia, chess is exponential-time-complete so of course it can be solved in "finite" time but you would hope that if the world united in the name of chess, one of our grandchildren can hold a 10^23ish sized hash table that is the optimal strategy. =D
There is certainly room for improvement in real-time chess as even bots have limited amount of time to make a move. Because of this, they expand the game tree as fast as they can, and then when they run out of time, they make a decision based on the best heuristic at the terminal node. So you can improve a chess-bot by 1) choosing better heuristics, 2) better pruning, 3) more computing power.
But if you are asking if there exists an unbeatable strategy in chess (wins at least as much as loses), the answer is yes.
|
On November 21 2012 03:33 sertas wrote: so many people say computers use "brute force" in chess is simply not true. If computers would use brute force they would never ever beat humans at chess. There are way to much to calculate in any given possition that you could take the best supercomputer in the world times 1000 and if it used brute force it would still take thousands of years at least. Chess computers dont brute force. They calculate like 100k possitions a second but its not even close to brute force.
It's probably something along the lines of what I'll call "educated brute force". It will take some likely best moves and run through some simulation and pick the best one from those available. It's why there was a huge controversy in the one Deep Blue vs. Kasparov game. I think if I remember correctly, Kasparov left a piece out in the open that would have been free for the computer to take - but would have allowed Kasparov to continue on an extremely complex series of moves that would lead to a win. The computer, however, opted not to capture the piece. Kasparov (and others) argued that another grandmaster must have intervened, because it was clearly not a computerized decision that made that move.
|
On November 21 2012 03:44 Caelestis wrote:Show nested quote +On November 21 2012 03:34 Legatus wrote:On November 21 2012 03:23 Caelestis wrote: If you are asking whether it is theoretically possible, the answer is yes. In fact, it's not hard to prove that any 1v1 RTS must provably have an optimal strategy if you recognize that is just a specific type of extensive-form game (in this case, one with imperfect knowledge and an infinite action space).
However, it isn't clear whether or not knowing this strategy (the nash equalibrium) has any value as it certainly cannot be reproduced by any human and more importantly, a method of approximating the nash equalibrium is different from how humans think. A Deep Blue will approximate the nash using heuristics and machine learning. A human plays SC2 based on case-based decision trees.
Computationally, it is certainly not feasible using today's technology. Chess has been solved because it's game tree is relatively simple. Even heads-up poker has been completely solved (i.e you cannot possibly beat Hyperborean more than 50% of the time). But Starcraft is different in that the action space is "somewhat" infinite. Actions are definitely finite (there are a finite number of pixels, but the time axis is hard to discretize). It will probably be a long time before we can approximate the nash equalibrium to a good enough degree that it actually wins games and even longer before a computer can execute perfect play.
Chess hasn't been solved though. Not even in a weak sense (only knowing the outcome of every possible position but not the perfect strategy). Maybe you meant checkers which was solved back in 2007? I'm using the word "solved" in the sense that you can produce an epsilon-approximation of the optimal strategy for any epsilon in finite time. Obviously you can pursue this agenda by simply enumerating the 10^123 game-tree states but that would take a long, long, (...long) time. There is certainly room for improvement in real-time chess as even bots have limited amount of time to make a move. Because of this, they expand the game tree as fast as they can, and then when they run out of time, they make a decision based on the best heuristic at the terminal node. So you can improve a chess-bot by 1) choosing better heuristics, 2) better pruning, 3) more computing power. But if you are asking if there exists an unbeatable strategy in chess (wins at least as much as loses), the answer is yes. OK, thanks for clarifying that. I certainly wouldn't refer to an approximation of the optimal strategy as a solution to the game. I think that's misleading at best. Instead I would settle for complete knowledge of the outcome under optimal play for each possible position, but without necessarily knowing the sequence of moves that lead to that outcome. For checkers, which has a much smaller state space, it has already been proved that the initial position is a draw under perfect play.
|
On November 21 2012 03:55 Legatus wrote:Show nested quote +On November 21 2012 03:44 Caelestis wrote:On November 21 2012 03:34 Legatus wrote:On November 21 2012 03:23 Caelestis wrote: If you are asking whether it is theoretically possible, the answer is yes. In fact, it's not hard to prove that any 1v1 RTS must provably have an optimal strategy if you recognize that is just a specific type of extensive-form game (in this case, one with imperfect knowledge and an infinite action space).
However, it isn't clear whether or not knowing this strategy (the nash equalibrium) has any value as it certainly cannot be reproduced by any human and more importantly, a method of approximating the nash equalibrium is different from how humans think. A Deep Blue will approximate the nash using heuristics and machine learning. A human plays SC2 based on case-based decision trees.
Computationally, it is certainly not feasible using today's technology. Chess has been solved because it's game tree is relatively simple. Even heads-up poker has been completely solved (i.e you cannot possibly beat Hyperborean more than 50% of the time). But Starcraft is different in that the action space is "somewhat" infinite. Actions are definitely finite (there are a finite number of pixels, but the time axis is hard to discretize). It will probably be a long time before we can approximate the nash equalibrium to a good enough degree that it actually wins games and even longer before a computer can execute perfect play.
Chess hasn't been solved though. Not even in a weak sense (only knowing the outcome of every possible position but not the perfect strategy). Maybe you meant checkers which was solved back in 2007? I'm using the word "solved" in the sense that you can produce an epsilon-approximation of the optimal strategy for any epsilon in finite time. Obviously you can pursue this agenda by simply enumerating the 10^123 game-tree states but that would take a long, long, (...long) time. There is certainly room for improvement in real-time chess as even bots have limited amount of time to make a move. Because of this, they expand the game tree as fast as they can, and then when they run out of time, they make a decision based on the best heuristic at the terminal node. So you can improve a chess-bot by 1) choosing better heuristics, 2) better pruning, 3) more computing power. But if you are asking if there exists an unbeatable strategy in chess (wins at least as much as loses), the answer is yes. OK, thanks for clarifying that. I certainly wouldn't refer to an approximation of the optimal strategy as a solution to the game. I think that's misleading at best. Instead I would settle for complete knowledge of the outcome under optimal play for each possible position, but without necessarily knowing the sequence of moves that lead to that outcome. For checkers, which has a much smaller state space, it has already been proved that the initial position is a draw under perfect play.
Checkers is indeed a depressing game to play for those who know this =(
|
Deep Blue was there to prove a point and it did just that.
There's no need to explore this further, as the results will be the same and the time+money costs will be far greater.
|
On November 21 2012 04:01 Novalisk wrote: Deep Blue was there to prove a point and it did just that.
There's no need to explore this further, as the results will be the same and the time+money costs will be far greater.
A lot of the lessons learned in Deep Blue were used to create IBM Watson. There are many benefits to exploring this subject and as you can see, they transcend the boundaries of simply solving games.
A "Deep Blue" of Starcraft would be a major breakthrough.
|
My guess is that even if for some reason tons of resources were poured into it the AI would still be far below top players. The bw AI's are all easily abusable, and are a joke for any player to defeat.
I think both Chess and Jeopardy computer programs being able to beat humans is cool, but they obviously have raw computing power for option exploring and decision weighting (chess) and unfair reflexes when provided with super-computing power (Jeopardy). Though, the fact that Watson understands the questions (or answers rather) is incredible. Makes me wonder why translating software isn't better than it is..
In terms of the level of complexity a game of bw or sc2 simply has a ton more going on and too many options to simply brute force it.
|
You're probably right. But I would note that the AI's that came out of the Berkeley research program focused on micro-related bots rather than game theoretic ones.
About the BW AI, does everyone remember when you attack a hatchery/CC/nex with one worker at the beginning of the game, ALL of the enemy workers suddenly follow your worker? =D
|
sc2 is a lot easier for computers to rape humans at than a lot of other games.
The reason? The game is 99% about mechanics.
Scouting is probably not that hard given that its not hard to do a path analysis to establish when the really critical buildings go down for various build order splits.
so the only real way to win will be cheeses but they would only work once.
But the real problem is that the c omputer actually has access to a crap ton more data than a player does because blizzard only made FOW a clinet side afterthought and send allt he info to players anyway.
SC is MASSIVLEY easy compared to go. Go is difficult due to depth ... sc is difficult due to number of operations per second required to be mildy profficient. Tactically its actually fairly simple once you cut out all the strats that make no sense. Eg any strat involving a carrier because other strats would perform its role better. I thinkt here will be lots of approximations that you can make that will add up to be a far better decision process than a human can manage.
You cross a build order generator with a rudimentary scouting algorith with automaton and you will have an aopponent that would be nigh on impossible for all but the best to beat.
As for the comment about go programs. I know many 1kyu players that destroy 6 dan go programs. Because they do have holes in their games adn people exploit them.
Being able to win the first game is very different to winning consistently. A computer sc2 program can definatley win 1 off.
The point is not that you need to solve a game, you just need to be good enough and computers can do a hell of a lot of things in sc2 world better than people. Its kind of why people use them to design build orders ...
The fact is there will be a nash equilibrium in build orders and one race WILL be more op than the rest. There will be a sequence of moves that result in a very very strong build order with all its branches mapped out. Whether you like it or not s2 is a sequence of moves through apm - it is very abstract i grant though. The real problem with nash though is that you will have no way of testing whether what you currently think is best is actually best.
|
|
|
|