摘 要 就 一 个 游 戏 而 言, 对 于 参 与 者, 需 要 研 究 不 同 的 策 略 去 达 到 胜 利, 而 对 于 游 戏 设 计 者, 则 需 要 研 究 这 个 游 戏 的 平 衡 性 与 记 分 规 则 的 合 理 性, 并 不 断 去 调 整 它 们 在 本 文 中, 我 们

三 国 杀 游 戏 平 衡 性 与 记 分 规 则 合 理 性 分 析 报 告

摘 要 就 一 个 游 戏 而 言, 对 于 参 与 者, 需 要 研 究 不 同 的 策 略 去 达 到 胜 利, 而 对 于 游 戏 设 计 者, 则 需 要 研 究 这 个 游 戏 的 平 衡 性 与 记 分 规 则 的 合 理 性, 并 不 断 去 调 整 它 们 在 本 文 中, 我 们 将 站 在 游 戏 设 计 者 的 角 度 研 究 最 近 较 为 流 行 的 三 国 杀 游 戏 的 平 衡 性 与 记 分 规 则 合 理 性, 通 过 简 化 三 国 杀 游 戏, 建 立 一 个 用 随 机 过 程 描 述 的 游 戏 模 型, 对 游 戏 参 与 者 进 行 简 单 的 讨 论 之 后, 我 们 给 每 个 参 与 者 的 策 略 进 行 了 较 为 合 理 的 假 设, 在 这 个 假 设 下, 我 们 发 现 这 个 随 机 过 程 是 时 齐 的 马 尔 科 夫 有 限 链 经 过 简 化 模 型 与 玩 家 策 略 假 设 之 后, 我 们 给 出 了 游 戏 平 衡 性 与 记 分 规 则 合 理 性 的 度 量, 进 一 步, 我 们 利 用 概 率 转 移 算 法, 计 算 出 玩 家 数 是 4 人 时 的 游 戏 平 衡 性 与 记 分 规 则 合 理 性 我 们 发 现, 在 4 个 人 的 时 候, 游 戏 是 极 其 不 平 衡 的, 反 贼 有 很 大 的 概 率 死 亡 对 于 更 多 玩 家 数 的 情 况, 概 率 转 移 模 型 已 经 不 能 胜 任, 于 是 我 们 采 用 了 蒙 特 卡 洛 算 法 进 行 大 量 的 随 机 试 验, 计 算 出 了 5-10 人 时 各 种 身 分 分 配 方 案 下 的 平 衡 性 与 合 理 性, 我 们 发 现, 在 人 数 适 中 的 情 况 下 ( 确 切 地 说 是 6-8 人 ), 游 戏 平 衡 性 最 佳, 记 分 也 非 常 合 理, 随 着 人 数 进 一 步 增 加, 主 公 的 优 势 过 于 明 显, 导 致 平 衡 性 丧 失, 但 是 记 分 规 则 弥 补 了 这 个 问 题, 使 得 各 个 身 份 的 得 分 期 望 相 差 不 多 在 计 算 平 衡 性 与 合 理 性 的 时 候, 我 们 还 利 用 概 率 转 移 的 结 果 验 证 了 由 大 数 定 理 保 证 的 蒙 特 卡 洛 算 法 的 有 效 性 在 本 文 的 开 始 和 最 后, 我 们 都 试 着 讨 论 了 研 究 三 国 杀 游 戏 对 现 实 生 活 的 意 义 关 键 词 三 国 杀, 动 态 博 弈, 概 率 转 移 算 法, 蒙 特 卡 洛 算 法, 游 戏 平 衡 性, 记 分 规 则 合 理 性 1

目 录 1 介 绍 4 1.1 背 景 : 动 态 博 弈 4 1.2 简 介 : 三 国 杀 游 戏 4 1.3 动 机 : 游 戏 趣 味 性 4 1.4 问 题 : 游 戏 平 衡 性 与 记 分 规 则 合 理 性 5 2 简 化 的 三 国 杀 游 戏 5 2.1 不 同 的 联 盟 5 2.2 回 合 5 2.3 死 亡 判 定 6 2.4 胜 利 条 件 6 2.5 玩 家 距 离 6 2.6 游 戏 牌 功 能 7 2.6.1 普 通 牌 7 2.6.2 锦 囊 牌 7 2.6.3 装 备 牌 7 2.7 简 化 模 型 梗 概 7 3 随 机 过 程 模 型 8 4 简 化 模 型 的 进 一 步 假 设 9 4.1 初 始 情 况 假 设 9 4.2 决 策 假 设 9 4.2.1 选 择 对 象 9 4.2.2 执 行 操 作 10 4.3 对 假 设 策 略 的 进 一 步 说 明 11 4.4 初 始 状 态 分 布 11 5 平 衡 性 与 合 理 性 的 度 量 11 6 概 率 转 移 算 法 12 6.1 算 法 框 架 12 6.2 迭 代 中 止 条 件 13 6.3 计 算 结 果 分 析 13 7 概 率 转 移 算 法 的 优 越 性 与 局 限 性 14 2

8 蒙 特 卡 洛 算 法 15 8.1 算 法 框 架 15 8.2 计 算 结 果 分 析 15 9 蒙 特 卡 洛 算 法 的 有 效 性 检 验 17 10 总 结 18 11 讨 论 与 开 放 问 题 18 A 概 率 转 移 算 法 代 码 19 B 蒙 特 卡 洛 算 法 代 码 25 C 原 始 数 据 31 3

1 介 绍 1.1 背 景 : 动 态 博 弈 在 现 实 生 活 中, 无 时 无 刻 不 在 发 生 动 态 博 弈 : 不 同 的 玩 家 和 联 盟 有 不 同 的 应 对 措 施 比 较 熟 悉 的 例 子 如 : 在 商 业 上, 公 司 的 股 东, 员 工, 管 理 者, 竞 争 对 手 在 学 校 里, 教 授, 学 生, 行 政 人 员, 后 勤 人 员 这 样 的 例 子 甚 至 可 以 追 溯 到 古 时 候, 主 公, 忠 臣, 反 贼, 内 奸 这 些 博 弈 都 有 一 个 共 同 的 特 征 : 每 个 身 在 其 中 的 人 都 属 于 一 个 或 多 个 联 盟, 他 们 之 间 有 不 同 的 利 益 关 系 1.2 简 介 : 三 国 杀 游 戏 三 国 杀 是 近 来 在 大 学 生 中 比 较 流 行 的 一 个 休 闲 纸 牌 游 戏, 它 将 杀 人 游 戏 和 三 国 故 事 结 合 起 来, 玩 家 扮 演 刘 备 孙 权 曹 操, 或 者 关 羽 张 飞 赵 云 等 三 国 著 名 人 物, 进 行 一 场 斗 智 斗 勇 的 游 戏 游 戏 开 始, 每 一 位 玩 家 得 到 一 张 随 机 分 发 的 身 份 牌 如 果 你 扮 演 的 是 主 公, 必 须 马 上 亮 出 你 的 身 份 牌 你 的 主 公 身 份 会 招 致 反 贼 的 群 起 而 攻, 但 你 身 边 的 忠 臣 们 会 不 遗 余 力 地 保 护 你, 同 时 也 要 小 心 内 奸 潜 伏 在 你 的 周 围 反 贼 的 任 务 则 是 刺 杀 主 公, 一 旦 主 公 死 亡, 反 贼 就 会 胜 利 忠 臣 的 任 务 则 是 保 护 主 公, 只 要 主 公 成 功 地 活 到 了 最 后, 即 消 灭 了 所 有 的 反 贼 和 内 奸, 正 义 的 一 方 就 会 获 得 胜 利 内 奸 则 希 望 借 正 义 之 手 消 灭 所 有 的 反 贼, 借 反 贼 之 手 消 灭 主 公 身 边 的 忠 臣, 内 奸 的 任 务 最 难 完 成, 他 要 消 灭 除 了 自 己 之 外 的 所 有 人 明 确 了 你 的 游 戏 任 务 之 后, 就 可 以 选 择 角 色, 这 一 步 将 决 定 你 在 三 国 中 扮 演 哪 一 个 历 史 人 物, 每 一 个 人 物 都 有 特 殊 的 技 能 属 性, 这 些 属 性 跟 人 物 的 真 实 性 格 是 相 关 的, 不 同 的 技 能 属 性 可 能 给 你 的 游 戏 带 来 不 同 的 帮 助 1.3 动 机 : 游 戏 趣 味 性 对 于 一 个 游 戏 而 言, 其 趣 味 性 在 于 结 果 的 未 知 性, 在 三 国 杀 游 戏 中, 倘 若 游 戏 设 计 得 不 平 衡, 在 分 配 身 份 和 角 色 之 后, 就 确 定 了 胜 负 和 相 应 的 得 分 谁 多 谁 少, 那 就 会 导 致 整 个 游 戏 的 趣 味 性 丧 失 在 社 会 中 也 有 这 样 的 要 求, 比 如, 在 赌 场 里, 赌 局 不 能 一 边 倒 ; 在 学 校 里, 两 个 老 师 教 同 一 个 课 程, 难 度 和 给 分 不 能 相 差 太 大, 等 等 针 对 一 个 游 戏 而 言, 不 同 身 份 胜 负 的 概 率 不 应 该 相 差 太 悬 殊, 在 这 个 胜 负 概 率 较 为 平 衡 的 基 础 上, 还 要 给 出 一 个 记 分 的 方 法, 也 就 是 奖 惩 的 措 施, 给 赢 面 稍 小 的 相 对 多 奖 励 一 些 这 些 平 衡 与 合 理 的 设 计 在 以 上 社 会 现 象 中 也 同 样 存 在 综 上, 研 究 游 戏 平 衡 性 与 记 分 规 则 合 理 性 不 仅 对 三 国 杀 游 戏 本 身 具 有 意 义, 对 一 些 社 会 现 象 也 具 有 同 样 的 普 遍 意 义 4

