Saturday, November 8, 2008

Study of the game Zilch part 1

You know you're a math nerd when you analyze a game to determine the best strategy. Be forewarned, the following post is really math intense; abandon all hope of avoiding nerdhood ye who enter here...

I have been introduced to a wonderful game called Zilch on Kongregate. If you want to lose hours of your life, go to Kongregate and check out all of their cool flash games, all of which you can play for free. :) The reason I wanted to talk about Zilch is that it is a great game that illustrates some of the interesting corner cases of game theory. I will be breaking up this analysis into several segments in order to discuss different aspects of the game, and the process one could go through in order to come up with a winning strategy for the game. This first segment will discuss the scoring and expected value of a hand, and will end with an analysis of an interesting situation in the game that has an unexpected strategy.

Let's start with a quick summation of the rules. Players play in turns, and attempt to score points by rolling dice for a hand. Once one player gets to 10,000 points, the other player has one more turn in order to attempt to beat the crosser's score. Scoring for a hand works as follows: you roll 6 dice, and every turn you have to score something and either bank or roll. You score based on the following scoring rules:
• 1 one: 100 points
• 1 five: 50 points
• a set of three or more dice: 12.5*base*2^dice. The base is the die value in points or 10 points for a one. For example a set of 4 sixes, it scores 12.5*6*2^4=1200 points. 6 ones is the largest score in the game worth 8000 points.
• a long straight 1-6: 1500 points
• three pairs (not necessarily unique): 1500 points
• nothing: if a roll of 6 dice results in no scorable dice, then it scores 500 points instead.
After each roll you take dice off and score them, keeping the points in a "bank". You may score any of your dice that you want, but you must score at least 1 die or get a Zilch for the round, scoring 0 points. After scoring dice, you get the option to either roll again with the remaining dice or taking your points from the bank and ending your turn. This is called "banking" and it requires that you have at least 300 points in your bank. If you are lucky enough to score all your dice then you get all of your dice back and it constitutes a free roll, which can be repeated as many times you can manage to pull it off. If you are unlucky enough to zilch three times in a row, then you score -500 points (this does not stack).

After the first few playthroughs, some interesting strategies seem to jump off. Firstly, if you have a single die remaining, and you can bank, it's usually a good idea to do so, for the probability to zilch in that position is 2/3. If you have two zilches against you, then you want to bank at your first opportunity in order to avoid the zilch penalty. When scoring, it's not always the best thing to score everything available to you, especially in the case of 3 twos. Your daring is really more of a function of what your opponent's score is in relation to your own.

So what does it mean to know the perfect strategy for a game? A perfect strategy is to know based upon any game position the proper play to make that maximizes some quality of the game state. This quality is usually to win the game, but in the case of the online game there are also strategies to obtain some of the achievement badges, such as winning a game without zilching, playing a game with the least number of turns, or scoring over a certain value for each non-zilched play. At first I will be analyzing the basic question of best play to win the game.

Therefore, we need to start by defining the game state. Since we at first do not care how many turns it takes, or whether or not the win is zilch free, or any other qualities of the game other than winning, a lot of historical values can be discarded. The remaining qualities of the game break down as follows:
• Whose turn
• Opponent's score
• Your zilch run (number of consecutive zilches before this turn)
• Opponent's zilch run
• Current bank value
• Dice state
My approach to determining the proper strategy is similar to how blackjack was analyzed. I start off by determining a "book strategy" which is the proper strategy in a turn based on the state of the game and the dice. From there I'll want to come up with some ground rules that aggregate that strategy into a set number of rules. This will boil down into something like "double down on 11, or 10 if dealer's not showing an Ace".

I could approach this from an elegant mathematical angle, using clever reasoning to determine each step in the process. Instead I decided to brute force the numbers, and get the elegance later when summing up the results. My tool in this quest is Java. Later on I will see how much faster this would have been in a language like Haskell, where this kind of search is better structured.

I represent my dice as an integer array. I then write a function that evaluates a set of dice for the score you'd get if you took everything (no banking instituted yet). After writing some tests to assert that I was good, I then wrote a clumsy for loop to evaluate across all dice:
`int dice[]=new int[]{1,1,1,1,1,1};           int fullscore=0;           Map<Integer,Integer> scorecount=new TreeMap<Integer,Integer>();           for(dice[0]=1;dice[0]<=6;dice[0]++)                   for(dice[1]=1;dice[1]<=6;dice[1]++)                           for(dice[2]=1;dice[2]<=6;dice[2]++)                                   for(dice[3]=1;dice[3]<=6;dice[3]++)                                           for(dice[4]=1;dice[4]<=6;dice[4]++)                                                   for(dice[5]=1;dice[5]<=6;dice[5]++){                                                                int sc=calculateScore(dice);                                                                if(sc<300)continue;                                                                if(scorecount.containsKey(sc)){                                                                        scorecount.put(sc, scorecount.get(sc)+1);                                                           }else scorecount.put(sc, 1);                                                           fullscore+=sc;                                                   }           double avgscore=(double)fullscore/46656.0;           System.out.println("Average score:"+avgscore);           boolean medflag=false;           System.out.println("Breakdown:");           int ssf=0;           for(int x:scorecount.keySet()){                   ssf+=scorecount.get(x);                   System.out.print(x+":\t"+scorecount.get(x)+"\t"                                   +(double)scorecount.get(x)/466.56                                   + "\t" + ssf                                   + "\t" + (double)ssf/466.56);                   if(!medflag && ssf>=23328){                           medflag=true;                           System.out.println("<=== Median");                   }else System.out.println("");           }`

