一種基于神經(jīng)網(wǎng)絡(luò)和Bradley-Terry模型的圍棋等級分模型

趙 睿 趙銀亮

(西安交通大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 陜西 西安 710049)

0 引 言

競技類體育賽事和游戲等一般都依賴于等級分系統(tǒng)進(jìn)行評價(jià)。等級分系統(tǒng)提供了對參賽選手水平的估計(jì)，該估計(jì)可用于安排更為公平、均衡的賽事，也能用于對未來的賽事進(jìn)行結(jié)果預(yù)測，同時(shí)提供參賽選手競技水平的動(dòng)態(tài)變化以激勵(lì)參賽者及觀眾。

多個(gè)個(gè)體之間的比較和排序通常以兩兩比較的形式進(jìn)行。分析成對比較數(shù)據(jù)的最主要的統(tǒng)計(jì)模型之一是Bradley-Terry模型[1](以下簡寫為B-T模型)，其將比較結(jié)果的概率建模為兩個(gè)選手技能βi和βj之和的函數(shù)，如式(1)所示。同時(shí)為了避免實(shí)力懸殊的選手技能評分?jǐn)?shù)量級相差過大，通常采取指數(shù)形式的實(shí)力ri和rj之和，如式(2)所示。由于B-T模型在成對比較數(shù)據(jù)模型中具有良好的統(tǒng)計(jì)性質(zhì)，因此應(yīng)用廣泛[2]。

(1)

(2)

Elo[3]最早為棋類賽事開發(fā)了一個(gè)增量式評級系統(tǒng)，該系統(tǒng)自1970年以來一直被國際象棋聯(lián)合會(huì)FIDE采用，并在改進(jìn)后因其客觀性、公平性成為選手水平評估的權(quán)威方法?；贓lo等級分系統(tǒng)，貝葉斯評級系統(tǒng)Glicko[4]首次考慮了選手評分的可信度；作為Elo算法在多人賽事中的擴(kuò)展，微軟研究院開發(fā)的Trueskill系統(tǒng)[5]能從團(tuán)隊(duì)對戰(zhàn)結(jié)果中推斷玩家個(gè)人技能。Elo、Glicko和Trueskill算法均屬于增量式模型，該類模型存在著對局信息利用不充分的問題，比如不能很好地體現(xiàn)出只與固定對手比賽的那些選手的競技水平變動(dòng)情況[6]。已有的增量式算法往往通過多次時(shí)間上的前向和后向運(yùn)行算法來校正評分不準(zhǔn)確性[7-9]，但簡單重復(fù)運(yùn)算會(huì)損害評分的時(shí)效性。不同于增量式模型，WHR[6]引入了選手水平動(dòng)態(tài)變化的先驗(yàn)，直接計(jì)算使比賽結(jié)果的后驗(yàn)概率最大化的選手等級分，但其存在計(jì)算復(fù)雜度高和耗時(shí)長的問題。針對圍棋對局，棋手的對局記錄通常持續(xù)數(shù)年時(shí)間，等級分模型需要處理棋手水平的時(shí)效性。除此之外，讓子棋是業(yè)余圍棋的常見對局模式，而現(xiàn)有的等級分算法無法直接處理讓子棋數(shù)據(jù)。

針對以上問題，本文提出基于B-T模型的神經(jīng)網(wǎng)絡(luò)等級分系統(tǒng)NN-Rating及其擴(kuò)展形式，用于評估圍棋選手的棋力水平。由式(2)可知，B-T模型與Sigmoid函數(shù)相似，在機(jī)器學(xué)習(xí)領(lǐng)域中，后者常作為神經(jīng)網(wǎng)絡(luò)的激活函數(shù)。對于成對比較數(shù)據(jù)，將單層神經(jīng)網(wǎng)絡(luò)中對應(yīng)于對局雙方的輸入固定為1和-1，則經(jīng)過Sigmoid激活函數(shù)后，網(wǎng)絡(luò)輸出即為輸入為1的選手預(yù)估勝率，網(wǎng)絡(luò)參數(shù)即為各選手相對實(shí)力。這種建模方法使得B-T這樣的統(tǒng)計(jì)模型能被應(yīng)用到機(jī)器學(xué)習(xí)領(lǐng)域，并能使用梯度下降方法簡單高效地迭代或增量求解模型參數(shù)，同時(shí)使得模型易于擴(kuò)展[10]。本文通過解析KGS圍棋服務(wù)器[11]上的棋譜數(shù)據(jù)獲取對局記錄并對其建模，利用神經(jīng)網(wǎng)絡(luò)小批量梯度下降法計(jì)算棋手等級分。對于時(shí)間跨度大的對局記錄，通過修改損失函數(shù)給NN-Rating模型引入一種歷史衰減優(yōu)化算法以關(guān)注當(dāng)下的棋力水平。同時(shí)，類似引入主場優(yōu)勢的B-T模型，NN-Rating模型的神經(jīng)網(wǎng)絡(luò)增加處理讓子棋的節(jié)點(diǎn)和參數(shù)，將讓子對局?jǐn)?shù)據(jù)納入等級分計(jì)算。在真實(shí)圍棋比賽數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果和分析表明，NN-Rating模型能準(zhǔn)確計(jì)算圍棋選手的等級分，獲得更高的預(yù)測準(zhǔn)確率，所得等級分與選手勝率呈正相關(guān)關(guān)系，表現(xiàn)出良好的客觀性和穩(wěn)定性。

