(K,t)-Wythoff博弈模型多项式时间的取胜策略  

A polynomial time winning strategy for(K,t)-Wythoff game

作　　者：李海燕[1] 白云霄[1] 曹慧[1] LI Hai-yan;BAI Yun-xiao;CAO Hui(School of Mathematics & Data Sciences, Shaanxi University of Science & Technology, Xi′an 710021, China)

机构地区：[1]陕西科技大学数学与数据科学学院,陕西西安710021

出　　处：《陕西科技大学学报》2021年第3期177-181,共5页Journal of Shaanxi University of Science & Technology

基　　金：国家自然科学基金项目(11971281);陕西省教育厅专项科研计划项目(20JK0546);陕西省科技厅自然科学基础研究计划项目(2020J-700)。

摘　　要：Li、Liu、Fraenkel等人于2017年提出了著名的两人公平组合博弈模型Wythoff模型的一个变体——(K,t)-Wythoff模型,并给出该模型P位置集合的数学刻画以及相应的指数时间内可计算的取胜策略.本文通过构造特殊的数制系统,使得(K,t)-Wythoff模型的P位置和N位置在该数制系统下表示唯一且有确切的规律,进而给出多项式时间内可计算的取胜策略.In 2017,Li,Liu and Fraenkel et al.proposed(K,t)-Wythoff game,which is a variant of the famous two-player impartial combinatorial game Wythoff,and provided the mathematical characterization of the set of its P-positions and the corresponding winning strategy which can be calculated in exponential time.In this paper,we provide a winning strategy for(K,t)-Wythoff game which can be calculated in polynomial time,using a special numeration system in which the P-positions and N-positions of(K,t)-Wythoff game have unique representations and definite rule.

关 键 词：组合博弈 Wythoff模型 多项式时间 

分 类 号：O225[理学—运筹学与控制论]