My goal here was to get the average and median scores from the first throw. This data would be useful later in understanding strategies and would allow me to develop the infrastructure needed to walk the state space of this game.

Results? You can execute the code yourself to get the score layouts. :) Here are the highlights. I get an average score from the first throw of 426.60. That's a lot of potential... what that tells me is that with average throws I should be able to score my 10,000 points in about 23 turns. The median of the first throw is 250 points, and your chances of having a bankable score at the start are 44.58%. If I only count bankable throws, and take worst case scenario of zilching otherwise, I get an average score of 341.78.

That told me a lot of info, but not everything I needed. I now wanted to evaluate based on the second and subsequent throws, meaning I'd have to evaluate with less dice. The idea of writing that horrendous for-loop structure was scary, so I decided to go a bit more functional. And man, Java didn't make it easy. :D

In order to evaluate across all dice of any number, I decided to stay with my int[] strategy. I started by writing a couple of generic interfaces:
`public class ZilchCalculations {    public interface DiceCalculation<X>{            public X evaluate(int[] dice);    }    public interface TreeCollate<X,Y>{            public X collate(X values, X nv);            public X ret(Y st);    }`

The first interface allowed me to make a calculation across dice. The second allowed me to collate that calculation across those dice combinations. Notice how I've abstracted the evaluation structure and the Collation structure. Essentially these interfaces will act as containers for function objects, much like a C# delegate structure. Next is to do the actual evaluation and collation:
`public static <X,Y> X acrossAllDice(int numdice,DiceCalculation<Y> eval,TreeCollate<X,Y> coll){            int[] dice=new int[numdice];            Arrays.fill(dice,-1);            return acrossDice(0,dice,eval,coll);    }    public static <X,Y> X acrossDice(int make,int[] dice,DiceCalculation<Y> eval, TreeCollate<X,Y> coll){            if(make<dice.length){                    X res=null;                    for(int d=1;d<=6;d++){                            dice[make]=d;                            if(d==1)res=acrossDice(make+1,dice,eval,coll);                            else res=coll.collate(res,acrossDice(make+1,dice,eval,coll));                    }                    return res;            }else return coll.ret(eval.evaluate(dice));    }`

This allows me to evaluate across all dice combinations for an arbitrary number of dice. The acrossAllDice function creates a holder array for the dice states, and recursion causes the numbers in dice to be updated in order. When I am at the root of the tree, I call the evaluate function in the DiceEvaluator to get my evaluation object, and then the TreeCollate's ret function to put that into a singleton collation object. It then continues to collate as it goes up the tree. I can easily wrap my scoring function in an evaluator:
`public static final DiceCalculation<Double> SCORE_CALC              =new DiceCalculation<Double>(){              public Double evaluate(int[] dice){return (double)calculateScore(dice);}      };`

and then my collation function for now will just sum the results:
`public static final TreeCollate<Double,Double> SUM_UP            =new TreeCollate<Double,Double>(){            public Double collate(Double values, Double nv){                    return values+nv;            }            public Double ret(Double x){return x;}    };`

Now to get the average score for 6 dice? acrossAllDice(6,SCORE_CALC,SUM_UP)/Math.pow(6.0, 6.0). For 5 dice it's just acrossAllDice(5,SCORE_CALC,SUM_UP)/Math.pow(6.0, 5). That seems like a lot of work just to be able to make a small change like that. Let's show the power of this approach. Say I want to collect all the scores into a list for stat evaluation:
`public static final TreeCollate<List<Double>,Double> COLLECT              =new TreeCollate<List<Double>,Double>(){              public List<Double> collate(List<Double> values,List<Double> nv){                      values.addAll(nv);                      return values;              }              public List<Double> ret(Double x){                      return Collections.singletonList(x);              }      };`

and change SUM_UP to COLLECT above to reap the benefits. Say I wanted to calculate the chances of zilching on a throw?
` public static final DiceCalculation<Double> ZILCH_CALC                        =new DiceCalculation<Double>(){                public Double evaluate(int[] dice){return calculateScore(dice)>0?0.0:1.0;}        };}`

