组合博弈入门：Nim-Sum与简单取子游戏解析

"这篇资料是关于杭州电子科技大学的ACM程序设计课程的课件，主题是组合博弈入门，特别介绍了Nim-Sum的概念，并通过一个简单的取子游戏来阐述组合游戏的基本规则和必败点、必胜点的性质。课程还包含了一些实战练习，如Subtraction Games和Kiki's Game，旨在帮助学生理解和应用理论知识。" 在这个课件中，首先引入了Nim-Sum的概念，它是组合博弈论中的一个基础概念。Nim-Sum是指两个二进制数的异或运算，用于计算游戏中不同状态的胜负情况。在给定的例子中，两个二进制数(xm · · · x0)2 和 (ym · · · y0)2 的nim-sum可以通过逐位相加并取模2得到(zm · · · z0)2，即 zk = xk + yk (mod 2)，这里的k从0到m。这种运算方式在分析游戏状态时非常重要，因为它能够帮助确定游戏的胜负趋势。 接着，课件提到了一个基本的取子游戏，作为组合游戏的一个实例。在这个游戏中，两位玩家轮流从23张扑克牌中取出1张、2张或3张，最后取完牌的人获胜。分析这个游戏的关键在于识别必败点（P点）和必胜点（N点）。必败点指的是当前玩家无论怎么操作都会导致对手在下一轮获胜的位置，而必胜点则是下一玩家可以确保获胜的位置。课件指出，所有游戏的终结点都是必败点，从必胜点出发，总能找到一种策略进入必败点，反之，从必败点出发，所有操作只能导向必胜点。 为了求解这类游戏，课件提出了一个简单的算法，分为四个步骤：首先，标记所有终结点为必败点；其次，标记一步之遥就能到达必败点的位置为必胜点；然后，检查是否所有操作都只能进入必胜点，如果是，则当前点也是必败点；最后，如果无法找到新的必败点，算法结束。这个算法可以帮助分析游戏的胜负策略。 课件中还提供了课内练习Subtraction Games，其规则是玩家可以从中选择1、3或4进行减法操作，同样涉及到必败点和必胜点的判断。此外，还有实战练习Kiki's Game，供学生实践所学知识。 这份资料详细介绍了组合博弈的入门知识，特别是Nim-Sum的计算方法以及如何通过必败点和必胜点的分析来解决这类游戏。对于ACM竞赛和对博弈论感兴趣的编程学习者来说，这是一个很好的学习资源。