基于賽制組織的遺傳變異棋局樣例生成算法

田 欣，姬 波,2，盧紅星,2，柳宏川,2，尤惠彬

1(鄭州大學 信息工程學院,鄭州 450001)

2(鄭州大學 產業技術研究所第四代工業研究所,鄭州 450001)

1 引 言

計算機棋類游戲被認為是人工智能領域的“果蠅”，對其的深入研究有助于對機器智能中很多基本問題的理解.作為計算機棋類游戲的3個里程碑，chinook，深藍和alphazero分別在西洋跳棋，國際象棋和圍棋比賽中取得了戰勝人類選手的成績，大大鼓舞了投身于這個領域的研究人員[1].

1999年Kumar Chellapilla等人就提出在不依賴專家知識庫的條件下，設計完全連接的前饋神經網絡，采用種群中互相博弈和遺傳變異的知識傳遞方式，使用多層前饋神經網絡評估棋盤位置，極小極大搜索策略進行搜索，以每一場比賽的最終結果(即贏、輸或平局)來完成神經網絡的競爭生存，最終篩選出種群中的最優選手作為優勝者，該選手能夠擊敗兩名專家級選手，并與一名高手打成平局[2].隨后Su Z采用遺傳算法解決跳棋博弈中的評價問題，在計算機上模擬兩個“玩家”之間的交替演化過程，博弈的輸方依次向獲勝方進行參數調整和進化.有效地解決了傳統搜索算法由于搜索程度的加深而帶來的計算量大幅增加的問題[3].為增加搜索樹的深度并減少運行時間，2014年Neto H C等人提出一種高效無監督進化學習系統，利用進化計算的方法，在選擇棋步時，保持深度前瞻搜索，使用搜索預測值來選擇與當前棋盤狀態相對應的最佳移動，神經網絡的權值通過一個評價函數進行更新，該評價函數通過時域差分方法自動調整，使棋盤狀態的選擇過程自動化[4].2016年David O E等人針對國際象棋程序缺乏學習能力的現象，提出一種基于深度神經網絡的端到端的國際象棋學習方法.在沒有任何先驗知識的情況下，依賴于數百萬個國際象棋游戲中黑白棋贏的局面，使用無監督訓練從一個給定的位置提取高級特征，而有監督訓練學習則比較兩個國際象棋位置并選擇更有利的一個.實驗表明，由此產生的神經網絡(DeepChess)與最先進的國際象棋程序不相上下[5].緊接著AlphaGo誕生，針對不可窮舉的大型游戲，為減少搜索空間，使用策略網絡選擇移動，價值網絡評估棋盤位置.這些神經網絡采用監督學習針對人類專家游戲中隨機抽樣的動作進行訓練，預測人類專家動作，利用強化學習進行自對弈.并提出一種將蒙特卡羅模擬與價值策略網絡相結合的搜索算法，通過這種搜索算法，AlphaGo達到了很高的勝率[6].然而，專家數據集通常是昂貴的、不可靠的或根本不可用的.因此AlphaGo Zero出現，提出一種完全基于強化學習的算法，使用自對弈，從隨機游戲開始，沒有任何監督或人類數據，訓練循環中加入了前瞻搜索，只使用棋盤上的黑白棋子作為輸入特征，在搜索時只依賴于一個單一的神經網絡來評估位置和樣本移動，而不執行任何蒙特卡羅rollout，提高了學習的速度、精度和穩定性[7].2018年將這一算法同時應用到國際象棋，shogi和圍棋中，對這3款游戲使用相同的算法和網絡架構.從隨機游戲開始，除了游戲規則外沒有任何領域知識，用深度神經網絡、通用強化學習算法和通用樹搜索算法取代了傳統游戲程序中使用的手工知識和特定領域的擴展，完全從自對弈中學習移動概率和價值估計.研究結果表明，一種通用的強化學習算法可以在沒有特定領域的人類知識或數據的情況下學習[8].2017年也曾嘗試通過僅從人類游戲的數據庫中學習來進化一種最先進的評估功能，并取得了成功，這是通過監督和非監督學習相結合實現的，在監督學習階段，選擇大師級游戲數據庫中的位置和在這個位置上的獲勝移動，進化模仿人類大師的行為，而在非監督學習階段，這些進化的生物通過共同進化的方式得到進一步的改進.結果表明，進化的程序比兩屆世界計算機國際象棋冠軍表現更好[9].2018年一種新的監督學習方法被提出，通過訓練人工神經網絡評估棋局，針對大約300萬個由高水平棋手進行的不同棋局，使用Stockfish的評估功能對它們打分，通過訓練不同的人工神經網絡體系結構來理解國際象棋的位置，該網絡根據深度為1的一組候選移動對可能的未來棋盤狀態進行評分，而無需進一步探究.從而找到一個精確的國際象棋位置的評估，更側重于發現國際象棋中固有的模式識別知識，而無需深入研究一大堆未來的棋盤狀態[10].

