Letter Shuffling Algorithms

All discussion relevant to Countdown that is not too spoilerific. New members: come here first to introduce yourself. We don't bite, or at least rarely.
Post Reply
JackHurst
Series 63 Champion
Posts: 1982
Joined: Tue Jan 20, 2009 8:40 pm

Letter Shuffling Algorithms

Post by JackHurst »

I have been experimenting with different ways to generate letters selections and seeing how it affects the average length of the best available word in a letters selection

  • 10000 rounds generated for each algorithm and maxes from those rounds analyzed
  • Rounds are picked to be 40% 3V 40% 4V and 20% 5V
  • Letters distribution is:

Code: Select all

                "B": 2
                "C": 2
                "D": 6
                "F": 2
                "G": 3
                "H": 2
                "J": 1
                "K": 1
                "L": 5
                "M": 4
                "N": 8
                "P": 4
                "Q": 1
                "R": 9
                "S": 9
                "T": 9
                "V": 1
                "W": 1
                "X": 1
                "Y": 1
                "Z": 1
                "A": 15
                "E": 21
	        "I": 13
	        "O": 13
	        "U": 5
Algorithm 1: Deduplication vs last letter
If the the next letter in the stack matches the last latter from that stack (counting consonant and vowel stack separately), then with 70% probability, instead of giving out that letter, repeat the process. Stack refreshes when it becomes empty.

Code: Select all

Total of 79850.0 avg max 7.985

Max of 4: 8
Max of 5: 169
Max of 6: 1367
Max of 7: 4037
Max of 8: 3703
Max of 9: 716

Total of 76169.0 distinct letters avg 7.6169 distinct letters per selection
Algorithm 2: Deduplication vs last letter + early refill
Same as above, but clear the stack when down to the last 5, with the idea being that the above algorithm gives you too many duplicates at the end of the stack.

Code: Select all

Total of 79916.0 avg 7.9916

Max of 4: 4
Max of 5: 157
Max of 6: 1359
Max of 7: 3989
Max of 8: 3780
Max of 9: 711

Total of 76353.0 distinct letters avg 7.6353 distinct letters per selection
Algorithm 3: Deduplication vs last 2 letters + early refill
As above, but apply the deduplication rule if either of the last TWO letters in the stack are the same as the candidate letter

Code: Select all

Total of 81583.0 avg 8.1583

Max of 4: 4
Max of 5: 121
Max of 6: 1095
Max of 7: 3908
Max of 8: 4066
Max of 9: 806

Total of 78818.0 distinct letters avg 7.8818 distinct letters per selection
Algorithm 4: Deduplication vs last 3 letters + early refill
As above, but apply the deduplication rule if either of the last THREE letters in the stack are the same as the candidate letter

Code: Select all

Total of 81940.0 avg 8.194

Max of 4: 4	
Max of 5: 109
Max of 6: 1055
Max of 7: 3777
Max of 8: 4238
Max of 9: 817

Total of 79782.0 distinct letters avg 7.9782 distinct letters per selection
Algorithm 5: No deduplication
Don't do anything to remove duplicates. (Similar to how co-events with the board game are played, if you assume players can shuffle cards adequately)

Code: Select all

Total of 76740.0 avg 7.674

Max of 4: 17
Max of 5: 261
Max of 6: 1693
Max of 7: 4263
Max of 8: 3242
Max of 9: 524

Total of 73016.0 distinct letters avg 7.3016 per selection

Conclusion
  • Reducing the number of duplicates in the selection appears to increase the max, which I am sure was already a well known thing.
  • I'm not aware of the avg letters max on the show over recent years, so it would be interesting to see that and how it compares to the baseline 7.3 score per letters selection with no shuffling. if anybody as that data, hit me up!
  • Over an Octorun you'd expect the available max to increase by 41.6 if you compare the harshest algorithm (number 5) with the nicest algorithm (algorithm 4)
Gavin Chipper
Post-apocalypse
Posts: 13194
Joined: Mon Jan 21, 2008 10:37 pm

Re: Letter Shuffling Algorithms

Post by Gavin Chipper »

JackHurst wrote: Mon Jul 13, 2020 12:09 pm
Algorithm 1: Deduplication vs last letter
If the the next letter in the stack matches the last latter from that stack (counting consonant and vowel stack separately), then with 70% probability, instead of giving out that letter, repeat the process. Stack refreshes when it becomes empty.
By the last letter, do you mean the immediately previous letter? (As opposed to the letter on the bottom of the pack.) What do you do with the letter if you don't use it? And when you say "repeat the process" you mean go to the next letter along and do the 70% trick? At least the word "if" has appeared at the start of this since I last looked, so it's a little bit less gobbledygook now!
JackHurst wrote: Mon Jul 13, 2020 12:09 pm
Algorithm 2: Deduplication vs last letter + early refill
Same as above, but clear the stack when down to the last 5, with the idea being that the above algorithm gives you too many duplicates at the end of the stack.
Should it? I don't really see the intuition behind it.
User avatar
Charlie Reams
Site Admin
Posts: 9494
Joined: Fri Jan 11, 2008 2:33 pm
Location: Cambridge
Contact:

