算法合集之《解析一类组合游戏》.ppt

解析一类组合游戏
四川省绵阳南山中学王晓珂各类取石子游戏

判断是否存在必胜策略怎样分析组合游戏？必败状态的特征

SG函数值游戏的和：
两名参与者轮流操作若干子游戏，每次操作可以选择任意一个子游戏进行操作，最后操作者胜利。
这样的游戏称为其子游戏的和！Sprague-Grundy函数

它是定义在组合游戏状态上的函数

用ｇ（ｘ）表示ｘ状态的函数值。

它的定如下：
ｇ（ｘ）＝ｍｉｎ｛n|n∈N,n≠fory∈F(x)｝Sprague-Grundy定理

ｇ（ｘ１，ｘ２，……ｘｎ）＝ｇ１（ｘ１）ｘｏｒｇ２（ｘ２）……ｇｎ（ｘｎ）
例题1
ｎｉｍ游戏
两人轮流从若干石堆中取走石子，每次可以取走任意一堆中任意数目的石子，但必须取走至少一枚，取走最后一枚石子的人胜利。
一堆石子的游戏：
等价转化例题１:
ACMICPC2006AsiaRegionalContest,Beijing
AFunnyStoneGame

David玩一个石子游戏。游戏中，有n堆石子,被编号为0..n-1。两名玩家轮流取石子。每一轮游戏，每名玩家选取3堆石子i,j,k(i<j,j<=k,且至少有一枚石子在第i堆石子中)，从i中取出一枚石子，并向j，k中各放入一枚石子(如果j=k则向k中放入2颗石子)。最先不能取石子的人输。石堆1：新操作：
拿走一个非0的石堆，并放入2个规模小于他的石堆(可以为0)例题三
IPSC2003GotRoot?
Alice&Bob在一个无向图上玩伐木游戏，无向图有唯一的根。两人轮流从图中截取一条边，将与根部相连的部分抛弃。
这样，最先不能操作的人输。
对于给出的无向图，Alice先行，两人都按最优策略操作,输出胜者的名字。转化成树？树转化成链图转化成树总结：谢谢