目前棋類智能的研究主要集中在優化搜索算法、評價函數以及提高學習能力3個方面，旨在找到每一步移動的最佳動作，同時通過提高學習能力，得到一個強大的人工智能選手[11].即使目前的人工智能選手已經可以戰勝人類選手，但在棋類“果蠅”身上依然存在很多未能透徹研究的問題.有限的學習樣例很大程度可以決定人工智能選手的能力，但對于學習樣例的具體產生方式卻未能引起足夠的重視.

因此，本文提出一種學習樣例的生成算法，將體育賽制(混合賽制、循環賽制、淘汰賽制)和遺傳算法結合，借用成熟公正的體育賽制高效的組織形式為人工智能選手匹配對手，結合遺傳算法自組織、自適應和自學習的特性，逐步進化選手，將優勝者之間的對局做為學習樣例.然后，以西洋跳棋為實例進行實驗，并通過定量分析指標建立學習樣例生成方式的評價體系，評價基于混合賽制、循環賽制和淘汰賽制3種不同體育賽制生成的學習樣例的優劣，并探討在行棋局數相同的情況下，最適合西洋跳棋的賽制組織形式.實驗表明，本文提出的樣例生成方式可以有效產生樣例，且在樣本綜合規模指標T下，3種賽制中基于混合賽制和循環賽制產生的學習樣例具有更高的質量，同時基于樣例訓練的選手能力對比表明，循環賽制最適合于西洋跳棋游戲的樣例產生.

2 研究背景

2.1 遺傳算法

遺傳算法(Genetic Algorithm)是一類借鑒生物界的進化規律(適者生存，優勝劣汰遺傳機制)演化而來的隨機化搜索方法.它最初是由1975年美國的J.Holland教授提出，借鑒進化生物學中的一些現象而發展起來的，通過運用生物遺傳與進化的特點，將要解決的問題模擬成一個生物進化過程，將一些待優化的解決方案作為群體.每一個群體通過繁殖、變異、競爭，實現優勝劣汰，逐步得到問題的解[12].

遺傳算法運用遺傳算子來進行遺傳操作，包括優選適應性強的個體的“選擇”，個體間交換基因產生新個體的“交叉”，個體間基因突變而產生新個體的“變異”.

選擇：選擇過程體現了生物進化過程中“適者生存，優勝劣汰”的思想.根據個體的適應度，按照一定的規則，從第n代群體中選擇出一些具有優良性狀的個體遺傳到(n+1)代群體.在這一選擇過程中，個體適應度越大，則被選擇到下一代的機會越大.某個體i的適應度為fi，種群大小為NP，則i被選擇的概率如公式(1)所示：

(1)

交叉：交叉算子模仿自然界有性繁殖的基因重組過程，其作用在于將已有的優良基因遺傳給下一代個體，并生成包含更復雜基因的新個體.最常用的交叉算子為單點交叉.即在個體串中隨機設定一個交叉點，實行交叉時，該點前或后的兩個個體的部分結構進行互換，并生成兩個新個體[13].

(2)

