组合博弈入门：简单取子游戏算法解析

"HDOJ--杭电ACM课件(lecture_11)组合博弈入门" 这篇资源主要涉及的是组合博弈的入门知识，包括ACM程序设计中的简单取子游戏和Nim游戏。课程由杭州电子科技大学的刘春英教授讲解，并提供了相关源代码示例。以下是具体内容的详解： 首先，课程提到了一个基础的取子游戏模型，它有两名玩家，23张扑克牌，玩家轮流取1张、2张或3张，最后取完牌的人获胜。这个问题的关键在于识别游戏中的必败点（P点）和必胜点（N点）。必败点是指当前玩家无论怎么操作都会导致对手获胜的状态，而必胜点则是下一个玩家总能找到策略赢取游戏的状态。 接着，课程介绍了组合游戏的一般定义，包括两个玩家、有限的操作状态、轮流操作、有限次操作后游戏结束等特性。还提到了必败点和必胜点的属性：所有终结状态是必败点，从必胜点出发至少有一种方法到达必败点，从必败点出发只能到达必胜点。 然后，给出了求解此类游戏的算法，分为四个步骤： 1. 将所有终结位置标记为必败点（P点）。 2. 将所有一步操作能进入必败点的位置标记为必胜点（N点）。 3. 如果某个点的所有一步操作都只能进入必胜点，将其标记为必败点（P点）。 4. 如果无法找到新的必败点，则算法终止，否则回到步骤2。 课程中还给出了一个实际的取子游戏例子，如Subtraction Games，其中定义了一个减法集`subtractionsetS={1,3,4}`，并展示了不同数量的子游戏状态，用"P"表示必败点，"N"表示必胜点。 此外，课程提到了另一个实战练习，可能是“Kiki's Game”，但具体规则没有给出，可能需要进一步学习或查阅相关资料。 最后，提供了源代码，这是一段C++代码，用于解决这类组合博弈问题。函数`mex`用于计算最小未使用的非负整数，`main`函数读取玩家和牌的数量，通过`mex`函数计算每个回合后的游戏状态，并输出获胜者（"L"表示先手赢，"W"表示后手赢）。 通过这个资源，学习者可以理解组合博弈的基本概念，掌握判断游戏胜负的策略，并能够编写程序来解决类似的问题。这对于参加ACM/ICPC等编程竞赛或对算法有兴趣的人来说是非常有价值的。