组合博弈入门：从简单取子到Nim游戏

"每周一星-杭电ACM课件(lecture_11)组合博弈入门，由杭州电子科技大学刘春英教授讲解，主要介绍了组合博弈的基础知识，包括简单的取子游戏和Nim游戏。" 在本次课程中，我们探讨了组合博弈的入门知识，这是一种涉及两个玩家的战略游戏。首先，通过一个名为"导引游戏"的例子来引入主题，这个游戏要求两名玩家轮流取一定数量的扑克牌，最终取光牌的人获胜。这个游戏引出了组合游戏的基本特征：两个玩家，有限的游戏状态，轮流操作，以及有限步数内结束。 组合游戏的定义进一步明确了这些特点，强调了游戏的有限性、可操作性和胜负条件。其中，关键概念包括必败点（P点）和必胜点（N点）。必败点指的是当前玩家无论怎么操作都无法获胜的位置，而必胜点则是下一玩家有策略可以赢得游戏的位置。必败点和必胜点具有特定的性质，例如所有终结状态都是必败点，且从必胜点出发总能找到通往必败点的路径。 为了确定游戏中的必败点和必胜点，课程介绍了一种算法实现，包括四个步骤：首先标记所有终结位置为必败点，接着找出一步操作能到达必败点的位置作为必胜点，然后检查是否有位置的所有一步操作都只能进入必胜点，最后不断重复这个过程直到没有新的必败点出现。 课程还提供了实际练习，如Subtraction Games，它涉及到一个减法集S={1,3,4}，并展示了不同位置的必败点和必胜点模式。此外，还有"Kiki's Game"作为实战练习，让学生们应用所学理论解决具体问题。 最后，课程预告了第二部分将讨论的Nim游戏，这是一类更复杂的组合游戏，通常涉及多个堆物体，玩家每次可以从中取走一定数量的物体，目标也是迫使对手无法进行有效操作。 通过这次的“每周一星”讲座，学习者能够初步掌握组合博弈的理论基础，理解必败点和必胜点的概念，并通过实例和练习提升分析和解决问题的能力。这为进一步深入研究博弈论和其他相关领域的复杂策略奠定了坚实的基础。