隨著應用領域的擴展，遺傳算法的研究出現了引人注目的新動向，即基于遺傳算法的機器學習，這一新的研究課題把遺傳算法從歷來離散的搜索空間的優化搜索算法擴展到具有獨特規則生成功能的嶄新的機器學習算法.這一新的學習機制對于解決人工智能中知識獲取和知識優化精煉的瓶頸難題帶來了希望.目前遺傳算法已經在人工智能領域最具有挑戰性的計算機棋類游戲中得到了廣泛的應用.Esch,J使用遺傳算法，將神經網絡模擬為玩家，玩家通過對標準參數和權值進行隨機變化的過程，互相競爭生存和產生后代，幸存的玩家從游戲中提取信息并提高他們的能力.該程序達到了可以通過棋子的位置和位置值以及神經網絡來評估棋盤位置的目的[14].Vazquezfernandez E等人針對國際象棋程序提出，將進化算法種群中的每一個個體都代表一個具有特定權重的評價函數的虛擬參與者，且算法中所執行的動作與數據庫中某個特定游戲中人類象棋大師所執行的動作相等.結果表明，該方法得到的權值與國際象棋理論得到的權值相近[15].之后，遺傳算法被用到棋類游戲的多個方面，用于優化得到更好的參數.2014年David O E等人使用遺傳算法來進化國際象棋程序的評估函數和選擇搜索機制參數.通過模仿人類大師的行為，以共同進化的方式得到進一步的改進，最終得到了與頂級錦標賽相似的性能[16].Hootan Dehghani在2017年提出一種基于遺傳算法的棋局樹空間約簡方法.將遺傳算法應用于減少國際象棋博弈樹的搜索空間，與Min-Max算法相比，在準確性和速度上具有更好的性能[17].

2.2 體育賽制

體育賽制是目前一種較為成熟公正的賽制組織形式，多用于在競賽中對比賽規則和參賽選手的具體安排，組織參賽選手合理高效的進行比賽.合理設置賽制，可以盡可能保證本次比賽的順利進行，同時縮短比賽時間，在一定程度上還可以保證每個參賽選手的公平.賽制包括多種競賽形式，主要有循環賽制、淘汰賽制和混合賽制.

2.2.1 循環賽制

在有多個隊參加比賽時，每一隊要與其他各隊至少進行一次(單循環)或多次(多循環)比賽，對每輪比賽勝負分別賦予不同的分值，最后以累計分值之和決定最終名次.循環制一般適用于參賽隊數不多，有足夠競賽時間的比賽，而且由于參加競賽的各隊都有相遇比賽的機會，是一種比較公平合理的比賽制度.當參賽隊數為n，進行單循環賽時，整個賽事總比賽輪次N如公式(3)所示：

(3)

2.2.2 淘汰賽制

淘汰賽制是指逐步淘汰失敗者，使勝者按預定比賽表進入下一輪比賽.淘汰賽制主要分為兩大類，第一類是單淘汰制，即比賽過程中選手只要失敗一次就被淘汰，直到決出最后的冠軍；第二類是雙敗復活淘汰制，將選手分為勝者組和敗者組，選手負一場后并未被淘汰，只是跌入敗者組，每一輪敗者組的比賽又分為兩個階段.第一個階段，由當前敗者組中的幸存者相互對陣，負者被淘汰，勝者進入第二個階段；第二個階段，由第一階段中敗者組的勝者對陣剛剛在本輪由勝者組中淘汰下來的選手，勝者進入下一輪中的敗者組，負者被淘汰[18].淘汰賽制適用于有大量參賽者的比賽.

當淘汰賽制的參賽隊數A正好為2n時，整個賽事總比賽輪次N如公式(4)所示；否則，整個賽事總比賽輪次是較大的一個以2為底的冪的指數.

(4)

2.2.3 混合賽制

混合賽制就是將循環賽與淘汰賽在比賽中先后使用，最后決出比賽名次，完成比賽工作.混合賽一般分兩個階段進行，第一階段常采用分組循環賽，第二階段常采用淘汰賽[19].混合賽綜合了循環賽和淘汰賽的優點，彌補了兩者的不足，既有利于參賽者相互交流，又最大限度地減少比賽勝負的偶然性.

3 基于賽制組織形式的遺傳變異樣例生成算法

綜合遺傳算法自組織、自適應和自學習的特性以及體育賽制成熟公正的賽制組織形式，本文提出了一種基于賽制組織形式的遺傳變異學習樣例生成算法，該算法將遺傳算法和體育賽制相結合，借助體育賽制中循環賽制、淘汰賽制和混合賽制3種不同的賽制組織形式，為人工智能選手匹配對手，并使用遺傳變異方法使選手逐代進化，最后將優勝者之間的對局做為學習樣例.基于賽制組織形式的遺傳變異樣例生成算法整體上分為5個步驟：

1)借助人工經驗確定初始種群：在項目組已有實驗結果的基礎上，得到一個較好的神經網絡，對該神經網絡的參數設置一個浮動值，隨機得到多個神經網絡，每一個神經網絡視為一個選手，初始得到多個對弈選手；

