博弈论

（本文章主要涉及Nim博弈及相关变种，二分图博弈以后再补_(:з)∠)_） Nim博弈是最经典的博弈论问题之一，一般可以描述为如下：两个人轮流从若干堆石子中取石子，每次只能取一堆石子中的任意个，最后无法取（即所有石子都被取完）的玩家判负。Nim游戏拥有简洁的规则和优雅的结论，也是SG函数的基础。 基本概念 首先明确一些概念，Nim博弈是公平组合游戏（Impartial Combinatorial Games, ICG）的一种，所谓公平组合游戏，需要满足以下几个条件 有两个玩家 两个玩家轮流操作，在一个有限集合内任选一个进行操作，改变游戏当前局面 一个局面的合法操作只与游戏当前局面有关，与当前玩家和次序等其他因素无关（公平） 无法操作者判负 为什么要提这个呢？因为从这些条件里，我们可以得出一个最基本的定理：一局游戏的胜负只与当前的局面有关，与当前是哪个玩家在操作无关，因为当局面确定，由于合法操作不受其他因素影响，那么其所有可以进行的操作与操作后的局面都是确定的，在两个玩家都绝对理性的情况下（这是大前提，否则就没有意义了），其胜负自然也是确定的。 那么，我们就可以把所有局面分成两种：必 ...