1.4 问 题 : 游 戏 平 衡 性 与 记 分 规 则 合 理 性 在 这 篇 论 文 中, 我 们 考 虑 这 样 的 问 题 : 在 三 国 杀 游 戏 中, 不 同 人 数 下, 已 经 有 不 同 身 份 个 数 的 分 配 方 案 ( 例 如 :5 玩 家, 其 中 主 公, 忠 臣, 内 奸 各 1 个, 反 贼 2 个 ), 在 这 些 方 案 下, 游 戏 的 胜 负 平 衡 性 应 如 何 度 量, 在 这 种 度 量 下, 判 断 游 戏 的 平 衡 性 是 否 好 对 已 有 的 记 分 方 案 进 行 评 估, 给 出 记 分 规 则 合 理 性 的 度 量, 并 判 断 记 分 规 则 是 否 合 理 2 简 化 的 三 国 杀 游 戏 由 于 原 有 的 三 国 杀 模 型 过 于 复 杂, 且 许 多 规 则 并 不 影 响 总 体 的 游 戏 平 衡 性 判 定, 所 以 我 们 研 究 以 下 三 国 杀 游 戏 的 简 化 模 型 2.1 不 同 的 联 盟 一 共 有 若 干 个 玩 家, 这 些 人 围 坐 成 一 圈, 按 出 牌 顺 序 方 向 ( 逆 时 针 ) 依 次 标 号 1, 2,..., N, 标 号 为 1 的 玩 家 是 主 公 N 名 玩 家 中 有 p 名 忠 臣, 他 们 的 编 号 是 A 1, A 2,..., A p N 名 玩 家 中 有 q 名 反 贼, 他 们 的 编 号 是 B 1, B 2,..., B q N 名 玩 家 中 有 r 名 内 奸, 他 们 的 编 号 是 C 1, C 2,..., C r 在 游 戏 一 开 始, 会 告 诉 每 个 玩 家 他 们 各 自 的 身 份 每 个 人 的 初 始 体 力 值 和 最 大 体 力 值 均 是 4 注 2.1 与 传 统 的 三 国 杀 游 戏 不 同, 在 简 化 模 型 中 没 有 角 色 这 个 概 念, 也 就 是 说, 没 有 特 殊 技 能 这 个 概 念 而 且 在 考 虑 到 传 统 三 国 杀 游 戏 中 最 大 体 力 值 是 3 的 角 色 都 拥 有 较 强 的 能 力, 所 以 在 简 化 模 型 中 统 一 认 为 最 大 体 力 值 是 4 2.2 回 合 在 简 化 模 型 中, 牌 堆 认 为 是 无 限 的 序 列, 每 种 牌 以 一 定 的 概 率 出 现 在 开 始 游 戏 之 前, 每 名 玩 家 从 牌 堆 摸 取 同 样 张 数 的 游 戏 牌, 作 为 起 始 手 牌 游 戏 是 从 主 公 开 始, 每 人 有 一 个 游 戏 回 合, 逆 时 针 方 向 按 回 合 轮 流 进 行 每 回 合 分 以 下 三 个 阶 段 组 成, 直 到 游 戏 结 束 摸 牌 阶 段 从 牌 堆 摸 两 张 牌 5

出 牌 阶 段 可 以 出 任 意 张 牌, 加 强 自 己 或 攻 击 他 人, 只 需 遵 照 以 下 两 条 限 制 : 每 回 合 仅 限 用 杀 攻 击 一 次 ; 玩 家 摆 在 面 前 的 牌 ( 包 括 自 己 的 装 备 ) 不 能 有 两 张 同 名 的 弃 牌 阶 段 不 想 再 出 牌 或 不 能 再 出 牌 时 就 进 入 弃 牌 阶 段, 此 时 检 查 自 己 的 手 牌 ( 拿 在 手 上 的 牌 ) 数, 是 否 超 过 自 己 当 前 体 力 值, 弃 掉 手 里 多 于 当 前 体 力 值 的 手 牌 记 在 回 合 t 结 束 后, 主 公, 忠 臣, 反 贼, 内 奸 分 别 剩 余 O(t), P (t), Q(t), R(t) 人 注 2.2 简 化 模 型 与 传 统 的 三 国 杀 游 戏 中 存 在 如 下 区 别 : 在 简 化 模 型 中, 牌 堆 认 为 是 无 限 的 序 列, 这 导 致 在 传 统 的 三 国 杀 游 戏 中 摸 牌 阶 段 中 可 能 出 现 的 牌 堆 被 摸 完 的 情 况 在 简 化 模 型 中 不 存 在 注 意, 由 于 在 简 化 模 型 中 不 存 在 角 色 的 概 念 和 延 时 类 锦 囊, 所 以 没 有 传 统 游 戏 中 的 回 合 开 始 阶 段 与 回 合 结 束 阶 段 2.3 死 亡 判 定 任 何 时 候, 如 果 某 角 色 体 力 值 减 少 为 0, 则 角 色 死 亡 死 亡 的 角 色 手 牌 和 该 角 色 面 前 已 装 备 的 装 备 牌 弃 到 弃 牌 堆 角 色 死 亡 的 玩 家 亮 出 身 份 牌, 并 退 出 游 戏 此 后 需 要 计 算 距 离 时, 忽 略 已 死 亡 的 角 色 注 2.3 在 简 化 模 型 中 任 何 人 杀 死 反 贼 可 获 得 摸 三 张 牌 的 奖 励 这 条 规 则 不 存 在 另 外, 传 统 的 三 国 杀 游 戏 中 所 规 定 的 如 果 主 公 误 杀 了 忠 臣, 需 要 弃 掉 所 有 的 手 牌 和 已 装 备 的 牌 在 简 化 模 型 中 不 存 在 2.4 胜 利 条 件 胜 利 条 件 是 由 拿 到 的 身 份 牌 决 定 的 : 主 公 和 忠 臣 的 胜 利 条 件 是 消 灭 所 有 反 贼 和 内 奸, 即 存 在 时 刻 t 使 得 Q(t) = R(t) = 0 反 贼 则 只 需 杀 死 主 公 就 能 获 得 胜 利, 即 存 在 时 刻 t 使 得 O(t) = 0 内 奸 则 只 有 消 灭 除 了 自 己 之 外 的 所 有 人 才 能 取 得 胜 利 ( 包 括 别 的 内 奸 ), 即 存 在 时 刻 t 使 得 O(t) = P (t) = Q(t) = 0 且 R(t) = 1 如 果 角 色 死 亡 导 致 任 意 一 方 的 胜 利 条 件 达 成, 则 游 戏 立 即 结 束, 也 就 是 说, 在 使 得 上 面 三 个 等 式 成 立 的 最 小 的 时 刻 t 游 戏 结 束 2.5 玩 家 距 离 无 论 顺 时 针 还 是 逆 时 针, 取 最 短 路 径, 即 为 两 名 玩 家 间 的 距 离 值 对 于 一 个 局 面 S( 其 中 包 括 了 所 有 人 的 信 息 ), 记 d(s, i, j) 表 示 在 这 个 局 面 下 玩 家 i 和 玩 家 j 的 距 离 注 2.4 装 备 马 在 简 化 模 型 中 不 存 在 装 备 马 可 以 改 变 玩 家 间 的 距 离 这 种 说 法, 因 为 根 本 没 有 6

