統計数理研究所・共同研究・H25年度 「社会物理学の展望」電機大130313 しっぺ返しに勝つ戦略 とこまで先を読むべきか？ 田中美栄子、糸井良太 共同研究者のM2糸井良太君は卒業 鳥取大学大学院工学研究科 情報エレクトロニクス専攻 知識工学A研究室 はじめに 囚人のジレンマ • • 協力的な行動はリスクが高い 裏切り的な行動を選んでしまう 例．核兵器保有問題，値下げ競争問題 etc 核兵器を持たない=協力，核兵器を持つ=裏切り 裏切り 協力 どの様に行動を決定するかが重要 戦略 目的 戦略 相手と自分の過去の行動から次手を決定 （履歴） 履歴１個 直前の相手の行動を参照 裏切り 協力 戦略 直前の 相手の行動 裏切り 裏切り 裏切り 戦略 直前の 相手の行動 協力 裏切り 裏切り 戦略 相手と自分の過去の行動から次手を決定 （履歴） 履歴１個 直前の相手の行動を参照 裏切り 協力 戦略 裏切り 裏切り 戦略 直前の 相手の行動 裏切り 直前の 相手の行動 協力 裏切り 裏切り 0 協力 裏切り 1 しっぺ返しより強い戦略は？ 「パブロフ」 は 「しっぺ返し」 より強い • 「しっぺ返し」 は 前回の相手の手に対応 • 「パブロフ」 は 前回の自分と相手の手 「パブロフ」の方が多くの項目を考慮 → もっと先読みをするともっと強くなる？ 強い戦略をさがすために・・・ 進化型繰り返し囚人のジレンマモデル (Iterated Prisoner’s Dilemma) • 新しい戦略が自動生成 • 強い戦略が生き残る 強い戦略を生成する 参考文献 Kristian Lindgren ：“Evolutionary Phenomena in Simple Dynamics” Artificial Life II，Addison-Wesley，PP．295-312(1990) 進化型IPDモデル 進化型ＩＰＤモデルの流れ 対戦 評価 突然変異 世代交代 進化型ＩＰＤモデルの流れ 自身を含めた全ての戦略と対戦 対戦 評価 突然変異 世代交代 進化型ＩＰＤモデルの流れ 対戦 戦略A 自身を含めた全ての戦略と対戦 戦略B 戦略A 戦略A 戦略B 戦略C 戦略B 戦略C 戦略C 進化型ＩＰＤモデルの流れ 対戦 利得 3 0 5 3 自身を含めた全ての戦略と対戦 戦略A 行動 1 1 0 1 戦略B 行動 利得 1 0 0 1 1 3 5 0 3 行 動 失 敗 進化型ＩＰＤモデルの流れ 対戦 獲得利得 − 全体利得平均 評価 突然変異 世代交代 進化型ＩＰＤモデルの流れ 対戦 評価 突然変異 強い戦略が繁栄 世代交代 進化型ＩＰＤモデルの流れ 対戦 評価 突然変異 世代交代 進化型ＩＰＤモデルの流れ 新しい戦略の出現 対戦 評価 突然変異 世代交代 進化型ＩＰＤモデルの流れ 突然変異 新しい戦略の出現 点変異 1 0 0 1 複写変異 1 0 1 1 0 1 1 0 1 0 ※ただし戦略の特徴は変わらない 分離変異 1 1 0 1 ※残る戦略はランダムに選択 1 1 進化型ＩＰＤモデルの流れ 対戦 評価 突然変異 1サイクル=1世代 世代交代 実験条件 初期戦略 パラメータ 確率 ランダム 点変異確率 2 × 10−5 複写変異確率 1 × 10−5 分離変異確率 ノイズ発生確率 対戦終了確率 1 × 10−5 0.01 0.01 最大世代数 10万世代 自分 , 相手 協力 裏切り 協力 3,3 5,0 裏切り 0,5 1,1 50回のシミュレーションを行う 11753 個(重複あり) の戦略が出現 戦略の評価 評価値𝑊𝑖 の求め方 𝑊𝑖 ≥ 0ならば 強い戦略 𝑊𝑖 < 0ならば 𝑊𝑖 = (獲得利得 − 平均値) 弱い戦略 戦略の評価結果 785 11753 … Strategy 1011 0.08 1011 1011 0001 0001 1011 0011 0001 0001 0000 1111 0011 0011 0001 1101 0011 0001 0001 -0.00 11101110 10110100 -2.12 -2.35 0.00 -0.00 𝑾𝒊 ≥ 𝟎 … 遺伝子座ごとの分析 戦略の分析 1001 0000 1111 1111 0000 1010 0101 戦略の分析 • 戦略の長さを合わせる 1001 1001 1001 1001 1001 10011001 1001 0000 1111 0000 11110000 1111 0000 1111 1111 0000 1010 0101 1111 0000 1010 0101 戦略の分析 • 各配置に‘1’が使われる確率を求める 1001 1001 1001 1001 1001 10011001 1001 0000 1111 0000 11110000 1111 0000 1111 1111 0000 1010 0101 1111 0000 1010 0101 0.66 0.33 0.00 分析結果 全ての戦略( 11753 個) 0.5に近い値 戦略構造に特徴がない 分析結果 𝑊𝑖 ≥ 0 を満たす 785 個の戦略 0.5から遠い値 戦略構造に特徴がある 分析結果 𝑊𝑖 ≥ 0 を満たす 785 個の戦略 分析結果 𝑊𝑖 ≥ 0 を満たす 785 個の戦略 1001 0001 0001 0001 1001 0001 0001 0001 同じ文字列 考察 の特徴 の特徴① 2手前の 自分の行動 2手前の 相手の行動 自 相 2手前の 相手の行動 自 相 相 自 相 相 自 相 自分からは裏切らない 相 の特徴② 2手前の 自分の行動 2手前の 相手の行動 自 相 2手前の 相手の行動 自 自 相 相 相 相 自 相 相 裏切られたら即座に報復する 相 の特徴③ 2手前の 自分の行動 2手前の 相手の行動 自 相 2手前の 相手の行動 自 自 相 相 相 相 自 相 相 相 裏切り合いが2回続くと関係修復を図る の特徴④ 2手前の 自分の行動 2手前の 相手の行動 自 相 2手前の 相手の行動 自 自 相 相 相 相 自 相 相 搾取できる相手からは，搾取を行う 相 まとめ • 進化型IPDモデルを用いて様々な戦略 を出現，競わせた • 出現した戦略を評価、分析を行った • 長さ32の最強戦略＝長さ16戦略 まとめ • 自分からは裏切らない • 裏切られたら即座に報復 • 裏切り合いが続くと，関係修復を図る • 搾取できる相手からは，搾取を行う 今後の課題 • しっぺ返し（L=2）より強い戦略はもっと長い • パブロフや報復型しっぺ返し（R-TFT）はL=4 • L=4で主流となる「３竦み」はもっと長い戦略に 負ける • L=16 で安定な戦略が見つかった • L=32で安定な戦略はL=16 と同一 • L=64 までは大きな変化なし • L>64 は今後の課題
© Copyright 2024 ExpyDoc