2)借助體育賽制的組織形式，為每個選手匹配對手：所有選手根據循環賽制、淘汰賽制或混合賽制的組織形式，為自己匹配相應的對弈選手，根據賽制的不同，每個選手將與不同的對手進行一次或兩次對弈；

3)選手對弈：選手與根據賽制所匹配的對手按照游戲規則進行對弈；

4)得到學習樣例：在對弈結束之后，將獲勝局中獲勝優勢較大的棋局信息作為學習樣例；

5)進化選手：一輪比賽包含多場選手之間的對弈，每一場選手對弈結束后，根據該場對弈結果的輸贏，保留獲勝優勢較大的選手，淘汰劣勢選手.本輪比賽結束之后，所有保留下來的選手作為本次進化的父代，所有父代之間交叉變異產生子代，得到下一輪比賽的選手.

3.1 西洋跳棋簡介

3.1.1 西洋跳棋游戲規則

西洋跳棋是一種在8×8棋盤上進行的技巧游戲，以吃掉或堵住對方所有棋子去路為勝利.棋盤上有黑白兩種顏色的方塊，黑色方塊不能放置任何棋子，白色為所有棋子行棋方塊，棋盤的左上角為黑色方塊，且相鄰的方塊不能為同種顏色[20].有兩名玩家，分別被稱為“紅方”和“藍方”，紅藍雙方各有12個相同顏色的棋子，分別占據棋盤兩邊(上方為“藍方”，下方為“紅方”)，如圖1所示.

圖1 西洋跳棋64格棋盤

游戲規則規定“紅方”為先手，雙方輪流下棋.“未成王”的棋子只能向對方左上角或右上角且無人占據的格子斜走一格.當棋子到達對方底線時則“成王”，王棋可向4個斜線方向中任意一個方向移動.但棋子在“成王”后不能馬上繼續吃棋，須等下一回合才可移動.在行棋過程中，執行吃子優先的規則，吃子時，敵方的棋子必須是在己方棋子的左上角或右上角的格子，而且該敵方棋子的對應的左上角或右上角必須沒有棋子.若一個棋子可以吃棋，那么它必須吃而不可以走其他棋子.若出現連吃情況，則連吃的優先級高于吃子，且繼續吃直到無法再吃為止.

出現下述情況則判定為該局游戲結束：

1)任意一方玩家的棋子被全部吃完，則判定留在棋局上的玩家為獲勝方.

2)棋局上留有雙方棋子，若一方所有棋子被堵住無法繼續移動，則判定另一方為獲勝方；若留在棋盤上的雙方所有棋子均被堵住而無法繼續移動，則判定雙方平局.

3)移動步數超過最大限度且仍未分出勝負，則判定雙方平局.

3.1.2 棋盤表示

棋子的強度代表著該棋子的水平.根據棋類游戲的規則，每一個棋子都有其獨特的移動方式，這意味著它在不同情況下的作用和重要程度是不同的.不同棋子的共同取值方式由數組元素{-K，-1，0，+1，+K}表示，以正負號區分玩家和對手.其中：-K表示藍王棋、-1表示普通藍棋、0表示空格(無棋子)、+1表示普通紅棋、+K表示紅王棋.本文K值設定為2.0.當普通棋子變成王棋后，棋子圖像由圓形變為標有“王”字樣的圓形用于區分普通棋子與王棋.

3.2 確定初始種群

本文將一個完整的BP神經網絡定義為一個人工智能選手，每一個選手又視為遺傳算法中的一個染色體，采用十進制編碼方式對每一個染色體進行編碼.該BP神經網絡以西洋跳棋的32個棋盤狀態作為輸入信息，且有兩個隱藏層信息，隱藏層結點個數分別為5和3，一個輸出層信息，結構如圖2所示[21].因此，一個神經網絡有187個權重和閾值參數，即每一個選手信息由187個神經網絡參數組成.

圖2 BP神經網絡結構

根據目前項目組的實驗結果，已通過自對弈訓練出一個優秀選手，該選手同樣包含187個神經網絡參數.本文借助人工經驗來確定初始種群，在該選手的基礎上，對其參數設置浮動值，得到多個人工智能選手.由于所有選手都基于初始的優秀選手得到，因此相對于隨機生成的初始選手，該方法得到的每一個選手的能力雖然存在差異，但分布較為均勻.