2.6 游 戏 牌 功 能 游 戏 牌 包 括 杀 闪 桃, 及 锦 囊 牌 和 装 备 牌 除 装 备 牌 外, 游 戏 牌 使 用 后 均 需 弃 掉 2.6.1 普 通 牌 杀 出 牌 阶 段 使 用, 攻 击 一 名 在 攻 击 距 离 内 ( 除 自 己 外 ) 的 玩 家, 若 攻 击 成 功, 被 攻 击 的 玩 家 减 1 点 体 力 未 装 备 武 器 时, 玩 家 杀 的 攻 击 距 离 为 1 装 备 武 器 后, 杀 的 攻 击 距 离 为 武 器 的 攻 击 距 离 出 现 杀 的 概 率 是 30/71 闪 在 别 的 玩 家 对 你 出 杀 可 以 打 出 闪, 闪 避 一 次 杀 的 攻 击 牌 堆 出 现 闪 的 概 率 是 15/71 桃 出 牌 阶 段 使 用, 为 自 己 加 一 点 体 力 任 何 时 候 体 力 值 不 得 超 过 体 力 上 限 桃 也 可 以 在 任 何 时 候 需 要 扣 减 最 后 一 点 体 力 时, 对 自 己 使 用, 抵 消 一 点 体 力 伤 害 牌 堆 出 现 桃 的 概 率 是 8/71 注 2.5 简 化 模 型 中 削 弱 了 桃 的 作 用, 即 不 能 在 其 他 玩 家 扣 减 最 后 一 点 体 力 的 时 候 使 用 2.6.2 锦 囊 牌 过 河 拆 桥 出 牌 阶 段 对 除 自 己 外 任 意 一 名 玩 家 使 用, 随 机 抽 对 方 一 张 手 牌, 或 选 择 一 张 已 装 备 的 装 备 牌, 并 将 之 弃 掉 牌 堆 出 现 过 河 拆 桥 的 概 率 是 6/71 顺 手 牵 羊 出 牌 阶 段 对 距 离 为 1 的 一 名 玩 家 使 用, 随 机 抽 对 方 一 张 手 牌, 或 选 择 一 张 已 装 备 的 装 备 牌, 将 之 收 入 自 己 的 手 牌, 顺 手 牵 羊 的 距 离 与 武 器 无 关 牌 堆 出 现 顺 手 牵 羊 的 概 率 是 5/71 注 2.6 简 化 模 型 中 忽 略 传 统 三 国 杀 中 所 有 总 数 量 小 于 5 的 牌 2.6.3 装 备 牌 简 化 模 型 中 只 有 一 种 装 备 牌 武 器 攻 击 距 离 是 3 牌 堆 出 现 武 器 的 概 率 是 7/71 注 2.7 简 化 模 型 除 了 忽 略 了 所 有 马, 防 具 和 诸 葛 连 弩 外, 并 将 剩 下 的 7 个 武 器 的 攻 击 距 离 加 权 平 均 计 算 得 到 平 均 攻 击 距 离 约 为 3 2.7 简 化 模 型 梗 概 相 对 于 传 统 的 三 国 杀 游 戏, 简 化 模 型 有 如 下 特 性 1. 牌 堆 是 无 限 的, 且 每 种 牌 以 给 定 概 率 出 现 7

2. 没 有 角 色 牌, 所 有 玩 家 都 除 身 份 外 处 于 相 同 水 平, 没 有 特 殊 技 能 以 及 一 切 与 角 色 有 关 的 概 念 3. 锦 囊 牌 仅 保 留 两 类, 即 过 河 拆 桥 和 顺 手 牵 羊 4. 桃 不 能 用 于 对 其 他 玩 家 的 急 救 5. 当 主 公 误 杀 忠 臣 或 者 任 何 人 杀 死 反 贼 时, 没 有 奖 励 和 惩 罚 措 施 3 随 机 过 程 模 型 简 化 模 型 中 的 牌 堆 可 以 认 为 是 一 串 独 立 同 分 布 的 随 即 变 量 X(i) 每 个 随 机 变 量 的 分 布 是 根 据 简 化 模 型 中 每 类 牌 出 现 的 概 率 决 定 的 这 些 随 机 变 量 的 取 值 集 合 Card 就 是 所 有 牌 的 种 类 简 化 模 型 的 每 个 状 态 可 通 过 一 个 随 机 过 程 S(t) 描 述 其 中 S(t) 是 一 个 随 机 向 量, 表 示 t 时 刻 的 状 态, 其 分 量 包 括 该 时 刻 应 该 摸 牌 的 玩 家 的 编 号 N(t) 每 个 玩 家 剩 余 的 体 力 值, 记 H(t, i) 表 示 此 时 第 i 个 玩 家 的 剩 余 体 力 值 每 个 玩 家 手 中 剩 余 4 张 牌 ( 可 能 少 于 4 张 牌 ) 的 情 况, 记 四 维 向 量 V (t, i) 表 示 此 时 第 i 个 玩 家 的 剩 余 体 力 值 每 个 玩 家 是 否 装 备 了 装 备 牌, 记 W (t, i) 表 示 此 时 第 i 个 玩 家 的 是 否 装 备 武 器,0 为 未 装 备,1 为 装 备 容 易 发 现 由 简 化 模 型 的 性 质, t 时 刻, 标 号 是 N(t) 人 从 牌 堆 拿 的 牌 恰 好 是 X(2t 1), X(2t) 我 们 称 S 的 取 值 集 合 State 的 元 素 为 局 面, 包 含 摸 牌 玩 家 编 号, 每 个 玩 家 剩 余 体 力 值 等 等 信 息 ) 对 于 这 个 随 机 过 程, 如 果 每 个 玩 家 的 策 略 ( 非 混 合 策 略 ) 给 定 且 策 略 是 仅 根 据 当 前 状 态 决 定 的, 在 这 种 情 况 下, 编 号 为 i 的 人 的 策 略 会 诱 导 一 个 从 State Card 2 到 State 的 映 射 p(i), 表 示 在 面 对 一 个 局 面 的 时 候, 当 玩 家 i 按 照 他 的 策 略 采 取 行 动, 等 回 合 结 束 的 局 面 而 对 于 混 合 策 略 的 情 况, 编 号 为 i 的 人 的 策 略 也 会 诱 导 一 个 从 State 上 的 分 布 与 Card 上 的 分 布 的 平 方 的 笛 卡 尔 积 到 State 上 的 分 布 的 映 射 p(i)( ), 这 个 映 射 可 以 如 下 决 定 整 个 随 机 过 程 : S(t + 1) = p(n(t))(s(t), X(2t 1), X(2t)) (3.1) 注 意, 初 始 条 件 S(1) 中 分 量 满 足 :P (N(1) = 1) = 1, P (H(t, i) = 4) = 1, 且 8

P (V (1, i) = (C 1, C 2, C 3, C 4 )) = P (C = C 1 )P (C = C 2 )P (C = C 3 )P (C = C 4 ) (3.2) 在 每 个 玩 家 的 策 略 给 定 且 策 略 是 仅 根 据 当 前 状 态 决 定 的 的 假 定 下, 注 意 到 X(t) 是 独 立 同 分 布 的, 可 知 这 个 随 机 过 程 是 一 个 马 尔 科 夫 链 如 果 再 假 定 策 略 与 时 间 t 无 关, 则 这 个 马 尔 科 夫 链 是 时 齐 的 在 后 面 的 文 章 中 我 们 都 作 这 样 的 假 定, 即 每 个 玩 家 的 策 略 给 定 的, 策 略 是 仅 根 据 当 前 状 态 决 定 的 且 与 时 间 无 关 由 于 可 能 的 状 态 数 是 有 限 的 ( 因 为 玩 家 数 量 是 有 限 的, 最 大 血 量 是 有 限 的, 手 牌 可 能 的 情 况 也 是 有 限 的 ) 所 以 这 个 马 尔 科 夫 链 是 有 限 链, 从 而 还 有 对 应 的 概 率 转 移 矩 阵 基 于 以 上 随 机 过 程 模 型, 我 们 计 算 在 不 同 假 设 下, 即 对 于 不 同 的 p(i) 的 概 率 转 移 矩 阵, 从 而 确 定 整 个 随 机 过 程, 以 及 随 机 过 程 中 的 一 些 统 计 量 注 3.1 这 样 假 设 的 合 理 性 在 于 对 于 三 国 杀 中 的 大 多 数 玩 家, 他 们 不 会 注 意 之 前 的 情 况, 而 只 注 重 当 前 的 状 态 4 简 化 模 型 的 进 一 步 假 设 在 本 节 中, 我 们 首 先 对 扮 演 不 同 身 份 玩 家 的 决 策 作 出 一 个 较 为 合 理 的 假 设 4.1 初 始 情 况 假 设 为 了 进 一 步 简 化, 我 们 假 设 在 开 始 阶 段, 每 个 人 手 上 都 有 两 张 闪, 没 有 其 他 牌 ( 包 括 锦 囊, 装 备 ) 4.2 决 策 假 设 为 了 分 析 记 分 规 则 的 合 理 性, 我 们 需 要 对 每 个 玩 家 的 策 略 作 出 一 定 的 假 设 每 个 玩 家 在 他 的 回 合 摸 好 两 张 牌 之 后, 分 两 个 步 骤 作 出 决 策 : 选 择 对 象, 执 行 操 作 4.2.1 选 择 对 象 下 面 是 不 同 身 份 对 应 的 不 同 对 象 选 择 策 略 : 反 贼 如 果 所 有 忠 臣 都 死 了, 在 最 后 一 个 忠 臣 死 的 时 候, 所 有 反 贼 同 时 表 明 自 己 的 身 份 俗 称 跳 反, 也 就 是 说, 所 有 人 都 知 道 反 贼 的 身 份 当 且 仅 当 忠 臣 的 人 数 为 0, 即 P (t) = 0 在 忠 臣 没 有 全 部 死 亡 的 情 况 下, 反 贼 随 机 从 能 攻 击 到 的 活 着 的 对 象 中 ( 除 了 主 公 ) 等 概 率 地 随 机 选 择 对 象 否 则, 反 贼 始 终 攻 击 主 公, 如 果 主 公 不 在 攻 击 范 围 内, 则 等 概 率 地 选 择 攻 击 范 围 内 的 活 着 的 内 奸 9

