計算機博弈中搜索算法的研究與改進

摘要：基于搜索算法可通過節點遞歸的方式進行深度搜索，并結合節點信息，開始進行廣度向量的最優搜索。在開始有效搜索后，其并不會限定節點的展開順序。因此，為提高搜索算法在計算機博弈中的應用效果，算法工程師以最佳優先搜索算法為中心，調整計算機博弈機制，通過更新活節點列表來縮小搜索范圍，從而提高計算機博弈搜索的綜合水平，并在分支定界以及節點處理的基礎上，改進計算機博弈搜索算法，提高計算機博弈程序的綜合應用水平。

關鍵詞：計算機博弈；搜索算法；改進；

計算機博弈是以可視化游戲界面為載體，以顯示局部以及控制落子為基本功能，在博弈環節中，可通過搜索算法的應用，為博弈類比賽交流提供方便。在利用搜索算法的過程中，以象棋為研究對象，并對極大極小算法與最優搜索算法進行對比研究。在這一思想下，計算機博弈分析可根據象棋規則及博弈雙方的下棋程序，創建數學模型，并利用數學算法進行推導與演示。通過對博弈過程進行優化，改進搜索算法的評估函數，并針對計算機博弈過程進行程序調整，從而促進計算機博弈搜索算法的應用效果提升[1]。

一、極大極小算法分析

極大極小算法是計算機博弈分析中常見的算法，在實際應用中，可通過極大極小數值，最終形成博弈樹。具體的博弈樹架構如圖1所示。

結合博弈樹的整體節點結構，要在根節點為初始狀態的情況下，利用節點進行分支延伸，分支相連后，子節點可以代表這一線路的變化狀態。考慮到節點會交替出現，因此，相鄰的兩層可以分別從不同角度進行分析，從而達到最優化的目的。在計算機博弈分析中，極大極小算法的實際應用則是考慮博弈中的布局需求，因此，為提高計算機博弈建模分析的有效性，在利用極大極小算法進行統計與分析中，則需要從一方下棋需求的角度進行計算。將計算機博弈雙方劃分為紅方與藍方，本次研究是以紅方視角為主，在計算機博弈視角下，可通過極大極小算法對節點關系以及數據分析過程進行優化，從而達到棋局合理布局的目的[2]。在實際走棋與分析中，紅方會選擇自己最有利的方向進行選擇，從而獲得分值最高的選擇路徑。藍方走棋階段，則也會根據自身的想法選擇最佳路徑。但是，從紅方的角度發現，藍方的最佳路徑會影響著自己的最佳路徑選擇。在這一視角下，如果博弈樹可以完全展開，那么，最后的葉節點可獲得最終的勝負結果。在進行最優搜索的過程中，可通過提高搜索深度，達到不落敗的目的，但是，這種程序設想僅存在理論層面。從事實上的角度分析，象棋的每個局面，可以有不同的后繼局面，在層層遞進展開中，節點數量會迅速增加。因此，在對限定深度的相關節點進行統計與計算中，可結合中國象棋中的空間復雜度，對對弈結局以及算法的反應時間等進行調整，從而提高節點分析的有效性。在確定節點的搜索方向后，可根據節點進行廣度、深度的搜索，并減少節點的不必要分支，提高檢索效率的同時，提高最優搜索的深度[3]。

二、計算機博弈中最優搜索算法的基本思想

根據理性地對博弈對手的基本假設，為簡化搜索邏輯，在對博弈中的搜索方式進行簡化中，乙方局中人可通過判斷為自己選擇利益最大的行為，在實際模擬與判斷中，可以總是選擇乙方局中人利益最小的行為。乙方局中人在進行搜索中，可以乙方最大利益為目的，但是，實際操作中，搜索深度對搜索結果會產生直接的影響，所以，在每一次的搜索迭代中，可按照極大極小的原則，對局中選擇行為進行搜索與判定[4]。在進行回溯處理中，通過子局面的評估，給出父局面的有效評價。得到最終相對最優行為后，完成搜索。例如，在數據搜索的過程中，則根據雙方行為，對最終的行為有效性進行評估，對極大極小過程進行模擬后，實現數據搜索。在這一過程中，根據父節點的評估值設定，對子節點的數據評估過程進行完善，從而達到雙方選擇相同的操作，提高搜索算法的簡潔性。但是，因為極大極小搜索算法在實際應用中完全等效，所以，為進一步優化極大極小算法的實際應用效果，提出最佳優先搜索算法的改進，從而提高計算機博弈模擬分析及結果選取的有效性[5]。

