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.
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)