1 相關(guān)工作

1.1 Elo等級分

Elo等級分最早應(yīng)用于國際象棋評分體系中。該方法基于B-T模型計(jì)算選手預(yù)期勝率，將勝率建模為參賽雙方的實(shí)力。根據(jù)對局結(jié)果增量式調(diào)整對局雙方等級分，調(diào)整幅度取決于預(yù)估勝率與實(shí)際對局結(jié)果之差。經(jīng)過大量對局后，所有選手等級分將穩(wěn)定到真實(shí)水平附近。Elo等級分由于其公平客觀性，在當(dāng)今棋類、拳擊和乒乓球等對抗類體育賽事中被廣泛采用，并使用更符合棋手水平分布的邏輯斯諦分布取代正態(tài)分布。雙方Elo等級分為Ri和Rj，則比較結(jié)果的概率表示為:

(3)

1.2 Glicko

Glicko系統(tǒng)首次考慮了等級分的置信度。除了計(jì)算選手評分之外，Glicko還加入了“評分誤差”(Ratings Deviation，RD)，用于衡量一個(gè)評分的不確定性(RD值越高，評分越不可信)。高RD值意味著選手并不頻繁地進(jìn)行對戰(zhàn)，或者該選手僅進(jìn)行了很少次數(shù)的對戰(zhàn)，而低RD值說明選手經(jīng)常進(jìn)行比賽。RD值的改變同時(shí)取決于游戲結(jié)果和未進(jìn)行游戲的時(shí)間長度。游戲的結(jié)果經(jīng)常會(huì)減少選手的RD值，而未進(jìn)行對戰(zhàn)的時(shí)間則經(jīng)常會(huì)增長選手的RD值。

1.3 Trueskill

Elo等級分主要適用于1vs1型賽事，在多人組隊(duì)等復(fù)雜賽事中作用受限。Trueskill算法結(jié)合了Elo方法和概率圖模型，由微軟研究院開發(fā)并應(yīng)用于Xbot Live匹配系統(tǒng)中。該算法假設(shè)選手水平符合正態(tài)分布，這個(gè)分布的方差被看作是選手水平的不確定性程度，而臨時(shí)發(fā)揮符合以水平為中心的正態(tài)分布，比賽預(yù)估結(jié)果取決于雙方臨時(shí)發(fā)揮的差值。賽后利用消息傳遞算法根據(jù)實(shí)際比賽結(jié)果對各選手水平隨機(jī)變量進(jìn)行后驗(yàn)推斷。吳霖等[11]將Trueskill算法應(yīng)用于職業(yè)圍棋選手比賽數(shù)據(jù)和仿真數(shù)據(jù)，并從客觀性、準(zhǔn)確性等方面分析了算法可行性。

1.4 WHR

WHR算法采用動(dòng)態(tài)B-T模型，引入了選手水平動(dòng)態(tài)變化的先驗(yàn)，認(rèn)為下一時(shí)間步的水平符合以上一時(shí)間步的水平為中心的正態(tài)分布，利用牛頓法優(yōu)化選手水平參數(shù)以最大化比賽結(jié)果的后驗(yàn)概率。為減少計(jì)算復(fù)雜度，WHR在每次賽后采用牛頓插值法估算新的等級分，在一定對局間隔后做全局迭代。

