李海燕, 白云霄, 曹 慧

(陕西科技大学 数学与数据科学学院, 陕西 西安 710021)

0 引言

组合博弈及其取胜策略蕴含着严密的数学逻辑和深刻的理论体系,因而一直受到许多数学研究者的关注.Wythoff模型是经典的两人公平组合博弈模型之一,其取胜序列与贝蒂定理和斐波那契序列等密切相关.Wythoff模型可描述为:给定初始位置(x,y),两人轮流移动,移动规则包括(i)(x,y)→(x-k,y);(ii)(x,y)→(x,y-l);(iii)(x,y)→(x-k,y-k).终止位置为(0,0).其中x,y∈且k,l∈+.最后移动者取胜.博弈过程中双方具有相同的决策集(公平的),即双方面对某个位置或状态时具有相同的可选移动[1].

1998年,Fraenkel将上述移动规则(iii)扩展为(x,y)→(x-k,y-l),s.t.|k-l|

在公平组合博弈中,给定一个位置或状态,如果竞争者从该位置出发没有任何取胜的策略,则称该位置为P位置; 如果从该位置出发至少存在一种取胜策略,则称该位置为N位置.比如在Wythoff模型中,(0,0)、(1,2)、(3,5)等是P位置,同时,根据移动规则的对称性易知(2,1)、(5,3)等也是P位置.对于任意一个公平组合博弈模型,分别用P和N表示它的所有P位置集合和所有N位置集合,且二者划分了所有的状态集.通常P位置相对较少,因此许多学者通过研究模型P位置的特性来确定模型的取胜策略.注意组合博弈模型的取胜策略只取决于模型本身的移动规则和取胜规则.更加详细的组合博弈理论和更多有趣的组合博弈模型,可参考文献[4-8].

其中mexS=min{S}表示除数集S中所有元素之外的最小非负整数,例如mex{0,2,3}=1.Fraenkel指出任给博弈位置(x,y)∈×,由mex函数表示P位置集合的递归形式所提供的取胜策略在算法……