はじめに
前回の続きです。
囚人のジレンマを勝ち抜いた戦略はどのようなアルゴリズムだったのか、紹介していきます。
『文章題で身に付くプログラミング思考入門️』は、日常や文章問題からプログラミング思考を身に付けていく、簡単で身近で、あなたをちょっと輝かせてくれるシリーズです。
これまでのまとめ
対象者
- プログラミングの考え方を学びたい人
- プログラミングに挫折したことのある人
- 論理的思考を鍛えたい人
- 文系の人
- エンジニアの思考を理解したい人
振り返り
囚人のジレンマとは
2人の囚人が別々に隔離されて尋問を受けている。
両者が「黙秘」すれば、2人とも軽い刑罰。
一方が裏切って「自白」、もう一方が「黙秘」すると、裏切った囚人は釈放、黙秘した囚人は重い刑罰。
両者が裏切り合って「自白」なら、中程度の刑罰。
理論的に優位な選択は
裏切って「自白」した方がお得です。
囚人のジレンマをテーマにしたアルゴリズムコンテスト
では本題です。
実施されたコンテストのルールは以下のようなものでした。
囚人のジレンマをテーマにしたアルゴリズムのコンテストは世界各地で複数開催されていて、必ずしもこのルールとは限りません。
「囚人のジレンマ アルゴリズム」などで検索してみてください。
今回はこちらの記事を元に書いていきます。
ラウンド形式
ゲームは複数のラウンドで構成され、各ラウンドで「協力」か「裏切り」を選択します。
ポイント制
各ラウンドでの結果に応じて、以下のポイントが与えられます。
- 両者が「協力」：3点ずつ
- 一方が「裏切り」もう一方が「協力」：裏切り側に5点、協力側は0点
- 両者が「裏切り」：1点ずつ
総得点の競争
全ラウンドが終了した時点で、得点が最も高い戦略が勝者となります。
未知の相手
各戦略は、他の参加者が作成した戦略や主催者が提供する戦略と対戦します。
代表的な戦略
囚人のジレンマのアルゴリズムでは、戦略パターンがいくつかにグルーピングできました。
①裏切り続ける（Always Defect）
常に「裏切り」を選択するシンプルな戦略。
自分が損をする可能性がなくなりますが、信頼関係の構築は不可能です。
②協力し続ける（Always Cooperate）
常に「協力」を選択する戦略。
対戦相手が協力的であれば非常に高いスコアを獲得できますが、裏切りに弱いのが難点です。
③しっぺ返し（Tit-for-Tat）
最初は「協力」し、以降は相手の前回の行動をコピーします。
信頼関係を築きつつ、裏切りにはペナルティを課すバランスの取れた戦略です。
④ランダム（Random）
ランダムに「協力」と「裏切り」を選択する戦略。
相手にパターンを読まれにくい利点がありますが、結果は運に依存します。
一番強かったのは
さて、これらの戦略のうち、どれが一番強かったと思いますか？
実は、③しっぺ返し（Tit-for-Tat） が一番強かったそうです。
- まずは友好的関係を構築する
- 相手が裏切ってきたら、こちらも許さないという態度をはっきりとる
- 相手が歩み寄ってきたら、こちらも歩み寄る。根に持たない
つまり、状況に応じて柔軟に対応できる方が強かったわけです。
長期的な利益と短期的な利益、どちらを優先するか？
相手の行動を予測するにはどうすればいいか？
不確定な状況で最善の選択をするには？
これらの問いに対する答えを定量的に表現したのが、プログラミングです。
プログラミングは、あなたの思考を助けます。
ついで
1/fゆらぎ、という言葉を聞いたことがあると思います。
このゆらぎが入った歌声は心地が良いと言われていますよね。
実は、今回題材にした、繰り返す囚人のジレンマゲームにおいて、1/fゆらぎが観測されたのだそうです。
面白いですね。
その論文では生物の進化についても触れられていました。
とても噛み砕いて言うと、生物の絶滅には法則が見られるということらしいのです。
1/fゆらぎも、自然界に存在する、予測できないとも変わらないとも観測できる波のことですね。
デジタルの仕事ばかりしていると、シータの言葉を思い出します。
「土から離れては生きられないのよ」
これから先のテクノロジーは、現実とデジタルの融合を目指して発展を遂げるのでしょう。
物理や生命への理解が、より深く求められる時代になるのかもしれません。
まとめ
囚人のジレンマ アルゴリズム編では、理論的な戦略、強い戦略について紹介しました。
次回は、囚人のジレンマ 矛盾編をお送りしたいと思います。
最後に
ここまで読んでくださってありがとうございます！
よかったら「いいね」をください。続ける励みになります！