三、計算機博弈中最佳優先搜索算法的改進與實現

（一）SSS*與A*搜索

SSS*（State Space Search）是以啟發式搜索的方式進行計算，在實際應用中，其搜索過程是利用節點更新的方式，控制節點的搜索范圍，最終獲得最優的搜索節點。在SSS*算法的應用中，所有的節點狀態可通過（n、s、h）來表示，n為博弈編號，n=1的狀態下，則為根節點，s為節點狀態，為有效獲得評估值，所以，將節點狀態設定為SOLVED，未搜索的節點狀態設定為LIVE。h為當前節點的評估值。在算法應用中，具體的操作流程如下：

①設置根節點的初始狀態，并選擇插入OPEN；

②從OPEN中提取h的最大節點P，如果n=root，同時s=SOLVED。那么，節點h則為真實值，算法終止。返回P節點的最佳方式是通過n的操作后，指向根節點。

③在對操作因子的操作過程進行分析中，可對P的執行操作方式進行調整與控制，根據操作需求選擇基礎節點，并按照降序的方式，對節點搜索順序進行排序。在進行因子檢驗與驗證后，可以在Min層中，對節點的數據進行評估。

在實現搜索算法優化中，以極大極小搜索算法為基礎，并在啟發式搜索的視角下，對操作因子以及活節點等進行計算，從而提高數據統計與分析的綜合水平。但是，在實現啟發搜索后，搜索時間效率會相對降低，這對計算機博弈統計及分析等產生一定的影響。因此，為進一步提高博弈搜索效率，則是在SSS*搜索的基礎上，簡化搜索過程，并通過S*在評估函數最優分支上進行深度搜索，從而達到提高計算機及博弈搜索分析效果提升的目的。

（二）計算機博弈最優分支的界定

分支界定是通過傳統算法中的節點分析，選擇最優啟發父節點，并在最優分支上進行界定后，提高博弈搜索效率。在極大極小性質下，分支界定可根據每個節點的上限與下限，對節點的所屬層進行優化。每一層的兄弟節點之間的上限與下限差異并不大，所以，為獲得最佳分支，則需要對計算機博弈進行深層次的搜索。考慮到對方反應存在一定的不確定性，所以，在計算機博弈中，要通過一個上限與下限來表示最差結果。優先展開最佳估計值計算中，可在修正分支后，對分支的最優解進行計算。在最優搜索中，下層節點可以向上層節點反饋，對上層節點的上限與下限進行計算，取值區間可不斷縮短，從而在算法終止后，獲得最佳分支結果。計算機博弈計算中的兩個估值有動態特征，且節點之間存在交叉傳遞的情況。在對下限估計與上限估計進行計算中，可根據節點的修正變化，對節點之間的對應關系進行調整，從而達到節點數據傳輸的目的。在進行修改中，子節點的數值可方便父節點的精化，可促使父節點的上下界相互靠近。具體的返修修正值過程如圖2所示。

圖2 返回修正值過程

在最優分支搜索中，選擇MAX層是指取本層節點中的最大者，MIN指取本層節點中的最小值。在子節點1初始值（30，15）使父節點（-∞，+∞），在進行精化處理后，可對父節點窗口進行更新，將其更新為（15，30），在1、4、5這幾個節點中，1節點的上限數值為30，所以，可以對1節點進行展開搜索。節點2的上限數值22，相比節點1的下限數值15要大，所以，可以將節點1的下限值轉化為22，并將1的上限值修訂為25。從根節點精細化處理的角度進行分析，要根據窗口改動與處理結果，確定最優的解決策略。在獲得最優分支后，返回到子節點層后，發現1的下限值22與4的上限值相同，大于5的上限值為19，因此，1所代表的分支就是最優分支。在實現數據求解與分析中，要考慮如果修改根節點，則需要根據根節點決定搜索方法的選擇，在證明最優過程中，可以采用排除其余過程的方式進行處理，其操作流程如圖3所示。

