2025-11-16T22:28:12.942550

Reinforcing Competitive Multi-Agents for Playing 'So Long Sucker'

Sharan, Adak
This paper investigates the strategy game So Long Sucker (SLS) as a novel benchmark for multi-agent reinforcement learning (MARL). Unlike traditional board or video game testbeds, SLS is distinguished by its coalition formation, strategic deception, and dynamic elimination rules, making it a uniquely challenging environment for autonomous agents. We introduce the first publicly available computational framework for SLS, complete with a graphical user interface and benchmarking support for reinforcement learning algorithms. Using classical deep reinforcement learning methods (e.g., DQN, DDQN, and Dueling DQN), we train self-playing agents to learn the rules and basic strategies of SLS. Experimental results demonstrate that, although these agents achieve roughly half of the maximum attainable reward and consistently outperform random baselines, they require long training horizons (~2000 games) and still commit occasional illegal moves, highlighting both the promise and limitations of classical reinforcement learning. Our findings establish SLS as a negotiation-aware benchmark for MARL, opening avenues for future research that integrates game-theoretic reasoning, coalition-aware strategies, and advanced reinforcement learning architectures to better capture the social and adversarial dynamics of complex multi-agent games.
academic

Reinforcing Competitive Multi-Agents for Playing 'So Long Sucker'