由公式(5)通過對初始優秀選手的每一個參數浮動得到多個不同的人工智能選手.其中，Nw是神經網絡中權重和閾值的數量(此處為187)，fd是浮動參數值且fd∈(0,1)，di是神經網絡的一個參數值，r是區間(0,1)內的隨機值，y是浮動后得到的相對應的神經網絡的一個參數.

(5)

3.3 借助賽制匹配對手

借助體育賽制成熟公正的組織形式，為每一個選手匹配其對手，以達到選手之間對弈的高效性.分別采用3種不同的體育賽制，即循環賽制、淘汰賽制和混合賽制，為選手匹配不同的對手.

3.3.1 采用循環賽制

當選手較多時，采用分組循環賽制.對初始選手進行分組，每組內選手的匹配方式采用′U′型逆時針旋轉法，將所有選手逆時針旋轉排列.為使選手之間盡量公平，先進行一次′U′型交叉匹配，然后之后的每一輪都將進行′U′型平行匹配.采用′U′型逆時針旋轉法編排方式，在每一輪選手匹配結束后，所有選手將依次逆時針旋轉一位，使每個選手都盡量能和組內的其它選手比賽.′U′型逆時針旋轉法的編排方法如圖3所示，以每組內4個選手為例:

圖3 ′U′型逆時針旋轉法

需進行5輪比賽，每一輪匹配的雙方選手如表1所示.

表1 循環賽對局編排表

采用′U′型逆時針旋轉法，可以減少選手比賽輪次，且使每個選手盡可能與組內的其他選手都進行一次比賽，并盡量都能擔任先手和后手的角色，避免了因先后手的區別對對弈結果產生的影響.

3.3.2 采用淘汰賽制

為避免匹配的雙方選手之間的偶然性以及選手的意外失誤，采用復活淘汰賽制，選手只有兩次都失敗才被淘汰，這種賽制可以給選手多一次的機會.每個選手依次和相鄰的下一個選手匹配為對手，選手分為勝者組和敗者組，選手負一場后，并未被淘汰，還能再進行一次比賽，選手只有兩次都失敗才被淘汰，這種賽制可以給選手多一次的機會.8個選手的淘汰賽制的具體對局編排表如圖4所示.

圖4 復活淘汰賽對局編排表

3.3.3 采用混合賽制

所有選手先進行組內循環賽，然后將組內循環賽的獲勝選手作為淘汰賽的初始選手，進行復活淘汰賽.混合賽中的組內循環賽和復活淘汰賽采用和以上相同的方式.

3.4 選手對弈

所有選手根據賽制的組織形式，匹配到自己的對手，然后雙方進行對弈，在對弈過程中，對于每一個位置都向下執行一層搜索，確定下一步走子，使用BP神經網絡來評估棋盤分值，紅方選擇下一步移動的最大值，藍方選擇最小值.

在西洋跳棋中，棋盤分值的計算均以當前棋盤的32個有效位置作為輸入，權重和閾值的初始值即為該選手的參數值，以BP神經網絡輸出的唯一標量值作為當前棋局狀態的分值.BP神經網絡仍采用圖2所示的結構，每個節點的凈輸入值Si經過sigmod激活函數f(x)變換后得到該節點的輸出.當前棋盤狀態的估值Vo的計算如公式(6)所示：

(6)

其中，H1j為第1層隱藏層每個節點的值，H2l為第2層隱藏層每個節點的值，Wij、Wjl、Wlo分別為輸入層和第1層隱藏層、第1層隱藏層和第2層隱藏層、第2層隱藏層和輸出層之間的權重，bj、bl和bo分別為第1層隱藏層、第2層隱藏層和輸出層的閾值.

3.5 生成學習樣例

在每一輪對弈結束后，有3種對局結果，分別為輸、贏和平局.本文僅在所有的獲勝棋局中，挑選在m(m很小)步之內就獲勝的棋局和獲勝n(n很大)子的棋局作為學習樣例.之所以沒有將所有的獲勝棋局作為學習樣例，一方面是排除那些“僥幸獲勝”的棋局棋局，另一方面，我們認為通過訓練獲勝局優勢較大的棋局局面得到的選手相對于其他棋局局面來說能力可能更強.

雙方對弈過程中，進入下一輪比賽的獲勝選手，如果它在下一局面臨的對手的走子方式不一樣，它的走子方式也不一樣，即對局局面不一樣，這在一定程度上增加了學習樣例的多樣性.