圖3 排除其他過程

為證明最大層的節點3為最優分支，則需要修改節點1與2的上限值，并適當減小1、2的上限值，最終促使所有節點的上限值小于3的下限值，從而獲得節點3為最優的證明。在實現這一操作目標的過程中，需要分配大量空間來存儲活節點，如果活節點是動態變化的，則采用動態分配內存空間才是最佳方法，但是，在實際操作的過程中，極容易因為申請的博弈數據空間過大，出現內存不足的情況。因此，計算機博弈計算與分析中，可對優先分配內存進行調整與控制，并根據搜索結果進行空間的選擇與釋放，結合釋放結果，提前判斷空間內存是否有溢出的情況。

（三）最優搜索評估

在最優搜索算法中，可利用評估函數進行計算，針對上限值與下限值進行計算中，假設評估函數的結果為V，則可以利用V×O代表局面的上限值，利用GV×P表示局面的下限值，其中，P＜1＜0。在對評估函數進行模擬與分析中，可在個人指定評估函數后，提高最優算法的搜索效率。在計算機博弈中，前十步的搜索效率如表1所示。

最優搜索在多數情況下，可通過簡單的評估函數，對極大極小數值進行統計與計算，并根據評估函數的結果，對計算機博弈過程以及計算數據等進行優化，聯系博弈上實際的局勢變化，提高評估函數的綜合應用效果。

（四）計算機博弈中最優搜索評估函數的應用

在利用最優搜索算法評估函數進行計算中，上限值與下限值的估計準確性高低會直接影響計算機博弈分析的有效性，所以，在對評估函數進行分析中，可根據計算機博弈的差異性，建立新的評估函數，其表達式如下：

Opt=RPieced-BPiece+RvsB

Pes=RPieced-BPiece-BvsR

結合上述對比結果，最優搜索算法非常依賴評估函數，考慮內存空間的基礎上，對活節點數進行控制，從而提高最優搜索節點的獲得效率。在分支界定中，可利用評估函數進行統計與計算，為計算機博弈過程進行預測與計算，對提高計算機博弈分析水平以及提高勝率等有促進作用。

四、結束語

計算機博弈中搜索算法的改進要根據博弈棋盤結構、棋子種類、數量等進行分析，以此數據結構進行建模，調整局面評估函數，并提出最佳優先搜索算法，從數據模塊匹配的角度，提高搜索算法在計算機博弈中的應用效果。在計算機博弈中，對搜索過程以及數據空間等進行優化，提高計算機程序的博弈能力。結合計算機博弈需求，改進搜索算法，通過快速匹配的方式，實現對博弈程序的優化與完善，滿足計算機博弈操作的綜合需求。

作者單位：苗莎 遼寧理工職業大學

參 "考 "文 "獻

[1]彭之軍.計算機博弈算法在黑白棋中的應用[J].現代信息科技，2021，5（17）：73-77+81.

[2]周子龍.博弈搜索樹算法的實現及其優化[J].科學技術創新，2021（18）：108-110.

[3]鄧銀瑩，常郝.并行思想的六子棋博弈搜索算法設計[J].電子界，2021（10）：146-147.

[4]朱良雙，王靜文，李媛.基于UCT搜索算法的點格棋博弈系統研究[J].智能計算機與應用，2021，11（02）：129-131.

[5]雷捷維，王嘉旸，任航，等.基于Expectimax搜索與Double DQN的非完備信息博弈算法[J].計算機工程，2021，47（03）：304-310+320.

[6]張芃芃，孟坤，楊震棟.基于強化學習的海克斯棋博弈算法研究與實現[J].智能計算機與應用，2020，10（03）：142-145.