中文模板

Transcription

1 软 件 学 报 doi: /j.cnki.jos 通 用 对 弈 游 戏 : 一 个 探 索 机 器 游 戏 智 能 的 领 域 张 海 峰 1+, 刘 当 一 1 1, 李 文 新 1 ( 北 京 大 学 信 息 科 学 技 术 学 院, 北 京 ) General Game Playing:A Research Field for Exploring Machine Intelligence in Games ZHANG Hai-Feng 1+, LIU Dang-Yi 1, LI Wen-Xin 1 1 (School of Electronics Engineering and Computer Science, Peking University, Beijing , China) + Corresponding author: pkuzhf@pku.edu.cn Abstract: General Game Playing (GGP) is a research field for improving the general gaming intelligence of machines. It is different from specific game playing in that GGP players do not know game rules before the game begins, which makes them independent from human experience on specific games. Until now, GGP researchers have deeply explored many problems, such as game representation, search algorithm, and state evaluation. Also, some efforts have been made on knowledge transfer. The progress of GGP research represents the development of artificial general intelligence to some extent, which makes it remarkable. Key words: general; game; logic; artificial intelligence; knowledge representation 摘 要 : 通 用 对 弈 游 戏 (General Game Playing, 以 下 简 称 GGP) 是 致 力 于 提 高 机 器 的 通 用 游 戏 智 能 的 研 究 领 域. 与 专 用 游 戏 智 能 程 序 不 同,GGP 玩 家 直 到 游 戏 开 始 时 才 获 得 游 戏 规 则, 从 而 避 免 依 赖 于 人 类 关 于 特 定 游 戏 的 经 验.GGP 研 究 发 展 至 今, 已 在 游 戏 表 示 搜 索 算 法 状 态 估 值 等 方 面 做 了 深 入 探 索, 并 在 知 识 迁 移 等 方 面 做 出 了 尝 试.GGP 研 究 的 进 展 在 一 定 程 度 上 代 表 了 通 用 人 工 智 能 的 发 展, 因 而 是 值 得 关 注 的. 关 键 词 : 通 用 ; 游 戏 ; 逻 辑 ; 人 工 智 能 ; 知 识 表 示 中 图 法 分 类 号 : TP301 文 献 标 识 码 : A 通 用 人 工 智 能 是 人 工 智 能 领 域 的 一 项 重 大 挑 战, 它 的 目 标 是 让 机 器 能 够 像 人 一 样 完 成 各 种 各 样 的 任 务. 具 体 到 游 戏 领 域, 通 用 对 弈 游 戏 (General Game Playing, 以 下 简 称 GGP) 致 力 于 开 发 一 种 能 够 以 人 类 水 准 玩 任 意 已 知 或 未 知 游 戏 的 人 工 智 能 系 统. 众 所 周 知,IBM 的 超 级 计 算 机 深 蓝 战 胜 国 际 象 棋 冠 军 卡 斯 帕 罗 夫 标 志 着 人 工 智 能 到 达 了 一 个 新 的 高 度. 然 而, 深 蓝 的 智 能 至 少 在 两 方 面 还 存 在 局 限 性 : 其 一 是 只 能 玩 国 际 象 棋 这 一 种 游 戏, 不 具 有 通 用 性 ; 其 二 是 依 赖 于 大 量 的 人 类 游 戏 经 验, 不 具 有 完 全 自 主 学 习 的 能 力.GGP 研 究 的 目 标 就 是 突 破 这 些 局 限, 它 设 置 的 环 境 要 作 者 简 介 : 张 海 峰 (1989-), 男, 福 建 浦 城 人, 博 士 生, 主 要 研 究 领 域 为 人 工 智 能 ; 刘 当 一 (1994-), 男, 本 科 生, 主 要 研 究 领 域 为 人 工 智 能 ; 李 文 新 (1968-), 女, 博 士, 教 授, 主 要 研 究 领 域 为 人 工 智 能. 收 稿 时 间 : ; 修 改 时 间 : ; 采 用 时 间 : ; jos 在 线 出 版 时 间 : CNKI 网 络 优 先 出 版 : :22:19,

2 求 机 器 必 须 在 没 有 人 类 游 戏 经 验 的 指 导 下 玩 各 种 各 样 的 游 戏. 因 此,GGP 研 究 的 进 展 反 映 了 机 器 游 戏 智 能 在 通 用 性 和 自 主 学 习 方 面 的 发 展,GGP 比 赛 则 成 为 一 种 评 价 机 器 游 戏 智 能 的 标 准. 1 GGP 研 究 的 基 本 框 架 Genesereth 等 于 2005 年 提 出 GGP [1], 同 时 开 始 举 办 一 年 一 度 的 国 际 GGP 比 赛.GGP 研 究 发 展 至 今, 已 经 形 成 了 一 个 特 定 的 游 戏 集 合, 并 在 不 断 地 发 展 扩 大. 游 戏 集 合 中 所 有 游 戏 的 规 则 都 用 一 种 统 一 的 游 戏 描 述 语 言 描 述,GGP 玩 家 在 每 场 游 戏 对 局 的 开 始 阶 段 获 得 游 戏 规 则. 在 一 场 游 戏 对 局 中, 参 与 游 戏 的 GGP 玩 家 与 一 台 扮 演 裁 判 的 游 戏 主 机 进 行 交 互, 共 同 完 成 游 戏. 组 织 游 戏 对 局 的 通 常 是 GGP 平 台 或 比 赛, 它 们 成 为 衡 量 GGP 研 究 进 展 的 标 尺. 1.1 游 戏 集 合 目 前 公 开 的 GGP 游 戏 约 有 几 百 个, 它 们 在 玩 家 人 数 复 杂 度 对 称 性 等 方 面 各 不 相 同, 具 有 很 好 的 多 样 性. 有 些 游 戏 之 间 还 具 有 关 联 性, 这 些 关 联 性 为 游 戏 知 识 的 迁 移 提 供 了 发 挥 作 用 的 空 间 典 型 游 戏 GGP 游 戏 中 最 常 见 的 是 棋 盘 游 戏, 此 外 还 有 地 图 游 戏 博 弈 论 游 戏 等 游 戏 形 式. 图 1 展 示 了 几 个 比 较 典 型 的 GGP 游 戏. Eight Puzzle Connect Four Checkers Pacman 3P Dots and Boxes Blocker Fig.1 Examples of games 图 1 游 戏 举 例 Eight Puzzle 是 一 个 单 人 游 戏, 玩 家 每 回 合 可 以 移 动 一 个 数 码, 目 标 是 使 全 部 数 码 按 照 1 至 8 的 顺 序 排 列.Connect Four 是 一 个 双 人 棋 盘 游 戏, 双 方 按 一 定 规 则 轮 流 落 子, 目 标 是 率 先 形 成 四 子 连 珠.Checkers( 西 洋 跳 棋 ) 是 一 个 经 典 的 双 人 棋 盘 游 戏, 它 的 棋 子 只 能 减 少 不 能 增 加, 这 与 Connect Four 正 好 相 反.Pacman 3P 是 一 个 不 对 称 的 三 人 地 图 游 戏, 其 中 一 个 玩 家 的 目 标 是 在 地 图 上 吃 尽 量 多 的 豆 子, 另 两 个 玩 家 的 目 标 是 围 捕 第 一 个 玩 家.Dots and Boxes 是 一 个 双 人 游 戏, 玩 家 轮 流 在 地 图 上 筑 墙, 筑 四 面 墙 能 够 圈 一 块 地, 圈 地 多 者 获 胜.Blocker 是

