|
Hi, I'm a student at University of Milan of Computer Science. I found a Nash Equilibrium Strategy (i.e. a strategy belonging to a Nash Equilibrium) for ZvZ openings. If you don't know what is a NE, check out here: https://en.wikipedia.org/wiki/Nash_equilibrium
Anyway, to make it simple, an NE strategy in a mirror game like ZvZ is a strategy that cannot lose and at least can win if the opponent make mistakes. Being a mirror game, would mean that in a NE (i.è. if both opponent use NE strategies), they have both 50% of winning. An NE strategy in this case is a strategy that has AT LEAST 50% of winning vs every possible opponent strategy.
I make this assumptions: 4P beats 12P 100% of the times. 9P beats 4P 100%. 12P vs 9P: in this case I assumed that the player with 12P take an advantage, I assumed he's probability of winning the rest of the game is now 60%. So from 50-50 the chances are now 60-40. XPvsXP: of course if both player plays the same strategy they have both 50% of winning.
With a lot of math I found the NE of this game, and it is this mixed strategy (a mixed strategy is a strategy where we choose at random from pure strategies):
------------------------------------------------------------------------------------------------------------------------------------------
NE STRATEGY FOR ZVZ OPENING 1/11: 4P 5/11: 9P 5/11: 12P
------------------------------------------------------------------------------------------------------------------------------------------
So it means we go for 4Pool 1/11 of the times, 9P 5/11 of the times and 12P the other 5/11, choosing at random each game.
We now verify if it is really an equilibrium. We try every pure strategy vs our strategy and see what is his income.
4PvsNE: 1/11*0.5 + 5/11*0 + 5/11*1 = 0.5 So 4P has no advantage vs our strategy.
9PvsNE: 1/11*1 + 5/11*0.5 + 5/11*0.4 = 0.5 Same.
12PvsNE: 1/11*0 + 5/11*0.6 + 5/11*0.5 = 0.5 Same.
We saw that the opponent is indiffirent to play any of his strategy vs us.
Now let's take a look how other common strats performs vs our NE:
12H: I assumed that 12H has 0% winning vs 4P; 20% vs 9P, and 60% vs 12P. 12HvsNE: 1/11*0 + 5/11*0.2 + 5/11*0.6 = 36% So if any opponent include the 12H strategy in his strategy and play with us, he will give us a LARGE edge, so overall we will have an advantage on him. Cool!
Let's see 9H: Now I assumed a 0% winning vs 4P, 70% vs 9P, and 30% vs 12P. 9HvsNE: 1/11*0 + 5/11*0.7 + 5/11*0.3 = 45% We also take a SMALL edge with our NE strategy vs the 9H.
We can also question ourselves if that can be other equilibrium strategies in this subgame. We can easily proove there is not. Infact:
If an opponent uses any pure strategy (for example, 100% 9P), it is of course exploitable (i.e. exists a strategy that can win more than 50% vs him), so it cannot be an equilibrium strategy.
If an opponent uses a mixed strategy that has 9H or 12H with a probability >0%, he give up edge vs our strategy, so it has <50% of winning vs us, so it cannot be an equilibrium strategy.
If an opponent try to use a mixed strategy only between 9P and 12P (with both >0%), he is exploitable to 12P. If an opponent try to use a mixed strategy only between 4P and 9P (with both >0%), he is exploitable to 9P. If an opponent try to use a mixed strategy only between 4P and 12P (with both >0%), he is exploitable to 4P.
Finally, note that this is the only point of indifference for mixed strategies with 4P 9P and 12P, infact if you try any different frequencies you'll see they are exploitable. So, if you have 4P<1/11 you are exploitable with 12P. If you have 9P<5/11 you are exploitable with 4P. And if you have 12P<5/11, you are exploitable with 9P.
And now we saw that all the possible strategies cannot be equilibrium strategies, so the only equilibrium strategy is our super cool NE strategy:
1/11: 4P 5/11: 9P 5/11: 12P
EDIT: ------------------------------------------------------------------------------------------------------------------------------------------ CHANING A PARAMETER: (as suggested by Ty2) 4Pvs12P 80% instead of 100% ------------------------------------------------------------------------------------------------------------------------------------------
I also tried to calcolate the NE with: 4P beats 12P 80% (changing from 100% to 80%). The Nash Equilibrium for this subgame becomes (instead of the 1/11 5/11 5/11):
1/9: 4P 3/9: 9P 5/9: 12P
I also checked 9H and 12H and they are still losing strategies vs this NE.
EDIT 2: ------------------------------------------------------------------------------------------------------------------------------------------ *******BEST STRATEGY******* CHANING PARAMETERS WITH REAL DATA: (as suggested by Crunchums) http://www.teamliquid.net/forum/bw-strategy/348493-zvz-build-order-statistics AND AVOID PLAYING 4P ------------------------------------------------------------------------------------------------------------------------------------------
New parameters: 9P vs 12H: 74% 12H vs 12P: 62% 12P vs 9P: 54%
I found this AMAZING strategy, even WITHOUT using 4P (using 12H instead). This strategy is also very very close to the equilibrium:
9P: 4/10 12P: 5/10 12H: 1/10
This strategy ensure a 49.6% vs 9P and 12P, a 50% vs 4P, and wins vs 12H and 9H. We had to give up that 0.4% edge to avoid playing 4P, but I think it's worth it. Best strategy here!
------------------------------------------------------------------------------------------------------------------------------------------
Final remarks on strategies:
1) 9P and 12P: as we can see, it's always a good idea to have our 12P frequency >= our 9P frequency. 2) 9H: Consequently to the 1*, 9H is an overall bad strategy (only good for exploiting a leak), because it would be good only vs players who 9P more than anything else. 3) 12H: this is a nice build if we are not using 4P in our strategy, and only with very low frequency (like 4P).
Of course, when we are in game, while taking informations, we could dinamically change the strategy we are using. So if, for example, we are going to 12P and we scout the opponent who 12P too, we change to 12H to take an advantage. Our frequencies must be used only at the start of the game, without any information, and can be changed during the game.
I hope you guys enjoyed my mathematical analysis. Best regards! Federico Distefano
|
United States1430 Posts
4P doesn't beat 12P 100% of times. 4P beats 12 Hatch 100% of times though. 12 P like 99% of times will win. Nice post though, it reminds me of the Game Theory StarCraft class by Alan Feng. I really enjoy the mathematics.
|
@Ty2 I edited the post with your suggestions. Thank you!
Best regards!
|
On May 22 2017 03:36 Ty2 wrote: 4P doesn't beat 12P 100% of times. 4P beats 12 Hatch 100% of times though. 12 P like 99% of times will win. Nice post though, it reminds me of the Game Theory StarCraft class by Alan Feng. I really enjoy the mathematics. it depends on pool placement, I was able to win with 5p vs. a pool that was in the top right of the base blocking off the minerals
the spawn was 5 o'clock on FS, so he couldn't drill drones to protect his pool
if he was in another spawn, for example 11 o'clock, then his pool would be in the back of his base and not easy to snipe (it would be in the corner)
|
|
Thanks! Really interesting post!
|
Thanks guys! @Crunchums, I edited the post with your data and found a fantastic strategy! Thank you!
Best regards!
|
I think you'd need a larger sample size from a specific map for this to be useful. Players like JD and 2 player maps make the winrates really unreliable. Also, a build may be better suited for pro players than amateurs, so the winrates may not be comparable anyway.
|
Hi Sero! As you can see, even if you are changing parameters, there are proportions that seems to remain. 12P is always slightly more than 9P, and 12H is a very low frequency strategy (and has the same purpose of 4P).
In any way you change the parameters, you will not go too far from the 4/10, 5/10, 1/10 equilibrium. I tried with other parameters and the differences are very small.
You could also, starting from this results, slightly adjust the frequencies based on the map or other parameters.
Best regards!
|
Nice analysis, thanks for sharing. A question I have in mind is where do your assumptions come from?
|
On May 23 2017 00:38 LRM)TechnicS wrote: Nice analysis, thanks for sharing. A question I have in mind is where do your assumptions come from? He changed his assumption to be inline with 2012 progame data in edit 2.
|
Canada2480 Posts
I don't think that's how Nash Equilibriums work?
|
On May 23 2017 02:30 swanized wrote: I don't think that's how Nash Equilibriums work? Elaborate?
|
I think there's two other element worth discussing here that have not been mentioned yet.
First, there are serious differences between series play against one or a small number of opponents with information of your previous games, and games played anonymously or semi-anonymously against a ladder. For series play with open information, say in a best of 9 series, such a Nash Equilibrium-based strategy will almost certainly give a higher degree of success than executing one build with excellence. However, in a ladder scenario there is another aspect of gameplay that cannot be ignored.
This other major point of relevance is that there are non-neglible benefits brought about by practicing and executing fewer builds. Most human players are not so elite as to be able to perfectly execute every build and understand any possible contingency that may arise. Against an anonymous ladder, it may become optimal to pick one or two builds and execute them well, to the exclusion of other possibilities. However, given many players implementing such a strategy, the ladder strategic data and statistics may not match those of heads-up series play. As a result, that may shift the equilibrium strategy for ladder. This runs headlong into what many gamers refer to as the concept of 'the metagame' or 'the meta'.
|
I don't think 4p beats 12p even 80% of the time
|
Cool, it also sounds a lot like game theory to my ears. It would be cool to apply these calculations to a big dataset to see the final outcome. Maybe we can draw more statistically backed conclusions?
|
i think its more complex but as first tryout its good to see your work,
Are you using Lemke Howson algorithm? (its very good algorithm)
Next steps are incorporate Stochastics aspects (different maps imply uncertaintainty in scouting timing or success) also depending on player you can incorporate volatility as risky aversion consequence
Have you seen AI competition? (if you get an advantage with NE you would win :p)
|
What about openings like 11 gas 10 pool or 9 gas 10 pool, as well as the others?
Even without taking into account player skills or what large advantages even small mistakes or mismanagement can bring into ZvZ, or without maps characteristics and such - the data deals with a small pool of builds.
It is a very interesting research and I hope you continue it, and if so - look into more openings and their statistical data *if proper one exists, as even those are skewered by before mentioned points*.
|
ZvZ builds that are worth being included are ovepool gas, overgas and 12h in main.
|
I think you have to consider too many factors into this to make it acceptable as a NE strategy: like all the different openings mentioned above, specific map characteristics too (ground/air distance, obstacles, etc.), and who what else.
|
Your average ZvZ opponent isn't going to adjust her/his opening to how often you do 4 pool or 12 hatch.
I think every Z should go overpool vs random people on 4 player maps. Unless you have a certain read on your opponent or you know you need to play safe because you are going to outclass your opponent either way.
Also, it is more likely that you want the opening that helps you improve the fastest. Not the opening that allows you to win the most.
|
On May 26 2017 00:50 Ernaine wrote: Your average ZvZ opponent isn't going to adjust her/his opening to how often you do 4 pool or 12 hatch.
I think every Z should go overpool vs random people on 4 player maps. Unless you have a certain read on your opponent or you know you need to play safe because you are going to outclass your opponent either way.
Also, it is more likely that you want the opening that helps you improve the fastest. Not the opening that allows you to win the most.
No, you should go 12 pool against randoms.
12 pool does NOT lose to 4 pool, I've tested this several times
If you see 4 pool (lings coming out when your overlord gets to his expansion on FS) then you cancel your hatchery and just make one sunken inside your base. If he brings a drone to sunken you, you can make a sunken inside the range of that other sunken while being protected by your first one. You will STILL have 10 drones to 3, making 2 sunkens is worth.
If you don't see it right away, cancel the hatch and make two sunkens. You may need to cancel one if he focuses it. You need to protect your pool long enough to start lings/sunkens.
The only way to lose is to lose your pool and not have any sunkens started. Or to try to keep the hatchery up (stupid, your opponent is all-in, no reason to get greedy)
|
12 pool just hard counters 4 pool in all scenarios.. You get 6 lings out when his 6 lings arrive at your gate.
|
On May 26 2017 00:50 Ernaine wrote: Your average ZvZ opponent isn't going to adjust her/his opening to how often you do 4 pool or 12 hatch.
I think every Z should go overpool vs random people on 4 player maps. Unless you have a certain read on your opponent or you know you need to play safe because you are going to outclass your opponent either way.
Also, it is more likely that you want the opening that helps you improve the fastest. Not the opening that allows you to win the most.
If you outclass all your opponents, maybe you should find better opponents. Certainly, his strategy is not the highest win % vs opponents of lesser skill, but that shouldn't be of too much concern. Unless maybe you have JvZ level of play. (edit: didn't read your post properly. Disregard this paragraph.)
It is quite interesting to have a strategy that cannot be exploited. Mainly for tournament play or high level ladder with a very limited pool of players. For ladder play, it would be better to analyze the opening trend of your player base and find the best (single) opening against those. It's a nice find though. However, the concerns mentioned (additional openings, maps, etc.) have to be further addressed.
|
Thank you guys! Taking in consideration your new suggestions, I made this new equilibrium: --------------------------------------------------------------- CONDITION: Maps large enough to be sure you have >50% chances of holding a 4P with a 12P
EQUILIBRIUM STRATEGY: 3/10: 9P 6/10: 12P 1/10: 12H
This strategy ensure at least a 50% win rate vs all strategies! ---------------------------------------------------------------
See ya!
|
On June 24 2017 22:39 kogeT wrote: 12 pool just hard counters 4 pool in all scenarios.. You get 6 lings out when his 6 lings arrive at your gate. the 6 lings get to your base slightly earlier, but you can cancel your hatch and throw down two sunkens if he brings drones to sunken you
the only way to lose is to try to defend your hatchery with drones - and it should really be 5p with a drone or two for sunkens
|
What's more interesting is 9p vs. in base 11h 10p scout 10g
|
I had a long discussion about this with a bitcoin enthusiast. Apparently we should just discard the law of independent events and therefore mixed strategy.
I'm pretty interested in this thread though. I was a professional game theorist for about 20 months.
|
You have to take into account two things: scouting advantage on a four-player map, and rush distance. For example, if you have a short rush distance, an aggressive build may do more damage versus and economic build, if the rush distance is greater, the economic build has more time to prepare, and aggressive builds may not do as much damage. Scouting advantage happens on three or four-player maps when one person sends their initial overlord the 'wrong way', and the other sends one the 'right way'.
Don't even get me started on building placement.
|
EQUILIBRIUM STRATEGY: 3/10: 9P 6/10: 12P 1/10: 12H
Is this saying you achieve statistical equilibrium if you play 9 pool 30% of the time, etc?
|
On March 01 2018 03:13 Dazed. wrote: EQUILIBRIUM STRATEGY: 3/10: 9P 6/10: 12P 1/10: 12H
Is this saying you achieve statistical equilibrium if you play 9 pool 30% of the time, etc? You have 50% win rate vs. any strategy, assuming you have the win rates in the OP post vs. those strategies
|
as having published the iterative market thesis I guess I would say you should view this on a game-by-game basis, although that is not what my professional recognition received was.
you might consider:
game 1 game 2 and how (though not precisely in a tree) we view this question in the infinities.
|
|
|
|