Optimal Strategies For A Few Classes Of Impartial Combinatorial Games In Discrete Space

Combinatorial game theory,a combination of the traditional game theory,combination op-timization and discrete mathematics,is mainly used in the computer field.In this paper,we mainly study the restrictions and extensions of the classical(s,t)-Wythoff game model,put forward several related game models,with solving all of their P-positions,and give their optimal polynomial time winning strategy using some new methods.The main contributions of this dissertation are summarized as follows:1.Three restricted models about(s,t)-Wythoff game in the horizontal and vertical directions are presented,and all of their P-positions for any s,t ∈ Z+ are solved thoroughly under both normal and misere play conventions.2.Firstly,some improvements are made for the strategies of two old models,EEW and Γ(s,t):By building a relationship between EEW and the original(s,t)-Wythoff,on the basis of the numeration system u1(presented by Fraenkel),a poly-time winning strategy for EEW is provided;by constructing a new numeration system u2,another poly-time winning strategy for r(s,t)is provided.Secondly,by extending EEW game,i.e.,adding some P-positions of EEW as additional legal moves,yields a new class of game models,which are denoted by Γ1EEW,Γ2EEW,Γ3EEW and Γ4EEW,aespectively.In normal play,a recursive.form of the set of the P-positions for Γ1EEW is given by using the mex function,which provides an exponential time winning strategy.Moreover,when s=1,t>2,an algebraic form of all P-positions for Γ1EEW is also given,which provides a poly-time winning strategy;when s>1,t ∈Z+,two poly-time winning strategies for Γ1EEW are provided by two different ways,i,e.,by defining a new numeration system and building a connection between the new and old models,respectively.Finally,it is proved in detail that the other three gamesΓ2EEW,Γ3EEW and Γ4EEW are all equivalent to Γ1EEW under certain conditions,thereby they have the same exponential and poly-time winning strategies as Γ1EEW does.3.A new(K,s,t)-Wythoff game model is defined,which is a further promotion of(s,t)-Wythoff game.Under both normal and misere play conventions,for any parameters K,5,t ∈Z+,the sets of P-positions for(K,s,t)-Wythoff are given by recursive forms,which provide exponential time winning strategies.In normal play,by a relationship between(K,s,t)-Wythoff and(s,t)-Wythoff,based on the numeration system u1,a poly-time winning s-trategy for(K,s,t)-Wythoff is indirectly obtained;by using a new numerical system uK,another poly-time winning strategy for(K,s,t)-Wythoff is directly given.In misere play,we also provide a poly-time strategy for(K,s,t)-Wythoff when s=1 by connecting(K,s,t)-Wythoff with a-Wythoff.Further,by extending(K,s,t)-Wythoff game,i.e.,adding some P-positions of(K,s,t)-Wythoff as additional legal moves,obtains a new class of game models,denoted by Γ1(K,s,t),Γ2(K,s,t),Γ3(K,s,t)and Γ4(K,s,t),respectively.About Γ1(K,s,t)under normal play convention,a recursive form of all P-positions for Γ1(K,s,t)under certain con-ditions is given,which provides an exponential time winning strategy.Furthermore,when s=1,and for any t>K,an algebraic form of all P-positions for Γ1(K,s,t)is given,which provides a poly-time winning strategy;when s>1,and for any K,t ∈Z+,two poly-time winning strategies for Γ1(K,s,t)are provided by different ways directly and indirectly,respec-tively.Finally,it is proved that Γ2(K,s,t),Γ3(K,s,t)and Γ4(K,s,t)have the same exponential time and poly-time winning strategies as Γ1(K,s,t)does under certain conditions.4.A n-player(s,t)-Wythoff game is presented,which is an extension of(s,t)-Wythoff about the number of players,and the play piles remain unchanged.Based on the impartial combinatorial game theory about n players introduced by Krawec in 2012,the n-player(s,t)-Wythoff game is analyzed.All the game values are obtained when s = 1,which determine the winning player relative to the current player.