TWI757971B - 確定執行設備的動作選擇方針 - Google Patents

Abstract

本文公開了用於生成執行設備的動作選擇方針以在環境中完成任務的方法、系統和裝置，包括編碼在計算機儲存媒體上的計算機程式。所述方法包括：在當前迭代中，基於執行設備的收益以及其他設備到達終點狀態的到達概率，計算執行設備在終點狀態下的反事實值(CFV)；計算執行設備在終點狀態下的經基線校正的CFV；對於具有子狀態的每個非終點狀態，基於執行設備在子狀態下的經基線校正的CFV的加權和，計算執行設備在非終點狀態下的CFV；計算執行設備在非終點狀態下的經基線校正的CFV和CFV基線；確定針對下一次迭代的非終點狀態下的動作選擇方針。

Description

確定執行設備的動作選擇方針

本文涉及確定用於執行設備的動作選擇方針，以在包括執行設備以及一個或多個其他設備的環境中完成任務。

兩個或更多個參與方之間的策略互動可以藉由涉及兩個或更多個參與方(也稱為玩家)的博弈來建模和模擬。在涉及兩個或更多個玩家的不完美資訊博弈(IIG)中，玩家在做出決策之前只能部分獲得對手的知識。這類似於現實場景，例如貿易、交通路線規劃和公開拍賣。許多現實生活場景可以表示為IIG，例如不同公司之間的商業競爭、拍賣場景中的競標關係以及欺詐方與反欺詐方之間的博弈關係。

由於資訊隱藏，玩家必須在對對手的資訊不確定的情況下做出決策，並且其還需要採取行動以利用對手對自己的資訊不確定的優勢。求解IIG可能在計算上是昂貴且耗時的，特別是對於具有大量可能狀態和供選擇的可能動作的大型博弈。期望以有效方式求解IIG的技術。

本主題的描述的實施例可以單獨地或組合地包括一個或多個特徵。

例如，在一個實施例中，一種執行設備的計算機實現的方法，一種執行設備的計算機實現的方法，用於生成動作選擇方針以在包括所述執行設備以及一個或多個其他設備的環境中完成任務，所述方法包括：在多次迭代的當前迭代中，基於所述執行設備在終點狀態下的收益以及所述一個或多個其他設備到達所述終點狀態的到達概率，計算所述執行設備在完成任務的所述終點狀態下的反事實值(CFV)，其中，所述終點狀態是由所述執行設備以及所述一個或多個其他設備在多個非終點狀態下採取的動作序列導致的，所述多個非終點狀態均具有一個或多個子狀態；基於所述執行設備在所述終點狀態下的CFV及/或所述執行設備在前一次迭代的終點狀態下的CFV基線，計算所述執行設備在所述終點狀態下的經基線校正的CFV；對於每個非終點狀態並從具有所述終點狀態以及一個或多個其他終點狀態作為子狀態的非終點狀態開始：基於所述執行設備在所述非終點狀態的子狀態下的經基線校正的CFV的加權和，計算所述執行設備在所述非終點狀態下的CFV；基於所述執行設備在所述非終點狀態下的CFV及/或所述執行設備在前一次迭代的非終點狀態下的CFV基線，計算所述執行設備在所述非終點狀態下的經基線校正的CFV；基於所述執行設備在所述前一次迭代的非終點狀態下的CFV基線與所述執行設備在所述非終點狀態下的CFV或經基線校正的CFV的加權和，計算所述執行設備在所述當前迭代的非終點狀態的CFV基線；以及基於所述執行設備在所述當前迭代的非終點狀態下的經基線校正的CFV，確定針對下一次迭代的非終點狀態下的動作選擇方針。

在一些實施例中，可以使用系統、方法或計算機程式，或者系統、方法和計算機程式的任何組合來實現這些一般和特定態樣。前述和其他描述的實施例可以各自包括以下一個或多個態樣：

在一些實施例中，反應於確定滿足收斂條件，基於所述非終點狀態下的動作選擇方針控制所述執行設備在所述非終點狀態下的操作，以用於所述下一次迭代。

在一些實施例中，基於所述執行設備在所述當前迭代的非終點狀態下的經基線校正的CFV來確定針對所述下一次迭代的非終點狀態下的動作選擇方針包括：基於所述執行設備在所述當前迭代的非終點狀態下的經基線校正的CFV計算遺憾值；以及根據遺憾匹配，基於所述遺憾值確定針對所述下一次迭代的非終點狀態下的動作選擇方針。

在一些實施例中，所述一個或多個其他設備到達所述終點狀態的到達概率包括由到達所述終點狀態的所述一個或多個其他設備採取的動作的概率的乘積。

在一些實施例中，基於所述執行設備在所述非終點狀態下的CFV及/或所述執行設備在前一次迭代的非終點狀態下的CFV基線，計算執行設備在非終點狀態下的經基線校正的CFV包括：基於以下計算在前一次迭代的終點狀態下採取所述動作的執行設備的採樣CFV基線：所述執行設備在所述前一次迭代的終點狀態下的CFV基線，所述執行設備在所述前一次迭代的終點狀態下採取所述動作的採樣方針，以及所述執行設備採取的動作序列導致到達所述終點狀態的概率；反應於確定對所述動作進行了採樣，基於所述執行設備在所述非終點狀態下的CFV和在所述前一次迭代的終點狀態下採取所述動作的執行設備的採樣CFV基線，計算在所述非終點狀態下採取所述動作的執行設備的經基線校正的CFV；以及反應於確定未對所述動作進行採樣，將在所述前一次迭代的終點狀態下採取所述動作的執行設備的採樣CFV基線用作所述執行設備在所述非終點狀態下的經基線校正的CFV。

在一些實施例中，基於經所述當前迭代中所述非終點狀態下的動作選擇方針加權的、所述執行設備在所述終點狀態下的經基線校正的CFV以及所述執行設備在所述一個或多個其他終點狀態下的對應的經基線校正的CFV，計算所述執行設備在所述終點狀態下的經基線校正後的CFV與所述執行設備在所述一個或多個其他終點狀態下的對應的經基線校正的CFV的加權和。

在一些實施例中，所述執行設備在所述前一次迭代的非終點狀態下的CFV基線與所述執行設備在所述非終點狀態下的CFV或經基線校正的CFV的加權和包括以下兩項之和：經標量加權的、所述執行設備在所述前一次迭代的非終點狀態下的CFV基線；以及經第二標量和考慮所述非終點狀態的概率加權的、所述執行設備在所述非終點狀態下的CFV或經基線校正的CFV。

應當理解，根據本文的方法可以包括本文描述的態樣和特徵的任何組合。即，根據本文的方法不限於本文具體描述的方面和特徵的組合，而是還包括所提供的方面和特徵的任何組合。

本文的一個或多個實施例的細節在附圖和以下描述中闡述。通過說明書和附圖以及申請專利範圍，本文的其他特徵和優點將變得清楚。

本文描述了用於確定執行設備的動作選擇方針的技術，以在包括執行設備以及一個或多個其他設備的環境中完成任務，例如，用於執行設備與一個或多個其他設備之間的策略互動。例如，執行設備可以執行用於搜索執行設備與一個或多個其他設備之間的博弈的納什均衡的計算機實現的方法，並獲得導致納什均衡或近似納什均衡的動作選擇方針(例如，解法或策略)。在一些實施例中，這些技術可以涉及執行反事實遺憾最小化(CFR)算法以求解不完美資訊博弈(IIG)。在一些實施例中，這些技術可以降低計算複雜度和方差，同時提高CFR算法的收斂速度。

IIG可以表示一種或多種現實場景，例如自動駕駛車輛(AV)控制、資源分配、產品/服務推薦、網路攻擊預測及/或預防、交通路線規劃、欺詐管理、貿易、投標等，其中涉及兩個或更多個參與方(也稱為玩家)的資訊，且每個參與方可以具有關於另一參與方決策的不完美或不完全資訊。本文使用撲克作為IIG的示例。所描述的技術可以在許多其他人工智慧(AI)和機器學習應用中使用。

求解IIG的典型目標是找到納什均衡，使得任何玩家都無法單方面提高獎勵。換句話說，納什均衡是涉及兩個或更多個玩家的IIG的典型解法。反事實遺憾最小化(CFR)是一種旨在近似地找到大型博弈的納什均衡的算法。CFR試圖使整體反事實遺憾最小化。事實證明，所有迭代中策略的平均值將收斂到納什均衡。在求解博弈時，原始形式的CFR(也稱為原始CFR、標準CFR、普通CFR或簡稱為CFR)在每次迭代中遍歷整個博弈樹。因此，原始CFR需要大容量記憶體來儲存大型零和擴展式博弈，例如單挑無限注德州撲克。在某些情況下，原始CFR可能無法用有限記憶體處理大型博弈。

引入蒙特卡洛CFR(MCCFR)以最小化反事實遺憾。MCCFR可以根據採樣的經驗求解不完美資訊博弈。與原始CFR不同，MCCFR在每次迭代中對博弈樹中的節點子集進行採樣。MCCFR可以計算反事實值的無偏估計，並避免遍歷整個博弈樹。由於在每次迭代中僅存取所有資訊集的子集，因此MCCFR比原始CFR需要更少的儲存空間。MCCFR可以包括不同的版本或變體，例如取決於不同的採樣方針。MCCFR通常因採樣而長期性能較差且方差較高。

本文描述了加速MCCFR收斂的示例性技術。例如，這些技術包括向量形式的採樣方針、具有可證明無偏估計的方差減小方法、探索技術以及利用跳過機制和貼現(discounting)更新的混合MCCFR變體。這些一種或多種技術可以組合在一起並應用於MCCFR。實驗結果表明，所描述的技術可以在MCCFR的許多場景下實現100倍至1000倍加速。

本文中描述的技術可以產生一個或多個技術優勢。在一些實施例中，所描述的技術可以由執行設備執行，用於生成動作選擇方針，以在包括執行設備以及一個或多個其他設備的環境中完成任務。在一些實施例中，所描述的技術可以確定用於軟體實現應用的動作選擇方針，該軟體實現應用在包括該應用支持的執行方以及一個或多個其他參與方的環境中執行動作。在一些實施例中，所描述的技術可以用於自動控制、自動駕駛車輛控制、機器人技術或涉及動作選擇的任何其他應用中。例如，所確定的動作選擇方針可以用於控制發動機、馬達、致動器、閥和任何其他設備，或者可以應用於控制電路中以控制一個或多個設備的操作。在一個示例中，鑒於對環境中其他車輛的運動的預測，自動駕駛車輛的控制系統可以適於控制自動駕駛車輛的速度、加速度、方向及/或行駛時間。控制系統可以以更好的路線選擇、減少的行駛時間及/或更低的燃料消耗來幫助自動駕駛車輛到達期望的目的地。例如，這可以促進交通規劃、避免事故和提高操作安全性。

作為在自動駕駛車輛中的應用的示例，環境可以包括多個自動駕駛車輛，用於完成諸如交通規劃或控制的任務，以避免碰撞並到達多個自動駕駛車輛的各個目的地。多個自動駕駛車輛中的每個都可以配備有執行設備，執行設備可以實施軟體實現應用，以生成動作選擇方針，從而在環境中完成任務。所生成的動作選擇方針包括控制資訊，該控制資訊被配置為控制自動駕駛車輛的發動機、馬達、致動器、制動器等中的一個或多個。因此，它可以被多個自動駕駛車輛中的每個用來控制自動駕駛車輛的一個或多個發動機、馬達、致動器、制動器等，使得自動駕駛車輛可以遵循所生成的動作選擇方針來實現任務。在一些實施例中，可以由IIG對任務進行建模，並且可以藉由計算機模擬(例如，藉由求解IIG)來生成動作選擇方針以實現任務。多個自動駕駛汽車中的每個都可以表示IIG的一個參與方。動作可以包括例如自動駕駛車輛的指定方向、速度、距離、時間或任何其他度量中的一個或多個。自動駕駛車輛的動作選擇方針可以包括在不同狀態下(例如，地理位置中的不同十字路口)選擇各個動作的策略，使得自動駕駛車輛可以在環境中導航並到達目的地。

作為機器人技術應用的另一示例，環境可以包括工業機器人(例如，倉庫機器人)，其與一個或多個其他參與方(例如，其他機器人)進行互動以完成任務(例如，在倉庫中移動物品或組裝一些產品)。在一些實施例中，可以由IIG對任務進行建模，並且可以藉由計算機模擬(例如，藉由求解IIG)來生成動作選擇方針以實現任務。該動作可以包括例如工業機器人的指定方向、位置、速度或任何其他運動中的一個或多個。工業機器人的動作選擇方針可以包括在不同狀態下(例如，倉庫中的不同位置)選擇各個動作的策略，使得工業機器人可以在環境中導航並完成任務(例如，移動倉庫中的物品)。

在一些實施例中，所描述的技術可以幫助找到諸如資源分配、產品/服務推薦、網路攻擊預測及/或預防、交通路線規劃、欺詐管理等的現實場景的更好策略，這些策略可以是由各方之間的策略互動來建模或表示，例如涉及兩個或更多個參與方的IIG。在一些實施例中，所描述的技術可以利用高級採樣方案(例如，考慮當前策略的向量及/或利用探索)，該高級採樣方案回傳方差較小的策略、更接近於全域最優解而不是局部最優解的策略、或者更接近於納什均衡的策略。

在一些實施例中，所描述的技術可以幫助以更有效的方式找到現實場景的策略。因此，可以用較少的計算機模擬量及/或在減少的等待時間/響應時間內找到現實場景的解法或策略。例如，與原始CFR相比，所描述的技術基於MCCFR，MCCFR僅對IIG玩家的所有可能動作組合中的一些進行採樣，從而大大減少了遍歷或用盡所有可能動作組合進行模擬和求解IIG所需的計算量。在一些實施例中，可以在顯著更短的響應時間內找到解法或策略，從而有助於使需要實時或接近實時響應或控制的某些現實場景成為可能。

在一些實施例中，所描述的技術可以在尋找納什均衡以求解表示一個或多個現實場景的博弈時提高收斂速度，提高計算效率並減少MCCFR算法的計算量。在一些實施例中，所描述的技術可以減小MCCFR算法的方差。

在一些實施例中，當以向量形式實現MCCFR時，所描述的向量形式的採樣方針可以提供更有效的採樣方針。所描述的向量形式的採樣方針可以在決策點考慮多種不同的策略，並計算更多地關注相對重要的動作的採樣方針，同時實現更好的找到納什均衡(包括近似納什均衡)的長期性能，例如，藉由提高執行MCCFR的收斂速度。

在一些實施例中，所描述的方差減小技術可以減小方差並減少MCCFR的迭代次數。在一些實施例中，所描述的方差減小技術可以藉由使用基於反事實值基線而不是基於預期效用值基線的控制變量算法來減少計算量並提高計算效率。

在一些實施例中，與現有技術方法相比，所描述的利用跳過機制和貼現更新的混合MCCFR算法可以加速收斂並減小MCCFR的方差。

在一些實施例中，擴展式IIG可以表示為如下。IIG中有n個玩家(機會除外)。N ={1,...,n }是玩家的有限集合，並且每個成員都是玩家。在兩玩家博弈中，N ={1, 2}。這兩個玩家由p 1和p 2表示。對手觀察不到玩家i的隱藏資訊(變量)，該資訊由h^v _i 表示。每個成員h ∈H 指可能的歷史(或狀態)。歷史(或狀態)可以包括導致狀態的動作序列(包括機會的動作)。

對於玩家i ，

指玩家i 以外的所有玩家的隱藏資訊。空序列ø是H 的成員。h_j

h 表示h_j 是h 的前提。Z表示終點歷史的集合，並且任何成員z∈Z都不是任何其他序列的前提。終點歷史也可以稱為終點狀態，其可以是IIG的結束狀態。在終點歷史中任何玩家都無需採取進一步的動作。每個終點歷史z ∈Z 對每個玩家i 都有關聯的效用或收益。

玩家函數P 將N ∪{c }的成員分配給每個非終點歷史，其中c 表示機會玩家。P (h )是在h 下採取動作的玩家。A (h ) = {a :ha ∈H }是h ∈H \Z 之後的可用動作的集合。非終點歷史也可以稱為非終點狀態，其可以是IIG的中間狀態。一個或多個玩家可以在非終點狀態下採取可能動作，從而導致另一狀態。

歷史{h ∈H :P (h ) =i }的I _i 是玩家i 的資訊分劃。集合I_i ∈I _i 是玩家i 的資訊集(infoset )，並且I_i (h )是指狀態h 下的資訊集I_i 。對於I_i ∈I _i ，A (I_i ) =A (h )和P (I_i ) =P (h )。如果一個博弈中的所有玩家都可以回憶起他們以前的動作和資訊集，則稱為完美回憶博弈。

鑒於所有玩家的歷史，可以遞歸建立前提樹(trie) 。這樣的前提樹在博弈理論中被稱為博弈樹。博弈樹中的每個節點都指的是歷史h 。每個玩家的資訊集樹都建立在資訊集而不是歷史上。公開樹是建立在公開序列上的前提樹。每個公開序列都可以包括所有玩家甚至第三方觀察者公開已知或可以觀察到的動作。在一些實施例中，終點歷史或終點狀態可以由博弈樹或公開樹的終點節點或葉子節點表示。非終點歷史或非終點狀態可以由博弈樹或公開樹的非終點節點表示。終點歷史z 對應於動作序列(也稱為終點動作序列)，其包括所有玩家所採取的導致終點歷史z 的動作。例如，終點歷史z 對應於沿著從博弈樹或公開樹的根節點到終點節點z 的軌跡或路徑的動作序列，其包括所有玩家採取的導致終點歷史z 的動作。