主 公 在 反 贼 没 有 标 明 身 份 的 情 况 下, 随 机 从 能 攻 击 到 的 所 有 对 象 中 等 概 率 地 选 择 一 个 对 象 否 则, 随 机 从 能 攻 击 到 的 反 贼 中 等 概 率 地 选 择 一 个 对 象 忠 臣 忠 臣 始 终 随 机 从 能 攻 击 到 的 活 着 的 对 象 中 ( 显 然, 除 了 主 公 ) 等 概 率 地 随 机 选 择, 通 过 反 贼 的 策 略 可 知, 不 存 在 忠 臣 得 知 反 贼 身 份 的 情 况 内 奸 始 终 随 机 从 能 攻 击 到 的 活 着 的 对 象 中 ( 除 了 主 公 ) 选 择 体 力 值 最 大 的, 如 果 有 体 力 值 相 等 的, 则 等 概 率 选 择 其 中 一 个 如 果 只 有 主 公 存 活, 则 攻 击 主 公 注 4.1 所 谓 对 象 就 是 接 下 来 执 行 操 作 的 时 候 需 要 攻 击 的 对 象, 通 过 不 同 联 盟 之 间 的 利 益 关 系, 以 上 对 象 的 选 择 是 有 一 定 合 理 性 的 注 意, 在 简 化 模 型 中, 装 备 牌 只 有 攻 击 距 离 为 3 的 武 器, 没 有 马 的 装 备, 所 以 不 存 在 无 法 选 择 对 象 的 情 况, 除 了 一 种 情 况, 就 是 反 贼 在 表 明 身 份 之 后, 攻 击 范 围 内 的 所 有 人 都 是 反 贼 4.2.2 执 行 操 作 在 确 定 了 对 象, 或 者 以 一 个 概 率 分 布 确 定 了 一 个 对 象 之 后, 考 虑 该 时 刻 玩 家 在 拿 上 两 张 牌 之 后 对 这 个 对 象 执 行 的 操 作 在 出 牌 阶 段, 玩 家 首 先 将 手 上 的 所 有 装 备 牌 装 备 到 身 上, 由 于 装 备 只 有 武 器, 并 且 互 相 之 间 没 有 任 何 区 别, 所 以 如 果 已 经 有 武 器, 则 直 接 弃 掉 装 备 牌 此 时, 手 上 只 剩 余 杀, 闪, 桃, 过 河 拆 桥 与 顺 手 牵 羊 这 些 按 照 下 面 的 策 略 对 已 经 选 择 的 对 象 执 行 注 意, 以 下 的 策 略 是 按 顺 序 执 行 的 顺 手 牵 羊 如 果 已 选 择 的 对 象 有 装 备, 则 对 装 备 使 用 顺 手 牵 羊, 否 则, 等 概 率 地 选 择 对 相 的 一 张 手 牌 ( 如 果 有 的 话 ), 将 其 顺 手 牵 羊 过 河 拆 桥 如 果 已 选 择 的 对 象 有 装 备, 则 对 装 备 使 用 过 河 拆 桥, 否 则, 等 概 率 地 选 择 对 相 的 一 张 手 牌 ( 如 果 有 的 话 ), 将 其 过 河 拆 桥 杀 对 已 选 择 的 对 象 使 用 闪 不 操 作 桃 如 果 自 己 的 体 力 值 没 有 达 到 最 大 值, 则 对 自 己 使 用 被 攻 击 的 玩 家 出 闪, 如 果 都 没 有, 就 扣 血 弃 牌 阶 段, 玩 家 弃 掉 所 有 手 头 的 杀, 桃, 过 河 拆 桥, 顺 手 牵 羊, 仅 保 留 闪 注 4.2 根 据 弃 牌 规 则, 玩 家 没 有 可 能 出 桃 来 抵 消 伤 害 根 据 被 攻 击 的 玩 家 必 定 出 闪 可 知, 不 存 在 血 比 闪 的 数 量 少 的 情 况 10

4.3 对 假 设 策 略 的 进 一 步 说 明 通 过 不 同 身 份 的 目 的, 我 们 逐 一 说 明 各 个 身 份 的 策 略 假 设 是 具 有 合 理 性 的 主 公 由 于 主 公 在 开 始 时 期 不 知 道 剩 下 人 的 身 份, 所 以 就 随 机 攻 击, 当 反 贼 暴 露 身 份 之 后, 很 自 然, 主 公 应 该 针 对 反 贼 进 行 攻 击 忠 臣 忠 臣 的 策 略 就 是 不 攻 击 主 公, 由 于 不 知 道 其 他 人 的 身 份, 所 以 只 能 随 机 攻 击, 如 果 有 反 贼 暴 露, 则 应 该 攻 击 反 贼 反 贼 反 贼 在 忠 臣 灭 亡 的 情 况 下, 应 开 始 攻 击 主 公, 尽 快 结 束 战 斗 内 奸 内 奸 需 要 消 灭 所 有 其 他 人, 所 以 它 需 要 不 断 削 弱 周 围 的 人, 但 是 在 开 始 的 时 候 他 不 能 攻 击 主 公, 直 到 只 剩 下 他 和 主 攻 我 们 所 假 定 的 策 略 都 是 根 据 以 上 的 几 条 制 定 的, 所 以 具 有 一 定 的 合 理 性 4.4 初 始 状 态 分 布 由 假 定 的 策 略 确 定 了 一 个 齐 时 的 马 尔 科 夫 有 限 链, 由 此 可 以 通 过 状 态 与 转 移 概 率 矩 阵 的 不 断 迭 代, 得 到 各 种 中 止 状 态 的 概 率 还 是 通 过 随 机 向 量 S(t) = (N(t), H(t), V (t), W (t)) 记 录 每 个 状 态 在 t 时 刻 的 分 布 注 意, 由 于 手 上 所 留 下 的 牌 只 可 能 是 闪, 这 里 V 是 一 个 有 n 各 分 量 的 向 量, 这 里 n 是 人 数 由 前 面 的 假 定, 初 始 状 态 S(1) 的 分 布 是 满 足 P (S(1) = (1, (4, 4,..., 4), (2, 2,..., 2), (0, 0,..., 0))) = 1 (4.1) 注 4.3 结 合 初 始 情 况 和 对 玩 家 策 略 的 假 定, 我 们 可 以 知 道 在 使 用 顺 手 牵 羊 或 者 过 河 拆 桥 的 时 候, 如 果 要 对 对 象 的 手 牌 进 行 随 机 选 择, 则 选 择 的 结 果 一 定 是 闪 5 平 衡 性 与 合 理 性 的 度 量 平 衡 性 体 现 在 胜 负 结 果 之 间 差 别 的 大 小, 我 们 通 过 差 方 来 度 量 平 衡 性 Bal, 定 义 如 下 Bal = (P 0 P ) 2 + (P 1 P ) 2 + (P 2 P ) 2 + (P 3 P ) 2 (5.1) 其 中,P 0, P 1, P 2, P 3 表 示 主 公, 每 个 忠 臣, 每 个 反 贼, 每 个 内 奸 最 终 存 活 的 概 率, P 是 这 四 个 值 的 平 均 注 5.1 对 于 一 个 纸 牌 游 戏, 大 家 主 要 的 目 的 就 是 娱 乐, 而 每 个 人 无 论 胜 负, 都 希 望 自 己 能 活 到 最 后 一 刻, 否 则 提 前 死 亡, 就 只 能 看 着 别 人 进 行 游 戏 所 以 这 里 采 用 每 个 身 份 最 终 存 活 得 概 率 来 度 量 游 戏 的 平 衡 性 11