NN-Rating模型使用小批量梯度下降法[12]迭代運(yùn)算可以充分利用對局信息，同時(shí)通過修改損失函數(shù)使越久遠(yuǎn)的對局在優(yōu)化中權(quán)重越低，選手水平時(shí)效性增強(qiáng)。相比其他模型，NN-Rating的另一優(yōu)勢是可以直接處理讓子棋對局?jǐn)?shù)據(jù)。

2 NN-Rating等級分模型

2.1 基本模型

NN-Rating模型的基本結(jié)構(gòu)如圖1所示。

圖1 NN-Rating模型基本結(jié)構(gòu)

模型輸入維度為N，其中N為棋手?jǐn)?shù)量，棋手相對索引順序保持固定。對于每一對局記錄，通過以下方式轉(zhuǎn)化為模型輸入向量：參與對局的兩名棋手中，黑子對應(yīng)棋手輸入固定為1，白子對應(yīng)棋手輸入固定為-1，未參與此輪對局的其他棋手輸入設(shè)為0(也可設(shè)計(jì)為參與對局的兩名棋手中，黑子對應(yīng)棋手輸入固定為-1，白子對應(yīng)棋手輸入固定為1，未參與此輪對局的其他棋手輸入設(shè)為0。此時(shí)模型輸出為白子預(yù)期勝率，模型目標(biāo)應(yīng)根據(jù)白子勝負(fù)或平的情況分別設(shè)為1、0或0.5。兩種設(shè)計(jì)均不影響模型訓(xùn)練和棋手等級分的計(jì)算)。輸入數(shù)據(jù)分別為w1,w2,…,wN。輸入數(shù)據(jù)經(jīng)過以Sigmoid函數(shù)為激活函數(shù)的單層神經(jīng)網(wǎng)絡(luò)后得到1維輸出數(shù)據(jù)，由神經(jīng)網(wǎng)絡(luò)前向傳播規(guī)則，輸出o為：

(4)

式中:wb為本輪對局中執(zhí)黑方對應(yīng)參數(shù);ww為執(zhí)白方對應(yīng)參數(shù)。該形式與Bradley-Terry模型相同，模型參數(shù)即為棋手對應(yīng)等級分，模型輸出即為黑子預(yù)期勝率。

使用NN-Rating模型的優(yōu)勢是可以利用梯度下降法等優(yōu)化方法計(jì)算模型參數(shù)，并可以方便地?cái)U(kuò)展模型以處理讓子等因素。對于每一對局記錄，模型的目標(biāo)ti通過對局結(jié)果按照以下方式計(jì)算：執(zhí)黑方獲勝則目標(biāo)為1，執(zhí)白方獲勝目標(biāo)為0，平局為0.5。模型的輸出為oi。利用神經(jīng)網(wǎng)絡(luò)小批量梯度下降法優(yōu)化模型參數(shù)，最小化模型輸出與目標(biāo)之間的均方誤差損失函數(shù)，訓(xùn)練完成后獲取模型參數(shù)即得各棋手相應(yīng)的等級分。模型損失函數(shù)如下：

(5)

式中：n為對局總數(shù)。

增量式模型中選手若只與固定對手對局且二者實(shí)力相當(dāng)，在對手與其他選手對局后水平變動(dòng)的情況下，該選手評分卻保持不變。增量式模型可通過時(shí)間上前后向多次迭代運(yùn)算來解決上述問題，但這種方式對所有時(shí)間段的對局同等看待，犧牲了等級分的時(shí)效性。NN-Rating模型訓(xùn)練過程中隨機(jī)選取部分記錄進(jìn)行迭代計(jì)算，因此不存在增量式模型中對對局信息利用不充分的問題。同時(shí)NN-Rating模型可通過簡單修改損失函數(shù)的方法降低過去對局的權(quán)重，保證了等級分的時(shí)效性。

2.2 歷史衰減模型

圍棋棋手的對局記錄通常持續(xù)數(shù)年時(shí)間，在時(shí)間跨度大的情況下，棋手的水平會(huì)發(fā)生一定變化。已有的歷史衰退模型對之前已經(jīng)發(fā)生的比賽結(jié)果做一次衰退處理，降低過去比賽的權(quán)重。

本文為了使計(jì)算出的棋手等級分更符合棋手當(dāng)下的水平，使得時(shí)效性增強(qiáng)，對2.1節(jié)中的基本模型進(jìn)行擴(kuò)展。對過去的對局添加指數(shù)年度衰減系數(shù)，使距離當(dāng)前越久遠(yuǎn)的對局在計(jì)算中所占權(quán)重越小。具體衰退通過修改損失函數(shù)完成，修改后原始損失函數(shù)為：

