EPTI 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.
[I] ZvZ Opening Probabilities - Page 3
| Forum Index > Brood War Strategy |
|
bumatlarge
United States4567 Posts
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. | ||
|
flag
United States228 Posts
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. | ||
|
Cascade
Australia5405 Posts
 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.  | ||
|
flag
United States228 Posts
| ||
|
Cascade
Australia5405 Posts
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. | ||
|
flag
United States228 Posts
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. | ||
|
Cascade
Australia5405 Posts
I guess the uniqueness is a property of symmetric zero-sum games. :/ | ||
|
flag
United States228 Posts
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. | ||
|
FieryBalrog
United States1381 Posts
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. | ||
|
ShaLLoW[baY]
Canada12499 Posts
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. | ||
|
CharlieMurphy
United States22895 Posts
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. | ||
|
5HITCOMBO
Japan2239 Posts
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. | ||
|
Southlight
United States11767 Posts
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. | ||
|
Breavman
Sweden598 Posts
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. | ||
|
5HITCOMBO
Japan2239 Posts
If played at an equal skill level from both sides, this is quite the advantage. However, we know that's not always the case. | ||
|
5HITCOMBO
Japan2239 Posts
| ||
Chill
Calgary25980 Posts
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. | ||
|
flag
United States228 Posts
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: ![[image loading]](http://golfscript.com/temp/zerglingpython.jpg) 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). | ||
|
bumatlarge
United States4567 Posts
| ||
|
hippo
France13 Posts
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. | ||
| ||
