杭电ACM课件：组合博弈入门——简单游戏理论

"杭电ACM课程的第三部分主要讲解了组合博弈的入门知识，包括Graph Games和Sprague-Grundy函数的概念。课程由杭州电子科技大学的刘春英教授讲授，探讨了一种简单的取子游戏，即组合游戏的一个实例，并深入介绍了必败点和必胜点的概念以及它们的特性。课程还提到了取子游戏的算法实现步骤，并提供了课内和实战练习，如Subtraction Games和kiki's game，以帮助学生理解和应用所学知识。" 在组合博弈中，游戏的基本结构通常包括两个玩家，一个有限的操作状态集合，以及按照特定规则轮流进行的操作。游戏的目标是通过策略使自己成为最后一个执行操作的人，从而获胜。在本课中提到的取子游戏为例，玩家需要在有限的扑克牌中按照特定规则取牌，最后取完牌的人为胜者。 必败点（P点）和必胜点（N点）是组合游戏中关键的概念。必败点指的是当前玩家无论怎么操作，都无法避免让对手在下一轮取得胜利的位置。相反，必胜点则是下一个玩家总能找到一种策略使自己获胜的位置。所有的终结状态都是必败点，因为一旦到达这些点，游戏结束且当前玩家无法再操作。从必胜点出发，玩家总能通过一次操作转移到必败点，而从必败点出发，玩家无论如何操作都会进入必胜点。 为了确定游戏中的必败点和必胜点，可以采用以下算法： 1. 首先，标记所有终结状态为必败点。 2. 接着，检查所有可以从当前位置一步操作到达必败点的位置，并将其标记为必胜点。 3. 如果一个位置的所有一步操作都只能进入必胜点，那么这个位置也被标记为必败点。 4. 重复步骤2和3，直到没有新的必败点出现，算法结束。 课程中还给出了Subtraction Games的示例，它是一种允许玩家在一系列数字中选择减去特定数值的游戏。在这个游戏中，玩家需要根据 subtraction set（例如 {1, 3, 4}）来决定每次减去的数值，目标是使对手无法进行操作。课件展示了游戏的不同状态（P点和N点）。 此外，课程提到了Nim游戏，这是一种经典的组合博弈，通常涉及多堆物品，玩家可以移除任意堆中任意数量的物品，但必须移除。Nim游戏有着深入的理论基础，其解决方案可以通过计算nim-sum来确定。 这门课程为学生提供了一个了解和解决组合博弈问题的基础，通过实际的游戏和练习，帮助他们掌握必胜策略和分析游戏状态的方法。