The Strange Prisoner Experiment

The Strange Prisoner Experiment

I found a video about this experiment on Youtube, made by Veritasium and recreated it using Python in Blender.

100 prisoners are sent into a room, one by one. In this room there are as many boxes as there are prisoners and each prisoner can open half the boxes in the room. Each box contains a random number and if the prisoner finds his number in any of the 50 boxes he is allowed to open, he succeeds. Each prisoner must leave the room exactly as he found it and cannot communicate  with any of the other prisoners after he's done. If any of the 100 prisoners fails, they all get executed.

The question: Is there a strategy the prisoners can agree on before the first prisoner enters the room to increase their chances of winning?
The proposed solution: Each prisoner opens the box with his number as the label first and then moves to the box with the number he finds inside that box.

For example, prisoner no. 10 enters the room, he opens box no. 10, if he indeed finds number 10 inside that box, he is done, if not he should open the box with the number he found inside box no 10 and so on.

I thought: maybe that's just one a theoretical probability experiment that only works in theory, so I whipped up this python script to test the hypothesis. I did not double-check how low the win rate is, when all prisoners pick boxes at random, because the math is pretty straight forward, so I'll assume Veritasium is right and the result it's very very low.

import numpy as np
import random
import time

print(100*"=")

prisoners = 100 # set number of prisoners here

def run(l):
	for i in range(prisoners):
		success = send_prisoner(l, i) # 
		if not success:
			#print("All dead, accomplished:", i)
			return False, i # i prisoners found their box before 1 failed

	return True, prisoners
	