3 一 个 不 对 称 的 双 人 游 戏, 蓝 绿 双 方 每 回 合 同 时 占 领 一 个 格 子, 绿 色 玩 家 的 目 标 是 连 接 左 右, 蓝 色 玩 家 的 目 标 是 阻 止 绿 色 玩 家. 可 见,GGP 游 戏 丰 富 多 彩, 既 有 单 人 的 也 有 多 人 的, 既 有 同 步 的 也 有 异 步 的, 既 有 竞 争 的 也 有 配 合 的, 既 有 对 称 的 也 有 非 对 称 的 生 成 的 游 戏 为 了 鼓 励 GGP 玩 家 实 现 游 戏 知 识 的 迁 移,GGP 游 戏 集 合 中 存 在 着 一 些 从 已 有 游 戏 生 成 的 游 戏, 包 括 组 合 游 戏 和 相 似 游 戏. 组 合 游 戏 是 由 几 个 相 同 或 不 同 的 游 戏 组 合 而 成 的 游 戏. 比 如, 可 以 将 两 个 Connect Four 棋 盘 组 合 成 一 个 新 游 戏, 玩 家 每 回 合 只 能 选 择 其 中 一 个 棋 盘 行 动, 率 先 在 任 何 一 个 棋 盘 获 胜 的 玩 家 获 胜. 游 戏 还 有 其 他 的 组 合 方 式, 比 如 两 个 棋 盘 都 获 胜 的 玩 家 才 获 胜, 或 者 指 定 其 中 一 个 棋 盘 获 胜 的 玩 家 才 获 胜. 相 似 游 戏 是 由 另 一 个 游 戏 修 改 某 些 条 件 变 化 而 来 的 游 戏. 其 中 最 为 典 型 的 是 自 杀 游 戏, 即 游 戏 结 果 与 原 游 戏 完 全 相 反 的 游 戏. 比 如,Connect Four Suicide 规 定 率 先 形 成 四 子 连 珠 的 玩 家 失 败, 这 与 Connect Four 正 好 相 反. 此 外, 修 改 游 戏 玩 家 数 修 改 棋 盘 大 小 也 是 常 见 的 构 造 相 似 游 戏 的 方 法. 1.2 游 戏 描 述 方 式 游 戏 的 规 则 可 以 用 不 同 的 方 式 加 以 描 述, 人 类 常 用 的 是 自 然 语 言, 数 学 定 义 上 则 常 用 状 态 机 模 型. 从 抽 象 程 度 上 来 说, 这 是 两 种 极 端 的 表 述 方 式. 高 度 抽 象 的 自 然 语 言 虽 然 简 洁, 但 对 于 计 算 机 程 序 来 说 存 在 太 多 歧 义, 如 何 正 确 地 解 读 还 是 一 个 难 题. 而 高 度 具 体 的 状 态 机 模 型 需 要 描 述 太 多 细 节, 对 于 很 多 游 戏 来 说 仅 存 在 理 论 上 的 可 用 性, 比 如 国 际 象 棋 具 有 约 个 状 态 [2], 远 远 超 过 当 今 计 算 机 存 储 空 间 的 数 量 级. 因 此, 要 让 计 算 机 理 解 游 戏 规 则, 需 要 采 用 抽 象 程 度 适 中 的 无 歧 义 的 相 对 简 洁 的 游 戏 描 述 方 式. Love 等 提 出 的 游 戏 描 述 语 言 (Game Description Language, 以 下 简 称 GDL) [3] 是 专 门 用 来 描 述 游 戏 规 则 的 一 种 语 言, 已 经 被 GGP 比 赛 广 泛 使 用.GDL 是 一 种 声 明 式 的 逻 辑 编 程 语 言, 它 的 抽 象 程 度 介 于 自 然 语 言 和 状 态 机 模 型 之 间, 是 无 歧 义 且 相 对 简 洁 的, 适 合 于 计 算 机 理 解.GDL 可 以 被 认 为 是 状 态 机 模 型 的 一 种 改 写, 它 将 状 态 机 的 状 态 用 命 题 集 合 的 方 式 编 码, 再 将 状 态 间 的 转 移 关 系 改 写 成 命 题 间 的 逻 辑 关 系, 这 种 改 写 大 大 简 化 了 游 戏 的 描 述 游 戏 的 状 态 机 模 型 状 态 机 模 型 是 用 集 合 论 描 述 游 戏 规 则 的 方 式. 状 态 机 的 每 一 个 状 态 对 应 游 戏 中 的 一 个 局 面, 每 一 个 状 态 下, 每 个 玩 家 具 有 若 干 个 合 法 的 动 作, 玩 家 各 自 选 择 一 个 合 法 动 作, 共 同 决 定 游 戏 的 下 一 个 状 态. 游 戏 具 有 一 个 初 始 [4] 状 态 和 若 干 个 结 束 状 态, 结 束 状 态 决 定 各 个 玩 家 的 得 分. 它 的 形 式 化 定 义 如 下. 定 义 1( 游 戏 的 状 态 机 模 型 ). 设 是 一 个 可 数 的 字 符 集, 是 一 个 状 态 集, 是 一 个 动 作 集, 则 一 个 离 散 的 同 步 的 确 定 性 的 完 全 信 息 的 游 戏 可 以 表 达 为 一 个 六 元 组, 满 足, 表 示 玩 家 ;, 表 示 游 戏 初 始 状 态 ;, 表 示 游 戏 结 束 状 态 ;, 表 示 各 玩 家 在 各 状 态 下 的 合 法 动 作 ;

4 , 表 示 在 各 玩 家 动 作 共 同 作 用 下 状 态 的 转 移 ;, 表 示 各 玩 家 在 各 状 态 下 的 得 分 GDL 的 语 法 GDL 用 命 题 的 集 合 编 码 游 戏 状 态. 对 于 一 个 游 戏,GDL 定 义 一 个 状 态 命 题 集 合 P, 并 在 游 戏 状 态 集 合 S 与 P 的 幂 集 2 P 之 间 建 立 一 个 单 射 f:s 2 P, 使 得 任 意 一 个 游 戏 状 态 对 应 P 的 一 个 子 集. 对 于 任 意 命 题 p 和 任 意 状 态 s, 若 p f(s), 则 称 p 在 s 下 为 真, 否 则 为 假.GDL 还 定 义 玩 家 的 动 作 命 题 集 合 A, 使 得 玩 家 在 任 何 游 戏 状 态 下 的 合 法 动 作 命 题 集 合 L s,r 都 是 A 的 一 个 子 集. 此 外,GDL 还 规 定 了 一 些 描 述 游 戏 元 素 的 命 题, 它 们 的 含 义 如 表 1 所 示. Table 1 Propositions describing elements of games in GDL 表 1 GDL 中 描 述 游 戏 元 素 的 命 题 命 题 命 题 为 真 时 的 含 义 (role r) r 是 一 个 玩 家 (init p) 状 态 命 题 p 在 初 始 状 态 下 为 真 (true p) 状 态 命 题 p 在 当 前 状 态 下 为 真 (legal r a) 玩 家 r 在 当 前 状 态 下 具 有 合 法 动 作 a (does r a) 玩 家 r 采 取 了 动 作 a (next p) 状 态 命 题 p 在 下 一 状 态 下 为 真 terminal 当 前 状 态 是 结 束 状 态 (goal r n) 当 前 状 态 下 玩 家 r 的 得 分 是 n 在 此 基 础 上,GDL 定 义 这 些 命 题 之 间 一 系 列 的 逻 辑 关 系, 包 括 : 当 前 状 态 是 否 是 结 束 状 态 的 逻 辑, 即 由 true 命 题 推 出 terminal 命 题 的 逻 辑 ; 当 前 状 态 下 各 玩 家 的 合 法 动 作 的 逻 辑, 即 由 true 命 题 推 出 legal 命 题 的 逻 辑 ; 当 前 状 态 如 何 转 移 到 下 一 状 态 的 逻 辑, 即 由 true 命 题 和 does 推 出 next 命 题 的 逻 辑 ; 当 前 状 态 下 各 玩 家 的 得 分 的 逻 辑, 即 由 true 命 题 推 出 goal 命 题 的 逻 辑. 有 了 这 些 定 义,GDL 的 描 述 能 力 就 与 状 态 机 模 型 等 价 了. 此 外, 实 际 的 GDL 规 则 中 通 常 还 含 有 辅 助 性 命 题, 辅 助 性 命 题 的 引 入 本 质 上 不 改 变 上 述 特 殊 命 题 之 间 的 逻 辑 关 系, 只 是 为 了 描 述 的 方 便 性 与 可 读 性 GDL 的 例 子 井 字 棋 井 字 棋 (Tic-Tac-Toe) 游 戏 是 一 个 简 单 易 玩 的 游 戏, 它 规 定 游 戏 双 方 在 3x3 的 棋 盘 上 轮 流 落 子, 率 先 将 己 方 落 子 连 成 三 子 一 线 ( 横 竖 或 对 角 线 ) 的 玩 家 获 胜. 井 字 棋 的 GDL 描 述 如 下 所 示. 1. (role xplayer) (role oplayer) 2. (init (cell 1 1 b)) (init (cell 1 2 b))...(init (cell 3 3 b)) 3. (init (control xplayer)) 4. (<= (legal?w (mark?x?y)) (true (cell?x?y b)) (true (control?w))) 5. (<= (legal xplayer noop) (true (control oplayer))) 6. (<= (legal oplayer noop) (true (control xplayer))) 7. (<= (next (cell?m?n x)) (does xplayer (mark?m?n)) (true (cell?m?n b))) 8. (<= (next (cell?m?n o)) (does oplayer (mark?m?n)) (true (cell?m?n b))) 9. (<= (next (cell?m?n?w)) (true (cell?m?n?w)) (distinct?w b)) 10. (<= (next (cell?m?n b)) (does?w (mark?j?k)) (true (cell?m?n b)) (or (distinct?m?j) (distinct?n?k))) 11. (<= (next (control xplayer)) (true (control oplayer))) 12. (<= (next (control oplayer)) (true (control xplayer))) 13. (<= (row?m?x) (true (cell?m 1?x)) (true (cell?m 2?x)) (true (cell?m 3?x)))