Re: Letter Shuffling Algorithms

Post by Charlie Reams »

I would be interested to see how these compare with the scores on the show (not just mean of the max but the whole distribution). The algorithm on apterous was based on a conversation with the person who had the job of semi-shuffling the tiles about how she did it, but obviously there's a fairly substantial gap between theory and practice there.
Paul Anderson
Enthusiast
Posts: 300
Joined: Tue Dec 10, 2019 2:18 pm

Re: Letter Shuffling Algorithms

Post by Paul Anderson »

Apto feels like a very similar distribution when compared to the show. Perhaps not on a Mocktorun, but on discreet games, yeah
JackHurst
Series 63 Champion
Posts: 1982
Joined: Tue Jan 20, 2009 8:40 pm

Re: Letter Shuffling Algorithms

Post by JackHurst »

Something I find truly astounding when looking at the stats on average maxes with these algorithms is looking at Octorun maxes:


Assuming all numbers rounds are solvable (as an upper bound), you'd have 50 pts per games available in numbers and conundrums rounds, so that's 400 pts per Octorun. Then under the most generous algorithm below you'd have:

8.194*80 = 655.52pts available in letters rounds
So that's 1055.52 pts available on average in a Octorun.
Elliott Mellor's 1061 Octorun means he exceeded the AVERAGE available max by at least 5.48pts.

1) That's absolutely mad and yet again shows how crazily good his Octorun was
2) Also makes me think the best Algorithm I can come up with for shuffling the letters still isn't as good as they do it on the show! What's the secret sauce Countdown Team?
Dave Preece
Devotee
Posts: 621
Joined: Thu Feb 21, 2013 11:50 pm

Re: Letter Shuffling Algorithms

Post by Dave Preece »

They obviously slightly hand pick it?
Fiona T
Kiloposter
Posts: 1441
Joined: Mon Mar 18, 2019 12:54 pm

Re: Letter Shuffling Algorithms

Post by Fiona T »

