The 28th Annual Conference of the Japanese Society for Artificial Intelligence, 2014
- 1 -
知能
軍拡競争：報酬
遅延
ン
同士
戦略
複雑化
Process of Enlarging Complexity of Agent using Delayed Reward Game
大澤
博隆
*1 Hirotaka OSAWA*1
筑波大学
University of TsukubaSocial brain theory hypothesizes that the human brain becomes larger through evolution mainly because of reading others' intentions in society. Reading opponents' intentions and cooperating with them or outsmarting them results in an intelligence arms race. The author simulates the evolution of intelligence arms race during long-term using finite state automatons.
1.
じめに
他 者 意 図 推 定 行 う心 理 論 人 間 持 最 複 雑 知能プ 一 あ [Hyatt 10] 社会脳仮 人間
互い ン う 意図推定プ
身 け い 推定 い [Bryne 89] 被
食者 捕食者間 軍拡競争 同 う 互い 意図
合 う 要 請 環境 知 能 対 軍拡 競争 発 生 期待 [Flinn 05] あ ン 他
ン 賢 け ば 他 ン 欺 多 利 益 手
入 う テ ン テ 人
工 知 能 共 興 味 深 い課 題 あ 他 者 意 図
解 テ 解 明 意 図 人 工 知
能 テ 作 能 う
筆 者 Anti-Max Prisonner's Dillemma game
(AMPD) 呼ば 繰 返 囚人 ン
ン 用 い う 知 能 発 生 プ 確 認
AMPD 用 い 人 間 間 ン 戦
略 人間 複雑化 プ 発見 [Osawa 13]
遺伝的プ ン 100 ンプ 1500世代
わ ン ン 行 結 う
知能 複雑化 普通 繰 返 囚人 ン 場合
発生 AMPD 場合 発生 突 止
[Osawa 14]
本研究 AMPD 用い ン
複雑化 長期 的 うい 過 程 10000 世代 わ
ン結 検討
2.
ゲー
モデ
本 研 究 行 わ 交 代 引 Robert Axelrod 行 繰 返 囚 人 ン [Axelrod 84] Angeline
改 良 Anti-Max Prisoner's Dilemma game (AMPD) 使 用 [Angeline 94] AMPD 相互協 調 交互 手
利益 最大化
戦 略 型 け 一 般的 利 得表 表 1 形
wait take Axelrod け coop
betray 対応 本利得表 繰 返 囚人 ン 発生
条件 式1 あ 場合 両者 協調
繰 返 う 交互 裏 返 利得 大 い 両 戦略
同 利 得 得 場 合 式 2 あ Multi-Max
Prisoner's Dilemma game (MMPD) 呼ば 協調
交互 引 有効 あ AMPD 発生 う 条件
式3 あ
表1 : 交代 引 一般的利得表
B \ A Cooperate Defect
Cooperate
(
A
:
c
,
B
:
c
)
(
A
:
a
,
B
:
b
)
Defect
(
A
:
b
,
B
:
a
)
(
A
:
d
,
B
:
d
)
b
d
c
a
,a
b
2
c
(1)b
d
c
a
,a
b
2
c
(2)b
d
c
a
,a
b
2
c
(3)AMPD条件 交互 Defect 繰 返 両者 利益
最大化 問題 う 相互裏 簡単 発生
い あ 交 互 裏 成 相 手 う手
出 攻撃 行う必要 あ 攻撃 行い 相手
ン 自 搾 行 う い 誤認
いけ い 相 手 ン 自 協 力 的
搾 値 対象 あ 思わ いけ い
本研究 AMPD 条件
a
7
b
3
c
1
1
d
いう条件 採用 [Osawa 14]3.
シ
ュ
ーション条件
各 ン 戦略 有限状態オ ン 記述
各 オ ン 数 状態 持 偶 数 推 移 協
力 戦 略 奇 数 移 動 裏 戦 略 意 味 代 表 的 戦 略 図1 示
図1 オート トンによ 戦略奇術の例
戦略 推移 3 数 組 記述 最初 数
現在状態 次 数 相手 手 0 協調 1 裏 意味
3番目 数 次 推移 状態 意味 例えば{{2},
{2,0,2}, {2,1,2}} 常 協 調 行 う戦 略 意 味 {{1}, {1, 0,
1}, {1,1,1}} 常 裏 行う戦略 意味 {{2}, {2,0,2},
{2,1,1}, {1,0,2}, {1,1,1}} IPD い 見 返 戦 略 TFT 意 味 aTFT TFT 開 始 時 裏
TFT あ Pavlov 相手 裏 返 場合 協調 裏 連 絡 先： 大 澤博 隆， テ 情報 系 知 能機 能 工学 域 ，〒
305-8573 茨 城 県 ば 市 天 王 1-1-1 ，
The 28th Annual Conference of the Japanese Society for Artificial Intelligence, 2014
- 2 -
図2 10000世代にわた シ ュレーション結 グレー領域およびY軸左の数字が使用 た の平均数を表し 黒線及びY軸右の 数字が使用 た の循環的複雑度(CC)を表す
反転 ン あ GRIM 戦 略 一度 裏
強調 一度裏 場合 全 裏 返 戦略
あ
オ ン 戦略 遺伝的プ ン (GP) 世代
進化 行う 今回 ン 50 ン
10000世代 わ 進化 行 ン
各世代 他 49 ン 対 総当 戦 行う
ン 成績 総 当 戦 結 得 総 ア数 決
定 各 ン 終 了 時 最 ン い ン
処刑 47 ~49 3体 ン 突然
変異 起 最後 1 2 ン 交差
新 い ン 生 出 足
突然変異 プ 以 3 い 10% 確
率 オ ン ノ ひ 選択 状態 反転
80% 確率 オ ン 一 選択
指 示 先 他 ノ 10% 確率 新 いノ
ン 追加 新 付け加え ノ 次
突然変異 オ ン 繋 能性 あ
交差 プ 2 ン う 一
選ば ン オ ン ツ 一部
う一 ン オ ン ツ 一 部 置 換 え
置 換え イン ン 選択 置 換
え ノ ツ ン 元 ン 重 複
場合 重複 い形 ノ 置 換 え 孤 立
ノ や 突 然 変 異 や 交 差 発 生 場 合
将来的 突然変異 繋 能性 残 保
初期 オ ン 多様性 GP 良 い結 導
重 要 あ 本 研究 理 論 選 ば ンプ
戦略 含 戦略群 初期50体 ン ン
配置 ン 1 2 ノ
開始ノ ン 配置 損結
32体 ン ン 生 成 初
期50体 ン 配置
評価方法 使用 ン 平均 ア 戦略
数 循環的複雑度(cyclomatic complexity) [McCabe 76]
点 比較 樹冠的複雑度(CC) 大 各戦略
岐 複雑 表 あ 本研究 使用 オ
ン 終了状態 在 い 循環的複 雑度 使用
数 使用 ノ 数 引 いう形
計算 例えば図1 believerやattacker CC 0 TFT やaTFT Pavlov CC 2 GRIM CC 1 遺
伝的プ ン 手法 実際 使 用 い 戦略
数 大 増加 い う 循 環的 複雑 度 数
え あ ン 総当 戦 一度以 使わ
ノ 使 用 計 算 ン 使 用
い い あ 将 来的 戦略 対 潜在的 頑健
対応力 示 い 能性 あ 今回 使用
数 え 試合 確実 使 用
計算 い
4.
シ
ュ
ーション結果
事前 テ 世代数 1500 世代 AMPD条件
ン 100 条件行 う 43条件 場合
ン ノ 数 成長 確認 条
件 う 1500 世 代 目 平 均 数 中 央 値 条件 元
10000世代 わ 長期 ン 行 最 初 500 世 代 平 均 ア 2 近 い
AMPD条件 け 最 高い ア 相互裏 条件 該当
図2 ン 結 示 図 領域
使用 平均数 図 2 黒い線 使用 循環
的複雑度 平均数 示 最初 1500 世代間 使用
使用 CC 増加 い 見
本結 筆者 以前行 ン結 同様 あ
[5] 1500~10000 世 代 間 使 用 平 均 数
増え い わ 一方 循環的複雑度 1500世代
順調 増加 以降 増加 緩 や
5.
考察
AMPD い ン 同士 同 戦略 持
い 場 合 ン 同士 相互 裏 状態 保
The 28th Annual Conference of the Japanese Society for Artificial Intelligence, 2014
- 3 -
い 戦略 持 う 働 け 示 唆 人
間同士 ン 著者 以前 実験結
各人間 戦 略 最初 互い 信号 送 合
う初期 在 わ い [大澤 13] 50 体
ン 信 号 持 最 6bit
岐 必 要 あ 循 環 的 複 雑 度 6
以 望 い 本 研 究 得 使 用 循 環
的複雑度 平均値 条件 満 い いえ
図2 け 使用 循環的複雑度 平均値
標準偏差 1000世代 図3 示
図3 1000世代 との循環的複雑度の平均と標準偏差
図3 値 使用 数 世代 経 毎 緩や
増加 い わ AMPD 条件 緩や 増加
使用 限 起 い いう ン
知能 示 戦略 増 加 単 純 遺 伝的プ ン
必 要 い 生 出 け 必 要 あ 形
使わ い わ AMPD条件 長期 わ
意味 あ 知能 増加 促 いう 示唆
標 準 偏 差 値 世 代 経 毎 増 加 い 見
各 ン け 使用 循環的 複雑
度 平均値 ぶ 大 い 意味 い 実際
図2 う 使用 循環的複雑度 世代 経 毎 増
減 激 4~12 値 合 わ 変化 使
用 い ン 同一 物 多 同一 ン
世 代 各 ン ノ 使用 少 数
ノ 使 用 いう う 対 応 変 化 い わ
ン 集団 複雑 岐 要 う 条
件 単純 岐 済 条 件 間 交 互 移 動 い 推測
図 3 表示 い あ 使用 循環的
複 雑 度 あ 推 測 ン 持
全 体 的 戦 略 オ ン 複 雑 岐 要 条 件
単純 岐 済 条件 対応 頑健 戦略 持
合わ い い いう 推測
6.
結論
本 研 究 有 限 状 態 オ ン 使 遺 伝 的 プ
ン 手法 軍拡競争 後押 利得条件 調 特
本研究 著者 結 け 長期 わ
う 戦 略 複 雑 化 調 結 報 酬 遅 延
利得 表 い ン 内 部状 態 複雑 化 軍拡
競 争 発 生 う 内 部 状 態 増 加 長 期 わ わ
7.
謝辞
本研究 独立行政法人科学 技 術振興機構 戦略的 創造研 究推進事 業 け 領域 情 報環境 人 援助 け 行わ
参考文献
[Hiatt 10] L. M. Hiatt and J. G. Trafton, “A Cognitive Model of
Theory of Mind,” in International Conference on Cognitive
Modeling, 2010, pp. 91–96.
[Bryne 89] R. W. Byrne and A. Whiten, Machiavellian Intelligence: Social Expertise and the Evolution of Intellect in
Monkeys, Apes, and Humans. Oxford University Press, USA, 1989.
[Flinn 05] M. V. Flinn, D. C. Geary, and C. V. Ward,
“Ecological dominance, social competition, and coalitionary
arms races,” Evol. Hum. Behav., vol. 26, no. 1, pp. 10–46, Jan.
2005.
[Osawa 13] H. Osawa and M. Imai, “Evolution of Mutual Trust Protocol in Human-based Multi-Agent Simulation,” in 12th European Conference on Artificial Life, 2013, pp. 692–697.
[Osawa 14] H. Osawa, “Intelligence Arms Race: Delayed Reward Increases Complexity of Agent Strategies,” in International Conference on Autonomous Agents, 2014, p. (accepted).
[Axelrod 84] R. Axelrod, The Evolution of Cooperation. Basic Books, 1984.
[Angeline 94] P. J. Angeline, “An Alternate Interpretation of
the Iterated Prisoner’s Dilemma and the Evolution of
Non-Mutual Cooperation,” in Proceedings of 4th artificial life
conference, 1994, pp. 353–358.
[McCabe 76] T. J. McCabe, “A Complexity Measure,” IEEE Trans. Softw. Eng., vol. SE-2, no. 4, pp. 308–320, 1976.
[大澤 13] 大澤博隆 and 今井倫太, “交代取引ゲー における
他者識別規則 進化,” in 人工知能学会全国大会, 2013, pp.