(6)

式中：d為對局發(fā)生年份與數(shù)據(jù)集中對局發(fā)生的最后年份之間的年份差。距離對局發(fā)生的最后年份越久的對局衰減得越多，最后年份當(dāng)年的對局不衰減。歷史衰減等級分模型的輸入輸出及計(jì)算方式與基本模型相同。

2.3 讓子棋模型

讓子棋是某些棋類活動(dòng)中的特殊情況。當(dāng)對弈雙方棋力差距較大時(shí)，按照不讓子方式進(jìn)行對弈，棋力高的一方將大概率勝出；而采用讓子的方式，可以削弱雙方棋力差距從而可以進(jìn)行基本平衡的對局。類似球類賽事中的主場優(yōu)勢，包含讓子因素的B-T模型中黑方勝率如下：

(7)

式中：λ為要學(xué)習(xí)的讓子參數(shù);h為讓子數(shù)。

已有的等級分算法中沒有可以直接處理讓子棋的。通過在2.1節(jié)中的基本模型中添加一個(gè)專門處理讓子因素的節(jié)點(diǎn)和該節(jié)點(diǎn)對應(yīng)的參數(shù)，本文模型可以直接處理不同讓子數(shù)的讓子棋而不需要將讓子數(shù)轉(zhuǎn)化為相應(yīng)的Elo分值。擴(kuò)展的可處理讓子棋的NN-Rating模型輸入維度為N+1，其中N為棋手?jǐn)?shù)量，前N維輸入與基本模型中相同，最后1維輸入為讓子數(shù)。輸入數(shù)據(jù)參數(shù)分別為w1,w2,…,wN,wλ，其中前N維參數(shù)分別代表各棋手等級分，最后1維參數(shù)代表讓子參數(shù)λ。在計(jì)算棋手等級分參數(shù)的訓(xùn)練過程中，讓子參數(shù)也通過梯度下降法求解。

2.4 置信度

棋手參與對局?jǐn)?shù)越多，對其等級分的計(jì)算就越接近其真實(shí)水平，所以本文引入一種啟發(fā)式方法計(jì)算等級分的置信度，同時(shí)不影響梯度下降法計(jì)算棋手等級分。gi為選手i參與的對局?jǐn)?shù)，則選手i等級分的置信度表示為：

(8)

式中：certaintyi為棋手i等級分的置信度;G為一個(gè)常數(shù)，表示對棋手i等級分完全置信時(shí)他需要參與的對局?jǐn)?shù)，文中取值為10。置信度可作為棋手等級分的輔助指標(biāo)。置信度越高，計(jì)算出的棋手等級分越接近其真實(shí)棋力。

3 實(shí) 驗(yàn)

3.1 數(shù)據(jù)集

KGS圍棋服務(wù)器[13]是世界上最大的圍棋服務(wù)器之一，包含從2001年至2018年的對局記錄。通過u-go.net網(wǎng)站[14]可獲取來自該服務(wù)器且經(jīng)過初步篩選和分類的對局的SGF棋譜文件。本文采用頂級業(yè)余棋手的對局記錄數(shù)據(jù)集，對弈雙方中一方為業(yè)余7d及以上或雙方均為業(yè)余6d。WHR算法選取了2000-11-07至2005-05-20的對局記錄作為訓(xùn)練集，2005-05-21至2007-10-01的對局記錄作為測試集，為保證與對比算法中數(shù)據(jù)集維度保持同等條件，同時(shí)避免對局記錄受圍棋AI的影響，本文選擇2010年—2014年的高水平業(yè)余棋手對局?jǐn)?shù)據(jù)作為訓(xùn)練集，2015年—2016年的對局?jǐn)?shù)據(jù)作為測試集。通過解析SGF文件并去除無效對局(沒有對局結(jié)果)，最終非讓子棋訓(xùn)練集包括52 255條對局記錄，3 591名棋手，測試集包括11 819條對局記錄，其中測試集中的4 269條記錄對弈雙方均已在訓(xùn)練集出現(xiàn)，可用于預(yù)測準(zhǔn)確率評估。讓子棋訓(xùn)練集包括22 498條對局記錄，4 725名棋手，測試集包括8 415條對局記錄，其中測試集中的1 689條記錄對弈雙方均已在訓(xùn)練集出現(xiàn)，可用于預(yù)測準(zhǔn)確率評估。

3.2 實(shí)驗(yàn)結(jié)果及分析

3.2.1收斂性

