Double up!

[bonanova]

Three people play a money game with (perhaps differing) initial stakes in the range [$1, $255]. On each turn they flip a fair coin to determine an odd-man-out. (If there are three heads or three tails they flip again.) The poorer of the remaining players then "doubles up" at the expense of the richer player. For example: If the initial stakes are ($15, $70, $150) then depending on which player sits out, the stakes at the end of the turn would be ($30, $55, $150), ( $30, $70, $135) or ($15, $140, $80).

The game ends when the two active players in any round have exactly the same stake.

For each set of initial stakes there is a minimum number of turns that must be played. In the above example, clearly two rounds must be played (more than two, actually.) Starting with ($1, $4, $6,) at least three turns must be played. 

Your task is to improve on that. Find initial stakes for which the game cannot end before N turns have been played, where N is the greatest number you can find. If you can beat N=3, post your solution and let others take a shot at beating it. Gold star will be awarded if the best possible N is found.

(This was adapted from a puzzle in a well-known puzzle site, which I will attribute when the best solution is found.)

[CaptainEd]

If the stakes are 1,1,3, and the 3 is odd man out, which one of the 1s loses his stake to the other? I presume this is how we lose players, right?

[CaptainEd]

I think I misunderstood; I guess in your description, a "turn" is the same as a "round", and the "two active players" are the two who flipped the same side of the coin. So, if they had 1,1,3 and the 3 was the odd man out, then the game is over. Have I got it this time?

Edited August 16, 2015 by CaptainEd
Fix typo

[bonanova]

I think I misunderstood; I guess in your description, a "turn" is the same as a "round", and the "two active players" are the two who flipped the same side of the coin. So, if they had 1,1,3 and the 3 was the odd man out, then the game is over. Have I got it this time?

Yes.

I used turn and round to mean the same thing. Sorry for the confusion.

[CaptainEd]

(little steps for little feet)

So (1,4,6) scores 2, because 1x6 yields (2,4,5) and 2x5 yields (4,4,3). Is that what you mean by three turns?

[CaptainEd]

i fear I still don't understand

I think I have exhaustive code to try all outcomes down to 4 steps, and it looks to me like your example of (15, 70, 150) is an example that requires 4 transactions:
there are three ways to do it ("ab" means the lowest two are active, "ac" means lowest vs highest, "bc" means highest two)
15,70,150 ab->30,55,150 ab->60, 25,150 ab-> 50 35 150 bc->35, 100,100
15,70,150 ab->30,55,150 bc->30, 95, 110 bc->15, 30, 190 ac->30, 30, 175
15,70,150 ac->30,70,155 ab-> 40,60,135 bc->40,75,120 ac-> 75,80,80

Are you looking for examples where number of transactions >4? or have I really misunderstood the problem or miscalculated?

[bonanova]

Hidden Content

Yes. You understand, and now everyone does.

Also, you hold the (for now) record of N = 4.   And there is now a target on your back.

[CaptainEd]

ok, here's my submission for N=5:

37,45,170 -> 8,74,170 -> 8,96,148 -> 16,96,140 -> 32,96,124 -> 64 64 124

[araver]

Question on wording of the goal: The game ends when the two active players in any round have exactly the same stake.

If (A,B,C) go into a round, B and C are active and B = A at the end of the round (e.g. B = A/2, B<C), does that count as stopping the game OR the game goes to the next round where only if C sits out the goal is met?

 

Edited August 18, 2015 by araver

[CaptainEd]

Araver, I'm assuming that the shortest path is what counts, and that a stakes assignment with two or three equal numbers counts as zero. I think the coin-flipping is window dressing...Of course, Bonanova's opinion is more reliable :-)

Here's my answer at 8 steps:

21    71    160
42    50    160
84    8    160
16    76    160
32    60    160
60    64    128
4    120    128
4    8    240
8    8    236

[araver]

N = 7. I reorder them each time for simplicity, doubling the smallest each time:

(127,128,129)->(127,256,1)->(2,126,256)->(4,124,256)->(8,120,256)->(16,112,256)->(32,96,256)->(64,64,256) 

Without reordering the same is written:

(A,B,C) = (127,128,129)->(127,256,1)->(126,256,2)->(124,256,4)->(120,256,8)->(112,256,16)->(96,256,32)->(64,256,64)

 

Edited August 18, 2015 by araver

[araver]

I keep forgetting to click "Sort by Date" and when it sorts by rating I get confused.

My question was different, let me rephrase: Assume there was no round before (A,B,C) = (4, 2, 5) with B and C active gets at the end of round 1 to (4, 4, 3).

1) Do we stop here even if the active players are not the ones equal? Bonanova's response does imply so i.e. Game ends at the end of the round if ANY 2 players are equal (different wording than OP though). So we count a minimum of 1 round before game with (4,2,5) ends.

2) If we let it go to the next round since the two active players (B and C) are not equal:

2A) assuming A and B could be active AND if we don't check the condition before we subtract, then one of them gets 0, and that may cause infinite rounds.

2B) If we do check the condition A=B since they are the active, then we call the game ending in Round 2.