合 理 性 体 现 在 得 分 期 望 之 间 的 差 别 大 小, 同 样 通 过 差 方 来 度 量 合 理 性 Rat, 定 义 如 下 Rat = (E 0 Ē)2 + (E 1 Ē)2 + (E 2 Ē)2 + (E 3 Ē)2 (5.2) 其 中,E 0, E 1, E 2, E 3 表 示 主 公, 忠 臣, 反 贼, 内 奸 的 得 分 期 望,Ē 表 示 四 个 得 分 期 望 的 平 均 值 注 5.2 对 于 记 分, 需 要 要 求 每 个 身 份 的 得 分 期 望 不 要 相 差 太 大, 所 以 我 们 采 用 这 样 公 式 来 度 量 记 分 合 理 性 6 概 率 转 移 算 法 下 面 介 绍 迭 代 算 法 的 细 节 6.1 算 法 框 架 对 于 分 布 S(t), 我 们 可 以 通 过 以 上 的 策 略 完 全 确 定 S(t + 1), 下 面 用 一 个 例 子 来 说 明 例 6.1 对 于 一 个 四 个 人 的 游 戏, 其 中 编 号 为 1, 2, 3, 4 的 分 别 是 主 公, 内 奸, 忠 臣, 反 贼 如 图 1 所 是 这 是 一 个 状 态 S(t) 中 的 一 个 局 面, 假 设 其 出 现 的 概 率 是 1/2 主 公 1(2,4,0) 反 贼 4(0,0,1) 内 奸 2(3,1,0) 忠 臣 3(2,2,0) 图 1: 状 态 1 其 中 主 公, 内 奸, 忠 臣, 反 贼 的 剩 余 体 力 值 分 别 是 2, 3, 2, 0, 他 们 手 中 闪 的 数 量 分 别 是 4, 1, 2, 0, 该 时 刻 轮 到 内 奸 假 设 内 奸 先 后 摸 到 一 张 杀 和 一 张 桃, 这 种 情 况 出 现 的 概 率 是 30 71 8 71 根 据 之 前 的 策 略, 内 奸 首 先 对 自 己 使 用 桃, 随 后 以 1 的 概 率 攻 击 忠 臣, 此 时 忠 臣 出 闪 于 是 先 后 摸 到 一 张 杀 和 一 张 桃 的 条 件 下, 对 下 一 时 刻 的 局 面 ( 如 图 2 所 示 ) 有 1 2 30 71 8 71 的 概 率 的 贡 献 对 所 有 t 时 刻 的 可 能 的 局 面 和 两 张 牌 不 同 的 情 况 进 行 这 样 的 计 算 就 可 以 得 到 t + 1 时 刻 的 状 态 ( 也 就 是 局 面 的 概 率 分 布 ) 12

主 公 1(2,4,0) 反 贼 4(0,0,1) 内 奸 2(4,1,0) 忠 臣 3(2,1,0) 图 2: 状 态 2 6.2 迭 代 中 止 条 件 在 时 刻 t 的 时 候, 当 所 有 非 中 止 状 态 ( 非 中 止 状 态 就 是 尚 未 有 某 一 方 已 经 获 胜 ) 的 概 率 都 小 于 一 个 固 定 的 常 数 的 时 候, 我 们 就 停 止 迭 代 这 里 我 们 取 这 个 常 数 是 1/(2 31 1), 其 实 为 了 实 现 的 方 便, 以 上 算 法 都 是 将 所 有 概 率 乘 以 一 个 常 数 2 31 1 之 后 进 行 迭 代 计 算 的 6.3 计 算 结 果 分 析 根 据 以 上 算 法, 我 们 设 计 了 迭 代 的 程 序, 代 码 见 附 录 A 当 玩 家 总 数 n = 4 的 时 候, 最 终 结 果 如 表 1 所 示, 此 时 除 中 止 局 面 外, 其 他 局 面 的 概 率 都 是 一 个 较 小 的 量 表 1 中 第 一 行 的 0 代 表 主 公,1 代 表 忠 臣,2 代 表 反 贼,3 代 表 内 奸 从 而 0123 代 表 逆 时 针 分 别 坐 主 公, 忠 臣, 反 贼, 内 奸, 其 他 以 此 类 推 第 一 列 中 0 代 表 死 亡,1 代 表 存 活, 从 左 向 右 依 次 是 主 公, 忠 臣, 反 贼, 内 奸 的 生 死 状 态 例 如 0001 表 示 主 攻 死 亡, 忠 臣 死 亡, 反 贼 死 亡, 内 奸 存 活 0123 0132 0213 0231 0312 0123 平 均 迭 代 步 骤 348 283 349 282 337 331 322 1 0 0 0 3.30% 45.75% 4.50% 29.16% 11.41% 6.00% 16.69% 1 1 0 0 26.74% 37.17% 5.67% 62.29% 6.52% 60.05% 33.07% 0 0 1 0 0.18% 9.21% 0.51% 3.28% 3.14% 0.21% 2.75% 0 0 0 1 69.78% 7.87% 89.32% 5.27% 78.91% 33.73% 47.48% 0 0 1 1 0.00% 0.00% 0.01% 0.00% 0.02% 0.00% 0.00% 表 1: 不 同 初 始 座 位 的 终 结 状 态 概 率 及 其 平 均 传 统 三 国 杀 游 戏 中 的 计 分 规 则 如 下 : 主 公 获 胜 主 公 得 10 分, 每 存 活 一 个 忠 臣 加 5 分 ; 忠 臣 存 活 得 10 分, 死 亡 得 7 分 ; 反 贼 得 0 分 ; 13

内 奸 得 0 分, 除 非 忠 臣 已 死, 内 奸 可 以 得 15 分 反 贼 获 胜 主 公, 忠 臣 得 0 分 ; 反 贼 存 活 得 12 分, 死 亡 得 9 分 ; 内 奸 存 活 得 5 分 减 去 存 活 反 贼 数, 否 则 内 奸 可 以 得 0 分 内 奸 获 胜 主 公 得 3 分, 内 奸 得 35 分, 其 他 人 不 得 分 通 过 这 些 最 终 状 态 的 概 率 分 布, 可 以 计 算 出 各 个 身 份 的 存 活 概 率, 如 表 2 所 示 身 份 主 公 忠 臣 反 贼 内 奸 存 活 概 率 49.76% 33.07% 2.76% 47.49% 表 2: 不 同 身 份 的 存 活 概 率 通 过 表 1 的 数 据, 还 可 以 计 算 出 每 种 初 始 座 位 下, 不 同 身 份 的 得 分 期 望, 如 表 3 所 示 身 份 0123 0132 0213 0231 0312 0123 平 均 主 公 6.43 10.39 3.98 12.42 4.49 10.62 8.05 忠 臣 2.90 6.92 0.88 8.27 1.45 6.43 4.48 反 贼 0.02 1.10 0.06 0.39 0.38 0.03 0.33 内 奸 24.92 9.62 31.94 6.22 29.33 12.71 19.12 表 3: 不 同 初 始 座 位 的 不 同 身 份 的 得 分 期 望 与 平 均 此 时, 平 衡 性 Bal = 14.05%, 合 理 性 Rat = 194.93 通 过 以 上 分 析, 在 4 个 人 的 游 戏 中, 通 过 概 率 转 移 算 法, 我 们 精 确 求 出 了 各 个 角 色 的 期 望, 结 果 表 明 游 戏 记 分 的 平 衡 性 在 4 个 人 的 时 候 是 非 常 不 好 的, 对 内 奸 非 常 有 利, 但 是 对 反 贼 非 常 不 利, 这 不 利 于 游 戏 的 趣 味 性 7 概 率 转 移 算 法 的 优 越 性 与 局 限 性 首 先, 我 们 计 算 状 态 的 总 个 数, 注 意 到, 一 个 状 态 就 是 一 个 局 面, 由 当 前 出 牌 的 人, 每 个 人 的 剩 余 血 量, 每 个 人 手 中 牌 的 数 量, 是 否 装 备 武 器 组 成 再 结 合 前 面 的 一 系 列 假 定, 还 可 以 知 道 每 个 人 手 中 牌 的 数 量 就 是 这 个 人 手 中 闪 的 数 量 定 理 7.1 对 于 一 个 玩 家 数 量 为 n 时, 可 能 到 达 的 状 态 不 超 过 n 30 n 种 证 明 当 前 出 牌 的 人 可 能 性 最 多 是 n, 对 于 血 量 为 h 的 人, 根 据 注 4.2 他 手 中 的 牌 ( 显 然 只 有 闪 ) 的 数 量 可 能 是 0, 1,..., h 中 的 一 种, 于 是 血 量 与 手 中 牌 的 可 能 性 总 数 是 1+2+3+4+5 = 15 种, 最 后, 是 否 有 装 备 的 可 能 性 是 2 种 由 乘 法 原 理 知, 可 以 达 到 的 状 态 不 超 过 n 30 n 种 14