圖1A和圖2B是示出根據本文的實施例的庫恩撲克的博弈樹100和公開樹150的示例的圖。庫恩撲克是零和兩玩家IIG撲克的示例。庫恩撲克是擴展式博弈的示例。博弈規則定義如下。整付牌僅包含三張撲克牌，例如，國王(K)、女王(Q)和傑克(J)。向每個玩家發一張牌，其可與標準撲克博弈類似地下注。如果兩個玩家都下注或兩個玩家都過牌，則牌較高的玩家獲勝，否則下注玩家獲勝。

博弈樹是有向圖。博弈樹的節點表示博弈中的位置(或玩家的狀態)。如圖1A所示，博弈樹100的根節點110由圓圈表示，該圓圈是機會節點(也稱為玩家0)。博弈樹100的每個終點節點或葉子節點(例如，終點節點143a、153a、153b、143c、143d、147a、157a、157b、147c或147d)由菱形表示，表示博弈中一個或兩個玩家的收益的終點狀態。每個正方形(例如，非終點節點123、127、143b或147b)表示玩家1的狀態。每個三角形(例如，非終點節點133a、133b、137a或137b)表示玩家2的狀態。在一些實施例中，h_i 表示非終點節點，z_i 表示終點節點。

在向每個玩家發一張牌之後，有六個不同的可能狀態。如從根節點110向外的六個箭頭所示，六個不同的可能狀態為[J, Q]、[J, K]、[Q, J]、[Q, K]、[K, J]、[K, Q]，分別表示玩家1和玩家2收到的牌。博弈樹100示出六個可能狀態中的兩個的子樹103和107。對應於狀態[J, Q]的左子樹103指示兩個玩家(玩家1和玩家2)分別被發到J和Q。對應於狀態[J, K]的右子樹107指示兩個玩家(玩家1和玩家2)分別被發到J和K。

從博弈樹的節點(或邊)向外的箭頭可以表示玩家在博弈狀態下的可能動作。如圖1A所示，節點123向外的箭頭表示玩家1在與狀態[J, Q]相對應的節點123的狀態下的可能動作A_1a 和A_1b 。類似地，節點133a向外的箭頭表示玩家2在與玩家1選擇的[J, Q, A_1a ]狀態相對應的節點133a的狀態下的可能動作A_2a 和A_2b 。節點133b向外的箭頭表示玩家2在與狀態[J, Q, A_1b ]相對應的節點133b的狀態下的可能動作A_2c 和A_2d 。

從根節點110到每個節點的軌跡是動作的序列或歷史。例如，如子樹103中所示，非終點節點143b對應於包括動作[J, Q, A_1a, A_2b ]的動作(可以表示為h _143b )的序列或歷史。終點節點153b對應於包括動作[J, Q, A_1a, A_2b, A_3b ]的動作(可以表示為h _153b )的序列或歷史。由於節點153b是終點節點，因該動作序列[J, Q, A_1a, A_2b, A_3b ]可以稱為終點動作序列(導致或引起終點狀態153b)。在子樹103中，節點143b是終點節點153b的前提。類似地，終點節點143c對應於包括動作[J, Q, A_1b, A_2c ]的動作(可以表示為h _143c )的序列或歷史。

在IIG中，玩家2看不到玩家1的私牌。類似地，玩家1看不到玩家2的私牌。因此，玩家1在與狀態[J, Q]相對應的節點123處和與狀態[J, K]相對應的節點127處可用的資訊實際上是相同的，因為玩家1只知道其私牌J，而不知道對手玩家2的私牌是Q還是K。資訊集I_i 可以用於表示這些未區分狀態的集合。令h ₁₂₃ 表示節點123的狀態，而I₁ (h ₁₂₃ )表示在節點123的狀態下的資訊集，並且h ₁₂₇ 表示節點127的狀態，而I₁ (h ₁₂₇ )表示在節點127的狀態下的資訊集。在該示例中，I₁ (h ₁₂₃ ) =I₁ (h ₁₂₇ )。通常，任何I_i ∈I包括玩家i 觀察到的資訊，其包括玩家i 的隱藏變量(例如，私牌)和公開動作。在此示例中，I₁ (h ₁₂₃ ) =I₁ (h ₁₂₇ ) = J，其可以表示為I₁₁ 。

類似地，玩家1在與狀態[Q, J]和[Q, K]相對應的節點處可用的資訊是相同的，可以由包括玩家1的私牌Q的相同資訊集I₁₂ 來表示。玩家1在與狀態[K, J]和[K, Q]相對應的節點處可用的資訊是相同的，可以由包括玩家1的私牌K的相同資訊集I₁₃ 來表示。

圖1B示出對應於博弈樹100的公開樹150。公開樹150中的每個節點125、135a、135b、145a、145b、145c、145d、155a或155b可以表示包括公開動作的序列或歷史(也稱為公開序列)的公開狀態。每個節點對應於資訊集的向量

= [I_{i 1} ,I_{i 2} ,I_{i 3} ,... ]。對於

，它們可以指示相同的公開序列。

指向量的長度。例如，如圖1B所示，節點125對應於初始公開序列，在該示例中其為空ø。節點125與玩家1的資訊集向量

= [1₁₁ , 1₁₂ , 1₁₃ ]相關聯，分別對應於玩家1的私牌J、Q、K。

作為另一示例，節點135a可以表示包括玩家1的動作[A_1a ]的公開序列並且對應於玩家2的資訊集向量。類似地，節點135b可以表示包括玩家1的動作[A_1b ]的公開序列，並且對應於玩家2的資訊集的另一向量。非終點節點145b對應於包括公開動作[A_1a, A_2b ]的公開序列。終點節點155b對應於包括公開動作[A_1a, A_2b, A_3b ]的公開序列。

在一些實施例中，公開樹150中的非終點節點145b可以表示六個不同的可能初始狀態[J, Q]、[J, K]、[Q, J]、[Q, K]、[K, J]和[K, Q]之間的共同公開狀態。非終點節點145b的共同公開狀態包括包含公開動作[A_1a, A_2b ]的公開序列，並且對應於玩家1在非終點節點145b處的資訊集向量，

(節點145b) = [I₁₁ (節點145b), I₁₂ (節點145b), I₁₃ (節點145b)]。I₁₁ (節點145b)可以表示玩家1在非終點節點145b處的資訊集，其包括玩家1的私人動作和導致非終點節點145b的共同序列。即，I₁₁ (節點145b) = [J, A_1a, A_2b ]。類似地，I₁₂ (節點145b) = [Q, A_1a, A_2b ]；以及I₁₃ (節點145b) = [K, A_1a, A_2b ]。資訊集I₁₁ (節點145b)可以由博弈樹100中的兩個節點143b和147b共享。節點143b對應於博弈中所有玩家的導致節點143b的私人動作和公開動作的序列。即，h _143b = [J, Q, A_1a, A_2b ]。類似地，節點147b對應於博弈中所有玩家的導致節點147b的私人動作和公開動作的序列。即，h _1473b = [J, K, A_1a, A_2b ]。可以看出，h _143b 和h _1473b 共享相同的資訊集I₁₁ (節點145b) = [J, A_1a, A_2b ]。

在一些實施例中，IIG的策略和納什均衡可以表示如下。對於玩家i ∈N，擴展式博弈中的策略σ_i (I_i )將A (I_i )上的動作分佈分配給資訊集I_i 。策略組合(strategy profile)可以表示為σ = {σ_i |σ_i ∈ Σ _i ,i ∈N }，其中Σ _i 是玩家i 的所有可能策略的集合。σ _−i 是指σ 中除σ_i 之外的所有策略。σ_i (I_i )是資訊集I_i 的策略。σ_i (a |h )是指玩家i 在狀態h 下採取動作a 的概率。∀h ₁ ,h ₂ ∈I_i ,I_i =I_i (h ₁ ) =I_i (h ₂ ),σ_i (I_i ) =σ_i (h ₁ ) =σ_i (h ₂ ),σ_i (a |I_i ) =σ_i (a |h ₁ ) =σ_i (a |h ₂ )。在一些實施例中，策略σ_i (I_i )指定並包括在策略σ_i (I_i )下在狀態h 下的多個可能動作中選擇動作a 的相應概率σ_i (a |h )。例如，對於圖1A中的博弈樹100的節點123處的玩家1，策略σ₁ (I_i )可以包括在節點123的狀態下從兩個可能動作A_1a 和A_1b 中選擇動作A_1a 的概率σ₁ (A_1a |節點123)，以及在節點123的狀態下從兩個可能動作A_1a 和A_1b 中選擇動作A_1b 的概率σ₁ (A_1b |節點123)。如果策略σ₁ (I_i )是均勻的(例如，初始策略)，則概率σ₁ (A_1a |節點123)= 0.5，概率σ₁ (A_1b |節點123)= 0.5。在一些實施例中，可以在CFR的每次迭代中更新策略σ₁ (I_i )，使得當CFR收斂時，如果玩家在狀態h 下或給定資訊集I 的情況下遵循策略σ₁ (I_i )中指定的概率選擇動作，則玩家可以達到納什均衡(或近似納什均衡)。例如，如果CFR輸出的策略σ₁ (I_i )指定概率σ₁ (A_1a |節點123)= 0.2，並且概率σ₁ (A_1b |節點123)= 0.8，則玩家可以在狀態h 下或者在給定資訊集I 的情況下選擇概率為0.8的動作A_1b ，以接近納什均衡(或近似納什均衡)。

對於CFR這樣的迭代學習方法，σ^t 表示第t次迭代的策略組合。π^σ (h )是指狀態到達概率(也稱為狀態範圍)，其是所有玩家(包括機會，例如博弈樹100中的根節點110)沿歷史h 的策略的乘積。對於空序列，π^σ (ø) = 1。

在一些實施例中，可將到達概率分解為

其中

是玩家i 的策略σ_i 的乘積，而

是除i 以外的所有玩家的策略的乘積，記為σ _−i 。∀h ∈I_i ,π_i ^σ (h ) =π_i ^σ (I_i )。

對於兩個歷史h ₁ 和h ₂ ，h 1

h 2，π^σ (h ₁ ,h ₂ )指的是所有玩家從歷史h ₁ 至h ₂ 的策略的乘積。可以類似的方式定義π_i ^σ (h ₁ ,h ₂ )和π^σ _-i (h ₁ ,h ₂ )。I_i 的資訊集到達概率(資訊集範圍)可以藉由

來定義。類似地，

。

對於玩家i ，期望的博弈效用可以藉由

來計算。給定固定的策略組合σ _−i ，最佳響應表示為

- 納什均衡是近似納什均衡，其策略組合σ ^∗ = (br (σ _−i ),br (σ_i ))，滿足：

策略σ_i 的可利用性可以定義為

。如果

，則策略無法利用。在大型兩玩家零和博弈例如撲克中，

會很難計算。但是，如果玩家交換位置，則一對博弈的值為零，即，

。可將策略組合σ 的可利用性定義為

。

CFR是一種用於在零和完美回憶不完美資訊博弈中找到納什均衡的迭代方法。可以計算出反事實值

，以表示玩家i 在當前策略組合σ^t 下在資訊集

處的預期效用，假設玩家i 進行博弈以達到

。在一些實施例中，給定σ^t ，可以藉由下式計算反事實值

其中

是對手的範圍矩陣(即，對手的到達概率)，

是玩家i 在給定資訊集

下的預期效用值矩陣，而d 表示維度。

在一些實施例中，

可以被計算為除玩家i 之外的所有玩家沿歷史

的策略的乘積，表示給定玩家i 在當前策略組合σ^t 下達到了當前資訊集

的情況下對手動作的後驗概率。給定玩家i 在當前策略組合σ^t 下達到了當前資訊集

並假設對手的私人動作是均勻分佈的，則

可以表示預期效用值矩陣。

例如，對於圖1A和1B中的庫恩撲克，

可以表示當向玩家2分別發了具有均勻分佈的私牌J、Q或K時，玩家1的預期效用值，而

可以是給定玩家1在當前策略組合σ^t 下達到了當前資訊集

，向玩家2分別發私牌J、Q或K的概率向量。

再舉一個示例，在單挑無限注德州撲克(HUNL)中，

中的每個條目都指的是當發了特定一對私牌時對手的範圍。

中的每個條目均指給定兩個玩家的私牌和當前策略下的預期效用值。

指的是動作a 的反事實值，其遺憾可藉由下式計算：

t 次迭代後動作a 的累計遺憾是

其中R_i ⁰ (a |I_i ) = 0。

定義

max

則可以基於遺憾匹配根據以下方式計算t+1次迭代時的當前策略：

可藉由下式計算T次迭代後的平均策略

：

CFR+與CFR類似，不同之處在於CFR+用遺憾匹配+替換遺憾匹配並使用加權平均策略。經過足夠的迭代，事實證明CFR和CFR+可以達到納什均衡。CFR和CFR+收斂到均衡的最著名的理論邊界是

。此邊界比以速率

收斂的一階方法慢。但是，在許多博弈中，CFR+的經驗收斂速度遠快於

。

MCCFR藉由在每次迭代中對資訊集的子集進行採樣來計算反事實值的無偏估計。定義Q= {Q ₁ ,Q ₂ ,...,Q_m }，其中Q_j ∈Z 是由MCCFR生成的採樣終點歷史的集合(塊)，使得Q _j 覆蓋集合Z。將

定義為考慮塊Q_j 的概率，其中

。定義

為考慮特定的終點歷史z 的概率。特定的終點歷史z 對應於動作序列(也稱為終點動作序列)，其包括所有玩家所採取的導致終點歷史z 的動作。在一些實施例中，考慮特定的終點歷史z 的概率是對該特定的終點歷史z 進行採樣的概率(也稱為採樣的終點動作序列的概率)。在一些實施例中，可以基於包括在導致採樣終點歷史z的採樣終點動作序列中的所有動作的採樣概率，來計算採樣終點歷史 z的概率或採樣終點動作序列的概率。例如，如果導致採樣終點歷史z的採樣終點動作序列包括動作序列[A ₁ ,A ₂ ,...,A_m ]，則可以將

計算為採樣終點動作序列[A ₁ ,A ₂ ,...,A_m ]中所有動作各自的採樣概率的乘積。

I_i 的採樣反事實值的估計值(也稱為估計反事實值)可以藉由下式計算：

其中1/q(z)可以表示在計算採樣反事實值

時特定的採樣終點歷史z的重要性。

將

定義為採樣策略組合，其中

是玩家i 的採樣策略，而

是除玩家i 外其他玩家的採樣策略。採樣動作

的遺憾可以藉由下式計算：

其中

其中

=

是經

加權的效用。

經過t 次迭代後，動作a 的估計累計遺憾為

其中

。

可以根據等式(7)基於遺憾匹配或類似於原始CFR的遺憾匹配+來計算t+1迭代時的當前策略。類似地，可以根據等式(8)來計算T次迭代後的平均策略

。

MCCFR可證明地保持了反事實值的無偏估計，並收斂到納什均衡。結果採樣和外部採樣是兩種流行的採樣方法。原始結果採樣根據兩個玩家的當前策略方針(或ϵ-貪婪)選擇一個歷史。外部採樣與結果採樣非常相似，不同之處在於一個玩家在其決策節點處採取所有動作。在每次迭代中，經典MCCFR指定一個玩家作為遍歷者，該玩家的累計遺憾和策略將在此迭代進行更新。之後，另一玩家將被指定為遍歷者。提出了另一種採樣方法，即強韌採樣，其中遍歷者對k 個動作進行採樣，而對手對一個動作進行採樣。在強韌採樣方案中，每個玩家都使用均勻採樣方法在當前決策點處進行採樣，而另一參與方根據對應策略進行採樣。對應於不同迭代的到達概率可以是固定的。可以證明，強韌採樣方案與MCCFR中的結果採樣方案相比，方差更小，而與外部採樣相比，儲存效率更高。在一些實施例中，強韌採樣方案可以使MCCFR以更快的收斂速度求解納什均衡(包括近似納什均衡)。

MCCFR及其變體可以分為三種類型：數值形式MCCFR、半向量形式MCCFR和向量形式MCCFR。為了清楚說明，將這三種類型的MCCFR形式解釋為在圖1A-B中所示的庫恩撲克中使用。在這裡，強韌採樣被用作默認採樣方法，玩家p 1是遍歷者。在每個決策節點，p 1根據均勻隨機方針對一個動作進行採樣，而p 2根據p 2的當前策略對一個動作進行採樣。

數值形式的MCCFR：在每次迭代的開始，分別為p 1和p 2發一張私牌，例如將J 發給p 1，將Q 發給p 2，如左子樹103所示。然後他們互相對抗直到結束。在完美回憶兩玩家不完美資訊博弈中，給定公開序列和p 2的私牌，可以確定特定的資訊集I ₂ ∈I₂ 。p 2根據σ ₂ (I ₂ )對一個動作進行採樣。在這種情況下，數值形式的MCCFR在每次迭代都會生成一個歷史h 。終點節點的值是博弈收益。

半向量形式的MCCFR：假設向p 2發了私牌Q ，而向p 1發了私牌向量[J, K ]。與數值形式的MCCFR相似，這兩個玩家互相對抗直到結束。p 1的決策節點維護資訊集向量

，而p 2的節點維護一個資訊集I ₂ 。此外，I ₁ 表示策略的向量

