Problem 84 - Project Euler
モノポリーでどのマスに止まる確率が高いのかを求める問題。
ルールは多少単純化されているけど、モノポリーやったことないので理解するのに苦労した。例えばゾロ目が連続して出るようなとき、振るごとに移動しマスの指示に従うのか、あるいはまとめて進むのかとか。
あとCHカードの指示で戻ったときにCCに止まるとき、再度カードを引くのかどうかもわからない(その状況に陥ってさらにカードが「当たる」確率は低いので引かないことにしてしまった)。
それで面倒なのでとりあえずモンテカルロで答だけ先に出してしまおうと思ったけれど、ルールを正確に把握してないのもあってなかなか苦戦した。
で、解いてみてスレッドのぞいてみると皆シミュレーションして答出してるのでどうもそういう問題だったらしい。
ところで未だにこの単語の意味がイマイチ分かってないのだけれど、こういうのをマルコフ連鎖と呼ぶんだろうか。
board <- c("GO","A1","CC", "A2", "T1","R","B1","CH","B2","B3", "JAIL","C1","U","C2","C3","R","D1","CC","D2","D3", "FP", "E1","CH", "E2","E3","R","F1","F2","U","F3", "G2J","G1","G2","CC", "G3","R","CH","H1","T2","H2") dice <- function(now){ doubles <- 0 roll <- sample(1:4,2,replace=T) if(roll[1]==roll[2]){ doubles <- 1 } now <- now+sum(roll) if(now>40) now <- now-40 if(now==31) return(c(11, doubles)) #JAIL if(board[now]=="CC"){ com <- sample(1:16,1) if(com==1) return(c(1, doubles)) #GO if(com==2) return(c(11, doubles)) #JAIL return(c(now,doubles)) } if(board[now]=="CH"){ cha <- sample(1:16,1) if(cha==1) return(c(1, doubles)) #GO if(cha==2) return(c(11,doubles)) #JAIL if(cha==3) return(c(12,doubles)) #C1 if(cha==4) return(c(25,doubles)) #E3 if(cha==5) return(c(40,doubles)) #H2 if(cha==6) return(c(6, doubles)) #R1 if(cha==7||cha==8){ while(board[now]!="R"){ now <- now+1 if(now==41) now <- 1 } return(c(now,doubles)) } if(cha==9){ while(board[now]!="U"){ now <- now+1 if(now==41) now <- 1 } return(c(now,doubles)) } if(cha==10) return(c(now-3,doubles)) return(c(now,doubles)) } return(c(now,doubles)) } limit <- 500000 record <- numeric(limit) now <- 1 doubles.c <- 0 for(i in 1:limit){ temp <- dice(now) if(temp[2]==1){ doubles.c <- doubles.c+1 if(doubles.c==3){ record[i] <- now <- 11 doubles.c <- 0 next } } doubles.c <- 0 record[i] <- now <- temp[1] } sort(rank(table(record))) sort(table(record))