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