杭电ACM课件：组合博弈入门——Subtraction Games与必败/必胜点分析

本资源是一份关于杭州电子科技大学ACM课程的课件，主题是"组合博弈入门"，由刘春英教授提供，邮箱acm@hdu.edu.cn。主要内容围绕Subtraction Games和Nim游戏展开，旨在帮助学生理解简单的博弈理论。 课件首先介绍了Subtraction Games，它是一种两人博弈，参与者使用给定的子集S={1, 3, 4}进行操作，从0开始，玩家轮流取1张、2张或3张牌，直到牌被取完为止。博弈结果的关键在于识别必败点(P点)和必胜点(N点)，即无论对手如何行动，先到达P点的玩家输，反之为赢。学习者需要通过标记策略来确定这些关键位置，例如，在提供的示例中，玩家交替取得优势。 接着，课程转向了Nim游戏，这是一种更经典的组合游戏，规则简单，通常涉及多个堆中的石子，玩家每次可以选择拿走任意数量的石子，但不能拿光。Nim游戏的关键在于 Sprague-Grundy 数（ Grundy 数），通过计算每一轮的剩余选项来判断胜负。必败点和必胜点的概念同样适用于Nim游戏，只是计算方法不同。 课内练习部分具体展示了Subtraction Games的状态，如 Pos: PNPN…，提示学生运用所学理论解决实际问题。实战练习则可能包括Kiki's game，这是一种具有挑战性的变体，用于检验学生对博弈策略的理解和应用能力。 这份课件不仅教授了基础的组合博弈理论，还通过实际练习帮助学生巩固知识，并培养他们在实际竞赛环境中的策略思考。通过解决这类问题，学生能够提升他们的逻辑分析能力和编程技巧，以应对ACM竞赛中的类似挑战。