组合博弈入门：必败与必胜点策略

本资源是一份关于组合博弈入门的ACM课程材料，由杭州电子科技大学的刘春英教授提供，邮件地址为acm@hdu.edu.cn，日期为2024年5月19日。课程围绕组合博弈展开，主要讲解了简单取子游戏的概念，这种博弈类型涉及两个玩家，游戏状态在一个有限集合（如指定大小的棋盘）中进行，遵循轮流操作的规则，且游戏最终会在有限步内结束。 核心知识点包括： 1. 组合博弈基础：组合游戏的特点是两个玩家，操作受限在有限状态空间，每轮只能取1、2或3张牌，直到牌被取完为止。胜利条件是最后一手操作的玩家无法使对手赢得比赛。 2. 必败点与必胜点：必败点（P点）是指当前玩家无法赢得的游戏状态，而必胜点（N点）则是后续玩家能够确保胜利的状态。所有终结点都是必败点，从必胜点出发总能找到进入必败点的方法，反之亦然。 3. 取子游戏算法：算法的核心是通过标记必败点和必胜点来判断游戏的胜负情况，首先标记所有终结位置为P点，然后找出可以一步达到P点的位置作为N点，再检查是否有无法回退到P点的情况，反复这个过程直到找到新P点或算法终止。 4. 实例分析：课程中提供了两个练习案例，如SubtractionGames，其中给出了初始状态和可能的胜败分布，以及"Kiki's game"，这是一种实战练习，用于学生理解和应用所学理论。 通过这些内容，学生可以学习如何分析这类组合博弈问题，理解如何通过策略选择和逻辑推理在有限步骤内确定游戏结果，这对于提高算法思维和解决实际ACM竞赛中的类似问题具有重要意义。对于准备参加杭电ACM课程或者想要提升博弈论和动态规划技巧的学生来说，这份资料是一份宝贵的资源。