Puzzle for programmers #2

Cerebral distractions of every kind, mostly but not exclusively Countdown-related.

Moderator: Michael Wallace

Post Reply
User avatar
Jon Corby
Moral Hero
Posts: 8018
Joined: Mon Jan 21, 2008 8:36 am

Puzzle for programmers #2

Post by Jon Corby »

Following the runaway success of Robert's "Puzzle for programmers" thread, I thought I'd follow it up with another. This isn't actually just for programmers, anybody can have a go, but I'm actually looking for a bit of help with logic. I used to be good at this kind of stuff, but my brain has completely failed me.

Anyway, imagine if you will, a hi-lo gambling game. The number reel is as follows:

12
5
3
6
4
9
7
11
5
1
11
8
10
7
3
2


The rules are simple, you guess higher/lower, and the machine spins in a number and you either win or lose (it can't spin back to the same number). The RED numbers are no-lose; you will always win the gamble whether you choose higher or lower. What I'm interested in is how many gambles I can guarantee winning, depending on which number I start. Easy - I'm guaranteed to win one gamble if I start on 1, 12, 5, 7 or 3, and two gambles if I start on 11. Right? Right. However, the waters are muddied because I can also have any combination of the following bonuses:

Extra Life. I can have zero or one of these. Means a losing gamble won't kill me. So if I'm on a 2 or 11 with an extra life, I'm guaranteed to one at least one further gamble.
Lucky 7. I can have zero or one of these, but it essentially makes the gamble on the (non-red) 7 no-lose. Use it once and it's gone (if I'm on the red 7, it won't use this bonus).
No Lose. I can have up to two of these, and means I will win the gamble. (A gamble which is already no-lose, i.e. the 1 or the 12 or any of the red numbers won't use up the bonus.)
Step. This enables me to step the reel UP to the number above. I can have zero to three of these, and you can use as many as you like in one go; so if I'm on the 4 I could step all the way to the red 5.

So the machine is always trying to kill me while allowing me to win as few gambles as possible (note that losing a gamble with the extra life doesn't count as a "win", it just means the game doesn't end). Ideally what I was after is a simulator which allowed me to play out any scenario, and also tell me how many gambles I can guarantee to win from any starting point (i.e. number showing and combination of bonuses).

Cheers in advance for any help!
User avatar
Matt Morrison
Post-apocalypse
Posts: 7822
Joined: Wed Oct 22, 2008 2:27 pm
Location: London
Contact:

Re: Puzzle for programmers #2

Post by Matt Morrison »

So you're back on the fruities then?
User avatar
Jon Corby
Moral Hero
Posts: 8018
Joined: Mon Jan 21, 2008 8:36 am

Re: Puzzle for programmers #2

Post by Jon Corby »

Ssh, this is a logic puzzle :?
User avatar
Matt Morrison
Post-apocalypse
Posts: 7822
Joined: Wed Oct 22, 2008 2:27 pm
Location: London
Contact:

Re: Puzzle for programmers #2

Post by Matt Morrison »

It does look very interesting. Well beyond me but I'm still going to have a go at it tomorrow.
I'm sure it won't be long before Graeme strays out of his thread and solves it for you.
User avatar
Jon O'Neill
Ginger Ninja
Posts: 4545
Joined: Tue Jan 22, 2008 12:45 am
Location: London, UK

Re: Puzzle for programmers #2

Post by Jon O'Neill »

I'd say if the number is below 7 you should go higher, and vica versa. But it all depends really.
User avatar
Charlie Reams
Site Admin
Posts: 9494
Joined: Fri Jan 11, 2008 2:33 pm
Location: Cambridge
Contact:

Re: Puzzle for programmers #2

Post by Charlie Reams »

This looks interesting but I don't really understand the explanation. What does it mean that "the machine spins in a number"? Anyway, apart from the details it sounds like you could Monte Carlo this fairly easily.
User avatar
Jon Corby
Moral Hero
Posts: 8018
Joined: Mon Jan 21, 2008 8:36 am

Re: Puzzle for programmers #2

Post by Jon Corby »

Jon O'Neill wrote:I'd say if the number is below 7 you should go higher, and vica versa. But it all depends really.
Generally yeah, but in this instance I'm not interested in having the "best chance" of winning a gamble, they have to be guaranteed winners. Usually on a no-lose gamble you'd "reverse" (i.e. go against the number, e.g. lower than a 3) to get the best number afterwards, but again that's not necessarily relevant here since I don't just want a good number, I need guaranteed winners.

Actually, the red 3 is a good example of where there may be subtleties at play here. If I'm on the red 3 and go lower, it can either spin to a 2 or a 1. The optimum play for the machine will depend on what bonuses I have remaining; if I have any steps, spinning the 2 will allow me to step straight back to the red 3 and be back in the same situation (albeit with one less step in my locker). It's probably therefore better to spin me to the 1 - yes I'm guaranteed to win the next gamble, but after that it can stitch me by spinning in the 9. The 9 looks like an absolute kicker - 3 steps won't even take you to a red number, so you'll need to be avoiding the 9 as best you can, or having a no-lose or at least an extra life and some steps (two, I think).
Charlie Reams wrote:This looks interesting but I don't really understand the explanation. What does it mean that "the machine spins in a number"?
Sorry, as Matt says this is a fruit machine hi-lo gamble, but I forget that not everybody will be familiar with these. The machine has a fixed reel, with the numbers in sequence as above. It's looped round so that the 2 is above the 12. It always shows a number. When I start the game it could be showing any number, and I have to then choose whether to gamble higher or lower than that number. The reel then has to spin to a different number (value I mean, so if you're on the non-red 3 it can't spin the red 3 straight after) , and I either win or lose the gamble. If I lose the gamble, it's game over (unless I have an extra life, in which case I just lose the life), if I win the gamble I advance one space. And then we go again from whatever number is now displayed. The number isn't random though, the machine is in complete control, but playing within the constraints as outlined above. If any of these are unclear, please say. Basically, I only have three buttons I can press; Hi, Lo or Step. I can't choose when to use any of the other bonuses apart from steps, the machine will just use them automatically as necessary. For example, I can't be on a 2 with a No-Lose and say "I'd like to save my no-lose for another time, and try going higher than the 2" - if I press Hi, it will use the bonus and win the gamble by spinning in a number higher than 2 (and obviously if I press Lo it will have to spin in the 1).

What I'm interested in is the optimal way to play this reel, and how many gambles I can be guaranteed to win from any given starting number, with any given combination of the available bonuses.

I figured I could write a simulator fairly easily which just kind of "brute-forced" its way through (as in, the only three buttons available are Step (if I have any steps left), Hi (if I'm on a number < 12) and Lo (if I'm on a number > 1), but I'm getting in a right muddle with the logic. I need a routine which basically returns the number of guaranteed wins given the number and the bonuses I have. However, this routine keeps then referencing itself (in order for the machine to decide its response, since it wants to give the response which gives me the fewest onward guaranteed wins) and it's messing my brain up. I'm annoyed because I'm positive it's the kind of thing I would have rattled off in no time about 10-15 years ago. Fucking old age.
Gavin Chipper
Post-apocalypse
Posts: 13214
Joined: Mon Jan 21, 2008 10:37 pm

Re: Puzzle for programmers #2

Post by Gavin Chipper »

Jon O'Neill wrote:I'd say if the number is below 7 you should go higher, and vica versa. But it all depends really.
Definitely. Also if you wait around until somebody before you loses a load of money and then pounce. I can't believe you haven't thought of any of this???!!!
User avatar
Matt Morrison
Post-apocalypse
Posts: 7822
Joined: Wed Oct 22, 2008 2:27 pm
Location: London
Contact:

Re: Puzzle for programmers #2

Post by Matt Morrison »

This is the sort of thing I hope to be able to rattle off in about 10-15 years time.
User avatar
Jon Corby
Moral Hero
Posts: 8018
Joined: Mon Jan 21, 2008 8:36 am

Re: Puzzle for programmers #2

Post by Jon Corby »

I made some progress with this, if anybody's interested, but it needs some tuning. I wanted to do a full sweep of every conceivable outcome rather than make any assumptions (such as "it would never be optimal for the machine to spin in a red number or a 1/12 if it wasn't forced into it) because as I showed above, it is better for the machine to spin the 1 in if you go lower than the red 3 and have 2 or more steps (I think). See, the fact that I'm not even sure about it is why I don't want to make any assumptions, and instead just test every scenario.

So I have a Position object, which contains the number the reel is currently showing, plus any bonuses I have.

I then have a method called 'GuaranteedWins' which accepts a Position as a parameter, and returns an integer, which is obviously how many guaranteed wins I can (optimally) achieve from that position. It does this by simply checking what the machine will do if I press any of the three buttons (Hi/Lo/Step, one or more of which may obviously not be available depending on the number and whether I have any steps), and then checking the GuaranteedWins of that new position to find which is highest (+1 if I've just won a gamble). As you can see, GuaranteedWins is repeatedly calling itself...

The final method is 'PressButton' which accepts a position and a button press (hi/lo/step) and returns the new position. For 'Step' this is easy, since it just has to shift the number reel up one, there's no decision to make. For Hi/Lo, I want the machine to play optimally against me, so for each allowable number on the reel (as per the constraints explained in the OP), it checks the GuaranteedWins (+1 if I've also just won that gamble), and goes with whichever response garners the fewest onward guaranteed wins.

Non-programmers may not quite follow, but basically the two methods are constantly calling each other in a massive nest. It's an absolute headfuck but it actually seems to hang together and work. However, it's completely unconstrained at the moment, so it also runs off in infinite loops - e.g. when the machine is considering its response, it explores what happens if it wins the gamble from a 5 to a 1, then wins that gamble to a 12, then wins the next gamble to a 1, then wins the next gamble to a 12, and so on and so forth.

I thought an easy way to combat this was to introduce a 'win limit', so if an avenue being explored hits this limit, we stop exploring it (since it will not be relevant). And indeed, if I set the win limit very low, and don't have any bonuses, I get the figures returned that I expect. Likewise, if I introduce a single bonus, such as Step or Extra Life, I can see that the results returned are sensible. However, if I up this win limit to try and explore more complex situations with multiple bonuses, it runs forever. This may be due to some other bug, but I think it's just the sheer number of possibilities it's scanning through that is screwing it.

So I think therefore the next step is to try and optimize the calculation of the machine's response. I'm still keen not to introduce any logic myself - for example, I have a strong hunch that it's never in the machine's interest to win a gamble that it could lose, or to spin in any of the red numbers, but I don't want to code that in as that's part of what I'm trying to analyse/prove. However, at the moment, it literally checks every avenue thoroughly, which is unnecessary wasteful. I think a good starting point would be to prioritise and check losing responses first (if any) followed by the winning ones, plus also, rather than have a set "win limit", make this variable, so once I've checked the guaranteed wins from one response, I can abort any subsequent checks as soon as they breach this limit (so if I've already checked that spinning a 5 would result in 2 more guaranteed wins, I can, when subsequently checking how this compares to what happens if the machine spin a 7, abort as soon as I hit any path that results in more than 2 wins)

Oh yeah, and also to make a library of the GuaranteedWins for every position examined; once I've ascertained that there are two onward GuaranteedWins from the red 11 with no bonuses, I shouldn't ever have to let it recalculate that, the method can just instantly return that it's 2. I think this will be very helpful as the situations get more complex.

Apologies if this lost anybody, or if you don't care, but would be interested in any input/suggestions/questions.
Gavin Chipper
Post-apocalypse
Posts: 13214
Joined: Mon Jan 21, 2008 10:37 pm

Re: Puzzle for programmers #2

Post by Gavin Chipper »

If the machine is purely trying to fuck you then surely it will never give you any of the bonus things if it can give you 0-3 or whatever. And of course it would never spin a red. So surely that's not actually what it's trying to do. It has to be generous enough to keep people's interest in the game and take more money overall.
User avatar
Jon Corby
Moral Hero
Posts: 8018
Joined: Mon Jan 21, 2008 8:36 am

Re: Puzzle for programmers #2

Post by Jon Corby »

Gavin Chipper wrote:If the machine is purely trying to fuck you then surely it will never give you any of the bonus things if it can give you 0-3 or whatever. And of course it would never spin a red. So surely that's not actually what it's trying to do. It has to be generous enough to keep people's interest in the game and take more money overall.
Correct. I have PM'd you.
Edit; I haven't actually PM'd you yet (at the time of writing this), but I'm going to now.
User avatar
Matt Morrison
Post-apocalypse
Posts: 7822
Joined: Wed Oct 22, 2008 2:27 pm
Location: London
Contact:

Re: Puzzle for programmers #2

Post by Matt Morrison »

Have you PM'd him yet?
User avatar
Jon Corby
Moral Hero
Posts: 8018
Joined: Mon Jan 21, 2008 8:36 am

Re: Puzzle for programmers #2

Post by Jon Corby »

Matt Morrison wrote:Have you PM'd him yet?
Yes.
Gavin Chipper
Post-apocalypse
Posts: 13214
Joined: Mon Jan 21, 2008 10:37 pm

Re: Puzzle for programmers #2

Post by Gavin Chipper »

Jon Corby wrote:
Matt Morrison wrote:Have you PM'd him yet?
Yes.
And I've PMed back. None of this "PM'd" rubbish for me
User avatar
Ian Volante
Postmaster General
Posts: 3956
Joined: Wed Sep 03, 2008 8:15 pm
Location: Edinburgh
Contact:

Re: Puzzle for programmers #2

Post by Ian Volante »

Interesting. I'd like to see the outcome of this, and to know which machine(s) it applies to. Just call me freeloader.
meles meles meles meles meles meles meles meles meles meles meles meles meles meles meles meles
User avatar
Jon Corby
Moral Hero
Posts: 8018
Joined: Mon Jan 21, 2008 8:36 am

Re: Puzzle for programmers #2

Post by Jon Corby »

Ian Volante wrote:Interesting. I'd like to see the outcome of this, and to know which machine(s) it applies to. Just call me freeloader.
You don't really have enough information (even with the outcome of this analysis) to particularly do anything with it, but I'll PM you anyway when I've got everything nailed down.
User avatar
Ian Volante
Postmaster General
Posts: 3956
Joined: Wed Sep 03, 2008 8:15 pm
Location: Edinburgh
Contact:

Re: Puzzle for programmers #2

Post by Ian Volante »

Jon Corby wrote:
Ian Volante wrote:Interesting. I'd like to see the outcome of this, and to know which machine(s) it applies to. Just call me freeloader.
You don't really have enough information (even with the outcome of this analysis) to particularly do anything with it, but I'll PM you anyway when I've got everything nailed down.
Cheers. It's the sort of thing I've been interested in for years anyway, but never got round to looking into.
meles meles meles meles meles meles meles meles meles meles meles meles meles meles meles meles
User avatar
Charlie Reams
Site Admin
Posts: 9494
Joined: Fri Jan 11, 2008 2:33 pm
Location: Cambridge
Contact:

Re: Puzzle for programmers #2

Post by Charlie Reams »

You seem to have reinvented dynamic programming. If you invent the minimax algorithm I think you'll be pretty much there.
User avatar
Jon Corby
Moral Hero
Posts: 8018
Joined: Mon Jan 21, 2008 8:36 am

Re: Puzzle for programmers #2

Post by Jon Corby »

Charlie Reams wrote:You seem to have reinvented dynamic programming. If you invent the minimax algorithm I think you'll be pretty much there.
I see.... :?
My planned optimisations didn't quite go according to plan. The interaction between the nested methods is so fiddly and intricate, and it just seems to hang together *somehow*. It's an absolute mare to debug because there's basically <50 lines of code, they just call each other constantly and I deliberately kept the information being exchanged to the absolute minimum to try and be as efficient as possible (my original intention was to do all the calculations on the fly while running the reel simulator, which was a somewhat rubbish guess at how quick it would be). As I said, it seems to work (I can test it fairly well with less complex reel layouts etc) but quickly spins out of control as soon as the situations get more complex. The idea of keeping a library of previous calculations is a good one, but it didn't seem to work when trying to use them in onward calculations, and this is due to the interaction between the methods evolving to be slightly more complex than just giving a number back. To be honest I've kind of lost control of how it's working (Skynet) and I don't fully understand why, but it just didn't work (even though in theory it should), so it came out. It's impossible to debug really so I just couldn't be arsed to work out why (it took me over an hour to find another error whereby I was accidentally resetting the win count when the 'Step' button was pressed, the laptop was close to going out of the window at that point.)

The idea of dealing with losing spins first to set a benchmark seemed to be a good one though, and I did settle on the end on a variation of the 'variable win limit' - it simply starts at 1 for each calculation, and if the maximum wins returned = that limit, we up the limit by 1 and go again, until the number returned < limit.

So I'm fairly happy that it's calculating correctly now, and while slow I'm pretty sure it can't get into infinite loops anymore, so I left it to run overnight... forgetting that I hadn't set the laptop not to go to sleep after 15 minutes' inactivity. OOPS. So it's running away at home now anyway.

I also figured that I could easily test that the results are correct by doing a full scan of the library that I've built. It's easy to be able to look at each reel position with no bonuses and say for absolute sure that they are correct, and every other position will ultimately cascade back to this. So I can check each position in turn (there's only 48 bonus combinations * 16 reel positions) and ensure that each button press conforms with the subsequent picture. I did begin to wonder if I could have built the whole library like this from the bottom up adding one bonus at a time, but I think it gets complicated on the no-lose gambles because you'd have to be looking at situations that haven't been calculated yet.

So hopefully when I get home tonight I will have the full library of data, and then it'll just be a case of knocking up a quick UI to practice with to ensure I know how to play optimally, and always know exactly what the score is. As Gev alluded to above, this won't be a realistic simulation of the machine in question (since it doesn't always play 100% optimally against you - otherwise you'd never win a single gamble that wasn't no lose, and people would very quickly get thoroughly pissed off with that) but the important thing in this particular case is knowing what situations you can manipulate the machine into which it can't suddenly get out of when it realises it needs to.

I can see now why people blog about absolute shit that nobody else is really interested in, it's actually quite fun just to write stuff down for yourself. Does anyone know how I can get in touch with Clare Sudbery to apologise?
Gavin Chipper
Post-apocalypse
Posts: 13214
Joined: Mon Jan 21, 2008 10:37 pm

Re: Puzzle for programmers #2

Post by Gavin Chipper »

Jon Corby wrote:I can see now why people blog about absolute shit that nobody else is really interested in, it's actually quite fun just to write stuff down for yourself. Does anyone know how I can get in touch with Clare Sudbery to apologise?
Is that why you fell out? What a cunt. I won't be talking to you on the train to COLIN.
User avatar
Jon Corby
Moral Hero
Posts: 8018
Joined: Mon Jan 21, 2008 8:36 am

Re: Puzzle for programmers #2

Post by Jon Corby »

Gavin Chipper wrote:
Jon Corby wrote:Does anyone know how I can get in touch with Clare Sudbery to apologise?
Is that why you fell out? What a cunt.
Harsh, even I never called her that.
Robert Lozyniak
Newbie
Posts: 17
Joined: Tue Aug 27, 2013 5:37 am

Re: Puzzle for programmers #2

Post by Robert Lozyniak »

Jon Corby wrote: The rules are simple, you guess higher/lower, and the machine spins in a number and you either win or lose (it can't spin back to the same number). The RED numbers are no-lose; you will always win the gamble whether you choose higher or lower. What I'm interested in is how many gambles I can guarantee winning, depending on which number I start. Easy - I'm guaranteed to win one gamble if I start on 1, 12, 5, 7 or 3, and two gambles if I start on 11. Right? Right.
I don't get it: how will starting on 11 allow you to win two gambles? What happens if the very next number is 4?
... Oh, I get it. A red number means you get to decide whether the next number will be higher or lower. Does the "no lose" bonus item also work this way?

This reminds me of games such as Nim (google it). The standard way of solving such things does not use simulation in the sense you seem to mean. Really, all you need to do is construct the game tree (google this too). At most there are 16*2*2*3*4=768 possible states the game can be in.
User avatar
Jon Corby
Moral Hero
Posts: 8018
Joined: Mon Jan 21, 2008 8:36 am

Re: Puzzle for programmers #2

Post by Jon Corby »

Robert Lozyniak wrote:
Jon Corby wrote: The rules are simple, you guess higher/lower, and the machine spins in a number and you either win or lose (it can't spin back to the same number). The RED numbers are no-lose; you will always win the gamble whether you choose higher or lower. What I'm interested in is how many gambles I can guarantee winning, depending on which number I start. Easy - I'm guaranteed to win one gamble if I start on 1, 12, 5, 7 or 3, and two gambles if I start on 11. Right? Right.
I don't get it: how will starting on 11 allow you to win two gambles? What happens if the very next number is 4?
... Oh, I get it. A red number means you get to decide whether the next number will be higher or lower. Does the "no lose" bonus item also work this way?
Correct, the red number works exactly the same as the no-lose bonus, that is, whichever way you guess, you will be right (the 1 and 12 might as well be red as well for all intents and purposes).

You can't "choose" to use the no-lose bonus either - if you gamble while you have a no-lose bonus (and you're not already on a no-lose number), it gets used.

I'm actually pretty much there anyway, I've got all the figures, so it's just a case of double-checking that they're correct, and then building a (simple) UI that allows me to play out/analyse various scenarios. My enthusiasm for the project has waned somewhat though, since on discussing my findings with my mate in-the-know, he pointed out that the machine in question doesn't actually play truly optimally against you, even when it's out-and-out trying to kill you - for example, if you're on a 9 with 2 steps and an extra life and go lower, it should take the life and spin the 12, allowing you to win just one more gamble; instead it ALWAYS spins to the 10, allowing you to win two more. Which, of course, is actually good news, but does render all the analysis somewhat incorrect. Oh well. I'll probably make a second version which takes this into account!
Robert Lozyniak
Newbie
Posts: 17
Joined: Tue Aug 27, 2013 5:37 am

Re: Puzzle for programmers #2

Post by Robert Lozyniak »

I kind of like this puzzle.

I live in the USA, where we don't have those machines (pity), but we do have YouTube, so I am a bit familiar with the genre you are describing.
Jon Corby wrote:he pointed out that the machine in question doesn't actually play truly optimally against you, even when it's out-and-out trying to kill you - for example, if you're on a 9 with 2 steps and an extra life and go lower, it should take the life and spin the 12, allowing you to win just one more gamble; instead it ALWAYS spins to the 10, allowing you to win two more.
I wonder what happens if the manufacturer finds this thread and reads your "bug report" there.

We should really get those machines in my country. People take up too much time in convenience stores buying lottery tickets (with their special lucky numbers, mind you!) when, if we had those machines, I would be able to just pay for my sandwich and get out. On second thought, the machines might very well make people like me broke.

Someone should come up with a fruit machine which dispenses real fruit. So if it comes up two lemons and a pear, that's what you get: two lemons and a pear.
User avatar
Jon Corby
Moral Hero
Posts: 8018
Joined: Mon Jan 21, 2008 8:36 am

Re: Puzzle for programmers #2

Post by Jon Corby »

Robert Lozyniak wrote:I wonder what happens if the manufacturer finds this thread and reads your "bug report" there.
I'm fairly confident that won't happen :D
Ryan Taylor
Postmaster General
Posts: 3661
Joined: Sun Oct 25, 2009 6:18 pm

Re: Puzzle for programmers #2

Post by Ryan Taylor »

What was all this about?
Post Reply