What I meant is that different wording makes either N=1 or N=2.

 

In any case, I'm assuming and counting using rule "Game ends at the end of the round if ANY 2 players are equal".

And another submission from me:

N = 11

(209,217,225)->(418,217,16)->(32,217,402)->(64,185,402)->(128,185,338)->(256,57,338)->(114,199,338)->(228,199,224)->(398,224,29)->(29,448,174)->(58,174,419)->(116,116,419) 

[bonanova]

I don't like the default sort by rating thing either. Site Admin is working on changing it to chronological.

araver, that is a valid assumption because the goal is to *assure* a given number of rounds.

If two are equal at the end of a round, they *could* be the active players on the next round.

[Rob_G]

What is the current official highest N? 4?

Edited August 19, 2015 by Rob_G

[araver]

What is the current official highest N? 4?

n=11 in my post above.

 

[araver]

I haven't been able to come up with a better than n=11 alternative. 

I'm pretty sure (branching my results at n=15) that there's nothing between 12 and 14.

[bonanova]

araver has it.

Problem. Solution.

[bubbled]

I had a lot of fun trying to program this. I program in Python and when you are doing 3 recursive calls, the program can bog down really fast if you don't optimize.

I limited the search depth to 1 and ran through the 2,731,135 combos while I stored all the combinations that came back 1 in a hash table to avoid retesting known combos. Then I raised the depth to 2 and ran through them again, etc. I can post code if anyone is interested.

