演算法和博弈

① 博弈樹演算法是啥

就是用樹的節點來表示博弈過程中的每一步，比如在象棋里，雙方棋手獲得相同的棋盤信息。他們輪流走棋，目的就是將死對方，或者避免被將死。
由此，我們可以用一棵「博弈樹」（一棵n叉樹）來表示下棋的過程——樹中每一個結點代表棋盤上的一個局面，對每一個局面（結點）根據不同的走法又產生不同的局面（生出新的結點），如此不斷直到再無可選擇的走法，即到達葉子結點（棋局結束）。

② 巴什博弈必勝策略演算法

巴什博弈公式是：(m+1)|n
理解是如果n=m+1,那麼由於一次最多隻能取m個,所以,無論先取者拿走多少個,後取者都能夠一次拿走剩餘的物品,後者取勝。
因此我們發現了如何取勝的法則是：如果n=(m+1)r+s,(r為任意自然數,s≤m)，那麼先取者要拿走s個物品，如果後取者拿走k(≤m)個，那麼先取者再拿走m+1-k個。結果剩下(m+1)(r-1)個，以後保持這樣的取法，那麼先取者肯定獲勝總之，要保持給對手留下(m+1)的倍數，就能最後獲勝。
同餘定理：n=k_(m+1)+r，先者拿走r個，那麼後者無論拿走1m個先者只要的數目使和為m+1，那麼先手必贏。
博弈論是ACM比賽中的一個很重要的理論，雖然很多情況可以套用公式。
博弈論題目特點:兩名選手，交替進行預先規定好的操作,在任何情況下，合法操作只取決於情況本身，與選手無關。游戲失敗的最終判定往往是選手無法進行合法操作了。

③ 棋類游戲的演算法有哪些

棋類游戲的演算法有哪些

棋類游戲通常包含三大要素：棋盤、棋子和游戲規則，其中游戲規則又包括勝負判定規則、落子的規則以及游戲的基本策略。下面我來給大家講講各類棋類游戲的演算法。

除了棋盤和棋子的建模，棋類游戲最重要的部分就是AI演算法的設計。目前棋類游戲的AI基本上就是帶啟發的搜索演算法，那麼常用的搜索演算法有哪些呢?

1. 博弈與博弈樹

博弈可以理解為有限參與者進行有限策略選擇的競爭性活動，比如下棋、打牌、競技、戰爭等。根據參與者種類和策略選擇的方式可以將博弈分成很多種，比如“二人零和、全信息、非偶然”博弈，也就是我們常說的零和博弈(Zero-sum Game)。所謂“零和”，就是有贏必有輸，不存在雙贏的結果。所謂“全信息”，是指參與博弈的雙方進行決策時能夠了解的信息是公開和透明的，不存在信息不對稱的情況。比如棋類游戲的棋盤和棋子狀態是公開的，下棋的雙方都可以看到當前所有棋子的位置，但是很多牌類游戲則不滿足全信息的條件，因為牌類游戲都不會公開自己手中的牌，也看不到對手手中的牌。所謂的“非偶然”，是指參與博弈的雙方的決策都是“理智”的行為，不存在失誤和碰運氣的情況。

在博弈過程中，任何一方都希望自己取得勝利，當某一方當前有多個行動方案可供選擇時，他總是挑選對自己最為有利同時對對方最為不利的那個行動方案。當然，博弈的另一方也會從多個行動方案中選擇一個對自己最有利的方案進行對抗。參與博弈的雙方在對抗或博弈的過程中會遇到各種狀態和移動(也可能是棋子落子)的選擇，博弈雙方交替選擇，每一次選擇都會產生一個新的棋局狀態。

