|
What are the probabilities of each opening build beating each other build? If this question can be answered then you can calculate with which percentage you should choose each build. This method can be used for any match up, any game or anything where opponents choose something blindly and the result of those choices can be calculated (does not have to be mirror match either). This is not exactly useful for playing random people on iccup, because there you can do the same thing every time, and your opponent will have no idea that you do this. This is more important for people trying to play unpredictably in repeat matches. Although the results here should still be useful for iccup users because certain builds should never be used and this will identify them.
I chose zerg versus zerg because they have the widest range of viable openings. I'm not a zerg player so figuring out these percentages is difficult. I would really appreciate if a top level zerg can give their own estimation of the probabilities. But for now I'll give my own estimations. Thanks goes out to saarto for helping me test some stuff like 6 pool versus 12 pool.
(for python, assuming both players pro level)
(PS anyone know how to post stuff using monospace font?)
Given these percentages, the optimal choice of strategy is 26.6% of the time choosing overpool, 66.6% 12 pool, 6.6% 12 hatch, and 0% for all others. Obviously this does not apply when players at 12/3 and 6/9 as you can see what each other are doing.
Note, I did not include builds such as extractor before pool, 9 hatch and stuff. If anyone feels those builds are viable, please estimate the probabilities v each build and I will include it in the chart and update calculations.
I was surprised by the result that you should never 4-9 pool, the reason for this is because the overpool strat still has good rushing potential and isn't so screwed against 12 pool. I doubt that more accurate values will bring back the 4-8 pool, so please put most emphasis on estimating 9 pool - 12 hatch @ natural please.
One non obvious implication of this method is that no player ever has more or less number of viable options than their opponent (even in non mirror matches). It is hard to explain why, but if you think about it should be clear. I can explain more if needed.
Edit: another non obvious implication is that in mirror matches, there is never an even number of viable builds.
|
United States24682 Posts
Why don't you retype your chart using other software and then paste in an image of it... I'm having trouble reading it.
Edit: I'll think about it more mathematically at that point because it's an interesting idea.
|
System font is what you're looking for.
|
Updated chart, thanks for the idea micronesia. 5hitcombo, is there way to do that in post directly?
|
It makes sense from a macro stand point. I think it would help your different bo's tremendously. Thanks for writing it out like that. More intricate tables would be awesome for other races and mid game strats, but the probabilities are endless...
|
Its funny because the most powerful build in ZvZ might be 9 pool speed, which according to your mathcraft should be never done.
Starcraft > Mathcraft
|
Belgium9947 Posts
hmm I dont know what to make of this.
If you do your suggestion vs a player that always 12hatches, you'll be behind in 73% of the cases, and be able to do small damage in 26.6% of the cases. If you do it vs someone that always 12pools, you'll be behind in 26.6% of the cases, even in 66.6% of the cases, and ahead in 6.6% of the cases.
Why is this a bad statistical analysis? The 4pool, 5pool, 6pool etc weigh in as much as 9pool 12 pool and 12hatch, eventhough they're barely used. So your statistics will prefer safe builds, while in the end (ofcourse incorporating the map layout and distances, which will prefer certain build), it will remain more or less RPS.
|
Calgary25980 Posts
On March 21 2008 03:59 FieryBalrog wrote:
Its funny because the most powerful build in ZvZ might be 9 pool speed, which according to your mathcraft should be never done.
Starcraft > Mathcraft
My thoughts exactly. In theory you should be able to apply percentages to the builds and solve for an optimal build. I'm not sure where you got your percentages from, but something is wrong. For example, how does 4 Pool beat 5 Pool 10% of the time?
|
Calgary25980 Posts
On March 21 2008 04:02 RaGe wrote:
hmm I dont know what to make of this.
If you do your suggestion vs a player that always 12hatches, you'll be behind in 73% of the cases, and be able to do small damage in 26.6% of the cases. If you do it vs someone that always 12pools, you'll be behind in 26.6% of the cases, even in 66.6% of the cases, and ahead in 6.6% of the cases.
Why is this a bad statistical analysis? The 4pool, 5pool, 6pool etc weigh in as much as 9pool 12 pool and 12hatch, eventhough they're barely used. So your statistics will prefer safe builds, while in the end (ofcourse incorporating the map layout and distances, which will prefer certain build), it will remain more or less RPS.
Very true, it needs to be iterative, right? You need to attach a "probably of opponent doing build" matrix as well.
So in case 2, the chance of every build is 1/n.
Case 2, the chance is equal to the probability of winning from Case 1.
Run it to infinity and see what comes out.
|
On March 21 2008 03:59 FieryBalrog wrote:
Its funny because the most powerful build in ZvZ might be 9 pool speed, which according to your mathcraft should be never done.
Starcraft > Mathcraft
"Given these percentages, the optimal choice of strategy is..." I never claim to be a zerg expert. If 9 pool speed is the most powerful, or even viable, its because I have underestimated its chances against other builds, or overestimated other builds that fulfill the same niche. I really want help from more knowledgeable zergs with this estimation, if you have any suggestions please make them. I think the most likely cause of error right now is bad estimation of overpool versus 12 hatch, I haven't tested that match up yet and it has a large impact on the results, is 70% too high an estimation for the overpool there?
|
On March 21 2008 04:02 RaGe wrote:
hmm I dont know what to make of this.
If you do your suggestion vs a player that always 12hatches, you'll be behind in 73% of the cases, and be able to do small damage in 26.6% of the cases. If you do it vs someone that always 12pools, you'll be behind in 26.6% of the cases, even in 66.6% of the cases, and ahead in 6.6% of the cases.
Why is this a bad statistical analysis? The 4pool, 5pool, 6pool etc weigh in as much as 9pool 12 pool and 12hatch, eventhough they're barely used. So your statistics will prefer safe builds, while in the end (ofcourse incorporating the map layout and distances, which will prefer certain build), it will remain more or less RPS.
If you know what they are doing already, don't use this method, choose the counter instead. But if they always do 12 hatch and you use this method, on average you will have a 50% chance of beating them. Because even though you are behind 73% of the time its not nearly as far behind as you are ahead when you do the overpool.
This is not bad statistical analysis, the 4pool, 5pool, etc do not weigh in as much as the 9pool 12 pool and 12 hatch. Infact they do not way in at all since they are inferior. The method I used to calculate the result, assumes that they are also choosing builds based on their goodness. It is standard game theory stuff. I can post the program used to calculate the results after I clean it up some.
On March 21 2008 04:04 Chill wrote:Show nested quote +On March 21 2008 04:02 RaGe wrote:
hmm I dont know what to make of this.
If you do your suggestion vs a player that always 12hatches, you'll be behind in 73% of the cases, and be able to do small damage in 26.6% of the cases. If you do it vs someone that always 12pools, you'll be behind in 26.6% of the cases, even in 66.6% of the cases, and ahead in 6.6% of the cases.
Why is this a bad statistical analysis? The 4pool, 5pool, 6pool etc weigh in as much as 9pool 12 pool and 12hatch, eventhough they're barely used. So your statistics will prefer safe builds, while in the end (ofcourse incorporating the map layout and distances, which will prefer certain build), it will remain more or less RPS. Very true, it needs to be iterative, right? You need to attach a "probably of opponent doing build" matrix as well. So in case 2, the chance of every build is 1/n. Case 2, the chance is equal to the probability of winning from Case 1. Run it to infinity and see what comes out.
I already do this...
|
Calgary25980 Posts
Oh, okay. You didn't mention in your post weighting anything based on chance they use it.
Edit: I must not be reading this properly, I don't see how you can come to the conclusion that you should do different builds. I'll have to reread it later. :X
|
On March 21 2008 04:02 Chill wrote:
how does 4 Pool beat 5 Pool 10% of the time?
Well this is an estimation, the 4 pool is behind by about 2 drones, but random stuff can happen on the way to their base since you are heading into the dark some of the time since you can't have scouted everywhere yet. I think this number is reasonable, but please instead of saying hey that's a bad estimation, just give a better one and I'll update. I didn't explain all my estimations because I expect a better zerg to come through and give better estimations making all mine irrelevant anyways. Also note since it turned out neither of these builds are used, it doesn't actually effect the results in any way what the chance of 4 pool beating 5 pool is.
|
Calgary25980 Posts
On March 21 2008 04:20 flag wrote:Show nested quote +On March 21 2008 04:02 Chill wrote:
how does 4 Pool beat 5 Pool 10% of the time? Well this is an estimation, the 4 pool is behind by about 2 drones, but random stuff can happen on the way to their base since you are heading into the dark some of the time since you can't have scouted everywhere yet. I think this number is reasonable, but please instead of saying hey that's a bad estimation, just give a better one and I'll update. I didn't explain all my estimations because I expect a better zerg to come through and give better estimations making all mine irrelevant anyways. Also note since it turned out neither of these builds are used, it doesn't actually effect the results in any way what the chance of 4 pool beating 5 pool is.
I mean, what kind of variability do you want? If I 7 Pool against a 5 Pool, there's a small chance I move out with my Zerglings and he comes in at the same time and kills my Spawning Pool / Drones. Are we giving credit to things like that? If neither playing makes a mistake, 4 Pool loses to 5 Pool every time. Do you want to apply a random "chance of mistake" factor?
|
On March 21 2008 04:19 Chill wrote:
Oh, okay. You didn't mention in your post weighting anything based on chance they use it.
Edit: I must not be reading this properly, I don't see how you can come to the conclusion that you should do different builds. I'll have to reread it later. :X
Ah yeah I should have mentioned the method used instead of assuming people would trust me. Basically it assumes the opponent knows what percentage you choose each strat, and you know what percentage they choose each. Your chance of winning is the sum of each strat's chance of winning times the probability of the two of you choosing the respective strategies. This method will give you optimal choice of strategies, but will not exploit inferior players tendencies. Although if you know their tendencies, you can choose a strategy that is optimal for defeating just them, and it might even be a strategy that my method says not to use at all. However if they know you will do this... (and so it repeats).
Sorry for the multiple post, hard to keep up with all the things being said in one post.
|
On March 21 2008 04:23 Chill wrote:Show nested quote +On March 21 2008 04:20 flag wrote:On March 21 2008 04:02 Chill wrote:
how does 4 Pool beat 5 Pool 10% of the time? Well this is an estimation, the 4 pool is behind by about 2 drones, but random stuff can happen on the way to their base since you are heading into the dark some of the time since you can't have scouted everywhere yet. I think this number is reasonable, but please instead of saying hey that's a bad estimation, just give a better one and I'll update. I didn't explain all my estimations because I expect a better zerg to come through and give better estimations making all mine irrelevant anyways. Also note since it turned out neither of these builds are used, it doesn't actually effect the results in any way what the chance of 4 pool beating 5 pool is. I mean, what kind of variability do you want? If I 7 Pool against a 5 Pool, there's a small chance I move out with my Zerglings and he comes in at the same time and kills my Spawning Pool / Drones. Are we giving credit to things like that? If neither playing makes a mistake, 4 Pool loses to 5 Pool every time. Do you want to apply a random "chance of mistake" factor?
It is hard to measure chance of an inferior build beating a superior one. The main important factor to keep things accurate, is that we are consistent. To ensure consistency, assume that the players are "pro level" and make about the same amount of mistakes as pro. I know this isn't an exact science, but luckily these crazy things like 5 pool versus 7, don't effect the results much. What effect the results more are stuff like 9 pool versus 12 pool. This is alot more common and good zergs probably know what their chances of winning in that situation are. In looking at previous ZvZ topics, people mentioned at least 2 instances where a pro using 9 pool beat one using 12.
And in that example you described I think the 7 pool build didn't make any "mistakes" they just got unlucky, so it would be good to say the 5 pool has at least a chance v 7 pool. (same true probably for 4 pool versus 5).
Also one other thing I never mentioned is, if positions are 12/3 or 6/9 then 4/5 pool builds are screwed, but a 6 pool build that builds 8 drones and cancels last 2 if they don't see an overlord coming can adapt with no penalty. So really the 4/5 pool builds need to multiply chance of win v overpool by 1/3 and chance of win v build in question by 2/3 to get real value and add them together. (I did this already in computation but didn't list in chart for simplicity purposes)
|
|
|
How many people overpool?
|
Guys, how often are zvz games at the pro level decided off of the build?
It's honestly more about adaptation. Every zvz is different.
|
no one really cares about the zvz match up its basically you overpool or 9 pool or your pretty much dead after taht its just your choice of agression fest lings, muta, sourge, devoirers. When i play zvz i think very little of my build after the 9 pool i just do what come naturally which is fast lair to zerg air when i play
|
On March 21 2008 10:32 IzzyCraft wrote:
no one really cares about the zvz match up its basically you overpool or 9 pool or your pretty much dead after taht its just your choice of agression fest lings, muta, sourge, devoirers. When i play zvz i think very little of my build after the 9 pool i just do what come naturally which is fast lair to zerg air when i play
Just because you only use two builds doesn't mean that only two builds work.
|
On March 21 2008 09:19 5HITCOMBO wrote:
Guys, how often are zvz games at the pro level decided off of the build?
It's honestly more about adaptation. Every zvz is different.
Prob half end mere minutes after the openings have been chosen.
I dont know if I think adaptation is a great description. More like tactical exploitation. Given a game is on even or semi-even footing build-wise whomever can "read" their opponent better in a fairly arbitrary/guessing manner then execute based on that read is the winner. And im not talking about build here.
If you are making nonstop ling in a 12hat vs 12hat opening situation and your opponent makes a few drones at the start of the ling pump cycle, you dont know he has made drones until they actually hatch. Sure after you see them you could decide to react in response but given that you are both producing your larvae, tech and everything at the exact same timing it is logical that the match up is related mostly to guesswork.
Taking the initiative is also often disastrous being that the person defending should in the army vs army sense(Not taking into account base harassment) always have the advantage.
|
On March 21 2008 23:34 red.venom wrote:Show nested quote +On March 21 2008 09:19 5HITCOMBO wrote:
Guys, how often are zvz games at the pro level decided off of the build?
It's honestly more about adaptation. Every zvz is different.
Prob half end mere minutes after the openings have been chosen.I dont know if I think adaptation is a great description. More like tactical exploitation. Given a game is on even or semi-even footing build-wise whomever can "read" their opponent better in a fairly arbitrary/guessing manner then execute based on that read is the winner. And im not talking about build here. If you are making nonstop ling in a 12hat vs 12hat opening situation and your opponent makes a few drones at the start of the ling pump cycle, you dont know he has made drones until they actually hatch. Sure after you see them you could decide to react in response but given that you are both producing your larvae, tech and everything at the exact same timing it is logical that the match up is related mostly to guesswork. Taking the initiative is also often disastrous being that the person defending should in the army vs army sense(Not taking into account base harassment) always have the advantage. Jaedong..if half are decided once the builds are chosen, why does he win so much? Why are there people who are 'good' at zvz
|
Russian Federation4235 Posts
Probabilities and StarCraft don't mix.
Or, rewording, playing unexpected and playing random are two completely different things, of which only one is productive.
|
I have not explained the concept clearly. I'll try again by using a simpler example.
In rock paper scissors, rock > scissors > paper > rock. In the probability table, it would be listed as
r p s
r 50 0 100
p 100 50 0
s 0 100 50
Now you say rock v rock is not 50% win, it is a tie, well you rego and in that rego you have a 50% shot. My program would say you should pick each randomly with 33% chance. This means that this is the only strategy such that there exist no other strategy that beats it more than 50% of the time. This is a trivial example, so lets say rock paper scissors is a little more complicated, lets say if one player chooses rock and the other scissors, this is a "skunk". A skunk is like 3 wins, so if you were doing best of 10 this is much better than a normal win.
What percent of the time should you choose each now? Try to answer this now in your head (answer below). I guarantee no one will even come close to the correct answer (except maybe some poker players) and that is the point of this topic, to try and calculate something that we all do naturally but much more accurately.
Alot of people have said "but starcraft is not about the build its about how you play." This is totally true, but the fact remains some builds do have small advantages over the other. Even if these advantages are small, one should still strive to cache in on every advantage possible no matter how small, that is starcraft.
Starcraft is just like rock paper scissors, except by choosing a counter build you don't automatically win, instead you might have a 55% chance of winning. Where as some other counter like 9pool versus 12 hatch might have an 85% chance of win. Just like the "skunk" from rock paper scissors, choosing a 9pool over a 12hatch has a much higher pay off than something like 12 pool over a 9 pool.
Obviously skill has a much higher impact than the build in many cases, if you are really serious about improving you should be practicing not reading this. But this topic is theoretical for players already at "the pro level". I believe that even though this isn't directly that useful, if given reasonably accurate estimation of the win percentages, it will shed some light on which zerg builds are viable and which are not, perhaps better than previous analysis has done.
Here is the answer to the rock paper scissors skunk thing:
The answer is 20% rock, 60% paper, and 20% scissors. You are probably thinking pssh that can't be right, but it is actually easy to verify that it is correct using the assertion mentioned earlier: "this is the only strategy such that there exist no other strategy that beats it more than 50% of the time." Although since weight of winning with rock over scissors is +3 instead of 1, it needs to be reworded to "this is the only strategy such that there exist no other strategy that has a positive expected score against it."
Here's how to check it.
rock v the strat:
strat choose rock 20%, but score diff is 0 since tie
strat chooses paper 60%, so 0.6 * -1 (for loss)
strat chooses scissors 20%, so 0.2 * 3 (3 for skunk)
add them up ======================================
equals 0
This means that if they choose rock against your strat on average the net score difference is 0.
Repeat for paper: 20% * 1 + 60% * 0 + 20% * -1 = 0
Repeat for scissors: 20% * -3 + 60% * 1 + 20% * 0 = 0
This means that no matter what they choose they cannot beat you on average. You are probably thinking that's nice, but even if they have an inferior strategy, using this will not actually give you an advantage, it will just tie. That is exactly correct. This only tells you how to be unbeatable on average not how to exploit other players tendencies. If you know your opponents tendencies, you can calculate which build you should use against them by just choosing the one that has the highest expected win average. The only time it pays to use a randomized starting build, is when your opponent knows your tendencies and you want to give him no option that on average beats you.
For all this to work we need better estimations of one build versus another. This is where I need your help. You don't have to redo the whole table, if you just say stuff like "I think at the pro level 9 pool has a 40% chance of beating 12 pool." If you are someone awesome like incontrol or midian you don't even need to explain why (other people do though).
|
On March 22 2008 02:14 flag wrote:
I have not explained the concept clearly. I'll try again by using a simpler example.
In rock paper scissors, rock > scissors > paper > rock. In the probability table, it would be listed as
r p s
r 50 0 100
p 100 50 0
s 0 100 50
Now you say rock v rock is not 50% win, it is a tie, well you rego and in that rego you have a 50% shot. My program would say you should pick each randomly with 33% chance. This means that this is the only strategy such that there exist no other strategy that beats it more than 50% of the time. This is a trivial example, so lets say rock paper scissors is a little more complicated, lets say if one player chooses rock and the other scissors, this is a "skunk". A skunk is like 3 wins, so if you were doing best of 10 this is much better than a normal win.
What percent of the time should you choose each now? Try to answer this now in your head (answer below). I guarantee no one will even come close to the correct answer (except maybe some poker players) and that is the point of this topic, to try and calculate something that we all do naturally but much more accurately.
Alot of people have said "but starcraft is not about the build its about how you play." This is totally true, but the fact remains some builds do have small advantages over the other. Even if these advantages are small, one should still strive to cache in on every advantage possible no matter how small, that is starcraft.
Starcraft is just like rock paper scissors, except by choosing a counter build you don't automatically win, instead you might have a 55% chance of winning. Where as some other counter like 9pool versus 12 hatch might have an 85% chance of win. Just like the "skunk" from rock paper scissors, choosing a 9pool over a 12hatch has a much higher pay off than something like 12 pool over a 9 pool.
Obviously skill has a much higher impact than the build in many cases, if you are really serious about improving you should be practicing not reading this. But this topic is theoretical for players already at "the pro level". I believe that even though this isn't directly that useful, if given reasonably accurate estimation of the win percentages, it will shed some light on which zerg builds are viable and which are not, perhaps better than previous analysis has done.
Here is the answer to the rock paper scissors skunk thing:
The answer is 20% rock, 60% paper, and 20% scissors. You are probably thinking pssh that can't be right, but it is actually easy to verify that it is correct using the assertion mentioned earlier: "this is the only strategy such that there exist no other strategy that beats it more than 50% of the time." Although since weight of winning with rock over scissors is +3 instead of 1, it needs to be reworded to "this is the only strategy such that there exist no other strategy that has a positive expected score against it."
Here's how to check it.
rock v the strat:
strat choose rock 20%, but score diff is 0 since tie
strat chooses paper 60%, so 0.6 * -1 (for loss)
strat chooses scissors 20%, so 0.2 * 3 (3 for skunk)
add them up ======================================
equals 0
This means that if they choose rock against your strat on average the net score difference is 0.
Repeat for paper: 20% * 1 + 60% * 0 + 20% * -1 = 0
Repeat for scissors: 20% * -3 + 60% * 1 + 20% * 0 = 0
This means that no matter what they choose they cannot beat you on average. You are probably thinking that's nice, but even if they have an inferior strategy, using this will not actually give you an advantage, it will just tie. That is exactly correct. This only tells you how to be unbeatable on average not how to exploit other players tendencies. If you know your opponents tendencies, you can calculate which build you should use against them by just choosing the one that has the highest expected win average. The only time it pays to use a randomized starting build, is when your opponent knows your tendencies and you want to give him no option that on average beats you.
For all this to work we need better estimations of one build versus another. This is where I need your help. You don't have to redo the whole table, if you just say stuff like "I think at the pro level 9 pool has a 40% chance of beating 12 pool." If you are someone awesome like incontrol or midian you don't even need to explain why (other people do though).
I do not understand how you can choose a strategy for a game of equal random chance.
Are you saying that you understand how to win every rock paper scissors match on average?
|
No, im saying I have a strategy for rock paper scissors that no one can beat me more than half the time. That strategy is choose rock 1/3 the time, choose scissors 1/3 of the time, choose paper 1/3 of the time, make this choice randomly.
I'm also saying that this is the only strategy that has this property.
|
I also disagree with which BOs you include. Nobody ever 8pools, since it makes no sense with respect to overlord timing. Also, the build I use the majority of the time is 11gas 10pool.
|
On March 22 2008 04:18 azndsh wrote:
I also disagree with which BOs you include. Nobody ever 8pools, since it makes no sense with respect to overlord timing. Also, the build I use the majority of the time is 11gas 10pool.
That means you agree actually, since after computation it was deemed don't 8 pool. It doesn't effect the percentages if the build isn't used, so it can't hurt to have them in extra. Please state your estimation analysis of 11gas 10pool versus other builds like 12pool 9pool 12hatch. And I'll throw it in in the chart, I've seen other zerg do this alot too so it should be added.
|
On March 22 2008 03:25 5HITCOMBO wrote:Show nested quote +On March 22 2008 02:14 flag wrote:
I have not explained the concept clearly. I'll try again by using a simpler example.
In rock paper scissors, rock > scissors > paper > rock. In the probability table, it would be listed as
r p s
r 50 0 100
p 100 50 0
s 0 100 50
Now you say rock v rock is not 50% win, it is a tie, well you rego and in that rego you have a 50% shot. My program would say you should pick each randomly with 33% chance. This means that this is the only strategy such that there exist no other strategy that beats it more than 50% of the time. This is a trivial example, so lets say rock paper scissors is a little more complicated, lets say if one player chooses rock and the other scissors, this is a "skunk". A skunk is like 3 wins, so if you were doing best of 10 this is much better than a normal win.
What percent of the time should you choose each now? Try to answer this now in your head (answer below). I guarantee no one will even come close to the correct answer (except maybe some poker players) and that is the point of this topic, to try and calculate something that we all do naturally but much more accurately.
Alot of people have said "but starcraft is not about the build its about how you play." This is totally true, but the fact remains some builds do have small advantages over the other. Even if these advantages are small, one should still strive to cache in on every advantage possible no matter how small, that is starcraft.
Starcraft is just like rock paper scissors, except by choosing a counter build you don't automatically win, instead you might have a 55% chance of winning. Where as some other counter like 9pool versus 12 hatch might have an 85% chance of win. Just like the "skunk" from rock paper scissors, choosing a 9pool over a 12hatch has a much higher pay off than something like 12 pool over a 9 pool.
Obviously skill has a much higher impact than the build in many cases, if you are really serious about improving you should be practicing not reading this. But this topic is theoretical for players already at "the pro level". I believe that even though this isn't directly that useful, if given reasonably accurate estimation of the win percentages, it will shed some light on which zerg builds are viable and which are not, perhaps better than previous analysis has done.
Here is the answer to the rock paper scissors skunk thing:
The answer is 20% rock, 60% paper, and 20% scissors. You are probably thinking pssh that can't be right, but it is actually easy to verify that it is correct using the assertion mentioned earlier: "this is the only strategy such that there exist no other strategy that beats it more than 50% of the time." Although since weight of winning with rock over scissors is +3 instead of 1, it needs to be reworded to "this is the only strategy such that there exist no other strategy that has a positive expected score against it."
Here's how to check it.
rock v the strat:
strat choose rock 20%, but score diff is 0 since tie
strat chooses paper 60%, so 0.6 * -1 (for loss)
strat chooses scissors 20%, so 0.2 * 3 (3 for skunk)
add them up ======================================
equals 0
This means that if they choose rock against your strat on average the net score difference is 0.
Repeat for paper: 20% * 1 + 60% * 0 + 20% * -1 = 0
Repeat for scissors: 20% * -3 + 60% * 1 + 20% * 0 = 0
This means that no matter what they choose they cannot beat you on average. You are probably thinking that's nice, but even if they have an inferior strategy, using this will not actually give you an advantage, it will just tie. That is exactly correct. This only tells you how to be unbeatable on average not how to exploit other players tendencies. If you know your opponents tendencies, you can calculate which build you should use against them by just choosing the one that has the highest expected win average. The only time it pays to use a randomized starting build, is when your opponent knows your tendencies and you want to give him no option that on average beats you.
For all this to work we need better estimations of one build versus another. This is where I need your help. You don't have to redo the whole table, if you just say stuff like "I think at the pro level 9 pool has a 40% chance of beating 12 pool." If you are someone awesome like incontrol or midian you don't even need to explain why (other people do though). I do not understand how you can choose a strategy for a game of equal random chance. Are you saying that you understand how to win every rock paper scissors match on average?
On March 22 2008 03:33 flag wrote:
No, im saying I have a strategy for rock paper scissors that no one can beat me more than half the time. That strategy is choose rock 1/3 the time, choose scissors 1/3 of the time, choose paper 1/3 of the time, make this choice randomly.
I'm also saying that this is the only strategy that has this property.
On March 22 2008 05:21 5HITCOMBO wrote:Show nested quote +On March 22 2008 03:33 flag wrote:
No, im saying I have a strategy for rock paper scissors that no one can beat me more than half the time. That strategy is choose rock 1/3 the time, choose scissors 1/3 of the time, choose paper 1/3 of the time, make this choice randomly.
I'm also saying that this is the only strategy that has this property. OH SHIT YOU HAVE A STRATEGY FOR WINNING HALF THE TIME IN ROCK PAPER SCISSORS????
You are essentially making fun of the obviousness of an answer to a question that you asked. That is not a very nice way to treat yourself.
I do not wish for you to harm yourself any more, so please 5hitcombo do not make any future post in this thread.
|
How did you make up those statistics?
|
the one thing I lack in this thing is the probabillity of a person using a certain BO against you.
|
merely as a point of interest, statistics have been gathered from mass rps gaming and it has been undeniably shown that it is NOT a game of chance, as people do NOT pick each choice 33.3333... % of the time.
Beginner players tend to play thus-
Rock is most common, so for their first throw they choose paper, to beat rock.
For non first throw, players tend to subconciously beat their own last throw. So their second would scissors.
I tested this with someone the other and they followed this pattern exactly ;p
As did I to start with, because I forgot lol. Then i remembered this, and won.
Of course more advanced RPS players go deeper into bluffs, double bluffs, etc, etc.
Serious, I'm not even kidding.
|
Calgary25980 Posts
Deleted some posts. I have nothing to add to this thread, but I think it's a worthwhile idea/project. As for how to get meaningful data into it, I have no idea.
|
On March 22 2008 03:33 flag wrote:
No, im saying I have a strategy for rock paper scissors that no one can beat me more than half the time. That strategy is choose rock 1/3 the time, choose scissors 1/3 of the time, choose paper 1/3 of the time, make this choice randomly.
I'm also saying that this is the only strategy that has this property.
Okay, I'm going to post one more thing and leave this thread for good.
Even if you have a strategy like that, you are incorrect in saying that "no one can beat me more than half the time."
No matter what, your opponent can always win if they choose the opposite of what you throw. This is the fault of statistics.
|
On March 22 2008 06:49 ZerG~LegenD wrote:
How did you make up those statistics?
For some of the match ups that occur less frequently I tested them with saarto. For others I watched a bunch of ZvZ replays of JulyZerg and Savior. It really is not very accurate at this point. I plan on attempting a more systematic way to calculate these probabilities soon, but I was also hoping to get some input from others.
On March 22 2008 12:55 MrBobby wrote:
merely as a point of interest, statistics have been gathered from mass rps gaming and it has been undeniably shown that it is NOT a game of chance, as people do NOT pick each choice 33.3333... % of the time.
Beginner players tend to play thus-
Rock is most common, so for their first throw they choose paper, to beat rock.
For non first throw, players tend to subconciously beat their own last throw. So their second would scissors.
I tested this with someone the other and they followed this pattern exactly ;p
As did I to start with, because I forgot lol. Then i remembered this, and won.
Of course more advanced RPS players go deeper into bluffs, double bluffs, etc, etc.
Serious, I'm not even kidding.
I think you might have missed a paragraph from previous post, hopefully this clears it up:
This means that no matter what they choose they cannot beat you on average. You are probably thinking that's nice, but even if they have an inferior strategy, using this will not actually give you an advantage, it will just tie. That is exactly correct. This only tells you how to be unbeatable on average not how to exploit other players tendencies. If you know your opponents tendencies, you can calculate which build you should use against them by just choosing the one that has the highest expected win average. The only time it pays to use a randomized starting build, is when your opponent knows your tendencies and you want to give him no option that on average beats you.
On March 22 2008 14:33 Chill wrote:
Deleted some posts. I have nothing to add to this thread, but I think it's a worthwhile idea/project. As for how to get meaningful data into it, I have no idea.
Thanks
|
I am very confused. I'm gonna say how I interpret this, and you correct me.
OK, so my understanding is, you start with a table with every mu vs. every other mu. You can make up (from watching games, pull numbers our of your ass, any method you wish) a table of probabilities (ie. you randomly say that 4 pool has 10% chance of beating 5 pool). You then make up another table of how likely the opponent is going to use a certain strat (ie. 10% of going 4 pool, 60% chance of going 9 pool, etc.). You then crank out some math based on positions and these two tables to determine which build "overall" will give you the most amount of wins over the long run.
Is my understanding correct?
Although this table won't be that useful, as you would have to recompute all of the tables for each player and each map, and even then the probabilities are very rough ballparks that won't decide how you play the game anyway. Though I do think it's pretty interesting, and things don't need to be useful to be interesting.
Just wondering, is your program as flexible as I think it is? Like, you can change any of the percentages around, you can add bo's (thus we can apply this to any mu we want)? How hard would it be (aside from redoing all the numbers and charts) to say, change the map from Python to Hunters (changing from 4 players to 8 players would screw up some of the scouting probabilities, no?)
|
Your understanding is basically correct except there is not a separate table for how likely your opponent is to use each strat, instead it uses the results for that.
The program doesn't have anything about starcraft in it, it just takes input of a matrix which has the percent win for each match up. And outputs what percent of the time to choose each. So for each match up, map, etc all the percentages would change and right now that would have to be done manually.
I have an idea to generate the percentages automatically using this method:
Simulate the builds, for every x seconds a player has lings in the other's base while they have none, give a drone kill. Once both players have lings it is now just a calculation of economic strength versus each other, this can be measured in how many seconds it would take one player to catch up economically to the other. Now the percent chance of win is solely a function of economic difference. This is not perfect, real starcraft is more complicated than this in many ways. Some of these ways could be accounted for but there are really too many. Two that I have in mind now are a small bonus of some sort for the aggressor. And some sort of bonus for getting gas up earlier.
This method will not be perfect but it will be consistent for all build orders at least. It could also be changed to other maps easily because only variables are time to get to them and a table of how many minerals per second per drone you get.
|
5hitcombo, I always thought of you as a pretty intelligent poster, and I am unfortunately annoyed by your blatant stupidity in this thread.
flag, I really appreciate your work into this, even if there are no major revelations that come from this. I think the biggest reason is because each individual player has their own tendencies, and the most important thing is to adapt to that particular opponent. Obviously a 1/3 1/3 1/3 strategy in RPS is optimal according to game theory, but since people do different strategies, there are counter strategies. Therefore, you make a small mistake of deviating from "optimal play" in order to take advantage of your opponent's "larger mistakes". (this ties into fundamental theory of poker, etc..)
Simple Starcraft example would be if someone constantly 4 pools, then you would 5-9 pool every game, despite this not being the "optimal strategy" in your table. If I play against Julyzerg, it is therefore more intimidating than a more 'conventional' zerg, seeing how he is capable of very rarely 4pooling, making his potential "build range" wide.
Bottom line is, while it is good to try to seek perfection, true perfection is knowing your opponents tendencies and making your 'build order range' as wide as possible (you are capable of anything), while subtly adapting to exploit your opponent.
|
Well done. I've been thinking of doing this as well for a long time, but i couldnt really convince myself of the usefulness. :/ anyways, im happy to se it done. 
For those that want to go more into detail, the solution is refered to as a "Nash equilibrium" and you can read more about it on wiki. Correct me if this is not how you've done flag, but Im pretty sure this is how you did it.
http://en.wikipedia.org/wiki/Nash_equilibrium
Reading just the first paragraph a few times should do the trick.
Note, that while, as stated already, this isnt useful in the case of a public game on bnet, it is highly useful for progamers. Difference is that your oponent in progaming will have access to all opening you've ever done. The (mathematically simpler) case of random pubby was cover by chill a while ago iirc.
So you basically just made up the winning percentages yourself? Or could you explain a bit closer exactly how you got them. I think the percentages really need to be looked over for this to be anywhere close to reality.
Im not a good player myself, but isnt 42% for 12 pool > 12 hatch a bit high? If you'd down that percentage a bit, 12 hatch would be more viable, so itd be done more, which would make 9 pool more viable, giving results closer to reality.
Im not sure. I would love it if this would produce useful infomration, but I think you have to find a better way of getting the percentages for this to be useful.  Like statistics from every ZvZ ever played by all progamers... So if someone got a year or two to spare for just watching ZvZs and taking statistics, we could get this going. 
|
It would be awesome to play a SC text game like this, keep it up!
I 12pool! Your turn Kaiba!
And using it for the actual game would be cool. Though even is every mu was ZvZ lings only, it still makes it pretty complicated. But a table of all early BOs vs other BOs would be possible.
|
Exalted thanks for the post. You are saying that the assumptions in Nash equilibrium are not met, the players are not perfect in their choice of stategy therefore this method will not give the optimal way to exploit them. This is completely true, but on the other hand using this method you can't go wrong (on average). This method isn't chosen to exploit other players, but to have the most mathematical basis to draw conclusions from.
Cascade, thanks for finding out what the method is really called! It would have saved me alot of trouble if I could have just said "click here if you don't believe me, it is sound game theory" instead of trying to explain everything. I had never heard of Nash equilibrium or anyone doing something like this before, but I figured it has probably been done before since it is all pretty straightforward to derive from assuming two players in imperfect knowledge game are optimal and solving how they should play.
As for the percentages, they are from some testing rush builds versus real builds and just general estimating. It is the real weakness to this method which is why I am always asking for help with it. In prev post I described a more systematic way to do this, but it still has weaknesses. Watching all pro replays is another way, but you would also have to factor in the players strength (which can be estimated with elo or something). This is actually plausible since bwchart can already get the BO from a replay I think. The main problem with it would be finding the replays, especially since many many replays would be needed for each map.
Edit: changed 12pool versus 12hatch to 36 percent. This caused new results to be 38.8% overpool, 55.5% 12pool, 5.5% 12 hatch.
|
EDIT on above: ahahhaa, well done on inventing Nash equilibria! 
Another thing I came to think about that you could do to get an idea of how sensititve the results are to the winning percentages:
1) Estimate the error for each percentage.
2) Rerun your program, but with new parameters, which is the old ones, but randomly modified according to the error estimates.
3) Do this many times, and look at the the distribution in the output.
My first approach at doing the errors would probably be to first change coordinates to artcan(winning %), then do normal gaussian error modification, and then transform back. Doing a straight gaussian directly in the winning percentages wouldnt be very realistic close to 1 and 0. Just a suggestion, you seem to know what you are doing.
Also, if it's easy for you to copy paste the code it'd be fun to have a quick look. spoiler it though.
|
Ah good idea, I had thought about attempting to get at sensitivity. But at the time I didn't think there would be any use for it, but now that you bring it up again, it could be really useful for determining which percentages affect the results the most and thus we need to put the most effort into approximating them. Also I will post the code, the only reason I haven't so far is because I'm a little embarrassed at how I calculate it. If you know which choices are viable (in the Nash equilibrium using new terminology), then it is easy to calculate, it is just solving a system of linear equations. So the tricky part was figuring out which ones are in. My approach right now is basically brute force, there are definitely more efficient ways, but I chose this because I wanted to minimize the chance of me making a mistake. Reading this wikipedia article will probably help me clean up the code some.
|
if its only a system of linear equations, then you can just solve it with all strategies straight away, right? A computer can do a 9x9 system really fast, and with the current percentages you can remove 4 pool and 5 pool straight away, since 6 pool is better against every other build anyway.
But are you sure it is only a linear system of equations? There are supposed to be several nash equilibria in general, and you cant get that from a linear system of equations. I'll look into it a bit mroe I think... it was some time since i did game theory, and i'm glad to find an excuse to get back to it.
|
Yeah, the if player 1 has options a,b,c and player 2 d,e,f
let "ad" mean chance of "a" beating "d", "a" mean chance of player 1 choosing "a"
then the system is
ad*d+ae*e+af*f=x
bd*d+be*e+bf*f=x
cd*d+ce*e+cf*f=x
and vice versa for solving for a,b,c
where x is the chance of a player 1 beating player 2 (50% for mirror matches). This value does not need to be calculated or hard coded either, any value can be used, but you must then scale d,e,f so that their sum = 100%.
The equation comes from saying "if I use optimal percent choice for each, it doesn't matter what you choose (assuming its "in the nach equation"), thus the expected score for all choices are equal.
You are right, the calculation is very easy for computer, the only slow part was figuring out which variables are relevant (which can be made very fast too I'm sure).
Edit: I don't know about several nach equalibrium's. There should only be one unless the matrix made by the system of linear equations is non invertible in which case there would be multiple ones. But in practice this is not likely to occur.
|
Im getting the same system from a different approach (partial derivaties of gain for a player, etc). But for example the drivers game on wiki is a 2player, 2 strategy game with 3 nash equilibria.
I guess the uniqueness is a property of symmetric zero-sum games. :/
|
Yeah I think the uniqueness is just from the your loss = my gain (zero sum). So I guess this stuff is just a special case of nash equilibrium.
I spent a little time working on a method to estimate economic strength. Basically it is to calculate the difference in time it would take to reach supply n as n goes to infinity. So like 12 pool versus overpool, the only difference is that the 12 pool gets 3 more drones earlier, but the overpool can just get these drones later and everything will be exactly the same (because neither waste larva), except the 12 pool will have more minerals. I haven't calculated how much more, but if it were 50 minerals then that would result in only about a 2 second economic lead. This should provide a good way to compare stuff how much early hatch helps, versus larva, versus minerals.
Real ZvZ though is more complicated. I watched http://teamliquid.net/tlpd/games/8668_Orion_vs_type-b[s.g]
And it raises a few questions for me:
It is 9 pool versus 12 pool. Basically the 9 pooler is unable to do any damage but keeps the 12 pooler contained. The 9 pooler gets spire a little earlier, and the 12 pooler instead decides to make scourge. The scourge get raped and 9 pooler wins.
Someone in the youtube comments said 12 pooler went scourge not because he was behind in time, but because he was behind in gas? If this is true I really don't see how 9 pool can be considered to be at a disadvantage v 12 pool?
Also right now I list 9 pool v 12 hatch at nat as 100% win, but I think this needs to be lowered. If the spawn points are far, and you just cancel the hatch you might be able to survive without being too far behind.
So I'm having doubts about whether or not there really is a systematic way to get the table of percents, but I still think if we get help of high level zerg players we can still get more accurate and meaningful results than nothing.
|
ZvZ isn't just decided by the opening BO and the subsequent tactical micro, the strategy goes a little deeper than that. There is some random element to it yes, but more than that it is just really hard to understand the correct decisions regarding larvae production, zergling positioning, tech timings and positionings, on such a tiny economy where every mistake can be horribly punished.
That is an additional reason why so few are good at ZvZ, not just the randomness that comes from lack of scouting intelligence, a small strategic mistake can cripple you if the opponent happens to take advantage of it, its not nearly so bad in most of the other matchups.
|
I definitely agree with FieryBalrog's above post. Often in a ZvZ you can tell who the more experienced player at the matchup is, as they can take a disadvantageous situation and turn it into a win through one tiny mistake.
An example of this could be a ZvZ I just played where I went 12pool against 12hatchexpo. His larva count allowed him to pressure with more lings, and my spire timing was just slightly ahead of his. I just patiently waited for an opportunity to bait him into fighting on my terms (with my sunken firing on him and my hatcheries close by for reinforcements), and when he eventually fell for it I easily finished him with a counter, as he'd expended his army for little gain.
And yes, I do want a cookie.
|
Funny that you made such a thread, I was actually in the process of breaking down all the blood bath builds (ZvZ) into a graph so you could tell which builds are best overall, and which builds can be timed to take advantage of, and when etc.
If you play correctly you will almost never lose to a 4-5pool if you 9pool on bloodbath. So imo on a 128x128 map 4-5 is only gonna beat a FE or some other slow build.
|
I know I said I was out of this thread, but I'd like to explain briefly why 9 pool is not countered by 12 pool if played correctly.
The old mentality was that you were supposed to attack with your lings if you chose to pool faster. However, the old rock-paper-scissors zvz has been largely replaced by the newer "gas as soon as feasible" zvz. The faster you pool, in general, the faster you get gas. The faster you get gas, the sooner you have a lair. It doesn't matter that your opponent has a better mineral economy; you have a spire and more gas! If you 9 pool and gas immediately, you have an overlord and roughly 1.5 drone spawntime gas advantage on a 12 pooler. This translates into an overlord and roughly 1.5 drone spawntime faster lair and spire. Assuming that you keep pressuring your opponent to make lings by making pure lings yourself, but not engaging, you have entirely negated his mineral advantage with a more important gas/time advantage.
12 hatch is no longer viable in zvz. 12 pool loses to a correctly played 9 pool.
However, all of this is subject to blunders, which can also completely turn the tide in zvz.
|
On March 25 2008 20:12 5HITCOMBO wrote:
The old mentality was that you were supposed to attack with your lings if you chose to pool faster. However, the old rock-paper-scissors zvz has been largely replaced by the newer "gas as soon as feasible" zvz. The faster you pool, in general, the faster you get gas. The faster you get gas, the sooner you have a lair. It doesn't matter that your opponent has a better mineral economy; you have a spire and more gas! If you 9 pool and gas immediately, you have an overlord and roughly 1.5 drone spawntime gas advantage on a 12 pooler. This translates into an overlord and roughly 1.5 drone spawntime faster lair and spire. Assuming that you keep pressuring your opponent to make lings by making pure lings yourself, but not engaging, you have entirely negated his mineral advantage with a more important gas/time advantage.
Holy crap. I'd always been tormented by "why Inc said 9pool" and now it makes sense O_O
Everything else in this thread aside, thanks, it makes so much more sense now.
|
On March 25 2008 20:12 5HITCOMBO wrote:
I know I said I was out of this thread, but I'd like to explain briefly why 9 pool is not countered by 12 pool if played correctly.
The old mentality was that you were supposed to attack with your lings if you chose to pool faster. However, the old rock-paper-scissors zvz has been largely replaced by the newer "gas as soon as feasible" zvz. The faster you pool, in general, the faster you get gas. The faster you get gas, the sooner you have a lair. It doesn't matter that your opponent has a better mineral economy; you have a spire and more gas! If you 9 pool and gas immediately, you have an overlord and roughly 1.5 drone spawntime gas advantage on a 12 pooler. This translates into an overlord and roughly 1.5 drone spawntime faster lair and spire. Assuming that you keep pressuring your opponent to make lings by making pure lings yourself, but not engaging, you have entirely negated his mineral advantage with a more important gas/time advantage.
12 hatch is no longer viable in zvz. 12 pool loses to a correctly played 9 pool.
However, all of this is subject to blunders, which can also completely turn the tide in zvz.
I'm not saying you are wrong, but I'd like some more insight about this. From my own experience, slightly faster spire and more gas won't get you ahead in a low econ ling heavy zvz. Both players will have plenty of gas for a while anyway if they keep full mining. The 12 pooler can afford a 2nd hatch faster which is pretty important. Maybe the extra gas/early spire is more of a factor in pro level, and 9pool is just harder to manage. But I feel that in this age of agressive zvz, less games are decided by lack of gas leading to a smaller muta army.
|
While I agree with the importance of a second hatchery, I feel that it is trumped by a faster lair. If the 12 pooler delays lair to get his second hatch, i.e. 12 pool 12 hat 11 gas, you have an extra 300 min advantage in time on him. His second hatchery will pop around the time your spire goes up, and his lair will be only halfway done. If you keep your lings at the top of your ramp, delay until you can get 3 muta, and then pump scourge from there, you force him on the aggressive-defense of trying to break your ramp with pure lings. One muta is HUGE here. As long as you clear the lings from your base, you can simply match his scourge production with scourge production of your own, and he can't catch up to your muta production. Take down his overlords with scourge, snipe some lings and drones with mutas, and whatever you do, don't lose muta to scourge if you can help it.
If played at an equal skill level from both sides, this is quite the advantage. However, we know that's not always the case.
|
Also note that 12 pool 11 gas generally does not get a second hatch until lair is morphing, at which point the production of lings from that hatch does not factor into the ramp break.
|
Calgary25980 Posts
I was silently disagreeing with almost everything you've said in this thread, until I read "ramp". Now I agree. But on non-ramped maps I still believe 12 Pool beats out 9 Pool.
I guess the non-ramped maps of today (Blue Storm, Longinus, Tau Cross, Katrina, Ungoro, etc) just made me assume you were talking about non-ramp maps.
|
On March 25 2008 15:35 CharlieMurphy wrote:
Funny that you made such a thread, I was actually in the process of breaking down all the blood bath builds (ZvZ) into a graph so you could tell which builds are best overall, and which builds can be timed to take advantage of, and when etc.
If you play correctly you will almost never lose to a 4-5pool if you 9pool on bloodbath. So imo on a 128x128 map 4-5 is only gonna beat a FE or some other slow build.
Heh I would like to see that blood bath chart, but I think it will be a different kind of analysis since most of the time its easy to get a scout off making a certain build superior and no randomness needed, exceptions exist though.
Thanks 5hitcombo for answering my question, it seems like there really isn't much of a counter to 9 pool for ramped maps then, except maybe an overpool?
Here is some timing stuff:
build (P=pool, d=drone, D=extractor trick drone, etc)
-> when get lings(in seconds)
what have after about 2000 trigger frames (12 per second) if after making 6 lings switch back to eco, listed as drones, minerals, larva, frames -> seconds to reach a certain point in economy in seconds (specific point does not matter as long as large and the same for all).
todo: extractor timing
4pool
Pdzzz -> 83
8, 191, 1, 1997 -> 636.0
<todo do 5pool-8pool>
9pool (non gas build)
dddddPdoDzzzH -> 109
13, 171, 0, 2004 (hatch at 2458) -> 568.6
overpool
dddddoPdddHzzz -> 121-131 (not all at same time)
13, 220, 0, 2004 (hatch at 2300) -> 563.0
12pool
dddddodddPdHzzz -> 136
13, 265, 0, 2004 (hatch at 2329) -> 561.4
12hatch
dddddodddHPdddzzz -> 165
13, 337, 0, 2004 (hatch at 2047) -> 553.3
for 9pool v 12hatch, if you kill 3 drones you are ahead which should be easily doable in the 15-20 seconds you have in their base before they get lings.
This might be useful for comparing builds but it doesn't factor in gas/lair timing at all yet. It is interesting that overpool is only 1.6 seconds behind 12 pool economically, but yet it can get lings about 11 seconds earlier.
After seeing these numbers I fully agree with what people are saying, ZvZ is hardly about the build, the worse counters only give about a 7 second economic advantage, this is by no means enough to win or lose as it takes about 25 seconds to get from ramp to ramp. That being said, there are still small advantages to gain so there is a reason to try and always get the build advantage. Perhaps other match ups could be better for analysis.
Here is map showing how long it takes lings (and ovie) to get to various places in seconds:
Here is source code for programs. You'll need ruby1.9 for the one to solve the system of linear equations and 1.8 for the others. I have not made any attempt to clean up the code or make readable (basically its all just stuff I wrote to calculate stuff without any regard for other people sorry).
|
Alright, this is gonna take a few days to sink into my head...
|
This is a very funny topic flag, thx a lot!! :-))
A few comments :
- as some already mentioned, it could be even more interesting for other MUs
- for medium skilled people i think the importance of the BO is bigger than for real gosus. So even if this thread will probably learn nothing to incontrol or nony or guys like that, i think it can really be useful for less good players
- at least it's very interesting intellectually
- a Nash equilibrium has no reason to be unique, as it is a "partial" optimum (ie one cannot do better by changing its own strategy while the other doesn't change) and it has nothing to do with zero sum games (see below for details)
- of course a global (deterministic) maximum is a Nash equilibrium
- the "strength" of generalized equilibrium is that it deals with the research of a (global) maximum, and it will exist and be unique under quite weak conditions (while Nash's will almost never be).
About the resolution and a few corrections :
1) notations :
player 1 has n possible strats and player 2 has N. I assume n less or equal to N.
In fact to solve the problem you have to solve 2 linear systems of size (N-1,n-1) and (n-1,N-1) respectively, the second matrix being the transposed of the first one (so let us consider only one).
The matrix (call it M) comes from the matrix of gains (n,N) but we substract the last column to all other colums and then the last line to all other lines (the order is not important of course).
More precisely mij = mij - min - mNj + mNn
-> this comes from the fact that the sum of probas must be equal to 1, and so the dimension is not n but n-1 (resp not N but N-1).
2) If this matrix is regular (= invertible), then there will exist a unique "theoretical" optimum, but we must check it is indeed a maximum and that it gives a solution (p1,...,pn-1) such as all are positive or 0, and the sum is less or equal to 1. If not, then the solution will be degenerated (ie at least one proba will be 0) or there will be an infinity of solutions (only if the matrix is singular = non invertible). I don't know if there is an a priori way to know if it will be the case...
3) about the uniqueness of the Nash equilibrium and the zero sum :
it has no relation. In fact in a zero sum game as well as in a non zero game you can have all cases : no (Nash) equilibirum, 1 unique equilibirum or several equilibria.
Look at the following examples :
0 equ.
(1,-1) (0, 0) (0, 0)
(0, 0) (1,-1) (-1,1)
(0, 0) (-1,1) (1,-1)
1 unique equ. (coeff 1,1)
(0, 0) (0, 0) (0, 0)
(0, 0) (1,-1) (-1,1)
(0, 0) (-1,1) (1,-1)
3 equ. (all coeff of first line)
(0, 0) (0, 0) (0, 0)
(0, 0) (1,-1) (0, 0)
(0, 0) (1,-1) (1,-1)
And if you add 1 to the gains of both players in all configurations, then it will give you non zero sum games absolutely equivalent to these 3 games, so the conclusion is the same for non zero games.
4) you said that the two players will have the same number of viable strategies -> this is slightly untrue (in non mirror mus of course).
In fact you must deal here with a system of N equations with n variables with N>n, say MA = B, B in R^N, A in R^n. M can't be surjecitve here, but in particular cases we can still solve this problem. It's only a matter of consistency between the lines : if the last N-n lines are linear combinations of the previous ones, then it's ok. If it's the case, player with n options will have a unique optimal stategy (assuming the rank of M is n), while the player with N might have an infinity of equivalent optimal strategies (if you forget about the condition p1,...,pN in [0,1] and sum = 1, it will be a vector space of dimension N-n, in fact it will the intersection of those 2 sets, which can be null, this is why i said "might have" before).
A very simple example is if 2 lines are absolutely the same (ie strat A1 and strat A2 for example give exactly the same gain against any strat B1,...,Bn), there the player can choose the proba p1 and p2 as he wants, as long as the sum p1+p2 is equal to the "optimal" proba he would obtain by considering the "reduced" game without strat A2 (so if the "reduced" game is not degenerated, neither will be the original problem).
You can indeed construct less "stupid" games where the linear combition between lines is less, well, "stupid". :-)
If the system is not consistent (ie B is not in the image of M, then it means the system is degenerated and at least 1 proba will be 0 -> as you said).
5) you said that in mirror mus, there is never an even number of viable strats -> again it's slightly untrue (more or less the same as before). But the reason why it is almost true is quite interesting.
In a mirror game (and only a mirror), M will be (square and) antisymmetric (ie tM = - M). And we can show that such a matrix will have an even rank. As M is of size n-1, we see that if n is even we won't have an invertible matrix. So if the system is consistent (ie if B is in the image of M), then we will have an infinity of solutions, which have no reason to imply that one proba is 0.
Exactly as before you can for example take a matrix with 2 identical lines, or construct "smarter" counter-examples.
But i agree those 2 last remarks will "never" happen in real life, so it's just theoretical remarks...
Hope it was useful.
|
On March 26 2008 06:06 Chill wrote:
I was silently disagreeing with almost everything you've said in this thread, until I read "ramp". Now I agree. But on non-ramped maps I still believe 12 Pool beats out 9 Pool.
I guess the non-ramped maps of today (Blue Storm, Longinus, Tau Cross, Katrina, Ungoro, etc) just made me assume you were talking about non-ramp maps.
Oh, yes, true, definitely.
I'm not a really diverse player or observer, though .
|
Hippo, nice to see someone analyzing the pure math of this stuff, because I sort of skimped on the proofs (mainly because I am bad at them). So should we call it generalized equilibrium instead of Nash?
Also about 2 comments about number of viable options. Since starcraft is a complex game, when 1 build faces another its chance of winning is really some real number more precise than what we list. And for the players to have a different number of viable options, something would have to work out so two unrelated real numbers are exactly equal, the chance of this is 1/infinity so I say it's not possible. But you are correct it really is possible. I was aware of this when I posted, but really didn't want to make the post any longer/I didn't posses the ability to explain it well.
Even though you say it will "never" happen in real life, I think your original statement has useful implications for real life. Because although the actual percent chance of a build beating another is some real number to infinite precision, our ability to measure/estimate it is very low precision. So things can work out to be close enough that we can't really say which is better and call them equal. This is also where style comes into play, maybe a certain build really is very so slightly better than some other, but a player has so much time invested in a previous style that it isn't better for them. Ofcourse we are trying to be theoretical so this stuff not that important, but just nice to keep it in mind.
In your post you said even number of options is this a typo or correct?
I'm glad that you like those statements btw
|
Well, the pleasure is mine. :-)
But for the "semantic" part, I was wrong : Walras equilibrium has nothing to do with game theory... it's a micro-economy concept. It's something about supply/demand equilibrium (i'm not an economist, I won't tell you more). So in the case where you allow random (or probablilist) strategies, it seems that you still call it a Nash equilibrium. Sorry I said shit (and don't know why I thought it was related :-o).
For the "real life" part, ok, then you must be careful and deal with those cases...
For the "even number" question you ask, well yes in the first sentence i meant "there is never an even number", but then in the explanation, it's correct : if n is even, then M (of size n-1) can't be invertible and we won't have a unique non-degenerated optimum.
I'll edit my post to take those 2 mistakes in consideration.
|
|
|
|
|
|
EPT![[image loading]](http://golfscript.com/temp/chart.png)
![[image loading]](http://golfscript.com/temp/zerglingpython.jpg)
