有趣的组合博弈(1)：取石子游戏

在一个无聊的下午，小朋友Alice和Bob一起相约在街边的公园玩耍。他们发明了一种新游戏，从公园的地上抓起一把石子，轮流从石子堆中取走石子。每次，每个人可以取走最少1个、最多3个石子，最后取走石子者获得游戏胜利。这种游戏策略简单，结果明确。

如果石子个数不是4的倍数，Alice可以采取策略，每次取走对应个数的石子，使得剩余的石子数恰好是4的倍数。通过这种方式，Alice可以确保在自己取完石子后剩余石子的个数为0，从而获胜。反之，如果石子的个数是4的倍数，那么Bob将获得游戏胜利。

组合博弈游戏包括在有限步内终止，有唯一赢家的游戏。取石子游戏属于此类，定义了游戏状态和状态转移。状态是游戏中的局势，状态转移图展示了状态之间的关系。通过分析状态转移图，可以明确每个状态的胜负性。

以取石子游戏为例，状态转移图显示了不同状态之间的转移关系。状态0（剩余0颗石子）是必败状态，其余状态分为必胜状态和必败状态。通过逐步分析，可以得出每个状态的胜负性。

在组合博弈中，胜负从一开始就注定了，取决于初始状态是必胜还是必败。先手玩家（Alice）如果面对必胜状态将获胜，否则后手玩家（Bob）获胜。

组合博弈的基本概念包括游戏状态和状态转移，通过状态转移图可以解决所有（带有隐含条件的）组合博弈问题。然而，在实际应用中，处理复杂游戏时，状态转移图的构建和分析变得不切实际。存在数学工具可以减少计算量，使得一些原本不可计算的问题变得可以计算。