假設兩個棋手(可能是兩個人，也可能是兩台計算機)MAX和MIN正在一個棋盤上進行博弈。當MAX做選擇時，主動權在MAX手中，MAX可以從多個可選決策方案中任選一個行動，一旦MAX選定某個行動方案後，主動權就轉移到了MIN手中。MIN也會有若干個可選決策方案，MIN可能會選擇任何一個方案行動，因此MAX必須對做好應對MIN的每一種選擇。如果把棋盤抽象為狀態，則MAX每選擇一個決策方案就會觸發產生一個新狀態，MIN也同樣，最終這些狀態就會形成一個狀態樹，這個附加了MAX和MIN的決策過程信息的狀態樹就是博弈樹(Game Tree)。

2. 極大極小值搜索演算法

極大極小值(Min-Max)搜索演算法是各種博弈樹搜索演算法中最基礎的搜索演算法。假如MAX和MIN兩個人在下棋，MAX會對所有自己可能的落子後產生的局面進行評估，選擇評估值最大的局面作為自己落子的選擇。這時候就該MIN落子，MIN當然也會選擇對自己最有利的局面，這就是雙方的博弈，即總是選擇最小化對手的'最大利益(令對手的最大利益最小化)的落子方法。作為一種博弈搜索演算法，極大極小值搜索演算法的名字就由此而來。

3. 負極大值搜索演算法

博弈樹的搜索是一個遞歸的過程，極大極小值演算法在遞歸搜索的過程中需要在每一步區分當前評估的是極大值節點還是極小值節點。1975年Knuth和Moore提出了一種消除MAX節點和MIN節點區別的簡化的極大極小值演算法，稱為負極大值演算法Negamax。該演算法的理論基礎是：

max(a,b) = -min(-a, -b)

簡單地將遞歸函數MiniMax()返回值取負再返回，就可以將所有的MIN 節點都轉化為MAX節點，對每個節點的搜索都嘗試讓節點值最大，這樣就將每一步遞歸搜索過程都統一起來。

4. “α-β”剪枝演算法

有很多資料將“α-β”剪枝演算法稱為“α-β”搜索演算法，實際上，它不是一種獨立的搜索演算法，而是一種嫁接在極大極小值演算法和負極大值演算法上的一種優化演算法。“α-β”剪枝演算法維護了一個搜索的極大極小值窗口：[α,β]。其中α表示在搜索進行到當前狀態時，博弈的MAX一方所追尋的最大值中最小的那個值(也就是MAX的最壞的情況)。在每一步的搜索中，如果MAX所獲得的極大值中最小的那個值比α大，則更新α值(用這個最小值代替α)，也就是提高α這個下限。

而β表示在搜索進行到當前狀態時，博弈的MIN一方的最小值中最大的那個值(也就是MIN的最壞的情況)。在每一步的搜索中，如果MIN所獲得的極小值中最大的那個值比β小，則更新β值(用這個最大值代替β)，也就是降低β這個上限。當某個節點的α≥β時，說明該節點的所有子節點的評估值既不會對MAX更有利，也不會對MIN更有利，也就是對MAX和MIN的選擇不會產生任何影響，因此就沒有必要再搜索這個節點及其所有子節點了。

5. 估值函數

對於很多啟發式搜索演算法，其“智力”的高低基本上是由估值函數(評估函數)所決定，棋類游戲的博弈樹搜索演算法也不例外。

估值函數的作用是把一個棋局量化成一個可直接比較的數字，這個數字在一定程度上能反映取勝的概率。棋局的量化需要考慮很多因素，量化結果是這些因素按照各種權重組合的結果。這些因素通常包括棋子的戰力(棋力)、雙方棋子佔領的空間、落子的機動性、威脅性(能吃掉對方的棋子)、形和勢等。

6. 置換表與哈希函數

置換表(transposition table)也是各種啟發式搜索演算法中常用的輔助演算法，它是一種以空間換時間的策略，使用置換表的目的就是提高搜索效率。一般情況下，置換表中的每一項代表者一個棋局中最好的落子方法，直接查找置換表獲得這個落子方法能避免耗時的重復搜索，這就是使用置換表能大幅提高搜索效率的原理。