and substitute ZILCH_CALC for SCORE_CALC. To get a tabluar evaluation:
`System.out.println("Number of dice\tAverage Score\tZilch Prob.");                for(int ndice=1;ndice<=6;ndice++){                        System.out.println(ndice+"\t"                                                        +(acrossAllDice(ndice,SCORE_CALC,SUM_UP)/Math.pow(6.0, ndice))+"\t"                                                        +(acrossAllDice(ndice,ZILCH_CALC,SUM_UP)/Math.pow(6.0, ndice))+"\t");                }`

which gives me the wonderful table:

Number of dice Average Score Zilch Prob.
1 25.0 0.6666666666666666
2 50.0 0.4444444444444444
3 86.80555555555556 0.2777777777777778
4 143.5185185185185 0.1574074074074074
5 225.7908950617284 0.07716049382716049
6 426.60108024691357 0.0

This table explains a great generic rule that's originally counterintuitive. Say you're under two zilches and you rolled 2-2-2-5-3-4, a rather unpleasant roll. Do you score the 5, the 3 twos, or both? If you look at the table, it'll make sense that you score only the 5. Scoring the 5 gives you the possibility of scoring an average of 225.79 points over those last 5 dice, meaning your average score is 275.79 (still not that good) but your chances for zilching are only 7%. If you take the three 2s, you do have 200 points, and your average is slightly higher now (286.81) but you've now quadrupled your chances to zilch (at ~28%). If you take both, your average is at 300, but your chances to zilch are now 4 in 9, an unhealthy prospect. It makes sense to reroll as much of this crappy roll as you can.

However, this isn't a soundproof argument for maximizing your score, only a good hunch based on some statistical calculations. The soundproof argument will come from calculating across the entire space, and that will happen in the next installment.

Bartolomew said...

Loved your post and can't wait for the next installment!

In fact i was just about to find some spare time to implement the score-evaluation code myself when i saw your post linked from the game page.

Great work so far! Kept me from wasting more time on Zilch than i already did ;)

Gaby said...

Awesome, I had no idea that Zilch would generate this kind of response. Keep up the good work!

Thanks for the kind words. And it's looking like a lot more work than I realized. :D But I'm thrilled at the prospect of flexing my math muscles, so it's a labor of love.

Anonymous said...

this game is so one sided it is fucking terrible. the maker should have coded it better so that the computer doesn't get all the good rolls.

Patrick said...

Does the estimated score per dice rolled account for the roll again if you use all six dice? I understand the odds of zilching on one die are 2/3rds but shouldn't the payoff matrix (even in its approximate form) include the 6 dice payoff?

I.e. if you roll one die you a 1/3 chance of scoring, but if you do score you get to roll again and get an additional average 426.60?

Or is this what the next part of the study will cover? Sorry if I'm being dense.

Birdseed said...

Great results so far!

One thing that needs to be taken into account is the amount you're risking. I mean, if you have a thousand points on the board you'll want to bank it straight away, even if there's a good chance you won't zilch the next round.

What's important in many considerations is not what you stand to gain but what you stand to lose in relation to it - for instance, if you've got a very low score (say, 350 or so) and the opportunity to roll the sixth die, I'd intuitively say you'd do it even if it's just a 1/3 chance because the potential gain is so high.

@anonymous: It only feels one-sided. If you mimic the realist's strategy, you'll win against it about 50% of the time and 80% against everyone else. Sure you'll have bad luck streaks and it'll feel biased, but that's what probability is all about.

@patrick, birdseed: I haven't completed the full analysis... and that's why the concerns you mentioned are not taken into account. This first step is solely a judgment of the first roll (without choosing dice, without rerolling). This is why I don't consider the reroll for six dice and why I don't consider the utility implications of the amount you already have banked. The full analysis will take all of that into account, although it is taking a lot longer than I thought, searching through so many cases.

dt said...

In that last example, 2-2-2-5-3-4, wouldn't it make the most sense to score both the three 2's and the 5, then bank straight away? Then you have both the highest average score and 0 chance of zilching.

Anonymous said...

In the case of having 2,2,2,5,n1,n2
where the n's are not 1,2,or 5.. you would bank the set of 2s and the five, you would only have 250 points. three 2's gives 200 points and the five gives you only 50.

BioHazzarDofUO

Anonymous said...

A quick second run might just involve adding in the expected value of a reroll (was it about 426?) at 1-p(zilch) right? In other words, just considering the added potential value of getting back to a position with six dice. Obviously there is a long way to go from there, including considering p(zilch), relative scores, etc. I didn't think it'd be so hard to get expected values for rolls: just compute the expected value of a zilch (which will vary depending on previous zilches as well as the points you could potentially bank) and compare it to the expected value of another roll, and you should know probablistically speaking what's the optimal course of action, no?

