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

趙 睿 趙銀亮

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

0 引 言

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

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

(1)

(2)

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

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

1 相關(guān)工作

1.1 Elo等級(jí)分

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

(3)

1.2 Glicko

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

1.3 Trueskill

Elo等級(jí)分主要適用于1vs1型賽事，在多人組隊(duì)等復(fù)雜賽事中作用受限。Trueskill算法結(jié)合了Elo方法和概率圖模型，由微軟研究院開(kāi)發(fā)并應(yīng)用于Xbot Live匹配系統(tǒng)中。該算法假設(shè)選手水平符合正態(tài)分布，這個(gè)分布的方差被看作是選手水平的不確定性程度，而臨時(shí)發(fā)揮符合以水平為中心的正態(tài)分布，比賽預(yù)估結(jié)果取決于雙方臨時(shí)發(fā)揮的差值。賽后利用消息傳遞算法根據(jù)實(shí)際比賽結(jié)果對(duì)各選手水平隨機(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在每次賽后采用牛頓插值法估算新的等級(jí)分，在一定對(duì)局間隔后做全局迭代。

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

2 NN-Rating等級(jí)分模型

2.1 基本模型

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

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

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

(4)

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

使用NN-Rating模型的優(yōu)勢(shì)是可以利用梯度下降法等優(yōu)化方法計(jì)算模型參數(shù)，并可以方便地?cái)U(kuò)展模型以處理讓子等因素。對(duì)于每一對(duì)局記錄，模型的目標(biāo)ti通過(guò)對(duì)局結(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)的等級(jí)分。模型損失函數(shù)如下：

(5)

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

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

2.2 歷史衰減模型

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

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

(6)

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

2.3 讓子棋模型

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

(7)

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

已有的等級(jí)分算法中沒(méi)有可以直接處理讓子棋的。通過(guò)在2.1節(jié)中的基本模型中添加一個(gè)專門(mén)處理讓子因素的節(jié)點(diǎn)和該節(jié)點(diǎn)對(duì)應(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ù)分別代表各棋手等級(jí)分，最后1維參數(shù)代表讓子參數(shù)λ。在計(jì)算棋手等級(jí)分參數(shù)的訓(xùn)練過(guò)程中，讓子參數(shù)也通過(guò)梯度下降法求解。

2.4 置信度

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

(8)

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

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

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

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

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

3.2.1收斂性

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

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

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

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

3.2.2客觀性

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

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

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

3.2.3準(zhǔn)確性

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

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

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

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

4 結(jié) 語(yǔ)

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