通過訓(xùn)練集上的迭代計(jì)算驗(yàn)證算法的收斂性。每輪迭代中采取小批量隨機(jī)梯度下降法最小化模型的損失函數(shù)。學(xué)習(xí)率取值為0.01，批大小取值為512，指數(shù)衰減系數(shù)γ取值為0.95，非讓子棋數(shù)據(jù)集迭代過程中模型的均方誤差變化如圖2所示。

圖2 訓(xùn)練誤差的收斂性

可以看出，經(jīng)過50輪迭代后，模型誤差趨于穩(wěn)定。最終計(jì)算出的排名前20的棋手等級分及置信度如表1所示。

表1 排名前20的棋手的等級分和置信度

3.2.2客觀性

勝率是選手實(shí)力的客觀體現(xiàn)和衡量標(biāo)準(zhǔn)之一，利用棋手勝率與NN-Rating模型計(jì)算出的等級分之間的關(guān)系如圖3所示。

圖3 勝率和等級分的關(guān)系

可以看出，勝率與等級分呈正相關(guān)關(guān)系，勝率高的棋手對應(yīng)的等級分也越高，表明模型具有良好的客觀性。

3.2.3準(zhǔn)確性

(1) 分先對局記錄。等級分算法的對比實(shí)驗(yàn)通過衡量各算法在測試集上的預(yù)測準(zhǔn)確率完成，其中算法在測試集對局記錄上預(yù)測出的勝者與對局實(shí)際結(jié)果一致則視為預(yù)測正確。各算法預(yù)測準(zhǔn)確率如表2所示。

表2 不同算法在非讓子棋數(shù)據(jù)集上的預(yù)測準(zhǔn)確率

Elo算法初始等級分設(shè)為1 300分，參數(shù)k取值為16。Trueskill采取微軟研究院開源算法的默認(rèn)設(shè)置，初始等級分為25。吳霖等[11]未修改原始Trueskill算法，而是使用隨機(jī)輸入多次迭代運(yùn)算來平滑結(jié)果，但損失了等級分計(jì)算的時(shí)效性，且在小數(shù)據(jù)集上的效果只略優(yōu)于Elo算法，在此分析的基礎(chǔ)上，本文選擇與原始算法作對比。利用NN-Rating模型計(jì)算出的棋手等級分在測試集上預(yù)測準(zhǔn)確率更高，表明該算法計(jì)算出的等級分更符合棋手的真實(shí)棋力。

(2) 讓子對局記錄。Trueskill、WHR等算法無法直接處理讓子棋，因此使用NN-Rating方法在讓子棋數(shù)據(jù)上進(jìn)行測試，其準(zhǔn)確率達(dá)到60.628%。

4 結(jié) 語

本文構(gòu)建NN-Rating神經(jīng)網(wǎng)絡(luò)等級分模型，為等級分算法在大規(guī)模數(shù)據(jù)上的應(yīng)用提供參考。本文的貢獻(xiàn)如下：1) 基于統(tǒng)計(jì)學(xué)的Bradley-Terry成對數(shù)據(jù)比較模型和人工神經(jīng)網(wǎng)絡(luò)設(shè)計(jì)NN-Rating等級分模型，利用小批量梯度下降方法迭代求解模型參數(shù)，消除增量式模型中對局信息利用不充分對等級分計(jì)算準(zhǔn)確性的影響；2) 通過修改損失函數(shù)擴(kuò)展NN-Rating模型為歷史衰減模型，使得距今越久遠(yuǎn)的對局記錄在模型訓(xùn)練過程中權(quán)重越小，因而計(jì)算出的等級分時(shí)效性更強(qiáng)，更符合選手當(dāng)下的水平；3) 針對圍棋讓子棋特點(diǎn)，借鑒主場優(yōu)勢特性擴(kuò)展NN-Rating基本模型為讓子棋模型，通過引入讓子數(shù)節(jié)點(diǎn)和對應(yīng)的讓子參數(shù)，讓子棋模型可以直接處理圍棋對局中的讓子棋，而已有的等級分算法中沒有可以直接處理讓子棋的。在真實(shí)賽事數(shù)據(jù)集上的實(shí)驗(yàn)表明模型具有良好的客觀性和準(zhǔn)確性。下一步工作除了考慮對局結(jié)果外，還將利用圍棋AI分析棋手對局過程中的表現(xiàn)，對對局結(jié)果和棋手中間勝率建模，有助于提升等級分模型的準(zhǔn)確性。