(K,t)-Wythoff博弈模型多項式時間的取勝策略

李海燕, 白云霄, 曹 慧

(陜西科技大學 數(shù)學與數(shù)據(jù)科學學院, 陜西 西安 710021)

0 引言

組合博弈及其取勝策略蘊含著嚴密的數(shù)學邏輯和深刻的理論體系,因而一直受到許多數(shù)學研究者的關注.Wythoff模型是經(jīng)典的兩人公平組合博弈模型之一,其取勝序列與貝蒂定理和斐波那契序列等密切相關.Wythoff模型可描述為:給定初始位置(x,y),兩人輪流移動,移動規(guī)則包括(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∈+.最后移動者取勝.博弈過程中雙方具有相同的決策集(公平的),即雙方面對某個位置或狀態(tài)時具有相同的可選移動[1].

1998年,Fraenkel將上述移動規(guī)則(iii)擴展為(x,y)→(x-k,y-l),s.t.|k-l|

在公平組合博弈中,給定一個位置或狀態(tài),如果競爭者從該位置出發(fā)沒有任何取勝的策略,則稱該位置為P位置; 如果從該位置出發(fā)至少存在一種取勝策略,則稱該位置為N位置.比如在Wythoff模型中,(0,0)、(1,2)、(3,5)等是P位置,同時,根據(jù)移動規(guī)則的對稱性易知(2,1)、(5,3)等也是P位置.對于任意一個公平組合博弈模型,分別用P和N表示它的所有P位置集合和所有N位置集合,且二者劃分了所有的狀態(tài)集.通常P位置相對較少,因此許多學者通過研究模型P位置的特性來確定模型的取勝策略.注意組合博弈模型的取勝策略只取決于模型本身的移動規(guī)則和取勝規(guī)則.更加詳細的組合博弈理論和更多有趣的組合博弈模型,可參考文獻[4-8].

其中mexS=min{S}表示除數(shù)集S中所有元素之外的最小非負整數(shù),例如mex{0,2,3}=1.Fraenkel指出任給博弈位置(x,y)∈×,由mex函數(shù)表示P位置集合的遞歸形式所提供的取勝策略在算法的執(zhí)行時間上關于輸入規(guī)模logxy是指數(shù)的[2,9].

給定參數(shù)K,t∈+,設Ωk={0,1,2,…,K-1},則(K,t)-Wythoff模型的P位置集合為

其中

這里|「·? 表示向上取整函數(shù),例如|「2.4?=3.

在文獻[3]中,作者通過(K,t)-Wythoff模型與t-Wythoff模型之間的內在聯(lián)系,借助于t-Wythoff模型已有的多項式時間取勝策略,間接地給出(K,t)-Wythoff模型的一種多項式時間內可計算的取勝策略.本文將基于(K,t)-Wythoff模型的兩個參數(shù)和P位置特點及其數(shù)學性質,構造一個特殊的數(shù)制系統(tǒng),同時模型位置在該數(shù)制系統(tǒng)下表示唯一且具有簡潔的規(guī)律性,于是(K,t)-Wythoff 模型的取勝策略不再依賴于mex函數(shù)的遞歸表示形式,進而能夠在多項式時間內計算.

1 預備知識

設u-1為常數(shù),令u0=1,且整數(shù)b1≥b2≥1,考慮線性迭代關系:un=b1un-1+b2un-2(n≥1).以u0,u1,u2,…作為權值,以di∈{0,1,…,b1}作為數(shù)碼,構造數(shù)制系統(tǒng),記為U.但對于正整數(shù)un此時有兩種表示方法:un本身和un=b1un-1+b2un-2.因此,為保證表示唯一性,規(guī)定:當di=b1時,一定有di-1

在文獻[3]中,對于t-Wythoff模型,構造數(shù)制系統(tǒng)U1:令u-1=u0=1,b1=t,b2=1,則un=tun-1+uu-2(n≥1),且di+1=t?di<1(i≥0).

例1在t-Wythoff模型中,考慮t=2的情形.此時u-1=u0=1,u1=3,u2=7,u3=17,….表1列出了正整數(shù)1至25在U1中的表示.表2列出了當t=2時t-Wythoff模型的前若干個P位置.

同時滿足以上三條性質的位置(An,Bn)一定是t-Wythoff模型當t=2時的P位置.

任給t-Wythoff模型的位置(x,y),不失一般性,設00,使得x=Bn,那么只存在n>0,使得x=An,注意RU1(Bn)=LRU1(An),容易比較y和Bn的大小并計算接下來的取勝策略.因此,在U1表示下,模型位置的信息完全決定相應的取勝策略.計算RU1(x)的時間復雜度,與輸入規(guī)模的一個確定的冪同階,即n=O(logx),屬于多項式時間算法,于是由這類數(shù)制系統(tǒng)確定的取勝策略是多項式時間的[9].

表1 當t=0時,正整數(shù)1至20的U1表示

表2 當t=2時,t-Wythoff模型的若干P位置

2 一個新的數(shù)制系統(tǒng)

定義1給定參數(shù)K,t∈+,令u-1=u0=K,線性迭代關系為:

un=|「t/K?un-1+un-2(n≥1).

(1)

以u0,u1,u2,…作為權值,以di∈{0,1,…,|「t/K?}作為數(shù)碼,并規(guī)定di+1=|「t/K??di=0(i≥0),定義一個新的數(shù)制系統(tǒng),記為UK.

對任意的i≥0,易知ui∈Mk={nK|n∈}.集合MK中每一個元素即模K余0的非負整數(shù)N都可以在數(shù)制系統(tǒng)UK下表示,且表示形式唯一,記為RUk(N).數(shù)制系統(tǒng)U1實際上是數(shù)制系統(tǒng)UK當K=1時的特殊形式,因此UK是U1的推廣.

例2設參數(shù)K=3,t∈{4,5,6},則|「t/K?=2,于是u-1=u0=3,u1=9,u2=21,u3=51,….數(shù)碼di∈{0,1,2}.表3給出了集合MK中3至69的UK表示.

表3 當t=2時,集合MK中3至69的UK表示

引理設在數(shù)制系統(tǒng)UK的表示下,屬于集合MK以偶數(shù)個0結尾的數(shù)記為{Vm}m≥0,且0=V0

Dm-Vm=|「t/K?Km.

(2)

證明:對m進行數(shù)學歸納.當m=0時,V0=D0=0,結論成立.假設式(2)對于任意m都成立,下面只需證該等式對于m+1也成立.

(3)

令r=|「t/K?,則UK的迭代式(1)簡化為

un=run-1+un-2(n≥1),

(4)

且di∈{0,1,…,r}滿足di+1=r?di=0(i≥0).接下來分情況討論,因為RUK(Vm)的結尾形式一定是以下三種情形之一:

情形1RUK(Vm)的結尾形式為:

d2k+1d2kd2k-1…d2d1d0=d2k+1r0…r0r0r,k∈,

其中d2k+1∈{0,1,…,r}且d2k+1=0?d2k+2

且以奇數(shù)個0結尾; 同時Vm+2K以1結尾,即以偶數(shù)個0結尾,如圖1所示.

圖1 情形1中Vm+K和Vm+2K 結尾形式示意圖

而Vm∈MK(m≥0),所以Vm+1=Vm+2K.注意

RUK(Dm+1)-LRUK(Vm+1),于是一方面

Dm+1-Vm+1=(u1-u0)+(d2k+1+1)u2k+2+

另一方面,根據(jù)式(3),

|「t/K?Km=r(u1-u0)+r(u3-u2)+

r(u5-u4)+…+r(u2k+1-u2k)+

注意將等號右邊所有正項相加,再加u0減u0,將所有負項相加,再減u-1加u-1,根據(jù)式(4),得

|「t/K?Km=u2k+2-u0-u2k+1+u-1+

因此,Dm+1-Vm+1=|「t/K?K(m+1).

情形2RUK(Vm)的結尾形式為:

d2kd2k-1d2k-2…d2d1d0=d2k0…0,k∈+.

其中d2k∈{1,…,r},而

并且Vm+K也以偶數(shù)個0結尾,如圖2所示.

圖2 情形2中Vm+K結尾形式示意圖

故Vm+1=Vm+K.于是,

情形3RUK(Vm)的結尾處d0滿足0

圖3 情形3中Vm+K結尾形式示意圖

由定義1可知,d1

Dm+1-Vm+1=(d0+1)(u1-u0)+

|「t/K?K(m+1).

證畢.

3 (K,t)-Wythoff模型多項式時間的取勝策略

定義2在(K,t)-Wythoff模型中,給定參數(shù)K,t∈+,根據(jù)其P位置集合表達式,對每一個n∈,(An,Bn)是P位置當且僅當(An+α,Bn+β)是P位置,其中α,β∈ΩK={0,1,…,K-1},我們稱(An,Bn)為(K,t)-Wythoff模型的P誘導位置.

例3在(K,t)-Wythoff模型中,考慮K=3,t∈{4,5,6}的情況,表4列出了(K,t)-Wythoff模型的前若干個P誘導位置.

表4 當K=3,t∈{4,5,6}時,(K,t)-Wythoff模型的若干P誘導位置

為了陳述主要結果,這里給出(K,t)-Wythoff模型P誘導位置序列{An},{Bn}的幾個重要性質[3]:

性質1An,Bn∈MK={nK|n∈,K∈+};

性質2對任意n>m≥0,有Bn>An>Am;

下面討論數(shù)制系統(tǒng)UK與(K,t)-Wythoff模型之間的聯(lián)系,并通過下面的定理為(K,t)-Wythoff模型提供多項式時間的取勝策略.

定理對所有的n∈,有(Vn,Dn)=(An,Bn).

證明:當n=0時,顯然有

(V0,D0)=(A0,B0)=(0,0).

對于n≥1,首先由引理和性質1可知Vn,Dn,An,Bn∈MK;其次Dn關于Vn與Bn關于An具有相同的函數(shù)關系,因此只需證An和Vn具有相同的遞歸表達式,即證

Vn=mex{Vi+α,Dj+β|0≤i,j

S={Vi+α,Dj+β|0≤i,j

假設存在某個τ≥n,使得maxS=Dτ,既然Vτ

證畢.

定理表明,在數(shù)制系統(tǒng)UK的表示下,(K,t)-Wythoff模型的P誘導位置具有顯著而簡潔的規(guī)律:

規(guī)律1所有RUK(An)均以偶數(shù)個0結尾.

規(guī)律2所有RUK(Bn)均以奇數(shù)個0結尾.

規(guī)律3對于任意n,RUK(Bn)=LRUK(An).

借助于數(shù)制系統(tǒng)UK的取勝策略優(yōu)點是不存在遞歸的形式,時間復雜度大大減小,類似于第一部分的分析,相應取勝策略在多項式時間內可計算.那么任給(K,t)-Wythoff模型的位置(x,y),如何確定它是P位置或是N位置以及相應的取勝策略?為了敘述方便,給出以下推論.

推論給定參數(shù)K，t∈+,設(x,y)為(K,t)-Wythoff模型的任意位置,則(x,y)∈P當且僅當存在n∈,使得

(|「x/K?K,|「y/K?K)=(Vn,Dn).

證明: 在(K,t)-Wythoff模型中,由于(An,Bn)∈P當且僅當(An+α,Bn+β)∈P,其中An,Bn∈MK,α,β∈ΩK.因此,(x,y)∈P當且僅當存在n∈,使得(|「x/K?K,|「y/K?K)=(An,Bn).由定理可知結論成立.

證畢.

任給(K,t)-Wythoff模型的位置(x,y),設

4 結論

本文通過定義一個新的數(shù)制系統(tǒng)，使得(K,t)-Wythoff模型的P誘導位置在該數(shù)制系統(tǒng)下的表示形式唯一且規(guī)律簡潔，相應的取勝策略在多項式時間內可解.因此，相對于遞歸形式提供的指數(shù)時間的取勝策略，在時間復雜度方面進行了改進.