使用置換表最大的問題是置換表的組織和查找的效率。一般來說，置換表越大，查找的命中率就越高。但這個關系不是絕對的，當置換表大小達到一定規模後，不僅不會再提高命中率，反而會因為耗時的查找操作影響演算法的效率。所以置換表不是越大越好，需要根據計算機的性能以及搜索的深度選擇一個合適的大小。此外，為了查找操作更高效，通常都會用可直接訪問的哈希表方式組織置換表，哈希函數的性能就成為影響置換表性能的重要因素。棋類游戲普遍採用Zobrist哈希演算法。

④ 演算法筆記之博弈問題——貓和老鼠

博弈問題，需要注意，對於每個玩家，都會爭取：

LeetCode913. 貓和老鼠

兩位玩家分別扮演貓和老鼠，在一張 無向 圖上進行游戲，兩人輪流行動。

圖的形式是：graph[a] 是一個列表，由滿足 ab 是圖中的一條邊的所有節點 b 組成。

老鼠從節點 1 開始，第一個出發；貓從節點 2 開始，第二個出發。在節點 0 處有一個洞。

在每個玩家的行動中，他們 必須 沿著圖中與所在當前位置連通的一條邊移動。例如，如果老鼠在節點 1 ，那麼它必須移動到 graph[1] 中的任一節點。

此外，貓無法移動到洞中（節點 0）。

然後，游戲在出現以下三種情形之一時結束：

如果貓和老鼠出現在同一個節點，貓獲勝。
如果老鼠到達洞中，老鼠獲勝。
如果某一位置重復出現（即，玩家的位置和移動順序都與上一次行動相同），游戲平局。
給你一張圖 graph ，並假設兩位玩家都都以最佳狀態參與游戲：

如果老鼠獲勝，則返回 1；
如果貓獲勝，則返回 2；
如果平局，則返回 0 。

題目描述比較長，但其實還是很好理解的。需要注意，每個玩家都會爭取自己獲勝。本題就是簡單的深度優先搜素+記憶化問題了。

這里考慮的是怎麼才能算平局，我們採取的方法是，如果有n個節點，到2n輪如果還沒出結果，就認為可以平局了。

需要注意的是記憶化，memo[i][j][k] 代表貓在i，老鼠在j，在第k輪的結果。

⑤ 多智能體博弈如何體現在演算法中

多智能體博弈體現在演算法中：
1.蟻群優化演算法（AntColonyOptimization,ACO）
ACO演算法思想來源於螞蟻尋食中的通信機制，螞蟻在尋找食物過程中通過分泌信息素，通過信息素的濃度來選取最佳路徑。
對於ACO演算法的改進有Max-MinAntSystem（MMAS）和AntColonySystem（ACS）演算法，MMAS演算法的主要特徵是在每一次迭代結束後，僅最優螞蟻對其所經過的最優路徑進行信息素
更新，其他螞蟻不參與更新，ACS加入偽隨機比例規則和離線信息素更新規則，並且只對全局最優路徑的信息素進行更新。
2.粒子群演算法（ParticleSwarmOptimization,PSO）為代表。
PSO演算法是科學家們在觀察鳥群覓食時利用計算機模擬鳥群的聚集行為總結出一種群智能演算法，可以在全局隨機搜索,演算法運行前會在自身建立的搜尋空間中設置一群隨機的粒子，粒子通過迭代的
過程不斷地更新自己的速度、位置逐漸朝著最優位置逼近，最終會找到最優解。

⑥ 博弈演算法的研究意義

博弈演算法的研究意義是可作為研究價格競爭問題的最有力的武器和有效的工具。根據查詢相關資料得知，博弈論是研究各方策略相互影響的條件下，理性決策人的決策行為的一種理論，通過利用博弈均衡理論在企業價格競爭當中的應用來研究企業應該正確的運用價格競爭策略。