3.6 進化選手

由于體育賽制選手編排的特點，每一輪比賽中包含多場選手之間的對弈，每一場選手對弈的結果有輸、贏或平局，而我們僅針對在獲勝選手中，選取在m(m很小)步之內就獲勝的選手和本場對弈結束后獲勝n(n很大)子的選手作為本次進化的父代.

一輪比賽結束后，將所有父代樣本隨機配對，然后在滿足交叉概率Pc內隨機選擇一對父代個體，將這兩個父代個體的部分結構加以替換重組而生成新個體.本文采用單點交叉方式，在個體串中隨機設定一個交叉點，實行交叉時，該點前或后的兩個個體的部分結構進行互換，并生成兩個新個體.

為使遺傳算法具有局部的隨機搜索能力，且維持群體多樣性，防止出現未成熟收斂的現象，在交叉操作后，對群體進行變異操作.對群中所有個體以事先設定的變異概率Pm判斷是否進行變異，對進行變異的個體隨機選擇變異位，對該位基因值用隨機生成的[-1,1]中的值來替換，從而形成新的個體.

進化完成后，所有的父代選手和子代選手作為下一輪對弈的初始選手.

3.7 算法復雜度

N表示算法的最大迭代次數，g表示循環賽的輪次，r表示淘汰賽進行的輪次，p表示進化種群數量.該算法的時間復雜度主要分為兩部分：1)計算3種賽制的時間復雜度.循環賽制的時間復雜度為O(g)，淘汰賽制的時間復雜度為O(r)，混合賽制的時間復雜度為O(g+r)；2)計算選手進化的時間復雜度，該過程時間復雜度為O(p).當迭代N次時，基于3種不同賽制的算法的總時間復雜度分別為O(N(g+p))，O(N(r+p))，O(N((g+r)+p)).

基于賽制組織形式的遺傳變異樣例生成算法的基本步驟如下：

輸入：BP神經網絡的所有參數值，為一個初始選手；

輸出：一定條件下獲勝者的對局，即學習樣例；

初始化：以一個BP神經網絡代表一個選手，對該選手參數值浮動得到200個初始種群選手；

1.while(i < N)do

2. if(循環賽)then

3. for(i=0;i

4. 分組，組內采用“U”型逆時針旋轉法匹配對手并對弈；

5. end for

6. else(淘汰賽)then

7. for(i=0;i<=r;i++)do

與相鄰選手互為對手，采用復活淘汰賽方式對弈；

8. end for

9. else(混合賽)then

10. 先組內循環賽，循環賽獲勝選手進入淘汰賽；

11. end if

12. if(紅方m步內獲勝或勝n子)then

13. 保存紅方對局作為學習樣例；

14. end if

15. if(紅方或藍方m步內獲勝或獲勝n子)then

16. 保存勝方選手至本代進化種群；

17. end if

18. for(i=0;i

19. 交叉，變異，得到下一代選手；

20. end for

21.end while

4 實驗結果與分析

本文的算法實驗平臺是由項目組歷時10個月自行開發的，該平臺主要功能是實現西洋跳棋自對弈棋局學習樣例生成器系統，主要包括界面初始化、行棋、學習樣例生成和訓練紅方選手4大功能.

4.1 樣例生成的可行性

實驗借助人工經驗，在目前項目組已有的實驗結果基礎上，通過對其優秀選手的參數值浮動，確定200個初始種群，并基于循環賽制、淘汰賽制和混合賽制3種不同的賽制為選手匹配對手，根據對弈結果(輸、贏和平局)，僅選擇在所有獲勝棋局中，120步之內就獲勝的棋局和獲勝棋子數超過8子的棋局作為學習樣例.在不同迭代次數下得到的學習樣例如表2所示.

表2 3種不同的學習樣例(M表示混合賽制、R表示循環賽制、K表示淘汰賽制)

由表2可以看出：

1)隨著迭代次數的增加，基于混合賽制、循環賽制和淘汰賽制生成的學習樣例的個數都逐漸增加，這說明本樣例生成算法是可行的；

2)當迭代相同次數時，單位時間內基于淘汰賽制生成樣例的效率最高，其次是循環賽制，最后是混合賽制，這與3.7節3種賽制的算法時間復雜度相吻合，表明該算法是正確的，可以有效產生樣例.

