|
5003 Posts
A year or two ago, the "Starcraft Professor", Alan Feng, visited the University of Chicago and gave a little lecture. He talked about the importance of randomizing build orders as a competitive players (essentially, reaching mixed nash equilibrium).
I was late for the earlier lecture, so I talked to him and tried to see what he talked about and what happened was that he actually just gave me his notes. I haven't done anything with them (after reading them of course) since then but I did have it scanned for the longest time.
I can give a much more formal explanation of the concepts he talked about if needed, I think (and probably mix in a little bit of how I understood it cause I think it's really interesting), but for everyone else interested, here are his notes. Warning though, it's extremely wonkish, and if there's demand for it I'll try and explain the ideas better (and even run some statistical tests determining these things -- I should have the means of doing that soon ^_^)
Enjoy, and let me know if you guys want to go a bit more indepth 
 
|
wow.. looks complicated, lol
|
Great stuff! I'm only on page 3 but so far I fully agree with what I can read :p. Please explain the formulas a bit for us!
edit: Just realized, which star craft is this for? :p
edit2: finished reading, I liked it a lot but I want better description of the diagrams 
|
Optimizing your build order choice is actually very similar to balancing your range properly in poker: people might want to check that out to. It's a pretty simple concept for poker players to carry over to sc2.
|
Edit: Reading through a bit of the OP's links, it really IS the same thing as properly balancing a range in poker. Same reasoning, basically a giant probability, anticipatory and equity question.
|
You can do this with player selection in team leagues too.
Say hite prepares Hydra and Snow for the ace match map and WeMade prepared Baby and Roro.
And let's say:
Baby beats Hydra 55% of the time.
Hydra beats Roro 58.8% of the time.
Roro beats Snow 60.6% of the time.
Snow beats Baby 64.5% of the time.
In a mixed strategy Nash equilibrium, the optimal strategy is to make your opponent indifferent, that is, to make him have the same utility no matter what option he picks.
So WeMade's ideal strategy is:
hite utility of sending Hydra = hite utility of sending Snow
%chance Hydra beats Baby * %chance Baby is sent out + %chance Hydra beats Roro * %chance Roro is sent out = %chance Snow beats Baby * %chance Baby is sent out + %chance Snow beats Roro * %chance Roro is sent out.
So, .45*x + .588*(1-x) = .645*x + .394*(1-x) where x is the chance Baby is sent out, and (1-x) is the chance Roro is sent out.
Solving the equation gives the Nash equilibrium as sending Baby 49.9% of the time, and Roro 50.1% of the time. You can do a similar calculation for hite to get that they send Hydra 51.3% of the time and Snow the other 48.7%.
|
It'd be great if the OP could simplify this as much as possible in how it relates to Starcraft 2 because this really does look like a lot of thought and work wras put into it, but its really hard to communicate higher end mathematics to a large audiecne of people. Could anybody give us a hand and simplify somewhat whats being said and stated in these equations?
|
I agree with fodder, I'm a math newb. Is he just saying you should randomize your play for optimum efficiency with a math to back it up?
|
I think what he's saying is make your build efficient by definition of the Nash Equilibrium. Which means your build should be equally good agianst any and all possible builds your opponent can do and that adapting is not necessary because it's already good equally against everything. And the math actually backs up which builds are equally good statistically against all builds without having to change your build at all or adapt. I don't know, its still really foggy for me. Did some reading on it but I'm not fully positive at all. It's really confusing.
|
This is game theory, basically describes the behaviour of 2 players when both have uncertainty of the other's decision, a nice example to start with is the prisoners dilemma
it is simple to understand and you can make the analogy with build orders...
|
TheBlueMeaner:
This is game theory, basically describes the behaviour of 2 players when both have uncertainty of the other's decision, a nice example to start with is the prisoners dilemma
it is simple to understand and you can make the analogy with build orders...
Yeah prior to this I've heard of that example before and I just re-watched a video on it and very basic game theory. But that doesn't exactly help me figure out how to apply this directly into a useful and meanignful way to Starcraft 2. I mean if someone coudl give an actual example of a build order or even somewhat describe how this could be applied that would be amazing because this looks awesome! 
|
Damn it, I was soooo gonna do a game theoretical analysis of Starcraft for my 1337th post. Guess I (sorta) got beat to it.
|
Entropic:
Damn it, I was soooo gonna do a game theoretical analysis of Starcraft for my 1337th post. Guess I (sorta) got beat to it
So do you understand game theory enough to help explain it to us to help us out? I'd really love to know how it's applied to Starcraft 2 and what can be learned from it. I'm guessing you do, since you've indirectly named yourself after an entropy which is involevd in higher branches in math, but maybe thats just a coincidence.
I really do hope someone can simplify this though for us all to understand, this does look like it has a lot of potential to be helpful.
|
On March 23 2011 18:02 FODDER~ wrote:Show nested quote +
Entropic:
Damn it, I was soooo gonna do a game theoretical analysis of Starcraft for my 1337th post. Guess I (sorta) got beat to it
So do you understand game theory enough to help explain it to us to help us out? I'd really love to know how it's applied to Starcraft 2 and what can be learned from it. I'm guessing you do, since you've indirectly named yourself after an entropy which is involevd in higher branches in math, but maybe thats just a coincidence. I really do hope someone can simplify this though for us all to understand, this does look like it has a lot of potential to be helpful.
I would say it doesn't really reveal any new insights that isn't already common rts wisdom. It's just fun to sort of formalize those ideas and starcraft strategy in general.
I think Milkis could explain it better than I can.
The main important point to take away from it is:
1) randomize between build orders (ie. essentially, dont do the same strategy every game, or, less extreme, there is an optimal proportion that you should use a certain build order. ie. if you have build orders A, B, C, there is an optimal x, y, z % time you should do each respectively, game to game)
I feel like the notes coulda gone a bit further but I can't say exactly what atm (so sleepy T_T).
|
Looks complicated haha, thanks for sharing Kelly.
|
On March 23 2011 20:12 Kamais_Ookin wrote:
Looks complicated haha, thanks for sharing Kelly.
Lol Milkis isn't kelly, kellymilkies is kelly.
|
On March 23 2011 20:23 AcrossFiveJulys wrote:Show nested quote +On March 23 2011 20:12 Kamais_Ookin wrote:
Looks complicated haha, thanks for sharing Kelly. Lol Milkis isn't kelly, kellymilkies is kelly.
+ Show Spoiler +I know! 
|
Germany2896 Posts
On March 23 2011 17:36 TheBlueMeaner wrote:This is game theory, basically describes the behaviour of 2 players when both have uncertainty of the other's decision, a nice example to start with is the prisoners dilemmait is simple to understand and you can make the analogy with build orders...
SC is a zero sum game, prisoner's dilemma isn't. So they have very different properties.
For a zero sum game you can simply solve it for pure strategies and then calculate the optimal mixed strategy(May be a bit expensive to do, but mathematically simple).
Prisoner's dilemma(especially when iterated) is more about psychology and how to achieve cooperation. Of course you can calculate the nash equilibrium, but the problem doesn't feel solved with just that.
|
Germany2896 Posts
On March 23 2011 17:49 FODDER~ wrote:But that doesn't exactly help me figure out how to apply this directly into a useful and meanignful way to Starcraft 2. I mean if someone coudl give an actual example of a build order or even somewhat describe how this could be applied that would be amazing because this looks awesome!
One thing you can conclude from game theory is that cheesing from time to time helps you even in games where you play more standard because it forces your opponent to be not overly greedy.
|
Thanks for the explanation MoC! This is great stuff . I'm gonna start linking anyone with the repetitious build to this and then help them with understanding it now . Props to Milkis for posting this great information!
|
Interesting, although to be honest its a very low level of game theory analysis. All the information there would be covered within the first month or two of an introduction to game theory class.
|
|
|
|
|
|
EPT