= [σ ₁₁ ,σ ₁₂ ]。在這種情況下，p 2根據σ ₂ (I ₂ ) 對一個動作進行採樣。當使用強韌採樣時，p 1根據均勻隨機方針而不是方針向量

對其動作進行採樣，因此無需指定特定的當前策略作為採樣方針。半向量形式的MCCFR在每次迭代時都會更新遍歷者的遺憾和策略的向量。可以預期，半向量形式的MCCFR可以從有效的矩陣運算中受益，並且經驗上的收斂速度要快於數值形式的MCCFR。

向量形式的MCCFR：此方法無需為p 1和p 2指定私牌。如圖1B所示，玩家i ∈[1,2]的決策節點(例如，非終點節點125、135a或135b)維護資訊集向量

= [I_{i 1} ,I_{i 2} ,I_{i 3} ]。在每次迭代中，向量形式的MCCFR沿公開樹150生成序列的向量(例如，從節點125到終點節點例如節點155b遵循公開序列[A_1a, A_2b , A_3b ])。

因為每個決策節點

表示當前策略的向量

= [σ_{i 1} ,σ_{i 2} ,σ_{i 3} ]。在給定當前策略向量

中的多個當前策略的情況下，需要確定採樣方針，以在決策節點

處從玩家i 的可能動作中對一個動作進行採樣。沒有使用均勻採樣方針來使

中的每個資訊集共享相同的均勻策略，而是介紹幾種非均勻採樣方針。在一些實施例中，這些非均勻採樣方針可以更加關注相對重要的動作，並且還可以獲得更好的長期性能。

隨機當前策略(RCS)：使用RCS時，玩家i 從

中隨機選擇一個資訊集I_i 並根據σ_i ^t (I_i )對一個動作進行採樣。

平均當前策略(MCS)：此採樣方針是

中所有資訊集的當前策略的平均值，其可以藉由下式計算：

MCS為

中的不同資訊集{I_i }賦予相同的權重。

加權當前策略(WCS)：在博弈論領域，玩家通常採取不利動作的概率非常低。通常，玩家在不同情況下會做出不同的決策。例如，在撲克博弈中顯示有益的公牌後，玩家可能需要採取更具侵略性的策略。因此，在WCS中，在等式(8)中的平均策略的基礎上，

中不同的資訊集{I_i }可以被不同地加權。例如，資訊集I_i 可以被玩家i 的範圍加權。在這種情況下，可以藉由下式定義WCS採樣方針：

在一些實施例中，WCS採樣策略可以包括其他版本，例如藉由賦予不同或附加的權重。例如，在等式(14)中玩家i 自己的範圍

可以被對手的範圍

或兩個玩家的範圍

替換。在許多情況下，上述WCS採樣策略可以有效地達到納什均衡。

加權平均策略(WAS)：在WAS中，等式(13)和等式(14)中的當前策略可以用t 次迭代中的平均策略作為納什均衡的近似值來替換。例如，藉由由平均策略

替換等式(13)中的當前策略σ^t ，加權平均策略可以定義為

在一些實施例中，可以將

而不是

用作等式(15中的每個資訊集的權重，因為等式(8)和等式(15)權重相同。

MCCFR從採樣經驗中學習狀態動作方針。蒙特卡洛方法中使用的方差減小技術可以應用於MCCFR。例如，控制變量是一種方差減小技術，其中隨機變量的方差可以藉由減去另一隨機變量並加上其期望值來減小。基線可用於方差減小技術中。基線允許基於從相同狀態開始時動作的對數概率的性能好於或差於平均性能來增加或減少動作的對數概率。在一些實施例中，為了減小方差，可以為每個反事實值指定特定的基線。在一些實施例中，基線可以是標量。在一些實施例中，經基線校正的CFV可以是原始CFV減去指定基線。

在一些實施例中，不使用預期效用值，可以使用反事實值作為應用於MCCFR的方差減小技術中的基線(稱為反事實值基線)。事實證明，基於反事實值基線的方差減小是無偏的，並且可以比基於預期效用值基線的方差減小在計算上更為有效。

在利用反事實值基線的方差減小中，可以遞歸定義估計反事實值。Q_j 指的是採樣塊，I_i 指的是

成立的採樣資訊集。

將b^t _i ⁻¹ (a |I_i )定義為迭代t-1上的狀態動作基線，將

定義為玩家i 的採樣方針，將q (I_i )定義為對I_i 進行採樣的概率。

在向量形式的MCCFR中，∀h ∈I_i ,q (h )=q (I_i )。迭代t-1上的估計狀態動作基線可以計算為：

給定資訊集I_i 處動作a 的估計反事實值

，動作a 的基線校正值或基線增強值

可以藉由下式計算：

資訊集I_i 的估計反事實值

可以藉由下式計算：

定義b ⁰ _i (a |I_i )=0。可以使用兩種示例性方法來更新基線。在第一種方法中，可以藉由下式基於估計反事實值更新基線：

在第二種方法中，基於等式(17)中的基線校正值

而不是估計反事實值

更新基線。換句話說，用基於等式(17)計算的

替換等式(19)中的

。第二基線也稱為引導基線。

可以按照原始MCCFR的類似公式來計算累計遺憾和平均策略，例如，分別根據等式(12)和(8)。可以針對所有資訊集沿採樣序列，遞歸更新估計反事實值和基線。

作為使用反事實值基線方法實現方差減小的示例，對於MCCFR的每次迭代，可以執行以下步驟。

(a)根據等式(18)的上方等式(或第一等式)計算博弈樹或公開樹的終點節點的CFV。在一些實施例中，對於數值形式的實施方式，根據等式(18)，針對公開樹的終點節點的CFV的計算可以實現為(1×d 矩陣)和(d ×1矩陣)的矩陣(或向量)乘積，類似於等式(4)。在一些實施例中，對於向量形式的實施方式，根據等式(18)針對公開樹的終點節點的CFV的計算可以實現為(d ×d 矩陣)和(d ×d 矩陣)的矩陣乘積。在一些實施例中，基於對手的範圍矩陣和預期效用值矩陣的CFV的計算僅需要針對公開序列的終點節點的每個公開序列計算一次。非終點節點的CFV可以基於非終點節點的子節點的加權CFV之和，例如，根據等式(18)的下方等式(或第二等式)。

(b)根據等式(17)計算經基線校正的CFV。在向量形式的實施方式中，由於基線是CFV基線，因此該步驟可能只需要兩個d×1 矩陣相加，如等式(17)中的下方等式所示，而不是根據預期效用基線進行進一步的運算。

(c)根據等式(18)的下方等式(或第二等式)針對每個非終點節點計算CFV。此步驟包括子節點的經加權的CFV的總和。在向量形式的實施方式中，獲得的CFV的維度為d×1 。

(d)根據等式(19)更新基線。該步驟包括經衰減因子

和考慮非終點狀態的概率

加權的平均CFV，該平均CFV可以基於導致

的動作序列的採樣概率的乘積來計算。在向量形式的實施方式中，得到的更新後的基線的維度為d×1 。

(e)沿著博弈樹或公開樹遞歸計算(b)-(d)，直到到達當前迭代的根節點為止。例如，分別根據等式(10)、(12)、(7)和(8)，按照原始MCCFR的類似公式，計算得出的每個節點的經基線校正的CFV可用於計算遺憾、累計遺憾、當前策略和平均策略。

迭代中的上述步驟可以重複進行，直到達到收斂條件為止。達到收斂後的當前策略或平均策略可以作為MCCFR的輸出回傳，以近似納什均衡。

可以證明，使用反事實值基線方法減小方差保持了反事實值的無偏估計。即，如果基線校正後的反事實值由等式(17)和等式(18)定義，則

成立。

在一些實施例中，基於反事實值基線的方差減小技術比基於預期效用值基線的技術需要更少的計算。例如，根據等式(4)，可將反事實值

計算為對手的範圍矩陣

和預期效用值矩陣

∈

^{d ×1} 的乘積。當使用向量形式的MCCFR時，基於預期效用值基線的方差減小技術將d×d 矩陣保持為基線，並在控制變量中使用該基線來更新基線校正後的預期效用值(也為d×d 矩陣)。此後，估計反事實值是對手的範圍矩陣(1×d 矩陣)、基線增強的預期效用值(d×d 矩陣)和

矩陣)的乘積。

與預期效用值基線不同，利用反事實值基線的方差減小技術在計算上更有效。在一些實施例中，資訊集向量

的反事實值是1×d 矩陣。如等式(19)中所定義，反事實值基線基於反事實值更新。對應於

的基線是1×d 矩陣。等式(17)和等式(18)是對應於

的幾個1×d 矩陣的求和或匯總。對於非終點狀態，反事實值或基線校正後的反事實值可以基於等式(18)的下方等式(或第二等式)中所示的求和或匯總來更新。相比之下，對於利用預期效用值基線的方差減小技術，基於所有終點狀態和非終點狀態的相乘(例如，如等式(4)所示)來更新反事實值或基線校正後的反事實值。這樣，反事實值基線相對於預期效用值基線所節省的計算量可以取決於表示環境或IIG的博弈樹或公開樹的深度及/或非終點狀態的數量。如果博弈樹或公開樹較深及/或具有大量非終點狀態，則利用反事實值基線的MCCFR的計算效率甚至比基於預期效用值基線的MCCFR的計算效率更高。例如，在HUNL中，d =1326⁴ 。基於期望值的方法至少需要進行1326×1326次加法運算以更新其基線，而基於反事實值的方法僅需要1×1326次加法運算。

在一些實施例中，探索技術可以應用於MCCFR，從而以較少的樣本實現更好的性能。在一些實施例中，可以使用混合或混雜採樣方針來平衡利用和探索，這是MCCFR中的權衡，其從採樣經驗中學習狀態動作方針。在一些實施例中，混合採樣方針可以表示為：

其中σ_i ^s (a |I_i )指採樣方針，σ_i ^e (a |I_i )指探索方針。α ∈[0, 1]是混合因子，其用於控制探索權重。通常，α 是衰減因子。例如，設置

，則lim _{t →∞} α = 0成立。採樣方針σ_i ^s 可以是任何合適的採樣方針，包括RCSσ_i ^rcs 、MCSσ_i ^mcs 、WASσ_i ^was 、結果採樣、外部採樣、強韌採樣或均勻採樣。在一些實施例中，

和

使

成立。因此，

使

成立。

將∆C^t (a |I_i )定義為迭代t 中資訊集I_i 處動作a 的採樣次數。如果在此迭代中未對資訊集I_i 或動作a 進行採樣，則∆C^t (a |I_i )為0。可以藉由下式計算累計採樣次數：

在數值形式的MCCFR中，例如結果採樣，如果在迭代t 中在資訊集I_i 處對動作a 進行採樣，則設置∆C^t (a |I_i ) = 1。在向量形式的MCCFR中，當對

進行採樣時，對於每個資訊集

，

應該相應地更新。在一些實施例中，單個計數器用於整個資訊集向量

，以計算對動作a 採樣的次數。在一些實施例中，使用小批量MCCFR(在2019年1月17日提交的名稱為“SAMPLING SCHEMES FOR STRATEGY SEARCHING IN STRATEGIC INTERACTION BETWEEN PARTIES(在多方策略互動中進行策略搜索的採樣方案)”的第PCT/CN2019/072200號PCT申請，和2019年6月21日提交的名稱為“SAMPLING SCHEMES FOR STRATEGY SEARCHING IN STRATEGIC INTERACTION BETWEEN PARTIES(在多方策略互動中進行策略搜索的採樣方案)”的第16/448,390號美國專利申請中描述)，因為在一次迭代中對小批量的塊進行採樣，因此

可能大於1。可以藉由下式計算探索方針

其中σ_i ^e,t 表示迭代t 中的探索方針，β 是非負實數。如果β =0，則σ_i ^e,t (a |I_i )是均勻隨機探索。如果β ＞0並且在I_i 處對動作a 進行重複採樣，則

趨於變小，因此與未進行探索的動作相比，對該動作採樣的概率可能更小。在經驗上，探索對MCCFR很有幫助。例如，如果一個動作的累計遺憾為負，則其當前策略為零。在這種情況下，該動作將不會在下一次迭代中被採樣。但是，在長時間進行迭代之後，該動作可能比其他動作具有更大的總體遺憾。因此，將需要很多次迭代才能使MCCFR將其負遺憾改變為正值。使用探索時，MCCFR有一定的概率對該動作進行採樣，並在一些迭代後進行探索。 已進行實驗以評估示例性技術，以在三種不同的撲克博弈上加速MCCFR的收斂：單挑無限注翻牌前德州撲克(NLPH)、單挑無限注翻牌德州撲克(NLFH)和單挑無限注德州撲克的河牌圈玩法(HUNL-R)。這些技術包括向量形式的採樣方針、利用反事實值基線的方差減小技術、利用探索的混合採樣方針以及利用跳過機制和貼現更新的混合MCCFR變體。實驗結果表明，所述MCCFR變體獲得了2或3個數量級的改進。

HUNL是不完美資訊博弈解法的主要基線。本實驗中使用的HUNL是年度計算機撲克競賽的標準版本。在HUNL開始時，兩個玩家擁有20000個籌碼。如果沒有一個玩家提前棄牌，HUNL最多可以進行四個下注回合。這四個下注回合分別由翻牌前、翻牌圈、轉牌圈和河牌圈來命名。每局開始時，從52張整付牌中向兩名玩家各發兩張私牌。小盲位的一個玩家首先應將50個籌碼放入底池，大盲位的另一玩家應將100個籌碼放入底池。他們的位置在每局之後交換。每個玩家可以選擇棄牌、跟注或加注。如果一個玩家選擇棄牌，那麼其將輸掉底池中的錢，這局牌就結束了。如果一個玩家選擇跟注，其應該在底池中放置一些籌碼，以使其總籌碼等於對手的籌碼。如果一個玩家選擇加注，其應該比對手增加更多籌碼。在翻牌前回合後，顯示三張公牌，然後出現翻牌下注回合。在此回合之後，將顯示另一張公牌，並且進行第三下注回合。之後，顯示最後一張公牌，然後河牌圈開始。

HUNL包含大約10¹⁶¹ 個資訊集，並且太大而無法遍歷所有節點。為了減少計算量，可以使用諸如動作抽象或紙牌抽象技術之類的抽象技術來實時求解完整HUNL的子博弈。本實驗使用1倍底池，並且全部在每個下注回合中，而無需任何卡牌抽象。

NLPH只有一個下注回合，終點節點的值由均勻隨機公共牌下的預期博弈效用表示，預期博弈效用已預先計算並保存在磁碟上。NLPH包含7.8×10⁴ 個資訊集和1.0×10⁹ 個狀態。NLFH與HUNL相似，不同之處在於僅具有前兩個下注回合(翻牌前和翻牌圈)和三張公共牌。NLFH是一款大型博弈，包含超過4.3×10⁹ 個資訊集和5.8×10¹² 個狀態。我們的實驗中使用的HUNL-R是指HUNL的第四下注回合。在這一回合開始時，每個玩家在底池中有$ 100，並且兩個玩家的範圍由均勻隨機方針指定。HUNL-R包含2.6×10⁴ 個資訊集和3.5×10⁷ 個狀態。

進行了一系列消融研究，涉及不同的採樣方針、探索技術和方差減小技術，並在NLPH上建立了反事實基線。然後，在HUNL-R和超大型NLFH上比較了不同的MCCFR方法。

藉由可利用性評估所有實驗，將可利用性用作標準獲勝率度量。具有較低可利用性的方法更好。納什均衡的可利用性為零。在本文中，可利用性的單位是每博弈百萬個盲注(mbb/g)。它表示一個玩家平均每局撲克贏取幾千分之一的大盲注。對於抽象的大型博弈，可利用性是在抽象的博弈上計算的。在實驗中，

並且γ=0.5。可以使用其他值。實驗遵循MCCFR的典型流程，每個玩家分別遍歷公開樹或博弈樹。圖2-6顯示了實驗中多個MCCFR變體的模擬結果的示例。每個圖的x軸表示迭代次數，每個圖的y軸表示可利用性。在不失一般性的前提下，將強韌採樣用作NLPH撲克上不同MCCFR變體的示例性採樣方案。強韌採樣的一種有效形式是，遍歷者根據均勻隨機方針對1個動作進行採樣，而對手根據其當前策略對1個動作進行採樣。

圖2是示出根據本文的實施例的以不同的採樣方針應用於NLPH的幾種MCCFR變體的收斂性能的雙對數座標曲線圖200。MCCFR是指半向量形式的MCCFR。MCCFR-RCS、MCCFR-MCS、MCCFR-WCS和MCCFR-WAS分別指利用不同MCS、WCS和WAS採樣方針的向量形式的MCCFR變體。結果表明，MCCFR-RCS與半向量形式的MCCFR達到了相似的收斂性，因為RCS從

中隨機選擇了資訊集

，並根據

採樣了一個動作。這種隨機選擇沒有考慮不同資訊集的重要性。除了MCCFR-RCS，其他向量形式的MCCFR變體比半向量形式的MCCFR實現了2或3個數量級的改進。由範圍對每個資訊集加權的WCS和WAS具有比MCS更好的長期性能。注意，通常半向量形式的MCCFR收斂速度快於其數值形式的版本，因此該數值形式的MCCFR的收斂曲線未顯示在圖2中。在其餘實驗中，選擇由兩個玩家的範圍加權的WCS作為採樣方針。

圖3是示出根據本文的實施例的在利用和不利用探索技術的情況下應用於NLPH的幾種MCCFR變體的收斂性能的雙對數座標曲線圖300。具體地，收斂曲線310、320、330和340分別對應於MCCFR、不利用探索的MCCFR-WCS、利用

