King of Tokyo Analysis (clojure)
I wanted to find the optimal strategy for King of Tokyo. I didn't figure there would be easily exploitable game balance problems as Richard Garfield, the designer, teaches a course in Game Theory. But that doesn't mean that there won't be exploitable holes in individuals play.
To this end, I first wanted to find exact values for the dice rolls that drive the game. You roll 6 dice, then chose any of the 6 to roll again, then chose any of the 6 to roll yet again. To complicate matters, Victory Points are only awarded if you get 3 of a kind (1s, 2s, or 3s) at the end of your rerolls, and then you get the face value for the set of 3 and 1 point each for additional dice of that type -> [1 1 3 3 3 3] = 4 points. For all other rolls, you simply get the number that you roll of [attack, energy, life].
I didn't use simulation to find these expected values. I found exact values, using (memoize), a pre packaged clojure function to build lookup tables on the fly. The benefit of not using simulations, and instead, exploring all routes, is that you can be sure you're finding the best strategy, not just guessing which path to take and simulating to find the outcome of that guessed-at strategy.
Note that I have 2 mutually recursive functions building the lookup tables, and that one of these functions calls itself to build out individual rolls, even though the roll would generally occur at once. This is helpful when you are rerolling varying numbers of dice where the new rolls become a simple lookup. If you remove the memoization from the first function, the program's run time increases approximately 5 orders of magnitude.
If you run the code above, you will find that:
Optimal Victory Point Strategy averages: 2.2357416
Optimal Attack (or other singleton) strategy average: 2.5277777
From here, the next step is to build these functions into a full min-max game tree for a HU game, taking position(in-tokyo?) into account. This will produce a better feel for how long a game should run, but my suspicion is that games are short enough that cards aren't really meant to be a good strategy outside of opportunistic use. Instead, the focus is on nicely balanced design centered on the dice rolls.
Alternatively, you may find that there are other interesting games to use this technique with, such as Zombie Dice.
Here are the correct rerolls for every combination of Victory Point dice rolled. Non-VP dice were simply set to 6s, which represent any combinations of 4s, 5s, and 6s. The second column shows which dice to keep. The last column shows the average number of dice held after both rerolls. Many of the results here are obvious, but some aren't obvious and may be downright non-intuitive. For instance, if you roll 2 1s and no other victory dice, and you have 2 rolls left, don't keep the 1s.
With 2 ReRolls:
(1 1 1 1 1 1) - (1 1 1 1 1 1) - 4.0
(1 1 1 1 1 2) - (1 1 1 1 1) - 3.3055556
(1 1 1 1 1 3) - (1 1 1 1 1) - 3.3055556
(1 1 1 1 2 2) - (1 1 1 1) - 2.6111112
(1 1 1 1 2 3) - (1 1 1 1) - 2.6111112
(1 1 1 1 3 3) - (3 3) - 2.8056753
(1 1 1 2 2 2) - (1 1 1 2 2 2) - 3.0
(1 1 1 2 2 3) - (2 2 3) - 2.1527243
(1 1 1 2 3 3) - (3 3) - 2.8056753
(1 1 1 3 3 3) - (1 1 1 3 3 3) - 4.0
(1 1 2 2 2 2) - (2 2 2 2) - 3.6111112
(1 1 2 2 2 3) - (2 2 2) - 2.9493313
(1 1 2 2 3 3) - (3 3) - 2.8056753
(1 1 2 3 3 3) - (3 3 3) - 3.9338348
(1 1 3 3 3 3) - (3 3 3 3) - 4.611111
(1 2 2 2 2 2) - (2 2 2 2 2) - 4.3055553
(1 2 2 2 2 3) - (2 2 2 2) - 3.6111112
(1 2 2 2 3 3) - (2 2 2 3 3) - 3.1666667
(1 2 2 3 3 3) - (3 3 3) - 3.9338348
(1 2 3 3 3 3) - (3 3 3 3) - 4.611111
(1 3 3 3 3 3) - (3 3 3 3 3) - 5.3055553
(2 2 2 2 2 2) - (2 2 2 2 2 2) - 5.0
(2 2 2 2 2 3) - (2 2 2 2 2) - 4.3055553
(2 2 2 2 3 3) - (2 2 2 2) - 3.6111112
(2 2 2 3 3 3) - (2 2 2 3 3 3) - 5.0
(2 2 3 3 3 3) - (3 3 3 3) - 4.611111
(2 3 3 3 3 3) - (3 3 3 3 3) - 5.3055553
(3 3 3 3 3 3) - (3 3 3 3 3 3) - 6.0
(1 1 1 1 1 6) - (1 1 1 1 1) - 3.3055556
(1 1 1 1 2 6) - (1 1 1 1) - 2.6111112
(1 1 1 1 3 6) - (1 1 1 1) - 2.6111112
(1 1 1 2 2 6) - (2 2) - 2.1150994
(1 1 1 2 3 6) - (1 1 1) - 1.9610982
(1 1 1 3 3 6) - (3 3) - 2.8056753
(1 1 2 2 2 6) - (2 2 2) - 2.9493313
(1 1 2 2 3 6) - (2 2 3) - 2.1527243
(1 1 2 3 3 6) - (3 3) - 2.8056753
(1 1 3 3 3 6) - (3 3 3) - 3.9338348
(1 2 2 2 2 6) - (2 2 2 2) - 3.6111112
(1 2 2 2 3 6) - (2 2 2) - 2.9493313
(1 2 2 3 3 6) - (3 3) - 2.8056753
(1 2 3 3 3 6) - (3 3 3) - 3.9338348
(1 3 3 3 3 6) - (3 3 3 3) - 4.611111
(2 2 2 2 2 6) - (2 2 2 2 2) - 4.3055553
(2 2 2 2 3 6) - (2 2 2 2) - 3.6111112
(2 2 2 3 3 6) - (2 2 2 3 3) - 3.1666667
(2 2 3 3 3 6) - (3 3 3) - 3.9338348
(2 3 3 3 3 6) - (3 3 3 3) - 4.611111
(3 3 3 3 3 6) - (3 3 3 3 3) - 5.3055553
(1 1 1 1 6 6) - (1 1 1 1) - 2.6111112
(1 1 1 2 6 6) - (1 1 1) - 1.9610982
(1 1 1 3 6 6) - (1 1 1) - 1.9610982
(1 1 2 2 6 6) - (2 2) - 2.1150994
(1 1 2 3 6 6) - (3) - 1.842984
(1 1 3 3 6 6) - (3 3) - 2.8056753
(1 2 2 2 6 6) - (2 2 2) - 2.9493313
(1 2 2 3 6 6) - (2 2 3) - 2.1527243
(1 2 3 3 6 6) - (3 3) - 2.8056753
(1 3 3 3 6 6) - (3 3 3) - 3.9338348
(2 2 2 2 6 6) - (2 2 2 2) - 3.6111112
(2 2 2 3 6 6) - (2 2 2) - 2.9493313
(2 2 3 3 6 6) - (3 3) - 2.8056753
(2 3 3 3 6 6) - (3 3 3) - 3.9338348
(3 3 3 3 6 6) - (3 3 3 3) - 4.611111
(1 1 1 6 6 6) - (1 1 1) - 1.9610982
(1 1 2 6 6 6) - (2) - 1.5491251
(1 1 3 6 6 6) - (3) - 1.842984
(1 2 2 6 6 6) - (2 2) - 2.1150994
(1 2 3 6 6 6) - (3) - 1.842984
(1 3 3 6 6 6) - (3 3) - 2.8056753
(2 2 2 6 6 6) - (2 2 2) - 2.9493313
(2 2 3 6 6 6) - (2 2 3) - 2.1527243
(2 3 3 6 6 6) - (3 3) - 2.8056753
(3 3 3 6 6 6) - (3 3 3) - 3.9338348
(1 1 6 6 6 6) - (1 1) - 1.4615251
(1 2 6 6 6 6) - (2) - 1.5491251
(1 3 6 6 6 6) - (3) - 1.842984
(2 2 6 6 6 6) - (2 2) - 2.1150994
(2 3 6 6 6 6) - (3) - 1.842984
(3 3 6 6 6 6) - (3 3) - 2.8056753
(1 6 6 6 6 6) - () - 1.3433428
(2 6 6 6 6 6) - (2) - 1.5491251
(3 6 6 6 6 6) - (3) - 1.842984
(6 6 6 6 6 6) - () - 1.3433428
With 1 ReRoll left:
(1 1 1 1 1 1) - (1 1 1 1 1 1) - 4.0
(1 1 1 1 1 2) - (1 1 1 1 1) - 3.1666667
(1 1 1 1 1 3) - (1 1 1 1 1) - 3.1666667
(1 1 1 1 2 2) - (1 1 1 1) - 2.3333333
(1 1 1 1 2 3) - (1 1 1 1) - 2.3333333
(1 1 1 1 3 3) - (1 1 1 1) - 2.3333333
(1 1 1 2 2 2) - (1 1 1 2 2 2) - 3.0
(1 1 1 2 2 3) - (1 1 1) - 1.5231482
(1 1 1 2 3 3) - (3 3) - 1.7523148
(1 1 1 3 3 3) - (1 1 1 3 3 3) - 4.0
(1 1 2 2 2 2) - (2 2 2 2) - 3.3333333
(1 1 2 2 2 3) - (2 2 2) - 2.5185184
(1 1 2 2 3 3) - (3 3) - 1.7523148
(1 1 2 3 3 3) - (3 3 3) - 3.5138888
(1 1 3 3 3 3) - (3 3 3 3) - 4.3333335
(1 2 2 2 2 2) - (2 2 2 2 2) - 4.1666665
(1 2 2 2 2 3) - (2 2 2 2) - 3.3333333
(1 2 2 2 3 3) - (2 2 2 3 3) - 2.6666667
(1 2 2 3 3 3) - (3 3 3) - 3.5138888
(1 2 3 3 3 3) - (3 3 3 3) - 4.3333335
(1 3 3 3 3 3) - (3 3 3 3 3) - 5.1666665
(2 2 2 2 2 2) - (2 2 2 2 2 2) - 5.0
(2 2 2 2 2 3) - (2 2 2 2 2) - 4.1666665
(2 2 2 2 3 3) - (2 2 2 2) - 3.3333333
(2 2 2 3 3 3) - (2 2 2 3 3 3) - 5.0
(2 2 3 3 3 3) - (3 3 3 3) - 4.3333335
(2 3 3 3 3 3) - (3 3 3 3 3) - 5.1666665
(3 3 3 3 3 3) - (3 3 3 3 3 3) - 6.0
(1 1 1 1 1 6) - (1 1 1 1 1) - 3.1666667
(1 1 1 1 2 6) - (1 1 1 1) - 2.3333333
(1 1 1 1 3 6) - (1 1 1 1) - 2.3333333
(1 1 1 2 2 6) - (1 1 1) - 1.5231482
(1 1 1 2 3 6) - (1 1 1) - 1.5231482
(1 1 1 3 3 6) - (3 3) - 1.7523148
(1 1 2 2 2 6) - (2 2 2) - 2.5185184
(1 1 2 2 3 6) - (2 2) - 1.2507716
(1 1 2 3 3 6) - (3 3) - 1.7523148
(1 1 3 3 3 6) - (3 3 3) - 3.5138888
(1 2 2 2 2 6) - (2 2 2 2) - 3.3333333
(1 2 2 2 3 6) - (2 2 2) - 2.5185184
(1 2 2 3 3 6) - (3 3) - 1.7523148
(1 2 3 3 3 6) - (3 3 3) - 3.5138888
(1 3 3 3 3 6) - (3 3 3 3) - 4.3333335
(2 2 2 2 2 6) - (2 2 2 2 2) - 4.1666665
(2 2 2 2 3 6) - (2 2 2 2) - 3.3333333
(2 2 2 3 3 6) - (2 2 2 3 3) - 2.6666667
(2 2 3 3 3 6) - (3 3 3) - 3.5138888
(2 3 3 3 3 6) - (3 3 3 3) - 4.3333335
(3 3 3 3 3 6) - (3 3 3 3 3) - 5.1666665
(1 1 1 1 6 6) - (1 1 1 1) - 2.3333333
(1 1 1 2 6 6) - (1 1 1) - 1.5231482
(1 1 1 3 6 6) - (1 1 1) - 1.5231482
(1 1 2 2 6 6) - (2 2) - 1.2507716
(1 1 2 3 6 6) - (1 1) - 0.7492284
(1 1 3 3 6 6) - (3 3) - 1.7523148
(1 2 2 2 6 6) - (2 2 2) - 2.5185184
(1 2 2 3 6 6) - (2 2) - 1.2507716
(1 2 3 3 6 6) - (3 3) - 1.7523148
(1 3 3 3 6 6) - (3 3 3) - 3.5138888
(2 2 2 2 6 6) - (2 2 2 2) - 3.3333333
(2 2 2 3 6 6) - (2 2 2) - 2.5185184
(2 2 3 3 6 6) - (3 3) - 1.7523148
(2 3 3 3 6 6) - (3 3 3) - 3.5138888
(3 3 3 3 6 6) - (3 3 3 3) - 4.3333335
(1 1 1 6 6 6) - (1 1 1) - 1.5231482
(1 1 2 6 6 6) - (1 1) - 0.7492284
(1 1 3 6 6 6) - (1 1) - 0.7492284
(1 2 2 6 6 6) - (2 2) - 1.2507716
(1 2 3 6 6 6) - (3) - 0.74112654
(1 3 3 6 6 6) - (3 3) - 1.7523148
(2 2 2 6 6 6) - (2 2 2) - 2.5185184
(2 2 3 6 6 6) - (2 2) - 1.2507716
(2 3 3 6 6 6) - (3 3) - 1.7523148
(3 3 3 6 6 6) - (3 3 3) - 3.5138888
(1 1 6 6 6 6) - (1 1) - 0.7492284
(1 2 6 6 6 6) - (2) - 0.5803755
(1 3 6 6 6 6) - (3) - 0.74112654
(2 2 6 6 6 6) - (2 2) - 1.2507716
(2 3 6 6 6 6) - (3) - 0.74112654
(3 3 6 6 6 6) - (3 3) - 1.7523148
(1 6 6 6 6 6) - (1) - 0.41962448
(2 6 6 6 6 6) - (2) - 0.5803755
(3 6 6 6 6 6) - (3) - 0.74112654
(6 6 6 6 6 6) - () - 0.40187758
-
Simulations should be written as a sanity check on these numbers.
-
A min-max game tree could be produced using the final VP and claw values to get a feel for how a HU game should play out
-
A min-max game tree that plays out rerolls and therefore take outlying rolls into account.
The Lazy version doesn't work. My stack overflows. I'm not a laziness expert, so you might see a way to fix it.
Copyright © 2016 FIXME
Distributed under the Eclipse Public License either version 1.0 or (at your option) any later version.