Bumping this - the tool that was used for hosting the finals yesterday implemented "algorithm 2" as outlined by Jack (although with 9 or 15 rounders (code bugs excepted!) we're never going to get near the end of the pack so algorithm 1 is probably fine!) I think it felt about right - there were a few awkward rounds, but with only 5 vowels to choose from you'd expect that, and I don't think those horrible selections were more frequent than you'd get on apterous. Those rounds can be the most challenging and are where the players who really know their stuff stand out.
User avatar
Graeme Cole
Series 65 Champion
Posts: 2024
Joined: Tue Jul 06, 2010 9:59 pm

Re: Letter Shuffling Algorithms

Post by Graeme Cole »

Fiona T wrote: Sun Nov 26, 2023 4:53 pm Bumping this - the tool that was used for hosting the finals yesterday implemented "algorithm 2" as outlined by Jack (although with 9 or 15 rounders (code bugs excepted!) we're never going to get near the end of the pack so algorithm 1 is probably fine!) I think it felt about right - there were a few awkward rounds, but with only 5 vowels to choose from you'd expect that, and I don't think those horrible selections were more frequent than you'd get on apterous. Those rounds can be the most challenging and are where the players who really know their stuff stand out.
Yes, very much this. I thought there was nothing generally wrong with the selections.

The occasional difficult selection shouldn't be seen as a negative. Tackling the more difficult selections is just as much part of the game as taking advantage of the more "promising" selections, and arguably more so. What requires more effort: winning a round by finding QUIB, GIBE or IBEX from BEXIUIGIQ, or taking one look at SLTIOEADN and automatically writing down DELATIONS?

If you dedupe it too much, the letters become predictable, and the high-probability nines become even higher-probability, which I think tips the balance even further in favour of the strongest players at the expense of those lower down the ratings ladder.
User avatar
Mark Deeks
Fanatic
Posts: 2442
Joined: Tue Jul 12, 2011 3:15 am

Re: Letter Shuffling Algorithms

Post by Mark Deeks »

Awkward rounds are the best rounds, anyway. Actual anagramming ability rather than memory tests.
Eoin Monaghan wrote:
He may not be liked on here, but you have to give some credit to Mark
Gavin Chipper
Post-apocalypse
Posts: 13194
Joined: Mon Jan 21, 2008 10:37 pm

Re: Letter Shuffling Algorithms

Post by Gavin Chipper »

Agreed - there's no reason selections have to always be "nice".
JackHurst
Series 63 Champion
Posts: 1982
Joined: Tue Jan 20, 2009 8:40 pm

Re: Letter Shuffling Algorithms

Post by JackHurst »

Graeme Cole wrote: Sun Nov 26, 2023 5:47 pm
Fiona T wrote: Sun Nov 26, 2023 4:53 pm Bumping this - the tool that was used for hosting the finals yesterday implemented "algorithm 2" as outlined by Jack (although with 9 or 15 rounders (code bugs excepted!) we're never going to get near the end of the pack so algorithm 1 is probably fine!) I think it felt about right - there were a few awkward rounds, but with only 5 vowels to choose from you'd expect that, and I don't think those horrible selections were more frequent than you'd get on apterous. Those rounds can be the most challenging and are where the players who really know their stuff stand out.
Yes, very much this. I thought there was nothing generally wrong with the selections.

The occasional difficult selection shouldn't be seen as a negative. Tackling the more difficult selections is just as much part of the game as taking advantage of the more "promising" selections, and arguably more so. What requires more effort: winning a round by finding QUIB, GIBE or IBEX from BEXIUIGIQ, or taking one look at SLTIOEADN and automatically writing down DELATIONS?

If you dedupe it too much, the letters become predictable, and the high-probability nines become even higher-probability, which I think tips the balance even further in favour of the strongest players at the expense of those lower down the ratings ladder.
100% agree.
Mark Deeks wrote: Sun Nov 26, 2023 6:14 pm Awkward rounds are the best rounds, anyway. Actual anagramming ability rather than memory tests.
I'd argue awkward rounds can also go the opposite way. PATACA ALAMEDA and NEOTENE all came up as darrens in awkward selections with very few distinct letters. IMO these are darrenic maxes that reward the "memory test" contingent more than the "anagramming ability" contingent.
User avatar
Ian Volante
Postmaster General
Posts: 3952
Joined: Wed Sep 03, 2008 8:15 pm
Location: Edinburgh
Contact:

Re: Letter Shuffling Algorithms

Post by Ian Volante »

Mark Deeks wrote: Sun Nov 26, 2023 6:14 pm Awkward rounds are the best rounds, anyway. Actual anagramming ability rather than memory tests.
I'm still smug about a Co-event final where I spotted ARCHAEAE (or was it ARCHAEAN?) and neither finalist did. So yes.
meles meles meles meles meles meles meles meles meles meles meles meles meles meles meles meles
User avatar
Mark Deeks
Fanatic
Posts: 2442
Joined: Tue Jul 12, 2011 3:15 am

Re: Letter Shuffling Algorithms

Post by Mark Deeks »

I was sitting next to you at the time and I also remember your smugness. What a moment.
Eoin Monaghan wrote:
He may not be liked on here, but you have to give some credit to Mark
JackHurst
Series 63 Champion
Posts: 1982
Joined: Tue Jan 20, 2009 8:40 pm

Re: Letter Shuffling Algorithms

Post by JackHurst »

Mark Deeks wrote: Mon Nov 27, 2023 3:23 pm I was sitting next to you at the time and I also remember your smugness. What a moment.
Did Ian give you A EARACHE?
JackHurst
Series 63 Champion
Posts: 1982
Joined: Tue Jan 20, 2009 8:40 pm

Re: Letter Shuffling Algorithms

Post by JackHurst »

BTW, something which I added a long time ago, but since the original post is factional letters to the packs. The motivation is that there are a couple of letters where 1 in the pack seems like a shame, but 2 every time would be annoying. So when the Consonant stack is made, three of the letters are chosen from separate pots of 5:

Code: Select all

listOf("B", "B", "M", "M", "K").random()
listOf("D", "D", "C", "C", "C").random()
listOf("T", "T", "V", "Y", "W").random()
So in addition to the fixed W you always get, theres a 20% chance each game that there will be a second W in the pack, giving the overall affect of 1.2Ws in the pack. Likewise for K and V.
Fiona T
Kiloposter
Posts: 1441
Joined: Mon Mar 18, 2019 12:54 pm

Re: Letter Shuffling Algorithms

Post by Fiona T »

JackHurst wrote: Thu Nov 30, 2023 7:48 pm BTW, something which I added a long time ago, but since the original post is factional letters to the packs. The motivation is that there are a couple of letters where 1 in the pack seems like a shame, but 2 every time would be annoying. So when the Consonant stack is made, three of the letters are chosen from separate pots of 5:

Code: Select all

listOf("B", "B", "M", "M", "K").random()
listOf("D", "D", "C", "C", "C").random()
listOf("T", "T", "V", "Y", "W").random()
So in addition to the fixed W you always get, theres a 20% chance each game that there will be a second W in the pack, giving the overall affect of 1.2Ws in the pack. Likewise for K and V.
This is nice
Post Reply