-貪婪探索的MCCFR-WCS以及利用參照等式(20)描述的示例性探索技術的MCCFR-WCS。圖3顯示了MCCFR-WCS在收斂性能方面優於MCCFR以及利用ϵ-貪婪探索的MCCFR-WCS和利用參照等式(20)描述的示例性探索技術的MCCFR-WCS在收斂性能方面優於MCCFR-WCS。而且，利用參照等式(20)描述的示例性探索技術的MCCFR-WCS的收斂速度比利用ϵ-貪婪探索的MCCFR-WCS的收斂速度甚至更快，因為前一種探索技術考慮了不同動作的採樣頻率。

圖4A示出根據本文的實施例的在利用和不利用不同方差減小技術的情況下應用於NLPH的幾種MCCFR變體的收斂性能的雙對數座標曲線圖400。具體地，收斂曲線410、420、430、440和450分別對應於MCCFR、不利用任何方差減小技術的MCCFR-WCS、利用使用預期效用值基線的方差減小技術的MCCFR-WCS(表示為MCCFR-WCS(ev b))、利用使用參照等式(19)描述的CFV基線的方差減小技術的MCCFR-WCS(表示為MCCFR-WCS(cfv b))、以及利用使用CFV引導基線的方差減小技術的MCCFR-WCS(表示為MCCFR-WCS(cfv b，boot))。

如圖4A所示，當使用方差減小技術(例如，控制變量技術)時，向量形式的MCCFR變體收斂更快。此外，使用CFV基線的方差減小技術(例如，MCCFR-WCS (cfv b)和MCCFR-WCS(cfv b，boot))優於利用預期效用值基線的方差減小技術，MCCFR-WCS(ev b)。此外，利用預期效用值基線的MCCFR需要對每個採樣節點執行1326×1326次加法運算，這比反事實值基線要耗時得多。為了進行公平的比較，在圖4A中提供了基於運行時間的收斂比較。

圖4B是示出根據本文的實施例的在利用和不利用不同方差減小技術的情況下應用於NLPH的幾種MCCFR變體的示例性計算效率的雙對數座標曲線圖405。在實驗中，半向量形式的MCCFR(表示為MCCFR)每千次迭代花費5.9秒；向量形式的MCCFR-WCS(表示為MCCFR-WCS)耗時6.2秒；利用反事實基線的方法(例如MCCFR-WCS(cfv b)或MCCFR-WCS(cfv b，boot))花費6.5秒，而利用預期效用值基線的方法(表示為MCCFR-WCS(ev b))花費48.7秒。

儘管在每次迭代中向量形式的MCCFR比半向量形式的MCCFR採樣了更多的資訊集，但是由於矩陣運算的優勢，它們花費了相似的計算時間。從經驗上講，利用引導基線的方法(MCCFR-WCS(cfv b，boot))的收斂速度比使用參照等式(19)描述的CFV基線的方法(表示為MCCFR-WCS(cfv b))的收斂速度稍快。在其餘的實驗中，選擇利用引導反事實基線的方法作為默認的MCCFR變體。

圖5A-5C是示出根據本文的實施例的藉由對三種不同的撲克博弈NLPH、HUNL-R和NLFH進行外部採樣的幾種MCCFR變體的收斂性能的雙對數座標曲線圖500、530和560。圖5A-5C示出利用所描述的WCS採樣方針和引導基線的MCCFR可以在許多場景(包括超大型博弈NLFH)中顯著改進MCCFR的收斂。改進的MCCFR可以使許多撲克AI受益，並幫助他們在更少的運行時間內實現更好的策略。 圖6A是示出根據本文的實施例的在NLPH上利用和不利用跳過的幾種MCCFR變體的收斂性能的雙對數座標曲線圖600。藉由對向量形式的MCCFR外部採樣進行實驗。在CFR中，累計遺憾初始化為零，當前策略從均勻隨機策略開始。在一些實施例中，證明僅所有迭代內的平均策略組合收斂於納什均衡。在一些實施例中，跳過CFR的前一次迭代可以獲得MCCFR的更快收斂。圖6A示出具有不同跳過迭代的MCCFR變體顯著改進了NLPH上的性能。圖6A示出MCCFR算法在長迭代範圍內在NLPH上的長期性能。跳過之前的10000次迭代(表示為WCS(skip 10k))的方法收斂到0.94-納什均衡。這種可利用性在德州撲克中被認為已經足夠收斂。 圖6B是示出根據本文的實施例的在NLPH上利用和不利用跳過的MCCFR變體的收斂性能的雙對數座標曲線圖650。藉由對向量形式的MCCFR外部採樣進行實驗。作為貼現機制，線性MCCFR利用取決於迭代t 的值對遺憾和平均策略加權。在實驗中，此貼現機制與指定權重為t^w 的向量形式的MCCFR結合使用。圖6B顯示，權重為t^w (其中w = 1和w = 2，表示為Linear WCS(w = 1)和Linear WCS(w = 2))的線性MCCFR與利用貼現的向量形式的MCCFR(表示為WCS)相比，改進了收斂性能。

圖7是根據本文的實施例的用於執行蒙特卡洛反事實遺憾最小化(MCCFR)以確定用於軟體應用的動作選擇方針的處理700的示例的流程圖。處理700可以是利用上述採樣方案的MCCFR算法的示例。

圖7所示的示例性處理700可以被修改或重新配置為包括附加的、更少的或不同的操作，其可以以所示的順序或以不同的順序執行。在某些情況下，例如可以重複或迭代一個或多個操作，直到達到終止條件為止。在一些實施方式中，圖7中所示的一個或多個單獨操作可以被執行為多個單獨的操作，或者圖7中所示的一個或多個操作子集可以被組合並且被執行為單個操作。

在一些實施例中，處理700可以以迭代方式執行，例如，藉由執行兩次或更多次迭代。在一些實施例中，處理700可以用在自動控制、機器人技術或涉及動作選擇的任何其他應用中。在一些實施例中，處理700可以由執行設備執行，用於生成動作選擇方針(例如，策略)，以在包括執行設備以及一個或多個其他設備的環境中完成任務(例如，找到納什均衡)。在一些實施例中，生成動作選擇方針可以包括處理700的一些或全部操作，例如，藉由在702處初始化動作選擇方針並在750處藉由迭代更新動作選擇方針。執行設備可以在環境中執行處理700，以根據動作選擇方針控制執行設備的操作。

在一些實施例中，執行設備可以包括位於一個或多個位置並且根據本文進行了適當程式化的資料處理裝置，諸如一個或多個計算機的系統。例如，經過適當程式化的圖10的計算機系統1000可以執行處理700。執行設備可以與執行方或玩家相關聯。執行方或玩家以及一個或多個其他參與方(例如，與一個或多個其他設備相關聯)可以是環境中的參與方或玩家，例如，以在執行方與一個或多個其他參與方之間的策略互動中進行策略搜索。

在一些實施例中，可以藉由涉及兩個或更多個玩家的不完美資訊博弈(IIG)來對環境進行建模。在一些實施例中，可以例如由應用支持的執行方執行處理700以求解IIG。IIG可以表示一個或多個現實場景，例如資源分配、產品/服務推薦、網路攻擊預測及/或預防、交通路線規劃、欺詐管理等，其中涉及兩個或多個參與方，每個參與方可能具有關於另一參與方的決策的不完全或不完美的資訊。作為示例，IIG可以表示至少涉及第一玩家和第二玩家的協作產品服務推薦服務。第一玩家可以是例如具有客戶(或用戶)資訊、產品和服務資訊、客戶的購買歷史等的在線零售商。第二玩家可以是例如具有該客戶的社交網路資料的社交網路平臺、擁有該客戶的財務資訊的銀行或其他金融機構、汽車經銷商或在預測和向客戶推薦產品和服務時具有關於該客戶的偏好、需求、財務狀況、位置等的客戶資訊的任何其他參與方。第一玩家和第二玩家可能各自具有該玩家不想與他人共享的專有資料。第二玩家可以在不同時間向第一玩家僅提供部分資訊。這樣，第一玩家可能僅具有對第二玩家的資訊的有限存取權。在一些實施例中，可以執行處理700以向具有第二參與方的有限資訊的參與方進行推薦，從而利用有限資訊規劃路線。

在702處，第一次迭代(即，t=1迭代)中，對動作選擇方針(例如，策略

)初始化。在一些實施例中，動作選擇方針可以包括或以其他方式指定執行設備(例如，執行 處理700的執行設備)從一個狀態(例如，當前狀態i)下的多個可能動作中選擇一個動作(例如，

)的相應概率(例如，

)。當前狀態是由執行設備在前一狀態下採取的前一動作導致的，並且當執行設備在當前狀態下時，多個可能動作中的每個動作如果被執行設備執行都導致相應的下一狀態。

在一些實施例中，狀態可以由博弈樹的節點(例如，博弈樹100的非終點節點123、127、143b或147b或者終點節點143a、153a、153b、143c、143d、147a、157a、157b、147c或147d)表示。在一些實施例中，狀態可以是由公開樹的節點(例如，公開樹150的非終點節點125、135a、135b或145b，或者終點節點145a、145c、145d、155a或155b)表示的公開狀態。

在一些實施例中，可以例如基於現有策略、均勻隨機策略(例如，基於均勻概率分佈的策略)或另一策略(例如，基於不同概率分佈的策略)來初始化該策略。例如，如果系統從現有的CFR方法(例如，原始CFR或MCCFR方法)熱啟動，則可以從現有策略組合中初始化迭代策略，以克隆現有的遺憾和策略。

在704處，確定是否滿足收斂條件。MCCFR通常包括多次迭代。收斂條件可用於確定是繼續還是終止迭代。在一些實施例中，收斂條件可以基於策略σ 的可利用性。根據可利用性的定義，可利用性應大於或等於0。越小的可利用性表示越好的策略。也就是說，經過足夠的迭代後，收斂策略的可利用性應該接近0。例如，在撲克中，當可利用性小於1時，時間平均策略被認為是一種好的策略，並且確定滿足收斂條件。在一些實施例中，收斂條件可以基於預定次數的迭代。例如，在小型博弈中，迭代可以藉由可利用性輕鬆確定。即，如果可利用性足夠小，則處理700可以終止。在大型博弈中，可利用性很複雜，並且通常可以指定較大的迭代參數。每次迭代後，都可以獲得新的策略組合，它比舊的策略組合更好。例如，在大型博弈中，處理700可以在足夠次數的迭代之後終止。

如果滿足收斂條件，則無需進一步迭代。處理700進行到706。根據當前動作選擇方針向量中的每個當前動作選擇方針來控制執行設備的操作。例如，可以將當前迭代中的每個當前動作選擇方針或t次迭代中的平均動作選擇方針作為控制命令輸出，以控制方向、速度、距離或者引擎、馬達、閥、致動器、加速器、制動器或自動駕駛汽車或其他應用中的其他設備的其他操作中的一個或多個。如果不滿足收斂條件，則將t增加1，並且處理700進行到下一次迭代，其中t＞1。

在當前迭代(例如，第t次迭代)中，在710處，識別執行設備在一個狀態下的多個可能動作。在一些實施例中，如上所述，狀態可以是由公開樹的節點(例如，公開樹150的非終點節點125、135a、135b或145b或者終點節點145a、145c、145d、155a或155b)表示的公開狀態。狀態可以對應於資訊集向量，並且資訊集向量中的每個資訊集包括由執行設備採取的導致該狀態的動作序列。例如，如圖1B所示，由公開樹150中的節點表示的狀態可以維護資訊集向量

= [I_{i 1} ,I_{i 2} ,I_{i 3} ]。

在一些實施例中，狀態對應於公開序列，公開序列包括執行設備以及一個或多個其他設備公開已知的一個或多個動作，其軌跡從初始狀態(例如，公開樹的根節點)開始並以該狀態結束。例如，節點155b的狀態對應於公開序列(例如，公開序列[A_1a, A_2b , A_3b, ])，該公開序列包括從根節點125到節點155b，執行設備公開已知的一個或多個動作(例如，A_1a 和A_3b )以及一個或多個其他設備的公開已知的一個或多個動作(例如A_2b )。資訊集向量中的每個資訊集都包括公開序列。在一些實施例中，資訊集向量中的每個資訊集還包括沿從初始狀態(例如，公開樹的根節點)開始到該狀態結束的軌跡上的一個或多個非公開動作(例如，由執行設備或機會採取的)。例如，在節點155b的狀態下的資訊集向量中的每個資訊集包括公開序列[A_1a, A_2b , A_3b, ]，以及相應的非公開動作(例如，機會發牌J、Q、K)。

如圖1B所示，利用對應的資訊集向量，由表示環境的公開樹的節點表示的狀態與該狀態下的多個可能動作相關聯或相對應。例如，如公開樹150中所示的節點125與該狀態下導致相應的下一狀態(例如，節點135a和節點135b)的多個動作(例如，動作A_1a 和A_1b )相關聯。作為另一示例，執行設備的另一狀態(例如，節點145b)與該狀態下導致相應的下一狀態(例如，節點155a和節點155b)的多個動作(例如，動作A_3a 和A_3b )相關聯，其中節點145b是由執行設備在前一狀態(例如，節點135a)下採取的前一動作A_2b 導致的。

在一些實施例中，例如藉由讀取表示環境的資料結構(例如，IIG的公開樹)來識別執行設備在該狀態下的多個可能動作。資料結構可以在環境的每個狀態下包括相應的多個可能動作。

在720處，識別該狀態下的當前動作選擇方針向量(例如，當前策略的向量

= [σ_{i 1} ,σ_{i 2} ,σ_{i 3} ])。在一些實施例中，該狀態下的當前動作選擇方針向量是當前迭代t中該狀態下的動作選擇方針(但是為簡單起見，省略了迭代t的注釋)。在一些實施例中，當前動作選擇方針向量中的每個當前動作選擇方針對應於資訊集向量(例如，資訊集向量

= [I_{i 1} ,I_{i 2} ,I_{i 3} ])中的資訊集。動作選擇方針指定從該狀態下的多個可能動作中選擇一動作的相應概率。例如，動作選擇方針σ_{i 1} 對應於該狀態下的資訊集向量

中的I_{i 1} 。如果狀態是圖1B中的公開樹150的節點125，則動作選擇方針σ_{i 1} 指定在當前迭代t 中根據動作選擇方針σ_{i 1} 在該狀態下選擇動作A_1a 的概率和選擇動作A_1b 的概率。

在一些實施例中，藉由在702處識別該狀態下當前動作選擇方針的初始向量，或者藉由例如根據750，識別前一次迭代中該狀態下的當前動作選擇方針的更新向量，來識別當前迭代中該狀態下的當前動作選擇方針向量。

在730處，基於該狀態下的當前動作選擇方針向量來計算採樣方針，其中，採樣方針指定與該狀態下的多個可能動作中的每個動作相對應的相應採樣概率。在一些實施例中，採樣方針包括在該狀態下的多個動作上的概率分佈。

注意，採樣方針不同於動作選擇方針(例如，當前動作選擇方針)，儘管兩者都可以是在一個狀態下的多個可能動作的概率分佈。採樣方針用於MCCFR中，以確定在蒙特卡洛方法中對環境中的哪些軌跡或路徑進行採樣，而不是遍歷環境中所有可能的軌跡或路徑。採樣方針被用來計算採樣終點軌跡(即動作序列)的概率，其用於計算採樣反事實值(也稱為估計反事實值)以近似等於基於遍歷環境中所有可能的軌跡或路徑計算出的(實際)反事實值。

另一方面，無論是否使用採樣，動作選擇方針都可以是這樣的策略：其指定及/或包括在該策略下從狀態h 下的多個可能動作中選擇動作a 的相應概率(例如σ_i (a |h ))，例如，以完成任務並接近納什均衡。可以在CFR算法的每次迭代中更新動作選擇方針。在一些實施例中，CFR算法的輸出可以是動作選擇方針(或多次迭代的平均動作選擇方針)，該動作選擇方針指定(根據如參照等式(2)所描述的最佳響應的策略)從IIG的每個狀態下的多個可能動作中選擇一個動作的相應概率，使得玩家可以接近或達到納什均衡。

在一些實施例中，在MCCFR中，一旦根據採樣方針採樣了動作，則可以基於遺憾、CFV以及基於採樣動作計算出的其他值中的一個或多個來更新動作選擇方針。在一些實施例中，採樣方針獨立於動作選擇方針，例如，在數值形式的MCCFR中。在向量形式的MCCFR中，一個狀態下存在多個動作選擇方針(例如，對應於資訊集向量的動作選擇方針向量)。在一些實施例中，採樣方針可以獨立於動作選擇方針(例如，根據均勻分佈或另一指定的分佈)。在一些實施例中，可以基於與資訊集向量相對應的多個動作選擇方針來計算採樣方針。

在一些實施例中，可以基於該狀態下的當前動作選擇方針向量來計算採樣方針，例如，根據隨機當前策略(RCS)、平均當前策略(MCS)、加權當前策略(WCS)、加權平均策略(WAS)或將採樣方針與該狀態下的多個當前動作選擇方針相關聯的任何其他方法。

在一些實施例中，基於執行設備在該狀態下的當前動作選擇方針向量來計算採樣方針包括：例如，根據等式(13)，將與該狀態下的多個可能動作中的每個動作相對應的採樣概率計算為在資訊集向量上在該狀態下的多個可能動作中的每個可動作的當前動作選擇方針的平均值。