5 14. (<= (column?n?x) (true (cell 1?n?x)) (true (cell 2?n?x)) (true (cell 3?n?x))) 15. (<= (diagonal?x) (true (cell 1 1?x)) (true (cell 2 2?x)) (true (cell 3 3?x))) 16. (<= (diagonal?x) (true (cell 1 3?x)) (true (cell 2 2?x)) (true (cell 3 1?x))) 17. (<= (line?x) (or (row?m?x) (column?m?x) (diagonal?x)) 18. (<= open (true (cell?m?n b))) 19. (<= (goal xplayer 100) (line x)) 20. (<= (goal xplayer 50) (not (line x)) (not (line o)) (not open)) 21. (<= (goal xplayer 0) (line o)) 22. (<= (goal oplayer 100) (line o)) 23. (<= (goal oplayer 50) (not (line x)) (not (line o)) (not open)) 24. (<= (goal oplayer 0) (line x)) 25. (<= terminal (or (line x) (line o) (not open))) GDL 采 用 的 是 前 缀 逻 辑, 其 中 <= 是 推 理 符 号, 其 后 的 第 一 项 表 示 推 理 结 果, 其 余 若 干 项 表 示 推 理 条 件. 以 问 号 开 头 的 字 符 串 表 示 变 量. 第 1 行 描 述 了 游 戏 有 两 个 玩 家. 第 2 3 行 描 述 了 游 戏 的 初 始 状 态, 即 棋 盘 九 个 格 子 都 为 空, 初 始 控 制 权 属 于 xplayer. 第 4 至 6 行 描 述 了 当 前 状 态 下 各 玩 家 的 合 法 动 作. 第 7 至 12 行 描 述 了 当 前 状 态 如 何 转 移 到 下 一 状 态. 第 13 至 18 行 描 述 了 一 些 辅 助 性 命 题, 如 三 子 一 线 等 概 念. 第 19 至 24 行 描 述 了 当 前 状 态 下 各 玩 家 的 得 分. 第 25 行 描 述 了 当 前 状 态 是 否 是 结 束 状 态 GDL 的 描 述 能 力 与 状 态 机 模 型 一 样,GDL 可 以 描 述 离 散 的 同 步 的 确 定 性 的 完 全 信 息 的 游 戏. GDL 只 能 描 述 离 散 的 游 戏, 因 为 它 所 定 义 的 游 戏 状 态 是 离 散 的. 对 于 具 有 连 续 状 态 的 游 戏, 可 以 通 过 大 量 离 散 状 态 逼 近 的 方 式 使 其 离 散 化, 再 用 GDL 加 以 描 述. 事 实 上, 由 于 计 算 机 的 工 作 方 式 本 身 是 离 散 的, 任 何 在 依 赖 于 连 续 概 念 的 游 戏 都 只 能 用 离 散 的 方 式 被 计 算 机 处 理. GDL 描 述 的 游 戏 是 同 步 的, 即 所 有 玩 家 在 某 一 状 态 下 同 时 采 取 动 作, 共 同 影 响 状 态 的 转 移. 事 实 上, 异 步 的 游 戏 可 以 通 过 增 加 无 效 的 动 作 转 化 成 同 步 的 游 戏. 无 效 的 动 作, 指 对 状 态 转 移 没 有 任 何 实 质 影 响 的 动 作. 如 上 述 井 字 棋 游 戏, 虽 然 是 双 方 轮 流 落 子 的 异 步 游 戏, 但 通 过 赋 予 非 落 子 方 一 个 无 效 的 noop 操 作 转 化 成 了 同 步 的 游 戏 ( 见 第 5 6 行 ). GDL 描 述 的 游 戏 都 是 确 定 性 的 和 完 全 信 息 的. 非 确 定 性 的 游 戏 包 括 一 些 需 要 掷 骰 子 的 游 戏, 在 这 类 游 戏 中, 状 态 的 转 移 不 仅 依 赖 于 玩 家 的 动 作, 还 依 赖 于 某 些 带 有 随 机 性 的 事 件. 非 完 全 信 息 的 游 戏 包 括 一 些 牌 类 游 戏, 在 这 类 游 戏 中, 玩 家 看 不 到 其 他 玩 家 的 牌, 因 此 不 能 完 全 知 晓 当 前 所 处 的 游 戏 状 态. 为 了 扩 大 GDL 的 描 述 能 力,Thielscher 等 提 出 的 GDL-II(Game Description Language with Incomplete Information) [5] 引 入 了 用 于 描 述 随 机 性 的 random 命 题 和 用 于 描 述 非 完 全 信 息 的 sees 命 题, 从 而 具 备 了 描 述 非 确 定 性 非 完 全 信 息 游 戏 的 能 力. 虽 然 如 此, 目 前 GGP 的 研 究 主 要 还 是 建 立 在 GDL 之 上,GDL-II 只 作 为 一 种 可 能 的 扩 展 方 式 而 存 在, 是 否 是 唯 一 或 最 佳 的 扩 展 方 式 尚 未 有 定 论. 1.3 游 戏 对 局 交 互 方 式 GGP 对 局 采 用 一 种 独 特 的 交 互 机 制, 它 规 定 玩 家 的 程 序 各 自 在 本 地 运 行, 并 提 供 一 个 网 络 接 口 供 游 戏 主 机 远 程 访 问. 游 戏 主 机 是 对 局 的 裁 判, 它 负 责 与 各 个 玩 家 通 信 以 进 行 游 戏, 玩 家 之 间 不 可 以 通 信. 交 互 机 制 如 图 2 所 示.

6 游 戏 主 机 判 断 下 一 状 态 是 否 为 结 束 状 态, 是 则 结 束 游 戏, 否 则 进 入 下 一 回 合 准 备 时 间 (Start Clock) 回 合 时 间 (Play Clock) 回 合 时 间 (Play Clock) 游 戏 主 机 对 局 开 始 信 息 ( 包 括 游 戏 规 则 玩 家 在 游 戏 中 的 角 色 准 备 时 间 回 合 时 间 ) 上 一 回 合 各 玩 家 采 取 的 动 作 ( 第 一 回 合 为 空 ) 上 一 回 合 各 玩 家 采 取 的 动 作 游 戏 玩 家 本 回 合 本 玩 家 采 取 的 动 作 本 回 合 本 玩 家 采 取 的 动 作 准 备 阶 段 第 一 回 合 第 二 回 合 Fig.2 Communication mechanism in GGP 图 2 GGP 对 局 交 互 机 制 游 戏 主 机 首 先 将 游 戏 开 始 的 信 息 同 时 发 送 给 各 个 玩 家, 这 个 信 息 中 包 含 游 戏 规 则 玩 家 在 游 戏 中 的 角 色 以 及 比 赛 的 准 备 时 间 和 回 合 时 间. 收 到 游 戏 开 始 的 信 息 后, 各 个 玩 家 有 一 段 时 间 做 准 备, 这 段 时 间 称 为 准 备 时 间 (Start Clock), 通 常 约 30 至 120 秒. 准 备 时 间 结 束 后, 游 戏 正 式 进 入 第 一 回 合. 每 回 合 各 个 玩 家 具 有 一 段 思 考 时 间, 这 段 时 间 称 为 回 合 时 间 (Play Clock), 通 常 约 15 至 60 秒. 在 每 回 合 开 始 时, 游 戏 主 机 会 将 上 一 回 合 各 个 玩 家 采 取 的 动 作 发 送 给 所 有 玩 家, 玩 家 可 以 据 此 更 新 游 戏 状 态, 并 计 算 当 前 回 合 的 合 法 动 作. 在 回 合 时 间 结 束 前, 玩 家 需 要 选 择 一 个 合 法 动 作 发 送 给 游 戏 主 机. 游 戏 主 机 收 到 各 玩 家 的 动 作 后, 计 算 出 下 一 回 合 的 游 戏 状 态, 并 判 断 该 状 态 是 否 为 游 戏 结 束 状 态, 若 是 则 结 束 游 戏 并 计 算 得 分, 若 不 是 则 开 始 下 一 回 合. 1.4 游 戏 平 台 与 比 赛 机 器 玩 通 用 游 戏 的 能 力 不 容 易 设 定 一 个 绝 对 的 标 准, 因 而 GGP 平 台 与 比 赛 是 衡 量 GGP 研 究 进 展 的 主 要 媒 介.GGP 平 台 收 集 了 大 量 的 游 戏, 提 供 常 年 的 在 线 评 测 服 务, 主 要 用 于 日 常 的 GGP 研 究.GGP 比 赛 则 定 期 在 线 上 或 线 下 举 行, 为 GGP 研 究 者 提 供 交 流 的 机 会 和 场 所, 比 赛 的 结 果 具 有 权 威 性 GGP 平 台 GGP 平 台 是 常 年 运 行 GGP 游 戏 主 机 的 在 线 平 台, 一 般 提 供 数 百 个 游 戏 的 游 戏 规 则, 以 及 这 些 游 戏 的 历 史 对 局 信 息. 游 戏 玩 家 可 以 通 过 GGP 平 台 与 别 的 游 戏 玩 家 进 行 游 戏, 游 戏 的 结 果 将 影 响 玩 家 在 平 台 上 的 排 名.GGP 平 台 采 用 上 文 所 述 的 统 一 的 游 戏 交 互 机 制, 为 世 界 各 地 GGP 研 究 者 的 交 流 提 供 了 方 便 Tiltyard Tiltyard 是 由 斯 坦 福 大 学 运 行 的 GGP 平 台, 建 立 之 初 主 要 为 斯 坦 福 大 学 的 GGP 课 程 提 供 服 务, 现 已 成 为 GGP 研 究 者 重 要 的 交 流 平 台.GGP 玩 家 与 Tiltyard 建 立 连 接 后,Tiltyard 从 游 戏 库 中 随 机 抽 取 游 戏 并 组 织 GGP 玩 家 进 行 对 局.Tiltyard 统 计 对 局 的 历 史 信 息, 对 玩 家 进 行 排 名, 并 根 据 一 定 规 则 计 算 游 戏 的 难 度 和 平 衡 性 Dresden GGP Server Dresden GGP Server 是 由 德 国 德 累 斯 顿 工 业 大 学 运 行 的 GGP 平 台, 主 要 为 德 累 斯 顿 工 业 大 学 的 GGP 课 程 提 供 服 务. 它 的 最 大 特 点 是 加 入 了 对 非 完 全 信 息 游 戏 描 述 语 言 (GDL-II) 的 支 持. 此 外, 它 还 具 有 人 为 选 择 游 戏 和 对 手 的 功 能 GGPZone GGPZone 是 由 北 京 大 学 运 行 的 GGP 平 台, 也 是 目 前 国 内 唯 一 的 GGP 平 台. 它 致 力 于 为 GGP 研 究 提 供 更 加

7 丰 富 的 游 戏 研 究 工 具 比 赛 模 式 GGP 比 赛 GGP 比 赛 在 GGP 研 究 中 扮 演 关 键 角 色, 它 是 评 价 GGP 研 究 进 展 的 重 要 标 尺. 国 际 GGP 比 赛 已 成 功 举 办 多 届, 吸 引 来 自 世 界 各 地 的 爱 好 者 参 加.GGP 比 赛 与 其 他 游 戏 比 赛 一 道 探 索 机 器 游 戏 智 能 的 极 限 国 际 GGP 比 赛 国 际 GGP 比 赛 (International General Game Playing Competition) 每 年 举 办 一 次, 主 办 方 为 斯 坦 福 大 学, 2014 年 之 前 在 IJCAI 或 AAAI 会 议 现 场 比 赛,2014 年 起 改 为 在 线 比 赛. 国 际 GGP 比 赛 的 参 赛 者 来 自 世 界 各 地, 其 优 胜 者 代 表 GGP 玩 家 的 最 高 水 平. 由 于 GGP 研 究 正 处 于 不 断 发 展 的 阶 段, 国 际 GGP 比 赛 赛 制 也 在 逐 年 改 进.2014 年 的 赛 制 分 为 资 格 赛 和 决 赛. 资 格 赛 共 有 6 轮, 任 何 人 可 以 在 线 报 名 任 意 多 轮 资 格 赛, 只 要 在 其 中 一 轮 中 获 得 出 线 权 即 可 参 加 决 赛. 每 轮 资 格 赛 GGP 玩 家 需 要 完 成 若 干 单 人 和 多 人 游 戏, 主 办 方 将 根 据 GGP 玩 家 的 表 现, 决 定 是 否 给 予 决 赛 资 格. 决 赛 为 双 败 淘 汰 制, 每 对 相 遇 的 玩 家 进 行 3 或 5 局 对 局, 最 终 从 进 入 决 赛 的 16 名 玩 家 中 选 出 最 终 的 冠 军. 国 际 GGP 比 赛 历 年 的 冠 军 如 表 2 所 示. Table 2 Champions of international GGP competitions (from Wikipedia) 表 2 国 际 GGP 比 赛 历 年 冠 军 ( 摘 自 维 基 百 科 ) 年 份 GGP 玩 家 作 者 学 校 2005 Cluneplayer Jim Clune UCLA 2006 Fluxplayer Stephan Schiffel, Michael Thielscher Dresden University of Technology 2007 Cadiaplayer Yngvi Björnsson, Hilmar Finnsson Reykjavik University 2008 Cadiaplayer Yngvi Björnsson, Hilmar Finnsson, Gylfi Þór Guðmundsson Reykjavik University 2009 Ary Jean Méhat Paris 8 University 2010 Ary Jean Méhat Paris 8 University 2011 TurboTurtle Sam Schreiber Cadiaplayer Hilmar Finnsson, Yngvi Björnsson Reykjavik University 2013 TurboTurtle Sam Schreiber Sancho Steve Draper, Andrew Rose - 国 际 GGP 比 赛 冠 军 在 各 自 夺 冠 的 时 期 做 出 了 突 破 性 工 作,Cluneplayer 和 Fluxplayer 采 用 的 是 基 于 评 估 的 搜 索 算 法 [6,7],Cadiaplayer 首 次 采 用 基 于 模 拟 的 搜 索 算 法 [8],Ary 使 用 集 群 分 布 式 地 进 行 蒙 特 卡 洛 树 搜 索 [9],Sancho 对 命 题 网 络 的 推 理 速 度 等 做 了 大 量 优 化 GGP 比 赛 与 其 他 游 戏 比 赛 的 比 较 从 比 赛 内 容 的 角 度 看,GGP 比 赛 是 针 对 通 用 游 戏 的, 这 是 它 与 围 棋 象 棋 等 特 定 游 戏 比 赛 相 比 最 大 的 不 同 之 处. 虽 然 GGP 游 戏 集 合 是 有 限 的, 但 在 正 式 比 赛 时 通 常 采 用 原 创 的 新 游 戏, 以 免 玩 家 预 先 针 对 特 定 游 戏 做 准 备.GGP 比 赛 不 是 唯 一 的 通 用 游 戏 比 赛,GVGP(General Vedio Game Playing) [10,11] 是 针 对 通 用 视 频 游 戏 的 比 赛. [12] 此 外,Google 公 司 对 Atari 游 戏 的 研 究 也 与 GVGP 的 设 定 是 类 似 的. 从 比 赛 规 则 的 角 度 看,GGP 比 赛 不 限 制 参 赛 玩 家 使 用 的 硬 件 资 源, 这 是 它 相 比 统 一 硬 件 资 源 的 比 赛 的 不 同 之 处. 因 此,GGP 比 赛 不 仅 考 验 参 赛 者 编 写 软 件 算 法 的 能 力, 还 鼓 励 参 赛 者 探 索 更 新 的 硬 件 或 组 织 更 大 规 模 的 硬 件 来 解 决 问 题. 随 着 并 行 计 算 技 术 的 进 步,GGP 比 赛 的 竞 技 水 平 必 将 进 一 步 发 展. 2 GGP 研 究 的 主 要 问 题 GGP 研 究 的 目 标 是 让 计 算 机 以 人 类 水 平 玩 所 有 的 游 戏, 在 现 阶 段 是 离 散 的 同 步 的 确 定 性 的 完 全 信 息 的 游 戏. 设 计 一 个 不 出 错 的 按 GDL 规 则 玩 游 戏 的 程 序 是 容 易 的, 但 使 之 掌 握 尽 可 能 好 的 游 戏 策 略 却 相 当 困 难. 理 论 上, 任 何 一 个 离 散 的 同 步 的 确 定 性 完 全 信 息 的 游 戏 都 是 有 确 定 解 的, 即 所 有 游 戏 状 态 的 价 值 是 可 计 算 的, 这 就 决 定 了 玩 家 天 然 具 有 某 种 最 优 策 略. 但 由 于 大 部 分 游 戏 状 态 数 过 大, 所 有 游 戏 状 态 的 价 值 无 法 在 有 限

8 的 计 算 资 源 下 被 计 算 出 来, 才 使 得 寻 找 尽 可 能 好 的 游 戏 策 略 成 为 一 个 值 得 研 究 的 问 题. 如 果 把 对 游 戏 的 理 解 看 成 知 识,GGP 研 究 的 问 题 可 以 归 纳 为 游 戏 知 识 的 表 示 获 取 和 迁 移. 2.1 游 戏 知 识 表 示 为 了 设 计 好 的 游 戏 策 略, 必 然 要 先 深 入 理 解 游 戏. 理 解 游 戏 的 第 一 步, 就 是 表 示 游 戏. 博 弈 树 和 命 题 网 络 是 两 种 常 用 的 表 示 游 戏 的 工 具, 事 实 上 它 们 与 上 文 提 到 的 用 于 描 述 游 戏 规 则 的 状 态 机 模 型 和 GDL 是 等 价 的. 博 弈 树 和 命 题 网 络 从 两 种 不 同 的 角 度 看 待 游 戏, 在 理 解 游 戏 的 过 程 中 起 到 相 辅 相 成 的 作 用 博 弈 树 博 弈 树 是 一 棵 表 示 游 戏 的 树, 它 的 节 点 表 示 游 戏 状 态, 边 表 示 玩 家 的 动 作. 博 弈 树 的 根 节 点 表 示 游 戏 的 初 始 状 态, 叶 子 节 点 表 示 游 戏 的 结 束 状 态. 对 于 异 步 的 游 戏, 博 弈 树 的 各 节 点 处 只 有 一 个 玩 家 可 以 行 动, 各 节 点 作 为 父 节 点 发 出 的 各 条 边 对 应 可 行 动 玩 家 的 各 个 合 法 动 作, 边 所 连 接 的 子 节 点 对 应 动 作 作 用 于 父 节 点 的 结 果. 对 于 同 步 的 游 戏, 博 弈 树 的 每 个 节 点 处 所 有 玩 家 均 可 以 行 动, 因 此 各 节 点 作 为 父 节 点 发 出 的 边 对 应 的 是 所 有 玩 家 的 一 个 合 法 动 作 组 合, 边 所 连 接 的 儿 子 节 点 是 这 个 动 作 组 合 作 用 于 父 节 点 的 结 果. 博 弈 树 与 状 态 机 的 区 别 在 于 同 一 个 游 戏 状 态 在 状 态 机 中 只 对 应 一 个 节 点, 而 在 博 弈 树 中 可 能 对 应 多 个 节 点. 这 是 因 为 从 初 始 状 态 到 某 个 游 戏 状 态 可 能 存 在 多 条 路 径, 在 状 态 机 中 这 些 路 径 都 汇 聚 到 一 个 节 点 上, 而 在 博 弈 树 中 这 些 路 径 导 向 完 全 不 同 的 节 点. [13] 借 助 博 弈 树 的 结 构, 可 以 自 底 向 上 地 按 照 极 大 极 小 搜 索 的 思 想 计 算 游 戏 状 态 的 价 值. 具 体 地, 叶 子 节 点 是 游 戏 结 束 状 态, 其 对 于 各 个 玩 家 的 价 值 ( 以 下 称 价 值 组 合 ) 直 接 从 游 戏 规 则 得 出. 假 设 某 个 节 点 的 所 有 儿 子 节 点 的 价 值 组 合 都 已 计 算 得 出, 则 这 个 节 点 的 价 值 组 合 取 决 于 该 节 点 处 玩 家 如 何 行 动. 若 该 节 点 处 只 有 一 个 玩 家 可 以 行 动, 则 该 玩 家 一 定 选 择 对 于 自 身 价 值 最 高 的 儿 子 节 点. 因 此, 待 求 节 点 的 价 值 组 合 等 于 对 于 行 动 玩 家 价 值 最 高 的 儿 子 节 点 的 价 值 组 合. 由 此, 可 以 自 底 向 上 计 算 出 整 棵 博 弈 树 的 节 点 价 值, 同 时 确 定 各 玩 家 的 最 优 策 略. 对 于 同 步 的 游 戏 也 是 类 似 的, 不 同 之 处 在 于 每 回 合 可 行 动 的 玩 家 有 多 个, 因 而 每 回 合 都 是 一 次 博 弈, 需 要 求 解 纳 什 均 衡 才 能 得 到 最 优 策 略. 博 弈 树 从 最 为 细 致 的 角 度 刻 画 了 游 戏, 为 完 全 理 解 游 戏 提 供 了 理 论 上 的 可 能 性. 但 现 实 中 大 型 博 弈 树 的 结 构 受 制 于 计 算 资 源 而 无 法 被 完 全 知 晓, 只 能 了 解 其 局 部 的 信 息. 局 部 信 息 包 括 节 点 的 估 值 树 的 结 构 等, 它 们 是 非 常 重 要 的 游 戏 知 识 命 题 网 络 命 题 网 络 (Propositional Net, 简 称 Propnet) 是 一 种 借 助 逻 辑 电 路 表 示 游 戏 的 方 式. 命 题 网 络 首 先 用 状 态 命 题 集 合 编 码 游 戏 状 态, 使 任 意 一 个 游 戏 状 态 对 应 一 个 状 态 命 题 集 合 的 子 集. 其 次, 命 题 网 络 定 义 了 一 系 列 命 题 表 示 游 戏 元 素, 如 合 法 动 作 游 戏 结 束 游 戏 得 分 状 态 转 移 等. 最 后, 命 题 网 络 在 这 些 命 题 之 间 建 立 逻 辑 连 接, 使 得 它 能 够 完 成 表 3 中 的 推 理. 输 入 当 前 状 态 命 题 集 合, 各 玩 家 的 动 作 组 合 当 前 状 态 命 题 集 合 当 前 状 态 命 题 集 合 当 前 状 态 命 题 集 合 Table 3 Reasoning achieved by propositional net 表 3 命 题 网 络 能 够 完 成 的 推 理 输 出 下 一 状 态 命 题 集 合 各 玩 家 合 法 动 作 集 合 结 束 命 题 得 分 命 题 命 题 网 络 的 定 义 与 上 文 所 述 GDL 的 定 义 是 一 脉 相 承 的. 事 实 上, 命 题 网 络 就 是 GDL 的 展 开 形 式.GDL 通 过 一 系 列 等 价 变 换 ( 消 除 变 量 辅 助 命 题, 只 保 留 描 述 基 本 游 戏 元 素 的 命 题 及 它 们 之 间 的 逻 辑 关 系 ), 就 得 到 了 命 题 网 络. 通 常 可 以 用 一 个 逻 辑 电 路 图 来 表 示 命 题 网 络, 如 图 3 所 示.

9 1. (role white) (legal white a) (legal white b) 2. (<= p (does white a) (true s)) (<= q (not p)) (<= r q) (<= r (does white b)) 3. (<= (next s) r) 4. (<= (goal white 100) (true s)) Fig.3 Illustration of propositional net (from Stanford CS227b) 图 3 命 题 网 络 示 意 图 ( 摘 自 斯 坦 福 课 程 CS227b 课 件 ) 命 题 网 络 中 的 与 或 非 门 与 逻 辑 电 路 图 类 似. 图 中 的 竖 实 线 表 示 存 储 器, 它 存 储 当 前 回 合 上 级 电 路 传 来 的 值, 并 在 下 一 回 合 将 这 个 值 传 给 下 级 电 路. 博 弈 树 的 每 一 条 边 描 述 前 后 两 个 状 态 间 的 关 系, 而 命 题 网 络 将 前 后 状 态 分 别 作 为 输 入 和 输 出, 相 当 于 将 博 弈 树 所 有 的 边 汇 聚 到 一 起, 用 一 个 逻 辑 电 路 统 一 描 述 了 所 有 前 后 状 态 间 的 关 系. 可 以 想 象, 如 果 将 一 棵 随 机 生 成 的 博 弈 树 转 化 成 命 题 网 络, 由 于 编 码 的 无 规 律 性, 并 不 能 降 低 描 述 的 复 杂 度. 但 现 实 中 大 多 数 游 戏 的 状 态 具 有 良 好 的 局 部 性, 命 题 网 络 可 以 利 用 这 种 局 部 性 降 低 描 述 的 复 杂 度. 例 如, 棋 盘 游 戏 的 状 态 是 由 一 个 个 落 子 点 组 合 而 成 的, 玩 家 的 某 个 动 作 通 常 只 对 某 个 或 某 几 个 落 子 点 产 生 影 响, 这 就 是 一 种 局 部 性. 命 题 网 络 用 命 题 推 理 的 形 式 统 一 描 述 这 种 局 部 的 关 系, 合 并 了 大 量 博 弈 树 中 描 述 这 种 关 系 的 边, 从 而 降 低 了 描 述 的 复 杂 度. 命 题 网 络 从 一 个 相 对 精 简 的 角 度 刻 画 了 游 戏, 它 的 描 述 是 建 立 在 游 戏 状 态 的 局 部 关 系 之 上 的. 它 的 结 构 也 包 含 了 许 多 游 戏 知 识, 例 如 Cox 等 利 用 命 题 网 络 检 测 游 戏 的 可 拆 分 性 [14]. 2.2 游 戏 知 识 获 取 游 戏 知 识 可 能 有 无 穷 多 种, 这 里 讨 论 比 较 具 有 代 表 性 的 两 种 : 游 戏 状 态 估 值 和 游 戏 结 构. 游 戏 状 态 估 值 一 般 通 过 搜 索 博 弈 树 获 取, 而 游 戏 结 构 则 主 要 通 过 分 析 命 题 网 络 得 到 游 戏 状 态 估 值 如 所 述, 游 戏 状 态 的 价 值 是 游 戏 的 关 键 知 识. 由 于 资 源 有 限, 计 算 游 戏 状 态 的 精 确 值 是 不 现 实 的, 估 值 便 成 为 常 见 的 替 代 方 案. 最 朴 素 的 估 值 方 法 是 构 造 一 个 静 态 估 值 函 数, 它 以 游 戏 状 态 为 输 入, 估 值 为 输 出. 这 种 估 值 方 法 强 烈 依 赖 于 函 数 构 造 者 的 游 戏 经 验. 更 进 一 步 的 估 值 方 法 是 局 部 展 开 法, 它 在 待 估 值 节 点 处 局 部 展 开 博 弈 树, 对 展 开 部 分 的 节 点 做 静 态 估 值, 再 通 过 某 种 方 式 计 算 出 待 估 值 节 点 的 估 值. 这 种 估 值 方 法 将 博 弈 树 的 局 部 结 构 信 息 与 静 态 估 值 相 结 合, 通 常 更 为 准 确. 局 部 展 开 博 弈 树 的 过 程 也 是 搜 索 博 弈 树 的 过 程, 在 GGP 实 践 中 主 要 有 基 于 评 估 的 搜 索 和 基 于 模 拟 的 搜 索 静 态 估 值 函 数 静 态 估 值 函 数 是 对 一 个 游 戏 状 态 直 接 评 估 价 值 的 函 数. 对 于 特 定 的 游 戏, 人 们 往 往 能 从 游 戏 状 态 中 归 纳 出 一 些 有 用 的 局 部 结 构, 这 些 局 部 结 构 被 称 为 特 征. 常 见 的 特 征 包 括 五 子 棋 中 的 活 三, 象 棋 中 的 车, 围 棋 中 的 眼 等. 一 个 状 态 可 以 具 有 多 个 特 征, 一 个 特 征 也 可 以 被 许 多 状 态 共 同 拥 有. 人 们 认 识 到, 同 一 个 特 征 对 不 同 状 态 的 估 值 的 贡 献 往 往 是 相 似 的. 因 此, 可 以 从 少 量 状 态 归 纳 出 贡 献 明 显 的 特 征, 再 将 这 些 特 征 应 用 于 其 他 状 态 的 估 值, 以 此 来 构 造 静 态 估 值 函 数. 在 GGP 框 架 下, 机 器 玩 家 从 接 触 游 戏 规 则 到 开 始 玩 游 戏 只 有 很 短 的 时 间, 这 使 发 现 并 利 用 特 征 构 造 静 态 估 值 函 数 成 为 挑 战.GGP 游 戏 的 特 征 可 以 大 致 分 为 如 下 三 类 : 适 用 于 特 定 游 戏 的 专 用 特 征. 由 于 游 戏 规 则 不 可 预 知, 专 用 特 征 无 法 被 事 先 写 入 程 序, 必 须 由 程 序 自 行 从 游 戏 规 则 中 生 成. 由 于 特 征 的 数 量 太 大, 目 前 尚 未 出 现 有 效 的 算 法 自 动 生 成 有 效 的 专 用 特 征.Kuhlmann [15] 提 出 了 特 征 树 (feature tree) 结 构 表 示 游 戏 的 特 征, 并 提 出 了 一 个 生 成 和 筛 选 特 征 的 [16] 方 法, 但 该 方 法 在 实 验 中 效 果 并 不 理 想.Haufe 等 提 出 的 State Sequence Invariants 可 以 用 于 专 用 特 征 的 表 示, 但 是 其 工 作 未 涉 及 专 用 特 征 的 生 成 和 筛 选. 适 用 于 所 有 游 戏 的 通 用 特 征. 通 用 特 征 是 与 特 定 游 戏 无 关 的, 人 们 可 以 事 先 总 结 和 定 义.Clune [6] 应 用

10 了 行 动 力 (mobility) 特 征, 即 玩 家 在 某 一 游 戏 状 态 下 的 合 法 动 作 数 量, 这 种 特 征 在 一 定 程 度 上 反 映 了 玩 家 在 游 戏 中 的 生 存 能 力 ( 一 般 认 为 合 法 动 作 数 量 越 多 生 存 能 力 越 强 ). [17] 介 于 通 用 和 专 用 之 间 的 特 征. 这 类 特 征 具 有 一 定 的 适 用 范 围, 适 用 于 某 一 类 别 的 游 戏.Kuhlmann 等 用 语 法 结 构 模 式 匹 配 的 方 法 检 测 游 戏 是 否 具 有 棋 子 棋 盘 等 特 征, 这 类 特 征 仅 适 用 于 棋 盘 游 戏 基 于 评 估 的 搜 索 在 GGP 的 语 境 中, 基 于 评 估 的 搜 索 (Evaluation-based Search Approach) 指 的 是 传 统 的 极 大 极 小 搜 索 及 其 变 种. 这 种 搜 索 方 式 有 两 个 特 点, 一 是 以 平 衡 的 方 式 扩 展 博 弈 树, 二 是 需 要 一 个 静 态 估 值 函 数. 以 平 衡 的 方 式 扩 展 博 弈 树 是 违 反 人 类 经 验 的. 人 在 下 分 支 因 子 很 大 的 棋 时, 通 常 花 很 短 的 时 间 识 别 并 排 除 前 途 较 差 的 走 法, 而 把 大 部 分 时 间 花 在 深 入 探 索 前 途 较 好 的 走 法 上.α-β 剪 枝 和 静 止 期 搜 索 (Quiescence Search) 等 技 术 应 用 了 人 的 这 种 思 想, 对 重 要 的 分 支 做 更 深 入 的 搜 索, 在 一 定 程 度 上 打 破 了 平 衡. 但 真 正 将 非 平 衡 扩 展 的 思 想 贯 彻 到 底 的 是 后 文 将 要 讨 论 的 基 于 模 拟 的 搜 索. 如 所 述, 在 GGP 框 架 下 构 造 静 态 估 值 函 数 是 困 难 的. 即 使 构 造 出 了 有 效 的 静 态 估 值 函 数, 其 所 消 耗 的 计 算 资 源 也 将 限 制 搜 索 的 节 点 数. 在 早 期 的 国 际 GGP 比 赛 中, 基 于 评 估 的 搜 索 占 据 着 主 导 地 位, 后 来 逐 渐 被 基 于 模 拟 的 搜 索 取 代. 虽 然 如 此, 静 态 估 值 函 数 的 构 造 还 是 值 得 继 续 探 索 的 基 于 模 拟 的 搜 索 在 GGP 的 语 境 中, 基 于 模 拟 的 搜 索 (Simulation-based Search Approach) 指 的 是 蒙 特 卡 洛 树 搜 索 (Monte [18] Carlo Tree Search) 算 法 及 其 变 种. 与 基 于 评 估 的 搜 索 方 法 不 同, 基 于 模 拟 的 搜 索 方 法 以 非 平 衡 的 方 式 扩 展 博 弈 树, 且 不 需 要 静 态 评 估 函 数. 基 于 模 拟 的 搜 索 算 法 由 选 择 (Selection) 扩 展 (Expansion) 模 拟 (Simulation) 反 向 传 播 (Backpropagation) 四 个 步 骤 重 复 执 行 而 实 现, 如 图 4 所 示. 第 一 步, 从 博 弈 树 的 根 节 点 开 始, 递 归 地 从 子 节 点 中 选 取 最 佳 的 节 点, 直 到 选 中 一 个 叶 节 点 为 止 ; 第 二 步, 扩 展 选 中 的 叶 节 点, 即 将 叶 节 点 的 一 个 子 节 点 加 入 博 弈 树 ; 第 三 步, 从 新 加 入 的 子 节 点 开 始 做 蒙 特 卡 洛 模 拟, 即 随 机 地 进 行 游 戏 直 到 结 束 ; 第 四 步, 将 蒙 特 卡 洛 模 拟 的 结 果 反 馈 到 叶 节 点 及 它 的 各 个 祖 先 节 点 处. 其 中, 第 一 步 中 最 佳 节 点 的 定 义 是 Upper Confidence Bounds (UCB) 值 最 大 的 节 点, 待 选 择 节 点 i [19] 的 UCB 值 的 计 算 公 式 如 下 : ln N vi + C, n 其 中 C 为 常 数,v i 代 表 节 点 i 的 估 值,n i 代 表 节 点 i 被 访 问 的 次 数,N 代 表 所 有 待 选 择 节 点 被 访 问 的 总 次 数 即 i 的 平 均 值.. 在 MCTS 中,v i 的 值 通 过 第 四 步 反 向 传 播 得 到, 即 v i 等 于 从 节 点 i 及 其 子 孙 节 点 开 始 的 蒙 特 卡 洛 模 拟 结 果

11 重 复 N 次 选 择 扩 展 模 拟 反 向 传 播 Fig.4 Illustration of MCTS Algorithm (from Chaslot, Guillaume, et al. "Monte-Carlo Tree Search: A New Framework for Game AI." AIIDE ) 图 4 蒙 特 卡 洛 树 搜 索 算 法 示 意 图 ( 摘 自 Chaslot, Guillaume, et al. "Monte-Carlo Tree Search: A New Framework for Game AI." AIIDE ) [20] 自 从 Björnsson 等 将 基 于 模 拟 的 搜 索 引 入 国 际 GGP 比 赛 以 来, 该 算 法 表 现 突 出, 目 前 已 成 为 主 流 的 算 法. 它 用 随 机 模 拟 的 方 法 评 估 游 戏 状 态, 回 避 了 通 用 游 戏 难 以 构 造 静 态 评 估 函 数 的 问 题. 此 外, 大 量 的 随 机 模 拟 适 合 并 行 计 算 也 使 基 于 模 拟 的 搜 索 具 有 优 势. 尽 管 基 于 模 拟 的 搜 索 已 经 在 实 践 中 取 得 成 功, 其 依 然 具 有 很 大 的 改 进 空 间. 例 如, 如 何 在 搜 索 时 获 取 和 应 用 游 戏 知 识 以 提 高 搜 索 效 率 就 是 一 个 值 得 关 注 的 问 题,Finnsson 等 尝 试 使 用 游 戏 知 识 指 导 模 拟 过 程 [21], 在 一 定 程 度 上 提 升 了 搜 索 的 效 率 游 戏 结 构 游 戏 结 构 也 是 一 种 游 戏 知 识. 博 弈 树 状 态 机 命 题 网 络 GDL 等 不 同 的 游 戏 表 示 方 式 从 各 自 的 角 度 描 述 游 戏, 其 反 映 的 游 戏 结 构 也 是 不 同 的. 博 弈 树 和 状 态 机 规 模 太 大, 利 用 它 们 的 结 构 特 征 还 比 较 困 难, 因 此 这 里 主 要 讨 论 命 题 网 络 和 GDL 的 结 构 游 戏 对 称 性 和 等 价 性 游 戏 对 称 性 包 括 玩 家 的 对 称 性 动 作 的 对 称 性 状 态 的 对 称 性 等, 现 实 中 的 游 戏 大 多 具 有 对 称 性. 发 现 游 戏 的 对 称 性, 有 助 于 提 高 搜 索 的 效 率, 因 为 对 称 的 游 戏 元 素 可 以 共 享 估 值.GDL 和 命 题 网 络 用 命 题 的 形 式 表 达 玩 家 动 作 状 态 等 游 戏 元 素, 因 此 这 些 游 戏 元 素 的 对 称 就 表 现 为 命 题 的 对 称. 发 掘 命 题 的 对 称, 可 以 通 过 分 析 GDL 或 命 题 网 络 的 结 构 实 现 [22]. 游 戏 等 价 性 指 的 是 两 个 不 同 游 戏 的 玩 家 动 作 状 态 之 间 存 在 某 个 一 一 映 射 的 关 系, 在 这 个 映 射 关 系 下 游 戏 的 状 态 更 新 合 法 动 作 终 局 得 分 等 都 是 等 价 的, 比 如 Tic-tac-toe 和 Number Scrabble [23]. 如 果 能 够 发 现 一 个 新 游 戏 和 已 知 的 游 戏 等 价, 那 么 就 可 以 利 用 已 知 游 戏 的 知 识 来 玩 新 游 戏. 虽 然 等 价 游 戏 存 在 的 可 能 性 很 低, 但 它 是 讨 论 游 戏 相 似 性 的 基 础, 而 知 识 在 相 似 游 戏 之 间 的 迁 移 是 很 有 思 考 价 值 的 问 题. 证 明 两 个 游 戏 等 价 的 过 程 与 发 掘 一 个 游 戏 的 对 称 性 的 过 程 具 有 很 强 的 关 联 性. 事 实 上, 判 断 游 戏 是 否 等 价 的 方 法 是 考 察 两 个 游 戏 的 GDL 或 命 题 网 络 是 否 同 构, 而 发 掘 游 戏 对 称 性 的 方 法 是 考 察 GDL 或 命 题 网 络 的 所 有 自 同 构. 因 此, 这 两 个 问 题 在 解 决 方 法 上 是 相 通 的 游 戏 拆 分 在 近 年 的 国 际 GGP 比 赛 中, 组 合 游 戏 被 作 为 一 个 考 察 的 重 点. 如 所 述, 组 合 游 戏 指 的 是 将 若 干 个 相 同 或 不 同 的 游 戏 通 过 某 种 方 式 组 合 在 一 起, 形 成 一 个 新 的 游 戏. 与 之 相 对 应 的 技 术, 就 叫 做 游 戏 拆 分 (Game Factoring).

12 游 戏 有 不 同 的 组 合 方 式, 一 种 简 单 的 组 合 方 式 是 两 个 玩 家 同 时 玩 两 个 相 同 的 游 戏, 每 回 合 只 能 选 择 其 中 一 个 游 戏 做 动 作. 比 如, 两 个 玩 家 同 时 下 两 盘 国 际 象 棋, 但 每 回 合 只 能 选 择 其 中 一 个 棋 盘 下, 最 后 任 意 一 个 棋 盘 结 束 则 整 个 游 戏 结 束. 在 这 样 的 规 则 下, 玩 家 识 别 出 两 个 相 互 独 立 的 棋 盘 是 十 分 重 要 的, 它 可 以 使 整 个 游 戏 过 程 的 分 支 因 子 下 降 一 半. 游 戏 拆 分 可 以 通 过 分 析 命 题 网 络 实 现 [14]. 通 过 分 析 命 题 之 间 的 依 赖 关 系, 有 可 能 把 命 题 网 络 拆 分 成 几 个 部 分, 形 成 独 立 的 几 个 子 游 戏. 2.3 游 戏 知 识 迁 移 GGP 的 框 架 为 讨 论 知 识 在 不 同 游 戏 之 间 迁 移 提 供 了 平 台, 这 是 GGP 研 究 不 同 于 特 定 游 戏 研 究 之 处, 也 是 极 具 挑 战 之 处. 哪 些 知 识 可 以 在 哪 些 游 戏 之 间 迁 移? 知 识 迁 移 可 以 多 大 程 度 提 高 对 新 游 戏 的 认 识? 这 些 问 题 都 有 待 深 入 探 索 知 识 在 相 同 游 戏 之 间 迁 移 如 所 述, 表 现 形 式 不 同 的 游 戏 可 能 在 本 质 上 可 能 是 相 同 的. 发 现 这 一 点 就 可 以 将 旧 游 戏 的 知 识 迁 移 到 新 游 戏 中. 除 完 全 相 同 外, 部 分 相 同 和 动 态 相 同 也 是 值 得 关 注 的. 考 虑 到 一 个 游 戏 可 能 可 以 拆 分 成 若 干 个 子 游 戏, 若 两 个 游 戏 存 在 相 同 的 子 游 戏, 则 可 以 在 子 游 戏 之 间 传 递 知 识, 这 种 情 况 就 是 游 戏 的 部 分 相 同. 动 态 相 同 指 的 是 两 个 游 戏 在 初 始 状 态 下 不 同, 但 在 游 戏 过 程 中 可 能 达 到 相 同 的 状 态, 如 正 常 中 国 象 棋 与 让 子 的 中 国 象 棋 可 以 在 游 戏 过 程 中 达 到 相 同 的 状 态. 两 个 动 态 相 同 的 游 戏 可 以 共 享 状 态 估 值 等 知 识 知 识 在 相 似 游 戏 之 间 迁 移 游 戏 的 相 似 性 包 括 多 种 多 样 的 情 况, 一 些 常 见 的 情 况 包 括 : 仅 棋 盘 大 小 或 形 状 不 同, 如 棋 盘 大 小 为 15*15 的 五 子 棋 和 棋 盘 大 小 为 16*16 的 五 子 棋 ; 仅 棋 子 不 同, 如 围 棋 和 让 2 子 的 围 棋 ; 仅 步 数 限 制 不 同, 如 不 限 回 合 数 的 国 际 象 棋 和 限 制 200 回 合 结 束 的 国 际 象 棋. 在 这 些 情 况 下, 关 于 游 戏 特 征 游 戏 结 构 的 知 识 大 多 是 可 迁 移 的. 例 如, 人 们 下 五 子 棋 时 一 般 不 会 因 为 棋 盘 大 小 相 差 一 行 一 列 而 改 变 游 戏 策 略 ; 下 让 2 子 围 棋 时, 对 于 各 种 棋 型 的 估 值 与 正 常 围 棋 是 相 同 的 ; 下 限 制 200 回 合 的 国 际 象 棋 时, 开 始 阶 段 几 乎 不 会 考 虑 回 合 数 的 限 制. 然 而, 量 变 会 引 发 质 变. 棋 盘 为 5*5 和 15*15 的 五 子 棋 正 常 围 棋 和 让 50 子 的 围 棋 不 限 回 合 数 和 限 制 30 回 合 结 束 的 国 际 象 棋 肯 定 有 很 大 的 不 同, 知 识 在 它 们 之 间 的 传 递 要 打 很 大 的 折 扣. 如 何 用 一 般 的 方 法 量 化 游 戏 的 相 似 程 度, 从 而 确 定 知 识 在 多 大 程 度 上 可 以 传 递, 是 一 个 有 待 讨 论 的 问 题. 此 外, 还 需 要 注 意 到, 有 时 游 戏 规 则 微 小 的 改 动 会 导 致 游 戏 变 得 很 不 一 样. 比 如, 考 虑 正 常 的 五 子 棋 游 戏 和 先 连 成 五 子 者 失 败 的 自 杀 五 子 棋 游 戏, 二 者 具 有 相 同 的 游 戏 状 态 空 间 合 法 动 作 结 束 条 件, 而 只 有 结 束 状 态 下 的 游 戏 得 分 不 同, 其 游 戏 策 略 就 大 相 径 庭, 很 难 说 清 有 哪 些 知 识 是 可 以 在 二 者 之 间 迁 移 的. 可 见, 量 化 两 个 游 戏 的 相 似 程 度 是 一 个 相 当 困 难 的 问 题. 对 于 这 个 问 题,Kuhlmann 做 了 较 为 深 入 的 探 索 [15] : 1. 定 义 了 几 种 游 戏 相 似 的 情 况 ( 如 棋 盘 大 小 步 数 限 制 等 ); 2. 通 过 将 游 戏 规 则 转 化 成 Rule Graph 并 分 析 两 个 游 戏 Rule Graph 的 相 似 性, 得 到 游 戏 的 相 似 性 ; 3. 对 于 相 似 的 游 戏, 定 义 了 对 称 性 估 值 函 数 蒙 特 卡 洛 搜 索 树 三 种 可 以 迁 移 的 知 识, 并 分 别 提 出 了 迁 移 的 方 法, 最 终 在 对 称 性 迁 移 和 估 值 函 数 迁 移 的 实 验 中 取 得 了 理 想 的 结 果. Kuhlmann 的 工 作 证 明 了 知 识 在 相 似 游 戏 之 间 迁 移 的 可 行 性, 但 也 存 在 着 诸 多 局 限, 包 括 游 戏 相 似 情 况 的 局 限 性 估 值 函 数 迁 移 仅 适 用 于 用 强 化 学 习 (Reinforcement Learning) 训 练 估 值 函 数 蒙 特 卡 洛 搜 索 树 迁 移 取 得 了 负 面 的 实 验 结 果 等 知 识 在 任 意 游 戏 之 间 迁 移 能 够 在 任 意 游 戏 之 间 迁 移 的 知 识, 可 以 被 称 为 通 用 知 识. 通 用 知 识 一 定 是 关 于 最 基 本 的 游 戏 元 素 的 知 识, 这 些 游 戏 元 素 在 任 何 游 戏 中 都 存 在, 比 如 博 弈 树 的 局 部 结 构 命 题 网 络 的 局 部 结 构 等. 通 用 知 识 一 旦 被 掌 握,

13 即 可 应 用 于 所 有 的 游 戏, 因 而 是 非 常 重 要 的. 通 用 知 识 包 括 上 文 提 到 的 通 用 游 戏 特 征 的 估 值. 博 弈 树 的 局 部 结 构 就 是 一 种 通 用 游 戏 特 征. 在 一 个 游 戏 中 [24] 对 不 同 的 博 弈 树 局 部 结 构 进 行 估 值, 再 将 估 值 结 果 应 用 于 另 一 个 游 戏, 是 有 可 能 的.Banerjee 等 提 出 了 针 对 特 定 游 戏 生 成 常 见 的 博 弈 树 局 部 结 构 的 方 法, 并 将 这 些 局 部 结 构 作 为 游 戏 的 特 征. 实 验 证 明, 在 已 知 游 戏 和 未 知 游 戏 使 用 相 同 的 游 戏 特 征 进 行 强 化 学 习 训 练 的 前 提 下, 将 已 知 游 戏 的 训 练 结 果 作 为 未 知 游 戏 的 初 始 训 练 参 数, 将 有 助 于 提 高 未 知 游 戏 训 练 的 质 量 或 缩 短 训 练 时 间. 此 外, 上 文 提 到 的 获 取 游 戏 知 识 的 方 法, 比 如 蒙 特 卡 洛 树 搜 索 算 法, 在 某 种 意 义 上 也 是 一 种 通 用 知 识. 在 这 种 意 义 上, 任 何 有 助 于 通 用 游 戏 程 序 进 步 的 方 法, 都 可 以 被 视 为 游 戏 的 通 用 知 识. 3 GGP 研 究 的 若 干 展 望 可 以 预 见,GGP 研 究 在 游 戏 知 识 表 示 方 面 将 稳 步 扩 展, 在 游 戏 知 识 获 取 方 面 将 更 加 深 入, 而 在 游 戏 知 识 迁 移 方 面 将 迎 来 曙 光. 下 文 分 别 从 GGP 规 则 GGP 玩 家 和 GGP 平 台 的 角 度 展 望 GGP 研 究 的 未 来 发 展 方 向. 3.1 GGP 规 则 展 望 GGP 规 则 包 括 GGP 比 赛 采 用 的 语 言 赛 制 等, 它 决 定 了 GGP 研 究 涵 盖 的 范 围.GDL 作 为 目 前 的 GGP 游 戏 描 述 语 言, 其 描 述 能 力 具 有 相 当 的 局 限 性, 如 所 述. 随 着 研 究 的 深 入, 扩 展 游 戏 语 言 的 描 述 能 力 是 必 然 的 趋 势 : 描 述 非 确 定 性 的 信 息 完 全 的 游 戏,GDL-II 已 经 做 出 了 很 好 的 探 索 ; 描 述 非 回 合 制 的 游 戏, 如 星 际 争 霸 帝 国 时 代 等 即 时 战 略 游 戏. 此 外, 放 弃 描 述 游 戏 规 则 也 是 可 能 的 发 展 方 向. 如 Google 公 司 对 Atari 游 戏 的 研 究 [12], 机 器 玩 家 不 知 道 确 切 的 游 戏 规 则, 只 通 过 模 拟 玩 游 戏, 得 到 游 戏 状 态 动 作 得 分 的 历 史 经 验 来 学 习 游 戏 策 略. 3.2 GGP 玩 家 展 望 现 阶 段 GGP 玩 家 在 知 识 获 取 方 面 已 经 形 成 了 比 较 成 熟 的 方 法, 而 在 知 识 迁 移 方 面 还 可 以 做 更 多 的 探 索. 以 2014 年 国 际 GGP 比 赛 冠 军 Sancho 为 例, 它 采 用 并 行 的 蒙 特 卡 洛 树 搜 索 算 法, 且 在 实 现 层 面 对 命 题 网 络 进 行 了 大 量 优 化. 它 能 在 游 戏 开 始 阶 段 对 游 戏 进 行 分 析, 从 而 检 查 游 戏 的 可 拆 分 性 以 及 调 整 各 种 启 发 函 数 的 参 数. 它 获 取 游 戏 知 识 的 能 力 超 过 了 竞 争 对 手, 这 是 它 成 功 的 主 要 原 因. 此 外, 它 在 游 戏 知 识 迁 移 方 面 也 做 了 一 些 探 索, 比 如 判 断 新 游 戏 是 否 与 已 知 的 游 戏 相 同, 从 而 利 用 已 有 的 游 戏 经 验 注 重 游 戏 知 识 对 蒙 特 卡 洛 树 搜 索 的 帮 助 虽 然 基 本 的 蒙 特 卡 洛 树 搜 索 算 法 不 需 要 游 戏 知 识, 但 结 合 游 戏 知 识 可 以 使 它 变 得 更 好. 游 戏 知 识 可 以 在 多 方 面 提 升 蒙 特 卡 洛 树 搜 索 算 法, 包 括 : 在 UCB 公 式 中 加 入 游 戏 知 识 相 关 的 项, 影 响 选 择 阶 段 ; 在 模 拟 阶 段 对 合 法 动 作 或 后 继 状 态 做 快 速 的 评 估, 从 完 全 随 机 的 模 拟 改 为 带 概 率 分 布 的 模 拟 ; 利 用 游 戏 结 构 的 局 部 性, 动 态 地 拆 分 游 戏, 运 用 局 部 搜 索 提 升 搜 索 效 率 应 用 其 他 人 工 智 能 算 法 目 前 许 多 人 工 智 能 算 法 被 成 功 地 应 用 到 了 GGP 的 研 究 中, 最 典 型 的 就 是 蒙 特 卡 洛 树 搜 索 算 法. 将 来 更 多 的 人 工 智 能 算 法 或 许 可 以 被 应 用 到 GGP 研 究 中, 包 括 : 用 遗 传 算 法 生 成 和 筛 选 游 戏 特 征, 可 以 从 最 基 本 的 游 戏 特 征 通 过 逻 辑 组 合 逐 渐 演 变 出 复 杂 的 特 征 ; 用 深 度 神 经 网 络 构 建 游 戏 特 征, 深 度 神 经 网 络 的 层 次 对 应 游 戏 特 征 的 复 杂 程 度 ; 将 更 多 的 专 用 游 戏 算 法 引 入 GGP 使 用 更 加 强 大 的 硬 件 GGP 比 赛 没 有 限 制 硬 件 的 使 用, 因 而 使 用 更 强 大 的 硬 件 是 提 升 GGP 玩 家 水 平 的 重 要 方 法. 目 前, 硬 件 方 面 的 提 升 主 要 体 现 在 使 用 更 多 计 算 核 心, 实 现 蒙 特 卡 洛 树 搜 索 的 并 行 计 算. 将 来, 更 多 的 硬 件 可 能 被 利 用 : 使 用 FPGA 实 现 命 题 网 络, 大 大 加 快 游 戏 状 态 的 更 新 过 程 ; 使 用 GPU 做 并 行 的 蒙 特 卡 洛 模 拟 ;

14 使 用 超 级 计 算 机 做 大 规 模 的 特 征 生 成 和 筛 选 蒙 特 卡 洛 模 拟 等. 3.3 GGP 平 台 展 望 GGP 平 台 具 有 引 领 GGP 研 究 的 作 用, 应 该 在 许 多 方 面 开 拓 进 取 添 加 有 针 对 性 的 游 戏 目 前 GGP 游 戏 的 数 量 级 还 较 小, 而 引 入 更 多 的 游 戏 无 疑 将 增 强 GGP 研 究 的 通 用 性.GGP 平 台 除 了 将 各 种 已 经 存 在 的 游 戏 翻 译 成 GDL 之 外, 还 应 该 人 为 创 造 一 些 具 有 特 点 的 游 戏. 这 些 游 戏 可 以 反 映 人 类 对 某 些 特 定 概 念 的 认 识, 比 如 介 绍 的 组 合 游 戏 反 映 了 人 类 对 组 合 的 认 识. 其 他 的 例 子 包 括 对 单 调 性 的 认 识 等. 这 样 的 认 识 在 人 看 来 一 目 了 然, 但 对 于 机 器 来 说 可 能 是 很 困 难 的. 有 针 对 性 地 创 造 这 类 游 戏, 将 对 机 器 认 识 到 这 些 概 念 起 到 积 极 作 用 鼓 励 探 索 知 识 迁 移 为 了 鼓 励 GGP 研 究 者 探 索 知 识 迁 移,GGP 平 台 可 以 提 供 更 有 针 对 性 的 比 赛 机 制. 由 于 直 接 研 究 通 用 知 识 是 比 较 困 难 的, 可 以 先 研 究 知 识 在 相 似 游 戏 中 的 迁 移. 例 如, 将 Connect Four 游 戏 的 各 种 变 体 划 入 一 个 集 合, 再 将 这 个 集 合 拆 分 为 训 练 集 和 测 试 集.GGP 玩 家 可 以 拥 有 一 段 时 间 在 无 人 指 导 的 环 境 下 对 训 练 集 中 的 游 戏 进 行 学 习, 然 后 在 正 式 比 赛 时 使 用 测 试 集 中 的 游 戏. 在 这 种 赛 制 下, 善 于 将 已 有 知 识 迁 移 到 相 似 游 戏 的 GGP 玩 家 将 获 得 优 势. 4 结 束 语 本 文 介 绍 了 GGP 研 究 的 基 本 框 架 和 主 要 问 题, 并 对 GGP 未 来 发 展 做 了 若 干 展 望.GGP 研 究 的 目 标 是 提 升 机 器 的 通 用 游 戏 智 能, 这 与 特 定 游 戏 的 研 究 是 不 同 的, 代 表 着 人 工 智 能 未 来 的 一 个 发 展 方 向.GGP 研 究 至 今 已 取 得 了 一 定 的 进 展, 但 在 深 度 和 广 度 两 方 面 都 还 有 很 大 的 拓 展 余 地, 因 而 是 值 得 广 大 研 究 者 关 注 的. 致 谢 在 此, 向 对 本 文 的 工 作 给 予 支 持 和 建 议 的 北 京 大 学 许 卓 群 教 授 表 示 感 谢. References: [1] Genesereth M, Love N, Pell B. General game playing: Overview of the AAAI competition. AI magazine, 2005, 26(2): 62. [2] Allis LV. Searching for Solutions in Games and Artificial Intelligence [Ph.D. Thesis]. Maastricht, the Netherlands: University of Limburg, [3] Love N, Hinrichs T, Haley D, Schkufza E, Genesereth M. General game playing: Game description language specification. LG : Stanford California, Stanford University, [4] Schiffel S, Thielscher M. A multiagent semantics for the game description language. In: Béatrice Duval, Jaap van den Herik, Stephane Loiseau, Joaquim Filipe, eds. Agents and Artificial Intelligence. Berlin, Heidelberg: Springer, [5] Thielscher M. A General Game Description Language for Incomplete Information Games. In: Proc. of the 24th AAAI Conf. on Artificial Intelligence. Menlo Park, California: AAAI Press, [6] Clune J. Heuristic evaluation functions for general game playing. In: Proc. of the 22nd AAAI Conf. on Artificial Intelligence. Menlo Park, California: AAAI Press, [7] Schiffel S, Thielscher M. Fluxplayer: A successful general game player. In: Proc. of the 22nd AAAI Conf. on Artificial Intelligence. Menlo Park, California: AAAI Press, [8] Finnsson H, Björnsson Y. Simulation-Based Approach to General Game Playing. In: Proc. of the 23rd AAAI Conf. on Artificial Intelligence. Menlo Park, California: AAAI Press, [9] Méhat J, Cazenave T. A Parallel General Game Player. Künstliche Intelligenz, 2011, 25(1): /s [10] Levine J, Congdon CB, Ebner M, Kendall G, Lucas SM, Miikkulainen R, Schaul T, Thompson T. General Video Game Playing. Artificial and Computational Intelligence in Games, 2013, 6: /DFU.Vol [11] Bellemare MG, Naddaf Y, Veness J, Bowling M. The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 2013, 47:

15 [12] Mnih V, Kavukcuoglu K, Silver D, Rusu AA, Veness J, Bellemare MG, Graves A, Riedmiller M, Fidjeland AK, Ostrovski G, Petersen S, Beattie C, Sadik A, Antonoglou I, King H, Kumaran D, Wierstra D, Legg S, Hassabis D. Human-level control through deep reinforcement learning. Nature, 2015, 518(7540): /nature [13] Neumann JV. Zur Theorie der Gesellschaftsspiele. Mathematische Annalen, 1928, 100(1): /BF [14] Cox E, Schkufza E, Madsen R, Genesereth M. Factoring general games using propositional automata. In Proc. of the IJCAI Workshop on General Intelligence in Game-Playing Agents (GIGA). Menlo Park, California: AAAI Press, [15] Kuhlmann GJ. Automated domain analysis and transfer learning in general game playing [Ph.D. Thesis]. Austin, Texas: The University of Texas at Austin, [16] Haufe S, Schiffel S, Thielscher M. Automated verification of state sequence invariants in general game playing. Artificial Intelligence, 2012, 187: [17] Kuhlmann G, Dresner K, Stone P. Automatic heuristic construction in a complete general game player. In: Proc. of the 21st AAAI Conf. on Artificial Intelligence. Menlo Park, California: AAAI Press, [18] Browne CB, Powley E, Whitehouse D, Lucas SM, Cowling P, Rohlfshagen P, Tavener S, Perez D, Samothrakis S, Colton S. A survey of monte carlo tree search methods. Computational Intelligence and AI in Games, IEEE Transactions on, 2012, 4(1): [19] Auer P. Using confidence bounds for exploitation-exploration trade-offs. The Journal of Machine Learning Research, 2003, 3: [20] Björnsson Y, Finnsson H. Cadiaplayer: A simulation-based general game player. Computational Intelligence and AI in Games, IEEE Transactions on, 2009, 1(1): [21] Finnsson H, Björnsson Y. Learning Simulation Control in General Game-Playing Agents. In: Proc. of the 24th AAAI Conf. on Artificial Intelligence. Menlo Park, California: AAAI Press, [22] Schiffel S. Symmetry Detection in General Game Playing. In: Proc. of the 24th AAAI Conf. on Artificial Intelligence. Menlo Park, California: AAAI Press, [23] Pell B. Strategy generation and evaluation for meta-game playing [Ph.D. Thesis]. Cambridge, United Kingdom: University of Cambridge, [24] Banerjee B, Stone P. General Game Learning Using Knowledge Transfer. In Proc. of the 20th International Joint Conference on Artificial Intelligence. Menlo Park, California: AAAI Press,