brhfl.com

Finding the greatest Yahtzee score

I’ve been meaning to implement a way to incorporate style or script requirements into my posts using Hugo frontmatter. I’m not there yet, and before I get there, I need a test post that requires one or the other. I thought a little toy that lets one play a turn (three rolls) of Yahtzee, and then returns the highest possible score of the roll would be a fun and simple demonstration. Aside from small straights wigging me out a little (and I still have a nagging feeling this can be optimized), it was indeed simple1 to come up with an optimal score search. Fortunately, for a single-turn score, we don’t need to worry about a few scoring rules: bonus (joker) Yahtzees, the upper row bonus, nor chance. We could implement chance easily, but it really doesn’t make sense for single-turn scoring.

A Yahtzee will always be optimally scored as such, and is the highest possible score, so we should test for this first. It’s an easy test: how many unique faces are there? If 1, we’ve got us a Yahtzee. Straights are the next highest, and again should always be scored as such. Testing for sequences in an array can be done a number of fancy ways using hashes and the like, but our requirements are so limited that we can probably knock it out more easily than that. Ensuring that our dice are sorted, testing that the middle three are a sequence covers all large straights and most small straights. It fails on a roll like 1, 2, 2, 3, 4, but that’s okay. There are a number of ways to test for a large straight; I rather like matching my following small straight test, but check that both the highest two and the lowest two dice are one apart. A simpler test would be subtracting the lowest from the highest; if the result is 4, that’s a large straight. If we didn’t score a large straight, we should see if either the highest two or the lowest two are one apart; this will confirm a small straight in our current subset.

This is where I briefly got grumpy and started looking into tests involving folding, filtering, reducing the array… and I was just coming up with more frustration. I didn’t really want to perform additional tests to eliminate the 1, 2, 2, 3, 4 issue from above, but in the end I think this is a relatively clean way that seems to catch all remaining small straights: if the number of unique faces is 4 (so we have exactly one duplicate), and the highest die minus the lowest is 3, that should be a small straight. So our first set of tests knocks out small straights where every face is unique (1, 2, 3, 4, 6); this one covers those with a single duplicate. This wouldn’t really work elsewhere, our oddly specific and controlled conditions really do work in our favor.

Next we need to test for three of a kind. If we have at least three of a kind, we can narrow down a full house easily. Three of a kind test is simple since everything is sorted, just check if any of the three outer positions where a three of a kind can sit match. That is, test the lowest and center or the highest and center or the two dice on either side of center for equality. If this is true, do the same for the four-of-a kind positions – are the lowest and second highest equal or the highest and second lowest? A four of a kind scores the same as a three of a kind, so we shouldn’t need to do this. But eliminating fours of a kind makes the full house test very simple – given one triplet, a unique face count of two is a full house. A full house is not always ideally scored as such; 5, 5, 6, 6, 6 and even 4, 4, 6, 6, 6 both score higher than 25. So score it as whichever is higher – 25 or the sum of all dice.

Having eliminated the bottom row, we now just need to figure out which score of numbers is best. It will never be ones (two ones are beaten by a single three), so we start our count at 2 (1, 1, 2, 2, 3 is the only roll in which twos will win, but it’s still valid so we’d better account for it). Going through 2-6, we simply score them all and add each to a score array, ultimately returning the highest value in said array.

Javascript (which is something I avoid like the plague, so no style criticism):

function sum(dice) {
	return dice.reduce((x,y)=>Number(x)+Number(y));
	}
function flatten(dice) {
	return dice.filter((x,y,z)=>z.indexOf(x)==y);
	}
function numUniques(dice) {
	return flatten(dice).length;
	}
function bestScore(dice) {
	dice.sort();
	/*if (dice.every((x)=>x==dice[0])) return 50;*/
	if (numUniques(dice)==1) return 50; // yahtzee
	if (dice[3]-dice[2]==1 && dice[2]-dice[1]==1) { // first set of straight tests
		if (dice[4]-dice[3]==1 && dice[1]-dice[0]==1) return 40; // large
		if (dice[4]-dice[3]==1 || dice[1]-dice[0]==1) return 30; // some smalls
		}
	if (numUniques(dice)==4 && flatten(dice)[3]-dice[0]==3) return 30; // rest 
		// of the smalls
	if (dice[0]==dice[2] || dice[2]==dice[4] || dice[1]==dice[3]) { // 3 of a kind
		/*if (dice[1]==dice[2] && dice[2]==dice[3]) return sum(dice);*/
		if (dice[0]==dice[3] || dice[1]==dice[4]) return sum(dice); // 4 of a kind; 
			// only need to test for this to simplify full house
		if (numUniques(dice)==2) return Math.max(sum(dice),25); //full house (which 
			// may net fewer points than 3/kind)
		else return sum(dice); // score as 3/kind
		}
	var score=[];
	for (i=1;i<7;++i){ //top row
		score.push(i*(dice.filter((x)=>x==i).length));
		}
	return Math.max.apply(null,score);
	}

  1. Much simpler than building the interactive V8 shell from source, despite what everyone says. I guess if you’re invested in developing for Chrome or other Google apps, it makes sense. Otherwise, what a fucking pain. ↩︎