- 棋類(lèi)游戲算法有哪些 推薦度：
- 相關(guān)推薦
棋類(lèi)游戲的算法有哪些
棋類(lèi)游戲通常包含三大要素：棋盤(pán)、棋子和游戲規則，其中游戲規則又包括勝負判定規則、落子的規則以及游戲的基本策略。下面小編來(lái)給大家講講各類(lèi)棋類(lèi)游戲的算法。
除了棋盤(pán)和棋子的建模，棋類(lèi)游戲最重要的部分就是AI算法的設計。目前棋類(lèi)游戲的AI基本上就是帶啟發(fā)的搜索算法，那么常用的搜索算法有哪些呢?
1. 博弈與博弈樹(shù)
博弈可以理解為有限參與者進(jìn)行有限策略選擇的競爭性活動(dòng)，比如下棋、打牌、競技、戰爭等。根據參與者種類(lèi)和策略選擇的方式可以將博弈分成很多種，比如“二人零和、全信息、非偶然”博弈，也就是我們常說(shuō)的零和博弈(Zero-sum Game)。所謂“零和”，就是有贏(yíng)必有輸，不存在雙贏(yíng)的結果。所謂“全信息”，是指參與博弈的雙方進(jìn)行決策時(shí)能夠了解的信息是公開(kāi)和透明的，不存在信息不對稱(chēng)的情況。比如棋類(lèi)游戲的棋盤(pán)和棋子狀態(tài)是公開(kāi)的，下棋的雙方都可以看到當前所有棋子的位置，但是很多牌類(lèi)游戲則不滿(mǎn)足全信息的條件，因為牌類(lèi)游戲都不會(huì )公開(kāi)自己手中的牌，也看不到對手手中的牌。所謂的“非偶然”，是指參與博弈的雙方的決策都是“理智”的行為，不存在失誤和碰運氣的情況。
在博弈過(guò)程中，任何一方都希望自己取得勝利，當某一方當前有多個(gè)行動(dòng)方案可供選擇時(shí)，他總是挑選對自己最為有利同時(shí)對對方最為不利的那個(gè)行動(dòng)方案。當然，博弈的另一方也會(huì )從多個(gè)行動(dòng)方案中選擇一個(gè)對自己最有利的方案進(jìn)行對抗。參與博弈的雙方在對抗或博弈的過(guò)程中會(huì )遇到各種狀態(tài)和移動(dòng)(也可能是棋子落子)的選擇，博弈雙方交替選擇，每一次選擇都會(huì )產(chǎn)生一個(gè)新的棋局狀態(tài)。
假設兩個(gè)棋手(可能是兩個(gè)人，也可能是兩臺計算機)MAX和MIN正在一個(gè)棋盤(pán)上進(jìn)行博弈。當MAX做選擇時(shí)，主動(dòng)權在MAX手中，MAX可以從多個(gè)可選決策方案中任選一個(gè)行動(dòng)，一旦MAX選定某個(gè)行動(dòng)方案后，主動(dòng)權就轉移到了MIN手中。MIN也會(huì )有若干個(gè)可選決策方案，MIN可能會(huì )選擇任何一個(gè)方案行動(dòng)，因此MAX必須對做好應對MIN的每一種選擇。如果把棋盤(pán)抽象為狀態(tài)，則MAX每選擇一個(gè)決策方案就會(huì )觸發(fā)產(chǎn)生一個(gè)新?tīng)顟B(tài)，MIN也同樣，最終這些狀態(tài)就會(huì )形成一個(gè)狀態(tài)樹(shù)，這個(gè)附加了MAX和MIN的決策過(guò)程信息的狀態(tài)樹(shù)就是博弈樹(shù)(Game Tree)。
2. 極大極小值搜索算法
極大極小值(Min-Max)搜索算法是各種博弈樹(shù)搜索算法中最基礎的搜索算法。假如MAX和MIN兩個(gè)人在下棋，MAX會(huì )對所有自己可能的落子后產(chǎn)生的局面進(jìn)行評估，選擇評估值最大的局面作為自己落子的選擇。這時(shí)候就該MIN落子，MIN當然也會(huì )選擇對自己最有利的局面，這就是雙方的博弈，即總是選擇最小化對手的最大利益(令對手的最大利益最小化)的落子方法。作為一種博弈搜索算法，極大極小值搜索算法的名字就由此而來(lái)。
3. 負極大值搜索算法
博弈樹(shù)的搜索是一個(gè)遞歸的過(guò)程，極大極小值算法在遞歸搜索的過(guò)程中需要在每一步區分當前評估的是極大值節點(diǎn)還是極小值節點(diǎn)。1975年Knuth和Moore提出了一種消除MAX節點(diǎn)和MIN節點(diǎn)區別的簡(jiǎn)化的極大極小值算法，稱(chēng)為負極大值算法Negamax。該算法的理論基礎是：
max(a,b) = -min(-a, -b)
簡(jiǎn)單地將遞歸函數MiniMax()返回值取負再返回，就可以將所有的MIN 節點(diǎn)都轉化為MAX節點(diǎn)，對每個(gè)節點(diǎn)的搜索都嘗試讓節點(diǎn)值最大，這樣就將每一步遞歸搜索過(guò)程都統一起來(lái)。
4. “α-β”剪枝算法
有很多資料將“α-β”剪枝算法稱(chēng)為“α-β”搜索算法，實(shí)際上，它不是一種獨立的搜索算法，而是一種嫁接在極大極小值算法和負極大值算法上的一種優(yōu)化算法。“α-β”剪枝算法維護了一個(gè)搜索的極大極小值窗口：[α,β]。其中α表示在搜索進(jìn)行到當前狀態(tài)時(shí)，博弈的MAX一方所追尋的最大值中最小的那個(gè)值(也就是MAX的最壞的情況)。在每一步的搜索中，如果MAX所獲得的極大值中最小的那個(gè)值比α大，則更新α值(用這個(gè)最小值代替α)，也就是提高α這個(gè)下限。
而β表示在搜索進(jìn)行到當前狀態(tài)時(shí)，博弈的MIN一方的最小值中最大的那個(gè)值(也就是MIN的最壞的情況)。在每一步的搜索中，如果MIN所獲得的極小值中最大的那個(gè)值比β小，則更新β值(用這個(gè)最大值代替β)，也就是降低β這個(gè)上限。當某個(gè)節點(diǎn)的α≥β時(shí)，說(shuō)明該節點(diǎn)的所有子節點(diǎn)的評估值既不會(huì )對MAX更有利，也不會(huì )對MIN更有利，也就是對MAX和MIN的選擇不會(huì )產(chǎn)生任何影響，因此就沒(méi)有必要再搜索這個(gè)節點(diǎn)及其所有子節點(diǎn)了。
5. 估值函數
對于很多啟發(fā)式搜索算法，其“智力”的高低基本上是由估值函數(評估函數)所決定，棋類(lèi)游戲的博弈樹(shù)搜索算法也不例外。
估值函數的作用是把一個(gè)棋局量化成一個(gè)可直接比較的數字，這個(gè)數字在一定程度上能反映取勝的概率。棋局的量化需要考慮很多因素，量化結果是這些因素按照各種權重組合的結果。這些因素通常包括棋子的戰力(棋力)、雙方棋子占領(lǐng)的空間、落子的機動(dòng)性、威脅性(能吃掉對方的棋子)、形和勢等。
6. 置換表與哈希函數
置換表(transposition table)也是各種啟發(fā)式搜索算法中常用的輔助算法，它是一種以空間換時(shí)間的策略，使用置換表的目的就是提高搜索效率。一般情況下，置換表中的每一項代表者一個(gè)棋局中最好的落子方法，直接查找置換表獲得這個(gè)落子方法能避免耗時(shí)的重復搜索，這就是使用置換表能大幅提高搜索效率的原理。
使用置換表最大的問(wèn)題是置換表的組織和查找的效率。一般來(lái)說(shuō)，置換表越大，查找的命中率就越高。但這個(gè)關(guān)系不是絕對的，當置換表大小達到一定規模后，不僅不會(huì )再提高命中率，反而會(huì )因為耗時(shí)的查找操作影響算法的效率。所以置換表不是越大越好，需要根據計算機的性能以及搜索的深度選擇一個(gè)合適的大小。此外，為了查找操作更高效，通常都會(huì )用可直接訪(fǎng)問(wèn)的哈希表方式組織置換表，哈希函數的性能就成為影響置換表性能的重要因素。棋類(lèi)游戲普遍采用Zobrist哈希算法。
7.開(kāi)局庫與終局庫
所謂的開(kāi)局庫和終局庫實(shí)際上就是一種存儲了各種開(kāi)局和終局棋局信息的數據庫。以開(kāi)局庫為例，開(kāi)局庫一般要存儲開(kāi)局的棋局，該棋局對應的各種走法和評估分數，有些開(kāi)局庫還統計了該開(kāi)局最終的勝局次數、平局次數和負局次數，給出開(kāi)局棋局的權重等附加信息供搜索時(shí)選擇。
【棋類(lèi)游戲的算法有哪些】相關(guān)文章：
棋類(lèi)游戲算法有哪些03-28
兒童益智游戲有哪些03-15
戶(hù)外活動(dòng)游戲有哪些03-28
兒童常玩的電子游戲有哪些11-19
圍棋和其它棋類(lèi)有什么不同03-11