在一些實施例中，基於執行設備在該狀態下的當前動作選擇方針向量來計算採樣方針包括：基於該狀態下的多個可能動作中的每個動作的當前動作選擇方針以及資訊集向量的相應到達概率來計算與該狀態下的多個可能動作中的每個動作對應的採樣概率。在一些實施例中，基於該狀態下的多個可能動作中的每個動作的當前動作選擇方針以及資訊集向量的相應到達概率來計算與該狀態下的多個可能動作中的每個動作對應的採樣概率，包括：例如，根據等式(14)，基於經資訊集向量的相應到達概率加權的該狀態下的多個可能動作中的每個動作的當前動作選擇方針的總和，計算與該狀態下的多個可能動作中的每個動作相對應的採樣概率。

在一些實施例中，基於執行設備在該狀態下的當前動作選擇方針向量來計算採樣方針包括：基於該狀態下的多個可能動作中的每個動作的平均動作選擇方針以及資訊集向量的相應到達概率來計算與該狀態下的多個可能動作中的每個動作相對應的採樣概率。在一些實施例中，基於該狀態下的多個可能動作中的每個動作的平均動作選擇方針以及資訊集向量的相應到達概率來計算與該狀態下的多個可能動作中的每個動作相對應的採樣概率，包括：例如根據等式(15)，基於經資訊集向量的相應到達概率加權的該狀態下的多個可能動作中的每個動作的平均動作選擇方針的總和來計算與該狀態下的多個可能動作中的每個動作相對應的採樣概率。

在740處，根據採樣方針中指定的該狀態下的多個可能動作中的一個動作的採樣概率，對該動作進行採樣。例如，對於圖1B中博弈樹150的節點135a處的玩家1，採樣方針可以包括對在節點135a的狀態下的兩個可能動作A_1a 和A_1b 中的動作A_1a 進行採樣的採樣概率(例如概率為0.3)，以及對節點135a的狀態下的兩個可能的動作A_1a 和A_1b 中的動作A_1b 進行採樣的採樣概率(例如概率為0.7)。在節點135a處，相比於動作A_1a ，以更高的概率0.7對動作A_1b 採樣。採樣動作A_1b 可用於針對下一次迭代更新當前動作選擇方針。

