Computerphile - Brute Forcing the Countdown Numbers Game

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
User avatar
Graeme Cole
Series 65 Champion
Posts: 1761
Joined: Tue Jul 06, 2010 9:59 pm

Computerphile - Brute Forcing the Countdown Numbers Game

Post by Graeme Cole » Sat Dec 19, 2020 2:40 pm

Published yesterday: an interesting new Computerphile video about the Countdown numbers game, and a method of generating every possible solution using Reverse Polish Notation.

Analysis of this kind has been done on this forum before, but one thing that I hadn't realised was that even targets are statistically significantly easier to achieve than odd targets. This seems obvious now (you can make an even number with odd numbers but you can't make an odd number with evens unless they're the right evens to do a division), I just hadn't thought of it until now.

User avatar
Jon O'Neill
Ginger Ninja
Posts: 4367
Joined: Tue Jan 22, 2008 12:45 am
Location: London, UK

Re: Computerphile - Brute Forcing the Countdown Numbers Game

Post by Jon O'Neill » Sat Dec 19, 2020 7:49 pm

I did see this.

Surely what he does here pales in sophistication to what you did for you solver Graeme? And especially what Charlie did for the apterous solver, which presumably has all spoilage numbers attacks solved...

User avatar
Graeme Cole
Series 65 Champion
Posts: 1761
Joined: Tue Jul 06, 2010 9:59 pm

Re: Computerphile - Brute Forcing the Countdown Numbers Game

Post by Graeme Cole » Sun Dec 20, 2020 11:25 am

My solver doesn't have anything precomputed - when you put in a selection, it works out all the expressions you can make from that selection (by representing each expression of N numbers as a tree, and combining them with the remaining numbers to make (N+1)-number expressions), and therefore what targets are achievable.

The Computerphile video is about enumerating every mathematical expression you can possibly make from any six numbers. Obviously this would give you a significant number of expressions which aren't legal in Countdown (reaching a negative number, divisions that don't produce an integer, etc), so presumably they eliminated those, but they don't say if there were any shortcuts taken, such as not bothering with 4+3 if you already have 3+4. My solver puts the elements of every expression in a defined order (basically this, although some minor details might have changed) and discards trees that look the same as others, thereby eliminating trivial rearrangements of the same solution and giving itself less work to do when it comes to combining those trees to form larger expressions.

User avatar
Charlie Reams
Site Admin
Posts: 9473
Joined: Fri Jan 11, 2008 2:33 pm
Location: Cambridge
Contact:

Re: Computerphile - Brute Forcing the Countdown Numbers Game

Post by Charlie Reams » Sun Dec 20, 2020 3:29 pm

Yep, apterous also uses a "backward" solver (given a target and working numbers, find the method) rather than a forward calculation of every possible number that can be made. However the answers are computed in advance and stored, in order to solve the problem from olden-days apterous where, for more difficult variants, the solver couldn't always find the solution inside 30 seconds. So we do have an increasingly comprehensive database of solutions for all variants.

One fun side-effect of that is that we can find the rounds that the solver had the hardest time solving. I'm not sure this correlates much with human-perceptible difficulty (the solver is not well-optimized for some variants), but in case anyone is interested here are the 10 "hardest" rounds in apterous history, according to time taken to find a solution. All ten are Hyper Lockdown, so the last number in the selection must be used:

150, 2, 3, 4, 6, 2, 6, 1 -> 7843
8, 3, 10, 2, 2, 2, 6, 6 -> 4589
9, 3, 2, 9, 9, 5, 3, 1 -> 9502
1, 9, 9, 4, 1, 9, 4, 2 -> 2743
200, 100, 8, 8, 10, 4, 10, 4 -> 7013
2, 2, 8, 4, 10, 7, 4, 1 -> 5276
6, 1, 1, 5, 2, 6, 2, 10 -> 6844
7, 6, 10, 2, 4, 2, 2, 5 -> 6338
6, 1, 6, 5, 8, 1, 8, 2 -> 7195
9, 4, 10, 10, 4, 9, 2, 1 -> 9019

These all took over 30 minutes for the solver! But two players (Edward Ashcroft and Adam Dexter) actually managed to solve one within 30 seconds, which is very impressive.

JackHurst
Series 63 Champion
Posts: 1506
Joined: Tue Jan 20, 2009 8:40 pm
Location: Leics

Re: Computerphile - Brute Forcing the Countdown Numbers Game

Post by JackHurst » Sun Dec 20, 2020 5:42 pm

Charlie Reams wrote:
Sun Dec 20, 2020 3:29 pm
Yep, apterous also uses a "backward" solver (given a target and working numbers, find the method) rather than a forward calculation of every possible number that can be made. However the answers are computed in advance and stored, in order to solve the problem from olden-days apterous where, for more difficult variants, the solver couldn't always find the solution inside 30 seconds. So we do have an increasingly comprehensive database of solutions for all variants.

