Author |
Topic: 100 prisoners & a light bulb (Read 166672 times) |
|
Hippo
Uberpuzzler
Gender: 
Posts: 919
|
 |
Re: 100 prisoners & a light bulb
« Reply #550 on: Apr 22nd, 2007, 12:51pm » |
|
As the thread is alive ... I have returned to implementation of observers method end, improving the initialisation. (Originaly I wanted to compute optimal parameters analytically ... but the time is more valuable). I have just now started genetic algorithm to find better parameters than guessed by me.
Curent average is under 3600 days.
Status:
3598.15 3598.15 3580.36 3580.36 3222 3222
10:0:11,8:1:9,7:1:8,6:1:7,5:1:6,5:1:6,4:1:6,4:1:6,4:1:6,4:1:5,3:1:5,3:1: 5,3:1:5,3:1:5,3:1:5,3:1:5|1700,600,350|418,368,354,297,269,282
... first row ... averages of different kinds, experiments count
... second row ... is my original initialisation in format:
snowball len:counter redistribution len:goal,...|
counter phase 1 len, counter phase 2 len, other counter phases len ...|
binary phase 1 len, binary phase 2 len, ..., last binary phase len is repeated.
Binary phases are in up, down, up, down ... order.
|
|
 IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a light bulb
« Reply #551 on: Apr 22nd, 2007, 11:46pm » |
|
Curent status of the genetic algorithm:
3485.55 3485.55 3553.18 3553.18 1797 1797 10:0:11,8:1:9,7:1:8,6:1:7,5:1:6,5:1:6,5:1:6,5:1:6,5:1:6,4:1:5,4:1:5,4:1: 5,4:1:5,4:1:5,4:1:5,4:1:5|1700,647,350|418,368,340,297,269,282
3485,55 is the average of all runs of genetic algorithm.
The "gen" mostly run is listed.
It was run 1797 times, 3553.18 is its average.
after a while:
3384.03 3384.03 3043.78 3043.78 2174 2174 7:0:11,4:1:8,4:1:8,3:1:7,2:1:6,2:1:6,2:1:6,2:1:6,2:1:6,2:1:6,1:1:5,1:1:5 ,1:1:5,1:1:5,1:1:5,1:1:5|1700,601,332|480,362,361,289,269,282 ...
3319.02 3319.02 3022.96 3022.96 2973 2973 7:0:11,4:1:8,4:1:8,3:1:7,2:1:6,2:1:6,2:1:6,2:1:6,2:1:6,2:1:6,1:1:5,1:1:5 ,1:1:5,1:1:5,1:1:5,1:1:5|1671,601,426|480,362,361,289,269,282 ...
3276.88 3276.88 3023.94 3023.94 3661 3661 7:0:11,4:1:8,4:1:8,3:1:7,2:1:6,2:1:6,2:1:6,2:1:6,2:1:6,2:1:6,1:1:5,1:1:5 ,1:1:5,1:1:5,1:1:5,1:1:5|1671,601,426|480,362,361,289,269,282 ...
3187.40 3186.65 2970.21 2970.21 10616 10616 7:0:11,4:1:8,4:1:8,3:1:7,2:1:6,2:1:6,2:1:6,2:1:6,2:1:6,2:1:6,1:1:5,1:1:5 ,1:1:5,1:1:5,1:1:5,1:1:5|1600,554,287|480,362,361,289,269,282 ...
3154.13 3152.12 2971.01 2971.01 13303 13303 7:0:11,4:1:8,4:1:8,3:1:7,2:1:6,2:1:6,2:1:6,2:1:6,2:1:6,2:1:6,1:1:5,1:1:5 ,1:1:5,1:1:5,1:1:5,1:1:5|1600,554,287|480,362,361,289,269,282
Now 3154.13 is the average of all runs of genetic algorithm, 3152.12 is the average of still alive gens.
I have expected breaking 3400 days barrier, but it seems I was breaking 3000 days! (Now I am approaching 2910 days, but the gen is not the major one yet). ...
2994.49 2908.78 2918.05 2918.05 22852 22852 7:0:11,4:1:8,4:1:8,3:1:7,2:1:6,2:1:6,2:1:6,2:1:6,2:1:6,2:1:6,1:1:5,1:1:5 ,1:1:5,1:1:5,1:1:5,1:1:5|1533,554,376|480,362,361,289,269,282
Damn ... there was a bug introduced ... I should correct it and rerun the algorithm ... so wait for another set of results 
Results after bug correction:
3616.20 3593.81 3484.97 3484.97 501 501 7:0:11,4:1:8,4:1:8,3:1:7,2:1:6,2:1:6,2:1:6,2:1:6,2:1:6,2:1:6,1:1:5,1:1:5 ,1:1:5,1:1:5,1:1:5,1:1:5|1700,601,332|480,362,387,289,269,282 ...
3530.24 3515.05 3504.83 3504.83 21689 21689 7:0:11,4:1:8,4:1:8,3:1:7,2:1:6,2:1:6,2:1:6,2:1:6,2:1:6,2:1:6,1:1:5,1:1:5 ,1:1:5,1:1:5,1:1:5,1:1:5|1671,601,404|480,362,361,266,269,282
I have run whole genetic algorithm once again getting folllowing result:
3534.42 3483.64 3482.73 3482.73 2904 2904 8:0:11,5:1:8,4:1:7,4:1:7,3:1:6,3:1:6,3:1:6,3:1:6,3:1:6,3:1:6,3:1:6,2:1:5 ,2:1:5,2:1:5,2:1:5,2:1:5|1717,695,529|480,362,415,289,208,311
There may be better parametrization ... different periodical len for downward phases, upward phases and the top phase, but I expect only small changes in average len. The snowballs parameters pattern ... always the same difference between the goal and snowball len may also not be optimal.
I don't know details of gypo's algorithm, but may be, simillar improvements can be obtained by genetic algorithm optimization ... so I cannot say whose algorithm is faster ... two lewel counters or one level counters with binary observers.
... Oh ... the optimised two level counters got 3460 ... so even after small improvement of my algorithm it seems this two level counters would be for 100 prisoners better.
After several restarts, current status is:
3536.38 3536.38 3478.23 3478.23 2697 2697 9:0:12,4:0:7,4:1:7,4:1:7,3:1:6,3:1:6,3:1:6,3:1:6,3:1:6,3:1:6,3:1:6,2:1:5 ,2:1:5,2:1:5,2:1:5,2:1:5|1622,554,355|480,358,361,300|314|242
(now binary phases are encoded separately for upward run, top level and downward run)
It does not seem to be much improving so the probability of beating the 3460 record is very small.
Especially the average 3536 ...
[edit]some typos corrected[/edit]
|
| « Last Edit: Mar 22nd, 2008, 4:24am by Hippo » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: 100 prisoners & a light bulb
« Reply #552 on: Apr 25th, 2007, 1:47pm » |
|
Um, could you explain in a little more detail how to turn that string of numbers into parameters for an algorithm so that I (or someone else) might be able to verify your results? 
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a light bulb
« Reply #553 on: Apr 26th, 2007, 1:21am » |
|
Current state is ...
3530.47 3530.47 3501.72 3501.72 13609 13609 9:0:12,4:0:7,4:1:7,4:1:7,3:1:6,3:1:6,3:1:6,3:1:6,3:1:6,3:1:6,3:1:6,2:1:5 ,2:1:5,2:1:5,2:1:5,2:1:5|1622,554,355|480,362,361,289|299|242
SMQ: I will try:
The "genom" is divided into 5 parts by '|'
First part represents snowball prephases,
Second part represents lengths of counter phases,
Third part lengths of binary phases when binary levels increases,
Fourth part lengths of binary phases on top level,
Fifth part lenghts of binary phases when binary levels decreases.
Division into prephase part and the rest is needed,
the division of the rest into four parts is here only because the last number on the list is repeated and it seems that these parts should behave a bit differently.
The prephase is divided into several snowballs (comma separates them in the "genom"), each snowwball into two parts. First number before colon is the number of days the snowball signalling takes (the first part), second number is the number of days the goal is reassigned, the third number is the goal the choosen counter should count to.
In the example above, there is 16 snowballs, first snowball takes 9 days, second 4 days, third 4+1 day, ....
After the snowball phases end, the counter phase starts of length 1622. After it binary phase 1 starts of length 480, after it binary phase 2 starts of length 362, after it binary phase 4 starts of length 361, after it top binary phase 8 of length 299, after it binary phase 4 of length 242, after it binary phase 2 of length 242, after it binary phase 1 of length 242, counter phase of length 554 follows, after it binary phase 1 of length 289, binary phase 2 of length 289, ....
Each prisoner starts with 1 token and 0 binaries.
During snowballs if he has token or binary, he lefts one token in the room (light on+number of tokens decrease). If he has no tokens or binaries he takes all tokens, subtracts the goal and sets binary to 1 (yes, counter have negative tokens during counting).
To prevent more binaries to be assigned to a prisoner, the goal reassignment parts are introduced ... after snowball ends, prisoner should take all tokens, subtract goal and increase its binary. But in the reassgnment part (if binary was >1) he can decrease binary and left the corresponding number of tokens here. (I suppose the same was done in optimisation of two level counting).
During binary phases prisoners can operate with all binaries except one in all cases. The last one he can use only when tokens=0. This reduces the problem to counting that all 16 binary tokens are available.
Observers end method was described earlier ... each prisoner has a knowledge of binary "amount" that "enter" given binary level. When he register on/off on the level, he knows at least 2 binary tokens on this level were unioned into binary token on higher level.
So he updates the "amount" represented by binary tokens he knows that enter the higher level.
Of course if amount which entered given level is higher then knowledge of amount on lower level, the knowledge for lower level should be increased.
The "on" on given level 2^k means amount that entered this level is at least 2^k plus amount I know entered level 2^{k+1}.
When just one binary token is not available after counter phase, the probability a prisoner whould know this at the and of downward binary phase on level 1 is high.
One should be carefull during the binary phase ending to update the knowledge appropriately (even in the case tokens<0). ... this was the source of (serie of) bugs mentioned above.
I have reread the posts leading to 3460 days ... you used almost the same prephase ... except not using reassignment parts. Also you don't try to optimise the phase lengths. You use the lengths given by informed guess ... So may be, I will rerun the genetic algorithm for two stage process later to try to optimise the parameters.
One more thing ... I forgot to mention there is 2-3 day hook (from 5A2 forum) in the first snowball used.
[edit]some typos corrected[/edit]
|
| « Last Edit: Mar 22nd, 2008, 4:35am by Hippo » |
IP Logged |
|
|
|
Rezyk
Junior Member
Gender:
Posts: 85
|
|
Re: 100 prisoners & a light bulb
« Reply #554 on: Apr 26th, 2007, 5:56pm » |
|
That explanation was a bit hard to follow for me; here is a guesswork-reinterpretation of it, along with pseudocode. (Can you see if it looks equivalent, Hippo?) I switch some terminology from:
"binary" to "badge"
Instead of each badge being assigned a token collection goal, they come with an equivalent token deficit that is summed into the individual prisoner's token count, and can be passed around as negative tokens.
100 tokens are loaned out and distributed, one to each prisoner. To pay back the loan, each of the 16 snowball rounds generates one badge which comes with part of the deficit, and that must be paid off before the badge can be used to win. Counter phases try to pay off deficits by moving tokens to badge holders one at a time. The paid-off badges are gathered together in binary groupings; win when a prisoner can deduce that all 16 have been paid off.
main() {
Set each inventory to 1 token.
snowball(9, 0, 12)
snowball(4, 0, 7)
snowball(4, 1, 7)
snowball(4, 1, 7)
repeat 7 times: snowball(3, 1, 6)
repeat 5 times: snowball(2, 1, 5)
set i = 1
repeat indefinitely: {
//1622,554,355|480,362,361,289|299|242
next (i==1?1622 : i==2?544 : 355) days: If tokens>0, pass 1 token. //counter phase
next (i==1?480 : 289) days: If badges%2>=1 and tokens>=0, pass 1 badge.
next (i==1?362 : 289) days: If badges%4>=2 and tokens>=0, pass 2 badges.
next (i==1?361 : 289) days: If badges%8>=4 and tokens>=0, pass 4 badges.
next 299 days: If badges%16>=8 and tokens>=0, pass 8 badges.
next 242 days: If badges%8>=4 and tokens>=0, pass 4 badges.
next 242 days: If badges%4>=2 and tokens>=0, pass 2 badges.
next 242 days: If badges%2>=1 and tokens>=0, pass 1 badge.
set i = i+1
}
}
snowball(buildupLength, reassignLength, deficit) {
subday 1: Create 1 badge and -deficit tokens. If badges>1 or (badges==1 and tokens>=-deficit+1), pass 1 badge and -deficit+1 tokens.
subday 2 through buildupLength: If badges>1 or (badges==1 and tokens>=-deficit+subday), pass 1 badge and -deficit+subday tokens.
next reassignLength days: If badges>1, pass 1 badge and -deficit+buildupLength tokens.
}
The simple win condition is collecting all 16 badges and having exactly zero tokens (no remaining deficit). One can also win by a deducing the number of active badges. For this, each prisoner independently tracks their answers to these:
Have I witnessed an 8-group of active badges?
Have I witnessed an 8-group of active badges, and then a free 4-group?
Have I witnessed an 8-group of active badges, and then a free 4-group, and then a free 2-group?
Have I witnessed an 8-group of active badges, and then a free 4-group, and then a free 2-group, and then a free 1-group?
Whenever a prisoner forms a new group of badges or pays off a deficit, a win can be declared if newGroupSize+witnessedGroupsSize=16.
|
| « Last Edit: Apr 26th, 2007, 6:51pm by Rezyk » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a light bulb
« Reply #555 on: Apr 27th, 2007, 1:06am » |
|
on Apr 26th, 2007, 5:56pm, Rezyk wrote:That explanation was a bit hard to follow for me; here is a guesswork-reinterpretation of it, along with pseudocode. (Can you see if it looks equivalent, Hippo?) I switch some terminology from:
"binary" to "badge"
Instead of each badge being assigned a token collection goal, they come with an equivalent token deficit that is summed into the individual prisoner's token count, and can be passed around as negative tokens.
|
|
Almost. Subtracting 7 tokens is equivalent to define goal 7. Negative tokens are passed only during 2nd part of snowballs (reassigning goals). Sorry ... yes in passing terminology you send negative tokens.
Quote:
100 tokens are loaned out and distributed, one to each prisoner. To pay back the loan, each of the 16 snowball rounds generates one badge which comes with part of the deficit, and that must be paid off before the badge can be used to win. Counter phases try to pay off deficits by moving tokens to badge holders one at a time. The paid-off badges are gathered together in binary groupings; win when a prisoner can deduce that all 16 have been paid off.
|
|
There should be specified what happens when two badges are assigned to a prisoner ... only the last one waits for all being paid, others are available.
Quote:
main() {
Set each inventory to 1 token.
snowball(9, 0, 12)
snowball(4, 0, 7)
snowball(4, 1, 7)
snowball(4, 1, 7)
repeat 7 times: snowball(3, 1, 6)
repeat 5 times: snowball(2, 1, 5)
set i = 1
repeat indefinitely: {
//1622,554,355|480,362,361,289|299|242
next (i==1?1622 : i==2?544 : 355) days: If tokens>0, pass 1 token. //counter phase
next (i==1?480 : 289) days: If badges%2>=1 and tokens>=0, pass 1 badge.
next (i==1?362 : 289) days: If badges%4>=2 and tokens>=0, pass 2 badges.
next (i==1?361 : 289) days: If badges%8>=4 and tokens>=0, pass 4 badges.
next 299 days: If badges%16>=8 and tokens>=0, pass 8 badges.
next 242 days: If badges%8>=4 and tokens>=0, pass 4 badges.
next 242 days: If badges%4>=2 and tokens>=0, pass 2 badges.
next 242 days: If badges%2>=1 and tokens>=0, pass 1 badge.
set i = i+1
}
}
|
|
[edit]12-03-2008
Oops, I have chosed codding in which prephases are included in the first phase so 1622 should be replaced by
1622-9-4-2*5-7*4-5*3 in the code.[/edit]
All expressions with badges%2^i>=2^i and tokens>=0 should be changed to ((badges-(?tokens>=0;0;1))%2^i)
Quote:
snowball(buildupLength, reassignLength, deficit) {
subday 1: Create 1 badge and -deficit tokens. If badges>1 or (badges==1 and tokens>=-deficit+1), pass 1 badge and -deficit+1 tokens.
subday 2 through buildupLength: If badges>1 or (badges==1 and tokens>=-deficit+subday), pass 1 badge and -deficit+subday tokens.
next reassignLength days: If badges>1, pass 1 badge and -deficit+buildupLength tokens.
}
|
|
Yes, it seems to be correctly translated to the "passing" terminology.
Edited 12-may-07: Except there is hook in the first snowball with high probability preventing collecting just one token (see 5 prisoners and a light bulb forum for details ... it saves less than 1 day anyway.)
Edited 26-nov-08: Behaviour of (badges==1 and tokens>=-deficit+subday) seems to be worse than (badges==1 and tokens=-deficit+subday). May be (badges==1 and (tokens>=-deficit+subday) and (tokens<-deficit+subday+2)) would be acceptable. ... snowball restarting paid by more tokens in hand of common prisoner seems to be too expensive.
Quote:
The simple win condition is collecting all 16 badges and having exactly zero tokens (no remaining deficit).
|
|
Yes of course, but this condition neednot be tested separately, it is special case of the following win condition. The condition giving the algorithm robustness ... as all prisoners are very likely to be well informed ...
Quote:
One can also win by a deducing the number of active badges. For this, each prisoner independently tracks their answers to these:
Have I witnessed an 8-group of active badges?
Have I witnessed an 8-group of active badges, and then a free 4-group?
Have I witnessed an 8-group of active badges, and then a free 4-group, and then a free 2-group?
Have I witnessed an 8-group of active badges, and then a free 4-group, and then a free 2-group, and then a free 1-group?
Whenever a prisoner forms a new group of badges or pays off a deficit, a win can be declared if newGroupSize+witnessedGroupsSize=16. |
|
Yes, typical example is seeing on,off,on,off during 4 badges phase.
First gives information ... there is a 4-group.
Second gives ... there is an 8-group
Third gives ... there is a 4-group and (I know also 8-group)
Fourth gives ... there is 2nd 8-group ... what is amount of 16 so we are done.
But if the same prisoner sees on,off,on during 4-badges phase and later on,off during 2-badges phase, he knows the amount in 4-groups and 8-groups was at least 12, now another 4-group is created so their amount is 16 and we are again done.
If a prisoner switches light ... he sees both states, but only if it is not forced nonintended switch during the phase end.
|
| « Last Edit: Dec 3rd, 2008, 7:00am by Hippo » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a light bulb
« Reply #556 on: May 9th, 2007, 1:57am » |
|
P.S.: Actual state of genetic algoritmh:
3526.80 3526.80 3511.31 3511.31 24390 24390 9:0:12,4:0:7,4:1:7,4:1:7,3:1:6,3:1:6,3:1:6,3:1:6,3:1:6,3:1:6,3:1:6,2:1:5 ,2:1:5,2:1:5,2:1:5,2:1:5|1622,554,355|480,362,361,289|299|242
The final state is:
3489.57 3489.57 3483.78 3483.78261756 261756
6:0:9,5:0:8,4:0:7,4:0:7,4:0:7,3:0:6,3:1:6,3:1:6,3:1:6,3:1:6,3:1:6,3:1:6, 2:1:5,2:1:5,2:1:5,2:1:5|1668,554,362|495,367,361,289|313|269
The state for two counter phases started recently:
3518.17 3518.17 3472.10 3472.10 2038 2038 8:0:13,5:0:10,5:0:10,5:0:10,5:0:10,5:1:10,5:1:10,5:1:10,4:1:9,3:1:8|1988 ,1584,268
3515.24 3515.24 3488.22 3488.22 3332 3332 8:0:13,5:0:10,5:0:10,5:0:10,5:0:10,5:1:10,5:1:10,5:1:10,4:1:9,3:1:8|1988 ,1584,268
3502.26 3502.26 3473.11 3473.11 9134 9134 8:0:13,5:0:10,5:0:10,5:0:10,5:0:10,5:1:10,5:1:10,5:1:10,4:1:9,3:1:8|1997 ,1652,343
I have let the algorithm to "restart" after 10^6 simulations. The state before restart follows:
3487.97 3487.97 3467.95 3467.95 79493 79493 8:0:13,6:0:11,5:0:10,5:0:10,5:0:10,5:0:10,5:1:10,4:1:9,4:1:9,3:1:8|1929, 1582,387
Current status is:
3485.89 3485.89 3470.42 3470.42 22565 22565 7:0:12,5:0:10,5:0:10,5:0:10,5:0:10,5:1:10,5:1:10,5:1:10,4:1:9,4:1:9|1965 ,1646,336
[26.11.08 text above moved from the previous post]
The final state of binary-observers is:
3489.57 3489.57 3483.78 3483.78261756 261756
6:0:9,5:0:8,4:0:7,4:0:7,4:0:7,3:0:6,3:1:6,3:1:6,3:1:6,3:1:6,3:1:6,3:1:6, 2:1:5,2:1:5,2:1:5,2:1:5 |1668,554,362|495,367,361,289|313|269
The final state of two stage counters is:
3485.19 3485.19 3467.06 3467.06 310426 310426 9:0:14,6:0:11,6:0:11,5:0:10,5:1:10,4:1:9,4:1:9,4:1:9,4:1:9,3:1:8 |1973,1663,404
BTW: You can see the unstability of the algorithm as small mutations change average to 3485 while these parameters give 3467.
Second most common gen was
8:0:13,7:0:12,6:0:11,5:1:10,4:1:9,4:1:9,4:1:9,4:1:9,4:1:9,4:1:9|1973,166 3,404
with average 3473.35 form 116695 experiments.
May be, my initialisation is worse than yours, but so far it does not seem to approach 3460 days. The simulation shows that for 100 prisoners two stages couning is better than binary-observers method.
(At least the local minimum of observers method is above the minimum of two stages method).
The simulation results are based on pseudorandom generator this is the main source of inaccuracy.
I can change mutation in the way the goals in optimal case are not equal but have g,g,g,g,..,g,g+1,g+1,g+1,...,g+1 shape but I guess improvement in such a case cannot exceed 8 days ... I expect 1 or 2 days improvement.
|
| « Last Edit: Dec 1st, 2008, 2:23pm by Hippo » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: 100 prisoners & a light bulb
« Reply #557 on: May 9th, 2007, 2:20pm » |
|
On the trail of the elusive marker-token:
Since first reading through this thread years ago I've been searching for a way to combine the strong start of a token-based strategy (leader, badges&crowns, etc.) with the strong finish of a marker-based (distribution) strategy. Well, here's a possibility. It clearly loses to any of the token strategies -- even single-leader -- but I believe once tuned it will beat any of the existing distribution strategies, and at least it's somewhat novel.
Maybe it will spark some fresh ideas. Or maybe it's just crap. 
Basically it's a way to hand out the numbers 1-100 for a distribution scheme reasonably efficiently, but there's a large penalty for failure of that portion of the scheme. I hope to have simulation results available in the next couple days.
Stage 1: Assignment.
This stage is divided into 100 rounds numbered 1 through 100 of varying lengths, from a few days to a few hundred days as roughly C*100/(101 - n) for round n with C fairly small. In each round, the first prisoner to enter who has not yet been assigned a number assigns himself number n and turns on the light. Any other prisoner who sees the light on remembers that prisoner n has visited (distribution scheme). If any number goes unassigned (the light is still off at the end of the round), either the last prisoner of that round or the first prisoner of the next round must remember that the number is unassigned -- it will be his responsibility to try to get it reassigned in a later stage.
Stage 2: Distribution
Just like any other distribution scheme: divide into 100 equal-length rounds (rmsgrey's work suggests 30-70 days per round may be roughly optimal), if prisoner n enters during round n he turns on the light; anyone observing the light on notes that prisoner n has entered; if anyone observes all 100 have entered he declares victory.
Stage 3: Reassignment
Here's where the major penalty comes in if stage 1 failed. Divide into 100 equal-length rounds of, maybe, 150-ish days each. In each round, if a prisoner enters who knows that n is still unassigned, he turns on the light. After that, if any prisoner enters who was not yet assigned a number he assigns himself number n and turns off the light. If the last prisoner of the round (or the first of the next) finds the light on, he remembers that n is still unassigned.
Repeat stages 2 & 3 as necessary.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a light bulb
« Reply #558 on: May 9th, 2007, 3:08pm » |
|
SMQ: You can almost translate this into token terminology in the following way:
There are tokens of 100 different kinds.
Assignment ... assigns token to a prisoner without a token so far and after that distribution subphase starts ... there is signal left for other prisoners improving their knowledge about token assignment. If the assignment failed a prisoner gets second token.
Distribution subphase ... does nothing unless the only prisoner with current kind of token enters. After that knowledge may be distributed.
Reassignment subphase ... does nothing unless the only prisoner with current kind of token enters after that does nothing unless a prisoner without a token enters. After that knowledge may be distributed.
This will be ineffective as it requires a lot of phase switching, You cannot know which phases are not required. The Distribution and Reassignment phase lengths should be longer than 100 days (probably 200 days) as they do nothing if the prisoner with the token does not enter. If a reassignment fails you must wait at least whole cycle of reassignments ... One cycle takes at least 20000 days .... (oh sorry ... tokens with small numbers are assigned well with higher probability, but it is surely more than 5000 days)
Oh sorry once again ... the method neednot be so bad ... the distribution phases does not wait for the only prisoner with the corresponding token but to anybody who knows the token was assigned. The problems are only with error recovery ... with the redistribution phases.
The Assignment phases should be long enough to have the fail probability to say 1/1000 (advantage is that assignment phases serve as distribution phases as well). ... in such a case fail of all assignment phases will be with probability around 1/10 what may be OK.
But if I understand it well, the process cannot end unless a prisoner enters the room 99times.
I have tried to approximate the probability a prisoner enters the room 99times before day 5000.
... it gave me something like 20000/2100 ... so don't expect to make a new record. Sorry once again ... this is not good approximation!!
Better approximation is 20000e50/2100=eln 20000+50-100ln 2 approx e-9.41.
Back to the search for optimal parameters of two level counting or counting with binary observers:
I have made the change to allow small increase of "optimal goals" in mutations. Furthermore, I have changed meaning of the first phase length ... it starts now on day 0 so prephases are part of its time. I hope this would improve the genetic algorithm stability. ... so wait another two weeks for results
|
| « Last Edit: May 10th, 2007, 7:24am by Hippo » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2872
|
|
Re: 100 prisoners & a light bulb
« Reply #559 on: May 10th, 2007, 7:59am » |
|
A trivial optimisation for SMQ's latest proposal: everyone knows that the prisoner who enters on day 1 will have token 1 and have been into the room, which means that you don't need to consider him in any future signalling. It may be worth throwing a snowball in early as well - rather than passing out copies of token 2, instead aim to pass out copies of tokens 2,3 and 4 simultaneously. You probably want to be reasonably conservative with such snowballs - using them saves maybe 50 days per additional number, but costs a lot when they miss.
In any case, you want the initial assignment sub-phases (apart from day 1) to all be long enough to get a reasonable number of copies of the phase token out there - otherwise you lose the major advantage of dynamic label assignment - not having to wait for a specified prisoner to visit to start copying a given labelled token.
There's a fairly obvious improvement to the reassignment phase too: rather than trying to pass labels to unlabelled prisoners, pass unlabelled tokens to prisoners with spare labels.
Rather than multiple numbered subphases, in which things will only happen if that label hasn't yet been assigned, have a single reassignment phase in which prisoners with unlabelled tokens pass their token at the first opportunity, and prisoners with an unassigned label collect any token that comes there way and label it. That way, the entire phase is potentially useful as long as there's any unassigned labels rather than 90%+ of it being wasted time.
Terminology:
Each prisoner starts with an unlabelled token.
During the assignment phase, 100 labels are created and handed out - where possible, to prisoners with an unlabelled token. Any time a prisoner has an unlabelled token and one or more labels, he labels the token with the lowest rank label.
Labelled tokens are automatically copied by anyone who sees them, and copies are passed around during the appropriate subphases of the assignment and distribution phases.
As soon as a prisoner sees 100 different tokens, he can claim victory.
It's also possible to generate a victory during a reassignment phase if someone sees enough unlabelled tokens pass by, or during a distribution phase if someone with an unlabelled token collects 99 labelled tokens...
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a light bulb
« Reply #560 on: May 10th, 2007, 1:24pm » |
|
SMQ, rmsgrey: Snowballs reduces the number of required visits of the prisoner declaring victory from 99 to say 90 ... depends on the snowball total lengths.
The probability a prisoner enters the room 90 times during first 5000 days remains negligible so this cannot beat the best algorithms. (You even cannot expect all the visits are usefull ...)
I don't understand the anonymous reassignment ... in this method you need to know the token "name" to be able to distribute the information later. With anonymous token you cannot do that.
Wait! ... Oh yes, there is a possibility ... when accepting anonymous token you create "new name" for it. So there will be more than 100 kinds of distribution phases (some of them having nothing to distribute).
Back to the finding optimal parameters:
I have checked mutation strategy and find some problems. ... The results after their correction seemed to be interesting ...
One more thing: I plan to run genetic algorithm also for variant with 8 counters ... therefore saving one binary level. This will prolong first phase around 650 days what would be compansated later I hope.
It seems all three methods are roughly equal.
3500.79 3500.79 3468.37 3468.37 283705 283705 9:0:14,6:0:11,5:0:10,5:1:10,5:1:10,4:1:9,4:1:9,4:1:9,4:1:9,4:1:9| 2015,1744,481
3526.40 3526.40 3471.83 3471.83 19345 19345 6:0:9,6:0:8,5:0:7,5:0:7,4:0:6,4:0:6,4:0:6,4:0:6,4:0:6,4:0:6,4:0:6,4:0:6, 4:0:6,3:0:5,3:1:5,3:1:5|1749,554,362|493,367,361,289|313|269
3493.37 3493.13 3472.99 3472.99 1231 1231 12:0:17,10:0:15,8:0:13,7:1:12,6:1:11,6:1:11,6:1:11,5:1:10|2263,554,411 |349,361,289,280|268|269
I would change parametrisation for 16binary adding one parameter to upward runs. The average of all runs is best for 8binary. 8binary is far for achieving its minimum ... even the upward binary string is nondecreasing.
Hmm, it seems to me that genetic algorithm could work for weeks and not to approach optimal values . As the quality of results is bounded by quality of pseudorandom generator I stop this experiment.
So far the two level counting scheme is the best one with average around 3470, observers method with either 8 or 16 counetrs have average around 3490.
|
| « Last Edit: May 19th, 2007, 10:05pm by Hippo » |
IP Logged |
|
|
|
AL007
Newbie
Posts: 1
|
|
Re: 100 prisoners & a light bulb
« Reply #561 on: May 30th, 2007, 9:08am » |
|
I have spent a good part of the last few days reading these 20+ pages and have found the evolution of the optimal solution fascinating! I complement all of the bright and creative people involved.
If anyone is still interested, there is a legitimate way to at least double the bandwidth and significantly shorten the problem. About two years ago Grimbal stated: " It doesn't matter how long a bulb can last. It will get replaced. Or not. The important thing is whether the switch is up or down."
Therefore, we have at least four states: switch up with bulb on, switch up with bulb off (unscrewed), switch down but will turn on, and switch down and won't turn on (unscrewed). Additionally, most switches will stay at the midpoint, so we may have five states.
Of course, if we allow this we could measure how far the bulb was unscrewed and add even more bandwidth. File this with the other cheats. . . .
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a light bulb
« Reply #562 on: May 30th, 2007, 12:59pm » |
|
Hmm ... you have read 20+ pages so you know, this "solution" is not what are we interested on.
I agree with the observation the bulb is not important - the switch is important, but in this riddle we are talking about one bit of information "problem".
If you are interested in switches with more states ... there is another thread.
|
| « Last Edit: May 30th, 2007, 1:01pm by Hippo » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: 100 prisoners & a light bulb
« Reply #563 on: May 31st, 2007, 5:44pm » |
|
And I'm pretty sure both the intermediate switch state and the partially loosened bulb have been suggested in the past (in fact, I think I may have been the one to suggest the 3-state switch)
|
|
IP Logged |
|
|
|
srn437
Newbie
the dark lord rises again....
Posts: 1
|
|
Re: 100 prisoners & a light bulb
« Reply #564 on: Aug 29th, 2007, 11:59am » |
|
The first one turns it on(unless it's already on)and draws a tally mark on the wall). Everyone who enters sees the tally mark(s) and adds one. When a person sees 100 after drawing theirs, they say they were the 100th person. If counting 100 in groups of 5 is to much for them, they group the groups of 5 into groups of 5 groups by circling every 5 groups in one circle.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a light bulb
« Reply #565 on: Aug 29th, 2007, 3:12pm » |
|
on Aug 29th, 2007, 11:59am, srn347 wrote:| The first one turns it on(unless it's already on)and draws a tally mark on the wall). Everyone who enters sees the tally mark(s) and adds one. When a person sees 100 after drawing theirs, they say they were the 100th person. If counting 100 in groups of 5 is to much for them, they group the groups of 5 into groups of 5 groups by circling every 5 groups in one circle. |
|
You must be a genius, 23 pages and noone found such solution ... please read it first, don't spam it
|
| « Last Edit: Aug 29th, 2007, 3:13pm by Hippo » |
IP Logged |
|
|
|
srn437
Newbie
the dark lord rises again....
Posts: 1
|
|
Re: 100 prisoners & a light bulb
« Reply #566 on: Aug 29th, 2007, 4:48pm » |
|
Read 23 long pages?! I will if you try the 3 nearly impossible riddles post.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: 100 prisoners & a light bulb
« Reply #567 on: Aug 30th, 2007, 2:10am » |
|
on Aug 29th, 2007, 4:48pm, srn347 wrote:| Read 23 long pages?! I will if you try the 3 nearly impossible riddles post. |
|
Just reading the first page would have done. Reply #13 includes an energy saving tip that your version overlooks
|
|
IP Logged |
|
|
|
Wardub
Junior Member
Gender:
Posts: 130
|
|
Re: 100 prisoners & a light bulb
« Reply #568 on: Sep 11th, 2007, 10:08pm » |
|
um could someone help me out? im not as smart as most of you, and im trying to figure out how the solution given by Gypo works. Im confused on stage 0. i assume the bulb is off initially? but doesn't turn off at the end of each cycle correct?
Im just confused on the wording.
For cycle 0, Quote:| If he now has one or more tokens or one or more badge, he turns the light on and subtracts one token from his inventory, even if he ends up with a negative number of tokens. If the prisoner has no tokens and no badges, he switches the light off and gets a badge. |
|
do i do this no matter the if the bulbs on or off?
After this step what is suppose to happen? theres suppose to be 10 people with badges right? and 1 witha crown? what about tokens im confused about this. how are you suppose to count people going through the first 40 days and how do those people know if they are counted or not? Sry if this doesn't make much sense just ask me and ill try to clarify.
|
| « Last Edit: Sep 11th, 2007, 10:08pm by Wardub » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: 100 prisoners & a light bulb
« Reply #569 on: Sep 12th, 2007, 6:08am » |
|
Sounds like you're close, Wardub; it took me a while to grasp what was going on in that stage too.
The first round of stage 0 is a little special:
- Everyone starts out with one token and nothing else.
- On day one (only), the prisoner who enters turns the light on (if it isn't already), and mentally "drops" his token.
- On day two (only), if the same prisoner enters again, he mentally "picks up" his token, "gets" a badge and a crown, and turns the light off (to signal that the first badge has been assigned). Otherwise, if a different prisoner enters, he mentally "drops" his token and leaves the light on.
- On days 3 and 4, if the light is already off (signaling that the first badge has been assigned already), the prisoner who enters does nothing. If the light is on and the prisoner has a token, he mentally "drops" it and leaves the light on; otherwise he "picks up" a number of tokens equal to the number of days that have passed, "gets" a badge and a crown, and turns the light off.
Then there are nine rounds that are all the same:
- On day 5, 9, 13, etc. If the light is on when a prisoner enters (indicating that no badge was assigned in the previous round) he picks up four tokens, gets a badge (and a crown iff it is day 5), and turns the light off. Now the procedure you quoted above happens (with the light always off to begin): If he has any tokens or any badges, he drops a token (even if that means he now has -1 tokens) and turns the light on; otherwise he leaves the light off and gets a badge.
- On all other days, things proceed as in days three and four: nothing happens if the light is off, otherwise the prisoner drops a token if he has one, or takes the accumulated tokens for the round and gets a badge (but not a crown) if not.
Finally, before other instructions, at the start of day 41, if the light is on, the prisoner picks up four tokens, gets a badge, and turns the light off.
At this point, ten badges and a crown have been assigned, and the total of all prisoners mental token counts is 100 (every token that was "dropped" was later "picked up"), even in the extremely unlucky case that one (or worse, more) of the prisoners with a badge has a negative count. With a bit of luck, no prisoner has more than one badge, and the prisoners with badges all have more than one token counted already.
From here, things go much simpler. Stage 1 (remember that we start with the light off possibly after a prisoner picked up the final basge first thing on day 41):
- If a prisoner has a token but no badge, and the light is off, he drops his token and turns the light on.
- If a prisoner has a badge and less than 10 tokens (or two badges and less than 20 tokens, etc.), and the light is on, he picks up the token and turns the light off.
- In all other situations, nothing happens.
At the start of the first day after stage 1, if the light is on, the prisoner turns it off and picks up a token, whether or not he has a badge. (Don't want to lose that token!) This way tokens are "passed" to the prisoners with badges, up to 10 tokens per badge.
Then, stage 2, like stage 1 but a "level up" (again starting with the light off from the last act of stage 1):
- If a prisoner has one or more badges and at least 10 tokens, and the light is off, he drops one badge, subtracts 10 tokens, and turns the light on.
- If a prisoner has the crown, and the light is on, he picks up the badge (and 10 tokens) and turns the light off. If he now has 10 badges (or, equivalently 100 tokens) he declares victory.
- In all other situations, nothing happens.
This way "filled" badges are passed to the single prisoner with the crown; once he has them all, he knows all 100 tokens are accounted for, and he declares victory. If at the end of Stage 2 there is no victory, every keeps what they have and repeast stage 1, then stage 2, etc. until victory is finally declared.
Hope that makes things clearer!
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Wardub
Junior Member
Gender:
Posts: 130
|
|
Re: 100 prisoners & a light bulb
« Reply #570 on: Sep 12th, 2007, 10:26am » |
|
thanks, i don't have time to read it all now, i have class, but i think i will be able to understand.
Also i found 2 special cases, i read the whole thread a while ago and i no you guys caught the case where the light is still on, on the last day of the cycle. but i found another "special case" but im pretty sure you have found it also, because you're all so smart. anyways
when i made my program, im very new to it so i used lots of whiles and ifs and stuff. anyway i only made the win scenario if the second cycle. but i found out there is a slight possibility that you can declare a win in the first cycle, its easy to see if you actually were doing this riddle, but pretty easy to overlook while programming.
if after the first time through the first 2300 day cycle, all the assistant counters have filled their badges but the Lead counter or w/e hasn't filled his. then if he counts all 9 assistant counters, then he knows that when he completes his badge then every prisoner has been through. so in my program if 100 days in to the second time through the first cycle, the lead counter fills his badge he can declare a win, but in my program the program would wait till cycle 2 and then declare a win adding on like 1000 days. Im sure you guys have already found this out, but w/e it probaby doesn't shave off even .1days after 1,000,000 times because its chances of happening are rare
|
|
IP Logged |
|
|
|
Wardub
Junior Member
Gender:
Posts: 130
|
|
Re: 100 prisoners & a light bulb
« Reply #571 on: Sep 15th, 2007, 7:50pm » |
|
ok i finally understand stage 0, but i have questions, it says that it will get rid of the problem with prisoners having multiple badges, but it looks like prisoners can still get multiple badges if their the first person in on the start of the cycle and the light is on , and they have atleast one badge. also does anyone have code for stage 0? could someone post it?
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 100 prisoners & a light bulb
« Reply #572 on: Sep 16th, 2007, 12:25pm » |
|
See the top third of the 23page ... the Rezyk one
... the snowball phases do not differ ...
in the pass (something) terminology you either switch light off or you let it on and subtract corresponding (something) from your inventory and virtualy let it in the room.
The amount is uniquely defined by the night number!
Who enters with the light on starts with grabbing (something).
----
And yes, you cannot prevent to have more badges in the same hand. You only can minimize the probability of it happen. ... There is nonzero but very very small probability all the first 10000 days the same prisoner enters ...
|
| « Last Edit: Sep 17th, 2007, 1:06am by Hippo » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: 100 prisoners & a light bulb
« Reply #573 on: Sep 17th, 2007, 6:12am » |
|
on Sep 15th, 2007, 7:50pm, Wardub wrote:| also does anyone have code for stage 0? could someone post it? |
|
already did.
To get exactly gypo's algorithm, set all badgesizes to 10 (except the first 0) and all rounddays to 4 (except for the first 0) at the top. Also be aware that the code as posted overcounts by one day. You can change int totaldays = 1 to int totaldays = 0 at the start of the second section to fix it.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
mzbach22
Newbie
Posts: 1
|
|
Re: 100 prisoners & a light bulb
« Reply #574 on: Jan 2nd, 2008, 10:13pm » |
|
I haven't read the entire forum; so, please excuse me if I am re-suggesting an idea.
The first prisoner / (day one) breaks the light bulb into 100 pieces. (The prisoner will know he/she is the first because the light bulb will still be whole). Then that prisoner takes one shard of the light bulb and leaves the rest in the room. As long as the prisoners only take one shard each (and they are very careful not to break the shards when entering the room) then the prisoner who enters the room and finds no shards declares that all the prisoners have been in the room.
The only potential problem may be that there is no light for the prisoners to see the shards. In that case, the first prisoner who shatters the light bulb arranges it into a 50 x 50 square and the prisoners all take one pieces from the lower right corner and snake their way up.
Another solution. Take the filament out of the light bulb and straighten it. The first prisoner makes a small bend in the filament. The second makes another small bend. Finally one hundred bends will be made and the last prisoner (albeit they have to count a lot of tiny bends) will be able to declare that everyone has been there.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Notify of replies
Send Topic
Print