组合博弈入门：导引游戏策略与算法解析

"导引游戏-杭电ACM课件(lecture_11)组合博弈入门" 本课件主要讲解了组合博弈的入门知识，特别是通过一个名为“导引游戏”的实例来阐述基本概念和策略。导引游戏是一个两人对弈的游戏，其中包含23张扑克牌，两名玩家按照一定的规则轮流取牌，每次可以取1张、2张或3张，最终取完所有牌的玩家为胜者。 组合博弈，也称为简单取子游戏，具备以下特点： 1. 参与游戏的玩家为两人。 2. 游戏的状态是一个有限集合，例如这里的23张扑克牌。 3. 游戏双方按照规定轮流进行操作。 4. 当某一方无法进行操作时，游戏结束，对方获胜。 5. 游戏总能在有限次操作后结束。 在组合游戏中，关键的概念包括必败点（P点）和必胜点（N点）。必败点指的是前一个玩家无论怎样操作都将导致对手获胜的位置，而必胜点则是下一个玩家有策略可以确保获胜的位置。 必败点和必胜点具有以下性质： 1. 所有游戏的终结状态都是必败点，因为此时没有可操作的空间。 2. 从必胜点出发，玩家总能找到一种策略转移到必败点。 3. 在必败点上，无论怎样操作，都会进入必胜点。 为了求解此类游戏的获胜策略，可以采用以下算法： 1. 首先，将所有终结位置标记为必败点。 2. 然后，检查每个位置，如果一步操作能到达必败点，则将该位置标记为必胜点。 3. 如果从某个位置出发的所有一步操作都只能到达必胜点，那么这个位置也是必败点。 4. 重复步骤2和3，直到没有新的必败点出现，算法结束。 课件中还提供了实际的练习题目，如Subtraction Games，其中定义了一个取子集{1, 3, 4}，并展示了一串位置的必败点和必胜点交替出现的序列。此外，还有其他的实战练习，如“kiki's game”，用于加深对理论知识的理解和应用。 通过这些基础理论和实例，学习者能够理解如何分析和解决简单的组合博弈问题，掌握必败点和必胜点的概念，以及如何运用算法找出游戏的获胜策略。这对于参与ACM程序设计竞赛或对博弈论感兴趣的个人来说，是一份非常有价值的教育资源。