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

本资源是关于杭州电子科技大学ACM课程中的“组合博弈入门”部分，由刘春英教授讲解，针对的是大学生进行的编程竞赛训练。主要内容涉及Graph Games（图博弈）和Sprague-Grundy函数，这些是博弈论在计算机科学中的应用。 在课程中，首先介绍了组合博弈的概念，它定义为一种两人对局，其状态空间是有限的，例如棋盘或特定大小的扑克牌游戏。游戏规则明确，包括轮流操作、有限步骤结束、以及胜利条件（最后一个取牌者为胜）。核心策略分析了必败点（P点）和必胜点（N点）的概念，其中必败点是前一个玩家无法避免失败的位置，而必胜点则是后一个玩家能确保获胜的位置。 算法实现的关键在于识别并标记这些点，步骤包括标记终结位置为P点，标记一步可达的P点为N点，以及递归检查是否所有一步操作只能到达N点，从而形成循环。举例中，"SubtractionGames"和"kiki'sgame"作为实战练习，前者涉及数字减法操作的游戏，后者则可能是一种更复杂的策略游戏，用于学生们实际操作和理解Sprague-Grundy函数的应用。 通过学习这个部分，学生不仅能提升编程技能，还能理解基本的博弈理论在解决这类问题时的作用，这对于解决ACM竞赛中的动态决策问题尤其重要。掌握这些概念和算法，能够帮助参赛者在有限时间内制定出有效的策略，提高比赛中的胜算。