对 于 通 常 使 用 的 通 过 矩 阵 乘 法 迭 代 来 计 算 马 尔 科 夫 过 程, 注 意 到, 此 时, 矩 阵 的 规 模 是 状 态 数 的 平 方, 而 由 定 理 7.1 的 结 论 可 以 知 道, 矩 阵 的 规 模 将 非 常 大, 从 而 会 带 来 极 高 的 时 间 复 杂 度 而 之 前 提 到 的 概 率 转 移 算 法, 其 优 越 性 在 于 充 分 利 用 了 概 率 模 型 中 转 移 概 率 矩 阵 的 稀 疏 性, 从 原 本 的 矩 阵 乘 法 来 进 行 迭 代 的 算 法, 转 变 为 一 个 以 概 率 来 模 拟 过 程 从 而 实 现 迭 代 的 算 法, 极 大 提 高 了 运 算 效 率 虽 然 概 率 转 移 算 法 能 够 精 确 地 计 算 出 达 到 中 止 状 态 的 概 率, 但 是 根 据 定 理 7.1 的 结 论, 对 于 5 个 玩 家 的 情 况, 需 要 存 储 5 30 5 个 状 态, 数 量 级 是 10 8, 一 般 计 算 机 内 存 无 法 承 受, 另 一 方 面, 计 算 时 间 和 状 态 数 也 成 正 比, 且 有 一 个 较 大 的 系 数, 容 易 看 出 在 玩 家 数 大 于 6 的 时 候, 时 间 复 杂 度 早 已 无 法 承 受, 基 于 以 上 原 因, 我 们 需 要 研 究 新 的 算 法, 使 之 对 较 大 的 n 同 样 能 得 到 比 较 好 的 结 果 8 蒙 特 卡 洛 算 法 对 于 一 般 的 n 个 玩 家, 我 们 考 虑 采 取 蒙 特 卡 洛 算 法, 即 进 行 大 量 随 机 试 验, 导 出 中 止 状 态 的 概 率 分 布 8.1 算 法 框 架 蒙 特 卡 洛 算 法 的 框 架 较 为 简 单, 在 游 戏 开 始 前, 随 机 将 n 个 玩 家 的 位 置 排 好, 每 个 人 发 放 2 张 闪, 从 主 攻 开 始 摸 牌, 摸 得 两 张 牌 也 随 机 生 成, 每 种 牌 的 出 现 概 率 由 之 前 的 假 定 确 定, 并 根 据 之 前 假 设 的 策 略 去 模 拟 接 下 来 的 每 一 步, 直 到 达 到 一 个 中 止 状 态 根 据 大 数 定 理, 理 论 上, 大 量 随 机 试 验 的 到 的 中 止 状 态 的 概 率 分 布 会 收 敛 到 由 马 尔 科 夫 链 计 算 出 的 中 止 状 态 概 率 分 布, 从 而 蒙 特 卡 洛 算 法 在 理 论 上 是 有 效 的 8.2 计 算 结 果 分 析 根 据 以 上 算 法, 我 们 设 计 了 随 机 模 拟 的 程 序, 代 码 见 附 录 B 对 于 不 同 的 游 戏 人 数 和 身 份 分 配 方 案, 我 们 进 行 10 6 次 试 验, 对 不 同 的 中 止 状 态 进 行 计 数 由 此 可 以 计 算 出 每 个 身 份 的 存 活 概 率, 得 分 期 望 具 体 数 据 见 附 录 C 中 的 表 格 通 过 各 个 身 份 存 活 概 率 和 得 分 期 望, 我 们 可 以 计 算 出 不 同 身 份 分 配 方 案 下 的 游 戏 平 衡 性 和 合 理 性, 如 表 4 所 示 游 戏 人 数 主 公 忠 臣 反 贼 内 奸 Bal Rat 4 1 1 1 1 13.35% 173.77 5 1 1 2 1 4.66% 84.28 6 1 1 3 1 3.78% 25.84 6 1 1 2 2 2.42% 36.90 15

图 3: 平衡性与合理性 图 4: 存活概率 7 1 2 3 1 6.48% 26.09 8 1 2 4 1 4.58% 9.74 8 1 2 3 2 4.16% 22.16 9 1 3 4 1 10.75% 25.03 10 1 3 4 2 7.82% 18.58 表 4: 不同身份分配方案的平衡性与合理性 如图3所示 我们可以看出平衡性和合理性随身份分配方案的变化而变化 通过附录C的数据 我们可以跟踪不同角色的存活概率 如图4所示 同样 我们可以跟踪不同角色的得分期望 如图5所示 根据这些数据 我们进行如下分析 16

图 5: 得分期望 1. 在玩家数是 6 个 分配方案是 1 主公 1 忠臣 2 反贼 2 内奸的时候 游戏的平衡性最好 此时各个身份获胜的概率相差最小 游戏可玩性最强 2. 在人数较少的情况下 玩家数是 4 个的游戏最不公平 反贼有很高的概率输掉比赛 于 是游戏便在剩下三个人之间进行 3. 人数较多的情况下 玩家数是 9 个 分配方案是 1 主公 3 忠臣 4 反贼 1 内奸的时候 游 戏平衡性不佳 主公此时优势过于明显 对于玩家数是 10 个人的身份分配方案 也有同 样的问题存在 4. 虽然对于较多的人数游戏的平衡性不佳 但是考虑到记分 我们可以发现 即使在主公 占有明显又是的情况下 但是各个身份的得分期望仍然相差不多 5. 主公的存活概率随人数的增加而增加 内奸的存活概率始终高于忠臣和反贼 6. 随着人数的增加 各个身份的得分期望越来越趋近 9 蒙特卡洛算法的有效性检验 之前的两个算法 即转移概率算法与蒙特卡洛算法 都能够给出玩家数是 4 时的结果 在 此我们进行比较 对应数据如表5所示 算法名称 主公 忠臣 反贼 内奸 Bal Rat 概率转移 49.76%, 8.05 33.07%, 4.48 2.76%, 0.33 47.49%, 19.12 14.05% 194.93 蒙特卡洛 47.89%, 7.87 32.54%, 4.33 3.51%, 0.42 48.60%, 18.16 13.35% 173.77 表 5: 算法比较 17

其 中, 每 个 身 份 下 的 两 个 数 字 分 别 是 存 活 概 率 和 得 分 期 望 可 以 看 出 两 个 算 法 得 到 的 结 果 相 近, 这 在 实 际 上 再 次 验 证 了 蒙 特 卡 洛 算 法 的 有 效 性, 即 其 准 确 程 度 和 概 率 转 移 算 法 相 近 10 总 结 通 过 以 上 分 析 比 较 我 们 可 以 得 到 如 下 结 论 : 1. 主 公 存 活 概 率 在 6 个 玩 家, 在 1 忠 臣 2 反 贼 2 内 奸 的 情 况 下, 此 时, 整 个 游 戏 也 最 具 平 衡 性, 娱 乐 性 较 强 2. 忠 臣 在 存 活 概 率 比 较 平 稳, 随 人 数 增 加 有 缓 慢 的 降 低 3. 反 贼 在 人 数 多 的 情 况 下, 存 活 概 率 与 忠 臣 趋 于 一 致, 在 6 玩 家 1 主 公 1 忠 臣 3 反 贼 1 内 奸 的 情 况 下 存 活 概 率 最 高 4. 内 奸 在 人 数 多 的 情 况 下 存 活 的 概 率 越 来 越 小, 在 7 人 以 下 的 情 况 下, 还 是 具 有 一 定 优 势 的 5. 在 人 中 等 情 况 下 ( 即 6 8 人 ), 平 衡 性 较 好, 记 分 规 则 也 比 较 合 理, 游 戏 的 有 趣 性 和 可 玩 性 非 常 高 6. 在 人 数 较 少 的 情 况 下, 特 别 是 4 个 人 的 时 候, 反 贼 劣 势 太 明 显, 有 戏 可 玩 性 较 低 7. 在 人 数 较 多 的 情 况 下, 虽 然 主 攻 的 优 势 过 于 明 显, 但 是 记 分 规 则 有 效 弥 补 了 这 个 问 题, 游 戏 有 趣 性 中 等 11 讨 论 与 开 放 问 题 现 实 生 活 中 的 很 多 问 题 都 与 三 国 杀 的 更 一 般 的 情 况 有 一 个 对 应, 游 戏 的 平 衡 性 对 应 于 现 实 生 活 中 的 一 个 活 动 ( 或 者 是 比 赛 ) 能 否 吸 引 他 人 来 参 加, 而 游 戏 记 分 规 则 的 合 理 性 对 应 于 这 个 活 动 是 否 对 参 赛 者 公 平 在 三 国 杀 中, 胜 负 条 件 决 定 了 各 方 的 策 略, 而 这 里 的 胜 负 条 件 是 较 为 简 单 的, 研 究 更 加 复 杂 的 胜 负 条 件, 对 现 实 生 活 的 复 杂 情 况 更 有 意 义 对 于 这 种 复 杂 情 况, 通 过 以 上 的 算 法 去 计 算 几 乎 是 不 可 能 的, 对 于 一 些 特 殊 的 复 杂 的 情 况, 是 否 存 在 一 个 简 单 的 游 戏 平 衡 性 与 记 分 合 理 性 的 度 量, 使 得 计 算 这 些 量 非 常 的 简 单 高 效, 这 个 问 题 有 待 日 后 进 一 步 解 决 18

A 概 率 转 移 算 法 代 码 源 代 码 如 下, 采 用 GCC 4.0 编 译 #include <stdio.h> #include <stdlib.h> #define n (4) #define fn (15*15*15*15) #define tn (2*2*2*2) #define in (12+12*15+12*15*15+12*15*15*15) #define mint (2147483647) int s[n][fn][tn], t[n][fn][tn]; int multiply(int a, int b, int c) if (mint / b > a) return (a * b) / c; else return (a / c) * b; int min(int a, int b) return a < b? a : b; int main() const int ch[16] = 0, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4; const int cv[16] = 0, 0, 1, 0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4; const int cpc[6] = 15, 8, 7, 5, 6, 30; int flag, i, j, k, l, m, o, M, N, nob, dp, ti, tj, tk, step; int id[n], H[n], V[n], W[n], R[4], Ob[n], th[n], tv[n], tw[n], C[6]; int ss[16]; id[0] = 0; id[1] = 3; id[2] = 2; id[3] = 1; step = 0; memset(s, 0, sizeof(int)*n*fn*tn); 19