基本信息

  • 论文ID: 2411.11057
  • 标题: Reinforcing Competitive Multi-Agents for Playing 'So Long Sucker'
  • 作者: Medant Sharan (King's College London), Chandranath Adak (IIT Patna)
  • 分类: cs.AI
  • 发表时间: 2024年11月 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2411.11057

摘要

本文首次将策略游戏"So Long Sucker"(SLS)引入多智能体强化学习(MARL)领域作为新基准。与传统棋类或视频游戏测试平台不同，SLS具有联盟形成、策略欺骗和动态淘汰规则等特点，为自主智能体提供了独特的挑战环境。研究者构建了首个公开可用的SLS计算框架，包含图形用户界面和强化学习算法基准测试支持。通过经典深度强化学习方法(DQN、DDQN、Dueling DQN)训练自对弈智能体学习SLS规则和基本策略。实验结果表明，虽然这些智能体能达到最大可获得奖励的约一半并持续优于随机基线，但需要长训练周期(约2000局游戏)且仍会偶尔执行非法动作，凸显了经典强化学习的潜力和局限性。

研究背景与动机

问题定义

现有的多智能体强化学习基准主要集中在纯合作目标(如协调任务)或对抗竞争(如两人零和博弈)，缺乏能够同时捕捉联盟形成和背叛动态的混合环境。虽然在Go、StarCraft II和Diplomacy等领域取得了突破，但这些基准并未充分体现SLS所特有的联盟与背叛混合动态。

研究重要性

SLS作为由Hausner、Nash、Shapley和Shubik设计的四人策略游戏，围绕联盟形成、临时联盟和不可避免的背叛展开，胜利不仅依赖合法行动，还需要外交和机会主义，使其成为研究信任、谈判和社会困境的独特测试平台。

现有方法局限性

  1. 大多数MARL基准缺乏联盟和背叛的混合动态
  2. 社会丰富设置的先前工作通常依赖显式通信渠道或手工制作的交互规则
  3. SLS此前未被作为计算基准进行研究

研究动机

通过将SLS形式化为可重现的序贯变体并基准测试基线DRL算法，本文将SLS定位为推进MARL研究的联盟和背叛感知测试平台。

核心贡献

  1. 首个SLS计算框架: 设计并发布了首个专为强化学习研究定制的SLS计算框架，配备GUI用于实验
  2. 经典DRL算法基准测试: 在SLS中基准测试了经典DRL算法(DQN、DDQN、Dueling DQN)，分析其获得合法游戏熟练度和部分策略意识的能力
  3. 联盟与背叛感知基准: 将SLS确立为MARL的联盟和背叛感知基准，激发结合DRL与博弈论推理的混合方法的未来研究

方法详解

任务定义

将SLS转换为MARL环境，采用广义Hofstra版本的零和变体。四名玩家每人分配独特颜色，从5个同色筹码开始，在最多6个活跃堆栈的棋盘上进行游戏。获胜条件是成为最后幸存的玩家。

强化学习形式化

将SLS建模为马尔可夫决策过程(MDP)：

  • 状态空间S: 所有可能的游戏状态集合
  • 动作空间A: 智能体可用的所有动作集合(离散有效移动集)
  • 转移函数: p(s'|s,a)表示在状态s执行动作a后转移到s'的概率
  • 奖励函数: r(s,a,s')为每次转移分配标量值
  • 策略: π(a|s)是智能体在给定状态s下选择动作a的策略

目标是找到最优策略π*以最大化期望折扣回报： Rt=∑k=0∞γkrt+k+1R_t = \sum_{k=0}^{\infty} \gamma^k r_{t+k+1}

状态表示

状态st编码描述游戏环境所需的所有信息： st=(Board Configuration,Player Chips,Eliminated Chips,Current Player,Game Phase,Step Count)s_t = (Board\ Configuration, Player\ Chips, Eliminated\ Chips, Current\ Player, Game\ Phase, Step\ Count)

观察空间大小为： obs_size=(nrows×nplayers×nmax_pile)+nplayers2+(2×nplayers)+4+1obs\_size = (n_{rows} \times n_{players} \times n_{max\_pile}) + n_{players}^2 + (2 \times n_{players}) + 4 + 1

动作空间

离散动作空间A = {A₀, A₁, ..., A₉}，包括：

  • A₀-A₅: 堆栈选择动作(选择堆栈阶段有效)
  • A₆-A₉: 玩家/颜色决策动作(选择筹码、选择下一玩家、淘汰筹码阶段有效)

奖励设计

奖励信号在时间步t的定义为： rt=min⁡(℘,℘(α/nc)⋅t)r_t = \min\left(\wp, \frac{\wp}{(\alpha/n_c) \cdot t}\right)

其中α ∈ (0,1]是控制衰减率的超参数，℘为奖励幅度。非法动作受到固定负奖励(-℘)惩罚，合法动作获得最多+℘的正奖励，该值随步数衰减以促进效率。

实验设置

游戏配置

  • 玩家数量: 4名玩家
  • 初始筹码: 每名玩家5个同色筹码
  • 最大堆栈数: 6个活跃堆栈
  • 获胜条件: 零和博弈，奖励结构{0,0,0,ù}，ù ∈ N⁺

训练配置

采用集中式累积学习设置，所有四个玩家智能体共享公共学习网络和重放缓冲区。网络架构为两个64神经元的全连接隐藏层(ReLU激活)，后接线性输出层。

超参数设置

  • 折扣因子γ = 0.95
  • 初始探索率ε₀ = 1.0
  • 探索衰减率ε_decay = 0.995
  • 最小探索率ε_min = 0.01
  • 学习率 = 0.001
  • 批次大小 = 64
  • 训练轮次 = 10,000局

评价指标

  • 累积奖励均值和标准差
  • 每局平均步数
  • 奖励范围最小值, 最大值
  • 步数范围最小值, 最大值

对比方法

  • DQN (Deep Q-Network)
  • DDQN (Double DQN)
  • Dueling DQN
  • Random baseline (随机基线)

实验结果

主要结果

智能体奖励(均值±标准差)奖励范围最小,最大步数(均值±标准差)步数范围最小,最大
DQN103.40 ± 42.31-313.45, 189.2461.16 ± 14.5127, 162
DDQN108.44 ± 44.95-279.13, 191.3861.23 ± 14.1828, 165
Dueling DQN102.06 ± 49.62-319.76, 192.0965.92 ± 15.9428, 173
Random-8.78 ± 43.52-419.26, 94.1965.24 ± 17.7629, 174

关键发现

  1. 性能表现: 所有DRL智能体均持续优于随机基线，达到理论最大奖励(≈200)的约一半
  2. 收敛特性: DDQN实现最稳定收敛和最高平均奖励，验证了双重估计在缓解长期博弈Q值过估计方面的益处
  3. 学习动态: 早期训练阶段(<500局)智能体表现出大幅奖励方差，约2000局后所有DRL智能体显示更平滑收敛

学习曲线分析

训练过程分为三个阶段：

  • 探索阶段(0-500局): 高方差，频繁非法动作
  • 学习阶段(500-2000局): 逐步掌握规则，奖励稳步上升
  • 收敛阶段(>2000局): 奖励稳定在100-120范围，偶有探索性下降

相关工作

MARL基准发展

  • 传统基准: Go、StarCraft II主要关注纯竞争或合作
  • 社会博弈: Diplomacy等涉及谈判但依赖显式通信
  • 博弈论应用: Nash均衡求解在多智能体系统中的应用

深度强化学习在博弈中的应用

  • AlphaGo系列: 在完全信息博弈中的突破
  • 多智能体学习: 自对弈训练和策略多样性
  • 价值函数方法: DQN及其变体在离散动作空间中的应用

SLS相关研究

本文首次将SLS作为计算基准，填补了联盟形成和背叛动态研究的空白。

结论与讨论

主要结论

  1. 经典价值基方法能够学习SLS的核心规则和部分策略，实现稳定但次优的性能
  2. 奖励的高方差反映了对初始化和探索的敏感性
  3. 上下文相关动作暴露了短期价值估计的局限性
  4. SLS成功建立为谈判感知的MARL基准

局限性

  1. 策略局限: 智能体往往采取反应式而非战略性行为
  2. 规则遵守: 尽管采用动态动作掩码，仍偶尔执行非法动作
  3. 长期推理: 在组合动作空间和延迟奖励依赖性方面存在困难
  4. 联盟动态: 未能充分捕捉复杂的联盟形成和背叛策略

未来方向

  1. 架构改进: 集成actor-critic和联盟感知框架
  2. 策略增强: 加强长期推理和规则遵守
  3. 社会动态: 开发谈判/联盟/欺骗能力
  4. 理论分析: 结合博弈论推理与深度学习

深度评价

优点

  1. 创新性基准: 首次将SLS引入MARL，填补了联盟与背叛动态研究的重要空白
  2. 完整框架: 提供了包含GUI的完整计算框架，促进可重现研究
  3. 系统评估: 对多种经典DRL方法进行了全面基准测试
  4. 理论贡献: 明确了零和变体规则，解决了原始形式化的不完整性

不足

  1. 方法局限: 仅测试了经典价值基方法，未探索更先进的MARL算法
  2. 简化设定: 移除了显式谈判机制，可能损失了SLS的核心特征
  3. 性能瓶颈: 智能体仍执行非法动作，暴露了基础方法的不足
  4. 理论分析不足: 缺乏对SLS博弈论性质的深入分析

影响力

  1. 学术价值: 为MARL社区提供了新的研究方向和基准
  2. 实用意义: 框架的开源发布将促进后续研究
  3. 方法论贡献: 展示了如何将复杂策略游戏转化为ML友好的环境
  4. 局限性启发: 揭示了经典RL在复杂社会博弈中的不足，指引未来研究方向

适用场景

  1. MARL研究: 联盟形成和背叛动态的算法开发
  2. 博弈论应用: 多方谈判和策略推理的计算模型
  3. 社会AI: 信任、欺骗和合作行为的建模
  4. 教育工具: 博弈论和多智能体系统的教学演示

参考文献

  1. Hausner, M., Nash, J., Shapley, L., & Shubik, M. (1964). So Long Sucker- A Four-Person Game
  2. Vinyals, O. et al. (2019). Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature
  3. FAIR Team et al. (2022). Human-level play in the game of diplomacy by combining language models with strategic reasoning. Science
  4. Mnih, V. et al. (2015). Human-level control through deep reinforcement learning. Nature

本论文通过引入SLS作为MARL新基准，为研究联盟形成和策略欺骗提供了宝贵平台。虽然当前结果显示经典方法的局限性，但这恰恰突出了该基准的挑战性和研究价值，为未来开发更先进的多智能体学习算法指明了方向。