この記事ははてなエンジニア Advent Calendar 2018の18日目の記事です. 昨日は
id:WindymeltのSmart::Argsのパーサを書いたでした. 明日の担当は
id:hokkai7goです.
他の担当者の記事は割と業務っぽいものが多いですが, 今回は趣味っぽいゆるゆるのネタです. 社内でとある数学パズルを紹介したところAdvent Calendarに書いてくれとリクエストがあったので, 紹介します. 単に問題を紹介するだけでは面白くないので, コードを書いて解答できるようにしてみました.
問題
あなたは100人の囚人の一人です. 全員で以下のようなゲームをして, 見事勝利できれば全員釈放, 負ければ全員死刑となります.
- ゲーム開始と同時に全員別々の独房に入ります
- 独房内や通路で他の囚人とやりとりすることはできません
- ランダムに1人ずつスイッチの部屋に呼ばれます
- 十分な時間待てば同じ人が何度でも呼ばれます
- いま誰が呼ばれているかは本人以外にはわかりません
- 部屋にはスイッチが2つ(AとB)ある以外はなにもありません
- ゲームに参加中の囚人以外がこの部屋に入ることはありません
- スイッチの部屋では以下のことができます
- 2つあるスイッチのon/offの状態を確認する
- 2つあるスイッチのいずれか, もしくは両方のon/offを切り替える
- 囚人はいつでも「全員スイッチの部屋に入った!」と宣言することができます
- 本当であれば勝利となります
- まだ一度も部屋に入っていない人がいたらその時点で負けです
- ゲーム開始時点でのスイッチの状態はランダムに決められます
ゲームを開始する前に, 囚人全員で集まって作戦を立てることができます. 必ず勝利できる作戦を考えてください.
答えがわかって物足りなければ以下についても考えてください.
- スイッチの部屋に入った総回数(の期待値)がなるべく少なくなるような作戦を立ててください
- スイッチを1つしか使わずに勝利する方法を考えてください
プログラマ的発想
プログラマなら脊髄反射で「スイッチ2つ=情報2ビットで4通りの値しか持てないんだから100数えるのは無理!」って思っちゃうやつですね. もちろん問題になっているからにはちゃんと解けます. べつになぞなぞとかでもありません.
なんらか答えはあるということで, 気にせずプログラマ脳でちょっと考えてみると, この「作戦を考えてください」というのは「アルゴリズムを考えてください」ということのように思えます. 100人の囚人がそれぞれどのようなアルゴリズムに沿って行動すれば勝利できるかという問題.
そうなるとコードを書いて解答してみたくなります. コードを書いて解答できるなら, 解答が正しいかどうかのチェックも自動化したくなります. ということで, しました!
Pull Requestを送ると自動で採点されて入室回数の少なさや使用したスイッチの少なさでスコアがつき, 順位などもこんなかんじで出ます.
解答方法
実際に, 誰でも以下のようにして解答することができるので, 是非やってみてください.
- Golang環境を用意
- tarao/prisoners-switchを
yourname/prisoners-switchにFork go get github.com/tarao/prisoners-switchyourname/prisoners-switchではなくtarao/prisoners-switchな点に注意
cd "$GOPATH"/src/github.com/tarao/prisoners-switchgit remote add yourname git@github.com:yourname/prisoners-switchgit checkout -b your-answerstrategy/my_strategy.goを編集して解答してgit commitgit push --set-upstream yourname your-answeryour-answerブランチをtarao/prisoners-switchのmasterブランチにPull Requestする
解答は以下の制限に合致している必要があります.
- 書き換えてよいのは
strategy/以下のみ- ファイルを追加してもよい
- 変更ファイル数の上限は20
github.com/tarao/prisoners-switch/rule以外をimportしてはいけない
うまく解けているか手元で確認したい場合はverifier/runを実行すると確認できます.
Pull Requestで解答する方式なので, 当たり前ですが他の人の解答も見えます. 自力で解いた方が当然おもしろいでしょう. より高いスコアを目指すというのもよさそうです.
出典
僕がこの問題を知ったのは10年くらい前に
id:tozimaさんに聞いたからで, id:tozimaさんはバーで自称数学科5回生*1に絡まれて問題を出されたそうで, 長らく出自不明な問題でした. 今回この記事を書くにあたって改めて調べてみたら, ある程度まで判明したので書き残しておきます.
結論から言うと, インターネットで辿れる範囲の初出はIBM Researchの月刊数学パズルでした.
IBM Research | Ponder This | July 2002 Challenge
細かな差異はあって,
- 人数が23人
- 一度の入室では1つのスイッチしか操作できず, また, いずれかのスイッチを操作しなければならない*2
というものだったようです.
This puzzle has been making the rounds of Hungarian mathematicians'parties.
IBM Research | Ponder this
とあり, この月刊パズルのために新規に考案したものではないのも確かですが, これ以上の出典は辿れません.
これより最近のもので言及しているものも多くあります.
- 100 Prisoners and a Light Bulb. William Wu. December 2002.
- 100人
- 勝利するとMENSAに入れるというバリエーションはこの人によるもの
- Mathematical Puzzles. Peter Winkler. 2003.
- One Hundred Prisoners and a Light Bulb (English Edition). Hans van Ditmarsch, Barteld Kooi, Elancheziyan. 2015.
- 原著はオランダ語らしい (ちょっとどれなのかわからなかった)
- MSRIのニュースレターによると原著は2004年のMath HorizonsなのでWinklerの方が先
自動チェックのしくみ
自動チェックされるとこのPull Requestのようにチェックマークがつきます:
https://github.com/tarao/prisoners-switch/pull/7
(正しい解答のコードは含めていませんが, 例示のためにインチキして無理矢理に正解のステータスにしています)
自動チェックは次のようになっています.
- Pull RequestがくるとTravis CIで
verifier/runが実行されるstrategy/以下に余計なimportがないかチェック- ゲームを複数回実行してすべて勝利することを確認, スコアなどを出力
- Travis CIのwebhookがGoogle Apps Script (GAS)をトリガ
- GASがビルド情報やPull Request情報を集める
- GASが改竄チェック
- GASがスコアなどの情報をGoogle Sheetsに保存
- Google Sheetsがスコアから順位を計算
- GASがGitHubのコミットステータスを更新
- (GASがSlackに通知)
これとは別に, 順位の変動をGitHubのコミットステータスに反映するための定期処理もGASで動いています.
GitHubのコミットステータスの"Details"で見られるスコアや順位の出る画面は, 実はGitHub Pagesに配置した静的ファイルで, クエリパラメータからすべての情報を受け取ってJavaScriptでレンダリングしているだけです. なので「順位の変動をGitHubのコミットステータスに反映」というのは単にリンクURLを変えているだけです.
Google Sheets (Googleスプレッドシート)に保存するのは, もともとは単に解答した人たちのスコアを一覧したいだけでしたが, いろいろ作っているうちに順位も出せたら面白そうと思い, どうにかできないかと思ったらRANK関数使うだけでできて, とにかくべんりですね.
こうして, とくに採点や結果の表示のために専用のサーバを立てるようなことはしないで済みました.
チート対策
今回いちばん面白かったところです. コードで解答となると, 解答する側がかなりいろいろなことができてしまうので, 題意に沿わない方法で「正解」の判定を出すことができてしまう可能性があり, うまく対策する必要があります. どんな対策をしたか, 例とともに見ていきましょう.
対策の漏れを見つけた人はframeworkブランチに対して対策をPull Requestしてください(masterブランチにすると自動チェックが走ってしまうからというだけなので修正案をくれるならなんでもよいです). もちろんその前にチートで高得点を叩き出す, というのをやってもかまいません(対策次第得点は無効にします).
「他の囚人とやりとりすることはできません」
コード化された問題を見たら, まずグローバル変数にどの囚人が部屋に入ったか記録していって, 全員が入っていたら勝利宣言する, というのをやってみるのではないでしょうか. なにか対策されているかもしれないけど, されてなかったらそれで解けるのは明らかなので, ひとまず手癖で試してみたくなります.
一方, 対策する側としてはこれは厄介な問題です. 素直に考えると各囚人のコードを別々のサンドボックスで実行しないといけない? どうやって? となります.
あんまり大掛かりなことをしたくはなかったので, 今回は発想を転換して, 「他の囚人とやりとりすることはできません」を直接実現するのではなく, 「やりとりしようと思えばできるが, 話した相手は別の並行世界の囚人かもしれない」としました. ゲームを複数回同時に回して, 同じ番号の囚人が複数人生まれるようにしました. 囚人のインスタンスの初期化順序もばらばらにして, どの囚人がどの囚人と同じ回のゲームにいるのかわからなくしました.
実はこれだけでは「全ゲームで勝利宣言できるだけの入室があったら宣言する」ということができてしまいます. たとえば10ゲーム走っているなら, 同じ番号でインスタンスが別の囚人が10人とも部屋に入ったかどうか確かめればよいのです(上の例は実際そうやっているものです).
そのため, 最終的な対策としては「絶対に勝利できないゲーム」もいくつか混ぜておきます(もちろんそれらのゲームへの勝利は正解判定の条件からは除外します). これらのゲームにはそれぞれ少なくとも1人, 絶対に部屋に呼ばれない囚人がいます. 全ゲームの全囚人が部屋に入ったことを確かめようとすると永久に勝利宣言できなくなります. 「絶対に勝利できないゲーム」の存在はある意味出題側のチートという感じですね.
なんかたぶん一般論として「他人とやりとりすることはできない」と「あらゆる並行世界の他人とやりとりしてしまう」は, ある意味では同値(?)とか双対(?)みたいなことが形式的に言えたりするんじゃないかと妄想しましたが, 妄想しただけで調べたり考えたりは何もしていません. ご存知の方がいたらこっそり教えてください.
不正な結果の出力その他
コードを自由に書けるということは, 偽のチェック結果を出力してすぐ終了したり, もしくはリフレクションやポインタ演算による不正なメモリアクセスなどでチェックを実行する部分のコードを不正に操作することで無理矢理に正解判定に持っていくことができてしまいそうです.
今回はたまたま言語にはGoを選んだので, Goではこのようなことをするには特定のパッケージ(fmtとかosとかreflectとかunsafeとか)をimportする必要があるはずです. そこで, ゲームのルール定義以外のパッケージのimportを一切禁止することにしてみました.
go list -f '{{range $imp := .Imports}}{{printf "%s\n" $imp}}{{end}}'とするとimportされたパッケージ一覧が取得できるので, 余計なものがあったらダメということにしています.
自動チェック方法そのものの改竄
そもそも不正なimportがないかどうかのチェックとか, 判定結果を出力している部分とか, 自動チェック機構そのものもリポジトリに含まれているので, それらを改竄されてしまったらどうしようもありません.
このために, 変更のあった部分に自動チェック機構のコードが含まれていないかチェックしています. これは単にGitHubのAPIで変更のあったファイルのリストを取得すればよいですね. この部分はTravis CIで実行されるverifier/runの中でやっても意味がない(改竄されてしまう)ので, GASでやります.
ただし, Travis CIのwebhookのペイロードは捏造されている可能性があるので注意が必要です. たとえば, ビルドIDやPull RequestのURLなどは正しく正解しているものを指しておいて, コミットステータスの対象のSHA1だけ別のものにすることで, 本来は正解していないものを正解のステータスにしようとしているかもしれません.
このようなことを避けるために, GAS側ではトリガとなるビルドIDのみ利用して, それ以外のPull Requestの情報, 実行結果のログ(正解判定やスコアの情報), 変更のあったファイル一覧などはすべて改めてAPIで取得します. こうすれば, ペイロードが捏造されても単に特定のビルドのチェックが余計に走るだけで, 結果を改竄することはできません.
Travis CIのwebhookには改竄防止のためにSignatureヘッダというのがついてきますが, GASで標準で使えるライブラリだけでこれを検証するのはちょっと面倒だったので使いませんでした. あとは, Travis CIではforked pull requestに対してsecureにした環境変数は(セキュリティ上の理由で)使えませんが, webhookをsecureにしておく(ログとかには一切表示しない)というのだけでもできるともうちょっと楽になりそうです(しかしpull requestに対しては使えないようでした).
おわりに
今回は特定の問題に対してPull Requestで解答できるようにしてみましたが, もうちょっと工夫すれば大枠のしくみは使いまわして, 低コストでこういう問題をいくつも作ることができるかもしれません. 他の人の解答も見えてしまうので, コンテストとか大学の課題みたいなものには使えませんが, 遊びとしてはこれくらいでもいいような気がします.
追記
24時間経たないうちに最初の正解者が出ました. @tomohisaotaさんによる解答で, 効率(ステップ数の少なさ)もかなりよいです.
さらにすぐ後にスイッチ1つの正解も出してくれました. 拍手!
これまでに投稿された解答は以下で誰でも一覧できるようにしました.