s[0][in][0] = mint; do step++; memset(t, 0, sizeof(int)*n*fn*tn); flag = 0; for (i = 0; i < n; i++) for (j = 0; j < fn; j++) for (k = 0; k < tn; k++) if (s[i][j][k]) if (s[i][j][k] < 0) printf("error!"); N = i; R[0] = R[1] = R[2] = R[3] = 0; tj = j; for (l = 0; l < n; l++) H[l] = tj % 15; tj /= 15; tk = k; for (l = 0; l < n; l++) V[l] = cv[h[l]]; H[l] = ch[h[l]]; W[l] = tk % 2; tk /= 2; if (H[l]) R[id[l]]++; if (R[2] + R[3] == 0 R[0] == 0 R[0] + R[1] + R[2] == 0) t[i][j][k] += s[i][j][k]; else if (s[i][j][k] > flag) flag = s[i][j][k]; 20

for (l = 0; l < n; l++) Ob[l] = 0; if (W[N]) l = m = 3; else l = m = 1; o = N; while (l > 0) o = (o + 1) % n; if (o == N) break; if (H[o]) l--; Ob[o] = 1; o = N; while (m > 0) o = (o + n - 1) % n; if (o == N) break; if (H[o]) m--; Ob[o] = 1; switch (id[n]) case 0: if (!R[1]) for (l = 0; l < n; l++) if (Ob[l] && id[l]!= 2) Ob[l] = 0; break; case 1: Ob[0] = 0; break; case 2: if (R[1]) Ob[0] = 0; else for (l = 1; l < n; l++) Ob[l] = 0; break; 21

case 3: if (R[1] + R[2] R[3] > 1) Ob[0] = 0; m = 0; for (l = 1; l < n; l++) if (Ob[l] && H[l] > m) m = H[l]; for (l = 1; l < n; l++) if (Ob[l] && H[l] < m) Ob[l] = 0; nob = 0; for (l = 0; l < n; l++) if (Ob[l]) nob++; for (l = 0; l < 36; l++) memset(c, 0, sizeof(int)*6); C[l%6]++; C[l/6]++; dp = multiply(multiply(s[i][j][k], cpc[l%6], 71), cpc[l/6], 71); if (nob) dp /= nob; for (M = 0; M < n; M++) if (Ob[M]) memcpy(th, H, sizeof(int)*n); memcpy(tv, V, sizeof(int)*n); memcpy(tw, W, sizeof(int)*n); while (C[3]) if (tw[m]) tw[m] = 0; tw[n] = 1; else if (tv[m]) 22

tv[m]--; tv[n]++; C[3]--; while (C[4]) if (tw[m]) tw[m] = 0; else if (tv[m]) tv[m]--; C[4]--; if (C[5]) if (tv[m]) tv[m]--; else th[m]--; th[n] = min(th[n] + C[1], 4); tv[n] += C[0]; tw[n] = min(tw[n] + C[2], 1); tv[n] = min(tv[n], th[n]); ti = (N + 1) % n; while (!H[ti] && ti!= N) ti = (ti + 1) % n; for (m = 0; m < n; m++) th[m] = th[m] * (th[m] + 1) / 2 + tv[m]; tj = 0; tk = 0; for (m = n - 1; m >= 0; m--) tj = tj * 15 + th[m]; tk = tk * 2 + tw[m]; t[ti][tj][tk] += dp; else memcpy(th, H, sizeof(int)*n); 23

memcpy(tv, V, sizeof(int)*n); memcpy(tw, W, sizeof(int)*n); th[n] = min(th[n] + C[1], 4); tv[n] += C[0]; tw[n] = min(tw[n] + C[2], 1); tv[n] = min(tv[n], th[n]); ti = (N + 1) % n; while (!H[ti] && ti!= N) ti = (ti + 1) % n; for (m = 0; m < n; m++) th[m] = th[m] * (th[m] + 1) / 2 + tv[m]; tj = 0; tk = 0; for (m = n - 1; m >= 0; m--) tj = tj * 15 + th[m]; tk = tk * 2 + tw[m]; t[ti][tj][tk] += dp; memcpy(s, t, sizeof(int)*n*fn*tn); printf("%d\n",flag); while (flag); printf("%d\n", step); for (i = 0; i < 16; i++) ss[i] = 0; for (i = 0; i < n; i++) for (j = 0; j < fn; j++) for (k = 0; k < tn; k++) if (s[i][j][k]) N = i; R[0] = R[1] = R[2] = R[3] = 0; 24

tj = j; for (l = 0; l < n; l++) H[l] = tj % 15; tj /= 15; tk = k; for (l = 0; l < n; l++) V[l] = cv[h[l]]; H[l] = ch[h[l]]; W[l] = tk % 2; tk /= 2; if (H[l]) R[id[l]]++; ss[r[0]+r[1]*2+r[2]*4+r[3]*8] += s[i][j][k]; for (i = 0; i < 16; i++) printf("%d :%d\n", i, ss[i]); return 0; B 蒙 特 卡 洛 算 法 代 码 源 代 码 如 下, 采 用 GCC 4.0 编 译 #include <stdio.h> #include <stdlib.h> #define n (10) #define NT 1000000 int Stat[5][5][5][5]; int min(int a, int b) return a < b? a : b; 25

int main() int i, j, k, l, m, o, nob, p; int nt = NT; int N, M, H[n], V[n], W[n], Ob[n]; int R[4], C[6]; int id[n]; int idn[n] = 0, 1, 1, 1, 2, 2, 2, 2, 3, 3; int idm[4] = 1, 3, 4, 2; double vr[4], vs[4]; int card[71] = 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5; srand(0); while (nt > 0) memset(id, 0, sizeof(int)*n); id[0] = 0; i = 1; while (i < n) j = rand() % n; if (!id[j] && j) id[j] = idn[i]; i++; 26

N = 0; for (i = 0; i < n; i++) H[i] = 4; V[i] = 2; W[i] = 0; while (1) R[0] = R[1] = R[2] = R[3] = 0; for (l = 0; l < n; l++) if (H[l]) R[id[l]]++; if (R[2] + R[3] == 0 R[0] == 0 (R[0] + R[1] + R[2] == 0 && R[3] == 1)) break; memset(ob, 0, sizeof(int)*n); if (W[N]) l = m = 3; else l = m = 1; o = N; while (l > 0) o = (o + 1) % n; if (o == N) break; if (H[o]) l--; Ob[o] = 1; o = N; while (m > 0) o = (o + n - 1) % n; if (o == N) break; if (H[o]) 27

m--; Ob[o] = 1; switch (id[n]) case 0: if (!R[1]) for (l = 0; l < n; l++) if (Ob[l] && id[l]!= 2) Ob[l] = 0; break; case 1: Ob[0] = 0; break; case 2: if (R[1]) Ob[0] = 0; else for (l = 1; l < n; l++) Ob[l] = 0; break; case 3: if (R[1] + R[2] R[3] > 1) Ob[0] = 0; m = 0; for (l = 1; l < n; l++) if (Ob[l] && H[l] > m) m = H[l]; for (l = 1; l < n; l++) if (Ob[l] && H[l] < m) Ob[l] = 0; nob = 0; for (l = 0; l < n; l++) if (Ob[l]) nob++; memset(c, 0, sizeof(int)*6); C[card[rand()%71]]++; C[card[rand()%71]]++; if (nob) do M = rand()%n; while (!Ob[M]); while (C[3]) 28

if (W[M]) W[M] = 0; W[N] = 1; else if (V[M]) V[M]--; V[N]++; C[3]--; while (C[4]) if (W[M]) W[M] = 0; else if (V[M]) V[M]--; C[4]--; if (C[5]) if (V[M]) V[M]--; else H[M]--; H[N] = min(h[n] + C[1], 4); V[N] = min(v[n] + C[0], H[N]); W[N] = min(w[n] + C[2], 1); else H[N] = min(h[n] + C[1], 4); V[N] = min(v[n] + C[0], H[N]); W[N] = min(w[n] + C[2], 1); M = N; do M = (M + 1) % n; while (M!= N &&!H[M]); N = M; 29