One fun side-effect of that is that we can find the rounds that the solver had the hardest time solving. I'm not sure this correlates much with human-perceptible difficulty (the solver is not well-optimized for some variants), but in case anyone is interested here are the 10 "hardest" rounds in apterous history, according to time taken to find a solution. All ten are Hyper Lockdown, so the last number in the selection must be used:

150, 2, 3, 4, 6, 2, 6, 1 -> 7843
8, 3, 10, 2, 2, 2, 6, 6 -> 4589
9, 3, 2, 9, 9, 5, 3, 1 -> 9502
1, 9, 9, 4, 1, 9, 4, 2 -> 2743
200, 100, 8, 8, 10, 4, 10, 4 -> 7013
2, 2, 8, 4, 10, 7, 4, 1 -> 5276
6, 1, 1, 5, 2, 6, 2, 10 -> 6844
7, 6, 10, 2, 4, 2, 2, 5 -> 6338
6, 1, 6, 5, 8, 1, 8, 2 -> 7195
9, 4, 10, 10, 4, 9, 2, 1 -> 9019

These all took over 30 minutes for the solver! But two players (Edward Ashcroft and Adam Dexter) actually managed to solve one within 30 seconds, which is very impressive.
Very interesting! What about you algorithm makes HyperLock harder for the solver than normal Hyper? In my head, intuitively adding a constraint that a specific numbers has to be included in the solution would mean fewer possibilities to iterate over, so a quicker solve.

Also, I'd be interested to hear more about how the "backward" solver works. Does this mean if Apterous faces a certain numbers round, it will check a database to see if it has solved an equivalent round before, and if so, it will use that historical solution, and otherwise it will tyr to do it on the fly in 30s? Also what data are you logging into that database? It sounds like you might be logging how long it took the solver which is cool. Any other info? Also how does apterous deal with multiple numbers rounds needing to be solved at the same time? Does it put them in a queue or do them on separate threads? Are there any edge cases you know about where you could have a bug if two players face the same round at the same time and it hasn't been seen by apterous before?

JackHurst
Series 63 Champion
Posts: 1506
Joined: Tue Jan 20, 2009 8:40 pm
Location: Leics

Re: Computerphile - Brute Forcing the Countdown Numbers Game

Post by JackHurst » Sun Dec 20, 2020 5:43 pm

Graeme Cole wrote:
Sat Dec 19, 2020 2:40 pm
Published yesterday: an interesting new Computerphile video about the Countdown numbers game, and a method of generating every possible solution using Reverse Polish Notation.

Analysis of this kind has been done on this forum before, but one thing that I hadn't realised was that even targets are statistically significantly easier to achieve than odd targets. This seems obvious now (you can make an even number with odd numbers but you can't make an odd number with evens unless they're the right evens to do a division), I just hadn't thought of it until now.
Nice video! I hope they do one about letters solver!

User avatar
Charlie Reams
Site Admin
Posts: 9473
Joined: Fri Jan 11, 2008 2:33 pm
Location: Cambridge
Contact:

Re: Computerphile - Brute Forcing the Countdown Numbers Game

Post by Charlie Reams » Tue Dec 22, 2020 12:12 pm

JackHurst wrote:
Sun Dec 20, 2020 5:42 pm
Very interesting! What about you algorithm makes HyperLock harder for the solver than normal Hyper? In my head, intuitively adding a constraint that a specific numbers has to be included in the solution would mean fewer possibilities to iterate over, so a quicker solve.
Yeah, that's a reasonable intuition, but there's a few other factors in the other direction that seem to outweigh it:
  • The solver stops as soon as it finds a solution, and the extra constraint greatly reduces the number of possible solutions, so on average we have to search for longer to find the first one.
  • The solver is designed to always find the shortest solution, but a lot of Hyperlock solutions are quite long -- so say the shortest solution is six steps, the solver won't accept that until it's checked every possible 5-step solution first (including many things that are clearly very unlikely to work). So that's a lot of overhead.
  • The solver just doesn't know any of the obvious observations about Lockdown that a human would use. For example, if the Locked number is a 1 then you can basically ignore the Locked-ness, because you can always do x1 at the end of any other solution. And in general it's not very smart about when to try to use up the locked number, and I don't have any good intuition on that myself. (Would be interested to hear from some of the stronger Lockdown players how they do this.)
All of this could be improved with some effort but Lockdown isn't played that much so it hasn't been worth the time so far.
Also, I'd be interested to hear more about how the "backward" solver works. Does this mean if Apterous faces a certain numbers round, it will check a database to see if it has solved an equivalent round before, and if so, it will use that historical solution, and otherwise it will tyr to do it on the fly in 30s? Also what data are you logging into that database? It sounds like you might be logging how long it took the solver which is cool. Any other info? Also how does apterous deal with multiple numbers rounds needing to be solved at the same time? Does it put them in a queue or do them on separate threads? Are there any edge cases you know about where you could have a bug if two players face the same round at the same time and it hasn't been seen by apterous before?
Not giving away all my trade secrets that easily! :lol:

User avatar
Rhys Benjamin
Fanatic
Posts: 2366
Joined: Thu Sep 09, 2010 4:28 pm
Location: Down in the tube station at midnight

Re: Computerphile - Brute Forcing the Countdown Numbers Game

Post by Rhys Benjamin » Tue Dec 22, 2020 1:14 pm

I’m guessing it’s better than it used to be, though? There’s that famous game where Matthew Tassier got a max +3 on a bullet hyperlock NA from 2013 but I haven’t seen anything like that in “the wild” since?
The forum's resident JAILBAKER, who has SPONDERED several times...

User avatar
Charlie Reams
Site Admin
Posts: 9473
Joined: Fri Jan 11, 2008 2:33 pm
Location: Cambridge
Contact:

Re: Computerphile - Brute Forcing the Countdown Numbers Game

Post by Charlie Reams » Tue Dec 22, 2020 5:14 pm

Rhys Benjamin wrote:
Tue Dec 22, 2020 1:14 pm
I’m guessing it’s better than it used to be, though? There’s that famous game where Matthew Tassier got a max +3 on a bullet hyperlock NA from 2013 but I haven’t seen anything like that in “the wild” since?
Correct, and the additional power of the new server also helps. I don't think it's possible to beat the solver now and it hasn't happened for many years. (Obviously I could cheat on that by recycling the player's solution if it beats the solver's max, but I've never needed to do that.)

It's worth keeping in mind though that the solver is playing a slightly different game to the human player. The solver needs to find the best possible solution in the fewest possible steps, whereas the human player is trying to find any solution that hits or approaches the target within the 30 seconds. If you really wanted to create a program that has the same objective as the human player, I expect it would be pretty easy to make something better than any human. (Not sure if this is a helpful analogy, but it's the difference between creating a chess computer that can beat Kasparov over the board versus creating a chess computer than can analyze his games offline and find the theoretical best moves; the two programs are similar but they wouldn't necessarily be good at solving the other program's task.)

Gavin Chipper
Post-apocalypse
Posts: 10168
Joined: Mon Jan 21, 2008 10:37 pm

Re: Computerphile - Brute Forcing the Countdown Numbers Game

Post by Gavin Chipper » Tue Dec 22, 2020 9:42 pm

Rhys Benjamin wrote:
Tue Dec 22, 2020 1:14 pm
I’m guessing it’s better than it used to be, though? There’s that famous game where Matthew Tassier got a max +3 on a bullet hyperlock NA from 2013 but I haven’t seen anything like that in “the wild” since?
This has happened multiple times. That game wasn't rare in that regard at all at the time.

George Pryn
Acolyte
Posts: 183
Joined: Tue Jan 28, 2014 10:55 pm

Re: Computerphile - Brute Forcing the Countdown Numbers Game

Post by George Pryn » Wed Jan 13, 2021 10:01 pm

Graeme Cole wrote:
Sat Dec 19, 2020 2:40 pm
Published yesterday: an interesting new Computerphile video about the Countdown numbers game, and a method of generating every possible solution using Reverse Polish Notation.

Analysis of this kind has been done on this forum before, but one thing that I hadn't realised was that even targets are statistically significantly easier to achieve than odd targets. This seems obvious now (you can make an even number with odd numbers but you can't make an odd number with evens unless they're the right evens to do a division), I just hadn't thought of it until now.
It makes a lot of sense considering most 'ooooo that's Tricky Luv' solves are when there's a product of two primes involved, which is always an odd number except anything involving the freak of nature numero duo... Odd numbers do just have significantly fewer factors in every instance, they miss out on the 2s, the 4s, the 8s, the 16s, whilst the Evens get to bask in the promise-land of 1,2,3,4,5,6,7,8,9,10,11,12... factors. Greedy fuckers. Also, in terms of the feeble human mind, we are always inclined to go for an even number close to the target when it is an odd one. For example, if I see 973, I'm going for 974. You can't stop me, neither can she. But can I make a 1 at the end? Who knows, I've already started. Now I'm running out of time anyway, so I'd best stick looking for 974. Oh no, I can't make it. Fuck. Finally, every single human being loves the following times-tables: 0 (lol), 1 (lol), 2 (lol), 4, 5, 10. Now, you might be thinking, that doesn't seem too different! Well, there are 500 multiples of 2 up to 1000, 250 multiples of 4 and 10 multiples of 10. There are only 200 multiples of 5, and people will generally always use a reference-near number, ala standard method, in one of those multiplication tables. The last part was complete nonsense, nobody likes times tables. Especially not me, that's why I retired.

Post Reply

Who is online

Users browsing this forum: JackHurst and 24 guests