文献あり

「100人の囚人問題」のシミュレーションをブラウザで実行する

118

はじめに

「100人の囚人問題」というパズルがあります。

100人の囚人問題

ある部屋に100人集められている。別の部屋に100個のロッカーがあり、それぞれのロッカーには100人のうち1人の名前が書かれた紙が入れてある。
順番を決め、1人がロッカーの部屋に入り、50個のロッカーを開ける。その中に自分の名前があれば、ロッカーを元の状態に戻し、次の人がロッカー部屋に入り、同様に50個のロッカーを開ける。これを繰り返し、100人が皆自分の名前を見つけられたらゲームは成功。1人でも名前が見つけられなければゲームは失敗である。
100人はゲームを始める前に議論し戦略を決めることができる。ただしゲームが始まったらお互いに話すこと・情報を伝えることはできない。
このゲームにおいて、30%以上の確率で成功する戦略を考えよ。

一見不可能そうな問題ですが、これを実現する戦略が存在します（下の▶をクリック）。

解答

【Pointer following】
人とロッカーに番号をふる。$i$番目の人はまず$i$番目のロッカーを開ける。その中に入っている人の名前に対応する番号のロッカーを次に開ける。これを繰り返し、50個のロッカーを開ける。${}_\blacksquare$

これに関してかつて記事を書きました：

100人の囚人問題: 最善の戦略は？その1
100人の囚人問題: 最善の戦略は？その2

こんな記事を書いてはいますが、私のような凡人にはこの問題を自力で解くことはできませんでした。それどころか、解答を聞いてもこの戦略で成功率が30%を超えるとは信じられませんでした。そこでシミュレーションコードを書いて動かしてみたところ確かに30%を超えることがわかり、初めてこの戦略が正しいことを理解しました。

100人の囚人問題のシミュレーションコード自体は単純ですが、コードの実行環境を用意しなければならないのがネックです。ところが近年、ブラウザ上でPythonコードを実行することが可能になっています（Ref.Suzuki pyscript）。本記事ではブラウザ上で実行可能な当該シミュレーションコードを記します。

シミュレーションコード

本コードはモンテカルロシミュレーションにより成功率を計算するプログラムです。ロッカー内の名前の配位をランダムに発生させ、上記解答のpointer followingに従い100人がロッカーを開けたときの成功/不成功を判定します。この試行を繰り返して成功率を計算します。

Niterが試行回数、Nhumanが囚人の人数、Nslockerがゲームに成功するための開けたロッカーの最大数です。NhumanとNslockerに関して、デフォルトでは100人の囚人問題と同じ設定になっています。好きに変えてみてください。
（その下のNfailとNOKは入力パラメータではありませんのでいじらないでください）

以下の環境で動作を確認しました：

ハードウェア: MacBook Air M1, 2020
OS: macOS Ventura Version 13.5.2
ブラウザ： Chrome および Safari

でもおそらく大体の環境で動くと思います。

以下コードです。
【実行方法】
下のスクリプトを何らかのテキストエディタにコピペし、適当なファイル名と.htmlという拡張子をつけて保存します（例えば100prisoners.htmlとか）。できたファイルをブラウザにドラッグ&ドロップして10秒ぐらい待てば計算が終了します。出力の"Probability of success"が成功率です。

      <html lang="ja">
  <head>
    <meta charset="utf-8"/>
    <link rel="stylesheet" href="https://pyscript.net/latest/pyscript.css" />
    <script defer src="https://pyscript.net/latest/pyscript.js"></script>
  </head>
  <body>
    <py-script>
      import random

      Niter=5000
      Nhuman=100
      Nslocker=50

      Nfail=0
      NOK=0

      test=[i for i in range(Nhuman)]

      print("Simulation: 100 prisoners")
      print ("-----")
      print ("No. of prisoners:", Nhuman)
      print ("No. of opening lockers for success:", Nslocker)
      print ("No. of iteration:", Niter)
      print ("-----")
      print ("Simulation started.")
      print ("")

      for iter in range(0,Niter):
        Nsuc=0
        random.shuffle(test)
        for i in range(0,Nhuman):
          temp=i
          for itry in range(0,Nslocker):
            if test[temp]!=i:
              temp=test[temp]
            else:
              Nsuc=Nsuc+1
              break
      #    print (Nsuc)
        if Nsuc==Nhuman:
          NOK=NOK+1
        else:
          Nfail=Nfail+1

      print ("Simulation finished.")
      print ("-----")
      print("No. of success:",NOK)
      print("No. of failure:",Nfail)
      print("Probability of success:", NOK/(Nfail+NOK))
      print ("-----")
    </py-script>
  </body>
</html>

宜しければ動かしてみてください。