Once again I am posting something that may result in some hate. If your first thought is some variation of "lol u dont no wat ur talking about", you're probably right and feel free to say so. But I love abstracting things and I wanted to share. <3
=====
When I was in middle school, I prided myself in knowing that I would never lose a game of tic-tac-toe for the rest of my life. I could be playing the smartest person in the world, but guess what? I won't lose. Why? Because of this simple fact: if two people play perfect tic-tac-toe, the game will end in a draw. If you're organized and you have a free hour, it isn't too hard to prove this by playing out every possible game (up to rotations and reflections). If you do this, every time a friend asks you to play tic-tac-toe, you can say, "We might as well agree to a draw and save the time!" The game is all figured out.
A similar game is Connect Four. Though it would probably take more than an hour to prove it by hand, it turns out that the first player can always force a win with perfect play. No matter what moves the second player picks, the first can always find a response that leads to a win. So next time you play Connect Four and your opponent asks, "You want to go first?", you can say, "You could've just asked me, 'You want to win?'" The game is all figured out.
In July, 2007, the game of checkers was solved. More specifically, it was found that if two perfect players sat down for a game of checkers and played perfectly, then the game would result in a draw. Stated another way, a perfect checkers player cannot lose a game. Though you probably can't prove this in an hour either (PM me if you can, we'll write a paper), if your uncle asks if you want to play checkers, you can safely say, "We might as well play tic-tac-toe!" The game is all figured out.
Jonathan Schaeffer, wrote Chinook, the program that solved checkers
There are still other games like rock-paper-scissors, whose "perfect play" is simply to roll the dice. No matter how much your brother might insist that he has a perfect system for playing a rock-paper-scissors best-of-5, it is complete nonsense. In fact, for any strategy that does not rely on randomness, there exists another strategy that will beat it. Just last week my brother and I were fighting over who should bring out the trash, and he challenged me to a best of 7. (Really, 7.) I really did say, "We might as well toss a coin." The game is all figured out.
I'm a chess player myself: what am I to make of this game? At the time of this post, chess has not been solved in the same way as any of the above games. Chess computers have existed for decades, but it could be decades more until the technology exists to map out this game, if that ever happens. When I look at a chess set, I am afraid of the game. I am scared of the uncertainty of winning and losing. I am scared of being caught in a trap laid by a better player. I am scared of staring at an endgame, knowing that every possible move is a losing one. I am scared of the thought of driving home from a chess tournament, crying because I'm so pissed off at myself, after some cute high school freshman girl just so happens to be rated 200+ points more than me and knocks me out in the first round (hypothetically). If a chess grandmaster asked me to play a game of chess with him/her, anything could happen. Maybe I'll get some divine insight into a particular position that he/she never considered before and I'm able to take a game from him/her. After all, he/she can't play perfect in every position, or the game would be solved! But in the same way, if my little brother challenged me to a chess match (which unfortunately never happens), I can't be sure I'll win all the time, no matter how much better I think I am, for the same reasons. In both instances, I can only say, "Alright, let's play," and do my best. The game is not all figured out.
Kasparov vs. Deep Blue, the iconic man vs. machine chess match
I was looking at my Starcraft: Brood War battle chest box the other day, running through some thought experiments. What would happen if a "perfect" Protoss player played a "perfect" Zerg player on some theoretical, "perfect" PvZ map? Trusting in BW's balance and taking checkers as the model, I imagined some 5-hour long game: with the money long gone from the map and both armies having killed each other, the game resorts to probe vs drone micro, culminating in the P's last pylon and the Z's last extractor falling at the exact same time. Then the P and the Z would look up at each other, smile, and say "gg, re?". Taking this analogy a bit further, what would a game between a perfect P and an imperfect Z look like? Well, by definition, the Z would make a mistake somewhere. Maybe he missed his 184/184 overlord by 0.5 seconds. Maybe he mismicroed during a crucial battle and lost an extra zergling. Maybe the Z's building placement was wrong so the drones took a little too long to get to the mineral patches from the eggs. In any case, the result would be the P gaining some sort of advantage that compounded across the rest of the game, and, since P's play is perfect, Z could do nothing to come back due to that one mistake. Indeed, if the Z could make a mistake and still break even with the P, then a perfect Z who did not make this mistake would have to beat the P, or else it wouldn't be a mistake made by the imperfect Z, in which case the balance of PvZ is contradicted!
But maybe our faith in BW is in vain, and PvZ is, in fact, imbalanced: maybe perfect Protoss play can always adapt and beat any variation a Zerg might try, just like in Connect Four.
Or worse, is PvZ like rock-paper-scissors, where perfect play would simply be rolling the dice? After all, you can't guarantee perfect information in any matchup at all times, so perhaps a matchup between a perfect P and a perfect Z would just be both sides randomly choosing a percentage build? Is PvZ and BW in general just a glorified coin toss at the level of perfect play?
Personally, I hope BW is like chess, and will never be "solved" (at least not in the foreseeable future) in the same way that any of the other above games are, constantly evolving as new ideas are continually brought to progamer matches (and elsewhere!). Chess has been around for centuries, and yet the game is still alive: books are still being written about various openings and systems, tournaments are still being held all around the world, and I still get a copy of Chess Life every month. Perhaps it is because chess is so resistant to our attempts to figure it out that it remains so interesting even now. Young child prodigies, senior citizens, nerdy college BW players, pretty high school girls... no one is immune to the calling of this mysterious mental challenge. But what happens should a breakthrough in computing allow technology to beat chess? Presumably interest would decrease as the curtains open and the lights shine on what was once a seductive enigma shadowed in uncertainty. Is it too much of a stretch to compare this with BW? I, at least, have maintained interest in such a (relatively) old game only because it feels like there is always something more to be understood about the game, even for those progamers that spend hours daily learning about it. Perhaps the game has survived this long only because of this apparent lack of a limit to what can be achieved by playing it.
I sincerely hope that, when I'm old and wrinkled, chatcrafting in the Bnet 2.0 op irc chat channel, if someone asks me, "hey FiBsTeR want to 1:1 in bw?", I'll have no choice but to respond, "gogo!".
After talking about "solved games" and "perfect play", I feel obliged to post some game theory related problems. If anyone else has any good ones, please post them!
[1] Consider a game called "double chess" in which the rules are all the same except each player is allowed two moves per turn. Prove that the second player cannot force a win.
[2] There is a circular table and a large pile of quarters. You and a friend take turns placing quarters on the table, such that no two quarters overlap. A player loses if he/she cannot place another quarter on the table. Do you want to move first or second?
You can't play a perfect game because of the luck factor. You don't know what your opponent is doing so you can't counter perfectly. For example, if your opponent goes 14cc, and you go 9 pool, they're going to die, even with perfect play. If you play perfectly safe, your opponent can counter with risky economic builds.
theoretically, even if you both go "standard, perfected builds", because of map imbalance and start position imbalance, you will never have the perfect build. plus, its physically impossible to play perfectly, unless the game never gets into lategame.
Perfect play is not humanly possible. Our resident AI programmers' bots micro a control group and change of muta near perfectly at up to 30,000apm. That's just a handful of units.
Someone asked this question on another thread long ago. Don't feel like finding it, I remember one response went something like "If a perfect terran played a perfect protoss, then the protoss would always stay out of range of the terran and the terran would always use his tank's superior range to hit the toss" effectively a shield and spear conundrum.
The perfect play boils down to maps of course, I can think of a map where terrans would win in 2 minutes no matter what, imagine your main buildings were all close to each other and block your workers from exiting or having space to place any additional buildings. The terran could lift off and attack the opponent's main building before the opponent had anything ready.
On a map like python however, a zerg would win because the drone is superior to the probe is superior to the scv with perfect micro. In effect, the zerg would be able to mine while chasing all the probes around, preventing them from mining, perhaps cornering them, and finishing them off while sustaining zero damage.
edit: Just to add, perfect play hasn't yet been achieved by computers, but I am assuming the FSM played against god. In addition, the reason I say that drones are better than probes and scvs is because of their range, attack animation, and acceleration. I am aware that scvs are physically stronger in the hands of human players.
starcraft can't be played perfectly because, it's not just a mental game like chess connect four and whatever, there's a physical limitation that humans have (similar to the video above) and thus can never be preformed perfectly.
sc can't be solved the same way as chess because as people have said, there is a physical skill factor involved (apm, micro, macro). Another difference is lack of information. With a chessboard, you can see everything your opponent is doing. In sc, there is fog and the enemy can play psychological tricks. Furthermore, strategies that may be popular and effective at one time may phase out in response to map changes or just evolution of play.
I remember in the thread which asked which race would win if played perfectly, a response was that the protoss could use their initial four probes and always micro and outrange the other two races to win.
SC can't be solved because there are some random factors in it : high ground advantage, pandabearguy movement. If I didn't forget another random factor, then it could be doable by a super robot, an AI or something if Starcraft is patched to handle as many actions as possible in a single frame.
Of course it depends on the map : if the 4 initial probes can just win right away, then there is no high ground advantage or pandabearguy in the way.
perhaps build and strategywise the game can be solved. It already looks like it's coming to this currently, which is why we have such diverse weird maps all the time.
But it is nearly impossible to play perfectly and there are luck elements to the game as well. It would be like trying to say poker will be solved.
The reason why Starcraft is not solvable is because a human being is not even remotely close to being a perfect player. The fastest recorded APM was 808 by July, and there was still like a million things he could have done more. If each individual unit was controlled by a single player, each player would ideally be doing 100-400 APM depending on what unit they are.
On June 21 2010 12:11 Sinensis wrote: Perfect play is not humanly possible. Our resident AI programmers' bots micro a control group and change of muta near perfectly at up to 30,000apm. That's just a handful of units.
Sorry for the confusion: let's say that perfect play in this context does not have to be humanly achievable, or even achievable by computers. Let's define it simply as a strategy that is (1) allowed by the rules and restrictions of the game (not the players) and (2) maximizes the probability of winning, no matter the play of the opponent. (In some games like Connect Four, this optimal probability is in fact 100%. For rock-paper-scissors it is 33%.)
So perfect play does not mean execution of standard builds with <100000 APM or even perfect execution of currently popular builds. It is simply a strategy that optimizes the percentage of winning, no more. It is abstract, yes, but I think it's unambiguous.
On June 21 2010 11:57 neobowman wrote: You can't play a perfect game because of the luck factor. You don't know what your opponent is doing so you can't counter perfectly. For example, if your opponent goes 14cc, and you go 9 pool, they're going to die, even with perfect play. If you play perfectly safe, your opponent can counter with risky economic builds.
You are assuming that a perfect T player can 14cc or that a perfect Z player can 9pool. It could be that, with the definition given above, perfect T play cannot include 14cc and that perfect Z play cannot include 9pool. In the same way, "perfectly safe" builds are not necessarily perfect play: as you said, it is possible that builds that try to defend against too many things at once reduces the probability of winning, and so wouldn't qualify as perfect play.
On June 21 2010 12:05 majesty.k)seRapH wrote: theoretically, even if you both go "standard, perfected builds", because of map imbalance and start position imbalance, you will never have the perfect build. plus, its physically impossible to play perfectly, unless the game never gets into lategame.
Granted. As I mentioned above, in these thought experiments, let's only consider theoretical maps that are perfectly balanced. If they don't exist for any non-mirror matchups, then we can still ask the same questions about mirror matchups: for example, whether perfect play in ZvZ revolves around percetange builds or not.
On June 21 2010 12:31 krndandaman wrote: starcraft won't be solved lol. it has alot of luck factor as well as way too many variables. what happens if pandabearguy gets in the way of tank moving up to push? even that makes a difference.
it just can't be done, my brain is boggled just thinking about every single variable
Rock-paper-scissors is still solved and is entirely based on luck. There is no skill involved. Solved does not mean that perfect play wins 100% of the time.
On June 21 2010 12:35 mdainoob wrote: sc can't be solved the same way as chess because as people have said, there is a physical skill factor involved (apm, micro, macro). Another difference is lack of information. With a chessboard, you can see everything your opponent is doing. In sc, there is fog and the enemy can play psychological tricks. Furthermore, strategies that may be popular and effective at one time may phase out in response to map changes or just evolution of play.
The lack of information is precisely the reason why we might even consider that perfect play revolves around percentage builds. If the two players had vision of each other then of course there would be no such thing as percentage builds. Note, though, that even Connect Four provides perfect information for each player yet the first player can still force a win since he can always respond with a winning move, no matter what the second player does.
On June 21 2010 12:46 CharlieMurphy wrote: perhaps build and strategywise the game can be solved. It already looks like it's coming to this currently, which is why we have such diverse weird maps all the time.
But it is nearly impossible to play perfectly and there are luck elements to the game as well. It would be like trying to say poker will be solved.
For the most part, some formats of hold'em are solved, certain SNG structures for example. It's solved (and was solved quickly) because at its core it is a game fundamentally comprised of actions and decisions that can be measured quantitatively. From there, solving the game using fundamental game theory and mathematics can be done (with the help of a computer of course).
StarCraft can't be "solved" due to variable, disproportionate circumstances (mostly wrt maps) and because the efficacy of each decision has no "cap" expected value (so it's not easy to quantify). If you can micro some marines and medics to kill off a Zerg Spire, Den, a bunch of drones, etc. you have raised the efficacy of the "Use Marines/Medics to Attack Zerg Base" decision to an incredible degree (as a newb would've unwillingly minimized potential damage, and would've lost his units a lot sooner). However, there is no quanitifiable scenario where "perfect" mm micro states that specifically X will happen, and that's why solving SC is hard (or impossible).
On June 21 2010 13:09 jalstar wrote: Rock paper scissors isn't 33% for each. People tend to go rock most, then paper, then scissors.
He's describing RPS in a vacuum wherein no external factors influence anything and the game is simply mathematical. You are given 3 decisions with equal values, one no better than the other.
[1] every strategy player 2 can use, player 1 can use as well, since for player 1's first move, he can move a knight out and then back to its original position; in other words, player 1 can restart the game, except now the player positions are reversed. so if player 2 has a forced win, then so does player 1, which means player 2 doesn't have a forced win after all.
[2] second. whenever player 1 places a quarter, say in some spot S, you should place a quarter in the spot that is diametrically opposed to S on the table. to see that you will never lose with this strategy, note the following invariant: after you have placed your quarter (on any move), you can spin the table 180 degrees, and the pattern of quarters on the table will not have changed. so if player 1 places a quarter in spot S, then spot S+180 degrees must be free as well ("undo" player 1's last move -- the quarter in spot S -- and apply the invariant)
It's impossible to play a perfect game of starcraft. For one, a lot of it is mindgames, you have to fool your opponent. It is not always viable to scout, and you may not see the difference between the two. A suitable response to both will not be better than a suitable response to one. The same is true with chess, really. Limited information is also a factor that prevents a perfect game. If a player is expected to go 3 hatch before pool, 14CC is a viable option. But if they decide to mix it up for some reason and 5 pool, you lose, short of some horrible mismicro that even a D Zerg player wouldn't make. So no, I don't see Starcraft being figured out in the same way.
On June 21 2010 13:31 spencer wrote: solutions for the game theory puzzles + Show Spoiler +
[1] every strategy player 2 can use, player 1 can use as well, since for player 1's first move, he can move a knight out and then back to its original position; in other words, player 1 can restart the game, except now the player positions are reversed. so if player 2 has a forced win, then so does player 1, which means player 2 doesn't have a forced win after all.
[2] second. whenever player 1 places a quarter, say in some spot S, you should place a quarter in the spot that is diametrically opposed to S on the table. to see that you will never lose with this strategy, note the following invariant: after you have placed your quarter (on any move), you can spin the table 180 degrees, and the pattern of quarters on the table will not have changed. so if player 1 places a quarter in spot S, then spot S+180 degrees must be free as well ("undo" player 1's last move -- the quarter in spot S -- and apply the invariant)
For the 2nd one, what if player 1 places the quarter in the exact center of the table?
I just want to say that you are wrong about rock paper scissors being like flipping a coin. Playing random is only the optimal strategy under certain assumptions about the way your opponent plays. Let me give you a very simple example to show this: suppose you play against someone who plays rock 100 times in a row. What are you going to choose for your 101st move? You can exploit your opponent's play in rock paper scissors when your opponent is playing suboptimally (like your brother probably would be).
For starcraft, don't worry about it being solved. It's insanely high dimensional and some dimensions are infinite. This means that the same techniques used to "solve" checkers are not applicable to solving starcraft, and furthermore the vast majority of learning algorithms aren't feasible for it.
You clarified your operative definition of "perfect play" and addressed the issue of lack of information in your replies to other peoples' posts.
On June 21 2010 13:01 FiBsTeR wrote:
Sorry for the confusion: let's say that perfect play in this context does not have to be humanly achievable, or even achievable by computers. Let's define it simply as a strategy that is (1) allowed by the rules and restrictions of the game (not the players) and (2) maximizes the probability of winning, no matter the play of the opponent.
The lack of information is precisely the reason why we might even consider that perfect play revolves around percentage builds. If the two players had vision of each other then of course there would be no such thing as percentage builds.
My understanding of your premise is that every action each player performs maximizes that player's probability of winning. This begs the question of how these players calculate the probability of success for every possible action. Even if the players can solve some formulas to arrive at these probabilities instantaneously, it is important to understand how they found said formulas.
e.g. f(x1,x2,x3,...,t) = A where x1, x2,x3,... are pieces of available information and t is time and A is the action which maximizes probability of victory.
Given the lack of knowledge of the opposing army's position/size/composition, such a formula would not necessarily output the same action that an equation based on full knowledge of such details would output. Similarly, different equations based on incomplete information would also yield different results. How would one choose the proper equation? Would it be based on prior statistical performance of that equation? How would one know if a successful equation fits into this definition of "perfect?"
If we write these equations, they have to be based on our human understanding of the game of StarCraft. If our understanding of the game is imperfect or if we hold some bias, can we write an equation which tells us the "perfect" action?
This is definitely an interesting and thought-provoking article.
To those interested in these questions, this is a fantastic article by Kasparov about Deep Blue and the 'solving' of chess. He's actually a very articulate and interesting writer. http://www.nybooks.com/articles/23592
Haven't a clue what to throw next? Then go with Paper. Why? Statistically, in competition play, it has been observed that scissors is thrown the least often. Specifically, it gets delivered 29.6% of the time, so it slightly under-indexes against the expected average of 33.33% by 3.73%. Obviously, knowing this only gives you a slight advantage, but in a situation where you just don't know what to do, even a slight edge is better than none at all.
On June 21 2010 12:42 Avidkeystamper wrote: I remember in the thread which asked which race would win if played perfectly, a response was that the protoss could use their initial four probes and always micro and outrange the other two races to win.
On June 21 2010 12:28 Hidden_MotiveS wrote: Someone asked this question on another thread long ago. Don't feel like finding it, I remember one response went something like "If a perfect terran played a perfect protoss, then the protoss would always stay out of range of the terran and the terran would always use his tank's superior range to hit the toss" effectively a shield and spear conundrum.
uh...? That analogy doesn't even work in SC. If anything, I'd expect Terran to win because he can perfectly lay mines and spread tanks and perfectly micro his units to never overkill and avoid friendly fire when possible.
All games can be "solved" in theory. Granted, the number of discrete game permutations might rapidly exceed the number of atoms in the known universe, and then you're never actually going to see 'solved' play, but it is a tautological truth that there exists perfect play for any game you want to name.
With regards to SC, you're not going to see perfect play until strong AI is developed (and is pointed at SC, which is itself unlikely). The physical limitations of human players enforces a hard APM cap at some point, and unless the game is such that beyond that cap no extra APM can be effective, humans will never be able to reach perfect play.
After talking about "solved games" and "perfect play", I feel obliged to post some game theory related problems. If anyone else has any good ones, please post them!
[1] Consider a game called "double chess" in which the rules are all the same except each player is allowed two moves per turn. Prove that the second player cannot force a win.
[2] There is a circular table and a large pile of quarters. You and a friend take turns placing quarters on the table, such that no two quarters overlap. A player loses if he/she cannot place another quarter on the table. Do you want to move first or second?
Can't both of those be solved by the strategy-stealing argument?
I agreed with the attitude of the OP. Not everyone understands what it means to "solve" a game; OP gets it, and asks the interesting question of whether SC can be solved.
There is a difference between solving a game of complete information (also called perfect information), like chess, and solving a game of incomplete information like Starcraft. A popular misconception is that games that have incomplete information can't be solved. or that it can't be solved if it contains random factors like rolling a dice, or miss chance. A game of incomplete information can be solved, and the solution is a mixed strategy.
Another issue is that unlike chess, we still do not know the complete rules of the game as of now. For example, when Marines shoot, they have random cooldown. What are the possible cooldown values, and what is the probability of each? Also, we are not completely sure of the miss rate shooting up cliffs: is it 50%? 55%? Another question is unit pathing and how exactly do units move. Can units move every which way, or are there only eight directions that units can move in? This game is played through software which is proprietary, and contains secrets. Until we unlock those secrets, we can't begin the work required to solve it.
It's not just the incomplete information which is a luck factor, there's actually tons of luck factors... Three/four of my "favorite" ones:
Path finding plus splash damage Send in a group of 12 zealots into 10 siege tanks multiple times and watch how every time there's a slightly different outcome (number of units left standing or amount of damage taken). Or do the same attack from a slightly different angle and watch how due to path finding and luck with splash damage the outcome is different as well, because some zealots might clump together a bit more or not and therefore take more damage or not. Or just watch how completely luck-based spider mines are. Terrans spam them everywhere, and how much damage they do (or don't do) over the course of the game makes a huge difference in TvP. And this is not just "they do a lot of damage when P doesn't see them". It's also their path finding issues, plus the path finding of the P units (are a few zealots clumped together (= more damage taken, more zealots lost) or not). And of course there's the famous luck unit, the reaver. Its scarabs are ridiculously luck-based. And when attacking from some "unfavorable" angle he might not shoot at all but instead run into the target (should be a well-known situation vs. sunken colonies or cannons).
Reliance upon units or abilities which can be dodged This is especially true in ZvT for the Z. There are at least 2 occasions where this happens: 1. Using swarm offensively against a group of M&M, then running in with lings/lurks. The Z is actually relying on the fact that T has so much to do multitasking-wise that he won't be able to react just in time before the majority of M&Ms die inside the swarm. This works well for the Z, and if this weren't possible, ZvT would be even more imbalanced. 2. Using a small group of lurkers against a small group of M&M. If T could play perfectly, no lurker would ever hit a marine or medic because all lurker spines can be dodged. However, lurkers are the primary counter/defense against M&M (until ultras come into play later on). This means that with near-perfect play, Z would have no counter against M&M in midgame. Thankfully for the Z, that is not possible, so lurkers are still useful -- but a significant change in gameplay already happened. Lurkers were used much more offensively in mid-game just a few years ago. It was common back then to attack a T army in mid-game with a ling/lurk army. These days, lurkers are mainly used defensively (especially at choke points) where their attacks can't be dodged and thus they can be used effectively. We all know that with current skill levels, a Julyzerg style play from 2005 or so with ling/lurk in midgame can't be played anymore because Ts are able to dodge lurker spines, spread marines and just rape *any* amount of lurkers in midgame on slightly more open terrain. So there's almost no other choice than to rush to hive for defiler/ultra and just use those lurks defensively. Which is a bit sad because ZvT got even more streamlined. Sure there are possible timing attacks or situations where T is at such a disadvantage mid-game so lurk/ling can still work, but in general it doesn't and Z desperately needs to go hive quickly.
Mutas vs irradiate This one belongs to the category above, but deserves a category on its own because it's so ridiculously luck-based. Imagine the following situation: Z went for a lot of mutas, T gets his first vessel out with irradiate researched. T irradiates one muta from the stacked group. Now, two things might happen (provided that the Z is currently paying attention to the mutas) and it's completely luck-based what will happen: a) Z is able to find that muta fast and move it out of the group => Z doesn't lose a single muta and thus T is at a heavy disadvantage because their primary counter vs. mutas in midgame didn't work b) Z isn't able to find/select that muta fast and move it out of the group => Z loses a ton of mutas and is at a heavy disadvantage because the mutas got countered "perfectly" (by chance)
Constantly changing maps Maps always change, and thus it's impossible for players to memorize all possible timings for cheeses or attacks on every single map, so there will always be some timing attacks which work against your build, and you can't do a thing except learn from that timing attack after your loss and prevent it from happening the next time. Build orders also slightly change, and what was the best build order on map A might not be the best choice on map B, but if it's a new map you probably haven't played it enough to really try out all the different build orders and set up an accurate list of pros/cons.
And of course there are lots more examples. Usually, one or two situations like that where things simply don't work out well for you aren't really game-deciding, but small disadvantages here and there quickly add up to a big disadvantage.
Until those things (and more) are solved, SC will remain a game influenced by luck NOT JUST because of incomplete information or things like one player being in a bad shape, but also because of game mechanics which you can't change and which might work against you.
IMO ZvT would be impossible for the reasons listed above.
Marines would be able to rape mutas because mutas can only shoot foward and the marines in front of the mutas just need to run and the rines from other directions can shoot them down without getting hit. Stimmed rines are faster than mutas too.
Lurkers are useless for the said reasons
Wraiths would be able to kill anything and everything. They have longer range than hydras and longer range than mutas. Cloak isn't even needed with that kind of range. The only way to stop perfect wraiths would be to make a bunch of spore colonies and give map control to the T.
As for TvP, seige tanks would rape everything. Know how the smart ai for tanks in SCII make them totally destroy everything? Now they have 70 damage. And up to 85 damage. Each tank can manually target and destroy the Protoss ball easily.
Because of the physical aspect and real-time nature of Starcraft, asking if it can be solved is a little like asking if something like golf can be solved. While I guess it's in principle possible to solve golf and Starcraft, it won't produce a strategy a human will ever be able to execute. It might be more relevant to ask about solving Starcraft with some input restriction, such as an APM limit.
On June 21 2010 13:04 PanoRaMa wrote: For the most part, some formats of hold'em are solved, certain SNG structures for example. It's solved (and was solved quickly) because at its core it is a game fundamentally comprised of actions and decisions that can be measured quantitatively.
Just because you can have positive expectation by following 10 simple rules in low limit sngs or whatever you're getting at, doesn't mean the game is solved in a game theory sense.
I shall assume that most people know some basic game theory, and hence skip the definitions of terms.
Leaving aside technical issues of APM and micro/macro skills, as I think the OP intended, Starcraft is a game with both simultaneous and sequential moves. The sequential strategy of players may be simplified to be recognised as only the "macro" aspect of the mid to late game, ie. the choice of unit compositions, number of bases to take, choice of tech, etc. which you decide when you are able to effectively scout your opponent's macro strategy. This aspect of SC may be solvable using rollback, as it is possible to come up with strategies to counter your opponent's strats (eg. vults to harass -> goons to defend -> sieged tanks to hold map control -> arbiters to stasis tanks -> vessels to emp arbiters). Again I must emphasise that this is possible because we are ignoring the "skill" of the players and only focusing on the balance of units between Perfect Players. Hence, it is mathematically possible to calculate a rollback equilibrium for this aspect.
The simultaneous aspect of SC occurs when there is strategic uncertainty because of a lack of scouting. This is definitely applicable when choosing the build orders to start the game with (5pool or 12hatch?) when you are uncertain about what your opponent will play. Since SCBW has been played by progamers for 10 years now, and there is no "imba" unstoppable strategy that has been found, we can quite surely say that there is no dominance in any particular build order. It is obvious that there is also no Nash equilibrium for choosing build orders, if not we'll be seeing the same games over and over again. Thus the thing to look for would be a mixed strategy. I do think that a lot of progamers or coaches have already devised rather successful mixed strategies for early game BOs.
Responding to some of the above posts, I do not agree that the "luck/chance" factor is a deterrent to solving the game. We know that a ranged unit has a certain miss chance against a unit up a cliff; the percentage might not be available to the public, but Blizzard certainly knows it. As such, it is theoretically possible to come up with the expected value of attacks that may miss or be dodged. With this expectation, it is now possible to come up with a mixed strategy.
Pathseeking: this does not matter at all with perfect micro. The units should move in Perfect movements, accurate up to the pixel.
Psychological mindgames: This should affect nothing other than the physical skill of a player; in a Perfect situation this can be ignored. I can't remember the proof off the top of my head, but in a zero-sum game such player communications (direct or indirect) can be ignored when devising strategies.
Maps: This is obviously a null point when discussing the THEORETICAL possibility of solving Starcraft. The map changes the expected payout of each strategy, hence all that is required is to alter the mixed strategy or rollback to fit the new payouts of each map.
Like some posters have mentioned, the second game's solution does not work if a player places a coin near the centre of the table. Is there a way to avoid this, or is there a more elegant solution?
EDIT: I think there is a misconception that "solving" a game means that one race or one strategy will definitely Win the game 100% of the time. However, the idea in mixed strategies is that it maximises the chances of winning regardless of what the opponent does (his indifference in strategies). This assumes that the game is perfectly balanced and has no pure, dominant strategy, hence no strategy or race is superior. Perhaps that is what some people are thinking of or seeking.
For the second game theory puzzle, the first player will win. He should place the quarter at the exact centre of the table, then follow the strategy stated by spencer. This will allow the first mover to win rather than the second.
I feel smart for realising this ridiculously easy solution heh =p
Very good blog. I really think that if we solve any game, it'll get boring after time because of the simple fact that you can win if you play perfect. IMO, StarCraft is way far to me solved. Even the random race proves this
On June 22 2010 18:39 blueblimp wrote: Because of the physical aspect and real-time nature of Starcraft, asking if it can be solved is a little like asking if something like golf can be solved. While I guess it's in principle possible to solve golf and Starcraft, it won't produce a strategy a human will ever be able to execute. It might be more relevant to ask about solving Starcraft with some input restriction, such as an APM limit.
The question of whether or not a game can be solved becomes more and more ridiculous as a question as games focus more on execution skillsets than strategic skillsets.
The amount of strategy in golf is miniscule compared to chess or SC - it doesn't matter if you solve the game strategically unless you can drive for 500 yards and put accurately, consistently.
Its not a correct analogy, because SC's focus on execution skillsets is much less.
EPT![[image loading]](http://dl.dropbox.com/u/4785014/solvingstarcraft/tictactoe.jpg)
![[image loading]](http://dl.dropbox.com/u/4785014/solvingstarcraft/connectfour.jpg)
![[image loading]](http://dl.dropbox.com/u/4785014/solvingstarcraft/checkers.jpg)
![[image loading]](http://dl.dropbox.com/u/4785014/solvingstarcraft/rockpaperscissors.jpg)
![[image loading]](http://dl.dropbox.com/u/4785014/solvingstarcraft/chess.jpg)
![[image loading]](http://dl.dropbox.com/u/4785014/solvingstarcraft/starcraft.jpg)
