|
WARNING! WALL OF TEXT TO FOLLOW.
I would like to present a concept from game theory and discuss how it might apply to strategy in Starcraft 2. The concept I would like to discuss is called backward induction. There is a similar concept for chess players but they call it retrograde analysis. The concept is simple. To find a winning strategy in a sequential game, i.e. a game where you take turns, one starts with the last decision made at the end of the game and determines what the best decision or best state is at the end of the game. Armed with this knowledge, the player then looks at second to last decision and makes the decision there that puts him in the optimal state for the next decision and does the same for the third to last decision and so on until he reaches the first decision of the game.
Let me give an example. Imagine a game where two players take turns choosing numbers between 1 and 10. When they choose a number it is added to a running sum of all the numbers chosen. The player who chooses a number to make the sum 50 or greater loses the game. One play through could be.
Turn 1: Player 1 chooses 5 Sum: 5
T2: P2 c 6 Sum: 11
T3: P1 c 8 Sum: 19
T4: P2 c 8 Sum: 27
T5: P1 c 4 Sum: 31
T6: P2 c 7 Sum: 38
T7: P1 c 1 Sum: 39
T8: P2 c 10 Sum: 49
Whatever P1 chooses in turn 9 he loses the game because any number makes the sum 50 or greater. However P1 did not lose the game in turn 9. He lost it earlier. When you ask the average person who has no exposure to this kind of stuff when did P1 lose the game, they usually answer in turn 5 or 7. Lets do the backward induction analysis in order to find out.
We see that when a player starts his turn with the sum at 49 he will lose the game. Therefore my objective should be to not let the other player have the option to get the sum to 49 on his last turn. So, I want him to have 38 on his second to last turn because no matter what he does he cannot leave me with 49 on the next turn. Subsequently, I want him to have 27 on his third to last turn because then he can't get the sum to 38. Now just continue this logic and we see that on the turn before that we want him to have 16 and before that we want him to have 5.
We can see that P1 made the correct decision in turn 1 but he made a mistake on turn 3 and P2 capitalized on the mistake. So, P1 lost the game on turn 3, but if he had played optimally he should not lose. P2 has lost the game before he makes his first move barring any mistakes from P1 . The winning strategy for P1 is to choose 5 on the first turn and then choose 11-n on every subsequent turn where n is the number that P2 chooses on the previous turn.
This game has a first mover advantage. In sequential deterministic (non-random) games the backward induction solution is such that there is a first mover advantage, a second mover advantage, or the game ends in a draw. Tic-tac-toe is an example of a game where if both players play correctly the game ends in a draw. A solution to checkers has been found that guarantees a draw for one of the players. Chess fits into one of these 3 classifications but the number of possible moves is so large, computers are not fast enough to calculate a solution in a feasible time scale.
One may ask, how does this apply to Starcraft 2? Starcraft is an RTS. It is not sequential and more complex. Granted, Starcraft is more complex than the games discussed previously. There is imperfect information, micro, macro, and so on. Chess is already complex enough to make a calculable solution infeasible. But, I am skeptical that Starcraft is truly "real time". I believe that "real time" in the game is an illusion. I think it is actually sequential. I am not an expert on computer science and computer engineering so I admit it is possible for me to be corrected on this point. I imagine that the code for the game is largely executed in sequence and not in parallel. Therefore, in principle a solution may exist for all the match-ups that classifies into a first mover advantage, second mover advantage, or a draw game.
If you start with this knowledge then when seeking to play at a high level you can ask questions like, when I forge fast expand am I giving up the advantage to a zerg. Is it the equivalent of choosing 1 instead of 5 in the number picking example. A similar question can be asked for going hatch first in ZvZ. Or does 2-Rax bunker rush on Metalopolis close air positions give me a first mover advantage against Zerg. The equivalent of choosing 5. Should there be more strategic importance placed on the opening than our intuition initially tells us? Just as it is not initially intuitively apparent to the average person that the opening decision is crucial in the number picking game.
As the title said, food for thought.
Edit for clarification. The point here is to use a concept from formal game theory to develop better intuition about decision making in Starcraft. This is not an argument that execution is irrelevant or that the solution for Starcraft will be found. It has been pointed out that a calculable solution for chess is not feasible because it is impossible to enumerate all the possible branches of decisions in a reasonable time scale. From what I understand though is that chess grandmasters do know most of the most common branches in detail and when they make decisions they use what they call retrograde analysis which is analogous to backward induction. They look ahead as far as they can and work backward to determine the best possible move now. In the same way the number picking game was analyzed. Just because they cannot see all the way to the end of the game it does not mean that exercising the backward induction skill is pointless. When a computer is programmed to play chess that is all it does. Enumerate all the possibilities as far forward as it can and make the best decision now based on that. The computer is unable to see all the way to the end in chess as well but since Big Blue (the IBM computer that was programmed to play chess) could see further ahead than its human competitor it was able to win.
Thinking in this way can help we who are trying to get better to determine how to open and when to make timing attacks to avoid certain states of the game where we know we lose and force other states where we know we win. I believe that most people do not work backward but forward and thinking about this concept can improve our play. As an example I have seen some PvZ games where my intuition tells me the Zerg player attacks too late after the Protoss forge fast expands. There exists a tipping point where the Protoss becomes too strong and there is little a Zerg can do after that. I think there are people who cry imbalance when something like this happens because they take 5 bases against the Protoss' three and they still lose. There is no rule anywhere that says 5 base Zerg is supposed to beat 3 base Protoss. It doesn't mean anything that 5>3. Perhaps the Zerg missed his opportunity earlier. It is possible they let the game get into a state where they couldn't win and that passive mass expansion was the wrong response. Earlier action may have been necessary (e.g. a timing attack) to force the game into a different state and perhaps that timing could come as early as when the Zerg is on one base. I'm not saying that is the case but it may be something that initially seems very unintuitive. Because the solution may be unintuitive people throw around the term all-in too loosely where I think some early attacks may be classified as forcing a certain state and not an all-in. The finals of MLG Providence Leenock vs Naniwa is a recent example. Leenock kept making early attacks against Naniwa and there were some who called it all-in. Perhaps he was forcing the game into a certain state. Relating back to the number picking game perhaps his choice was analogous to choosing 5 at the start.
|
Maybe, but in Starcraft, you can make your opponent's 5 a 4.
|
But, I am skeptical that Starcraft is truly "real time". I believe that "real time" in the game is an illusion. I think it is actually sequential. I am not an expert on computer science and computer engineering so I admit it is possible for me to be corrected on this point. I imagine that the code for the game is largely executed in sequence and not in parallel. Therefore, in principle a solution may exist for all the match-ups that classifies into a first mover advantage, second mover advantage, or a draw game .
Your premise is entirely incorrect. Whether or not StarCraft is simultaneous or sequential - at the code level - is irrelevant. It's simultaneous at the player level.
When chess has not even been solved, I doubt there's much value in a lay analysis on 'solving' StarCraft in the way you imagine.
|
Starcraft involves imperfect information so at best a Nash Equilibrium would be found, constisting of randomly picking amoung builds based on certain weights. ie. 50% of the time I'm going to 15 hatch in zvz, 40% i'm going to 14-14 and 10% I'm going to 10 pool.
But, I am skeptical that Starcraft is truly "real time". I believe that "real time" in the game is an illusion. I think it is actually sequential.
It is a largely discrete game, in that the number of "optimal builds" is very small. However, the possibility of using "non-optimal" builds to throw one's opponent off as they assume you are doing something different is quite strong, meaning that there could still be a continuous range of viable strategies.
In Starcraft 2 since there is imperfect infromation in most situations someone who is behind has a lesser chance of winning but can still win. A powerful example is that as the late-game gets figured out more and more these probabilities change and the definition of "ahead" changes accordingly.
Because of the above, since Starcraft II is still a continuous game I feel, and a Nash Equilibrium may not even exist because of this.
http://en.wikipedia.org/wiki/Continuous_game
|
It is real time. Here, 'real time' refers to not turn based. As in, players are free to move and do things at whatever rate they can. And, as automaton 2000 has shown us, the ceiling for micro is essentially unattainable by humans. Therefore, player skill and speed will always play a role far too important to have any of this make sense beyond interesting theorycrafting. You may devise 'first turn advantages' by deciding what builds and transitions counter what builds and transitions, but it will never be reliable.
|
Very interesting read, but not applicable in general. In SC2 there are first turn advantages but they're not guaranteed, and also you don't get to see what number your opponent picked so most of the time you are guessing at him picking the number most advantageous to him when you could be wrong.
|
@khanofmongols
I agree with a lot of your points especially that a solution may only be in mixed strategies and that the game is largely discrete. However, I find it hard to believe that there exists a continuous range of strategies in Starcraft. Which makes me feel the existence of a Nash Equilibrium is more likely.
|
That's trivial, you know. That's just a fixed point theorem.
|
Yea, beyond imperfect information, we have imperfect execution. Even if there is an optimal decision that equates to a first mover advantage, I don't think we can assume perfect execution of that decision. Furthermore, given the way decisions are made without full knowledge of the opponent, I would argue that both players decisions mutually and, in many cases, simultaneously determine (open up or close off) future decisions.
tl;dr Execution of even the most perfect decision will rarely be perfect. And the most perfect decision in a game will be consistently reshaped by the interaction of both players decisions up to that point.
|
One may ask, how does this apply to Starcraft 2? Starcraft is an RTS. It is not sequential and more complex. Granted, Starcraft is more complex than the games discussed previously. There is imperfect information, micro, macro, and so on. Chess is already complex enough to make a calculable solution infeasible. But, I am skeptical that Starcraft is truly "real time". I believe that "real time" in the game is an illusion. I think it is actually sequential. I am not an expert on computer science and computer engineering so I admit it is possible for me to be corrected on this point. I imagine that the code for the game is largely executed in sequence and not in parallel. Therefore, in principle a solution may exist for all the match-ups that classifies into a first mover advantage, second mover advantage, or a draw game.
Supposing you did break the game down to discrete turns on a sufficiently short timescale, I don't think it would be a useful approach. Clearly there would be many more turns and many more available "moves" on any given turn that in Chess, which is already intractable. I think if there is to be value in this type of approach, you need to use some sort of lower resolution chunking. For example, rather than describing every single action, break it down into "Player expands" or "Player techs to DTs". Similar to SC2 manager if you've played that.
|
Cool read but I would like to see some better examples of how it relates to SC2 directly in the OP. Otherwise you're kinda just posting what you know about a game theory topic and saying "...and it might relate to SC2. Have at it, guys!"
|
Cool read but I would like to see some better examples of how it relates to SC2 directly in the OP. Otherwise you're kinda just posting what you know about a game theory topic and saying "...and it might relate to SC2. Have at it, guys!"
@yeastiality
Does the edit do that for you?
|
Chess which has only one available move per turn is still (arguably) unsolved.
Starcraft has upwards of thousands of individual "moves" you can do per second, and a 'perfect' game isn't stable due to imperfect vision.
The only place where this could apply is a single confrontation. Like for instance, tank+ marine force in the middle of the map, against you, the zerg, with muta ling. There's nearly infinite ways to engage the force (even ignoring choices like sending one unit at a time). Even something like that would take an insane amount of time for an optimal solution, and even then you'd come up with an automaton 2000 type solution: impossible for humans.
The entire point of starcraft is that you can't do everything perfectly, and you must choose what to do when given limited data and take chances.
|
I think when we see gas steals and blocking of expansions it is this concept in action. The player thinks ahead and says 2-port banshee or Zerg getting their expansion too early puts the game in a certain state where I most likely lose therefore I am going to take this action to prevent that future state. I gave the best examples that stand out the most to me. I don't have all the answers otherwise I would be in code s. Hopefully this concept rings true with you when you are playing the game now that you are aware of it.
|
I really like this topic.
Even though players continually make mistakes, there should still be an optimal strategy for every move, just as the OP says (in my opinion). The only difference is that tactical decisions can alter the outcome of the game, but we should not consider this too much when we plan out strategies.
For example, I currently believe than when I play PvT on Shakuras I should always be planning for a 2 gate expand into 2 base 3 gate robo. The reason is there is nothing that my opponent can do to punish this opening, that I cant scout. If I plan to 2 gate expand and my opponent does X counter, it is scoutable and I can adapt into any defense from my 2 gate opening.
Now, compare that to a 1 gate expand on shakuras. If my opponent does a 3 rax marine/scv all in then he has taken the advantage. Even if I scout it I cannot save my nexus. By doing a 1 gate expand I have given my opponent a chance to counter me.
Another example would be that I think a terran should always 2 rax expand vs me on close air metalopolis. There is no way I can gain a strategic advantage of this without him being able to adapt to it. Where as, if the terran opens banshee and I do a 1 gate zealot 3 stalker expand into robo, the terrans strategy has been counted and he has already started his fast starport before he knows what I am doing.
|
While game theory could be useful in SC2, backwards induction is the wrong way to go about it since, as people have said, optimal play is so hard to determine.
However, we could generally determine that certain strategies do better than other if we assume the players' execution has roughly the same competence. For instance, a 1-gate expand does well against something like a siege-tank expand, while faring poorly against 2-rax pressure.
The most obvious game theory lesson to take, especially in the context of a BoX series, is that you have to vary your strategies to make sure that your opponent cannot take advantage of them...
+ Show Spoiler +
|
While game theory could be useful in SC2, backwards induction is the wrong way to go about it since, as people have said, optimal play is so hard to determine.
Again, optimal play in chess is undetermined as well. But we know that it exists. I argued that it exists in Starcraft as well. You are free to disagree with that. Someone argued earlier that a solution could be in mixed strategies and I agreed with them. That supports your last point about mixing your play. In chess this type of thinking is still useful even though the solution is unknown. Strategy is strategy.
@hzflank
All your examples are exactly the type of thing I am talking about.
|
interesting thoughts. you need a simplified mathematical modell of sc2 in order to do calculations. the number choosing game does not hit it (i get it was'nt meant to do that). i have developed such a mathematical model (i am not sure tl members would enjoy this stuff .. its not that simple). Anyway the main conclusion after some calculus were:
1) information advantage is extremely important (its not about scouting only, but also denying it)
2) having too much production (too much hatches, barracks etc.) can make up for information disadvantage (quicker army on demand)
3) mobility is a deciding factor as it shortens reaction time. see speed upgrades/drop/nydus/warp-in
4) return-on-investment is a key concept
5) alternatively you will reach pretty high winrates by more or less blindly peerforming timing pushes/all ins based on metagame trends
(well not that new stuff overall =)) )
|
On December 05 2011 08:29 hzflank wrote:
I really like this topic.
Even though players continually make mistakes, there should still be an optimal strategy for every move, just as the OP says (in my opinion). The only difference is that tactical decisions can alter the outcome of the game, but we should not consider this too much when we plan out strategies.
For example, I currently believe than when I play PvT on Shakuras I should always be planning for a 2 gate expand into 2 base 3 gate robo. The reason is there is nothing that my opponent can do to punish this opening, that I cant scout. If I plan to 2 gate expand and my opponent does X counter, it is scoutable and I can adapt into any defense from my 2 gate opening.
Now, compare that to a 1 gate expand on shakuras. If my opponent does a 3 rax marine/scv all in then he has taken the advantage. Even if I scout it I cannot save my nexus. By doing a 1 gate expand I have given my opponent a chance to counter me.
Another example would be that I think a terran should always 2 rax expand vs me on close air metalopolis. There is no way I can gain a strategic advantage of this without him being able to adapt to it. Where as, if the terran opens banshee and I do a 1 gate zealot 3 stalker expand into robo, the terrans strategy has been counted and he has already started his fast starport before he knows what I am doing.
great idea: judging a build by the scoutability of counters. you get an information advantage doing so ..
|
I find that SC2 is 'who the ball is on'.
Example: PvZ.
1) I open 15 nexus (blind). Therefore the ball is on me to defend, similarly, the ball is on him to decide what to do to punish me. If I manage to hold off until a certain point, then I can do a timing push barring any mistakes.
2) Zerg opens 3 hatch before pool. Ball is now on me to punish him. If I let him get away with 3 bases running, I'm gonna lose the macro war.
3) Zerg sees forge spinning, you better get your carapace +1 started or your lings are gonna melt!
|
|
|
|
|
|
EPT