Bottom line, I found two other triples (from araver's answer) that come back 11. I also confirmed that my hash table of solutions stored all 2,731,135 starting conditions, so unless my code is incorrect, there are no paths greater than 11 and exactly 3 that equal 11.

Here are the other 2 (the path starts at the stopping condition and moves towards the answer): [175, 199, 223] -- 

[232, 133, 232], [116, 133, 348], [58, 133, 406], [58, 203, 336], [168, 203, 226], [113, 168, 316], [113, 158, 326], [79, 192, 326], [96, 175, 326], [48, 223, 326], [24, 223, 350], [175, 199, 223]

[197, 205, 213] -- 

[158, 158, 299], [79, 158, 378], [158, 189, 268], [134, 189, 292], [67, 256, 292], [146, 213, 256], [128, 213, 274], [64, 213, 338], [32, 213, 370], [16, 213, 386], [8, 213, 394], [197, 205, 213]

[bonanova]

I had a lot of fun trying to program this. I program in Python and when you are doing 3 recursive calls, the program can bog down really fast if you don't optimize.

I limited the search depth to 1 and ran through the 2,731,135 combos while I stored all the combinations that came back 1 in a hash table to avoid retesting known combos. Then I raised the depth to 2 and ran through them again, etc. I can post code if anyone is interested.

Bottom line, I found two other triples (from araver's answer) that come back 11. I also confirmed that my hash table of solutions stored all 2,731,135 starting conditions, so unless my code is incorrect, there are no paths greater than 11 and exactly 3 that equal 11.

Hidden Content

@bubbled, Nice job. Would love to see the code. Actually I'm trying to learn python.

@araver, belatedly your gold star!

[bubbled]

I had a lot of fun trying to program this. I program in Python and when you are doing 3 recursive calls, the program can bog down really fast if you don't optimize.

I limited the search depth to 1 and ran through the 2,731,135 combos while I stored all the combinations that came back 1 in a hash table to avoid retesting known combos. Then I raised the depth to 2 and ran through them again, etc. I can post code if anyone is interested.

Bottom line, I found two other triples (from araver's answer) that come back 11. I also confirmed that my hash table of solutions stored all 2,731,135 starting conditions, so unless my code is incorrect, there are no paths greater than 11 and exactly 3 that equal 11.

Hidden Content

@bubbled, Nice job. Would love to see the code. Actually I'm trying to learn python.

@araver, belatedly your gold star!

In the other thread, I was uncomfortable doing comments on code I didn't write. But I did write this code, so I went back and added comments, to try to give you a really good idea of what's going on. Recursion is really tricky, particularly for this problem. For example, if we start with [2, 4, 100], clearly the answer is 1. But, in the recursion, one of the calls will be [2, 4, 100], and then one of the secondary calls will be [2,4,100] ad infinitum.

My friend, who wrote the 'random bullets' code that I posted for you, helped me with the concept of iteration limiting. In the case of a repeating infinite loop, the limit will terminate that branch and return None, which will get appropriately ignored. That way, by raising the recursion limit 1 level at a time and storing the found answers as we go, we never hit an infinite loop and we get faster and faster performance.

It's very important to go up 1 at a time. This program would run for days if I set the limit to 11 to start with, and then tried to march through the 2.7M possibilities. For an example like [2, 4, 100], which will still come back 1, some of the branches will go down 11 levels. That's potentially, 3^11 calls, for a triple that should stop after 3 calls. But, it does terminate after just 3 calls, if you set the limit to 1. I'd rather do millions of extra hash table look-ups than do 2.7M X 3^11 recursive calls.

For giggles, I just ran a test. I called my function on [2, 4, 100] with a limit of 1, and it returns 1 in .00009 seconds. The same triple, but with the limit raised to 11, comes back with the same answer but in .3 seconds; a huge difference in performance. During my routine, by the time I've raised the iteration limit up to 11, the answer to [2, 4, 100] is already in the solution table, so instead of wasting .3 seconds, we see that the answer is already in the table and we move on.

If you have any questions, I'd be happy to answer. You'll enjoy Python. It's easy and robust, but it's not the fastest language, so it forces you to optimize.  

 

from itertools import combinations
# combinations will efficiently produce all the triples we need to test

best_scores = {}

# best_scores is a dictionary (python hash table) to store
# all the found solutions as we walk up each iteration level.
# It will also speed up each level, as we won't need to re-compute
# a solution that we have already found

def game(stakes, iteration, limit):
    if stakes[0] == stakes[1] or stakes[0] == stakes[2] or stakes[1] == stakes[2]:
        return 0
# Every recursive function needs a base case stopping condition. If any two of stake1, stake2 or stake3
# are equal, the function terminates and returns 0
    
    if iteration == 0:    
        stakes = sorted(stakes)

# For safety, just in case someone uses the function and uses an unsorted
# triple
        
    if tuple(stakes) in best_scores:
        
# Have to change the list into a tuple, because Python lists are not hashable and can't
# be dictionary keys.
        
        return best_scores[tuple(stakes)]

# This short-curcuits recursive calls if a solution is already
# in best_scores
   
    if iteration > limit:
        return None

# Very important. Each branch will return None if we exceed the iteration limit.
# We only store correct solutions. If a particular triple needs more than the limit
# to return a good solution, the function terminates and returns None. The triple will
# get tested again with a higher limit.
    
    r1_stakes = sorted([stakes[0] * 2, stakes[1] - stakes[0], stakes[2]])
    r2_stakes = sorted([stakes[0] * 2, stakes[1], stakes[2] - stakes[0]])
    r3_stakes = sorted([stakes[0], stakes[1] * 2, stakes[2] - stakes[1]])

# We sort the triples, to reduce to 3, the number of possible next games and reduce number of solutions in best_scores.   
    
    r1 = game(r1_stakes, iteration + 1, limit)
    r2 = game(r2_stakes, iteration + 1, limit)
    r3 = game(r3_stakes, iteration + 1, limit)

# These are the rucursive calls. Many times r1, r2, or r3 might come back None. Those results
# will be ingnored below. Very important, we raise the interation (to be tested above against the limit)
# each level of the recursion. Without this, some branches might never terminate.
    
    low_test= []
    
    if r1 != None and r1 <= limit:
        low_test.append(r1)

# We check to make sure the result of each recursion is not None and it's not above 
# the iteration limit. If so, it goes into low_test.
    
    if r2 != None and r2 <= limit:
        low_test.append(r2)
    if r3 != None and r3 <= limit:
        low_test.append(r3)

   
    if low_test:        
        return 1 + min(low_test)
        
# If at least one good result is in low_test, then we return the min + 1. 
    
    else:
        return None

# If not, we return None. This is the end of the main function    

results = [(0, [2,2,2])]

# A dummy result just to get results started. It will get replaced by real results quickly

for limit in range(1, 13):  # The outer loop walks us up the iteration levels.
    for combo in combinations(range(1, 256), 3): # The inner loop walks through all the 
                                                # possible '255 choose 3' triples
        if combo not in best_scores: # If we have a solution already, skip and go to the next one
            test_combo = list(combo) # combinations returns tuples, and we need to
                                     #use lists for the recursion, because they are mutable       
            test_result = game(test_combo, 0, limit)
            if test_result != None:            
                best_scores[combo] = test_result
# If test_result is not None, we know it is correct and it's not in best_results 
# yet, so it goes in
                if test_result > results[0][0]:
                    results = [(test_result, test_combo)]
# This is where we store the biggest results so far
                elif test_result == results[0][0]:
                        results.append((test_result, test_combo))
    

print results
print len(best_scores)
# This shows we have found solutions for all possible triples

 

[bonanova]

I followed most of this on first read. Nicely done and clearly commented. Thanks.

I'd like to compile and run it. What do I need for that?

[bubbled]

I followed most of this on first read. Nicely done and clearly commented. Thanks.

I'd like to compile and run it. What do I need for that?

I'd strongly suggest you use the Anaconda distribution of Python. Python is open source, which is a huge strength (great packages) and a weakness (hard to keep up with and occasional compatibility issues). Anaconda gathers all the most important packages, like Scikit-Learn (machine learning), Numpy (blazing fast matrix operations), Pandas (R-like statistical and data tools) and many others, makes sure they play nice together and updates them. Those are the packages that are of most interest to me, but there are hundreds. 

It also includes Spyder which is a really good IDE. You can get all of these packages on your own, but then updating one, might break another. Anaconda takes care of all that for you. You just check to see if there's an update every once in a while, and if there is, it will all come at once and work.

Anaconda is free and works on Windows, Mac and Linux. I also suggest you use the 2.7x compatible version of Python. It seems to be the more common version.  

https://store.continuum.io/cshop/anaconda/