并行思想的六子棋博弈搜索算法設(shè)計(jì)

安徽財(cái)經(jīng)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 鄧銀瑩 常 郝

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

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

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

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

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

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

1.2 當(dāng)前研究存在不足

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

1.3 研究意義

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

2 搜索技術(shù)分析

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

表1 搜索算法優(yōu)缺點(diǎn)對(duì)比

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

深度優(yōu)先搜索與樹(shù)的先序遍歷類(lèi)似，對(duì)每一個(gè)可能的分支進(jìn)行深入查找。訪問(wèn)后更改當(dāng)前結(jié)點(diǎn)狀態(tài)，保證每個(gè)結(jié)點(diǎn)只訪問(wèn)一次。當(dāng)某個(gè)分支訪問(wèn)至葉子結(jié)點(diǎn)，則進(jìn)行回溯，查找相鄰結(jié)點(diǎn)進(jìn)行訪問(wèn)。

2.2 極大極小值搜索

假設(shè)雙方每次落子為最佳走法，而落子后雙方都需通過(guò)估值函數(shù)評(píng)價(jià)各自棋局好壞。對(duì)于己方必是選取最優(yōu)落子點(diǎn)，同時(shí)認(rèn)為對(duì)方選取的也是最優(yōu)落子，因此選擇估值最低的局面開(kāi)展博弈樹(shù)。

2.3 Alpha-Beta剪枝搜索

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

2.4 深度學(xué)習(xí)搜素

深度學(xué)習(xí)旨在建立一個(gè)模擬人腦的神經(jīng)網(wǎng)絡(luò)，設(shè)定當(dāng)前局面為輸入層，下一步落棋點(diǎn)為輸出層，在隱藏層中利用六子棋規(guī)則篩選落子點(diǎn)，給不同棋子位置設(shè)定不同概率，經(jīng)過(guò)訓(xùn)練得到最優(yōu)解。

3 算法設(shè)計(jì)

3.1 并行處理

并行計(jì)算將任務(wù)分為多個(gè)小對(duì)象，使計(jì)算機(jī)能同時(shí)處理多個(gè)程序，從而加快計(jì)算機(jī)整體運(yùn)行速度，提高完成效率。其難點(diǎn)在于，找到程序中可以并行運(yùn)算的部分。

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

圖1 并行算法流程圖

3.2 估值函數(shù)

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

表2 連子估值表

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

3.3 走法生成與選擇

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

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

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

圖2 某時(shí)刻棋局圖

表3 落子分值表

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