Satrina's Disproving Short-Circuit Evaluation


#1

Disproving Short-Circuit Evaluation

Originally posted on the Evil Empire guild website as a part of Satrina’s warrior guides. This was excavated from an archive made by the Wayback Machine. As such, offsite links will likely not work.

Satrina@Stormrage - Last updated 18 January 2006

Background

What we’re really doing here is proving that WoW doesn’t use a short-circuit evaluation, then providing evidence for table based combat. Instead of going into a bunch of math theory and talking about Bayes’ Theorem, we’ll just talk a little math and then let the numbers speak for themselves. Here are our two methods, the first is the short-circuit evaluation, the second is a table:

  • Random to see if your attack misses {random(100) <= 5}

  • Random to see if your attack is dodged {random(100) <= 10}

  • Random to see if your attack is parried {random(100) <= 10}

  • Random to see if your attack is blocked {random(100) <= 10}

  • Random to see if your attack is a critical hit {random(100) <= 15}

  • If you get here, your attack is a normal hit

  • 000-049 = Miss (5%)

  • 050-149 = Dodge (10%)

  • 150-249 = Parry (10%)

  • 250-349 = Block (10%)

  • 350-499 = Critical Hit (15%)

  • 500-999 = Hit (50%)

The fundamental difference between these two methods is that the first is conditional, and the second one is not. In the first method, you cannot possibly determine if an attack is dodged until you have determined that it didn’t miss. You cannot determine it is a hit until you have determined that it didn’t miss, wasn’t dodged, wasn’t parried, wasn’t blocked, and was not a critical hit. This is the key point -> none of the events are independent. What does that mean? It’s a variation on the classic coin flip problem. If I flip a penny, the chance of it being heads or tails is 50%. If I flip it twice, the chance of getting two heads in a row is 25%. You can’t get two heads in a row if the first flip comes up tails; the chance of getting two heads in a row is conditional on the first flip’s result. That is exactly what will happen here, following short-circuit evaluation. Let’s see how and why.

Results of a Non-Independent System

To illustrate, I wrote up a simple little program. It’s written in Lua, and if you copy and paste it then run it using the Lua interpreter, it will give you similar results to what I present here:

miss = 0
dodge = 0
parry = 0
block = 0
crit = 0
hit = 0

math.randomseed(os.time())

for i=1,1000000 do
	if (math.random(1,100) <= 5) then	
		miss = miss + 1
	elseif (math.random(1,100) <= 10) then
		dodge = dodge + 1
	elseif (math.random(1,100) <= 10) then
		parry = parry + 1
	elseif (math.random(1,100) <= 10) then
		block = block + 1
	elseif (math.random(1,100) <= 15) then
		crit = crit + 1
	else
		hit = hit + 1
	end
end

print("miss: "..miss.." "..miss/1000000)
print("dodge: "..dodge.." "..dodge/1000000)
print("parry: "..parry.." "..parry/1000000)
print("block: "..block.." "..block/1000000)
print("crit: "..crit.." "..crit/1000000)
print("hit: "..hit.." "..hit/1000000)

What this does is determine the result of a combat action following the short-circuit evaluation method, one million times, then print the results. It checks the 5% chance of a miss, then the 10% chance for a dodge, then 10% for a parry, then 15% for a crit, and then calls it a regular hit if none of the previous conditions are met. It gives the number of misses, dodges, parries, blocks, crits, and hits, as well as the percentage of total attacks that each one makes as printed results. Here are the results of one run:

Result	Count	Percentage
Misses	50215	5.0215%
Dodges	95482	9.5482%
Parries	85364	8.5364%
Blocks	76712	7.6712%
Crits	104321	10.4321%
Hits	587906	58.7906%

We see here that using this method, we get 104321 critical hits on 1000000 attacks. That’s 10.4%, not 15%. Where did the other 4.6% go? The problem isn’t that we lost 4.6% crits, it is that the conditional method “loses” attacks as it progresses through the series of evaluations. If we look at the number of dodges, we see it is 9.6%, which is close to the 10% we said our dodge rate. But, we did a million iterations. It should be a lot closer to 10% exactly. How do we find the missing dodges then? Remember, we can’t check to see if we dodged unless the attack was not a miss. There is no independence of events. That means the 50215 misses in our million attacks had no chance to be a dodge - so they don’t count. Look at this: 95482/(1000000 - 50215) = 0.10053. We find the missing 0.4% by discounting the attacks that were misses and could not possibly have been dodges.

This holds true all the way up the list. We can now find the missing 4.6% critical hits here:

104321/(1000000 - 50215 - 95482 - 85364 -76712) = 0.15070

We get 15% critical hits over ONLY those attacks that were not misses, dodged, parried, or blocked. Since we have it from Blizzard that you must get 15% critical hits over all attacks, which would be 150000 critical hits in this example, we prove that combat cannot be resolved by a short-circuit evaluation. Also note that if this was the method in play, you’d be getting short-changed on your dodges, blocks, and parries when something attacks you.

Results of an Independent System

Now we come back to the table based system. We generate one random number and look up what happens in the table. Because of this, any single check can be any result present in the table, with no conditions attached. This is a completely independent system. Here is another little program:

miss = 0
dodge = 0
parry = 0
block = 0
crit = 0
hit = 0

math.randomseed(os.time())

for i=1,1000000 do
	r = math.random(1,100)
	if (r <= 5) then	
		miss = miss + 1
	elseif (r > 5 and r <= 15) then
		dodge = dodge + 1
	elseif (r > 15 and r <= 25) then
		parry = parry + 1
	elseif (r > 25 and r <= 35) then
		block = block + 1
	elseif (r > 35 and r <= 50) then
		crit = crit + 1
	else
		hit = hit + 1
	end
end

print("miss: "..miss.." "..miss/1000000)
print("dodge: "..dodge.." "..dodge/1000000)
print("parry: "..parry.." "..parry/1000000)
print("block: "..block.." "..block/1000000)
print("crit: "..crit.." "..crit/1000000)
print("hit: "..hit.." "..hit/1000000)

What this does is determine the result of a combat action by generating a single random number and looking up the result in the table, one million times, then print the results. It gives the number of misses, dodges, parries, blocks, crits, and hits, as well as the percentage of total attacks that each one makes as printed results. Here are the results of one run:

Result	Count	Percentage
Misses	49984	4.9984%
Dodges	100113	10.0113%
Parries	99979	9.9979%
Blocks	99951	9.9951%
Crits	150316	15.0316%
Hits	499657	49.9657%

We see here that using this method, we get 150316 critical hits on 1000000 attacks. That’s 15%. Similarly, our miss, dodge, parry, and block rates are 5%, 10%, 10%, and 10%. The results here are consistent with what we are told to expect by Blizzard. Note that this does not absolutely prove that WoW uses table based combat, but given the history of MMORPGs using it for efficiency, it’s a good bet.