4.2 樣例質量

本文采用項目組提出的樣例規模綜合指標T，對該算法產生的學習樣例進行定量分析，評價學習樣例的質量.與學習樣例直接相關的兩個定量指標分別是：樣例總個數s和樣例重復率x=r/s.其中，r為重復樣例個數，樣例規模綜合指標T如公式(7)所示：

T=α*y-(1-α)*x

(7)

s∈[0,+∞]；x=r/s；y=tanh(logs)；α為平衡因子且α∈[0,1]；T的值域范圍為[0,1].當通過學習樣例訓練得到的選手勝率變化規律和T值的變化規律一致時，表明該學習樣例質量較高.

通過對學習樣例訓練得到不同的選手，將這些選手作為紅方，與隨機選手對弈.實驗結果如表3-表5所示，并根據表中數據繪制樣例規模綜合指標T(a=0.8)與勝率變化組合圖，如圖5所示.其中橫坐標表示迭代次數，左側數值表示T值，右側數值表示通過學習樣例訓練得到的選手的勝率.

表3 基于混合賽制實驗結果

表4 基于循環賽制實驗結果

表5 基于淘汰賽制實驗結果

通過對圖5分析，可以發現：

圖5 T值與紅方勝率變化圖

1)基于混合賽制和基于循環賽制生成的學習樣例的規模綜合指標T的變化規律和紅方獲勝概率的變化規律相同，均符合樣例規模綜合指標T的特點，表明基于這兩種賽制得到的學習樣例具有較高的質量；

2)基于淘汰賽制得到的學習樣例的T值變化規律，雖然在迭代3000次和5000次時，與紅方獲勝概率的變化規律相同，但是當迭代次數增大時，T值和紅方訓練后的勝率變化規律變得不一致，因此基于淘汰賽制得到的學習樣例質量具有不穩定性.

4.3 樣例訓練效果

為了進一步分析基于混合賽制、循環賽制和淘汰賽制生成的學習樣例的優劣，本文采用BP神經網絡對學習樣例進行訓練，以棋盤的32個狀態作為輸入值，當前棋盤狀態的分值作為目標值，通過兩層BP神經網絡(第1個隱藏層結點個數為5，第2個隱藏層結點個數為3)的逆向反饋調整權值和閾值，最后得到一個神經網絡模型，該模型即為根據學習樣例訓練得到的一個選手.

將基于3種賽制生成的學習樣例訓練得到的選手分別作為紅藍方，雙方對弈多次，將多次對弈結果取均值，對應的結果如圖6所示.

圖6 選手對弈結果

圖中橫坐標表示迭代次數，縱坐標表示雙方對弈結果.從圖 6可以看出：

1)在迭代次數相同時，盡管雙方平局居多，但不論基于循環賽制學習樣例訓練得到的選手是作為紅方選手還是藍方選手進行對弈，其結果相對于基于混合賽制學習樣例訓練得到的選手來說，其都具有一定的優勢，這表明，基于循環賽制生成的學習樣例的訓練效果最佳.

2)基于循環賽制學習樣例訓練得到的選手和基于淘汰賽制學習樣例訓練得到的選手作為紅藍方對弈時，結果仍然是基于循環賽制學習樣例訓練得到的選手具有獲勝優勢，表明基于循環賽制生成的學習樣例的訓練效果同樣優于淘汰賽制.

綜合以上分析得出：

1)借助成熟公正的體育賽制組織形式為人工智能選手匹配對手，是可行和有效的，可以在短時間內生成大量有效樣例；

2)基于樣本規模綜合指標T的評價表明，基于混合賽制和循環賽制產生的學習樣例具有較高的質量，而基于淘汰賽制產生的學習樣例質量則較為不穩定；

3)樣例訓練之后的選手能力比對實驗表明，循環賽制最適合于西洋跳棋游戲.

5 結束語

目前對于計算機棋類游戲的研究目標多聚焦于人工智能選手與其他選手，尤其是人類冠軍選手比賽的輸贏結果上.雖然眾所周知人工智能選手能力在很大程度上取決于學習樣例，但樣例的產生算法卻沒有引起足夠重視和討論.因此，本文提出了一種學習樣例生成算法，借助體育賽制高效的組織形式為人工智能選手匹配對手，使用遺傳算法使選手進化，最終將優勝者的對局信息作為學習樣例.