【Project Euler】Problem 84: モノポリーの確率

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 84.モノポリーの確率

原文 Problem 84: Monopoly odds

問題の要約：モノポリーのボード上で一人で4面サイコロを2個振って移動したときに停まるマスの確率を高い順3つ並べて6桁の数字にせよ

あまりにも文章が長くて読むだけでも大変な問題。要点は、

• Community Chest(CC)とChance(CH)のマスに停まったらそれぞれ16枚のカードを引いて移動に関係ある場合だけその指示に従う。
• ゾロ目が出たら、もう一度サイコロを振れるが一人なのであまり関係がない。ただしゾロ目が3連続で出た場合だけは、Jailに移動する。
• 6面サイコロの場合は上位3マスが、JAIL (6.24%)=#10, E3 (3.18%)=#24, and GO (3.09%)=#00なので答えは102400

モンテカルロ法で解きます。乱数を使ってサイコロをたくさん振って各マスに停まった数を数えます。

まず全体の流れを見るためにメイン・プログラムから。

かなりシンプルです。サイコロを振ってChanceとCommunity ChestとGo to Jailの判定をして移動したマスのカウンター(board[bPos])をカウントアップします。

#--------- main ------------
import numpy as np

bPos = 0                     # current position of square
board = np.array([0] * 40)   # square visiting count
for i in range(100000):
  bPos = rollDice(bPos)      # roll the dices  
  bPos = handleChance(bPos)  # Handle chance
  bPos = handleCC(bPos)      # Handle CC
  if (bPos == 30): bPos = 10 # Go to Jail 
  board[bPos] += 1           # increase the square visiting count

つぎにサイコロを振るrollDice.ゾロ目の連続回数をdcountで数えます。

from random import randint
# Dice handling including doubles
dmax = 4    # max number of a dice
dcount = 0  # double continuous count
def rollDice(bPos):
  global dcount
  d1, d2 = randint(1,dmax), randint(1,dmax)
  dsum = d1+d2  
  if d1==d2: # if doubles
    dcount += 1
    if dcount > 2:  bPos, dsum, dcount = 10, 0, 0 # Go to jail
    else: dcount = 0
  bPos = (bPos + dsum) % 40    # Move the square
  return bPos

あとはCommunity Chest(handleCC)とChance(handleCC)の処理.

各々のカードは最初にシャッフルすべきでしょうが、施行回数が多いので影響ないかなと思ってやっていません。

# Chance handling
CCSquare = [2, 17, 33]       # Community Chest Squares positions
cc = [0, 10]
ccPos = 0
def handleCC(bPos):  # Community Chest
    global ccPos
    if  bPos not in CCSquare: return(bPos)
    ccPos = (ccPos+1) % 16
    if ccPos < 2: bPos = cc[ccPos]
    return(bPos)

# Chance handling
ChSquare= [7, 22, 36]   # Chance Squares
chance = [0, 10, 11, 24, 39, 5] # chance card 1-6
chPos = 0
def handleChance(bPos):
    global chPos
    if  bPos not in ChSquare: return(bPos)
    chPos = (chPos+1) % 16
    if chPos < 6: bPos = chance[chPos]
    if chPos == 6 or chPos == 7:  # Railway company
      if (bPos == 7): bPos = 15
      if (bPos == 22): bPos = 25
      if (bPos == 36): bPos = 5
    if (chPos == 8 ): # Utility company
      bPos = 8 if (bPos == 22) else 12
    if (chPos == 9): bPos -= 3
    return bPos

最後にマスのカウントデータから上位3つを取り出して、答えの6桁にします。

# Determine top 3 to make six-digit modal string.
ans = ""
for i in range(3):
  mpos = np.argmax(board)
  ans += str(mpos)
  board[mpos] = 0 # clear the value to find next max
print(f"Answer: {ans}")

（開発環境：Google Colab）