在750處，基於該動作(例如，上述示例中的採樣動作A_1b )來更新執行設備在該狀態下的當前動作選擇方針向量中的每個當前動作選擇方針。在一些實施例中，基於該動作來更新執行設備在該狀態下的當前動作選擇方針向量中的每個當前動作選擇方針包括：例如，根據等式(4)-(12)中的一些或全部，基於該動作執行蒙特卡洛反事實遺憾最小化(MCCFR)。例如，基於該動作更新執行設備在該狀態下的當前動作選擇方針向量中的每個當前動作選擇方針包括：基於動作的採樣概率計算採樣終點動作序列的概率(例如，

)，採樣終點動作序列包括該動作和完成任務的終點狀態；基於採樣終點動作序列的概率計算動作的採樣反事實值(如根據式(9)；基於動作的採樣反事實值計算動作的遺憾值(例如，根據等式(10)- (12)的部分或全部)；以及基於動作的遺憾值(例如，根據基於等式(7)的遺憾匹配或遺憾匹配+)來更新執行設備在該狀態下的當前動作選擇方針向量中的每個。在一些實施例中，例如，根據等式(8)，可以計算當前迭代之後的平均策略

。

在750之後，處理700可以返回到704以確定是否滿足收斂條件。在一些實施例中，反應於確定滿足收斂條件，基於動作選擇方針來控制執行設備的操作。在一些實施例中，反應於確定滿足收斂條件，可以例如根據等式(8)計算每個狀態下跨所有迭代(例如，從第一迭代到當前迭代)的平均動作選擇方針。在一些實施例中，平均動作選擇方針可以用作處理700的輸出，例如，用作計算出的納什均衡。

在一些實施例中，動作選擇方針可以用作軟體實現應用的輸出，以例如藉由基於動作選擇方針在多個可能動作中選擇概率最高的動作來自動控制執行設備在每個狀態下的動作。例如，環境包括交通路線規劃環境，應用支持的執行設備包括計算機輔助車輛，動作選擇方針包括用於控制計算機輔助車輛的方向的路線選擇方針，並且根據動作選擇方針控制執行設備的操作包括根據路線選擇方針控制計算機輔助車輛的方向。控制計算機輔助車輛的操作可以包括控制節氣門、轉向、制動、導航、引擎模式中的一個或多個以實現方向、速度、在路線選擇方針中指定的根據處理700生成的其他參數以完成例如，在包括共享道路的其他計算機輔助車輛的環境中到達所需目的地的任務。

圖8是根據本文的實施例的用於執行蒙特卡洛反事實遺憾最小化(MCCFR)以確定用於軟體應用的動作選擇方針的另一處理800的示例的流程圖。處理800可以是利用如上所述的使用探索的混合採樣方案的MCCFR算法的示例。注意，處理800可以應用於數值形式MCCFR、半向量形式MCCFR和向量形式MCCFR。在一些實施例中，例如，可以藉由用處理800中的混合採樣方針替換處理700中的採樣方針，將處理800與處理700結合。

圖8所示的示例性處理800可以被修改或重新配置為包括附加的、更少的或不同的操作，其可以以所示的順序或以不同的順序執行。在某些情況下，例如可以重複或迭代一個或多個操作，直到達到終止條件為止。在一些實施方式中，圖8中所示的一個或多個單獨操作可以被執行為多個單獨的操作，或者可以將圖8中所示的一個或多個操作子集組合為單個操作並作為單個操作被執行。

在一些實施例中，處理800可以以迭代的方式執行，例如，藉由執行兩次或更多次迭代。在一些實施例中，處理800可以用於自動控制、機器人技術或涉及動作選擇的任何其他應用中。在一些實施例中，處理800可以由執行設備執行，用於生成動作選擇方針(例如，策略)，以在包括執行設備以及一個或多個其他設備的環境中完成任務(例如，找到納什均衡)。在一些實施例中，生成動作選擇方針可以包括處理800中的一些或全部操作，例如，藉由在802處初始化動作選擇方針並在850處藉由迭代更新動作選擇方針。執行設備可以在環境中執行處理800，以根據動作選擇方針控制執行設備的操作。

在一些實施例中，執行設備可以包括位於一個或多個位置並且根據本文進行了適當程式化的資料處理裝置，諸如一個或多個計算機的系統。例如，經過適當程式化的圖10的計算機系統1000可以執行處理800。執行設備可以與執行方或玩家相關聯。執行方或玩家以及一個或多個其他參與方(例如，與一個或多個其他設備相關聯)可以是環境中的參與方或玩家，例如，以在執行方與一個或多個其他參與方之間的策略互動中進行策略搜索。

在一些實施例中，可以藉由涉及兩個或更多個玩家的不完美資訊博弈(IIG)對環境進行建模。在一些實施例中，處理800可以例如由應用支持的執行方執行以求解IIG。IIG可以表示一個或多個現實場景，例如資源分配、產品/服務推薦、網路攻擊預測及/或預防、交通路線規劃、欺詐管理等，其中涉及兩個或更多個參與方，每個參與方可能具有關於另一參與方的決策的不完美或不完全的資訊。作為示例，IIG可以表示至少涉及第一玩家和第二玩家的協作產品服務推薦服務。第一玩家可以是例如具有客戶(或用戶)資訊、產品和服務資訊、客戶的購買歷史等的在線零售商。第二玩家可以是例如具有該客戶的社交網路資料的社交網路平臺、擁有該客戶的財務資訊的銀行或其他金融機構、汽車經銷店或在預測和向客戶推薦產品和服務時具有關於該客戶的偏好、需求、財務狀況、位置等的客戶資訊的任何其他參與方。第一玩家和第二玩家可能各自具有該玩家不想與他人共享的專有資料。第二玩家可以在不同時間向第一玩家僅提供部分資訊。這樣，第一玩家可能僅具有對第二玩家的資訊的有限存取權。在一些實施例中，可以執行處理800以向具有第二參與方的有限資訊的參與方進行推薦，從而利用有限資訊規劃路線。

在802處，類似於702，在第一次迭代(即，t=1迭代)中，對動作選擇方針(例如，策略

)初始化。在一些實施例中，動作選擇方針可以包括或以其他方式指定執行設備(例如，執行處理800的執行設備的設備)從一個狀態(例如，當前狀態i)下的多個可能動作中選擇一個動作(例如，

)的相應概率(例如，

)。當前狀態是由執行設備在前一狀態下採取的前一動作導致的，並且當執行設備在當前狀態下時，多個可能動作中的每個動作如果被執行設備執行都導致相應的下一狀態。

在一些實施例中，狀態可以由博弈樹的節點(例如，博弈樹100的非終點節點123、127、143b或147b或者終點節點143a、153a、153b、143c、143d、147a、157a、157b、147c或147d)表示。在一些實施例中，狀態可以是由公開樹的節點(例如，公開樹150的非終點節點125、135a、135b或145b，或者終點節點145a、145c、145d、155a或155b)表示的公開狀態。

在一些實施例中，可以例如基於現有策略、均勻隨機策略(例如，基於均勻概率分佈的策略)或另一策略(例如，基於不同概率分佈的策略)來初始化該策略。例如，如果系統從現有的CFR方法(例如，原始CFR或MCCFR方法)熱啟動，則可以從現有策略組合中初始化迭代策略，以克隆現有的遺憾和策略。

在804處，類似於704，確定是否滿足收斂條件。MCCFR通常包括多次迭代。收斂條件可用於確定是繼續還是終止迭代。在一些實施例中，收斂條件可以基於策略σ的可利用性。根據可利用性的定義，可利用性應大於或等於0。越小的可利用性表示越好的策略。也就是說，經過足夠的迭代後，收斂策略的可利用性應該接近0。例如，在撲克中，當可利用性小於1時，時間平均策略被認為是一種好的策略，並且確定滿足收斂條件。在一些實施例中，收斂條件可以基於預定次數的迭代。例如，在小型博弈中，迭代可以藉由可利用性輕鬆確定。即，如果可利用性足夠小，則處理800可以終止。在大型博弈中，可利用性很複雜，並且通常可以指定較大的迭代參數。每次迭代後，都可以獲得新的策略組合，它比舊的策略組合更好。例如，在大型博弈中，處理800可以在足夠次數的迭代之後終止。

如果滿足收斂條件，則無需進一步迭代。處理800進行到806，並且根據動作選擇方針來控制執行設備的操作。例如，可以將當前迭代中的動作選擇方針或t次迭代中的平均動作選擇方針作為控制命令輸出，以控制方向、速度、距離或者引擎、馬達、閥、致動器、加速器、制動器或自動駕駛汽車或其他應用中的其他設備的其他操作中的一個或多個。如果不滿足收斂條件，則將t增加1，並且處理800進行到下一次迭代，其中t＞1。

在當前迭代(例如，第t次迭代)中，在810處，識別執行設備在一個狀態下的採樣方針。採樣方針指定對該狀態下的多個可能動作中的每個動作進行採樣的相應採樣概率。在一些實施例中，採樣方針包括在該狀態下的多個可能動作上的第一概率分佈。採樣方針可以是關於圖7描述的採樣方針中的任何一個。例如，採樣方針可以是均勻採樣方針、隨機採樣方針、指定的隨機方針、隨機當前策略(RCS)、平均當前策略(MCS)、加權當前策略(WCS)、加權平均策略(WAS)或任何其他採樣方針中的一個或多個。在一些實施例中，例如根據參照處理700的730所描述的示例性技術來識別執行設備在該狀態下的採樣方針。

在820處，識別執行設備在該狀態下的探索方針。探索方針指定與該狀態下的多個可能動作中的每個動作相對應的相應探索概率，其中，探索概率與在該狀態下的多個可能動作中的每個動作已被採樣的次數負相關。在一些實施例中，探索方針包括在該狀態下的多個可能動作上的第二概率分佈。

在一些實施例中，例如，藉由根據等式(22)計算多個可能動作中的每個動作的探索概率，來識別執行設備在該狀態下的探索方針，其中，i 表示執行設備的標識(例如，與玩家i 相關聯)；I_i 表示狀態的資訊集；

表示在該狀態下的多個可能動作；a 表示在該狀態下的多個可能動作之一；t 表示當前迭代；∆C^t (a |I_i )表示直到迭代t ，在該狀態下已對動作a 採樣的次數；以及σ_i ^e,t

表示在迭代t 中，在該狀態下探索動作a 的探索方針；以及β 是非負實數。

在830處，基於採樣方針和探索方針來計算混合採樣方針。在一些實施例中，基於採樣方針和探索方針來計算混合採樣方針包括：基於在該狀態下的多個可能動作中的每個動作的採樣概率與該狀態下的多個可能動作中的每個動作的探索概率的加權和，計算該狀態下的多個可能動作中的每個動作的概率。在一些實施例中，基於採樣方針和探索方針來計算混合採樣方針包括：根據等式(20)，計算該狀態下的多個可能動作中的每個動作的概率，其中，I_i 表示狀態的資訊集；a 表示該狀態下的多個可能動作之一；σ_i ^se (a |I_i )表示在該狀態下對動作a 進行採樣的混合採樣方針；σ_i ^s (a |I_i )表示在該狀態下對動作a 進行採樣的採樣方針；σ_i ^e (a |I_i )表示在該狀態下探索動作a 的探索方針；以及α ∈ [0, 1]表示控制探索權重的因子。

在840處，根據在混合採樣方針中指定的該狀態下的多個可能動作中的動作的採樣概率，對該動作進行採樣。例如，對於圖1B中博弈樹150的節點135a處的玩家1，混合採樣方針可以包括對節點135a的狀態下的兩個可能動作A_1a 和A_1b 中的動作A_1a 進行採樣的混合採樣概率(例如概率為0.2)，以及對節點135a的狀態下的兩個可能動作A_1a 和A_1b 中的動作A_1b 進行採樣的混合採樣概率(例如概率為0.8)。在節點135a處，與動作A_1a 相比，可以以0.8的更高概率來對動作A_1b 採樣。採樣動作A_1b 可用於針對下一次迭代更新動作選擇方針。

在842處，反應於根據混合採樣方針對該狀態下的多個可能動作中的一個動作進行採樣，增加在該狀態下對該動作採樣的次數。在一些實施例中，在該狀態下對該動作採樣的次數包括直到當前迭代為止在該狀態下對該動作已進行採樣的次數(例如，∆C^t (a |I_i ))。

在844處，減小與該狀態下的多個可能動作中的該動作相對應的探索概率以計算下一次迭代(例如，第(t+1)次迭代)中的混合採樣方針，使得該動作在下一次迭代中被採樣的概率較低。在一些實施例中，例如根據等式(22)或其他函數，參照在該狀態下對該動作已採樣的次數，減小執行設備在該狀態下的探索方針。

在850處，藉由基於該動作來執行蒙特卡羅反事實遺憾最小化(MCCFR)，從而基於該動作(例如，在840中描述的示例中的採樣動作A_lb )更新執行設備在該狀態下的動作選擇方針。動作選擇方針指定在該狀態下的多個可能動作中選擇一個動作的相應概率以在環境中完成任務。動作選擇方針可以是例如執行設備在該狀態下的當前策略。例如，在MCCFR中，一旦根據採樣方針對動作進行了採樣，則可以基於遺憾、CFV和其他基於採樣動作計算出的值中的一個或多個來更新動作選擇方針。

在一些實施例中，基於該動作來更新執行設備在該狀態下的動作選擇方針包括：例如根據等式(4)-(12)中的一些或全部，基於該動作來執行MCCFR。例如，基於該動作來執行蒙特卡洛反事實遺憾最小化(MCCFR)包括：基於該動作的混合採樣概率計算採樣終點動作序列的概率(例如，

)，該採樣終點動作序列包括該動作和完成任務的終點狀態；基於採樣終點動作序列的概率來計算動作的採樣反事實值(例如，根據等式(9))；基於動作的採樣反事實值來計算動作的遺憾值(例如，根據等式(10)-(12)中的一些或全部)；以及基於動作的遺憾值來更新執行設備在該狀態下的動作選擇方針(例如，根據基於等式(8)的遺憾匹配或遺憾匹配+)。在一些實施例中，例如，根據等式(8)，可以計算當前迭代之後的平均策略

。

在850之後，處理800可以返回到804以確定是否滿足收斂條件。在一些實施例中，反應於確定滿足收斂條件，基於動作選擇方針來控制執行設備的操作。在一些實施例中，反應於確定滿足收斂條件，可以計算每個狀態下跨所有迭代(例如，從第一迭代到當前迭代)的平均動作選擇方針。例如，根據等式(8)。在一些實施例中，平均動作選擇方針可以用作處理800的輸出，例如，用作計算出的納什均衡。

在一些實施例中，動作選擇方針可以用作軟體實現應用的輸出，以例如藉由基於動作選擇方針在多個可能動作中選擇概率最高的動作來自動控制執行設備在每個狀態下的動作。例如，環境包括交通路線規劃環境，應用支持的執行設備包括計算機輔助車輛，動作選擇方針包括用於控制計算機輔助車輛的方向的路線選擇方針，並且根據動作選擇方針控制執行設備的操作包括根據路線選擇方針控制計算機輔助車輛的方向。

圖9是根據本文的實施例的用於執行蒙特卡洛反事實遺憾最小化(MCCFR)以確定用於軟體應用的動作選擇方針的另一處理900的示例的流程圖。處理900可以是利用如上所述的使用CFV基線的方差減小的MCCFR算法的示例。注意，處理900可以應用於數值形式、半向量形式和向量形式的MCCFR。在一些實施例中，處理900可以與處理700及/或處理800結合以進一步改進MCCFR的收斂性能。

圖9所示的示例性處理900可以被修改或重新配置為包括附加的、更少的或不同的操作，其可以以所示的順序或以不同的順序執行。在某些情況下，例如可以重複或迭代一個或多個操作，直到達到終止條件為止。在一些實施方式中，圖9中所示的一個或多個單獨操作可以被執行為多個單獨的操作，或者可以將圖9中所示的一個或多個操作子集組合為單個操作並作為單個操作被執行。

在一些實施例中，處理900可以以迭代方式執行，例如，藉由執行兩次或更多次迭代。在一些實施例中，處理900可以用於自動控制、機器人技術或涉及動作選擇的任何其他應用中。在一些實施例中，處理900可以由執行設備執行，用於生成動作選擇方針(例如，策略)，以在包括執行設備以及一個或多個其他設備的環境中完成任務(例如，找到納什均衡)。在一些實施例中，生成動作選擇方針可以包括處理900的一些或全部操作，例如，藉由在902處初始化動作選擇方針並在916處藉由迭代更新動作選擇方針。執行設備可以在環境中執行處理900，以根據動作選擇方針控制執行設備的操作。

在一些實施例中，執行設備可以包括位於一個或多個位置並且根據本文進行了適當程式化的資料處理裝置，諸如一個或多個計算機的系統。例如，經過適當程式化的圖10的計算機系統1000可以執行處理900。執行設備可以與執行方或玩家相關聯。執行方或玩家以及一個或多個其他參與方(例如，與一個或多個其他設備相關聯)可以是環境中的參與方或玩家，例如，以在執行方與一個或多個其他參與方之間的策略互動中進行策略搜索。

在一些實施例中，可以藉由涉及兩個或更多個玩家的不完美資訊博弈(IIG)來對環境進行建模。在一些實施例中，處理900可以例如由應用支持的執行方執行以求解IIG。IIG可以表示一個或多個現實場景，例如資源分配、產品/服務推薦、網路攻擊預測及/或預防、交通路線規劃、欺詐管理等，其中涉及兩個或更多個玩家，每個參與方可能具有關於另一參與方的決策的不完美或不完全的資訊。作為示例，IIG可以表示至少涉及第一玩家和第二玩家的協作產品服務推薦服務。第一玩家可以是例如具有客戶(或用戶)資訊、產品和服務資訊、客戶的購買歷史等的在線零售商。第二玩家可以是例如具有該客戶的社交網路資料的社交網路平臺、擁有該客戶的財務資訊的銀行或其他金融機構，汽車經銷店或在預測和向客戶推薦產品和服務時具有關於該客戶的偏好、需求、財務狀況、位置等的客戶資訊的任何其他參與方。第一玩家和第二玩家可能各自具有該玩家不想與他人共享的專有資料。第二玩家可以在不同時間向第一玩家僅提供部分資訊。這樣，第一玩家可能僅具有對第二玩家的資訊的有限存取權。在一些實施例中，可以執行處理900以向具有第二參與方的有限資訊的參與方進行推薦，從而利用有限資訊規劃路線。

在902處，類似於702，在第一次迭代(即，t=1迭代)中，對動作選擇方針(例如，策略

)初始化。在一些實施例中，動作選擇方針可以包括或以其他方式指定執行設備(例如，執行處理900的執行設備)從一個狀態(例如，當前狀態i)下的多個可能動作中選擇一個動作(例如，

)的相應概率(例如，

)。當前狀態是由執行設備在前一狀態下採取的前一動作導致的，並且當執行設備在當前狀態下時，多個可能動作中的每個動作如果被執行設備執行都導致相應的下一狀態。

在一些實施例中，狀態可以由博弈樹的節點(例如，博弈樹100的非終點節點123、127、143b或147b或者終點節點143a、153a、153b、143c、143d、147a、157a、157b、147c或147d)。在一些實施例中，狀態可以是由公開樹的節點(例如，公開樹150的非終點節點125、135a，135b或145b，或者終點節點145a、145c、145d、155a或155b)表示的公開狀態。

在一些實施例中，可以例如基於現有策略、均勻隨機策略(例如，基於均勻概率分佈的策略)或另一策略(例如，基於不同概率分佈的策略)來初始化該策略。例如，如果系統從現有的CFR方法(例如，原始CFR或MCCFR方法)熱啟動，則可以從現有策略組合中初始化迭代策略，以克隆現有的遺憾和策略。

在904處，類似於704，確定是否滿足收斂條件。MCCFR通常包括多次迭代。收斂條件可用於確定是繼續還是終至迭代。在一些實施例中，收斂條件可以基於策略σ的可利用性。根據可利用性的定義，可利用性應大於或等於0。越小的可利用性表示越好的策略。也就是說，經過足夠的迭代後，收斂策略的可利用性應該接近0。例如，在撲克中，當可利用性小於1時，時間平均策略被認為是一種好的策略，並且確定滿足收斂條件。在一些實施例中，收斂條件可以基於預定次數的迭代。例如，在小型博弈中，迭代可以藉由可利用性輕鬆確定。即，如果可利用性足夠小，則處理900可以終止。在大型博弈中，可利用性很複雜，通常可以指定較大的迭代參數。每次迭代後，都可以獲得一個新的策略組合，它比舊的策略組合更好。例如，在大型博弈中，處理900可以在足夠次數的迭代之後終止。

如果滿足收斂條件，則無需進一步迭代。處理900進行到922，並且根據動作選擇方針來控制執行設備的操作。在一些實施例中，動作選擇方針包括執行設備在非終點狀態下的動作選擇方針。在一些實施例中，根據動作選擇方針來控制執行設備的操作，包括基於非終點狀態下的動作選擇方針來控制執行設備在非終點狀態下的操作，以用於下一次迭代。在一些實施例中，可以將當前迭代中的動作選擇方針或t次迭代中的平均動作選擇方針作為控制命令輸出，以控制方向、速度、距離或者引擎、馬達、閥、致動器、加速器、制動器或自動駕駛汽車或其他應用中的其他設備的其他操作中的一個或多個。如果不滿足收斂條件，則將t增加1，並且處理900進行到下一次迭代，其中t＞1。

在一些實施例中，處理900的每次迭代可以包括用於計算CFV並更新不同狀態的動作選擇方針的自下而上的處理。例如，處理900可以從終點狀態(例如，圖1A中的博弈樹100的葉子節點或終點節點143a、153a、153b、143c、143d、147a、157a、157b、147c或147d開始，或者圖1B中的公開樹150的終點節點145a、145c、145d、155a或155b)並向上移動到初始狀態(例如，圖1A中的博弈樹100的根節點110或圖1B中的公開樹150的根節點125)。

在當前迭代(例如，第t次迭代)中，在905處，例如根據等式(18)的上方等式(或第一等式)，基於執行設備在終點狀態下的收益以及一個或多個其他設備到達終點狀態的到達概率計算執行設備在完成任務的終點狀態下的反事實值(CFV)(例如，

)。

終點狀態(例如，圖1B中的終點節點155b)是由動作序列(例如，動作序列[A_1a, A_2b, A_3b ])導致的，動作序列包括執行設備在多個非終點狀態下採取的動作(例如A_1a 和A_3b )以及一個或多個其他設備在多個非終點狀態下採取的動作(例如A_2b )。在一些實施例中，多個非終點狀態中的每個具有一個或多個子狀態。例如，非終點節點125具有兩個子狀態，即節點135a和135b；非終點節點135a具有兩個子狀態，即節點145a和145b；以及非終點節點145b具有兩個子狀態，即節點155a和155b。

在一些實施例中，一個或多個其他設備的到達終點狀態的到達概率包括由到達終點狀態的一個或多個其他設備所採取的動作的概率的乘積。例如，如果執行設備對應於玩家1，則一個或多個其他設備(例如，對應於玩家2)到達終點狀態(例如，終點節點155b)的到達概率包括由到達終點狀態的一個或多個其他設備所採取的動作(例如動作A_2b )的概率的乘積。如果執行設備對應於玩家2，則一個或多個其他設備(例如，對應於玩家1)到達終點狀態(例如，終點節點155b)的到達概率包括由到達終點狀態的一個或多個其他設備所採取的動作(例如，A_1a 和A_3b )的概率的乘積。

在906處，例如根據等式(17)，基於執行設備在終點狀態下的CFV及/或執行設備在前一次迭代的終點狀態下的CFV基線，計算執行設備在終點狀態下的經基線校正的CFV(例如，

)。例如，根據等式(16)，例如，基於以下計算在前一次迭代的終點狀態下採取動作的執行設備的採樣CFV基線(例如，

)：執行設備在前一次迭代的終點狀態下的CFV基線、執行設備在前一次迭代的終點狀態下採取動作的採樣方針、以及執行設備採取的動作序列導致到達終點狀態的概率。反應於確定動作被採樣，例如，根據等式(17)的下方等式(或第二等式)，基於執行設備在非終點狀態下的CFV以及在前一次迭代的終點狀態下採取動作的執行設備的採樣CFV基線，計算在非終點狀態下採取該動作的執行設備的經基線校正的CFV(例如，

)。反應於確定未對動作進行採樣，例如，根據等式(17)的上方等式(或第一等式)，將在前一次迭代的終點狀態下採取該動作的執行設備的採樣CFV基線用作執行設備在非終點狀態下的經基線校正的CFV。

在一些實施例中，對於每個非終點狀態，並從具有終點狀態以及一個或多個其他終點狀態作為子狀態的非終點狀態開始，在908處，基於執行設備在非終點狀態的子狀態下的經基線校正的CFV的加權和計算執行設備在非終點狀態下的CFV(例如，估計反事實值

)。在一些實施例中，例如，根據等式(18)中下方等式(或第二等式)，基於經當前迭代中非終點狀態下的動作選擇方針加權的、執行設備在終點狀態下的經基線校正的CFV以及執行設備在一個或多個其他終點狀態下的對應經基線校正的CFV，計算執行設備在終點狀態下的經基線校正的CFV與執行設備在一個或多個其他終點狀態下的對應經基線校正的CFV的加權和。

在910處，類似於參照906描述的技術，例如根據等式(17)，基於執行設備在非終點狀態下的CFV及/或執行設備在前一次迭代的非終點狀態下的CFV基線，計算執行設備在非終點狀態下的經基線校正的CFV(例如，

)。

在912處，例如根據等式(19)，基於執行設備在前一次迭代的非終點狀態下的CFV基線與執行設備在非終點狀態下的CFV(例如

)或經基線校正的CFV(例如

)的加權和，計算執行設備在當前迭代的非終點狀態下的CFV基線(例如

)。在一些實施例中執行設備在前一次迭代的非終點狀態下的CFV基線與執行設備在非終點狀態下的CFV或經基線校正的CFV的加權和包括：經標量(例如

)加權的、執行設備在前一次迭代的非終點狀態下的CFV基線與經第二標量(例如

)和考慮非終點狀態的概率(例如

)加權的、執行設備在非終點狀態下的CFV或經基線校正的CFV的總和，例如根據等式(19)的下方等式(或第二等式)。

在916處，基於執行設備在當前迭代的非終點狀態下的的經基線校正的CFV來確定針對下一次迭代的非終點狀態下的動作選擇方針。在一些實施例中，每個節點的經基線校正的CFV可用於例如根據等式(10)、(12)、(7)和(8)來計算遺憾、累計遺憾、當前策略和平均策略。在一些實施例中，基於執行設備在當前迭代的非終點狀態下的的經基線校正的CFV，確定針對下一次迭代的非終點狀態下的動作選擇方針包括：基於執行設備在當前迭代的非終點狀態下的經基線校正的CFV計算遺憾值(例如，根據等式(10)-(12)中的一些或全部)；以及根據遺憾匹配(例如，根據基於等式(8)的遺憾匹配或遺憾匹配+)，基於遺憾值確定針對下一次迭代的非終點狀態下的動作選擇方針。在一些實施例中，例如，根據等式(8)，可以計算當前迭代之後的平均策略

。

在918處，確定當前狀態是否是初始狀態。在一些實施例中，這種確定可以用於確定是繼續還是終止更新當前迭代中的狀態的經基線校正的CFV。如果當前狀態為初始狀態，則無需進一步更新經基線校正的CFV。處理900進行到下一次迭代，即進行到904。如果當前狀態不是初始狀態，則該狀態的前一狀態或父狀態(例如，博弈樹或公開樹中當前節點的父節點)用於替換當前狀態，並且處理900返回到908以獲得針對前一狀態的每個動作的CFV。處理900可以如圖9所示繼續。

在一些實施例中，如上所述，對於處理900的每次迭代，僅終點狀態將需要基於執行設備在終點狀態下的收益與一個或多個其他設備到達終點狀態的到達概率的乘積來計算反事實值(例如

)(例如根據等式(18)的上方等式(或第一等式))。對於非終點狀態，因為基線基於反事實值，而不是基於效用值，所以可以基於終點狀態的反事實值的加權和及/或基線增強的反事實值的加權和來計算反事實值及/或基線增強的反事實值。因此，與例如，根據等式(4)，基於玩家i 的效用值矩陣和對手的範圍矩陣(即對手的到達概率)計算反事實值的使用預期效用值基線的方差減小技術相比，處理900可以減少計算量並提高計算效率。在一些實施例中，反事實值基線相對於預期效用值基線所節省的計算量可以取決於表示環境或IIG的博弈樹或公開樹中的深度及/或非終點狀態的數量。

圖10描繪了示出根據本文的實施例的計算機實現的用於提供與所描述的算法、方法、功能、處理、流程和程式相關聯的計算功能的系統的示例的框圖。圖10是示出根據本公開的實施例的計算機實現的用於提供與所描述的算法、方法、功能、處理、流程和程式相關聯的計算功能的系統1000的示例的框圖。在所示的實施例中，系統1000包括計算機1002和網路1030。

所示的計算機1002旨在包含任何計算設備，例如伺服器、桌上型計算機、膝上型計算機/筆記本計算機、無線資料埠、智慧電話、個人資料助理(PDA)、平板計算機、這些設備中的一個或多個處理器、另一計算設備或計算設備的組合，包括計算設備的物理或反事實實例、或計算設備的物理或反事實實例的組合。另外，計算機1002可以包括輸入設備，例如小鍵盤、鍵盤、觸控螢幕，另一輸入設備或可以接受用戶資訊的輸入設備的組合，以及傳達與計算機1002的操作相關聯的資訊的輸出設備，包括圖形類型的用戶界面(UI)(或GUI)或其他UI上的數位資料、視覺、音頻、另一種類型的資訊或各種類型的資訊的組合。

計算機1002可以在分布式計算系統中充當客戶端、網路組件、伺服器、資料庫的角色或另一持續性設備、另一角色或用於執行本公開中描述的主題的角色的組合。所示的計算機1002可通信地與網路1030耦接。在一些實施例中，計算機1002的一個或多個組件可以被配置為在包括基於雲計算的環境、本地環境、全域環境、另一環境或環境組合的環境中操作。

在高級別上，計算機1002是可操作用於接收、發送、處理、儲存或管理與所描述的主題相關聯的資料和資訊的電子計算設備。根據一些實施例，計算機1002還可包括伺服器或與伺服器可通信地耦接，包括應用伺服器、電子郵件伺服器、網路伺服器、高速緩存伺服器、流資料伺服器、另一伺服器或伺服器的組合。

計算機1002可以通過網路1030(例如，來自另一計算機1002上執行的客戶端軟體應用)接收請求，並藉由使用軟體應用或軟體應用的組合處理接收的請求來響應接收的請求。另外，還可以從內部用戶(例如，從命令控制台或藉由另一內部存取方法)、外部或第三方或者其他實體、個人、系統或計算機向計算機1002發送請求。

計算機1002的每個組件可以使用系統匯流排1003進行通信。在一些實施例中，計算機1002的任何或所有組件，包括硬體、軟體或者硬體和軟體的組合，可以使用應用程式化介面(API)1012、服務層1013、或者API 1012和服務層1013的組合通過系統匯流排1003進行介面連接。API 1012可以包括用於常式、資料結構和對象類的規範。API 1012可以是獨立於計算機語言的或依賴於計算機語言的，並且是指完整的介面、單個函數或甚至一組API。服務層1013向計算機1002或可通信地耦接到計算機1002的其他組件(無論是否示出)提供軟體服務。使用服務層1013的所有服務客戶可存取計算機1002的功能諸如由服務層1013提供的軟體服務藉由定義的介面提供可重用的、定義的功能。例如，該介面可以是用以JAVA、C ++、另一種計算語言、或以可擴展標記語言(XML)格式、另一種格式或多種格式的組合提供資料的計算機語言的組合編寫的軟體。雖然示出為計算機1002的積體組件，但是替代實施例可以將API 1012或服務層1013示出為與計算機1002的其他組件有關的獨立組件或可通信地耦接到計算機1002的其他組件(無論是否示出)。此外，在不脫離本公開的範圍的情況下，API 1012或服務層1013的任何或所有部分可以被實現為另一軟體模組、企業應用或硬體模組的子模組(a child or a sub-module)。

計算機1002包括介面1004。儘管示出為單個介面1004，但是可以根據計算機1002的特定需要、期望或特定實施例使用兩個或更多個介面1004。介面1004被計算機1002用來與在分布式環境中通信地鏈接到網路1030的另一計算系統(無論是否示出)進行通信。通常，介面1004可操作地與網路1030通信，並且包括以軟體、硬體或者軟體和硬體的組合編碼的邏輯。更具體地說，介面1004可以包括支持與通信相關聯的一個或多個通信協定的軟體，以使得網路1030或介面1004的硬體可操作地在所示計算機1002之內和所示計算機1002之外通信物理信號。

計算機1002包括處理器1005。儘管示出為單個處理器1005，但是可以根據計算機1002的特定需要、期望或特定實施例使用兩個或更多個處理器1005。通常，處理器1005執行指令並操縱資料以執行計算機1002的操作以及本公開中所描述的任何算法、方法、功能、處理、流程和程式。

計算機1002還包括資料庫1006，該資料庫1006可以保存用於計算機1002的資料、通信地鏈接到網路1030的另一組件(無論是否示出)的資料、或者計算機1002和另一組件的組合的資料。例如，資料庫1006可以是儲存與本公開一致的儲存資料的內存、常規資料庫或另一類型的資料庫。在一些實施例中，根據計算機1002的特定需要、期望或特定實施例以及所描述的功能，資料庫1006可以是兩個或更多個不同資料庫類型的組合(例如，混合內存和常規資料庫)。儘管被示為單個資料庫1006，但是可以根據計算機1002的特定需求、期望或特定實施例以及所描述的功能來使用相似或不同類型的兩個或更多個資料庫。儘管資料庫1006被示為計算機1002的積體組件，但在替代實施例中，資料庫1006可以在計算機1002的外部。作為示例，資料庫1006可以包括如上所述的動作選擇方針(策略)1026，例如用於計算累計及/或平均動作選擇(策略)。

計算機1002還包括記憶體1007，該記憶體1007可以保存用於計算機1002的資料、通信地鏈接到網路1030的另一組件(無論是否示出)的資料、或者計算機1002和另一組件的組合的資料。記憶體1007可以儲存與本公開一致的任何資料。在一些實施例中，根據計算機1002的特定需要、期望或特定實施例以及所描述的功能，記憶體1007可以是兩種或更多種不同類型的記憶體的組合(例如，半導體和磁儲存設備的組合)。儘管被示為單個記憶體1007，但是可以根據計算機1002的特定需求、期望或特定實施例以及所描述的功能來使用相似或不同類型的兩個或更多個記憶體1007。儘管記憶體1007被示為計算機1002的積體組件，但在替代實施例中，記憶體1007可以在計算機1002的外部。

應用1008是算法軟體引擎，其提供根據計算機1002的特定需要、期望或特定實施例的功能，特別是關於本公開中描述的功能。例如，應用1008可以用作一個或多個組件、模組或應用。此外，儘管被示為單個應用1008，但是應用1008可以被實現為計算機1002上的多個應用1008。另外，儘管被示為與計算機1002整合，但是在替代實施例中，應用1008可以在計算機1002的外部。

計算機1002還可以包括電源1014。電源1014可包括可被配置為用戶可更換的可充電電池或用戶不可更換的不可充電電池。在一些實施例中，電源1014可以包括功率轉換或管理電路(包括充電、備用或另一電源管理功能)。在一些實施例中，電源1014可以包括電源插頭，以允許將計算機1002插入壁式插座或另一電源中，從而例如為計算機1002供電或為可充電電池充電。

可以存在與包含計算機1002的計算機系統關聯或在其外部的任何數量的計算機1002，每個計算機1002通過網路1030進行通信。此外，在不脫離本公開的範圍的情況下，術語“客戶端”、“用戶”或其他適當的術語可以適當地互換使用。此外，本公開預期許多用戶可以使用一個計算機1002，或者一個用戶可以使用多個計算機1002。

圖11是根據本文的實施例的裝置1100的模組的示例的圖。裝置1100可以是用於生成動作選擇方針以在包括執行設備以及一個或多個其他設備的環境中完成任務的資料處理裝置或執行設備的示例性實施例。裝置1100可以對應於上述實施例，裝置1100包括以下：第一識別模組1101，用於識別一個狀態下的多個可能動作，其中，所述狀態對應於資訊集向量，並且資訊集向量中的每個資訊集包括由執行設備採取的導致所述狀態的動作序列；第二識別模組1102，用於識別所述狀態下的當前動作選擇方針向量，其中，當前動作選擇方針向量中的每個當前動作選擇方針對應於資訊集向量中的資訊集，並且動作選擇方針指定在所述狀態下的多個可能動作中選擇一個動作的相應概率；計算模組1103，用於基於所述狀態下的當前動作選擇方針向量，計算採樣方針，其中，所述採樣方針指定與所述狀態下的多個可能動作中的每個動作相對應的相應採樣概率；採樣模組1104，用於根據所述採樣方針中指定的所述狀態下的多個可能動作中的一個動作的採樣概率，對該動作進行採樣；以及更新模組1105，用於基於該動作，更新執行設備在所述狀態下的當前動作選擇方針向量中的每個當前動作選擇方針。

在一些實施例中，裝置1100還包括以下：控制模組1106，用於反應於確定滿足收斂條件而基於動作選擇方針來控制執行設備的操作。

在一些實施例中，其中，基於動作更新執行設備在所述狀態下的當前動作選擇方針向量中的每個當前動作選擇方針包括：基於動作執行蒙特卡羅反事實遺憾最小化(MCCFR)。

在一些實施例中，其中，基於該動作更新執行設備在所述狀態下的當前動作選擇方針向量中的每個當前動作選擇方針包括：基於動作的採樣概率，計算採樣終點動作序列的概率，採樣的終點動作序列包括動作和完成任務的終點狀態；基於採樣的終點動作序列的概率計算動作的採樣反事實值；基於動作的採樣反事實值，計算動作的遺憾值；基於動作的遺憾值，更新執行設備在所述狀態下的當前動作選擇方針向量中的每個當前動作選擇方針。

在一些實施例中，其中，所述狀態對應於公開序列，所述公開序列包括執行設備以及一個或多個其他設備公開已知的一個或多個動作；並且資訊集向量中的每個資訊集包括公開序列。

在一些實施例中，其中，基於執行設備在所述狀態下的當前動作選擇方針向量來計算採樣方針包括：將與所述狀態下的多個可能動作中的每個動作相對應的採樣概率計算為資訊集向量上所述狀態下的多個可能動作中的每個動作的當前動作選擇方針的平均值。

在一些實施例中，其中，基於執行設備在所述狀態下的當前動作選擇方針向量來計算採樣方針包括：基於所述狀態下的多個可能動作中的每個動作的當前動作選擇方針和資訊集向量的相應到達概率計算與所述狀態下的多個可能動作中的每個動作相對應的採樣概率。

在一些實施例中，其中，基於所述狀態下的多個可能動作中的每個動作的當前動作選擇方針和資訊集向量的相應到達概率，來計算與所述狀態下的多個可能動作中的每個動作對應的採樣概率包括：基於經資訊集向量的相應到達概率加權的所述狀態下的多個可能動作中的每個動作的當前動作選擇方針的總和，計算與所述狀態下的多個可能動作中的每個動作相對應的採樣概率。

在一些實施例中，其中，基於執行設備在所述狀態下的當前動作選擇方針向量來計算採樣方針包括：基於所述狀態下的多個可能動作中的每個動作的平均動作選擇方針和資訊集向量的相應到達概率，計算與所述狀態下的多個可能動作中的每個動作相對應的採樣概率。

在一些實施例中，其中，基於所述狀態下的多個可能動作中的每個動作的平均動作選擇方針和資訊集向量的相應到達概率，來計算與所述狀態下的多個可能動作中的每個動作對應的採樣概率包括：基於經資訊集向量的相應到達概率加權的所述狀態下的多個可能動作中的每個動作的平均動作選擇方針之和計算與所述狀態下的多個可能動作中的每個動作相對應的採樣概率。

圖12是根據本文的實施例的設備1200的模組的示例的圖。裝置1200可以是用於生成動作選擇方針以在包括執行設備以及一個或多個其他設備的環境中完成任務的資料處理裝置或執行設備的示例性實施例。裝置1200可以對應於上述實施例，裝置1200包括以下：計算模組1201，用於基於採樣方針和探索方針計算執行設備在一個狀態下的混合採樣方針，其中，所述狀態對應於多個可能動作，當執行設備在所述狀態下時，所述多個可能動作如果被執行設備執行，將導致相應的下一狀態，其中，採樣方針指定對所述狀態下的多個可能動作中的每個動作進行採樣的相應採樣概率，其中，所述探索方針指定與所述狀態下的多個可能動作中的每個動作相對應的相應的探索概率，其中，探索概率與所述狀態下的多個可能動作中的每個動作已被採樣的次數負相關；採樣模組1202，用於根據混合採樣方針中指定的所述狀態下的多個可能動作中的一個動作的採樣概率，對該動作進行採樣；以及更新模組1203，用於藉由基於所述動作執行蒙特卡羅反事實遺憾最小化(MCCFR)來更新執行設備在所述狀態下的動作選擇方針，其中，所述動作選擇方針指定從所述狀態下的多個可能動作中選擇一個動作的相應概率，用於在環境中完成任務。

在一些實施例中，裝置1200還包括以下：控制模組1204，用於反應於確定滿足收斂條件而基於動作選擇方針來控制執行設備的操作。

在一些實施例中，裝置1200還包括：增加模組，用於增加在所述狀態下對所述動作進行採樣的次數；以及減小模組，用於反應於根據混合採樣方針從所述狀態下的多個可能動作中對所述動作進行採樣，減小與所述狀態下的多個可能動作中的所述動作相對應的探索概率，用於計算下一次迭代中的混合採樣方針。

在一些實施例中，其中，基於所述動作執行蒙特卡羅反事實遺憾最小化(MCCFR)包括：基於動作的混合採樣概率，計算採樣的終點動作序列的概率，採樣的終點動作序列包括動作和完成任務的終點狀態；基於採樣的終點動作序列的概率，計算動作的採樣反事實值；基於動作的採樣反事實值，計算動作的遺憾值；基於動作的遺憾值，更新執行設備在所述狀態下的動作選擇方針。

在一些實施例中，其中：採樣方針包括所述狀態下的多個可能動作上的第一概率分佈，並且探索方針包括所述狀態下的多個可能動作上的第二概率分佈。

在一些實施例中，其中，基於採樣方針和探索方針計算混合採樣方針包括：基於所述狀態下的多個可能動作中的每個動作的採樣概率和所述狀態下的多個可能動作中的每個動作的探索概率的加權和來計算所述狀態下的多個可能動作中的每個動作的概率。

在一些實施例中，其中，基於採樣方針和探索方針計算混合採樣方針包括：根據下式計算所述狀態下的多個可能動作中的每個動作的概率：

其中：I_i 表示狀態的資訊集；a 表示多個可能動作之一；σ_i ^se (a |I_i )表示在所述狀態下對動作a 進行採樣的混合採樣方針；σ_i ^s (a |I_i )表示在所述狀態下對動作a 進行採樣的採樣方針；σ_i ^e (a |I_i )表示在所述狀態下探索動作a 的探索方針；以及α ∈[0, 1]表示控制探索權重的因子。

在一些實施例中，其中，根據下式計算所述狀態下的多個可能動作中的每個動作的探索概率：

其中：i 表示執行設備的標識；I_i 表示狀態的資訊集；

表示所述狀態下的多個可能動作；a 表示所述狀態下的多個可能動作之一；t 表示當前迭代；∆C^t (a |I_i )表示直到當前迭代t 在所述狀態下對動作a 進行採樣的次數；σ_i ^e,t

表示在當前迭代t 中在所述狀態下探索動作a 的探索方針；以及β 是非負實數。

圖13是根據本文的實施例的裝置1300的模組的示例的圖。裝置1300可以是用於生成動作選擇方針以在包括執行設備以及一個或多個其他設備的環境中完成任務的資料處理裝置或執行設備的示例性實施例。裝置1300可以對應於上述實施例，並且裝置1300包括以下：對於多次迭代中的當前迭代，第一計算模組1301，用於基於執行設備在終點狀態下的收益以及一個或多個其他設備到達終點狀態的到達概率計算執行設備在完成任務的終點狀態下的反事實值(CFV)，其中，終點狀態是由執行設備以及一個或多個其他設備在多個非終點狀態下採取的動作序列導致的，其中，多個非終點狀態中的每個具有一個或多個子狀態；第二計算模組1302，用於基於執行設備在終點狀態下的CFV及/或執行設備在前一次迭代的終點狀態下的CFV基線，計算執行設備在終點狀態下的經基線校正的CFV；對於每個非終點狀態，並從具有終點狀態以及一個或多個其他終點狀態作為子狀態的非終點狀態開始：第三計算模組1303，用於基於執行設備在非終點狀態的子狀態下的經基線校正的CFV的加權和計算執行設備在非終點狀態下的CFV；第四計算模組1304，用於基於執行設備在非終點狀態下的CFV及/或執行設備在前一次迭代的非終點狀態下的CFV基線，計算執行設備在非終點狀態下的經基線校正的CFV；第五計算模組1305，用於基於執行設備在前一次迭代的非終點狀態下的CFV基線與執行設備在非終點狀態下的CFV或經基線校正的CFV的加權和，計算執行設備在當前迭代的非終點狀態下的CFV基線；確定模組1306，用於基於執行設備在當前迭代的非終點狀態下的經基線校正的CFV，確定針對下一次迭代的非終點狀態下的動作選擇方針。

在一些實施例中，裝置1300還包括以下：控制識別模組1307，用於反應於確定滿足收斂條件，基於非終點狀態下的動作選擇方針控制執行設備在非終點狀態下的操作，以用於下一次迭代。

在一些實施例中，其中，基於執行設備在當前迭代的非終點狀態下的經基線校正的CFV來確定針對下一次迭代的非終點狀態下的動作選擇方針包括：基於執行設備在當前迭代的非終點狀態下的經基線校正的CFV計算遺憾值；以及根據遺憾匹配，基於遺憾值確定針對下一次迭代的非終點狀態下的動作選擇方針。

在一些實施例中，其中，一個或多個其他設備到達終點狀態的到達概率包括由到達終點狀態的一個或多個其他設備採取的動作的概率的乘積。

在一些實施例中，其中，基於執行設備在非終點狀態下的CFV，及/或執行設備在前一次迭代的非終點狀態下的CFV基線來計算執行設備在非終點狀態下的經基線校正的CFV包括，基於以下計算在前一次迭代的終點狀態下採取動作的執行設備的採樣CFV基線：執行設備在前一次迭代的終點狀態下的CFV基線，執行設備在前一次迭代的終點狀態下採取動作的採樣方針，以及執行設備採取的動作序列導致到達終點狀態的概率；反應於確定對所述動作進行了採樣，基於執行設備在非終點狀態下的CFV和在前一次迭代的終點狀態下採取該動作的執行設備的採樣CFV基線計算在非終點狀態下採取該動作的執行設備的經基線校正的CFV；以及反應於確定未對該動作進行採樣，將在前一次迭代的終點狀態下採取該動作的執行設備的採樣CFV基線用作執行設備在非終點狀態下的經基線校正的CFV。

在一些實施例中，其中，基於經當前迭代中非終點狀態下的動作選擇方針加權的、執行設備在終點狀態下的經基線校正的CFV以及執行設備在一個或多個其他終點狀態下的對應的經基線校正的CFV，計算執行設備在終點狀態下的經基線校正後的CFV與執行設備在一個或多個其他終點狀態下的對應的經基線校正的CFV的加權和。

在一些實施例中，其中，執行設備在前一次迭代的非終點狀態下的CFV基線與執行設備在非終點狀態下的CFV或經基線校正的CFV的加權和包括以下兩項之和：經標量加權的、執行設備在前一次迭代的非終點狀態下的CFV基線；經第二標量和考慮非終點狀態的概率加權的、執行設備在非終點狀態下的CFV或經基線校正的CFV。

在先前實施例中所示的系統、裝置、模組或單元可以藉由使用計算機芯片或實體來實現，或者可以藉由使用具有特定功能的產品來實現。典型實施例設備是計算機，計算機可以是個人計算機、膝上型計算機、蜂巢式電話、攝像電話、智慧手機、個人數位助理、媒體播放器、導航設備、電子郵件收發設備、遊戲機、平板電腦、可穿戴設備，或這些設備的任何組合。

對於裝置中每個模組的功能和作用的實施過程，可以參考前述方法中相應步驟的實施過程。為了簡單起見，這裡省略了細節。

由於裝置實施例基本上對應於方法實施例，因此對於相關部分，可以參考方法實施例中的相關描述。前面描述的裝置實施例僅僅是示例。被描述為獨立部分的模組可以是物理上獨立的或者不是物理上獨立的，顯示為模組的部分可以是物理模組或者不是物理模組，可以位於一個位置，或者可以分佈在多個網路模組上。部分或全部模組可基於實際需求來選擇，以達到本文的解決方案的目的。本領域的普通技術人員無需創造性的努力即可理解和實現本申請的實施例。

再次參考圖11-13，每個圖都可以解釋為示出資料處理裝置或執行設備的內部功能模組和結構，該資料處理裝置或執行設備用於生成動作選擇方針，以在包括執行設備以及一個或多個其他設備的環境中完成任務。執行主體本質上可以是電子設備，並且電子設備包括以下：一個或多個處理器；以及被配置為儲存一個或多個處理器的可執行指令的一個或多個計算機可讀記憶體。在一些實施例中，一個或多個計算機可讀記憶體耦接到一個或多個處理器，並且其上儲存有程式化指令，該程式化指令可由一個或多個處理器執行以執行算法、方法、功能、處理、流程和過程，如本文中所述。本文還提供了一個或多個非暫時性計算機可讀儲存媒體，其耦接到一個或多個處理器且其上儲存有指令，當由一個或多個處理器執行時，所述指令使一個或多個處理器執行根據本文提供的方法的實施例的操作。

本文還提供了用於一種用於實現本文提供的方法的系統。所述系統包括一個或多個處理器，以及耦接到一個或多個處理器的計算機可讀儲存媒體，計算機可讀儲存媒體上儲存有指令，當由一個或多個處理器執行時，所述指令使一個或多個處理器執行根據本文提供的方法的實施例的操作。

在本文中描述的主題的實施例以及動作和操作可以以數位電子電路、有形實現的計算機軟體或韌體、計算機硬體(包括本文中公開的結構及其結構等同物)、或者它們中的一個或多個的組合實現。本文中描述的主題的實施例可以實現為一個或多個計算機程式，例如，一個或多個計算機程式指令模組，編碼在計算機程式載體上，用於由資料處理裝置執行或控制資料處理裝置的操作。例如，計算機程式載體可以包括具有編碼在其上或者儲存在其上的指令的一個或多個計算機儲存媒體。載體可以是有形的非暫態計算機可讀媒體，諸如磁碟、磁光碟或者光碟、固態驅動器、隨機儲存區記憶體(RAM)、唯讀記憶體(ROM)、或者其他類型的媒體。可選地或附加地，載體可以是人工生成的傳播信號，例如，機器生成的電信號、光信號或電磁信號，其被生成來編碼資訊用於傳輸到合適的接收器裝置以供資料處理裝置執行。計算機儲存媒體可以是或部分是機器可讀儲存設備、機器可讀儲存基板、隨機或串行存取記憶體設備或它們中的一個或多個的組合。計算機儲存媒體不是傳播信號。

計算機程式，也可以被稱為或描述為程式、軟體、軟體應用、應用、模組、軟體模組、引擎、腳本或代碼，可以以任何形式的程式化語言編寫，包括編譯或演繹性語言、說明或程式性語言；它可以配置為任何形式，包括作為獨立程式，或者作為模組、組件、引擎、子程式或適合在計算環境中執行的其他單元，該環境可包括由資料通信網路互聯的在一個或多個位置的一台或多台計算機。

計算機程式可以但非必須對應於文件系統中的文件。計算機程式可以儲存在：保存其他程式或資料的文件的一部分中，例如，儲存在標記語言文檔中的一個或多個腳本；專用於所討論的程式的單個文件；或者多個協調文件，例如，儲存一個或多個模組、子程式或代碼部分的多個文件。

用於執行計算機程式的處理器包括例如通用微處理器和專用微處理器以及任何種類的數位計算機的任一個或多個處理器。通常，處理器將從耦接至該處理器的非暫態計算機可讀媒體接收用於執行的計算機程式的指令以及資料。

術語“資料處理裝置”包括用於處理資料的所有類型的裝置、設備和機器，包括例如可程式化處理器、計算機或者多處理器或計算機。資料處理裝置可以包括專用邏輯電路，例如FPGA(現場可程式化門陣列)、ASIC(專用積體電路)或GPU(圖形處理單元)。除了硬體，該裝置還可以包括為計算機程式創建執行環境的代碼，例如，構成處理器韌體、協定疊、資料庫管理系統、操作系統或者它們中的一個或多個的組合的代碼。

本文中描述的過程和邏輯流程可藉由一台或多台計算機或處理器執行一個或多個計算機程式來進行，以藉由對輸入資料進行運算並生成輸出進行操作。過程和邏輯流程也可以由例如FPGA、ASIC、GPU等的專用邏輯電路或專用邏輯電路與一個或多個程式化計算機的組合來執行。

適合於執行計算機程式的計算機可以基於通用或專用微處理器或者兩者，或任何其他種類的中央處理單元。通常，中央處理單元將從唯讀記憶體或隨機存取記憶體或兩者接收指令和資料。計算機的元件可包括用於執行指令的中央處理單元以及用於儲存指令和資料的一個或多個記憶體設備。中央處理單元和記憶體可以補充有專用邏輯電路或整合在專用邏輯電路中。

通常，計算機還將包括或可操作地耦接至一個或多個儲存設備，以從一個或多個儲存設備接收資料或將資料傳輸到一個或多個儲存設備。儲存設備可以是例如磁碟、磁光碟或光碟、固態驅動器、或者任何其他類型的非暫態計算機可讀媒體。但是，計算機不需要具有這樣的設備。因此，計算機可以耦接至一個或多個儲存設備，諸如本地及/或遠程的一個或多個記憶體。例如，計算機可以包括作為計算機的組成部件的一個或多個本地記憶體，或者計算機可以耦接至處於雲網路中的一個或多個遠程記憶體。此外，計算機可以嵌入在另一個設備中，例如行動電話、個人數位助理(PDA)、行動音頻或視頻播放器、遊戲控制台、全球定位系統(GPS)接收器或例如通用串行匯流排(USB)閃存驅動器的便攜式儲存設備，僅舉幾例。

組件可以藉由諸如直接或經由一個或多個中間組件彼此互動性地電連接或光學連接而彼此耦接。如果一個組件整合到另一個組件中，部件也可以耦接至彼此。例如，整合到處理器(例如，L2緩存組件)中的儲存組件耦接至處理器。

為了提供與用戶的互動，本文中描述的主題的實施例可以在計算機上實現或配置為與該計算機通信，該計算機具有：顯示設備，例如，LCD(液晶顯示器)監視器，用於向用戶顯示資訊；以及輸入設備，用戶可以藉由該輸入設備向該計算機提供輸入，例如鍵盤和例如滑鼠、軌跡球或觸摸板等的指針設備。其他類型的設備也可用於提供與用戶的互動；例如，提供給用戶的反饋可以是任何形式的感官反饋，例如視覺反饋、聽覺反饋或觸覺反饋；並且可以接收來自用戶的任何形式的輸入，包括聲音、語音或觸覺輸入。此外，計算機可以藉由向用戶使用的設備發送文檔和從用戶使用的設備接收文檔來與用戶互動；例如，藉由向用戶設備上的web瀏覽器發送web頁面以響應從web瀏覽器收到的請求，或者藉由與例如智慧電話或電子平板電腦等的用戶設備上運行的應用(app)進行互動。此外，計算機可以藉由向個人設備(例如，運行消息應用的智慧手機)輪流發送文本消息或其他形式的消息並接收來自用戶的響應消息來與用戶互動。

本文使用與系統、裝置和計算機程式組件有關的術語“配置為”。對於被配置為執行特定操作或動作的一個或多個計算機的系統，意味著系統已經在其上安裝了在運行中促使該系統執行所述操作或動作的軟體、韌體、硬體或它們的組合。對於被配置為執行特定操作或動作的一個或多個計算機程式，意味著一個或多個程式包括當被資料處理裝置執行時促使該裝置執行所述操作或動作的指令。對於被配置為執行特定操作或動作的專用邏輯電路，意味著該電路具有執行所述操作或動作的電子邏輯。

雖然本文包含許多具體實施細節，但是這些不應被解釋為由請求項本身限定的對要求保護的範圍的限制，而是作為對特定實施例的具體特徵的描述。在本文中在多個單獨實施例的上下文中描述的多個特定特徵也可以在單個實施例中組合地實現。相反，在單個實施例的上下文中描述的各種特徵也可以單獨地或以任何合適的子組合在多個實施例中實現。此外，儘管上面的特徵可以描述為以某些組合起作用並且甚至最初如此要求保護，但是在一些情況下，可以從要求保護的組合中刪除來自該組合的一個或多個特徵，並且可以要求保護指向子組合或子組合的變體。

類似地，雖然以特定順序在附圖中描繪了操作並且在請求項中敘述了操作，但是這不應該被理解為：為了達到期望的結果，要求以所示的特定順序或依次執行這些操作，或者要求執行所有示出的操作。在一些情況下，多任務並行處理可能是有利的。此外，上述實施例中的各種系統模組和組件的劃分不應被理解為所有實施例中都要求如此劃分，而應當理解，所描述的程式組件和系統通常可以一起整合在單個軟體產品或者打包成多個軟體產品。

已經描述了主題的特定實施例。其他實施例在以下請求項的範圍內。例如，請求項中記載的動作可以以不同的順序執行並且仍然實現期望的結果。作為一個示例，附圖中描繪的過程無需要求所示的特定順序或次序來實現期望的結果。在一些情況下，多任務和並行處理可能是有利的。

100:博弈樹 103:子樹 107:子樹 110:根節點 123:節點 127:節點 133a:節點 133b:節點 137a:節點 137b:節點 143a:節點 143b:節點 143c:節點 143d:節點 147a:節點 147b:節點 147c:節點 147d:節點 153a:節點 153b:節點 157a:節點 157b:節點 150:公開樹 125:節點 135a:節點 135b:節點 145a:節點 145b:節點 145c:節點 145d:節點 155a:節點 155b:節點 1000:計算機系統 1002:計算機 1003:系統匯流排 1004:介面 1005:處理器 1006:資料庫 1007:記憶體 1008:應用 1012:應用程式化介面 1013:服務層 1014:電源 1026:動作選擇方針 1030:網路 1100:裝置 1101:第一識別模組 1102:第二識別模組 1103:計算模組 1104:採樣模組 1105:更新模組 1106:控制模組 1200:設備 1201:計算模組 1202:採樣模組 1203:更新模組 1204:控制模組 1300:裝置 1301:第一計算模組 1302:第二計算模組 1303:第三計算模組 1304:第四計算模組 1305:第五計算模組 1306:確定模組 1307:控制識別模組

[圖1A和1B]是示出根據本文的實施例的庫恩撲克(Kuhn Poker)的博弈樹和公開樹的示例的圖。

[圖2]是示出根據本文的實施例的以不同的採樣方針應用於NLPH的幾種MCCFR變體的收斂性能的雙對數座標曲線圖。

[圖3]是示出根據本文的實施例的在利用和不利用探索技術的情況下應用於NLPH的幾種MCCFR變體的收斂性能的雙對數座標曲線圖。

[圖4A]是示出根據本文的實施例的在利用和不利用不同方差減小技術的情況下應用於NLPH的幾種MCCFR變體的收斂性能的雙對數座標曲線圖。

[圖4B]是示出根據本文的實施例的在利用和不利用不同方差減小技術的情況下應用於NLPH的幾種MCCFR變體的示例計算效率的雙對數座標曲線圖。

[圖5A至圖5C]是示出根據本文的實施例的藉由對三種不同的撲克博弈NLPH、HUNL-R和NLFH的外部採樣的幾種MCCFR變體的收斂性能的雙對數座標曲線圖。

[圖6A]是示出根據本文的實施例的在NLPH上利用和不利用跳過的幾種MCCFR變體的收斂性能的雙對數座標曲線圖。

[圖6B]是示出根據本文的實施例的在NLPH上利用和不利用跳過的MCCFR變體的收斂性能的雙對數座標曲線圖。

[圖7]是根據本文的實施例的用於執行蒙特卡洛反事實遺憾最小化(MCCFR)以確定用於軟體應用的動作選擇方針的過程的示例的流程圖。

[圖8]是根據本文的實施例的用於執行蒙特卡洛反事實遺憾最小化(MCCFR)以確定用於軟體應用的動作選擇方針的另一過程的示例的流程圖。

[圖9]是根據本文的實施例的用於執行蒙特卡洛反事實遺憾最小化(MCCFR)以確定用於軟體應用的動作選擇方針的另一過程的示例的流程圖。

[圖10]描繪示出根據本文的實施例的用於提供與所描述的算法、方法、功能、過程、流程和過程相關聯的計算功能的計算機實現的系統的示例的框圖。

[圖11]描繪根據本文的實施例的裝置的模組的示例。

[圖12]描繪根據本文的實施例的另一裝置的模組的示例。

[圖13]描繪根據本文的實施例的另一裝置的模組的示例。

在各個附圖中，相同的附圖標記和名稱指示相同的元件。

Claims (10)

1. 一種執行設備的計算機實現的方法，用於生成動作選擇方針以在包括該執行設備以及一個或多個其他設備的環境中完成任務，該方法包括：在多次迭代的當前迭代中，基於該執行設備在終點狀態下的收益以及該一個或多個其他設備到達該終點狀態的到達概率，由該執行設備計算該執行設備在完成任務的該終點狀態下的反事實值CFV，其中，該終點狀態是由該執行設備以及該一個或多個其他設備在多個非終點狀態下採取的動作序列導致的，該多個非終點狀態各具有一個或多個子狀態；基於該執行設備在該終點狀態下的反事實值、該執行設備在前一次迭代的終點狀態下的反事實值基線、或該執行設備在該終點狀態下的反事實值及該執行設備在該前一次迭代的該終點狀態下的反事實值基線，由該執行設備計算該執行設備在該終點狀態下的經基線校正的反事實值；對於每個非終點狀態並從具有該終點狀態以及一個或多個其他終點狀態作為子狀態的非終點狀態開始：基於該執行設備在該非終點狀態的子狀態下的經基線校正的反事實值的加權和，由該執行設備計算該執行設備在該非終點狀態下的反事實值；基於該執行設備在該非終點狀態下的反事實值、該執行設備在前一次迭代的非終點狀態下的反事實值基線、或該執行設備在該非終點狀態下的反事實值及該執行 設備在該前一次迭代的該非終點狀態下的反事實值基線，由該執行設備計算該執行設備在該非終點狀態下的經基線校正的反事實值；基於該執行設備在該前一次迭代的非終點狀態下的反事實值基線與該執行設備在該非終點狀態下的反事實值或該執行設備在該非終點狀態下的經基線校正的反事實值的加權和，由該執行設備計算該執行設備在該當前迭代的非終點狀態的反事實值基線；以及基於該執行設備在該當前迭代的非終點狀態下的經基線校正的反事實值，由該執行設備確定針對下一次迭代的非終點狀態下的動作選擇方針。
2. 如請求項1所述的方法，還包括：反應於確定滿足收斂條件，基於該非終點狀態下的動作選擇方針控制該執行設備在該非終點狀態下的操作，以用於該下一次迭代。
3. 如請求項1所述的方法，其中，基於該執行設備在該當前迭代的非終點狀態下的經基線校正的反事實值來確定針對該下一次迭代的非終點狀態下的該動作選擇方針包括：基於該執行設備在該當前迭代的非終點狀態下的經基線校正的反事實值計算遺憾值；以及根據遺憾匹配，基於該遺憾值確定針對該下一次迭代的非終點狀態下的該動作選擇方針。
4. 如請求項1所述的方法，其中，該一個或 多個其他設備到達該終點狀態的到達概率包括由到達該終點狀態的該一個或多個其他設備採取的動作的概率的乘積。
5. 如請求項1所述的方法，其中，基於該執行設備在該非終點狀態下的反事實值、該執行設備在前一次迭代的非終點狀態下的反事實值基線、或該執行設備在該非終點狀態下的反事實值及該執行設備在該前一次迭代的該非終點狀態下的反事實值基線，計算執行設備在非終點狀態下的經基線校正的反事實值包括：基於以下計算在前一次迭代的終點狀態下採取動作的執行設備的採樣反事實值基線：該執行設備在該前一次迭代的終點狀態下的反事實值基線，在該前一次迭代的終點狀態下採取該動作的該執行設備的採樣方針，以及到達該執行設備採取的動作序列導致該終點狀態的概率；反應於確定對該動作進行了採樣，基於該執行設備在該非終點狀態下的反事實值和在該前一次迭代的終點狀態下採取該動作的執行設備的採樣反事實值基線，計算在該非終點狀態下採取該動作的執行設備的經基線校正的反事實值；以及反應於確定未對該動作進行採樣，將在該前一次迭代的終點狀態下採取該動作的執行設備的採樣反事實值基線用作該執行設備在該非終點狀態下的經基線校正的反事實值。
6. 如請求項1所述的方法，其中，基於經該 當前迭代中該非終點狀態下的動作選擇方針加權的該執行設備在該終點狀態下的經基線校正的反事實值以及該執行設備在該一個或多個其他終點狀態下的對應的經基線校正的反事實值，計算該執行設備在該終點狀態下的經基線校正後的反事實值與該執行設備在該一個或多個其他終點狀態下的對應的經基線校正的反事實值的加權和。
7. 如請求項1所述的方法，其中，該執行設備在該前一次迭代的非終點狀態下的反事實值基線與該執行設備在該非終點狀態下的反事實值或經基線校正的反事實值的加權和包括以下兩項之和：經標量加權的該執行設備在該前一次迭代的非終點狀態下的反事實值基線；以及經第二標量和考慮該非終點狀態的概率加權的該執行設備在該非終點狀態下的反事實值或經基線校正的反事實值。
8. 如請求項1~7中任一項所述的方法，其中，該動作選擇方針用於實現一個或多個其他設備動作控制、產品/服務推薦或交通路線規劃。
9. 一種用於執行軟體實現應用的系統，用於為軟體實現應用生成動作選擇方針，該軟體實現應用在包括該應用支持的執行方以及一個或多個其他設備的環境中執行動作，該系統包括：一個或多個處理器；以及一個或多個計算機可讀記憶體，耦接到該一個或多個 處理器且其上儲存有指令，該指令能由該一個或多個處理器執行以實施如請求項1至8中任一項所述的方法。
10. 一種用於為軟體實現應用生成動作選擇方針的裝置，該軟體實現應用在包括該應用支持的執行方以及一個或多個其他設備的環境中執行動作，該裝置包括多個模組，用於實施如請求項1至8中任一項所述的方法。

Images