并行思想的六子棋博弈搜索算法設計

安徽財經大學計算機科學與技術系 鄧銀瑩 常 郝

搜索算法是計算機博弈的核心問題，其好壞對整個系統(tǒng)產生直接影響。通過對計算機六子棋博弈中搜索算法的研究，將Alpha-Beta剪枝、深度優(yōu)先搜索、極大極小值、深度學習四種算法并行結合，使計算機在對抗過程中綜合選取最佳落子點，借此提高機器博弈水平，使計算機博弈更加靈活高效。

1 六子棋搜索策略發(fā)展現狀及研究意義

計算機博弈是人工智能領域一個重要且具有挑戰(zhàn)性的研究分支，包括五子棋、軍旗等棋牌游戲。六子棋以規(guī)則簡單、局面復雜的特點吸引玩家前來研究與挑戰(zhàn)，其設計包含數據結構、搜索算法、估值函數、著法生成四部分。六子棋落子需綜合評估兩步棋的狀態(tài)，而如何讓這兩步棋發(fā)揮最大作用，是研究的難點所在。

1.1 六子棋搜索策略發(fā)展現狀

2005年六子棋出現至今，雖與五子棋略有相似，但由于六子棋每輪每方可落兩子，最后的局面由兩子統(tǒng)一評定，所以它的計算復雜度相當于五子棋的兩倍，利用研究五子棋的方法無法完全解決六子棋博弈問題。因此許多研究者開始尋找其它策略，應對六子棋出現后的新挑戰(zhàn)。

目前已研究的六子棋搜索策略包括極大極小搜索、Alpha-Beta剪枝、深度優(yōu)先搜索、蒙特卡洛搜索、深度學習等。這些方法或多或少在提高程序搜索效率，提升博弈研究水平方面做出貢獻，也為后來者進一步研究與優(yōu)化提供理論支持與方向。

1.2 當前研究存在不足

目前六子棋的搜索算法多樣，但存在以下缺點：1）算法在計算機中串行執(zhí)行，無法充分利用CPU并行計算優(yōu)勢。2）部分算法因搜索時間長，無法在既定時間內完成最佳落子的查找與判定。3）部分算法雖耗時短，但因搜索不充分導致落子策略存在缺陷。

1.3 研究意義

對六子棋博弈搜索技術的研究，一方面是為找出更佳的搜索策略，能夠在更短的時間進行更深、更廣的搜索，從而提高六子棋博弈水平，更好地解決計算機博弈中的問題。另一方面通過學習并行計算相關知識，研究計算機博弈算法并行可行性，借此加深對機器博弈的理解與應用，推動未來人類智能領域發(fā)展。

2 搜索技術分析

搜索算法能從當前局面找出合適落子點進行棋局。當局面逐漸復雜時，簡單的搜索并不能有效找到最佳落子點，針對不同位置還應考慮落子后的發(fā)展情況。因此，為了更加有效地利用搜索算法，在提高落子質量的同時，對搜索深度與存儲空間進行合理分配，從而達到優(yōu)化程序的目的，下面介紹幾種博弈搜索算法。搜索算法優(yōu)缺點對比表1所示。

表1 搜索算法優(yōu)缺點對比

2.1 深度優(yōu)先搜索

深度優(yōu)先搜索與樹的先序遍歷類似，對每一個可能的分支進行深入查找。訪問后更改當前結點狀態(tài)，保證每個結點只訪問一次。當某個分支訪問至葉子結點，則進行回溯，查找相鄰結點進行訪問。

2.2 極大極小值搜索

假設雙方每次落子為最佳走法，而落子后雙方都需通過估值函數評價各自棋局好壞。對于己方必是選取最優(yōu)落子點，同時認為對方選取的也是最優(yōu)落子，因此選擇估值最低的局面開展博弈樹。

2.3 Alpha-Beta剪枝搜索

Alpha-Beta剪枝以極大極小值搜索為基礎，通過排除搜索后的無用結點節(jié)省搜索空間，提高算法效率。對于極大值情況，保留最大分支；對于極小值情況，保留最小分支。

2.4 深度學習搜素

深度學習旨在建立一個模擬人腦的神經網絡，設定當前局面為輸入層，下一步落棋點為輸出層，在隱藏層中利用六子棋規(guī)則篩選落子點，給不同棋子位置設定不同概率，經過訓練得到最優(yōu)解。

3 算法設計

3.1 并行處理

并行計算將任務分為多個小對象，使計算機能同時處理多個程序，從而加快計算機整體運行速度，提高完成效率。其難點在于，找到程序中可以并行運算的部分。

圖1表示同時執(zhí)行四種搜索算法，綜合得到的落子并選取最佳落子點，使各算法得到充分利用，避免單個算法帶來的局限性。

圖1 并行算法流程圖

3.2 估值函數

博弈程序的落子點判斷，主要由搜索策略和估值函數配合完成。對于棋局的判斷，以基于“路”的搜索為基礎，在搜索中無需考慮棋形分布，只需查找某條路上是否存在六子，即可判斷勝負。每條路由某個點位以及與之相連的5個點組成，統(tǒng)計該條路上棋子個數，并用二進制將信息存儲。接著調用估值函數，給不同路賦予不同分值，最后綜合分值選出最優(yōu)落子策略。相比基于“棋形”的搜索，該方法節(jié)省大量匹配時間，便于對當前棋局的評估。連子估值如表2所示。

表2 連子估值表

估值函數的判定需參考固定子力值、棋子位置值、棋子靈活度值、威脅與保護值、動態(tài)調整值五要素。上表為最初參數設定，還需通過不斷測試找到更合適的權值，從而完善程序，提高棋力。

3.3 走法生成與選擇

走法生成是指將當前局面所有合理走法羅列出的模塊，也是用以告知計算機下一步走法的部分。通過并行計算得到每種搜索方式提供的最佳走法，再進行模擬比較，選擇分值最高的落子點作為之后的博弈策略。

圖2代表一副棋局，接下來由計算機執(zhí)行程序確定兩顆白子下落位置。表3列出計算機并行處理四種搜索算法得到的兩顆落子坐標，以及利用估值函數得到的棋子分值。由表可知，深度學習算法得到的落子分值最高，為最佳落子。

最佳落子的選擇利用貪心思想，選取分值最高者為最終結果，但可能存在一定誤差。因此還需考慮不同搜索算法所消耗時間、對之后棋局的影響等因素，綜合判斷后再做定奪。

圖2 某時刻棋局圖

表3 落子分值表

總結：隨著計算機博弈不斷發(fā)展，單一算法不足以適應復雜多變的棋局狀況。本文通過對計算機博弈中六子棋搜索技術的研究，結合并行算法，為計算機博弈搜索策略提供新思路與研究方向。