Search code examples
pythonpython-3.xprobabilityprobability-theory

100 Prisoners Dilemma - Python code isn't working


I stumbled across an interesting probability problem about half an hour ago. https://en.wikipedia.org/wiki/100_prisoners_problem

Essentially, there are 100 boxes, drawers, etc, each with a unique number between 1-100 inside of them. There are also 100 prisoners. Each prisoner has 50 chances to find the box with their number. If even one does not, they all fail. The chances would be abysmally low if they all randomly picked 50 boxes, but there's a better strategy.

Each prisoner first opens the box labeled with their own number. If this box contains their number, they are done and were successful. Otherwise, the box contains the number of another prisoner, and they next open the drawer labeled with this number. The prisoner repeats steps 2 and 3 until they find their own number, or fail because the number is not found in the first fifty opened drawers. This should increase their chances to above 30 percent with the way everything can fall into a loop

I glanced through this and decided it was interesting enough to quickly code out in python, but I'm getting a really interesting (and probably wrong) result. Could someone take a look at the code?

import random 

def begin(p=False): #print
    prisoners = [i for i in range(100)]
    boxes = prisoners.copy()
    random.shuffle(boxes)  #we now have a list of shuffled boxes. index represents box num


    if p: #prints 
        for i,num in enumerate(boxes): #i=index, num=content of box. Just to print it out
            print(i,num)

def run(p=True): #print
    results ={"Success":False, "NumSucceed":0, "NumFail":0 }
    
    for prisoner in prisoners:             #Try every prisoner
        fail = True                         #check if they fail
        choice = boxes[prisoner]           #initialize choice as box with prisoner num

        for i in range(49):          #49 becaues first choice counts as well
            if choice==prisoner:
                fail = False
                break
            choice = boxes[choice]
        
        if fail:
            results["NumFail"] +=1
        else:
            results["NumSucceed"]+=1    
    
    
    if results["NumSucceed"]==100:
        results["Success"] = True
    
    if p: #just if I choose not to print results
        print(results)
    return results


for i in range(100):
    begin()
    run()

How many ever times I run it I always get a failing result where 17 prisoners succeeded and the rest failed (I randomize the rotation of the boxes each time too). Does anyone know why? I hope I didn't just make some stupid error somewhere and waste your time lol, if you do look through this I'd appreciate it


Solution

  • Couple of notes first. Make sure you keep locality/scope in mind with variables. You have a begin() function thats used to declare your variables for the entire script, but they aren't declared globally so when the other method runs, it won't be able to find the variables to declare in begin()

    not sure how you got it to run as is tbh

    so let's scrap the method and just initialize our prisoners and boxes

    import random
    
    prisoners = [i for i in range(100)]
    boxes = [i for i in range(100)]
    

    now you can put the shuffle in your run method, since only boxes need to be randomized and conceptually, randomizing boxes would be the first thing done each time the prisoner dilemma happens.

    
    
    def run(p=True): #print
        random.shuffle(boxes)
        results ={"Success":False, "NumSucceed":0, "NumFail":0 }
        # ...
    

    I ran a couple times and got 20-40 out of 100 total runs where all prisoners found their tag