Johnny said...

What perplexes me the most are the apparent inconsistencies in the realist's strategy. Sometimes it stops with 300 points and 2 dice to roll. Sometimes it decides to roll 1 die when 1000 or more could have been banked. It doesn't seem to be related to relative scores, either, i.e. it takes the apparently foolish gamble even when it doesn't need to. Curious!

These are the kinds of posts I'd love to see more of across the board in flash dev... the 'why's and the process behind it.. loved the post man! keep it up!

atanner53 said...

I teach high school statistics and once I found Zilch, I decided to use it for a semester probability project.

I wrote a C# program to calculate the probabilities. After I wrote it, Gaby sent me here. I got the same results as you did for 1-5 dice. But my average for 6 dice is 426.2796. When subtracted from you average and multiplied by 46656, my total is 15000 too low.

Could you publish your calculateScore method? Thanks, I want to find the bug in my code and my thinking.

Thanks.

Acrisius said...

My average for first roll (6 dice) is 427.43699. My logic:
a) determine if a "special" grouping happened (3 pairs or straight)
b) calculate any 3+ groupings and add any single or double 1s & 5s
c) if both a & b come up zero (6-dice zilch), count 500.
d) take the maximum from a,b,c. Could be anywhere from 50 - 8000.

NOTE: don't forget that 4-of-a-kind plus a pair counts as 3 pairs! So, 2-2-2-2-5-5 counts 1500 rather than (400+100).

Anonymous said...

Not that useful so far :(

Can someone of you lovely nerds please answer some of my questions?

1) More wonderful table: number of dice, chance to zilch, chance to score something but not a free roll, average points gained when scoring something but not a free roll, chance to get a free roll, average points when you score a free roll.

2) What are the best chices for a strategy "take the money and run", i mean, suppose you bank whenever you can and don't have a free roll, what is better to roll when you cannot bank?

3) Bank or roll? You can bank X or roll Y dice, what is best? The more wonderful table may help. (maybe it is usefull to suppose that you apply take the money and run above some amount of points, and that adter some consecutive free rolls you are forced to bank without taking a new free roll).

4)Minimize the number of turns you expect to reach 10,000.

The case, you score 2000 without taking a free roll, or 1500 with free roll can screw up the more wonderful table. just consider it only free roll, or make 2 tables.

Albert said...

Confirmed that Acrisius' average is correct.

You get:

422.26 - If you don't consider quad+pair to be 3 pairs. atanner this is probably what you got.
426.60 - If you always consider quad+pair to be 3 pairs (sub-optimal)
427.43699 - If you take the better scoring of quad+pair vs 3 pairs.

dcoelho1968@hotmail.com said...

In the rules you correctly said:
"Once one player gets to 10,000 points, the other player has one more turn in order to attempt to beat the crosser's score."
I've started a discussion with Gaby (the maker) on this rule. It is not fair in my humble opinion.
For a game like this (it's the same with billiards, libre game) all players should have the same amount of turns. That is the premise. So, no extra turns for a starting player over a follower already reaching 10,000.
So my argument is not on your good work, but on the (un)fairness in the game itself. See my point? What are your thoughts?
David

Stef said...

Zilch has dedicated fans! It's also known as Farkle: There are many strategies published related to this game.

Anonymous said...

the code does not include how u calculate the score. u only showed us "calculateScore". so i can't be sure whether u somehow did manage to calculate the average score, and whether it is correct.
About the zilch prob, they all can be calculated with high school math, so it remains possible that you're not using your code. The easy ones are 4/6 one die, (4/6)^2 for two, 0 for six, (4/6)^3 - 4/(6^3) for three, then using "tree diagrams" to calculate for four and five. On a side note, i want to point out that since it is true that the zilch prob is so low, players who are unfamiliar with the math behind it will assume the computer is cheating.
And you're right about statistical treatment. The mean value is not good, the median score is more useful! so we need the probability function to show us more than the mean. Yes we can use the distribution of the probabilities to really predict what is the best move, but that would be too complicated. Why is everyone using your mean value?! It makes no sense to use mean! i'm very concerned.
About how to calculate the score if you rolled the last die and got a free roll, we can use eigenvalue functions, like in google PageRank search algorithm and in genetics, to explain why the ratios of various gene groups tends towards a steady value.
@Johnny: About the Realist strategy, i've read on the game coder's blog, it does say the strategy takes into account the current total score. But anyway, i still believe that any strategy shouldn't take into account the past scores. Past rolls do not affect subsequent ones. Don't be afraid when your score is lower than the computer, treat them like sunk costs. But that's jus me.