Stat[R[0]][R[1]][R[2]][R[3]]++; nt--; if (nt % (NT / 10) == 0) printf("%d\n", nt / (NT / 10)); printf("%d & %d & %d & %d & %d \\\\\n", idm[0], idm[1], idm[2], idm[3], n); memset(vr, 0, sizeof(int) * 4); memset(vs, 0, sizeof(int) * 4); for (i = 0; i < 5; i++) for (j = 0; j < 5; j++) for (k = 0; k < 5; k++) for (l = 0; l < 5; l++) if (p = Stat[i][j][k][l]) printf("%d & %d & %d & %d & %d \\\\\n", i, j, k, l, p); vr[0] += i * p; vr[1] += j * p; vr[2] += k * p; vr[3] += l * p; if (i + j + k == 0 && l == 1) vs[0] += 3 * p; vs[3] += 35 / idm[3] * P; else if (k + l == 0) vs[0] += (10 + 5 * j) * p; vs[1] += (7 + 3. * j / idm[1]) * p; if (j + k + l == 0) vs[3] += 15. / id[3] * p; else if (i == 0) vs[2] += (9 + 3. * k / idm[2]) * p; 30

vs[3] += (5. - k) * l / idm[3] * p; vr[0] /= (NT * idm[0]); vr[1] /= (NT * idm[1]); vr[2] /= (NT * idm[2]); vr[3] /= (NT * idm[3]); vs[0] /= NT; vs[1] /= NT; vs[2] /= NT; vs[3] /= NT; printf("%f\t%f\t%f\t%f\n", vr[0], vr[1], vr[2], vr[3]); printf("%f\t%f\t%f\t%f\n", vs[0], vs[1], vs[2], vs[3]); return 0; C 原 始 数 据 当 游 戏 人 数 是 4 人, 主 公 1 人, 忠 臣 1 人, 反 贼 1 人, 内 奸 1 人 时, 有 主 公 忠 臣 反 贼 内 奸 次 数 1 1 1 1 4 0 0 0 1 485928 0 0 1 0 35032 0 0 1 1 101 1 0 0 0 153542 1 1 0 0 325397 表 6: 4: 1 1 1 1 对 应 的 存 活 概 率 和 得 分 期 望 是 主 公 忠 臣 反 贼 内 奸 存 活 概 率 47.89% 32.54% 3.51% 48.60% 31

得 分 期 望 7.87 4.33 0.42 18.16 表 7: 4: 1 1 1 1 当 游 戏 人 数 是 5 人, 主 公 1 人, 忠 臣 1 人, 反 贼 2 人, 内 奸 1 人 时, 有 主 公 忠 臣 反 贼 内 奸 次 数 0 0 0 1 367333 0 0 1 0 42848 0 0 1 1 12477 0 0 2 0 89974 0 0 2 1 90239 1 0 0 0 154155 1 1 0 0 242974 表 8: 5: 1 1 2 1 对 应 的 存 活 概 率 和 得 分 期 望 是 主 公 忠 臣 反 贼 内 奸 存 活 概 率 39.71% 24.30% 20.79% 47.00% 得 分 期 望 6.29 3.51 2.74 14.33 表 9: 5: 1 1 2 1 当 游 戏 人 数 是 6 人, 主 公 1 人, 忠 臣 1 人, 反 贼 3 人, 内 奸 1 人 时, 有 主 公 忠 臣 反 贼 内 奸 次 数 0 0 0 1 234980 0 0 1 0 39799 0 0 1 1 9622 0 0 2 0 101698 0 0 2 1 79516 0 0 3 0 53681 0 0 3 1 147022 1 0 0 0 137557 1 1 0 0 196125 表 10: 6: 1 1 3 1 32

对 应 的 存 活 概 率 和 得 分 期 望 是 主 公 忠 臣 反 贼 内 奸 存 活 概 率 33.37% 19.61% 33.80% 47.11% 得 分 期 望 5.02 2.92 4.90 9.83 表 11: 6: 1 1 3 1 当 游 戏 人 数 是 6 人, 主 公 1 人, 忠 臣 1 人, 反 贼 2 人, 内 奸 2 人 时, 有 主 公 忠 臣 反 贼 内 奸 次 数 0 0 0 1 515781 0 0 1 0 24245 0 0 1 1 7016 0 0 1 2 12886 0 0 2 0 35698 0 0 2 1 44828 0 0 2 2 66038 1 0 0 0 98561 1 1 0 0 194947 表 12: 6: 1 1 2 2 对 应 的 存 活 概 率 和 得 分 期 望 是 主 公 忠 臣 反 贼 内 奸 存 活 概 率 29.35% 19.49% 16.86% 36.27% 得 分 期 望 5.46 2.64 2.22 9.84 表 13: 6: 1 1 2 2 当 游 戏 人 数 是 7 人, 主 公 1 人, 忠 臣 2 人, 反 贼 3 人, 内 奸 1 人 时, 有 主 公 忠 臣 反 贼 内 奸 次 数 0 0 0 1 220690 0 0 1 0 49643 0 0 1 1 5620 0 0 2 0 95569 0 0 2 1 43068 0 0 3 0 33358 33

0 0 3 1 46173 1 0 0 0 177501 1 1 0 0 258277 1 2 0 0 70101 表 14: 7: 1 2 3 1 对 应 的 存 活 概 率 和 得 分 期 望 是 主 公 忠 臣 反 贼 内 奸 存 活 概 率 50.59% 19.92% 19.04% 31.56% 得 分 期 望 7.71 4.14 3.03 9.30 表 15: 7: 1 2 3 1 当 游 戏 人 数 是 8 人, 主 公 1 人, 忠 臣 2 人, 反 贼 4 人, 内 奸 1 人 时, 有 主 公 忠 臣 反 贼 内 奸 次 数 0 0 0 1 173067 0 0 1 0 49173 0 0 1 1 5297 0 0 2 0 109005 0 0 2 1 40022 0 0 3 0 56464 0 0 3 1 57576 0 0 4 0 19452 0 0 4 1 37710 1 0 0 0 169920 1 1 0 0 232631 1 2 0 0 49683 表 16: 8: 1 2 4 1 对 应 的 存 活 概 率 和 得 分 期 望 是 主 公 忠 臣 反 贼 内 奸 存 活 概 率 45.22% 16.60% 23.08% 31.37% 得 分 期 望 6.70 3.66 4.06 7.20 表 17: 8: 1 2 4 1 34

当 游 戏 人 数 是 8 人, 主 公 1 人, 忠 臣 2 人, 反 贼 3 人, 内 奸 2 人 时, 有 主 公 忠 臣 反 贼 内 奸 次 数 0 0 0 1 353958 0 0 1 0 35081 0 0 1 1 5460 0 0 1 2 4236 0 0 2 0 56133 0 0 2 1 37625 0 0 2 2 22319 0 0 3 0 15093 0 0 3 1 29437 0 0 3 2 26752 1 0 0 0 133149 1 1 0 0 228874 1 2 0 0 51883 表 18: 8: 1 2 3 2 对 应 的 存 活 概 率 和 得 分 期 望 是 主 公 忠 臣 反 贼 内 奸 存 活 概 率 41.39% 16.63% 16.36% 26.65% 得 分 期 望 6.86 3.40 2.58 8.25 表 19: 8: 1 2 3 2 当 游 戏 人 数 是 9 人, 主 公 1 人, 忠 臣 3 人, 反 贼 4 人, 内 奸 1 人 时, 有 主 公 忠 臣 反 贼 内 奸 次 数 0 0 0 1 161296 0 0 1 0 52932 0 0 1 1 3615 0 0 2 0 99409 0 0 2 1 27315 0 0 3 0 41506 0 0 3 1 30808 0 0 4 0 10691 0 0 4 1 13979 35

1 0 0 0 187841 1 1 0 0 259768 1 2 0 0 92128 1 3 0 0 18712 表 20: 9: 1 3 4 1 对 应 的 存 活 概 率 和 得 分 期 望 是 主 公 忠 臣 反 贼 内 奸 存 活 概 率 55.84% 16.67% 15.64% 23.70% 得 分 期 望 8.57 4.41 2.99 8.63 表 21: 9: 1 3 4 1 当 游 戏 人 数 是 10 人, 主 公 1 人, 忠 臣 3 人, 反 贼 4 人, 内 奸 2 人 时, 有 主 公 忠 臣 反 贼 内 奸 次 数 0 0 0 1 271987 0 0 1 0 40431 0 0 1 1 4331 0 0 1 2 2169 0 0 2 0 68218 0 0 2 1 30765 0 0 2 2 10919 0 0 3 0 23678 0 0 3 1 29057 0 0 3 2 14347 0 0 4 0 4936 0 0 4 1 10058 0 0 4 2 8193 1 0 0 0 151980 1 1 0 0 240364 1 2 0 0 75525 1 3 0 0 13042 表 22: 10: 1 3 4 2 对 应 的 存 活 概 率 和 得 分 期 望 是 36

主 公 忠 臣 反 贼 内 奸 存 活 概 率 48.09% 14.35% 14.02% 20.87% 得 分 期 望 7.78 3.80 2.64 7.07 表 23: 6: 1 1 3 1 37

参 考 文 献 [1] Mark Barverman, Omid Etesami, Elchanan Mossel,Mafia: A Theoretical Study of Players and Coalitions in a Partial Infomation Environment,The Annals of Applied Probability,2008. [2] 张 波, 张 景 肖, 应 用 随 机 过 程, 清 华 大 学 出 版 社, Springer,2004. 38