def send_prisoner(l, prisoner):
	# let 1 prisoner search the boxes
	next_box = prisoner # start with the box with index prisoner
	for i in range(prisoners // 2): # each prisoner can check half the amount of boxes as there are prisoners
		#print("Checking", next_box, "found:", l[next_box]) #uncomment to check if they march in loops
		if l[next_box] == prisoner:
			#print("Found it, tries", i) # uncomment to see how many tries it took each prisoner
			return True
		next_box = l[next_box]
	return False

def get_boxes():
	boxes = []
	for i in range(prisoners):
		boxes.append(i)
	random.shuffle(boxes)
	return boxes

	# returns as many boxes as there are prisoners
	boxes = np.arange(prisoners) # get a list of the numbers [0 ; prisoners -1]
	np.random.shuffle(boxes) #shuffle the numbers inside the boxes
	return boxes

def main():
	successes = 0
	total_successes = 0
	start_time = time.time()
	n = 1000 # how many times the warden gets his sadism on
	for i in range(n):
		l = get_boxes()
		success, total = run(l) # run 1 experiment
		#print("Run no:", i, "successes:", total)
		total_successes += total
		if success:
			successes += 1
	
	end_time = time.time()
			
	win_ratio = successes / n
	total_completed = total_successes / (prisoners * n)
	print("Total prisoners that succeeded", total_successes, "out of: ", (prisoners * n), "=>", total_completed)
	print("Win ratio:", str(round(win_ratio * 100, 3)) + '%')
	print("Method took:", end_time - start_time) # so you can plan ahead how much time it would take to increase either n or prisoners
	
if __name__ == "__main__":
	main()

Running the plotted script below with n = 100,000 resulted in:

Prisoners: 2, Win rate 0.49721
Prisoners: 20, Win rate 0.32954
Prisoners: 50, Win rate 0.31907
Prisoners: 100, Win rate 0.31063
Prisoners: 200, Win rate 0.30901
Prisoners: 500, Win rate 0.30874
Prisoners: 1000, Win rate 0.30913

 

As you would expect, running the experiment 100 times is not sufficient to be statistically reliable. That would be like throwing a dye 6 times and expecting each number exactly once. This means we get a lot of fluctuation.

Using 1,000 iterations brings us closer to the truth and 100,000 should be sufficient to show that just like Eric claimed 100 prisoners have a success rate of ~31.1% and 1,000 still survive ~30.6% of the time.

And this wouldn't be BlenderDiplom if we would not provide the method we used to plot this in Blender, here is the script:

import random
import time

from bpy import data as D
from bpy import context as C
from mathutils import Vector

print(100*"=")

def run(l, prisoners):
	for i in range(prisoners):
		success = send_prisoner(l, i) # 
		if not success:
			#print("All dead, accomplished:", i)
			return False, i # i prisoners found their box before 1 failed

	return True, prisoners
	
def send_prisoner(l, prisoner):
	# let 1 prisoner search the boxes
	next_box = prisoner # start with the box with index prisoner
	length = len(l) // 2
	for i in range(length): # each prisoner can check half the amount of boxes as there are prisoners
		#print("Checking", next_box, "found:", l[next_box]) #uncomment to check if they march in loops
		if l[next_box] == prisoner: # number inside the box equals the number of the current prisoner
			#print("Found it, tries", i) # uncomment to see how many tries it took each prisoner
			return True
		next_box = l[next_box]
	return False

def get_boxes(prisoners):
	# returns as many boxes as there are prisoners
	boxes = []
	for i in range(prisoners):
		boxes.append(i)
	random.shuffle(boxes)
	return boxes

def run_experiment(prisoners, n):
	team_successes = 0 # number of times all prisoners succeded
	start_time = time.time()
	results = []
	
	for i in range(n):
		l = get_boxes(prisoners)
		success, total = run(l, prisoners) # run 1 experiment
		#print("Run no:", i, "successes:", total)
		if success:
			team_successes += 1
	
	win_ratio = team_successes / n
	return win_ratio


def plot(results, distance):
	mesh = D.meshes['Plane'] # the base mesh for the bar, add a plane and scale it in Edit Mode
	collection = D.collections['Plot']
	txt_mat = None
	bar_mat = None
	if not 'Label' in D.materials:
		txt_mat = D.materials.new('Label')
	else:
		txt_mat = D.materials['Label']

	for i, result in enumerate(results):
		prisoners = result['prisoners']
		print("Prisoners", prisoners, "Win rate", result['win_ratio'])
		label = str(prisoners)
		txt = D.curves.new(type="FONT", name = 'Label-' + label) # need to use a font curve as object data
		txt.body = label 
		txt.align_x = 'CENTER'
		txt_ob = D.objects.new('Label-' + label, txt) # curve here, text does not work directly
		txt_ob.data.materials.append(txt_mat) # so you can change the appearance of all labels at once
		
		x = i * distance # evenly space the results
		txt_ob.location = Vector((x, -1.2, 0)) #hardcoded values that fit the current setup
		txt_scale = 1.3
		txt_ob.scale = Vector((txt_scale, txt_scale, txt_scale))
		bar = D.objects.new('Bar-' + label, mesh)
		bar.scale = Vector((1, result['win_ratio'] * 20, 1))
		bar.location = Vector((x, 0, 0))
		collection.objects.link(txt_ob) # link the objects to the collection
		collection.objects.link(bar)
		
def main():
	start_time = time.time()
	results = []
	current_prisoners = [2, 20, 50, 100, 200, 500, 1000]
	n = 100 # how many times the warden gets his sadism on
	for prisoners in current_prisoners:
		win_ratio = run_experiment(prisoners, n)
		result = { # use a struct to link the current no of prisoners to their win ratio
				'prisoners' : prisoners,
				'win_ratio' : win_ratio
			}
		results.append(result)
		print(prisoners, "prisoners:", win_ratio)
	end_time = time.time()
	print("Calculations took:", end_time - start_time) # in sec so you can plan ahead how much time it would take to increase either n or prisoners
	distance = 4 # spacing between 2 bars
	plot(results, distance)

if __name__ == "__main__":
	main()

You can probably use parts of it as snippets and even if not, it might still help you to evade the pit-fall that bpy.data.texts.new() does not create object data, you need to create a curve object data with type='FONT'.