|
On November 16 2012 04:23 Cheerio wrote:Show nested quote +On November 11 2012 14:34 Figgy wrote: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.
Yeah, just have an algorithm do things, so easy man! Hey Mr. Algorithm, please check if making lings or pulling workers is viable! Such a task surely isn't complex, right? I mean, it sounds so easy "check xyz!" Done!
Do you not see what you're writing? In this one example alone you're talking about a crapton of decisions and algorithms to react accordingly. Now, what do we do with the roughly other 10^10^10^10^10^10^10^10^10^10 (read: pretty much infinite) possible states that all may require their own perfect reaction?
|
I have not coded any advanced AI, but it sure seems like a lot of work. I mean, obviously the computer is capable of maintaining 1000 apm with no redundancy and less than 5ms of delay on anything. That kind of mechanical superiority isn't very interesting though. The interesting thing is about making a computer beat a human at their strongest point.
It is probably possible but it will be thousands of hours before you have anything near a smart ai.
|
On November 21 2012 04:23 MrTortoise wrote:
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.
SC and Go suffer the exact same problem with depth. You are right in that the complexity class of Go is much larger than that of Chess or Checkers but you don't seem to know why.
We can bound Chess and Checkers at O(EXPTIME) in the size of the board from the simple but powerful observation that after every turn, the number of pieces a player controls either stays the same, or decreases. Given each board state, there are a polynomial number of moves that do not involve taking a piece. Therefore there are an exponential number of turns before the game ends. The depth of the game tree of Chess and related games are asymptotically bounded because of this. This is not true in Go nor SC and for that reason, both are Omega(EXPTIME).
I would think that SC is actually in a larger complexity class than Go from the fact that the "number of turns" in SC grows faster than a constant in the size of the map. Each branch in the Go game tree corresponds to a "subtree" in the SC game-tree.
EDIT: Grammar
EDIT 2: Apparently there are conflicting proofs as to whether go is EXPTIME-complete or PSPACE-hard. This appears to still be somewhat of an open question (?). Regardless, it is at least as hard as chess.
|
Well but automaton isn't a player, automaton knows everything, he knows where the next siegetank is and which ling is focused.
If you want to have an AI to play starcraft it won't know these things, so an AI won't be that good in splitting lings.
|
a futur AI coming in 2025-2035 will dominate anyone
|
On November 21 2012 04:31 Na_Dann_Ma_GoGo wrote:Show nested quote +On November 16 2012 04:23 Cheerio wrote:On November 11 2012 14:34 Figgy wrote: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. Yeah, just have an algorithm do things, so easy man! Hey Mr. Algorithm, please check if making lings or pulling workers is viable! Such a task surely isn't complex, right? I mean, it sounds so easy "check xyz!" Done! Do you not see what you're writing? In this one example alone you're talking about a crapton of decisions and algorithms to react accordingly. Now, what do we do with the roughly other 10^10^10^10^10^10^10^10^10^10 (read: pretty much infinite) possible states that all may require their own perfect reaction? I'm no programmer but checking if pulling scvs is viable is quite easy: restrict the movement of workers and then calculate the amount of workers needed to kill the intruding forces. The allowed losses could be set to 0 but may be an external variable calculated say by the amount of workers the zerg didn't make for sending those lings into your base.
You might argue that with this you could force unnecessary SCV pulls but you can account to this with sending the appropriate number of units back to defend.
My approach would be to try to classify situations based on gametime and evaluate these classes. Theoretically every move is different but in reality it doesn't matter which ling arrives first at your base. E: not every state requires an "own perfect reaction". A broodlord infestor deathball is always the same while on the map. And you can easily allow variance in the number of broodlords/infestors.
|
A lot of people seem to be confusing not-feasible with impossible.
Only a fool would argue that algorithms to construct an AI which outperforms the best humans cannot be written. Whether or not those algorithms will be written remains a practical formality of prioritization and chance.
|
Nestea Vs. Deep Blue? Sorry you lose. The computer will explode
|
If someone did program a deep blue for sc2, the perfect ultimate computer that is programed to handle every situation and scenario over the course of the game, i would fricken love playing against it.
|
On November 21 2012 04:31 Na_Dann_Ma_GoGo wrote:Show nested quote +On November 16 2012 04:23 Cheerio wrote:On November 11 2012 14:34 Figgy wrote: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. Yeah, just have an algorithm do things, so easy man! Hey Mr. Algorithm, please check if making lings or pulling workers is viable! Such a task surely isn't complex, right? I mean, it sounds so easy "check xyz!" Done! Do you not see what you're writing? In this one example alone you're talking about a crapton of decisions and algorithms to react accordingly. Now, what do we do with the roughly other 10^10^10^10^10^10^10^10^10^10 (read: pretty much infinite) possible states that all may require their own perfect reaction?
What?
Things like making lings/pulling drones are decisions that are difficult for HUMANS. They are NOT difficult for a computer. A computer will know exactly how long it will take for a cannon to finish, it will know exactly how long it would take its workers/zerglings to get to the cannon, and it can instantly do a resource optimization where you pull enough workers to kill the cannon fast and not lose too much while not pulling too many (so that you miss out on as little mining time as possible.)
When we see a great player pull just the right amount of workers we call it great game-sense, great timing and experience, but that's simply because a player never outright calculates these things all it is is a good estimate. This is definitely an example of something a computer will do better than a human.
Honestly, I think if you look at strategy in starcraft a series of bottlenecks then the game becomes a lot less complicated in terms strategical response, if you combine this with a machine learning algorithm computers can quickly get a grasp of counters. On top of that since computer can instantly calculate the resource/supply value of your army and buildings on sight and can have a pre-calculated estimates of your total collected resources at time x it can get a lot more factual information from its scouting than a human player.
|
You do not want a computer playing better than humans. Why? Because it destroys the game, I was a Chess Master at 14 willing to become the best but what made me quit? Seeing computer play the game. Chess is pretty much solved these days, there is no more glory in playing it like it was for centuries. Whats the point in watching the best human plays knowing that from an engine point of view, most moves are inaccurate and even accurate once are sometimes by chance because many continuations are inaccurate. There is no way even top GM's can beat an iphone4/5 Chess Engine on equal time odds.
In CS, you can definitely kill noobs that have either WH or Aimbot on because if your game sense is good enough you will always find a way to outsmart them but if both are on, there is pretty much nothing you can do. And if autoshotting is on, the only way you can kill bastards is to wallbang by using their footsteps or bombard with nades because you will be dead in a nanosecond after the first pixel of your head is visible.
|
I think AI based on neural network could do it. All it needs is play A LOT of games first though.
|
On November 21 2012 10:51 OpTiKDream wrote: If someone did program a deep blue for sc2, the perfect ultimate computer that is programed to handle every situation and scenario over the course of the game, i would fricken love playing against it.
All it would take is for computer to calculate MAXIMUM possible power of your army at each given second at every spawn location relative to its own so it will always have just enough time to stop the attack and you will NEVER have even a glimpse of winning. Or if a sadist programs an AI, it will just calculate a weak point where AI army will outmicro a human player no matter the build/location, so it will always attack before you even had a chance because only real chance you could have is with same level of micro as AI. Yeah would be fun for maybe 5-10 games but after that you will just stop playing because of how futile it would be.
|
Maybe it's been mentioned already, but didn't someone try to do this for BroodWar, and the program was only able to get up to something like B- on ICCUP?
|
On November 21 2012 17:19 Fighter wrote: Maybe it's been mentioned already, but didn't someone try to do this for BroodWar, and the program was only able to get up to something like B- on ICCUP? AI technology and processing power goes up alot faster than human capabilities (which are pretty much flat). Not to mention it is all a matter of how much money you want to throw at it.
On November 21 2012 11:22 Kiarip wrote:Show nested quote +On November 21 2012 04:31 Na_Dann_Ma_GoGo wrote:On November 16 2012 04:23 Cheerio wrote:On November 11 2012 14:34 Figgy wrote: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. Yeah, just have an algorithm do things, so easy man! Hey Mr. Algorithm, please check if making lings or pulling workers is viable! Such a task surely isn't complex, right? I mean, it sounds so easy "check xyz!" Done! Do you not see what you're writing? In this one example alone you're talking about a crapton of decisions and algorithms to react accordingly. Now, what do we do with the roughly other 10^10^10^10^10^10^10^10^10^10 (read: pretty much infinite) possible states that all may require their own perfect reaction? On top of that since computer can instantly calculate the resource/supply value of your army and buildings on sight and can have a pre-calculated estimates of your total collected resources at time x it can get a lot more factual information from its scouting than a human player. And there is more. Lets assume he plays terran, and scans the base and natural of a protoss player, including the majority of the toss army (or he scouted it in a different way). The AI will instantly calculate the amount of minerals and gas mined, cross reference that to the amount of buildings and army it knows of, and deduct if the opponent is doing something sneaky. Sure a human tries to do that too, but an ai is so much better at it.
Also for example using changelings is a waste of time against such an ai, it knows of every unit it has exactly where it is, so if anything is seen on the minimap where it shouldnt be, it knows it should kill it.
|
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.
If human can make a decission, and computer can register the same variables then you can always write a program that does it.
|
to program an AI that can beat the best human, you would have to mimic the neocortex of the human brain. Right now, you can only program AI's to do specific builds and react in specific ways (go back to base if attacked), you can't make it go something different. Humans deviate from standard and come up with new builds because of our neocortex. The neocortex has different layers that send feedback to one another and from there you use your memory to complete a task. The Ai's of today are not capable to do that. They don't use memory, therefore they will only be able to execute the things you program them to execute (make units, use specific builds or attack at certain times to name a few).
|
On November 21 2012 19:45 agahamsorr0w wrote: to program an AI that can beat the best human, you would have to mimic the neocortex of the human brain. Right now, you can only program AI's to do specific builds and react in specific ways (go back to base if attacked), you can't make it go something different. Humans deviate from standard and come up with new builds because of our neocortex. The neocortex has different layers that send feedback to one another and from there you use your memory to complete a task. The Ai's of today are not capable to do that. They don't use memory, therefore they will only be able to execute the things you program them to execute (make units, use specific builds or attack at certain times to name a few).
The point is that there isn't an infinite number of possibilitys of how the game can be played. The units and the maps are set in stone. you can't leave the map and you can't build a hydraroach. You also don't have to build an AI that plays perfectly but one who beats every human. No human can micro on three attacks simultaniously. And as others already have mentioned: the Computer gains much more information out of a scan/scout than a human player.
It sure would take some time/money to develop it, but I'm sure it could be done. My guess would be starting with something like ling/muta into blord/infestor in ZvT.
|
On November 21 2012 10:32 ArcLiTe wrote: Nestea Vs. Deep Blue? Sorry you lose. The computer will explode
Trick question. NesTea and Deep Blue are the same entity.
Deep Blue is just the reptilian portion of NesTea's giant brain.
|
Have any of you guys studied Deep Blue? This computer was actually beaten by many many grandmasters. The problem with a computer is that it can be deceived. The grandmasters would rotate strategies, or mix strategies at random in order to trick it. This is because a player can purposely play a move that has a lower payoff, whereas the computer will always choose the highest payoff choice.
So even if you built a computer that could theoretically play perfectly, it still wouldn't be perfect. Computers can't take big crazy risks, they can't think on their feet, and they can't be conditioned in the same way a human can. Plus, starcraft is a game of imperfect information, unlike chess.
|
|
|
|