Computerphile - Brute Forcing the Countdown Numbers Game
- Graeme Cole
- Series 65 Champion
- Posts: 2041
- Joined: Tue Jul 06, 2010 9:59 pm
Computerphile - Brute Forcing the Countdown Numbers Game
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.
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.
- Jon O'Neill
- Ginger Ninja
- Posts: 4551
- Joined: Tue Jan 22, 2008 12:45 am
- Location: London, UK
Re: Computerphile - Brute Forcing the Countdown Numbers Game
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...
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...
- Graeme Cole
- Series 65 Champion
- Posts: 2041
- Joined: Tue Jul 06, 2010 9:59 pm
Re: Computerphile - Brute Forcing the Countdown Numbers Game
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.
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.
- Charlie Reams
- Site Admin
- Posts: 9494
- Joined: Fri Jan 11, 2008 2:33 pm
- Location: Cambridge
- Contact:
Re: Computerphile - Brute Forcing the Countdown Numbers Game
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.
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.
Re: Computerphile - Brute Forcing the Countdown Numbers Game
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.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.
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?
Re: Computerphile - Brute Forcing the Countdown Numbers Game
Nice video! I hope they do one about letters solver!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.
- Charlie Reams
- Site Admin
- Posts: 9494
- Joined: Fri Jan 11, 2008 2:33 pm
- Location: Cambridge
- Contact:
Re: Computerphile - Brute Forcing the Countdown Numbers Game
Yeah, that's a reasonable intuition, but there's a few other factors in the other direction that seem to outweigh it: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.
- 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.)
Not giving away all my trade secrets that easily!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?
- Rhys Benjamin
- Postmaster General
- Posts: 3107
- Joined: Thu Sep 09, 2010 4:28 pm
Re: Computerphile - Brute Forcing the Countdown Numbers Game
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?
- Charlie Reams
- Site Admin
- Posts: 9494
- Joined: Fri Jan 11, 2008 2:33 pm
- Location: Cambridge
- Contact:
Re: Computerphile - Brute Forcing the Countdown Numbers Game
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.)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?
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.)
-
- Post-apocalypse
- Posts: 13312
- Joined: Mon Jan 21, 2008 10:37 pm
Re: Computerphile - Brute Forcing the Countdown Numbers Game
This has happened multiple times. That game wasn't rare in that regard at all at the time.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?
-
- Acolyte
- Posts: 184
- Joined: Tue Jan 28, 2014 10:55 pm
Re: Computerphile - Brute Forcing the Countdown Numbers Game
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.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.