HoverHell comments on The Absent-Minded Driver - Less Wrong

27 Post author: Wei_Dai 16 September 2009 12:51AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Article Navigation

Comments (139)
Tags: udt absentminded_driver

Comments (139)

You are viewing a single comment's thread. Show more comments above.

Comment author: gwern 02 February 2011 09:37:57PM *  4 points [-]

In #lesswrong, me, Boxo, and Hyphen-ated each wrote a simple simulation/calculation of the absent-minded driver and checked how the various strategies did. Our results:

  • 1/3 = 1.3337, 1.3338174; Hyphen-ated: 1.33332; Boxo: 1.3333333333333335
  • 1/4 = 1.3127752; Hyphen-ated: 1.31247; Boxo: 1.3125
  • 2/3 = 0.9882
  • 4/9 = 1.2745, 1.2898, 1.299709, 1.297746, 1.297292, 1.2968815; Hyphen-ated: 1.29634; Boxo: 1.2962962962962963

As expected, 4/9 does distinctly worse than 1/3, which is the best strategy of the ones we tested. I'm a little surprised at Piccione & Rubinstein - didn't they run any quick* little simulation to see whether 4/9 was beaten by another probability or did they realize this and had some reason bad performance was justifiable? (I haven't read P&R's paper.)

Boxo used his UDT in Haskell code ([eu (Strategy $ const $ chance p) absentMinded id | p <- [0, 1/2, 1/3, 1/4, 4/9]]); I used some quick and dirty Haskell pasted below; and I don't know what Hyphen-ated used.

import System.Random
import Control.Monad
main = foo >>= print -- test out the 1/4 strategy. obvious how to adapt
foo = let n = 10000000 in fmap (\x -> fromIntegral (sum x) / fromIntegral n) $ replicateM n run
run = do x <- getStdRandom (randomR (1,4))
y <- getStdRandom (randomR (1,4))
return $ trial x y
trial :: Int -> Int -> Int
trial x y | x == 1 = 0 -- exit at first turn with reward 0
| y == 1 = 4 -- second turn, reward 4
| otherwise = 1 -- missed both, reward 1

* It's not like this is a complex simulation. I'm not familiar with Haskell's System.Random so it took perhaps 20 or 30 minutes to get something working and then another 20 or 30 minutes to run the simulations with 1 or 10 million iterations because it's not optimized code, but Boxo and Hyphen-ated worked even faster than that.

Comment author: HoverHell 31 December 2011 08:23:18PM 1 point [-]

Another variation of simulation, in Python, and bit more defined strategy-abstraction (though written for improving own understanding anyway):

from __future__ import division
import random
def run(strt): # compute (possibly stochastic) outcome of strategy execution
docont = strt() # ... no arguments.
if not docont: # at intersection X
return 0
docont = strt()
if not docont:
return 4
return 1
def evst(strt, fun=run, n=100): # evaluate strategy by running `n` times
r = 0.0
for i in range(n):
r += fun(strt)
return r/n
""" # sample use:
> ra = [(v/30, evst(lambda: random.random() < v/30, n=30000)) for v in range(30)]
> max(ra, key=lambda v: v[1]) # maximal stochastic value and its `p`
(0.6666666666666666, 1.3515666666666666)
"""
Powered by Reddit Powered by Reddit