啟發式搜尋策略即為結點排序技術。α-β 搜尋/剪枝算法的剪枝效率對同一結點下的孩子結點的排列順序非常敏感，這些結點的排列越理想，則剪枝越早發生，需要展開和估值的結點數越少，算法效率越高，反之搜尋效率越低。
雖然無法事先預知哪個結點是最佳結點，但卻可以採取一些措施，讓能產生剪枝的幾率越高的結點越排在前面，以優先搜尋，使博弈樹儘可能接近最小樹。
常見的結點排序技術，有吃子啟發、置換表啟發、歷史啟發、殺手啟發等。
基本介紹
- 中文名：博弈樹啟發式搜尋
- 套用學科：計算機
- 適用領域範圍：計算機博弈
- 適用領域範圍：人工智慧
博弈樹,吃子啟發,置換表啟發,歷史啟發,殺手啟發,各種啟發策略的組合與順序,
博弈樹
博弈樹是一種與/或樹的一種，為了方便博弈樹的研究，我們利用最簡單的一種博弈來作為研究的對象。這種博弈具有三個特性:二人零和，全信息，非偶然。具體的說這樣的博弈具有如下的特點:
(1)對壘的A，B雙方輪流採取行動(這就比同時採取行動在分析上方便的許多)，博弈的結果只有三種情況:A方勝，B方敗；A方敗，B方勝；雙方戰成平局。
(2)在對壘過程中，任何一方都了解當前的格局及過去的歷史。
(3)任何一方在採取行動前都要根據當前的實際情況，進行得失分析，選取對自己最為有利而對對方最為不利的對策,不存在“碰運氣”的偶然因素。即雙方都是很理智地決定自己的行動。
在博弈過程中，任何一方都希望自己取得勝利。因此,在某一方當前有多個行動方案可供選擇時，他總是挑選對自己最為有利而對對方最為不利的那個行動方案。此時，如果我們站在A方的立場上，則可供A方選擇的若干行動方案之間是“或”關係，因為主動權操在A方手裡，他或者選擇這個行動方案，或者選擇另一個行動方案，完全由A方決定。但是，若B方也有若干個可供選擇的行動方案，則對A方來說這些行動方案之間是“與”關係，因為這時主動權操在B方手裡，這些可供選擇的行動方案中地任何一個都可能被B方選中，A方必須考慮到對自己最不利的情況發生。
若把上述博弈過程用圖表示出來，得到的是一棵“與/或”樹。這裡要特別指出，該“與/或”樹是始終站在某一方(例如A方)的立場上得出的，決不可一會兒站在這一方的立場上,一會兒又站在另一方的立場上。
博弈樹有如下的特點:
(1)博弈的初始格局是初始節點。
(2)在博弈樹中，“或”節點和“與”節點是逐層交替出現的。自己一方擴展的節點之前是“或”關係，對方擴展節點之前是“與”關係。雙方輪流地擴展節點。
(3)所有能使自己一方獲勝的終局都是本原問題，相應的節點是可解節點；所有使得對方獲勝的終局都是不可解節點。
從上面的敘述中我們可以看到對博弈樹的研究有這樣幾點:
(1)雖然這樣的博弈是相對簡單的,但是它在實際中卻又有著很廣泛的基礎。小到棋類活動中子力部署和調遣，大到軍事行動中軍隊的部署，後勤物資的供應,乃至行動的時機的選擇都可以在適當的條件下成為博弈的對象，得到優良的結果。
(2)為複雜的博弈問題，提供了參考基礎。在多方參加，不完全知識並且存在運氣的情況下，原有的成果只要將新加入的條件作為加入的參數進行博弈，仍然可以很好的完成工作。
(3)博弈樹的搜尋還只是整個過程的一部分，它還需要對所分析事件進行合理的建模才能達成良好的結果。這就要求我們在研究博弈樹的同時，需要能夠合理的分析具體問題，並建立恰當的數據結構，同時根據具體問題的複雜程度選擇恰當的分析策略。
具體到兩個人的博弈問題中，為了從眾多可供選擇的行動方案中選出一個對自己有利的行動方案，就需要對當前情況以及將要發生的情況進行分析，從中選出最優者。最常使用的分析方法是極大極小分析法。其基本思想是:
(1)設博弈的雙方中一方為A,另一方為B。極大極小分析法是為其中一方(例如A)尋找一個最優行動方案的方法。
(2)為了找到當前的最優行動方案，需要對各個方案可能產生的後果進行比較。具體地說，就是要考慮每一方案實施後對方可能採取的所有行動，並計算可能的得分。
(3)為計算得分，需要根據問題的特性信息定義一個估值函式，用來估算當前博弈樹端節點的得分。此時估算出來的得分稱為靜態估值。
(4)當端節點的估值計算出來後，再推算出父節點的得分。推算的方法是:對“或”節點，選其子節點中一個最大的得分作為父節點的得分，這是為了使自己在可供選擇的方案中選一個對自己最有利的方案；對“與”節點，選其子節點中一個最小的得分作為父節點的得分，這是為了立足於最壞的情況。這樣計算出的父節點的得分稱為倒推值。
(5)如果一個行動方案能獲得較大的倒推值,則它就是當前最好的行動方案。
在博弈問題中，每一個格局可供選擇的行動方案都有很多，因此會生成十分龐大的博弈樹。據統計西洋跳棋完整的博弈樹約有1040個節點。試圖利用完整的博弈樹來進行極大極小分析是困難的。可行的辦法是只生成一定深度的博弈樹，然後進行極大極小分析，找出當前最好的行動方案。在此之後，再在已經選定的分支上擴展一定深度,再選最好的行動方案。如此進行下去,知道取出勝敗的結果為止。至於每次生成博弈樹的深度，當然是越大越好，但由於受到計算機存儲空間的限制，只好根據實際情況而定。
吃子啟發
吃子啟發（Capturing Heuristic）也稱為靜態啟發（Static Heuristic），僅針對吃子著法。吃子啟發通過 MVV/LVA（Most Valuable Victim/Least ValuableAttacker，最大價值的受害者 /最小价值的攻擊者）思想為吃子著法定義了一種“吃子得分”， 在被吃的棋子有對方其他棋子保護的情況下，一個吃子著法的吃子得分為：對方被吃子價值 MVV 減去己方攻擊子價值 LVA；如果被吃的棋子沒有保護，則只考慮對方被吃子價值 MVV。將吃子著法按照吃子得分從大到小排列，值越大的越優先搜尋。
以中國象棋為例，在開局狀態下，最初搜尋時，置換表啟發、歷史啟發、殺手啟發這些動態啟發起的作用很小甚至來不及起作用，此時吃子啟發起的作用較大。因此，在著法生成時，考慮首先生成車、馬、炮的著法，最後生成帥的著法，往往是很有效的。
有文獻認為，吃子著法不多，分析了對應的局面後不用經過搜尋，就大致應該知道哪些著法應該首先嘗試，很多情況下能立刻得到較好的效果，在各種結點排序技術中應該優先考慮。
有些棋類遊戲，如五子棋，不存在吃子啟發。
置換表啟發
置換表除了記錄結點局面估值信息以供查詢外，還能提供啟發的功能。置換表啟發（Translation Table Heuristic）即在置換表的數據項中，增加一個域，用來保存該局面的估值對應的著法。再次搜尋到同樣局面的結點時，先查找置換表，如果命中，但因置換表內記錄的深度為達到搜尋深度要求，或者邊界值條件不成立，則估值結果不能被利用，但置換表對應數據項中記錄的著法依舊有一定意義，可優先搜尋這個著法，多數情況下能更快產生剪枝。
PV 結點對應的著法顯然是最佳著法，無疑應該保存到置換表中。β 結點能產生剪枝，其對應的著法多數情況下也是較優的著法，顯然也應保存到置換表。
至於 α 結點，有文獻認為 α 結點的每個著法均返回 α 值，無法確定哪個著法是最好的，因此無需保存 α 結點對應的著法，僅保存估值信息即可；也有文獻認為 α 結點結點對應的著法也可以保存到置換表，只要下次搜尋時該著法是個合理的著法就可以優先搜尋；而著名的中國象棋程式“縱馬奔流”則採取了一個更好的方法，稱為“低出/高出邊界的修正”策略，使得某些 α 結點也存在置換表著法，減少了搜尋結點數。
“低出邊界的修正”指的是，當某個 α 結點覆蓋某個相同局面的置換表數據項時，保留該表項的最佳著法。“高出邊界的修正”指的是，當某個 β 結點沒能覆蓋某個相同局面的置換表項（該表項記錄了一個沒有著法的 α 結點）時，只把這個 β 結點的截斷著法寫入該置換表項。
歷史啟發
歷史啟發（History Heuristic）是 J.Schaeffer 於 20 世紀 80 年代提出的博弈樹結點排序技術。在搜尋過程中，以前搜尋到的某一局面下的最佳著法，在其他相差不大的局面下，仍有很大可能也是最佳著法。某個著法被證明是最佳的次數越多，成為相應局面最佳著法的可能性也越大。當一個著法作為兄弟著法中的最佳者，或者能引發了剪枝，則被認為是一個“好”的著法。歷史啟發的思想是為每個著法設定一個歷史得分，每次搜尋到一個“好”的著法，該著法的歷史得分就累加上一個增量，一般認為，搜尋深度越深，搜尋結果越可靠，所以這個增量值的大小與相應結點靠近根結點的距離有關，越靠近頂層的結點，這個增量值就越大，越靠近葉子結點則越小。一個“好”的著法被搜尋到的次數越多，其歷史得分就會較高。生成某一局面下的全部著法時，將所有著法根據歷史得分重新排列，歷史得分越高的著法越優先搜尋，越早引發剪枝的機率越大。
一些文獻認為，歷史啟發僅適用於非吃子著法，但也有文獻將歷史啟發使用在任何類型的著法中。在眾多的啟發策略中，歷史啟發的效果是最好的。歷史啟發不依賴於具體棋類遊戲的規則和知識，是一種較為通用的結點排序技術，它付出的代價很少，卻往往就能收到極好的效果。在不同的棋類博弈遊戲中歷史啟發的效果差異很大，如在西洋棋、中國象棋中能獲得很好的效果，但在五子棋中，歷史啟發的效果就不如西洋棋和中國象棋。
殺手啟發
殺手啟發（Killer Heuristic）可以看作是歷史啟發的一種特例。所謂“殺手”，指的是同一層中引發剪枝最多的結點。殺手啟發的方法是為每一層記錄引發剪枝最多的殺手著法（一般是記錄 2 個殺手著法），當下次搜尋到同一層時，如果殺手著法是合法的著法，則優先搜尋殺手著法。一般認為，殺手著法不僅可以是引發剪枝的 β 結點對應的著法，也可以是 PV 結點對應的著法，或者是 α 結點估值最好的非空著法；但也有人認為，殺手著法應該只是引發剪枝的 β 結點對應的著法，才配的上“殺手”這個名稱。殺手啟發的開銷要小於歷史啟發，但效果也弱於歷史啟發。
各種啟發策略的組合與順序
吃子啟發不依賴於以往的搜尋結果，也被稱為靜態啟發（Static Heuristic），而置換表啟發、歷史啟發、殺手啟發依賴於以往的搜尋結果，屬於動態啟發（Dynamic Heuristic）。多種啟發策略混合使用效果更好。如果將多種啟發策略混合使用，要考慮策略順序。
不同的棋類博弈遊戲，最好的策略順序會有所不同。以中國象棋計算機博弈為例，多數文獻為一種較好的策略順序是：
（1）置換表啟發：若置換表中的著法不為空，則首先搜尋置換表中的著法；
（2）吃子啟發：生成所有吃子著法，按照 MVV/LVA 值從大到小排序；
（3）殺手啟發：如果殺手著法是合理的著法，再搜尋殺手著法；
（4）歷史啟發：生成所有非吃子著法，著法按照歷史得分從大到小排序。
