(57)【要約】  2人以上の当事者の間の戦略的対話における戦略探索のための反事実的リグレット最小化(CFR)を実施するための、コンピュータ記憶媒体上で符号化されたコンピュータプログラムを含む、方法、システム、および装置を、本明細書で開示する。方法のうちの1つは、複数のリグレットサンプルを第1のデータストアに記憶するステップであって、複数のリグレットサンプルは、2人以上の当事者の間の戦略的対話における戦略探索におけるCFRアルゴリズムの2回以上の反復において取得される、ステップと、複数の戦略サンプルを第2のデータストアに記憶するステップと、第1のデータストア中の複数のリグレットサンプルに基づいて、当事者の状態における可能な行動のリグレット値を予測するための、第1のニューラルネットワークのパラメータを更新するステップと、第2のデータストア中の複数の戦略サンプルに基づいて、当事者の状態における可能な行動の戦略値を予測するための、第2のニューラルネットワークのパラメータを更新するステップとを含む。
2021509492.tif 000002
【特許請求の範囲】
【請求項１】
2人以上の当事者の間の戦略的対話における戦略探索のための反事実的リグレット最小化(CFR)を実施するためのコンピュータ実装方法であって、
複数のリグレットサンプルを第1のデータストアに記憶するステップであって、前記複数のリグレットサンプルの各々は、当事者の状態、および前記当事者の前記状態における可能な行動のリグレット値を含み、前記複数のリグレットサンプルは、前記当事者と少なくとも他の当事者との間の戦略的対話における戦略探索における反事実的リグレット最小化(CFR)アルゴリズムの2回以上の反復において取得される、ステップと、
複数の戦略サンプルを第2のデータストアに記憶するステップであって、前記複数の戦略サンプルの各々は、前記当事者の状態、および前記当事者の前記状態における可能な行動の戦略値を含む、ステップと、
前記第1のデータストア中の前記複数のリグレットサンプルに基づいて、前記当事者の状態における可能な行動のリグレット値を予測するための、第1のニューラルネットワークのパラメータを更新するステップと、
前記第2のデータストア中の前記複数の戦略サンプルに基づいて、前記当事者の状態における可能な行動の戦略値を予測するための、第2のニューラルネットワークのパラメータを更新するステップとを含む方法。
【請求項２】
前記当事者の第1の状態、および前記当事者の前記第1の状態における第1の可能な行動を識別するステップと、
前記第1のニューラルネットワークの前記パラメータを使って、前記当事者の前記第1の状態における前記第1の可能な行動の第1のリグレット値を予測するステップと、
前記第2のニューラルネットワークの前記パラメータを使って、前記当事者の前記第1の状態における前記第1の可能な行動の第1の戦略値を予測するステップと
をさらに含む、請求項1に記載の方法。
【請求項３】
新たなリグレットサンプルを取得するステップと、
リザーバサンプリングアルゴリズムに従って、前記新たなリグレットサンプルを前記第1のデータストアの中に記憶するステップと
をさらに含む、請求項1に記載の方法。
【請求項４】
リザーバサンプリングアルゴリズムに従って、前記新たなリグレットサンプルを前記第1のデータストアの中に記憶するステップは、
前記第1のデータストアが満杯であるかどうかを判断するステップと、
前記第1のデータストアが満杯であると判断したことに応答して、前記第1のデータストア中の前記複数のリグレットサンプルのうちの1つを前記新たなリグレットサンプルで置き換えるステップとを含む、請求項3に記載の方法。
【請求項５】
前記CFRアルゴリズムはロバストサンプリングCFRアルゴリズムを含む、請求項1に記載の方法。
【請求項６】
前記当事者の前記状態における可能な行動の前記戦略値は平均戦略の分子を含む、請求項1に記載の方法。
【請求項７】
前記当事者の前記状態における可能な行動の前記リグレット値は、前記当事者の前記状態における前記可能な行動の反事実値に基づいて算出された、前記当事者の前記状態における前記可能な行動の反事実リグレット値を含む、請求項1に記載の方法。
【請求項８】
前記当事者と前記少なくとも他の当事者との間の戦略的対話における戦略探索における反事実的リグレット最小化(CFR)アルゴリズムの前記2回以上の反復の各々において、
サンプリング方式に従って、当事者の第2の状態における複数の可能な行動の中から可能な行動をサンプリングするステップと、
前記当事者の前記第2の状態における前記可能な行動の反事実値を算出するステップと、
前記当事者の前記第2の状態における前記可能な行動の前記反事実値に基づいて、前記当事者の前記第2の状態における前記可能な行動のリグレット値を算出するステップと、
リグレットマッチングアルゴリズムに従って、前記当事者の前記第2の状態における前記可能な行動の前記リグレット値に基づいて、前記当事者の前記第2の状態における前記可能な行動の更新された戦略を算出するステップと、
前記当事者の前記第2の状態における前記可能な行動の前記更新された戦略に基づいて、前記当事者の前記第2の状態における前記可能な行動の戦略値を算出するステップと
をさらに含む、請求項1に記載の方法。
【請求項９】
前の反復における前記第1のニューラルネットワークのパラメータに基づいて、前記第1のニューラルネットワークの前記パラメータを初期化するステップと、
前の反復における前記第2のニューラルネットワークのパラメータに基づいて、前記第2のニューラルネットワークの前記パラメータを初期化するステップと
をさらに含む、請求項1に記載の方法。
【請求項１０】
2人以上の当事者の間の戦略的対話における戦略探索のための反事実的リグレット最小化(CFR)を実施するための装置であって、
複数のリグレットサンプルを第1のデータストアに記憶するための第1の記憶モジュールであって、前記複数のリグレットサンプルの各々は、当事者の状態、および前記当事者の前記状態における可能な行動のリグレット値を含み、前記複数のリグレットサンプルは、前記当事者と少なくとも他の当事者との間の戦略的対話における戦略探索における反事実的リグレット最小化(CFR)アルゴリズムの2回以上の反復において取得される、第1の記憶モジュールと、
複数の戦略サンプルを第2のデータストアに記憶するための第2の記憶モジュールであって、前記複数の戦略サンプルの各々は、前記当事者の状態、および前記当事者の前記状態における可能な行動の戦略値を含む、第2の記憶モジュールと、
前記第1のデータストア中の前記複数のリグレットサンプルに基づいて、前記当事者の状態における可能な行動のリグレット値を予測するための、第1のニューラルネットワークのパラメータを更新するための第1の更新モジュールと、
前記第2のデータストア中の前記複数の戦略サンプルに基づいて、前記当事者の状態における可能な行動の戦略値を予測するための、第2のニューラルネットワークのパラメータを更新するための第2の更新モジュールとを備える装置。
【請求項１１】
前記当事者の第1の状態、および前記当事者の前記第1の状態における第1の可能な行動を識別するための識別モジュールと、
前記第1のニューラルネットワークの前記パラメータを使って、前記当事者の前記第1の状態における前記第1の可能な行動の第1のリグレット値を予測するための第1の予測モジュールと、
前記第2のニューラルネットワークの前記パラメータを使って、前記当事者の前記第1の状態における前記第1の可能な行動の第1の戦略値を予測するための第2の予測モジュールと
をさらに備える、請求項10に記載の装置。
【請求項１２】
前記第1の記憶モジュールは、新たなリグレットサンプルを取得すること、およびリザーバサンプリングアルゴリズムに従って、前記新たなリグレットサンプルを前記第1のデータストアの中に記憶することが可能である、請求項10に記載の装置。
【請求項１３】
リザーバサンプリングアルゴリズムに従って、前記新たなリグレットサンプルを前記第1のデータストアの中に記憶することは、
前記第1のデータストアが満杯であるかどうかを判断することと、
前記第1のデータストアが満杯であると判断したことに応答して、前記第1のデータストア中の前記複数のリグレットサンプルのうちの1つを前記新たなリグレットサンプルで置き換えることとを含む、請求項12に記載の装置。
【請求項１４】
前記CFRアルゴリズムはロバストサンプリングCFRアルゴリズムを含む、請求項10に記載の装置。
【請求項１５】
前記当事者の前記状態における可能な行動の前記戦略値は平均戦略の分子を含む、請求項10に記載の装置。
【請求項１６】
前記当事者の前記状態における可能な行動の前記リグレット値は、前記当事者の前記状態における前記可能な行動の反事実値に基づいて算出された、前記当事者の前記状態における前記可能な行動の反事実リグレット値を含む、請求項10に記載の装置。
【請求項１７】
前記当事者と前記少なくとも他の当事者との間の戦略的対話における戦略探索における反事実的リグレット最小化(CFR)アルゴリズムの前記2回以上の反復の各々において、
サンプリング方式に従って、当事者の第2の状態における複数の可能な行動の中から可能な行動をサンプリングするためのサンプリングモジュールと、
前記当事者の前記第2の状態における前記可能な行動の反事実値を算出するための第1の算出モジュールと、
前記当事者の前記第2の状態における前記可能な行動の前記反事実値に基づいて、前記当事者の前記第2の状態における前記可能な行動のリグレット値を算出するための第2の算出モジュールと、
リグレットマッチングアルゴリズムに従って、前記当事者の前記第2の状態における前記可能な行動の前記リグレット値に基づいて、前記当事者の前記第2の状態における前記可能な行動の更新された戦略を算出するための第3の算出モジュールと、
前記当事者の前記第2の状態における前記可能な行動の前記更新された戦略に基づいて、前記当事者の前記第2の状態における前記可能な行動の戦略値を算出するための第4の算出モジュールと
をさらに備える、請求項10に記載の装置。
【請求項１８】
前の反復における前記第1のニューラルネットワークのパラメータに基づいて、前記第1のニューラルネットワークの前記パラメータを初期化するための第1の初期化モジュールと、
前の反復における前記第2のニューラルネットワークのパラメータに基づいて、前記第2のニューラルネットワークの前記パラメータを初期化するための第2の初期化モジュールと
をさらに備える、請求項10に記載の装置。
【請求項１９】
1つまたは複数のプロセッサと、
前記1つまたは複数のプロセッサに結合されるとともに、請求項1から9のいずれか一項に記載の方法を実施するように、前記1つまたは複数のプロセッサによって実行可能である命令を記憶した1つまたは複数のコンピュータ可読メモリと
を備えるシステム。
【請求項２０】
2人以上の当事者が関与する不完全情報ゲーム(IIG)を解くための反事実的リグレット最小化(CFR)を実施するためのコンピュータ実装方法であって、
複数のリグレットサンプルを第1のデータストアに記憶するステップであって、前記複数のリグレットサンプルの各々は、当事者の状態、および前記当事者の前記状態における可能な行動のリグレット値を含み、前記複数のリグレットサンプルは、戦略的対話における戦略探索における反事実的リグレット最小化(CFR)アルゴリズムの2回以上の反復において取得され、前記IIGは、少なくとも前記当事者および第2の当事者が関与する協調型製品サービス推奨サービスを表し、前記当事者は、前記第2の当事者の情報への制限付きアクセスを有し、前記当事者の前記状態は、前記第2の当事者によって提供された情報の履歴を含み、前記当事者の前記可能な行動は、顧客への製品サービス推奨を提供するための、前記第2の当事者によって提供された情報の前記履歴に応答して可能な行動を含む、ステップと、
複数の戦略サンプルを第2のデータストアに記憶するステップであって、前記複数の戦略サンプルの各々は、前記当事者の状態、および前記当事者の前記状態における可能な行動の戦略値を含む、ステップと、
前記第1のデータストア中の前記複数のリグレットサンプルに基づいて、前記当事者の状態における可能な行動のリグレット値を予測するための、第1のニューラルネットワークのパラメータを更新するステップと、
前記第2のデータストア中の前記複数の戦略サンプルに基づいて、前記当事者の状態における可能な行動の戦略値を予測するための、第2のニューラルネットワークのパラメータを更新するステップとを含む方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書は、2人以上の当事者の間の戦略的対話における戦略探索に関する。
【背景技術】
【０００２】
2人以上の当事者の間の戦略的対話が、2人以上の当事者(プレーヤとも呼ばれる)が関与するゲームによってモデル化され得る。2人以上のプレーヤが関与する不完全情報ゲーム(IIG)では、プレーヤは、決定を行う前に、自分の対戦相手の知識を部分的にしか入手できない。これは、取引、トラフィックルーティング、および公開オークションなどの実世界シナリオと同様である。異なる企業の間の商業上の競争、オークションシナリオにおける入札関係、不正当事者と不正対策当事者との間のゲーム関係など、多くの実生活シナリオが、IIGとして表され得る。
【０００３】
IIGを解くための方法は、大きな経済的および社会的利益となる。隠れた情報により、プレーヤは、自分の対戦相手の情報について確信をもてない状況で推論しなければならず、プレーヤは、自分の対戦相手が、自分自身の情報について確信をもてないことを利用するように行動する必要がある。
【発明の概要】
【課題を解決するための手段】
【０００４】
本明細書の実装形態は、当事者の間の戦略的対話における戦略探索のためのコンピュータ実装方法を含む。より詳細には、本明細書は、不完全情報ゲーム(IIG)を解く際に反事実的リグレット最小化(CFR)アルゴリズムを実施するためのサンプリング方式の例について記載し、この方式は、CFRアルゴリズムの収束速度を改善しながら、計算複雑性および分散を低減することができる。本明細書は、ニューラルネットワークを用いて反事実的リグレット最小化(CFR)を実施するための技法についても記載し、この技法は、ニューラルネットワークの汎化能力により、メモリ空間を節約し、より速い収束を提供することができる。
【０００５】
特定の実施形態で実装される、本明細書に記載する主題は、以下の技術的効果および利点のうちの1つまたは複数を実現する。いくつかの実施形態では、記載するサンプリング技法は、より効率的に、2人以上の当事者が関与するIIGなど、当事者の間の戦略的対話によってモデル化され、または表され得るリソース割り当て、製品/サービス推奨、サイバー攻撃予測および/または防止、トラフィックルーティング、不正管理などのような、実世界シナリオのより優れた戦略を見つけるのを助けることができる。いくつかの実施形態では、記載する技法は、IIGによってモデル化される実世界シナリオの最良戦略を見つける際に、計算効率を改善し、反事実的リグレット最小化(CFR)アルゴリズムの計算負荷を低減することができる。いくつかの実施形態では、記載するサンプリング技法は、結果サンプリングよりも低い分散を提供することができると同時に、外部サンプリングよりもメモリ効率的である。いくつかの実施形態では、記載する技法は、1つまたは複数の実世界シナリオを表すゲームを解くためのナッシュ均衡を見つける際の、CFRアルゴリズムの収束速度を改善することができる。いくつかの実施形態では、記載する技法は、CFRアルゴリズムが、より小さい分散およびより速い収束速度を有し得るように、IIGを表すゲームツリーの、より偏りのない、包括的な情報を提供する。いくつかの実施形態では、記載する技法は、CFRアルゴリズムと関連してニューラルネットワークを使うことによって、メモリ空間を節約し、より速い収束を提供する。いくつかの実施形態では、記載する技法は、CFRアルゴリズムの各反復のために、少量のメモリ空間を必要とするだけでよい。
【０００６】
本明細書は、1つまたは複数のプロセッサに結合されるとともに、1つまたは複数のプロセッサによって実行されると、1つまたは複数のプロセッサに、本明細書において提供される方法の実施形態に従って動作を実施させる命令を記憶した1つまたは複数の非一時的コンピュータ可読記憶媒体も提供する。
【０００７】
本明細書は、本明細書において提供される方法を実装するためのシステムをさらに提供する。このシステムは、1つまたは複数のプロセッサと、1つまたは複数のプロセッサによって実行されると、1つまたは複数のプロセッサに、本明細書において提供される方法の実施形態に従って動作を実施させる命令を記憶した1つまたは複数のプロセッサに結合されたコンピュータ可読記憶媒体とを含む。
【０００８】
本明細書による方法は、本明細書に記載する態様および特徴の任意の組合せを含み得ることを諒解されたい。つまり、本明細書による方法は、本明細書において具体的に記載される態様および特徴の組合せに限定されるのではなく、提供される態様および特徴の任意の組合せを含む。
【０００９】
本明細書の1つまたは複数の実施形態の詳細が、添付図面および以下の説明に記載される。本明細書の他の特徴および利点は、説明および図面から、ならびに特許請求の範囲から明らかになるであろう。
【図面の簡単な説明】
【００１０】
【図１】本明細書の実施形態による、1枚ポーカーにおける部分的ゲームツリーの例を示す図である。
【図２】本明細書の実施形態による異なるサンプリング方式の例を示す図である。
【図３】本明細書の実施形態による、ロバストサンプリング・モンテカルロCFR(MCCFR)の例の擬似コードである。
【図４】本明細書の実施形態による、ゲームツリーに適用される二重ニューラルCFRアルゴリズムの例を示す図である。
【図５】本明細書の実施形態による、二重ニューラルCFRアルゴリズムの例の擬似コードである。
【図６】本明細書の実施形態による、二重ニューラルCFRアルゴリズムに関連してニューラルネットワークを最適化するためのアルゴリズムの例の擬似コードである。
【図７】本明細書の実施形態による、ミニバッチMCCFRアルゴリズムの例の擬似コードである。
【図８】本明細書の実施形態による、MCCFRを実施するためのサンプリングプロセスの例を示すフローチャートである。
【図９】本明細書の実施形態による二重ニューラルCFRアルゴリズムの例を示すフローチャートである。
【図１０】本明細書の実施形態による、記載するアルゴリズム、方法、機能、プロセス、フロー、および手順に関連付けられた計算機能性を提供するのに使われるコンピュータ実装システムの例を示すブロック図である。
【図１１】本明細書の実施形態による装置のモジュールの例を示す図である。
【図１２】本明細書の実施形態による他の装置のモジュールの例を示す図である。
【発明を実施するための形態】
【００１１】
様々な図面における同様の参照番号および名称は、同様の要素を示す。
【００１２】
本明細書の実装形態は、たとえば、不完全情報ゲーム(IIG)を解くことによる、当事者の間の戦略的対話における戦略探索のためのコンピュータ実装方法を含む。IIGは、2人以上の当事者(プレーヤとも呼ばれる)が関与する、リソース割り当て、製品/サービス推奨、サイバー攻撃予測および/または防止、トラフィックルーティング、不正管理などといった、1つまたは複数の実世界シナリオを表すことができ、各当事者は、他の当事者の意思決定についての不十分または不完全な情報を有し得る。より詳細には、本明細書は、IIGを解く際に反事実的リグレット最小化(CFR)アルゴリズムを実施するためのサンプリング方式の例について記載し、この方式は、CFRアルゴリズムの収束速度を改善しつつ、計算複雑性および分散を低減することができる。本明細書は、ニューラルネットワークを用いて反事実的リグレット最小化(CFR)を実施するための技法についても記載し、この技法は、ニューラルネットワークの汎化能力により、メモリ空間を節約し、より速い収束を提供することができる。
【００１３】
ナッシュ均衡は、2人以上のプレーヤが関与するIIGのための典型的な解である。反事実的リグレット最小化(CFR)は、大規模なゲームのためのナッシュ均衡を近似的に見つけるように設計されたアルゴリズムである。CFRは、全体としての反事実リグレットを最小限にしようとする。すべての反復における戦略の平均は、ナッシュ均衡に収束するはずであることが証明されている。ゲームを解くとき、元の形のCFR(オリジナルCFR、標準CFR、バニラCFR、または単にCFRとも呼ばれる)が、各反復のたびにゲームツリー全体を巡回する。したがって、オリジナルCFRは、heads-up no-limit Texas Hold'emなどの、大規模なゼロサム展開形ゲームのためには大容量メモリを要求する。いくつかの事例では、オリジナルCFRは、限られたメモリでは大規模なゲームを扱うことができないことがある。
【００１４】
反事実リグレットを最小限にするために、モンテカルロCFR(MCCFR)が導入された。MCCFRは、反事実値の不偏推定量を計算し、ゲームツリー全体を巡回するのを避けることができる。すべての情報集合の部分集合のみが各反復において訪問されるので、MCCFRは、オリジナルCFRよりも少ないメモリを必要とする。
【００１５】
MCCFRは、結果サンプリングアルゴリズムまたは外部サンプリングアルゴリズムを用いて実施され得る。MCCFRにおける結果サンプリングアルゴリズムは、大きい分散を有し、より少ない反復ステップで近似ナッシュ均衡解に収束するのは難しい。MCCFRにおける外部サンプリングアルゴリズムは、結果サンプリングアルゴリズムよりも小さい分散を有するが、この方法は、CFRの欠点と同様である。ゲームツリーが大きいとき、非常に大きなメモリ空間を必要とし、複雑な大規模IIGへと拡張することができない。
【００１６】
本明細書は、ロバストサンプリング方式を開示する。ロバストサンプリング方式では、各プレーヤは、現在の決定点においてサンプリングするのに、一様サンプリング方法を使い、他の当事者は、対応する戦略に従ってサンプリングする。異なる反復に対応する到達確率は固定されうる。ロバストサンプリング方式は、外部サンプリングよりもメモリ効率がよい一方で、MCCFRにおける結果サンプリング方式よりも小さい分散を有することが証明され得る。いくつかの実施形態では、ロバストサンプリング方式は、MCCFRに、より速い収束でナッシュ均衡を解かせることができる。
【００１７】
本明細書は、深さ依存サンプリング方式を開示する。深さ依存サンプリング方式は、
終端状態から離れた他の状態よりも終端状態に近い(または初期もしくは開始状態により近い)状態に、より高いサンプリング確率を割り当てることができる。いくつかの実施形態では、深さ依存サンプリング方式は、終端状態により近い、より多くの状態がサンプリングされることを可能とし、IIGのより万遍のない(well-around)情報を提供し、したがって、既存のサンプリング方式と比較してMCCFRの収束レートを改善することができる。
【００１８】
本明細書は、二重ニューラルCFRアルゴリズムをさらに開示する。CFRおよびMCCFRなど、既存のCFR方法は、すべての情報集合についての累積リグレットおよび平均戦略を記録するのに、2つの大容量表ベースメモリを使う。そのような表による表現は、これらの方法を、限られた時間および空間をもつ大規模な展開型ゲームに適用しにくくさせる。
【００１９】
対照的に、二重ニューラルCFRアルゴリズムは、IIGの近似ナッシュ均衡を計算するのに、2つのニューラルネットワークを使う。たとえば、ニューラルネットワークの一方は、累積リグレットを学習するのに使うことができ、他方は、平均戦略プロファイルの累積分子を学習するのに使うことができる。これらの2つのネットワークの助けを受けると、二重ニューラルCFRアルゴリズムは、2つの大容量表ベースメモリを使う必要はない。コンパクトなニューラルネットワークの汎化能力に基づいて、累積リグレットおよび平均戦略が学習され、生成されうる。開示する二重ニューラルCFRアルゴリズムは、2つの大容量表メモリの必要なしに、より少ない計算負荷を必要とするという、MCCFRの利益を保つことができる。開示する二重ニューラルCFRアルゴリズムは、メモリ制約があっても、大規模なゲームにおいて使うことができる。いくつかの実施形態では、二重ニューラル方法は、既存の技法よりも少ない反復で、より低い可搾取量を達成し得る。さらに、いくつかの実施形態では、二重ニューラルCFRは、不十分な表戦略からの初期化の後も絶えず向上し得る。
【００２０】
いくつかの実施形態では、記載する技法は、たとえば、AIポーカー、推奨プラットフォーム、ならびに多くの他のAIおよび機械学習用途において使うことができる。記載する技法は、モンテカルロ方法を使い、ゲームツリー全体のための変数を必要としない。
【００２１】
いくつかの実施形態では、プレーヤの有限集合N={0,1,...,n-1}をもつ展開型ゲームは、以下のように表され得る。hviを、IIGにおけるプレーヤiの隠れた変数と定義する。たとえば、ポーカーゲームにおいて、hviは、プレーヤiの非公開カードを指すことができる。Hは、履歴の有限集合を指す。Hの各メンバー
【００２２】
【数１】
2021509492.tif 000003
【００２３】
は、可能な履歴(または状態)を示し、これは、各プレーヤの隠れた変数と、チャンスを含む、プレーヤによってとられるL個の行動とを含む。プレーヤiについて、hは、
【００２４】
【数２】
2021509492.tif 000004
【００２５】
として示すこともでき、ここで、
【００２６】
【数３】
2021509492.tif 000005
【００２７】
は、対戦相手の隠れた変数を指す。空のシーケンスφは、Hのメンバーである。表現
【００２８】
【数４】
2021509492.tif 000006
【００２９】
は、hjがhのプレフィックスであることを示し、ここで、
【００３０】
【数５】
2021509492.tif 000007
【００３１】
であり、0<L'<Lである。Z⊆Hは終端履歴を示し、いずれのメンバーz∈Zも、いずれの他のシーケンスのプレフィックスではない。A(h)={a:ha∈H}は、非終端履歴h∈H＼Zの後の利用可能な行動の集合である。プレーヤ関数Pは、N∪{c}のメンバーを各非終端履歴に割り当て、ここでcは、チャンスプレーヤ識別子(ID)を示し、これは典型的には、たとえば、-1であり得る。P(h)は、履歴hの後に行動をとるプレーヤである。
【００３２】
履歴{h∈H:P(h)=i}のIiは、プレーヤiの情報区分である。集合Ii∈Iiは、プレーヤiの情報集合である。Ii(h)は、状態hにおける情報集合Iiを指す。いくつかの実施形態では、Iiは、プレーヤiの隠れた変数および公開行動を含む、プレーヤiによって観察される情報を覚えておくだけでよい。したがって、Iiは、IIGにおけるシーケンス、すなわち、hvia0a2...aL-1を示す。いくつかの実施形態では、Ii∈Iiについて、および任意のh∈Iiについて、集合A(h)はA(Ii)によって示すことができ、プレーヤP(h)はP(Ii)によって示される。各プレーヤi∈Nについて、効用関数ui(z)は、終端状態zにおける利得を定義する。これらの表記および定義のより詳細な説明について、図1に示す例を含め、以下で論じられる。
【００３３】
図1は、本明細書の実施形態による、1枚ポーカーにおける部分的ゲームツリー102および104の例を示すダイアグラム100である。1枚ポーカーとは、ポーカーの2プレーヤIIGである。1枚ポーカーは、展開型ゲームの例である。ゲーム規則は、以下のように定義される。各プレーヤは、X枚のカードからなるデッキから、1枚のカードを配られる。第1のプレーヤは、パスまたはベットすることができる。第1のプレーヤがベットした場合、第2のプレーヤはコールまたはフォールドすることができる。第1のプレーヤがパスした場合、第2のプレーヤはパスまたはベットすることができる。第2のプレーヤがベットした場合、第1のプレーヤはフォールドまたはコールすることができる。ゲームは、2回のパス、1回のコール、または1回のフォールドで終わる。フォールドプレーヤは、1チップを失うことになる。2回のパスでゲームが終わった場合、より高いカードをもっているプレーヤが1チップを勝ち取る。1回のコールでゲームが終わった場合、より高いカードをもっているプレーヤが2チップを勝ち取る。
【００３４】
ゲームツリーは有向グラフである。ゲームツリーのノードは、ゲームにおける位置(またはプレーヤの状態)を表し、ゲームのプレーヤの動きまたは行動を表すことができる。図1において、ziは、終端状態を表す終端ノードを示し、hiは非終端ノードを示す。部分的ゲームツリー102および104の各々は、チャンスを表すルートノードh0を有する。第1の部分ツリー102には19個の別個のノードがあり、左ツリー中の、チャンスh0を含む9つの非終端ノードhiおよび10個の終端ノードziに対応する。
【００３５】
第1の部分ツリー102では、2人のプレーヤ(プレーヤ0およびプレーヤ1)は、左サブツリーにおいて「0:Q 1:J」と示されるように(クイーン、ジャック)を、および右サブツリーにおいて「0:Q 1:K」と示されるように(クイーン、キング)を配られる。
【００３６】
ルートノードから各ノードへの軌線は、行動の履歴である。行動は、ゲームツリーの辺(矢印によって示される)の隣の文字(たとえば、F、C、P、およびB)または表現(たとえば、「0:Q 1:J」)によって提示される。文字F、C、P、Bは、それぞれ、フォールド、コール、パス、およびベットを指す。
【００３７】
展開型ゲームにおいて、hiは行動の履歴を指す。たとえば、第1の部分ツリー102に示すように、h3は行動0:Q、1:JおよびPを含む。h7は、行動0:Q、1:J、PおよびBを含む。h8は、行動0:Q、1:K、PおよびBを含む。第1の部分ツリー102において、
【００３８】
【数６】
2021509492.tif 000008
【００３９】
であり、つまり、h3はh7のプレフィックスである。A(h3)={P,B}は、非終端履歴h3の後の利用可能な行動の集合がPおよびBであることを示す。P(h3)=1は、履歴h3の後に行動をとるプレーヤがプレーヤ1であることを示す。
【００４０】
IIGでは、プレーヤ1の非公開カードはプレーヤ0には見えず、したがって、h7およびh8は実際には、プレーヤ0にとって同じである。情報集合は、これらの区別されない状態の集合を示すのに使うことができる。同様に、h1およびh2は同じ情報集合の中にある。右部分ツリー104について、h'3およびh'5は、同じ情報集合の中にあり、h'4およびh'6は、同じ情報集合の中にある。
【００４１】
典型的には、任意のIi∈Iは、プレーヤiの隠れた変数および公開行動を含む、プレーヤiによって観察される情報を覚えておくだけでよい。たとえば、第1の部分ツリー102に示すように、h7およびh8の情報集合は、0:Q、P、およびBのシーケンスを示す。h7およびh8は、IIGにおけるプレーヤ0によって区別されないので、I0がh7およびh8の情報集合である場合、I0=I0(h7)=I0(h8)である。
【００４２】
戦略プロファイルσ={σi|σi∈Σi,i∈N}は、すべてのプレーヤについての戦略の集合体であり、Σiは、プレーヤiについてのすべての可能な戦略の集合である。σ-iは、プレーヤi以外のすべてのプレーヤの戦略を指す。プレーヤi∈Nに対して、戦略σi(Ii)は関数であり、これは、A(Ii)にわたる行動分布を情報集合Iiに割り当てる。σi(a|h)は、状態hにおいてプレーヤi∈N∪{c}によってとられる行動aの確率を示す。IIGでは、2つ以上の状態が同じ情報集合を有する場合、2つ以上の状態は同じ戦略を有する。つまり、∀h1,h2∈Ii、Ii=Ii(h1)=Ii(h2)、σi(Ii)=σi(h1)=σi(h2)、σi(a|Ii)=σi(a|h1)=σi(a|h2)である。たとえば、I0は、h7およびh8の情報集合であり、I0=I0(h7)=I0(h8)、σ0(I0)=σ0(h7)=σ0(h8)、σ0(a|I0)=σ0(a|h7)=σ0(a|h8)である。図1において、各状態についてのグレー以外の同じ色は、同じ情報集合の中にある。
【００４３】
プレーヤiについて、戦略プロファイルσの期待ゲーム効用は、
【００４４】
【数７】
2021509492.tif 000009
【００４５】
として示され、これは、すべての可能な終端ノードの期待利得である。固定戦略プロファイルσ-iが与えられると、
【００４６】
【数８】
2021509492.tif 000010
【００４７】
に対する最大利得を達成する、プレーヤiの任意の戦略σi*=arg max
【００４８】
【数９】
2021509492.tif 000011
【００４９】
が最適応答である。2人のプレーヤの展開型ゲームに対して、ナッシュ均衡は、各プレーヤの戦略が対戦相手にとって最適応答であるような戦略プロファイル
【００５０】
【数１０】
2021509492.tif 000012
【００５１】
である。∈ナッシュ均衡は、ナッシュ均衡の近似であり、その戦略プロファイルσ*は、
【００５２】
【数１１】
2021509492.tif 000013
【００５３】
を満たす。
【００５４】
戦略σiの可搾取量は、
【００５５】
【数１２】
2021509492.tif 000014
【００５６】
と定義され得る。戦略は、∈i(σi)=0である場合、搾取不可能である。ポーカーなどの大規模な2プレーヤゼロサムゲームでは、
【００５７】
【数１３】
2021509492.tif 000015
【００５８】
は、計算するのが困難な場合がある。ただし、プレーヤが位置を交替した場合、ゲームのペアの値はゼロであり、すなわち、
【００５９】
【数１４】
2021509492.tif 000016
【００６０】
である。戦略プロファイルσの可搾取量は、
【００６１】
【数１５】
2021509492.tif 000017
【００６２】
と定義され得る。
【００６３】
CFRなどの反復方法に対して、σtは、第tの反復における戦略プロファイルを指し得る。履歴hの状態到達確率は、プレーヤがσに従って行動をとる場合、πσ(h)によって示すことができる。空のシーケンスに対して、πσ(φ)=1である。到達確率は、各プレーヤの寄与に従って、
【００６４】
【数１６】
2021509492.tif 000018
【００６５】
に分解することができ、ここで、
【００６６】
【数１７】
2021509492.tif 000019
【００６７】
である。
【００６８】
情報集合Iiの到達確率(情報集合到達確率とも呼ばれる)は、
【００６９】
【数１８】
2021509492.tif 000020
【００７０】
と定義され得る。
【００７１】
【数１９】
2021509492.tif 000021
【００７２】
である場合、状態h'からhへの間隔状態到達確率は、πσ(h',h)と定義することができ、したがってπσ(h',h)=πσ(h)/πσ(h')である。到達確率
【００７３】
【数２０】
2021509492.tif 000022
【００７４】
が同様に定義され得る。
【００７５】
大型でゼロサムのIIGにおいて、CFRは、ナッシュ均衡を計算するための効率的方法であると証明されている。1人のプレーヤの状態到達確率は、対戦相手の隠れた変数の事後確率に比例することが証明されており、すなわち、
【００７６】
【数２１】
2021509492.tif 000023
【００７７】
であり、ここでhviおよびIiはある特定のhを示す。
【００７８】
プレーヤiおよび戦略プロファイルσに対して、状態hにおける反事実値(CFV)viσ(h)は、
【００７９】
【数２２】
2021509492.tif 000024
【００８０】
と定義されてよく、ここで、
【００８１】
【数２３】
2021509492.tif 000025
【００８２】
は、対戦相手の隠れた変数の近似された事後分布に関する、プレーヤiの期待報酬である。行動aをとる行動反事実値は、viσ(a|h)=viσ(ha)と示すことができ、この行動をとるリグレットは、riσ(a|h)=viσ(a|h)-viσ(h)である。
【００８３】
同様に、情報集合IiのCFVは、
【００８４】
【数２４】
2021509492.tif 000026
【００８５】
と定義することができ、情報集合Iiを与えられた行動aのリグレットは、
【００８６】
【数２５】
2021509492.tif 000027
【００８７】
と定義することができる。
【００８８】
次いで、T回の反復の後の行動aの累積リグレットは、式(2)
【００８９】
【数２６】
2021509492.tif 000028
【００９０】
に従って算出することができ、上式で、Ri0(a|Ii)=0である。RiT,+(a|Ii)=max(RiT(a|Ii),0)と定義すると、T+1反復における現在の戦略(または挙動戦略)は、たとえば、以下の式(3)に従って、リグレットマッチングに基づいて更新され得る。
【００９１】
【数２７】
2021509492.tif 000029
【００９２】
反復1からTまでの平均戦略
【００９３】
【数２８】
2021509492.tif 000030
【００９４】
は、
【００９５】
【数２９】
2021509492.tif 000031
【００９６】
と定義することができ、上式で、
【００９７】
【数３０】
2021509492.tif 000032
【００９８】
は、第tの反復におけるIiの情報集合到達確率を示し、対応する現在の戦略
【００９９】
【数３１】
2021509492.tif 000033
【０１００】
を重み付けするのに使われる。
【０１０１】
【数３２】
2021509492.tif 000034
【０１０２】
を反復tにおける追加分子と定義すると、平均戦略
【０１０３】
【数３３】
2021509492.tif 000035
【０１０４】
の累積分子は、
【０１０５】
【数３４】
2021509492.tif 000036
【０１０６】
と定義することができ、上式で、S0(a|Ii)=0である。
【０１０７】
ゲームを解くとき、オリジナルCFRは、各反復においてゲームツリー全体を巡回する。これにより、オリジナルCFRは、限られたメモリでは大規模なゲームを扱うことができない。反事実リグレットを最小限にするために、モンテカルロCFR(MCCFR)が導入された。MCCFRは、反事実値の不偏推定量を計算し、ゲームツリー全体を巡回するのを避けることができる。すべての情報集合の部分集合のみが各反復において訪問されるので、MCCFRは、オリジナルCFRよりも小さいメモリを必要とする。
【０１０８】
たとえば、Q={Q1,Q2,...,Qm}を定義し、ここで、Qj∈Zは、Qjが集合Zに広がるような、各反復におけるサンプリング終端履歴のブロックである。概して、異なるQjは、指定されたサンプリング方式に従って重複を有し得る。いくつかのサンプリング方式が使用され得る。
【０１０９】
図2は、本明細書の実施形態による異なるサンプリング方式の例を示すダイアグラム200である。具体的には、サブプロットAは、ゲームツリーの外部サンプリング方式202の例を示し、サブプロットBは、ゲームツリーの結果サンプリング方式204の例を示し、サブプロットCは、ゲームツリーのロバストサンプリング方式206の例を示す。
【０１１０】
図2に示すように、円はプレーヤ0ノードを表し、矩形はプレーヤ1ノードを表し、三角形はチャンスノードを表す。実線の辺または矢印は、サンプリングされる行動を提示し、破線の辺または矢印は、サンプリングされない行動を提示する。影付きノードは、サンプリングされるノードを提示し、ブランクノードは、サンプリングされないノードを提示する。
【０１１１】
プレーヤ0の更新を一例としてとると、サブプロットAに示す外部サンプリング方式202を用いて、プレーヤ0ノードは、プレーヤ0ノードのすべての分岐を巡回し、非プレーヤ0ノード(たとえば、プレーヤ1ノードおよびチャンスノード)は、対応するサンプリング戦略に従って、分岐をランダムにサンプリングする。
【０１１２】
結果サンプリング方式は、異なるプレーヤを区別しない。サブプロットBに示すように、結果サンプリング方式204は、対応するサンプリング戦略に従って、すべてのプレーヤについて、1つの分岐をランダムにサンプリングする。したがって、結果サンプリング方式の下では、ただ1つの軌線がサンプリングされることになる。
【０１１３】
サブプロットCに示すように、ロバストサンプリング方式206は、プレーヤ0についての一様分布に従って、k個の分岐をランダムに選択し、対応するサンプリング戦略に従って、非プレーヤ0ノードについての1つの分岐に対してランダムサンプリングを実施する。kの値を変えることによって、ロバストサンプリング方式は、たとえば、実際のメモリ必要性またはシステム仕様に依存して、複数の経路、または単一の経路をサンプリングすることができる。外部サンプリング方式とは異なり、ロバストサンプリング方式は、すべての可能な行動の知識および現在のプレーヤiの決定点における変数を毎回要求するわけではない。
【０１１４】
いくつかの実施形態では、外部サンプリングおよび結果サンプリング方式において、各ブロックQj∈QはZの区分を表す。qQjを、ブロックQjを検討する確率と定義し、ここで、
【０１１５】
【数３５】
2021509492.tif 000037
【０１１６】
である。
【０１１７】
【数３６】
2021509492.tif 000038
【０１１８】
を、特定の終端履歴zを検討する確率と定義する。いくつかの実施形態では、バニラCFRは、MCCFRの特殊ケースと見なすことができ、Q={Z}は、1つのブロックを含むだけであり、qQ1=1である。
【０１１９】
結果サンプリング方式では、∀Qj∈Q、|Qj|=1および|Qj|=|Z|となるように、ただ1つの軌線がサンプリングされることになる。情報集合Iiについて、反事実値のサンプル推定値は、
【０１２０】
【数３７】
2021509492.tif 000039
【０１２１】
である。
【０１２２】
MCCFRにおけるサンプリング反事実値は、CFR:
【０１２３】
【数３８】
2021509492.tif 000040
【０１２４】
における実際の反事実値の不偏推定量であることが証明されている。
【０１２５】
σrsをサンプリング戦略プロファイルとして定義し、ここで、
【０１２６】
【数３９】
2021509492.tif 000041
【０１２７】
は、プレーヤiについてのサンプリング戦略であり、
【０１２８】
【数４０】
2021509492.tif 000042
【０１２９】
は、プレーヤiを除くプレーヤについてのサンプリング戦略である。いくつかの実施形態では、外部サンプリングと結果サンプリングの両方について、
【０１３０】
【数４１】
2021509492.tif 000043
【０１３１】
である。サンプリングされた行動a∈A(Ii)のリグレットは、
【０１３２】
【数４２】
2021509492.tif 000044
【０１３３】
と定義することができ、ここで、
【０１３４】
【数４３】
2021509492.tif 000045
【０１３５】
は、
【０１３６】
【数４４】
2021509492.tif 000046
【０１３７】
によって重み付けられた新たな効用である。T回の反復の後の行動aの累積リグレットについてのサンプル推定値は、
【０１３８】
【数４５】
2021509492.tif 000047
【０１３９】
と定義することができる。
【０１４０】
ロバストサンプリングに対して、サンプリングプロファイルは、
【０１４１】
【数４６】
2021509492.tif 000048
【０１４２】
と定義することができ、ここで、プレーヤiは、各情報集合Iiについてのサンプリング戦略
【０１４３】
【数４７】
2021509492.tif 000049
【０１４４】
に従って、k個の行動をランダムに選択することができ、他のプレーヤは、戦略σ-iに従って1つの行動をランダムに選択することができる。
【０１４５】
いくつかの実施形態では、プレーヤiが、情報集合Iiにおける離散一様分布unif(0,|A(Ii)|)に従ってmin(k,|A(Ii)|)個の行動をランダムに選択した、つまり、
【０１４６】
【数４８】
2021509492.tif 000050
【０１４７】
である場合、サンプリング戦略またはプロファイル
【０１４８】
【数４９】
2021509492.tif 000051
【０１４９】
に従って行動をプレーヤiがとった場合の情報集合Iiの到達確率は、
【０１５０】
【数５０】
2021509492.tif 000052
【０１５１】
によって算出することができ、重み付き効用
【０１５２】
【数５１】
2021509492.tif 000053
【０１５３】
は、サンプリングプロファイルσrs(k)を与えられた場合の各反復における定数であってよく、低い分散を有する。さらに、重み付き効用は、対戦相手の戦略の明示的知識をもはや必要としないため、ロバストサンプリングは、オンラインリグレット最小化のために使われ得る。
【０１５４】
表記を簡素化するために、k=maxはk=maxIi∈I|A(Ii)|を指すものとする。k=maxであり、プレーヤiが情報集合Iiにおける離散一様分布unif(0,|A(Ii)|)、∀i∈N、∀Ii∈Li、∀a∈A(Ii)、
【０１５５】
【数５２】
2021509492.tif 000054
【０１５６】
に従ってk個の行動をランダムに選択する場合、ロバストサンプリングは、k=maxIi∈I|A(Ii)|であるときの外部サンプリングと同様であってよい。
【０１５７】
k=1および
【０１５８】
【数５３】
2021509492.tif 000055
【０１５９】
であり、ただ1つの履歴zがこのケースにおいてサンプリングされる場合、
【０１６０】
【数５４】
2021509492.tif 000056
【０１６１】
、∃h∈Iiであり、a∈Ars(k)(Ii)に対して、
【０１６２】
【数５５】
2021509492.tif 000057
【０１６３】
である。
【０１６４】
行動aが状態hにおいてサンプリングされない、すなわち、
【０１６５】
【数５６】
2021509492.tif 000058
【０１６６】
である場合、リグレットは、
【０１６７】
【数５７】
2021509492.tif 000059
【０１６８】
である。この場合、ロバストサンプリングは、k=1および
【０１６９】
【数５８】
2021509492.tif 000060
【０１７０】
であるときの結果サンプリングと同様である。
【０１７１】
k=1であり、プレーヤiが、情報集合Iiにおける離散一様分布unif(0,|A(Ii)|)に従って1つの行動をランダムに選択する場合、ロバストサンプリングは結果サンプリングと同様であってよい。たとえば、k=1であり、プレーヤiが、情報集合Iiにおける離散一様分布unif(0,|A(Ii)|)に従って1つの行動をランダムに選択する場合、
【０１７２】
【数５９】
2021509492.tif 000061
【０１７３】
は定数であり、∃h∈Iiであり、a∈Ars(k)(Ii)に対して、
【０１７４】
【数６０】
2021509492.tif 000062
【０１７５】
である。
【０１７６】
行動aが状態hにおいてサンプリングされない、すなわち、
【０１７７】
【数６１】
2021509492.tif 000063
【０１７８】
である場合、リグレットは、
【０１７９】
【数６２】
2021509492.tif 000064
【０１８０】
である。結果サンプリングと比較して、この場合のロバストサンプリングは、定数
【０１８１】
【数６３】
2021509492.tif 000065
【０１８２】
により、より低い分散を有する。
【０１８３】
図3は、本明細書の実施形態による、ロバストサンプリングMCCFRの例の擬似コード300である。擬似コード300の行1〜5に示すように、全体としてのロバストサンプリングMCCFRは、反復の総数、すなわちt個の入力をもつ反復アルゴリズムである。各反復tにおいて、累積リグレットRt(・|Ii)および平均戦略分子St(a|Ii)を更新するために、プレーヤ0およびプレーヤ1について関数ロバストサンプリングMCCFR(RS-MCCFR)が呼び出される(行3および4に示す)。関数RS-MCCFRは、擬似コード300の行6〜30に示すように定義され得る。関数RS-MCCFRは、各情報集合の反事実値を出力として戻す。いくつかの実施形態では、反事実値は、反事実リグレットを算出するのに使われ得る。したがって、累積リグレットおよび時間平均戦略が相応して取得され得る。
【０１８４】
具体的には、関数RS-MCCFRは、図2に関連して上述したように、ロバストサンプリング方式に従って行動をサンプリングする。擬似コード300の行16に示すように、k個の異なる行動が、ロバストサンプリング戦略
【０１８５】
【数６４】
2021509492.tif 000066
【０１８６】
に従って、Ars(k)(Ii)としてサンプリングされ、収集され得る。
【０１８７】
いくつかの実施形態では、深さ依存サンプリング方式が、ゲームツリーによって表される、ゲームの、より偏りのない、または万遍のない情報を提供するのに使われ得る。たとえば、サンプリング戦略
【０１８８】
【数６５】
2021509492.tif 000067
【０１８９】
は、ゲームツリーにおける状態hの深さの関数であり得る。たとえば、サンプリング戦略
【０１９０】
【数６６】
2021509492.tif 000068
【０１９１】
は、終端状態により近い状態が、初期状態(たとえば、ゲームツリーのルートによって表される)により近い状態よりも高い、サンプリングされる確率を有するように設計されてよい。一例として、深さ依存サンプリング方式は、異なる深さをもつ異なる状態のサンプリング確率に異なる重みを適用することによって実装され得る。そのような深さ依存サンプリングは、終端状態により近い状態についてのより多くの情報を提供するのを助けることができ、これは、典型的には、(たとえば、ゲームツリーの分岐構造により)初期状態により近いものよりも終端状態により近い状態が多く、これらのノードは、既存のサンプリング方式の下でサンプリングされた軌線においては、ルートノードにより近いノードよりも、サンプリングされるチャンスが低いので、有利であり得る。
【０１９２】
いくつかの実施形態では、深さ依存サンプリング方式は、ロバストサンプリング、結果サンプリング、外部サンプリング、またはどの他の適切なサンプリングアルゴリズムとの組合せでも使われ得る。たとえば、深さ依存サンプリング方式は、ロバストサンプリング、結果サンプリング、および外部サンプリングのいずれかの分散および収束速度をさらに改善することができるが、それは、後者の3つのサンプリング方式は、プレーヤの状態の異なる行動(たとえば、ゲームツリーのノードの異なる分岐によって表される)の中で、水平サンプリングにより焦点を合わせるからである。
【０１９３】
図4は、本明細書の実施形態による、ゲームツリー410に適用される二重ニューラルCFRアルゴリズムの例400を示す図である。二重ニューラルCFRアルゴリズム400は、ゲームツリー410によって表されるようなIIGの近似ナッシュ均衡を計算するのに、2つのニューラルネットワーク420および430を使う。図4に示すように、一方のニューラルネットワーク420が、累積リグレットを取得するために使われ、RegretSumNetwork(RSN)と呼ばれる。他のニューラルネットワーク430は、平均戦略を取得するために使われ、AveStrategyNetwork(ASN)と呼ばれる。
【０１９４】
いくつかの実施形態では、CFRアルゴリズムの反復更新は、2つの戦略、すなわち、現在の戦略σit(a|Ii)、および∀i∈N、∀Ii∈Ii、∀a∈A(Ii)、∀t∈{1,...,T}に対する平均戦略
【０１９５】
【数６７】
2021509492.tif 000069
【０１９６】
を維持する。したがって、2つのニューラルネットワーク420および430は、それぞれ、これらの2つの戦略を反復方式で記録するように設計され得る。いくつかの実施形態では、ニューラルネットワークが、各反復において新たな追加サンプルに基づいてトレーニングまたは最適化されるので、二重ニューラルCFRアルゴリズムの例400は、二重増分CFRアルゴリズムと呼ばれる場合がある。
【０１９７】
式(3)によると、現在の戦略σt+1(a|Ii)は、累積リグレットRt(a|Ii)によって計算され得る。いくつかの実施形態では、戦略が使われるとき、分母における正規化は容易に計算され得るので、式(3)における分子のみが追跡される。情報集合Iiおよび行動aが与えられると、
【０１９８】
【数６８】
2021509492.tif 000070
【０１９９】
として示されるニューラルネットワークRSN420は、Rt(a|Ii)を学習するのに使うことができ、ここで、
【０２００】
【数６９】
2021509492.tif 000071
【０２０１】
は、第tの反復におけるRSN420中のパラメータである。
【０２０２】
図4に示されるように、メモリ
【０２０３】
【数７０】
2021509492.tif 000072
【０２０４】
は、
【０２０５】
【数７１】
2021509492.tif 000073
【０２０６】
と定義され得る。
【０２０７】
【数７２】
2021509492.tif 000074
【０２０８】
の各メンバーは、訪問された情報集合Iiおよび対応するリグレット
【０２０９】
【数７３】
2021509492.tif 000075
【０２１０】
を含んでよく、ここで、Qjは、第tの反復におけるサンプリングされたブロックである。式(2)によると、
【０２１１】
【数７４】
2021509492.tif 000076
【０２１２】
は、以下の最適化、すなわち
【０２１３】
【数７５】
2021509492.tif 000077
【０２１４】
を使って推定され得る。式(4)によると、近似ナッシュ均衡は、T回の反復にわたる、すべての前の戦略の重み付き平均である。累積リグレットと同様、
【０２１５】
【数７６】
2021509492.tif 000078
【０２１６】
として示される他のニューラルネットワークASN430が、平均戦略の分子を学習するのに使われ得る。他のメモリ
【０２１７】
【数７７】
2021509492.tif 000079
【０２１８】
を、
【０２１９】
【数７８】
2021509492.tif 000080
【０２２０】
と定義する。
【０２２１】
【数７９】
2021509492.tif 000081
【０２２２】
の各メンバーは、訪問された情報集合Iiおよび
【０２２３】
【数８０】
2021509492.tif 000082
【０２２４】
の値を含んでよく、ここで、Qjは、第tの反復におけるサンプリングされたブロックである。次いで、ASN430のパラメータ
【０２２５】
【数８１】
2021509492.tif 000083
【０２２６】
が、以下の公式によって推定され得る。
【０２２７】
【数８２】
2021509492.tif 000084
【０２２８】
いくつかの実施形態では、各反復において、
【０２２９】
【数８３】
2021509492.tif 000085
【０２３０】
の両方が、以下で図7に関して記載するミニバッチ確率論的勾配降下方法などの勾配降下方法に従って式(7)および式(8)における目標を最適化することによって最適化され得る。
【０２３１】
いくつかの実施形態では、複数の反復において、
【０２３２】
【数８４】
2021509492.tif 000086
【０２３３】
を集約し、保存するのに大きいメモリが利用可能である場合、平均戦略は、各反復において更新する必要はない。メモリ
【０２３４】
【数８５】
2021509492.tif 000087
【０２３５】
が満杯である場合、増分値は、式(8)を最適化することによって学習され得る。
【０２３６】
いくつかの実施形態では、各反復において、情報集合の小さい部分集合のみがサンプリングされ、これは、ニューラルネットワークRSN420およびASN430が、観察されないか、またはサンプリングされない情報集合の値を忘れることにつながり得る。この問題に対処するために、前の反復からのニューラルネットワークパラメータが現在の反復の初期化として使われてよく、これは、更新にオンライン学習/適応特質を与える。さらに、ニューラルネットワークの汎化能力により、少数の情報集合からのサンプルさえも、新たなニューラルネットワークを更新するのに使うことができ、新たに更新されたニューラルネットワークは、いくつかの実施形態では、累積リグレットおよび平均戦略についての良好な値を生じ得る。
【０２３７】
いくつかの実施形態では、反復tの数が増すと、Rit(a|Ii)の値はますます大きくなる場合があり、可能性としては、ニューラルネットワークが学習するのを難しくする。この問題に対処するために、累積リグレットは、その範囲をより安定させるために、
【０２３８】
【数８６】
2021509492.tif 000088
【０２３９】
倍だけ正規化され得る。これは、オンライン学習のリグレット境界から理解することができる。より具体的には、Δ=maxIi,a,t|Rt(a|Ii)-Rt-1(a|Ii)|、∀Ii∈I、a∈A(Ii)、t∈{1,...,T}とする。
【０２４０】
【数８７】
2021509492.tif 000089
【０２４１】
であり、ここで、|A|=maxIi∈I|A(Ii)|である。いくつかの実施形態では、ニューラルネットワークRSN420は、
【０２４２】
【数８８】
2021509492.tif 000090
【０２４３】
を追跡し、それを
【０２４４】
【数８９】
2021509492.tif 000091
【０２４５】
によって更新するのに使うことができ、ここで、
【０２４６】
【数９０】
2021509492.tif 000092
【０２４７】
である。
【０２４８】
いくつかの実施形態では、二重増分CFRアルゴリズムにおいて、
【０２４９】
【数９１】
2021509492.tif 000093
【０２５０】
は、たとえば、
【０２５１】
【数９２】
2021509492.tif 000094
【０２５２】
の限られたサイズにより、各反復の後でクリアされてよい。いくつかの実施形態では、たとえば大規模なゲームにおいて、累積リグレットおよび平均戦略を学習するのにニューラルネットワークを使う二重増分CFRアルゴリズムを用いても、
【０２５３】
【数９３】
2021509492.tif 000095
【０２５４】
のサイズは、各反復についての累積リグレットおよび平均戦略を記録するために、依然として非常に大きい必要があり得る。
【０２５５】
いくつかの実施形態では、限られたメモリだが無限反復を用いて平均戦略を絶えず改善するため、および/またはメモリサイズに対する要件をさらに軽減するために、異なる反復にわたるサンプリングされた累積リグレットおよび平均戦略を保存するために、ならびに累積リグレットおよび平均戦略を動的に学習するために2つのリザーバMRおよびMSを使う二重リザーバCFRアルゴリズムが使われ得る。
【０２５６】
いくつかの実施形態では、T回の反復の後の平均累積リグレットは、式(2)を書き換えることによって、式(10)に従って取得され得る。
【０２５７】
【数９４】
2021509492.tif 000096
【０２５８】
同様に、平均戦略は、式(4)に示すように累積戦略の正規化であってよく、これは、その到達確率
【０２５９】
【数９５】
2021509492.tif 000097
【０２６０】
による重み付き平均戦略
【０２６１】
【数９６】
2021509492.tif 000098
【０２６２】
である。
【０２６３】
いくつかの実施形態では、2つの一様なリザーバMRおよびMSが、それぞれ、サンプリングされた
【０２６４】
【数９７】
2021509492.tif 000099
【０２６５】
およびst(a|Ii)を保存するのに使われ得る。具体的には、MRは、サンプルを
【０２６６】
【数９８】
2021509492.tif 000100
【０２６７】
に保存するためのリザーバであってよく、MSは、サンプルを
【０２６８】
【数９９】
2021509492.tif 000101
【０２６９】
に保存するためのリザーバであってよい。新たなサンプルが、リザーバサンプリングアルゴリズムによってリザーバの中に挿入され得る。リザーバサンプリングは、n個の項目を含むリストからk個の項目をランダムに選ぶためのランダムアルゴリズムのファミリーを含む。たとえば、リザーバが満杯でない場合、新たなサンプルがリザーバに直接追加されてよい。リザーバが満杯である場合、新たなサンプルが、たとえば、先入れ先出し(FIFO)原理に従って、または一様ランダム分布もしくは他の分布に従って、古いサンプルと置き換わり得る。
【０２７０】
二重増分CFRアルゴリズムと二重リザーバCFRアルゴリズムの両方が、オンライン学習における考え方を利用し、それぞれ、更新リグレットおよび平均戦略を学習するために2つのニューラルネットワークを使うことに留意されたい。いくつかの実施形態では、ASNは、各反復において更新される必要はなく、RSNは、新たな挙動戦略を生じるように、モンテカルロサンプリングの後で最適化される必要があり得る。たとえば、新たな挙動戦略が、ゲームツリーを巡回するのに使われるとき、RSNは、反復の度に更新される必要があり得る。一方、ASNは、挙動戦略の重み付き平均である最終近似ナッシュ均衡として使われ得る。ASNは、二重ニューラルCFRアルゴリズムの出力として働き得る。サンプルをすべて保存するための十分大きいデータストアがある場合、最終ステップにおいて平均戦略を最適化することが必要とされるだけである。実際、大規模なゲームの場合、大きいデータストアは非常に高価であり得る。したがって、平均戦略は、データストア(たとえば、リザーバ
【０２７１】
【数１００】
2021509492.tif 000102
【０２７２】
)が満杯である場合、増分的に最適化され得る。したがって、二重ニューラルCFRアルゴリズムは2つの変形を含み得る。二重増分アルゴリズムでは、ニューラルネットワーク(たとえば、RSNおよびASNの一方または両方)は増分サンプルのみによって最適化され、二重リザーバアルゴリズムでは、ニューラルネットワーク(たとえば、RSNおよびASNの一方または両方)は、リザーバ中のサンプルすべてによって最適化され得る。
【０２７３】
二重ニューラルCFRアルゴリズムおよび二重リザーバCFRアルゴリズムは、異なるサンプル集合体を有する。二重増分CFR用に、ニューラルネットワークは、新たに追加されたサンプルに基づいて最適化される。二重リザーバCFR用に、ニューラルネットワークは、固定サイズリザーバ中のサンプルに基づいて最適化される。さらに、二重リザーバ方法では、平均戦略は、最小二乗誤差ではなく最大対数尤度によって最適化され得る。
【０２７４】
図5は、本明細書の実施形態による、二重ニューラルCFRアルゴリズムの例の擬似コード500である。二重ニューラルCFRアルゴリズムの例は、二重ニューラルCFRアルゴリズムまたは二重リザーバCFRアルゴリズムを使うという選択肢を含む。
【０２７５】
擬似コード500の行3〜7は、第1の反復における初期化戦略の例を示す。たとえば、システムが、既存のCFR方法(たとえば、表ベースのCFRもしくはMCCFR方法または二重ニューラルCFR方法)からウォームスタートする場合、ニューラルネットワークは、累積リグレットおよび戦略をクローニングするように、既存の戦略プロファイルから初期化されてよい。ウォームスタート初期化がない場合、二重ニューラルCFRアルゴリズムは、反復t=1においてRSNおよびASNにおけるパラメータをランダムに初期化することによってスタートしてよい。
【０２７６】
いくつかの実施形態では、二重増分CFRアルゴリズムが使われる場合、擬似コード500の行8に示すように、この反復におけるサンプリングされた情報集合に対する、反事実リグレットと平均戦略の分子とを戻すのに、サンプリング方法が使われ得る。この反復における、サンプリングされた情報集合に対する反事実リグレットおよび平均戦略の分子は、それぞれ、
【０２７７】
【数１０１】
2021509492.tif 000103
【０２７８】
に保存されてよい。サンプリング方法は、たとえば、図7に関して記載するミニバッチロバストサンプリング方法アルゴリズムを含み得る。いくつかの実施形態では、この反復における、サンプリングされた情報集合に対する反事実リグレットは合計されて、たとえば、以下の式(11)および図7に関して記載するミニバッチMCCFRアルゴリズムに従って、情報集合による
【０２７９】
【数１０２】
2021509492.tif 000104
【０２８０】
で合計値を与えることができる。いくつかの実施形態では、
【０２８１】
【数１０３】
2021509492.tif 000105
【０２８２】
の中の複製された記録は削除されてよい。
【０２８３】
いくつかの実施形態では、二重リザーバCFRアルゴリズムが使われる場合、この反復における、サンプリングされた情報集合に対する、反事実リグレットおよび平均戦略の分子(二重増分CFRアルゴリズムにおいて
【０２８４】
【数１０４】
2021509492.tif 000106
【０２８５】
に保存されたものなど)は、それぞれ、リザーバMRおよびMSに保存されてよい。リザーバMRおよびMSの一方または両方が満杯である場合、リザーバサンプリングが使われ得る。
【０２８６】
擬似コード500の行13〜15に示すように、この反復における、サンプリングされた情報集合に対する、これらの反事実リグレットおよび平均戦略の分子は、図6に示すNeuralAgentアルゴリズムによって、2つのニューラルネットワーク、すなわちRSNおよびASNを最適化し、RSNおよびASN(たとえば、
【０２８７】
【数１０５】
2021509492.tif 000107
【０２８８】
)のパラメータ(たとえば、
【０２８９】
【数１０６】
2021509492.tif 000108
【０２９０】
)を戻すのに使うことができる。
【０２９１】
図6は、本明細書の実施形態による、二重ニューラルCFRアルゴリズムに関連してニューラルネットワークを最適化するためのアルゴリズムの例の擬似コード600である。このアルゴリズムの例は、NeuralAgentアルゴリズムと呼ばれる。記載する二重ニューラルCFRアルゴリズムは、二重ニューラルCFRアルゴリズムにおいて使われる一方または両方のニューラルネットワークを最適化するための、他のアルゴリズムを使うことができる。
【０２９２】
βepochをトレーニングエポックと、βlrを学習レートと、βlossを早期停止または終了のための基準と、βreを、最後に最小損失を得てからの反復の回数に対する上限と、θt-1を、最適化するためのパラメータと、f(・|θt-1)をニューラルネットワークと、Mを、情報集合および対応する目標を構成するトレーニングサンプルと定義する。表記を簡素化するために、ニューラルネットワークのパラメータの集合を示すのにβ*を使う。たとえば、
【０２９３】
【数１０７】
2021509492.tif 000109
【０２９４】
およびβS*は、それぞれ、RSNおよびASNにおけるパラメータの集合を指す。注意深く設計されたNeuralAgentアルゴリズムは、ニューラルネットワークRSNおよびASNを最適化する際の、可搾取量の比較的高い収束レートを取得し得ることを、実験が示している。擬似コード600は、説明コメント付きのNeuralAgentアルゴリズムの詳細を示す。
【０２９５】
いくつかの実施形態では、既存のオプティマイザは、潜在的鞍点または局所的最小により、比較的十分低い損失を戻すことができない。比較的高い正確さおよび低い最適化損失を取得するために、スケジューラは特に、損失が低下するのをやめたときに学習レートを低減するように設計される。具体的には、スケジューラは、メトリック量、たとえば、平均二乗誤差を読み取り、いくつかのエポックについて改善が見られない場合、学習レートは、ある倍率だけ低減される。さらに、損失がβre個のエポックにおいて低下するのをやめると、学習レートは、オプティマイザとスケジューラの両方においてリセットされてよい。勾配クリッピング機構が、パラメータ勾配の規模を制限し、オプティマイザを、絶壁(steep cliff)の付近においてより良好に振る舞わせるのに使われ得る。各エポックの後、最良パラメータは更新されることになる。最も低い損失が、指定された基準βloss未満になると、早期停止機構が使われる。
【０２９６】
実験において、ニューラルネットワークのハイパーパラメータは次のように設定されてよい。たとえば、RSNに対して、ニューラルバッチサイズは256であり、学習レートβlr=0.001である。エポックの数および損失の収束レートに基づいて学習レートを低減することになるスケジューラは、ニューラルエージェントが高い正確さを取得するのを助ける。10個のエポックの後に損失が改善するのをやめたとき、学習レートは、0.5だけ低減され得る。このスケジューラにおけるすべてのパラメータの学習レートに対する下限は、10-6である。アルゴリズムが潜在的な局所的最小または鞍点に収束するのを避けるために、学習レートは、たとえば、0.001にリセットされ、オプティマイザがより優れた性能を学習するのを助けることができる。
【０２９７】
【数１０８】
2021509492.tif 000110
【０２９８】
は、T個のエポックの後の最も低い損失を達成するための最良パラメータである。エポックtに対する平均損失が、指定された基準βloss=10-4未満である場合、オプティマイザは、早期停止を行ってよい。一例として、βepoch=2000と設定し、オプティマイザを2000個の最大エポックで更新する。
【０２９９】
ASNに対して、早期停止基準の損失は10-5と設定されてよい。15個のエポックの後に損失が改善するのをやめたとき、学習レートは、0.7だけ低減され得る。ASNにおける他のハイパーパラメータは、RSNのものと同様であり得る。
【０３００】
図7は、本明細書の実施形態による、ミニバッチMCCFRアルゴリズムの例の擬似コード700である。ミニバッチMCCFRアルゴリズム(Mini-Batch-MCCFR-NNとして示される)は、ゲームのサンプリングされた情報集合に対する、反事実リグレットおよび平均戦略の分子を取得するためのサンプリングアルゴリズムを含む。ある反復において1つのブロックをサンプリングするだけであり、起点CFVの不偏推定量を提供する、従来の結果サンプリングおよび外部サンプリングとは異なり、ミニバッチサンプリング技法は、1回の反復においてb個のブロックをランダムにサンプリングすることができる。擬似コード700に示すミニバッチMCCFRアルゴリズムの例は、上述したロバストサンプリングに基づく。いくつかの実施形態では、ミニバッチMCCFRアルゴリズムは、深さ依存サンプリング方式など、他のサンプリング方式と関連して使うことができる。ミニバッチMCCFRアルゴリズムは、ゲームのサンプリングされた情報集合に対する、反事実リグレットおよび平均戦略の分子を取得するためのアルゴリズムの例であることに留意されたい。二重ニューラルCFRアルゴリズムは、ゲームのサンプリングされた情報集合に対する、反事実リグレットおよび平均戦略の分子を取得するための他のアルゴリズムを使うことができる。
【０３０１】
Qjは、第jのときのロバストサンプリング方式に従ってサンプリングされた終端のブロックを示すものとすると、情報集合Iiに対するb個のミニバッチをもつミニバッチCFVは、以下のように定義することができる。
【０３０２】
【数１０９】
2021509492.tif 000111
【０３０３】
さらに、
【０３０４】
【数１１０】
2021509492.tif 000112
【０３０５】
は、Iiの反事実値の不偏推定量であること、すなわち
【０３０６】
【数１１１】
2021509492.tif 000113
【０３０７】
が示され得る。
【０３０８】
同様に、行動aの累積ミニバッチリグレットは、
【０３０９】
【数１１２】
2021509492.tif 000114
【０３１０】
であり、上式で、
【０３１１】
【数１１３】
2021509492.tif 000115
【０３１２】
である。いくつかの実施形態では、ミニバッチMCCFRは、b個のブロックを並行してサンプリングし、MCCFRがより速く収束するのを助けることができる。
【０３１３】
ミニバッチMCCFRは、累積ミニバッチリグレットR-T,+((a|Ii)|b)を更新するのに、リグレットマッチングアルゴリズムを使うことに留意されたい。いくつかの実施形態では、ミニバッチMCCFRの変形体として、ミニバッチMCCFR+アルゴリズムが、累積ミニバッチリグレットR-T,+((a|Ii)|b)を反復Tまで、
【０３１４】
【数１１４】
2021509492.tif 000116
【０３１５】
によって更新するのに使われてよく、上式で、(x)+=max(x,0)である。いくつかの実施形態では、ミニバッチMCCFR+は、適切なミニバッチサイズを指定しているとき、ミニバッチMCCFRよりも速く収束することがわかる。
【０３１６】
擬似コード700に示す関数Mini-Batch-MCCFR-NNは、ミニバッチサンプリング方法を提示し、ここで、b個のブロックが並行してサンプリングされることになる。このミニバッチ方法は、MCCFRが、CFVのより正確な推定を達成するのを助けることができる。並列サンプリングは、この方法を、実際に効率的にする。
【０３１７】
擬似コード700の行1〜6に示すように、Mini-Batch-MCCFR-NNは、反復の総数、すなわちt個の入力をもつ反復アルゴリズムである。各反復内で、MCCFR-NN関数が、プレーヤ0およびプレーヤ1について呼び出され(行4および5に示すように)、この反復における、サンプリングされた情報集合に対する、反事実リグレットおよび平均戦略の分子が、戻され、
【０３１８】
【数１１５】
2021509492.tif 000117
【０３１９】
にそれぞれ保存される。
【０３２０】
関数MCCFR-NNは、擬似コード700の行8〜33に示すように定義され得る。関数MCCFR-NNは、表によるMCCFRのようにゲームツリーを巡回し、これは、ルート履歴h=φからスタートする。Iiを、hの情報集合と定義する。プレーヤiは、ロバストサンプリングに従ってk個の行動をサンプリングすることになると仮定する。次いで、関数は以下のように定義され得る。(1)履歴が終端である場合(たとえば、h∈Z)、関数は、重み付き効用を戻す。(2)履歴がチャンスプレーヤである場合(たとえば、P(Ii)=-1,)、1つの行動a∈A(Ii)が、戦略σ-i(Ii)に従ってサンプリングされ得る。次いで、この行動は、履歴に追加されることになり、すなわち、h←haとなる。(3)P(Ii)=iである場合、現在の戦略は、RSNによって予測される累積リグレットによって更新され得る。次いで、指定されたサンプリング戦略プロファイル
【０３２１】
【数１１６】
2021509492.tif 000118
【０３２２】
(たとえば、深さ依存サンプリングを用いるか、または用いないロバストサンプリング)に従って、k個の行動をサンプリングする。再帰的更新の後、Iiにおける各行動の反事実値およびリグレットが取得され得る。訪問されたノードについて、それらの反事実リグレットおよび対応する平均戦略の分子は、
【０３２３】
【数１１７】
2021509492.tif 000119
【０３２４】
にそれぞれ記憶されてよい。(4)P(Ii)が対戦相手である場合、ただ1つの行動が、戦略σ-i(Ii)に従ってサンプリングされることになる。
【０３２５】
図8は、本明細書の実施形態による、MCCFRを実施するためのサンプリングプロセス800の例のフローチャートである。サンプリングプロセス800は、2人以上の当事者の間の戦略的対話における戦略探索のための反事実的リグレット最小化(CFR)を行うための、上述した深さ依存サンプリング方式の例であり得る。いくつかの実施形態では、2人以上のプレーヤの間の戦略的対話は、2人以上のプレーヤが関与する不完全情報ゲーム(IIG)によってモデル化され得る。IIGは、2人以上の当事者が関与する、リソース割り当て、製品/サービス推奨、サイバー攻撃予測および/または防止、トラフィックルーティング、不正管理などのような、1つまたは複数の実世界シナリオを表すことができ、各当事者は、他の当事者の決定についての不十分または不完全な情報を有し得る。一例として、IIGは、少なくとも第1のプレーヤおよび第2のプレーヤが関与する協調型製品サービス推奨サービスを表すことができる。第1のプレーヤは、たとえば、顧客(またはユーザ)情報、製品およびサービス情報、顧客の購入履歴などを有するオンライン小売業者であってよい。第2のプレーヤは、たとえば、顧客のソーシャルネットワーキングデータを有するソーシャルネットワークプラットフォーム、顧客の財務情報を有する銀行または他の金融機関、車販売店、または顧客への製品およびサービスの予測および推奨における顧客の嗜好、必要性、財務状況、ロケーションなどについての顧客の情報を有し得る、どの他の当事者であってもよい。第1のプレーヤおよび第2のプレーヤは各々、他者とは共有したくない固有データを有し得る。第2のプレーヤは、異なるときに第1のプレーヤに部分情報を提供するだけでよい。したがって、第1のプレーヤは、第2のプレーヤの情報への限定アクセスを有するだけであり得る。便宜上、プロセス800は、1つまたは複数のロケーションにあるとともに、本明細書に従って適切にプログラムされた1つまたは複数のコンピュータからなるシステムなどのデータ処理装置によって実施されるものとして記載される。たとえば、適切にプログラムされた、図10のコンピュータシステム1000が、プロセス800を実施し得る。
【０３２６】
810において、データ処理装置が、第1のプレーヤの第1の状態における、第1のプレーヤのN1個の可能な行動を識別する。いくつかの実施形態では、IIGは、ゲームツリー(たとえば、ゲームツリー102、104、202、204または206)によって表され得る。第1のプレーヤの第1の状態は、ゲームツリーの第1のノード(たとえば、ゲームツリー102における、プレーヤ0のノードh1)によって表すことができ、N1個の可能な行動は、ゲームツリーの第1のノードの辺または分岐(たとえば、ゲームツリー102における、プレーヤ0のノードh1のPおよびB辺)であり得る。協調型製品サービス推奨サービスの例では、第1のプレーヤの第1の状態は、第2のプレーヤによって提供される情報の履歴を含み、第1のプレーヤのN1個の可能な行動は、製品サービス推奨を顧客に提供するための、第2のプレーヤによって提供された情報の履歴に応答する、N1個の可能な行動を含む。第1のプレーヤの第1の状態および可能な行動は、IIGによってモデル化される他の実世界シナリオにおける他の特徴を含み得る。
【０３２７】
820において、データ処理装置は、第1のプレーヤの第1の状態におけるN1個の可能な行動の中から、第1のサンプリング確率で可能な行動をサンプリングする。いくつかの実施形態では、データ処理装置は、第1のプレーヤの第1の状態におけるN1個の可能な行動の中からk1個の可能な行動をサンプリングすることができ、k1個の可能な行動の各々は、同じ第1のサンプリング確率でサンプリングされる。
【０３２８】
830において、データ処理装置は、第1のプレーヤの第2の状態における、第1のプレーヤのN2個の可能な行動を識別し、第1のプレーヤの第1の状態は、第1のプレーヤの第2の状態よりもIIGの開始状態に近い。ゲームツリー102の例では、第1のプレーヤの第2の状態は、たとえば、h7ノードであってよく、このノードは、第1のプレーヤの第1の状態(たとえば、ゲームツリー102におけるプレーヤ0のノードh1)よりも、ゲームツリー102の開始状態(たとえば、h0ノード)から離れている。
【０３２９】
840において、データ処理装置は、第1のプレーヤの第2の状態におけるN2個の可能な行動の中から、第2のサンプリング確率で可能な行動をサンプリングし、第1のサンプリング確率は、第2のサンプリング確率未満である。いくつかの実施形態では、データ処理装置は、第1のプレーヤの第2の状態におけるN2個の可能な行動の中からk2個の可能な行動をサンプリングし、k2個の可能な行動の各々は、同じ第2のサンプリング確率でサンプリングされる。
【０３３０】
850において、データ処理装置は、第1のプレーヤの第1の状態におけるN1個の可能な行動のうちの可能な行動および第1のプレーヤの第2の状態におけるN2個の可能な行動のうちの可能な行動に基づいて、CFRを実施する。いくつかの実施形態では、CFRは、図3および/または図7に関して記載した例示的技法に従って実施され得る。
【０３３１】
いくつかの実施形態では、IIGを解いたことから得られた、第1のプレーヤの戦略が出力される。戦略は、IIGによってモデル化された実世界シナリオにおける、第1のプレーヤの一連の行動を含み得る。たとえば、協調型製品サービス推奨シナリオにおいて、IIGを解いたことから得られた、第1のプレーヤの戦略は、たとえば、第2のプレーヤによって提供された情報に応答する一連の行動、第1のプレーヤの情報および第2のプレーヤによって提供された情報に基づく、顧客への対応する製品サービス推奨を含み得る。IIGを解いたことから得られる、第1のプレーヤの出力戦略は、IIGによってモデル化される、他の実世界シナリオにおける他の情報を含み得る。
【０３３２】
いくつかの実施形態では、第1のプレーヤの第1の状態におけるN1個の可能な行動のうちの可能な行動および第1のプレーヤの第2の状態におけるN2個の可能な行動のうちの可能な行動に基づいてCFRを実施することは、第1のプレーヤの第1の状態におけるN1個の可能な行動のうちの可能な行動のリグレット値を(たとえば、式(1a)および/または式(2)に従って)算出することと、第1のプレーヤの第2の状態におけるN2個の可能な行動のうちの可能な行動のリグレット値を(たとえば、式(1a)および/または式(2)に従って)算出することと、N1個の可能な行動のうちの可能な行動のリグレット値に基づいて、第1の状態における第1のプレーヤの第1の戦略を(たとえば、式(3)に従って)更新することと、N2個の可能な行動のうちの可能な行動のリグレット値に基づいて、第2の状態における第1のプレーヤの第2の戦略を(たとえば、式(3)に従って)更新することとを含む。
【０３３３】
いくつかの実施形態では、データ処理装置は、第1のプレーヤの第1の状態におけるN1個の可能な行動のうちのk1個の可能な行動および第1のプレーヤの第2の状態におけるN2個の可能な行動のうちのk2個の可能な行動に基づいて、CFRを実施する。
【０３３４】
いくつかの実施形態では、ロバストサンプリングが、深さ依存サンプリングに関連して実施され得る。たとえば、第1のサンプリング確率はk1/N1であり、第2のサンプリング確率はk2/N2である。したがって、可能な行動は、一様分布に従ってサンプリングされる。
【０３３５】
いくつかの実施形態では、プレーヤの各状態について複数の可能な行動が訪問されるように、2<=k1<=N1および2<=k2<=N2である。
【０３３６】
いくつかの実施形態では、k1=k2であり、したがって、第1のプレーヤの第1の状態および第2の状態において、等しい数のサンプルが選択され、または訪問される。
【０３３７】
同様に、深さ依存サンプリングは、第2のプレーヤに関連して実施され得る。たとえば、データ処理装置は、第2のプレーヤの第1の状態における、第2のプレーヤのM1個の可能な行動を識別する。データ処理装置は、第2のプレーヤの第1の状態におけるM1個の可能な行動の中から、第3のサンプリング確率で可能な行動をサンプリングする。データ処理装置は、第2のプレーヤの第2の状態における、第2のプレーヤのM2個の可能な行動を識別し、第2のプレーヤの第1の状態は、第2のプレーヤの第2の状態よりもIIGの開始状態に近い。データ処理装置は、第1のプレーヤの第2の状態における、M2個の可能な行動の中から、第4のサンプリング確率で可能な行動をサンプリングし、第3のサンプリング確率は、第4のサンプリング確率未満である。
【０３３８】
いくつかの実施形態では、深さ依存サンプリングは、第1のプレーヤと第2のプレーヤの両方に関連して実施され得る。いくつかの実施形態では、データ処理装置は、第2のプレーヤの第1の状態における、第2のプレーヤのM1個の可能な行動を識別し、第1のプレーヤの第1の状態(たとえば、ゲームツリー102におけるプレーヤ0の状態h1)は、第2のプレーヤの第1の状態(たとえば、ゲームツリー102におけるプレーヤ1の状態h4)よりも、IIGの開始状態(たとえば、h0状態)に近い。データ処理装置は、第2のプレーヤの第1の状態におけるM1個の可能な行動の中から、第3のサンプリング確率で可能な行動をサンプリングし、第3のサンプリング確率は、第1のサンプリング確率よりも大きい。
【０３３９】
図9は、本明細書の実施形態による、MCCFRを実施するための二重ニューラルCFRアルゴリズム900の例のフローチャートである。サンプリングプロセス900は、2人以上のプレーヤの間の戦略的対話における戦略探索のための反事実的リグレット最小化(CFR)を実施するための、図4〜図7に関して上述した二重リザーバCFRアルゴリズムの例であり得る。いくつかの実施形態では、2人以上のプレーヤの間の戦略的対話は、2人以上のプレーヤが関与する不完全情報ゲーム(IIG)によってモデル化され得る。IIGは、2人以上の当事者が関与する、リソース割り当て、製品/サービス推奨、サイバー攻撃予測および/または防止、トラフィックルーティング、不正管理などのような、1つまたは複数の実世界シナリオを表すことができ、各当事者は、他の当事者の決定についての不十分または不完全な情報を有し得る。一例として、IIGは、少なくとも第1のプレーヤおよび第2のプレーヤが関与する協調型製品サービス推奨サービスを表すことができる。第1のプレーヤは、たとえば、顧客(またはユーザ)情報、製品およびサービス情報、顧客の購入履歴などを有するオンライン小売業者であってよい。第2のプレーヤは、たとえば、顧客のソーシャルネットワーキングデータを有するソーシャルネットワークプラットフォーム、顧客の財務情報を有する銀行または他の金融機関、車販売店、または顧客への製品およびサービスの予測および推奨における顧客の嗜好、必要性、財務状況、ロケーションなどについての顧客の情報を有し得る、どの他の当事者であってもよい。第1のプレーヤおよび第2のプレーヤは各々、他者とは共有したくない固有データを有し得る。第2のプレーヤは、異なるときに第1のプレーヤに部分情報を提供するだけでよい。したがって、第1のプレーヤは、第2のプレーヤの情報への限定アクセスを有するだけであり得る。便宜上、プロセス900は、1つまたは複数のロケーションにあるとともに、本明細書に従って適切にプログラムされた1つまたは複数のコンピュータからなるシステムなどのデータ処理装置によって実施されるものとして記載される。たとえば、適切にプログラムされた、図10のコンピュータシステム1000が、プロセス900を実施し得る。
【０３４０】
910において、データ処理装置が、第1のニューラルネットワークのパラメータおよび第2のニューラルネットワークのパラメータを初期化する。第1のニューラルネットワーク(たとえば、RegretSumNetwork(RSN)420)は、プレーヤの状態における可能な行動のリグレット値を予測するために使われ得る。協調型製品サービス推奨サービスの例では、プレーヤの状態は、第2のプレーヤによって提供された情報の履歴を含み、プレーヤの可能な行動は、製品サービス推奨を顧客に提供するための、第2のプレーヤによって提供された情報の履歴に応答する、可能な行動を含む。第2のニューラルネットワーク(たとえば、AveStrategyNetwork(ASN)430)は、プレーヤの状態における可能な行動の戦略値を予測するために使われ得る。いくつかの実施形態では、データ処理装置は、ウォームスタートに従って、たとえば、それぞれ、前の反復における、または既存のCFRアルゴリズムに基づいて取得された、第1のニューラルネットワークのパラメータまたは第2のニューラルネットワークのパラメータに基づいて、パラメータを初期化する。いくつかの実施形態では、データ処理装置は、第1のニューラルネットワークのパラメータおよび第2のニューラルネットワークのパラメータをランダムに初期化する。
【０３４１】
920において、データ処理装置は、いくつかのリグレットサンプルを第1のデータストア(たとえば、リザーバMR)に記憶し、いくつかのリグレットサンプルの各々は、プレーヤの状態、およびプレーヤの状態における可能な行動のリグレット値を含む。いくつかの実施形態では、プレーヤの状態における可能な行動のリグレット値は、プレーヤの状態における可能な行動の反事実値に基づいて算出された、プレーヤの状態における可能な行動の反事実リグレット値を含む。たとえば、各リグレットサンプルは、リグレットタプル
【０３４２】
【数１１８】
2021509492.tif 000120
【０３４３】
)を含み得る。いくつかの実施形態では、いくつかのリグレットサンプルは、プレーヤと少なくとも他のプレーヤとの間の戦略的対話における戦略探索における反事実的リグレット最小化(CFR)アルゴリズムの2回以上の反復において取得される。いくつかの実施形態では、CFRアルゴリズムは、ロバストサンプリングCFRアルゴリズムを含む。
【０３４４】
いくつかの実施形態では、IIGを解く際の、CFRアルゴリズムの2回以上の反復の各々において、データ処理装置は、サンプリング方式に従って、プレーヤの第2の状態におけるいくつかの可能な行動の中から可能な行動をサンプリングし、プレーヤの第2の状態における可能な行動の反事実値を(たとえば、式(1)に従って)算出し、プレーヤの第2の状態における可能な行動の反事実値に基づいて、プレーヤの第2の状態における可能な行動のリグレット値を(たとえば、式(1a)および/または式(2)に従って)算出し、リグレットマッチングアルゴリズムに従って、プレーヤの第2の状態における可能な行動のリグレット値に基づいて、プレーヤの第2の状態における可能な行動の更新された戦略を(たとえば、式(3)に従って)算出し、プレーヤの第2の状態における可能な行動の更新された戦略に基づいて、プレーヤの第2の状態における可能な行動の戦略値を(たとえば、式(4)および/または式(5)に従って)算出する。
【０３４５】
いくつかの実施形態では、データ処理装置は、(たとえば、MCCFRの他の反復を実施することによって)新たなリグレットサンプルを取得することができる。データ処理装置は、リザーバサンプリングアルゴリズムに従って、新たなリグレットサンプルを第1のデータストアの中に記憶することができる。たとえば、リザーバサンプリングアルゴリズムに従って、新たなリグレットサンプルを第1のデータストアの中に記憶することは、第1のデータストアが満杯であるかどうかを判断することと、第1のデータストアが満杯であると判断したことに応答して、第1のデータストア中のいくつかのリグレットサンプルのうちの1つを、新たなリグレットサンプルで置き換えることとを含む。
【０３４６】
930において、データ処理装置は、いくつかの戦略サンプルを第2のデータストア(たとえば、リザーバMS)に記憶し、いくつかの戦略サンプルの各々は、プレーヤの状態、およびプレーヤの状態における可能な行動の戦略値を含む。いくつかの実施形態では、プレーヤの状態における可能な行動の戦略値は、平均戦略の分子を含む。たとえば、いくつかの戦略サンプルの各々は、戦略タプル(Ii、st(a|Ii))を含み得る。
【０３４７】
940において、データ処理装置は、たとえば、式(7)に従って、第1のデータストア中のいくつかのリグレットサンプルに基づいて、プレーヤの状態における可能な行動のリグレット値を予測するための、第1のニューラルネットワークのパラメータを更新する。いくつかの実施形態では、第1のニューラルネットワークのパラメータは、図6に示すNeuralAgentアルゴリズム、またはニューラルネットワークを最適化するための、どの他のアルゴリズムに従って更新されてもよい。
【０３４８】
950において、データ処理装置は、たとえば、式(8)に従って、第2のデータストア中のいくつかの戦略サンプルに基づいて、プレーヤの状態における可能な行動の戦略値を予測するための、第2のニューラルネットワークのパラメータを更新する。いくつかの実施形態では、第2のニューラルネットワークのパラメータは、図6に示すNeuralAgentアルゴリズム、またはニューラルネットワークを最適化するための、どの他のアルゴリズムに従って更新されてもよい。
【０３４９】
960において、データ処理装置は、プレーヤの第1の状態、およびプレーヤの第1の状態における第1の可能な行動を識別する。
【０３５０】
970において、データ処理装置は、第1のニューラルネットワークのパラメータを使って、プレーヤの第1の状態における第1の可能な行動の第1のリグレット値を予測する。いくつかの実施形態では、プレーヤの第1の状態における第1の可能な行動の予測される第1のリグレット値は、CFRアルゴリズムの次の反復において使われ得る。
【０３５１】
980において、データ処理装置は、第2のニューラルネットワークのパラメータを使って、プレーヤの第1の状態における第1の可能な行動の第1の戦略値を予測する。いくつかの実施形態では、プレーヤの第1の状態における第1の可能な行動の予測される第1の戦略値は、CFRアルゴリズムの次の反復において使われ得る。いくつかの実施形態では、プレーヤの第1の状態における第1の可能な行動の予測される第1の戦略値は、近似ナッシュ均衡を算出するのに使われ、CFRアルゴリズムの出力として働き得る。いくつかの実施形態では、プレーヤの第1の状態における第1の可能な行動の予測される第1の戦略値は、IIGによってモデル化される実世界シナリオにおける、第1のプレーヤの一連の行動を含み得る。たとえば、協調型製品サービス推奨シナリオでは、プレーヤの第1の状態における第1の可能な行動の予測される第1の戦略値は、たとえば、第2のプレーヤによって提供された情報に応答する一連の行動、第1のプレーヤの情報および第2のプレーヤによって提供された情報に基づく、顧客への対応する製品サービス推奨を含み得る。プレーヤの第1の状態における第1の可能な行動の予測される第1の戦略値は、IIGによってモデル化される他の実世界シナリオにおける他の情報を含み得る。
【０３５２】
図10は、本明細書の実施形態による、記載するアルゴリズム、方法、機能、プロセス、フロー、および手順に関連付けられた計算機能性を提供するのに使われるコンピュータ実装システムの例を示すブロック図を示す。図10は、本開示の実施形態による、記載するアルゴリズム、方法、機能、プロセス、フロー、および手順に関連付けられた計算機能性を提供するのに使われるコンピュータ実装システム1000の例を示すブロック図である。図示する実施形態では、システム1000は、コンピュータ1002およびネットワーク1030を含む。
【０３５３】
示されるコンピュータ1002は、サーバ、デスクトップコンピュータ、ラップトップ/ノートブックコンピュータ、ワイヤレスデータポート、スマートフォン、個人情報端末(PDA)、タブレットコンピュータ、これらのデバイス内の1つもしくは複数のプロセッサ、他のコンピューティングデバイス、またはコンピューティングデバイスの物理もしくは仮想インスタンスを含むコンピューティングデバイスの組合せ、またはコンピューティングデバイスの物理もしくは仮想インスタンスの組合せなど、どのコンピューティングデバイスも包含することが意図されている。さらに、コンピュータ1002は、キーパッド、キーボード、タッチスクリーン、他の入力デバイスなどの入力デバイス、またはユーザ情報を受諾することができる入力デバイスの組合せと、グラフィカルタイプユーザインターフェース(UI)(もしくはGUI)または他のUI上で、デジタルデータ、ビジュアル、オーディオ、他のタイプの情報、または情報のタイプの組合せを含む、コンピュータ1002の動作に関連付けられた情報を伝える出力デバイスとを含み得る。
【０３５４】
コンピュータ1002は、クライアント、ネットワーク構成要素、サーバ、データベースとして、分散型コンピューティングシステムにおける役割を、または他の持続性、他の役割、もしくは本開示に記載する主題を実施するための役割の組合せを果たし得る。示されるコンピュータ1002は、ネットワーク1030と通信可能に結合される。いくつかの実施形態では、コンピュータ1002の1つまたは複数の構成要素は、クラウドコンピューティングベース、ローカル、グローバル、他の環境を含む環境、または環境の組合せにおいて動作するように構成され得る。
【０３５５】
上位レベルにおいて、コンピュータ1002は、記載する主題に関連付けられたデータおよび情報を受信し、送信し、処理し、記憶し、または管理するように動作可能な電子コンピューティングデバイスである。いくつかの実施形態によると、コンピュータ1002はまた、アプリケーションサーバ、eメールサーバ、ウェブサーバ、キャッシュサーバ、ストリーミングデータサーバ、他のサーバ、またはサーバの組合せを含むサーバを含むか、またはサーバと通信可能に結合され得る。
【０３５６】
コンピュータ1002は、(たとえば、他のコンピュータ1002上で実行するクライアントソフトウェアアプリケーションから)ネットワーク1030を介して要求を受信し、ソフトウェアアプリケーション、またはソフトウェアアプリケーションの組合せを使って、受信した要求を処理することによって、受信した要求に応答することができる。さらに、要求は、内部ユーザ(たとえば、コマンドコンソールから、もしくは他の内部アクセス方法によって)、外部もしくは第三者、または他のエンティティ、個人、システム、もしくはコンピュータから、コンピュータ1002へ送られてもよい。
【０３５７】
コンピュータ1002の構成要素の各々は、システムバス1003を使って通信し得る。いくつかの実施形態では、ハードウェア、ソフトウェア、またはハードウェアとソフトウェアの組合せを含む、コンピュータ1002の構成要素のいずれかまたはすべてが、アプリケーションプログラミングインターフェース(API)1012、サービスレイヤ1013、またはAPI1012とサービスレイヤ1013の組合せを使って、システムバス1003を介してインターフェースすることができる。API1012は、ルーチン、データ構造、オブジェクトクラス向けの仕様を含み得る。API1012は、コンピュータ言語非依存または依存のいずれかであり、完全インターフェース、単一の機能、またはAPIのセットさえも指し得る。サービスレイヤ1013は、コンピュータ1002、またはコンピュータ1002に通信可能に結合される他の構成要素(示されるかどうかにかかわらず)にソフトウェアサービスを提供する。コンピュータ1002の機能性は、サービスレイヤ1013を使って、すべてのサービス消費者にとってアクセス可能であり得る。サービスレイヤ1013によって提供されるものなどのソフトウェアサービスは、定義されたインターフェースを通して、再利用可能な、定義された機能性を提供する。たとえば、インターフェースは、JAVA(登録商標)、C++、他のコンピューティング言語、または拡張マークアップ言語(XML)フォーマット、他のフォーマット、もしくはフォーマットの組合せでデータを提供するコンピューティング言語の組合せで書かれたソフトウェアであってよい。コンピュータ1002の統合構成要素として示されているが、代替実施形態は、API1012またはサービスレイヤ1013を、コンピュータ1002の他の構成要素またはコンピュータ1002に通信可能に結合される他の構成要素(示されるかどうかにかかわらず)と関係したスタンドアロン構成要素として示し得る。その上、API1012またはサービスレイヤ1013のいずれかまたはすべての部分は、本開示の範囲から逸脱することなく、他のソフトウェアモジュール、企業アプリケーション、またはハードウェアモジュールの子またはサブモジュールとして実装され得る。
【０３５８】
コンピュータ1002は、インターフェース1004を含む。単一のインターフェース1004として示されているが、コンピュータ1002の特定の必要性、要望、または特定の実施形態に従って、2つ以上のインターフェース1004が使われてよい。インターフェース1004は、コンピュータ1002によって、分散型環境においてネットワーク1030に通信可能にリンクされている他のコンピューティングシステム(示されるかどうかにかかわらず)と通信するために使われる。概して、インターフェース1004は、ネットワーク1030と通信するように動作可能であり、ソフトウェア、ハードウェア、またはソフトウェアとハードウェアの組合せで符号化された論理を含む。より具体的には、インターフェース1004は、ネットワーク1030またはインターフェース1004のハードウェアが、示されるコンピュータ1002内および外で物理信号を通信するように動作可能であるように、通信に関連付けられた1つまたは複数の通信プロトコルをサポートするソフトウェアを含み得る。
【０３５９】
コンピュータ1002は、プロセッサ1005を含む。単一のプロセッサ1005として示されているが、コンピュータ1002の特定の必要性、要望、または特定の実施形態に従って、2つ以上のプロセッサ1005が使われてよい。概して、プロセッサ1005は、コンピュータ1002の動作と、本開示に記載するあらゆるアルゴリズム、方法、機能、プロセス、フロー、および手順とを実施するために、命令を実行し、データを操作する。
【０３６０】
コンピュータ1002は、コンピュータ1002のためのデータを保持することができるデータベース1006、ネットワーク1030に通信可能にリンクされた他の構成要素(示されるかどうかにかかわらず)、またはコンピュータ1002と他の構成要素の組合せも含む。たとえば、データベース1006は、本開示に一致するデータを記憶する、インメモリの、従来の、または他のタイプのデータベースであってよい。いくつかの実施形態では、データベース1006は、コンピュータ1002の特定の必要性、要望、または特定の実施形態および記載する機能性に従って、2つ以上の異なるデータベースタイプ(たとえば、ハイブリッドインメモリおよび従来のデータベース)の組合せであってよい。単一のデータベース1006として示されているが、同様または異なるタイプの2つ以上のデータベースが、コンピュータ1002の特定の必要性、要望、または特定の実施形態および記載する機能性に従って使われてよい。データベース1006はコンピュータ1002の一体型構成要素として示されているが、代替実施形態では、データベース1006は、コンピュータ1002にとって外部であってよい。一例として、データベース1006は、リグレットサンプル1026を記憶する、上に記載したリザーバMR1016および戦略サンプル1028を記憶するリザーバMS1018を含み得る。
【０３６１】
コンピュータ1002は、コンピュータ1002のためのデータを保持することができるメモリ1007、ネットワーク1030に通信可能にリンクされた他の構成要素もしくは複数の構成要素(示されるかどうかにかかわらず)、またはコンピュータ1002と他の構成要素の組合せも含む。メモリ1007は、本開示に一致するどのデータも記憶することができる。いくつかの実施形態では、メモリ1007は、コンピュータ1002の特定の必要性、要望、または特定の実施形態および記載する機能性に従って、2つ以上の異なるタイプのメモリの組合せ(たとえば、半導体と磁気ストレージの組合せ)であってよい。単一のメモリ1007として示されているが、2つ以上のメモリ1007または同様もしくは異なるタイプが、コンピュータ1002の特定の必要性、要望、または特定の実施形態および記載する機能性に従って使われてよい。メモリ1007はコンピュータ1002の一体型構成要素として示されているが、代替実施形態では、メモリ1007は、コンピュータ1002にとって外部であってよい。
【０３６２】
アプリケーション1008は、特に本開示に記載する機能性に関して、コンピュータ1002の特定の必要性、要望、または特定の実施形態に従って機能性を提供する、アルゴリズムによるソフトウェアエンジンである。たとえば、アプリケーション1008は、1つまたは複数の構成要素、モジュール、またはアプリケーションとして働き得る。さらに、単一のアプリケーション1008として示されているが、アプリケーション1008は、コンピュータ1002上で複数のアプリケーション1008として実装されてよい。さらに、コンピュータ1002と一体として示されているが、代替実施形態では、アプリケーション1008は、コンピュータ1002にとって外部であってよい。
【０３６３】
コンピュータ1002は、電源1014も含み得る。電源1014は、ユーザまたは非ユーザ交換可能のいずれかであるように構成され得る充電可能または非充電可能バッテリーを含み得る。いくつかの実施形態では、電源1014は、電力変換または管理回路(充電、スタンバイ、もしくは他の電源管理機能を含む)を含み得る。いくつかの実施形態では、電源1014は、コンピュータ1002を壁面ソケットにプラグ接続させる電力プラグまたは、たとえば、コンピュータ1002に電力供給し、もしくは充電可能バッテリーを充電するための他の電力源を含み得る。
【０３６４】
コンピュータ1002を含む、コンピュータシステムに関連付けられるか、または外部の、任意の数のコンピュータ1002があってよく、各コンピュータ1002はネットワーク1030を介して通信する。さらに、「クライアント」、「ユーザ」という用語、または他の適切な用語が、必要に応じて、本開示の範囲から逸脱することなく、交換可能に使われてよい。その上、本開示は、多くのユーザが1つのコンピュータ1002を使い得ること、または1人のユーザが複数のコンピュータ1002を使い得ることを企図している。
【０３６５】
図11は、本明細書の実施形態による装置1100のモジュールの例の図である。装置1100は、2人以上のプレーヤの間の戦略的対話における戦略探索のための反事実的リグレット最小化(CFR)を実施するためのデータ処理装置の例示的実施形態であり得る。いくつかの実施形態では、2人以上のプレーヤの間の戦略的対話は、2人以上のプレーヤが関与する不完全情報ゲーム(IIG)によってモデル化され得る。一例として、IIGは、少なくとも第1のプレーヤおよび第2のプレーヤが関与する協調型製品サービス推奨サービスを表し、第1のプレーヤは、第2のプレーヤの情報への制限付きアクセスを有する。装置1100は、上述した実施形態に対応してよく、装置1100は、第1のプレーヤの第1の状態における、第1のプレーヤのN1個の可能な行動を識別するための第1の識別モジュール1101と、第1のプレーヤの第1の状態におけるN1個の可能な行動の中から、第1のサンプリング確率で可能な行動をサンプリングするための第1のサンプリングモジュール1102と、第1のプレーヤの第2の状態における、第1のプレーヤのN2個の可能な行動を識別するための第2の識別モジュール1103であって、第1のプレーヤの第1の状態は、第1のプレーヤの第2の状態よりもIIGの開始状態に近い、第2の識別モジュール1103と、第1のプレーヤの第2の状態におけるN2個の可能な行動の中から、第2のサンプリング確率で可能な行動をサンプリングするための第2のサンプリングモジュール1104であって、第1のサンプリング確率は、第2のサンプリング確率未満である、第2のサンプリングモジュール1104と、第1のプレーヤの第1の状態におけるN1個の可能な行動のうちの可能な行動および第1のプレーヤの第2の状態におけるN2個の可能な行動のうちの可能な行動に基づいて、CFRを実施するための処理モジュール1105とを含む。いくつかの実施形態では、第1のプレーヤの第1の状態は、第2のプレーヤによって提供された情報の履歴を含み、第1のプレーヤのN1個の可能な行動は、製品サービス推奨を顧客に提供するための、第2のプレーヤによって提供された情報の履歴に応答する、N1個の可能な行動を含む。
【０３６６】
任意選択の実施形態において、処理モジュールは、第1のプレーヤの第1の状態におけるN1個の可能な行動のうちの可能な行動のリグレット値を算出するための第1の算出モジュールと、第1のプレーヤの第2の状態におけるN2個の可能な行動のうちの可能な行動のリグレット値を算出するための第2の算出モジュールと、N1個の可能な行動のうちの可能な行動のリグレット値に基づいて、第1の状態における第1のプレーヤの第1の戦略を更新するための第1の更新モジュールと、N2個の可能な行動のうちの可能な行動のリグレット値に基づいて、第2の状態における第1のプレーヤの第2の戦略を更新するための第2の更新モジュールとを含む。
【０３６７】
任意選択の実施形態において、第1のサンプリングモジュールは、第1のプレーヤの第1の状態におけるN1個の可能な行動の中からk1個の可能な行動をサンプリングし、k1個の可能な行動の各々は、同じ第1のサンプリング確率でサンプリングされ、第2のサンプリングモジュールは、第1のプレーヤの第2の状態におけるN2個の可能な行動の中からk2個の可能な行動をサンプリングし、k2個の可能な行動の各々は、同じ第2のサンプリング確率でサンプリングされる。
【０３６８】
任意選択の実施形態において、処理モジュールは、第1のプレーヤの第1の状態におけるN1個の可能な行動のうちのk1個の可能な行動および第1のプレーヤの第2の状態におけるN2個の可能な行動のうちのk2個の可能な行動に基づいて、CFRを実施する。
【０３６９】
任意選択の実施形態において、第1のサンプリング確率はk1/N1であり、第2のサンプリング確率はk2/N2である。
【０３７０】
任意選択の実施形態において、2<=k1<=N1および2<=k2<=N2である。
【０３７１】
任意選択の実施形態において、k1=k2である。
【０３７２】
任意選択の実施形態において、装置1100は、第2のプレーヤの第1の状態における、第2のプレーヤのM1個の可能な行動を識別するための第3の識別モジュールと、第2のプレーヤの第1の状態におけるM1個の可能な行動の中から、第3のサンプリング確率で可能な行動をサンプリングするための第3のサンプリングモジュールと、第2のプレーヤの第2の状態における、第2のプレーヤのM2個の可能な行動を識別するための第4の識別モジュールであって、第2のプレーヤの第1の状態は、第2のプレーヤの第2の状態よりもIIGの開始状態に近い、第4の識別モジュールと、第1のプレーヤの第2の状態における、M2個の可能な行動の中から、第4のサンプリング確率で可能な行動をサンプリングするための第4のサンプリングモジュールであって、第3のサンプリング確率は、第4のサンプリング確率未満である、第4のサンプリングモジュールとをさらに含む。
【０３７３】
任意選択の実施形態において、装置1100は、第2のプレーヤの第1の状態における、第2のプレーヤのM1個の可能な行動を識別するための第5の識別モジュールであって、第1のプレーヤの第1の状態は、第2のプレーヤの第1の状態よりもIIGの開始状態に近い、第5の識別モジュールと、第2のプレーヤの第1の状態におけるM1個の可能な行動の中から、第3のサンプリング確率で可能な行動をサンプリングするための第5のサンプリングモジュールであって、第3のサンプリング確率は、第1のサンプリング確率よりも大きい、第5のサンプリングモジュールとをさらに含む。
【０３７４】
前の実施形態に示されたシステム、装置、モジュール、またはユニットは、コンピュータチップもしくはエンティティを使うことによって実装され得るか、または特定の機能を有する製品を使うことによって実装され得る。典型的な実施形態デバイスがコンピュータであり、コンピュータは、パーソナルコンピュータ、ラップトップコンピュータ、セルラーフォン、カメラフォン、スマートフォン、携帯情報端末、メディアプレーヤ、ナビゲーションデバイス、eメール受信および送付デバイス、ゲームコンソール、タブレットコンピュータ、装着可能デバイス、またはこれらのデバイスの任意の組合せであってもよい。
【０３７５】
装置の中の各モジュールの機能および役割の実施形態プロセスについて、前の方法における対応するステップからなる実施形態プロセスへの参照が行われる場合がある。詳細については、簡単のために、ここでは省く。
【０３７６】
装置実施形態は基本的に、方法実施形態に対応するので、関連部分について、方法実施形態における関連記述に対して参照が行われる場合がある。前に記載した装置実施形態は、例にすぎない。別個の部分として記述されるモジュールは、物理的に別個であってもなくてもよく、モジュールとして表示される部分は、物理モジュールであってもなくてもよく、ある位置に位置決めされ得るか、またはいくつかのネットワークモジュール上で分散され得る。モジュールの一部または全部が、本明細書の解決法の目的を達成するために、実際の需要に基づいて選択されてよい。当業者は、本出願の実施形態を理解し、創造的努力なしで実装することができよう。
【０３７７】
再度図11を参照すると、これは、2人以上のプレーヤの間の戦略的対話における戦略探索のための反事実的リグレット最小化(CFR)を実施するためのデータ処理装置の内部機能モジュールおよび構造を示していると解釈することができる。いくつかの実施形態では、2人以上のプレーヤの間の戦略的対話は、2人以上のプレーヤが関与する不完全情報ゲーム(IIG)によってモデル化され得る。本質的な実行本体は電子デバイスであってよく、電子デバイスは、1つまたは複数のプロセッサと、1つまたは複数のプロセッサの実行可能命令を記憶するように構成されたメモリとを含む。
【０３７８】
1つまたは複数のプロセッサは、第1のプレーヤの第1の状態における、第1のプレーヤのN1個の可能な行動を識別することと、第1のプレーヤの第1の状態におけるN1個の可能な行動の中から、第1のサンプリング確率で可能な行動をサンプリングすることと、第1のプレーヤの第2の状態における、第1のプレーヤのN2個の可能な行動を識別することであって、第1のプレーヤの第1の状態は、第1のプレーヤの第2の状態よりもIIGの開始状態に近い、ことと、第1のプレーヤの第2の状態におけるN2個の可能な行動の中から、第2のサンプリング確率で可能な行動をサンプリングすることであって、第1のサンプリング確率は、第2のサンプリング確率未満である、ことと、第1のプレーヤの第1の状態におけるN1個の可能な行動のうちの可能な行動および第1のプレーヤの第2の状態におけるN2個の可能な行動のうちの可能な行動に基づいて、CFRを実施することとを行うように構成される。
【０３７９】
任意選択で、1つまたは複数のプロセッサは、第1のプレーヤの第1の状態におけるN1個の可能な行動のうちの可能な行動のリグレット値を算出し、第1のプレーヤの第2の状態におけるN2個の可能な行動のうちの可能な行動のリグレット値を算出し、N1個の可能な行動のうちの可能な行動のリグレット値に基づいて、第1の状態における第1のプレーヤの第1の戦略を更新し、N2個の可能な行動のうちの可能な行動のリグレット値に基づいて、第2の状態における第1のプレーヤの第2の戦略を更新するように構成される。
【０３８０】
任意選択で、1つまたは複数のプロセッサは、第1のプレーヤの第1の状態におけるN1個の可能な行動の中からk1個の可能な行動をサンプリングすることであって、k1個の可能な行動の各々は、同じ第1のサンプリング確率でサンプリングされる、ことと、第1のプレーヤの第2の状態におけるN2個の可能な行動の中からk2個の可能な行動をサンプリングすることであって、k2個の可能な行動の各々は、同じ第2のサンプリング確率でサンプリングされる、こととを行うように構成される。
【０３８１】
任意選択で、1つまたは複数のプロセッサは、第1のプレーヤの第1の状態におけるN1個の可能な行動のうちのk1個の可能な行動および第1のプレーヤの第2の状態におけるN2個の可能な行動のうちのk2個の可能な行動に基づいて、CFRを実施するように構成される。
【０３８２】
任意選択で、第1のサンプリング確率はk1/N1であり、第2のサンプリング確率はk2/N2である。
【０３８３】
任意選択で、2<=k1<=N1および2<=k2<=N2である。
【０３８４】
任意選択で、k1=k2である。
【０３８５】
任意選択で、1つまたは複数のプロセッサは、第2のプレーヤの第1の状態における、第2のプレーヤのM1個の可能な行動を識別することと、第2のプレーヤの第1の状態におけるM1個の可能な行動の中から、第3のサンプリング確率で可能な行動をサンプリングすることと、第2のプレーヤの第2の状態における、第2のプレーヤのM2個の可能な行動を識別することであって、第2のプレーヤの第1の状態は、第2のプレーヤの第2の状態よりもIIGの開始状態に近い、ことと、第1のプレーヤの第2の状態における、M2個の可能な行動の中から、第4のサンプリング確率で可能な行動をサンプリングすることであって、第3のサンプリング確率は、第4のサンプリング確率未満である、こととを行うように構成される。
【０３８６】
任意選択で、1つまたは複数のプロセッサは、第2のプレーヤの第1の状態における、第2のプレーヤのM1個の可能な行動を識別することであって、第1のプレーヤの第1の状態は、第2のプレーヤの第1の状態よりもIIGの開始状態に近い、ことと、第2のプレーヤの第1の状態におけるM1個の可能な行動の中から、第3のサンプリング確率で可能な行動をサンプリングすることであって、第3のサンプリング確率は、第1のサンプリング確率よりも大きい、こととを行うように構成される。
【０３８７】
図12は、本明細書の実施形態による他の装置1200のモジュールの例の図である。装置1200は、2人以上のプレーヤの間の戦略的対話における戦略探索のための反事実的リグレット最小化(CFR)を実施するためのデータ処理装置の例示的実施形態であり得る。装置1200は上述した実施形態に対応してよく、装置1200は、いくつかのリグレットサンプルを第1のデータストアに記憶するための第1の記憶モジュール1201であって、いくつかのリグレットサンプルの各々は、プレーヤの状態、およびプレーヤの状態における可能な行動のリグレット値を含み、いくつかのリグレットサンプルは、プレーヤと少なくとも他のプレーヤとの間の戦略的対話における戦略探索における反事実的リグレット最小化(CFR)アルゴリズムの2回以上の反復において取得される、第1の記憶モジュール1201と、いくつかの戦略サンプルを第2のデータストアに記憶するための第2の記憶モジュール1202であって、いくつかの戦略サンプルの各々は、プレーヤの状態、およびプレーヤの状態における可能な行動の戦略値を含む、第2の記憶モジュール1202と、第1のデータストア中のいくつかのリグレットサンプルに基づいて、プレーヤの状態における可能な行動のリグレット値を予測するための、第1のニューラルネットワークのパラメータを更新するための第1の更新モジュール1203と、第2のデータストア中のいくつかの戦略サンプルに基づいて、プレーヤの状態における可能な行動の戦略値を予測するための、第2のニューラルネットワークのパラメータを更新するための第2の更新モジュール1204とを含む。いくつかの実施形態では、2人以上のプレーヤの間の戦略的対話は、2人以上のプレーヤが関与する不完全情報ゲーム(IIG)によってモデル化され得る。一例として、IIGは、少なくともプレーヤおよび第2のプレーヤが関与する協調型製品サービス推奨サービスを表し、プレーヤは、第2のプレーヤの情報への制限付きアクセスを有し、プレーヤの状態は、第2のプレーヤによって提供された情報の履歴を含み、プレーヤの可能な行動は、製品サービス推奨を顧客に提供するための、第2のプレーヤによって提供された情報の履歴に応答する、可能な行動を含む。
【０３８８】
上記および他の記載される実施形態は各々、任意選択で、以下の特徴のうちの1つまたは複数を含み得る。
【０３８９】
任意選択の実施形態において、装置1200は、プレーヤの第1の状態、およびプレーヤの第1の状態における第1の可能な行動を識別するための識別モジュールと、第1のニューラルネットワークのパラメータを使って、プレーヤの第1の状態における第1の可能な行動の第1のリグレット値を予測するための第1の予測モジュールと、第2のニューラルネットワークのパラメータを使って、プレーヤの第1の状態における第1の可能な行動の第1の戦略値を予測するための第2の予測モジュールとをさらに含む。
【０３９０】
任意選択の実施形態において、第1の記憶モジュールは、新たなリグレットサンプルを取得すること、およびリザーバサンプリングアルゴリズムに従って、新たなリグレットサンプルを第1のデータストアの中に記憶することが可能である。
【０３９１】
任意選択の実施形態において、リザーバサンプリングアルゴリズムに従って、新たなリグレットサンプルを第1のデータストアの中に記憶することは、第1のデータストアが満杯であるかどうかを判断することと、第1のデータストアが満杯であると判断したことに応答して、第1のデータストア中のいくつかのリグレットサンプルのうちの1つを、新たなリグレットサンプルで置き換えることとを含む。
【０３９２】
任意選択の実施形態において、CFRアルゴリズムはロバストサンプリングCFRアルゴリズムを含む。
【０３９３】
任意選択の実施形態において、プレーヤの状態における可能な行動の戦略値は、平均戦略の分子を含む。
【０３９４】
任意選択の実施形態において、プレーヤの状態における可能な行動のリグレット値は、プレーヤの状態における可能な行動の反事実値に基づいて算出された、プレーヤの状態における可能な行動の反事実リグレット値を含む。
【０３９５】
任意選択の実施形態において、装置1200は、プレーヤと少なくとも他のプレーヤとの間の戦略的対話における戦略探索における反事実的リグレット最小化(CFR)アルゴリズムの2回以上の反復の各々において、サンプリング方式に従って、プレーヤの第2の状態におけるいくつかの可能な行動の中から、可能な行動をサンプリングするためのサンプリングモジュールと、プレーヤの第2の状態における可能な行動の反事実値を算出するための第1の算出モジュールと、プレーヤの第2の状態における可能な行動の反事実値に基づいて、プレーヤの第2の状態における可能な行動のリグレット値を算出するための第2の算出モジュールと、リグレットマッチングアルゴリズムに従って、プレーヤの第2の状態における可能な行動のリグレット値に基づいて、プレーヤの第2の状態における可能な行動の更新された戦略を算出するための第3の算出モジュールと、プレーヤの第2の状態における可能な行動の更新された戦略に基づいて、プレーヤの第2の状態における可能な行動の戦略値を算出するための第4の算出モジュールとをさらに含む。
【０３９６】
任意選択の実施形態において、装置1200は、前の反復における第1のニューラルネットワークのパラメータに基づいて、第1のニューラルネットワークのパラメータを初期化するための第1の初期化モジュールと、前の反復における第2のニューラルネットワークのパラメータに基づいて、第2のニューラルネットワークのパラメータを初期化するための第2の初期化モジュールとをさらに含む。
【０３９７】
前の実施形態に示されたシステム、装置、モジュール、またはユニットは、コンピュータチップもしくはエンティティを使うことによって実装され得るか、または特定の機能を有する製品を使うことによって実装され得る。典型的な実施形態デバイスがコンピュータであり、コンピュータは、パーソナルコンピュータ、ラップトップコンピュータ、セルラーフォン、カメラフォン、スマートフォン、携帯情報端末、メディアプレーヤ、ナビゲーションデバイス、eメール受信および送付デバイス、ゲームコンソール、タブレットコンピュータ、装着可能デバイス、またはこれらのデバイスの任意の組合せであってもよい。
【０３９８】
装置の中の各モジュールの機能および役割の実施形態プロセスについて、前の方法における対応するステップからなる実施形態プロセスへの参照が行われる場合がある。詳細については、簡単のために、ここでは省く。
【０３９９】
装置実施形態は基本的に、方法実施形態に対応するので、関連部分について、方法実施形態における関連記述に対して参照が行われる場合がある。前に記載した装置実施形態は、例にすぎない。別個の部分として記述されるモジュールは、物理的に別個であってもなくてもよく、モジュールとして表示される部分は、物理モジュールであってもなくてもよく、ある位置に位置決めされ得るか、またはいくつかのネットワークモジュール上で分散され得る。モジュールの一部または全部が、本明細書の解決法の目的を達成するために、実際の需要に基づいて選択されてよい。当業者は、本出願の実施形態を理解し、創造的努力なしで実装することができよう。
【０４００】
再度図12を参照すると、これは、2人以上のプレーヤの間の戦略的対話における戦略探索のための反事実的リグレット最小化(CFR)を実施するためのデータ処理装置の内部機能モジュールおよび構造を示していと解釈することができる。本質的な実行本体は電子デバイスであってよく、電子デバイスは、1つまたは複数のプロセッサと、1つまたは複数のプロセッサの実行可能命令を記憶するように構成されたメモリとを含む。
【０４０１】
1つまたは複数のプロセッサは、いくつかのリグレットサンプルを第1のデータストアに記憶することであって、いくつかのリグレットサンプルの各々は、プレーヤの状態、およびプレーヤの状態における可能な行動のリグレット値を含み、いくつかのリグレットサンプルは、プレーヤと少なくとも他のプレーヤとの間の戦略的対話における戦略探索における反事実的リグレット最小化(CFR)アルゴリズムの2回以上の反復において取得される、ことと、いくつかの戦略サンプルを第2のデータストアに記憶することであって、いくつかの戦略サンプルの各々は、プレーヤの状態、およびプレーヤの状態における可能な行動の戦略値を含む、ことと、第1のデータストア中のいくつかのリグレットサンプルに基づいて、プレーヤの状態における可能な行動のリグレット値を予測するための、第1のニューラルネットワークのパラメータを更新することと、第2のデータストア中のいくつかの戦略サンプルに基づいて、プレーヤの状態における可能な行動の戦略値を予測するための、第2のニューラルネットワークのパラメータを更新することとを行うように構成される。いくつかの実施形態では、2人以上のプレーヤの間の戦略的対話は、2人以上のプレーヤが関与する不完全情報ゲーム(IIG)によってモデル化され得る。一例として、IIGは、少なくともプレーヤおよび第2のプレーヤが関与する協調型製品サービス推奨サービスを表し、プレーヤは、第2のプレーヤの情報への制限付きアクセスを有し、プレーヤの状態は、第2のプレーヤによって提供された情報の履歴を含み、プレーヤの可能な行動は、製品サービス推奨を顧客に提供するための、第2のプレーヤによって提供された情報の履歴に応答する、可能な行動を含む。
【０４０２】
任意選択で、1つまたは複数のプロセッサは、プレーヤの第1の状態、およびプレーヤの第1の状態における第1の可能な行動を識別し、第1のニューラルネットワークのパラメータを使って、プレーヤの第1の状態における第1の可能な行動の第1のリグレット値を予測し、第2のニューラルネットワークのパラメータを使って、プレーヤの第1の状態における第1の可能な行動の第1の戦略値を予測するように構成される。
【０４０３】
任意選択で、1つまたは複数のプロセッサは、新たなリグレットサンプルを取得し、リザーバサンプリングアルゴリズムに従って、新たなリグレットサンプルを第1のデータストアの中に記憶するように構成される。
【０４０４】
任意選択で、1つまたは複数のプロセッサは、第1のデータストアが満杯であるかどうかを判断し、第1のデータストアが満杯であると判断したことに応答して、第1のデータストア中のいくつかのリグレットサンプルのうちの1つを、新たなリグレットサンプルで置き換えるように構成される。
【０４０５】
任意選択で、CFRアルゴリズムは、ロバストサンプリングCFRアルゴリズムを含む。
【０４０６】
任意選択で、プレーヤの状態における可能な行動の戦略値は、平均戦略の分子を含む。
【０４０７】
任意選択で、プレーヤの状態における可能な行動のリグレット値は、プレーヤの状態における可能な行動の反事実値に基づいて算出された、プレーヤの状態における可能な行動の反事実リグレット値を含む。
【０４０８】
任意選択で、1つまたは複数のプロセッサは、プレーヤと少なくとも他のプレーヤとの間の戦略的対話における戦略探索における反事実的リグレット最小化(CFR)アルゴリズムの2回以上の反復の各々において、サンプリング方式に従って、プレーヤの第2の状態におけるいくつかの可能な行動の中から、可能な行動をサンプリングし、プレーヤの第2の状態における可能な行動の反事実値を算出し、プレーヤの第2の状態における可能な行動の反事実値に基づいて、プレーヤの第2の状態における可能な行動のリグレット値を算出し、リグレットマッチングアルゴリズムに従って、プレーヤの第2の状態における可能な行動のリグレット値に基づいて、プレーヤの第2の状態における可能な行動の更新された戦略を算出し、プレーヤの第2の状態における可能な行動の更新された戦略に基づいて、プレーヤの第2の状態における可能な行動の戦略値を算出するように構成される。
【０４０９】
任意選択で、1つまたは複数のプロセッサは、前の反復における第1のニューラルネットワークのパラメータに基づいて、第1のニューラルネットワークのパラメータを初期化し、前の反復における第2のニューラルネットワークのパラメータに基づいて、第2のニューラルネットワークのパラメータを初期化するように構成される。
【０４１０】
本主題の記載された実施形態は、1つまたは複数の特徴を、単独で、または組合せとして含み得る。たとえば、第1の実施形態は、2人以上のプレーヤの間の戦略的対話における戦略探索のための反事実的リグレット最小化(CFR)を実施するためのコンピュータ実装方法である。この方法は、いくつかのリグレットサンプルを第1のデータストアに記憶するステップであって、いくつかのリグレットサンプルの各々は、プレーヤの状態、およびプレーヤの状態における可能な行動のリグレット値を含み、いくつかのリグレットサンプルは、プレーヤと少なくとも他のプレーヤとの間の戦略的対話における戦略探索における反事実的リグレット最小化(CFR)アルゴリズムの2回以上の反復において取得される、ステップと、いくつかの戦略サンプルを第2のデータストアに記憶するステップであって、いくつかの戦略サンプルの各々は、プレーヤの状態、およびプレーヤの状態における可能な行動の戦略値を含む、ステップと、第1のデータストア中のいくつかのリグレットサンプルに基づいて、プレーヤの状態における可能な行動のリグレット値を予測するための、第1のニューラルネットワークのパラメータを更新するステップと、第2のデータストア中のいくつかの戦略サンプルに基づいて、プレーヤの状態における可能な行動の戦略値を予測するための、第2のニューラルネットワークのパラメータを更新するステップとを含む。
【０４１１】
上記および他の記載される実施形態は各々、任意選択で、以下の特徴のうちの1つまたは複数を含み得る。
【０４１２】
以下の特徴のうちのいずれとも組み合わせ可能な第1の特徴は、プレーヤの第1の状態、およびプレーヤの第1の状態における第1の可能な行動を識別することと、第1のニューラルネットワークのパラメータを使って、プレーヤの第1の状態における第1の可能な行動の第1のリグレット値を予測することと、第2のニューラルネットワークのパラメータを使って、プレーヤの第1の状態における第1の可能な行動の第1の戦略値を予測することとをさらに含む。
【０４１３】
以下の特徴のうちのいずれとも組み合わせ可能な第2の特徴は、新たなリグレットサンプルを取得することと、リザーバサンプリングアルゴリズムに従って、新たなリグレットサンプルを第1のデータストアの中に記憶することとをさらに含む。
【０４１４】
以下の特徴のうちのいずれとも組み合わせ可能な第3の特徴において、リザーバサンプリングアルゴリズムに従って、新たなリグレットサンプルを第1のデータストアの中に記憶することは、第1のデータストアが満杯であるかどうかを判断することと、第1のデータストアが満杯であると判断したことに応答して、第1のデータストア中のいくつかのリグレットサンプルのうちの1つを、新たなリグレットサンプルで置き換えることとを含む。
【０４１５】
以下の特徴のうちのいずれとも組み合わせ可能な第4の特徴において、CFRアルゴリズムはロバストサンプリングCFRアルゴリズムを含む。
【０４１６】
以下の特徴のうちのいずれとも組み合わせ可能な第5の特徴において、プレーヤの状態における可能な行動の戦略値は、平均戦略の分子を含む。
【０４１７】
以下の特徴のうちのいずれとも組み合わせ可能な第6の特徴において、プレーヤの状態における可能な行動のリグレット値は、プレーヤの状態における可能な行動の反事実値に基づいて算出された、プレーヤの状態における可能な行動の反事実リグレット値を含む。
【０４１８】
以下の特徴のうちのいずれとも組み合わせ可能な第7の特徴は、プレーヤと少なくとも他のプレーヤとの間の戦略的対話における戦略探索における反事実的リグレット最小化(CFR)アルゴリズムの2回以上の反復の各々において、サンプリング方式に従って、プレーヤの第2の状態におけるいくつかの可能な行動の中から、可能な行動をサンプリングすることと、プレーヤの第2の状態における可能な行動の反事実値を算出することと、プレーヤの第2の状態における可能な行動の反事実値に基づいて、プレーヤの第2の状態における可能な行動のリグレット値を算出することと、リグレットマッチングアルゴリズムに従って、プレーヤの第2の状態における可能な行動のリグレット値に基づいて、プレーヤの第2の状態における可能な行動の更新された戦略を算出することと、プレーヤの第2の状態における可能な行動の更新された戦略に基づいて、プレーヤの第2の状態における可能な行動の戦略値を算出することとをさらに含む。
【０４１９】
以下の特徴のうちのいずれとも組み合わせ可能な第8の特徴は、前の反復における第1のニューラルネットワークのパラメータに基づいて、第1のニューラルネットワークのパラメータを初期化することと、前の反復における第2のニューラルネットワークのパラメータに基づいて、第2のニューラルネットワークのパラメータを初期化することとをさらに含む。
【０４２０】
第2の実施形態において、システムは、1つまたは複数のプロセッサと、1つまたは複数のプロセッサに結合されるとともに、第1の実施形態および上述した特徴のうちの1つまたは複数の、その任意選択の組合せのいずれかの方法を実施するように、1つまたは複数のプロセッサによって実行可能な命令を記憶した1つまたは複数のコンピュータ可読メモリとを含む。
【０４２１】
第3の実施形態において、2人以上のプレーヤが関与する戦略的対話における戦略探索のための反事実的リグレット最小化(CFR)を実施するための装置は、いくつかのリグレットサンプルを第1のデータストアに記憶するための第1の記憶モジュールであって、いくつかのリグレットサンプルの各々は、プレーヤの状態、およびプレーヤの状態における可能な行動のリグレット値を含み、いくつかのリグレットサンプルは、プレーヤと少なくとも他のプレーヤとの間の戦略的対話における戦略探索における反事実的リグレット最小化(CFR)アルゴリズムの2回以上の反復において取得される、第1の記憶モジュールと、いくつかの戦略サンプルを第2のデータストアに記憶するための第2の記憶モジュールであって、いくつかの戦略サンプルの各々は、プレーヤの状態、およびプレーヤの状態における可能な行動の戦略値を含む、第2の記憶モジュールと、第1のデータストア中のいくつかのリグレットサンプルに基づいて、プレーヤの状態における可能な行動のリグレット値を予測するための、第1のニューラルネットワークのパラメータを更新するための第1の更新モジュールと、第2のデータストア中のいくつかの戦略サンプルに基づいて、プレーヤの状態における可能な行動の戦略値を予測するための、第2のニューラルネットワークのパラメータを更新するための第2の更新モジュールとを含む。いくつかの実施形態では、2人以上のプレーヤの間の戦略的対話は、2人以上のプレーヤが関与する不完全情報ゲーム(IIG)によってモデル化され得る。一例として、IIGは、少なくともプレーヤおよび第2のプレーヤが関与する協調型製品サービス推奨サービスを表し、プレーヤは、第2のプレーヤの情報への制限付きアクセスを有し、プレーヤの状態は、第2のプレーヤによって提供された情報の履歴を含み、プレーヤの可能な行動は、製品サービス推奨を顧客に提供するための、第2のプレーヤによって提供された情報の履歴に応答する、可能な行動を含む。
【０４２２】
上記および他の記載される実施形態は各々、任意選択で、以下の特徴のうちの1つまたは複数を含み得る。
【０４２３】
以下の特徴のうちのいずれとも組み合わせ可能な第1の特徴は、プレーヤの第1の状態、およびプレーヤの第1の状態における第1の可能な行動を識別するための識別モジュールと、第1のニューラルネットワークのパラメータを使って、プレーヤの第1の状態における第1の可能な行動の第1のリグレット値を予測するための第1の予測モジュールと、第2のニューラルネットワークのパラメータを使って、プレーヤの第1の状態における第1の可能な行動の第1の戦略値を予測するための第2の予測モジュールとをさらに含む。
【０４２４】
以下の特徴のうちのいずれとも組み合わせ可能な第2の特徴において、第1の記憶モジュールは、新たなリグレットサンプルを取得すること、およびリザーバサンプリングアルゴリズムに従って、新たなリグレットサンプルを第1のデータストアの中に記憶することが可能である。
【０４２５】
以下の特徴のうちのいずれとも組み合わせ可能な第3の特徴において、リザーバサンプリングアルゴリズムに従って、新たなリグレットサンプルを第1のデータストアの中に記憶することは、第1のデータストアが満杯であるかどうかを判断することと、第1のデータストアが満杯であると判断したことに応答して、第1のデータストア中のいくつかのリグレットサンプルのうちの1つを、新たなリグレットサンプルで置き換えることとを含む。
【０４２６】
以下の特徴のうちのいずれとも組み合わせ可能な第4の特徴において、CFRアルゴリズムはロバストサンプリングCFRアルゴリズムを含む。
【０４２７】
以下の特徴のうちのいずれとも組み合わせ可能な第5の特徴において、プレーヤの状態における可能な行動の戦略値は、平均戦略の分子を含む。
【０４２８】
以下の特徴のうちのいずれとも組み合わせ可能な第6の特徴において、プレーヤの状態における可能な行動のリグレット値は、プレーヤの状態における可能な行動の反事実値に基づいて算出された、プレーヤの状態における可能な行動の反事実リグレット値を含む。
【０４２９】
以下の特徴のうちのいずれとも組み合わせ可能な第7の特徴は、プレーヤと少なくとも他のプレーヤとの間の戦略的対話における戦略探索における反事実的リグレット最小化(CFR)アルゴリズムの2回以上の反復の各々において、サンプリング方式に従って、プレーヤの第2の状態におけるいくつかの可能な行動の中から、可能な行動をサンプリングするためのサンプリングモジュールと、プレーヤの第2の状態における可能な行動の反事実値を算出するための第1の算出モジュールと、プレーヤの第2の状態における可能な行動の反事実値に基づいて、プレーヤの第2の状態における可能な行動のリグレット値を算出するための第2の算出モジュールと、リグレットマッチングアルゴリズムに従って、プレーヤの第2の状態における可能な行動のリグレット値に基づいて、プレーヤの第2の状態における可能な行動の更新された戦略を算出するための第3の算出モジュールと、プレーヤの第2の状態における可能な行動の更新された戦略に基づいて、プレーヤの第2の状態における可能な行動の戦略値を算出するための第4の算出モジュールとをさらに含む。
【０４３０】
以下の特徴のうちのいずれとも組み合わせ可能な第8の特徴は、前の反復における第1のニューラルネットワークのパラメータに基づいて、第1のニューラルネットワークのパラメータを初期化するための第1の初期化モジュールと、前の反復における第2のニューラルネットワークのパラメータに基づいて、第2のニューラルネットワークのパラメータを初期化するための第2の初期化モジュールとをさらに含む。
【０４３１】
本明細書に記載する主題ならびに行動および動作の実施形態は、デジタル電子回路機構で、または有形に実施されるコンピュータソフトウェアもしくはファームウェアで、本明細書において開示した構造およびそれらの構造的等価物を含むコンピュータハードウェアで、またはそれらのうちの1つもしくは複数の、組合せで実装することができる。本明細書において説明される主題の実施形態は、1つまたは複数のコンピュータプログラムとして、たとえば、データ処理装置によって実行するか、またはデータ処理装置の動作を制御するための、コンピュータプログラムキャリア上に符号化されたコンピュータプログラム命令の1つまたは複数のモジュールとして、実装することができる。たとえば、コンピュータプログラムキャリアが、命令を符号化または記憶した1つまたは複数のコンピュータ可読記憶媒体を含み得る。キャリアは、磁気、光磁気、もしくは光ディスク、固体状態ドライブ、ランダムアクセスメモリ(RAM)、読取り専用メモリ(ROM)、または他のタイプの媒体など、有形の非一時的コンピュータ可読媒体であってよい。代替または追加として、キャリアは、データ処理装置による実行のために、適切な受信機装置への送信用の情報を符号化するように生成される、人工的に生成された伝搬信号、たとえば、機械生成された電気、光学、または電磁信号であってよい。コンピュータ記憶媒体は、機械可読記憶デバイス、機械可読記憶基板、ランダムもしくはシリアルアクセスメモリデバイス、またはそれらのうちの1つもしくは複数の、組合せであるか、またはその一部であってよい。コンピュータ記憶媒体は、伝播される信号ではない。
【０４３２】
コンピュータプログラムは、プログラム、ソフトウェア、ソフトウェアアプリケーション、アプリ、モジュール、ソフトウェアモジュール、エンジン、スクリプト、またはコードと呼ばれるか、またはそれらとして知られている場合もあり、コンパイル型もしくはインタープリタ型言語、または宣言型もしくは手続き型言語を含む、どの形のプログラミング言語でも書かれてよく、スタンドアロンプログラムとして、またはモジュール、構成要素、エンジン、サブルーチン、もしくはコンピューティング環境における実行に適した他の単位として、を含む、どの形でも展開することができ、環境は、1つまたは複数のロケーションにある、データ通信ネットワークによって相互接続された1つまたは複数のコンピュータを含み得る。
【０４３３】
コンピュータプログラムが、ファイルシステム内のファイルに対応してよいが、そうである必要はない。コンピュータプログラムは、他のプログラムもしくはデータ、たとえば、マークアップ言語ドキュメントに記憶された1つもしくは複数のスクリプトを保持するファイル部分に、問題になっているプログラムに専用の単一のファイルに、または複数の協調ファイル、たとえば、1つもしくは複数のモジュール、サブプログラム、もしくはコードの部分を記憶するファイルに記憶することができる。
【０４３４】
コンピュータプログラムの実行のためのプロセッサは、例として、汎用および特殊目的マイクロプロセッサの両方、ならびにどの種類のデジタルコンピュータのどの1つまたは複数のプロセッサも含む。概して、プロセッサが、実行用の、コンピュータプログラムの命令ならびにデータを、プロセッサに結合された非一時的コンピュータ可読媒体から受信することになる。
【０４３５】
「データ処理装置」という用語は、例として、プログラム可能プロセッサ、1つのコンピュータ、または複数のプロセッサもしくはコンピュータを含む、データを処理するための、あらゆる種類の装置、デバイス、および機械を包含する。データ処理装置は、特殊目的論理回路機構、たとえば、FPGA(フィールドプログラマブルゲートアレイ)、ASIC(特定用途向け集積回路)、またはGPU(グラフィックス処理ユニット)を含むことができる。装置はまた、ハードウェアに加え、コンピュータプログラムのための実行環境を作成するコード、たとえば、プロセッサファームウェア、プロトコルスタック、データベース管理システム、オペレーティングシステム、またはそれらのうちの1つもしくは複数の、組合せを構成するコードを含むことができる。
【０４３６】
本明細書に記載したプロセスおよび論理フローは、入力データに対して動作し、出力を生成することによって動作を実施するための1つまたは複数のコンピュータプログラムを実行する1つまたは複数のコンピュータまたはプロセッサによって実施され得る。プロセスおよび論理フローは、特殊目的論理回路機構、たとえば、FPGA、ASIC、もしくはGPUによって、または特殊目的論理回路機構と1つもしくは複数のプログラムされたコンピュータの組合せによって実施されてもよい。
【０４３７】
コンピュータプログラムの実行に適したコンピュータは、汎用もしくは特殊目的マイクロプロセッサもしくは両方、またはどの他の種類の中央処理ユニットに基づいてもよい。概して、中央処理ユニットは、読取り専用メモリもしくはランダムアクセスメモリまたは両方から、命令およびデータを受信することになる。コンピュータの要素は、命令を実行するための中央処理ユニットと、命令およびデータを記憶するための1つまたは複数のメモリデバイスとを含み得る。中央処理ユニットおよびメモリは、特殊目的論理回路要素によって補完することも、その中に組み込むこともできる。
【０４３８】
概して、コンピュータはまた、1つまたは複数の記憶デバイスを含むか、あるいは1つまたは複数の記憶デバイスからデータを受信し、またはそこへデータを転送するために動作可能に結合されることになる。記憶デバイスは、たとえば、磁気、光磁気、もしくは光ディスク、固体状態ドライブ、またはどの他のタイプの非一時的コンピュータ可読媒体であってもよい。ただし、コンピュータは、そのようなデバイスを有する必要はない。したがって、コンピュータは、ローカルおよび/またはリモートである、1つまたは複数のメモリなど、1つまたは複数の記憶デバイスに結合され得る。たとえば、コンピュータは、コンピュータの一体型構成要素である1つもしくは複数のローカルメモリを含んでよく、またはコンピュータは、クラウドネットワーク中にある1つもしくは複数のリモートメモリに結合されてよい。その上、コンピュータは、他のデバイス、たとえば、ほんのいくつかの例を挙げれば、モバイル電話、携帯情報端末(PDA)、モバイルオーディオまたはビデオプレーヤ、ゲームコンソール、全地球測位システム(GPS)受信機、またはポータブル記憶デバイス、たとえば、ユニバーサルシリアルバス(USB)フラッシュドライブに組み込むことができる。
【０４３９】
構成要素は、直接または1つもしくは複数の仲介構成要素を介して、のいずれかで、電気的または光学的など、通信可能に互いに接続されることによって、互い「に結合され」得る。構成要素はまた、構成要素のうちの1つが他の構成要素に統合される場合、互い「に結合され」得る。たとえば、プロセッサに統合される記憶構成要素(たとえば、L2キャッシュ構成要素)は、プロセッサ「に結合される」。
【０４４０】
ユーザとの対話を提供するために、本明細書に記載する主題の実施形態は、ユーザに情報を表示するためのディスプレイデバイス、たとえば、LCD(液晶ディスプレイ)モニタと、ユーザがコンピュータに入力を提供し得るための入力デバイス、たとえば、キーボードおよびポインティングデバイス、たとえば、マウス、トラックボールまたはタッチパッドとを有するコンピュータ上で実装されるか、またはコンピュータと通信するように構成され得る。他の種類のデバイスも、ユーザとの対話を可能にするのに使われることが可能であり、たとえば、ユーザに与えられるフィードバックは、どの形の感覚フィードバックでも、たとえば、視覚フィードバック、聴覚フィードバック、または触覚フィードバックであることができ、ユーザからのインプットは、音響、発話、または触覚インプットを含む、どの形でも受信されることが可能である。さらに、コンピュータは、ユーザによって使われるデバイスへドキュメントを送信し、デバイスからドキュメントを受信することによって、たとえば、ウェブブラウザから受信された要求に応答して、ユーザのデバイス上のウェブブラウザへウェブページを送信することによって、またはユーザデバイス、たとえば、スマートフォンもしくは電子タブレット上で稼動するアプリと対話することによって、ユーザと対話することができる。また、コンピュータは、パーソナルデバイス、たとえば、メッセージングアプリケーションを稼動しているスマートフォンにテキストメッセージまたは他の形のメッセージを送り、ユーザから引き換えに応答メッセージを受信することによって、ユーザと対話することができる。
【０４４１】
本明細書は、「ように構成される」という用語を、システム、装置、およびコンピュータプログラム構成要素との関連で使っている。1つまたは複数のコンピュータからなるシステムが特定の動作または行動を実施するように構成されることは、システムが、動作の際にシステムに動作または行動を実施させるソフトウェア、ファームウェア、ハードウェア、またはそれらの組合せをインストールしたことを意味する。1つまたは複数のコンピュータプログラムが、特定の動作または行動を実施するように構成されることは、1つまたは複数のプログラムが、データ処理装置によって実行されると、動作または行動を装置に実施させる命令を含むことを意味する。特殊目的論理回路機構が、特定の動作または行動を実施するように構成されることは、回路機構が、動作または行動を実施する電子論理を有することを意味する。
【０４４２】
本明細書は、多くの具体的な実施形態詳細を含むが、これらは、請求項自体によって定義される、特許請求されているものの範囲において、限定と解釈されるべきではなく、特定の実施形態に特有であり得る特徴の記述として解釈されるべきである。また、別個の実施形態の文脈において本明細書で説明したいくつかの特徴は、単一の実施形態において組み合わせて実現することができる。逆に、単一の実施形態の文脈において記載される様々な特徴はまた、複数の実施形態において別々に、またはどの適切な部分組合せでも実現することができる。さらに、特徴は、いくつかの組合せで働くものとして上記で説明され、初めにそのように特許請求される場合さえあるが、特許請求された組合せからの1つまたは複数の特徴は、場合によってはその組合せから削除することができ、請求される組合せは、部分組合せ、または部分組合せの変形形態を対象とすることができる。
【０４４３】
同様に、動作は、特定の順序において図面に示され、請求項に具陳されているが、これは、そのような動作が図示された特定の順序において、もしくは順次に実施されることを必要とするか、または、所望の結果を達成するためにすべての示された動作が実施されることを必要とするものと理解されるべきではない。いくつかの状況では、マルチタスキングおよび並列処理が有利であり得る。その上、上述した実施形態における様々なシステムモジュールおよび構成要素の分離は、すべての実施形態においてそのような分離を必要とするものとして理解されるべきではなく、記載したプログラム構成要素およびシステムは概して、単一のソフトウェア製品に一緒に統合されるか、または複数のソフトウェア製品にパッケージングされることが可能であることを理解されたい。
【０４４４】
本主題の特定の実施形態について記載した。他の実施形態は、以下の特許請求の範囲内である。たとえば、請求項に具陳される行動は、異なる順序で実施され、依然として望ましい結果を達成することができる。一例として、添付の図面に示されるプロセスは、望ましい結果を達成するのに、図示される特定の順序、または順番を必ずしも要求しない。いくつかのケースでは、マルチタスキングおよび並列処理が有利であり得る。
【符号の説明】
【０４４５】
102  部分的ゲームツリー、第1の部分ツリー、ゲームツリー
104  部分的ゲームツリー、右部分ツリー、ゲームツリー
202  外部サンプリング方式、ゲームツリー
204  結果サンプリング方式、ゲームツリー
206  ロバストサンプリング方式、ゲームツリー
300  擬似コード
400  二重ニューラルCFRアルゴリズム
410  ゲームツリー
420  ニューラルネットワーク、RSN、RegretSumNetwork
430  ニューラルネットワーク、ASN、AveStrategyNetwork
500  擬似コード
600  擬似コード
700  擬似コード
800  サンプリングプロセス
900  二重ニューラルCFRアルゴリズム、サンプリングプロセス、プロセス
1000  コンピュータシステム、コンピュータ実装システム、システム
1002  コンピュータ
1003  システムバス
1004  インターフェース
1005  プロセッサ
1006  データベース
1007  メモリ
1008  アプリケーション
1012  アプリケーションプログラミングインターフェース(API)
1013  サービスレイヤ
1014  電源
1016  リザーバMR
1018  リザーバMS
1026  リグレットサンプル
1028  戦略サンプル
1030  ネットワーク
1100  装置
1101  第1の識別モジュール
1102  第1のサンプリングモジュール
1103  第2の識別モジュール
1104  第2のサンプリングモジュール
1105  処理モジュール
1200  装置
1201  第1の記憶モジュール
1202  第2の記憶モジュール
1203  第1の更新モジュール
1204  第2の更新モジュール
【図１】
2021509492.tif 000121
【図２】
2021509492.tif 000122
【図３】
2021509492.tif 000123
【図４】
2021509492.tif 000124
【図５】
2021509492.tif 000125
【図６】
2021509492.tif 000126
【図７】
2021509492.tif 000127
【図８】
2021509492.tif 000128
【図９】
2021509492.tif 000129
【図１０】
2021509492.tif 000130
【図１１】
2021509492.tif 000131
【図１２】
2021509492.tif 000132
【手続補正書】
【提出日】令和2年5月15日(2020.5.15)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
2人以上の当事者の間の戦略的対話における戦略探索のための反事実的リグレット最小化(CFR)を実施するためのコンピュータ実装方法であって、
複数の増分リグレットサンプルを第1のデータストアに記憶するステップであって、前記複数の増分リグレットサンプルの各々は、当事者の状態、および前記当事者の前記状態における可能な行動のリグレット値を含み、前記複数の増分リグレットサンプルは、前記当事者と少なくとも他の当事者との間の戦略的対話における戦略探索における反事実的リグレット最小化(CFR)アルゴリズムの2回以上の反復のうちの現在の反復において取得される新たな追加的なリグレットサンプルである、ステップと、
複数の戦略サンプルを第2のデータストアに記憶するステップであって、前記複数の戦略サンプルの各々は、前記当事者の状態、および前記当事者の前記状態における可能な行動の戦略値を含む、ステップと、
異なる反復にわたって取得されるリグレットサンプルに基づくのではなく、前記第1のデータストアの中の前記複数の増分リグレットサンプルのみに基づいて、前記当事者の状態における可能な行動のリグレット値を予測するための、第1のニューラルネットワークのパラメータを更新するステップと、
前記第2のデータストアの中の前記複数の戦略サンプルに基づいて、前記当事者の状態における可能な行動の戦略値を予測するための、第2のニューラルネットワークのパラメータを更新するステップとを含む方法。
【請求項２】
前記当事者の第1の状態、および前記当事者の前記第1の状態における第1の可能な行動を識別するステップと、
前記第1のニューラルネットワークの前記パラメータを使って、前記当事者の前記第1の状態における前記第1の可能な行動の第1のリグレット値を予測するステップと、
前記第2のニューラルネットワークの前記パラメータを使って、前記当事者の前記第1の状態における前記第1の可能な行動の第1の戦略値を予測するステップと
をさらに含む、請求項1に記載の方法。
【請求項３】
各反復の後に前記第1のデータストアをクリアするステップをさらに含む、請求項1に記載の方法。
【請求項４】
前記第2のデータストアから重複する記録を削除するステップをさらに含む、請求項1に記載の方法。
【請求項５】
前記CFRアルゴリズムはロバストサンプリングCFRアルゴリズムを含む、請求項1に記載の方法。
【請求項６】
前記当事者の前記状態における可能な行動の前記戦略値は平均戦略の分子を含む、請求項1に記載の方法。
【請求項７】
前記当事者の前記状態における可能な行動の前記リグレット値は、前記当事者の前記状態における前記可能な行動の反事実値に基づいて算出された、前記当事者の前記状態における前記可能な行動の反事実リグレット値を含む、請求項1に記載の方法。
【請求項８】
前記当事者と前記少なくとも他の当事者との間の戦略的対話における戦略探索における反事実的リグレット最小化(CFR)アルゴリズムの前記2回以上の反復の各々において、
サンプリング方式に従って、当事者の第2の状態における複数の可能な行動の中から可能な行動をサンプリングするステップと、
前記当事者の前記第2の状態における前記可能な行動の反事実値を算出するステップと、
前記当事者の前記第2の状態における前記可能な行動の前記反事実値に基づいて、前記当事者の前記第2の状態における前記可能な行動のリグレット値を算出するステップと、
リグレットマッチングアルゴリズムに従って、前記当事者の前記第2の状態における前記可能な行動の前記リグレット値に基づいて、前記当事者の前記第2の状態における前記可能な行動の更新された戦略を算出するステップと、
前記当事者の前記第2の状態における前記可能な行動の前記更新された戦略に基づいて、前記当事者の前記第2の状態における前記可能な行動の戦略値を算出するステップと
をさらに含む、請求項1に記載の方法。
【請求項９】
前の反復における前記第1のニューラルネットワークのパラメータに基づいて、前記第1のニューラルネットワークの前記パラメータを初期化するステップと、
前の反復における前記第2のニューラルネットワークのパラメータに基づいて、前記第2のニューラルネットワークの前記パラメータを初期化するステップと
をさらに含む、請求項1に記載の方法。
【請求項１０】
前記当事者は、前記他の当事者の情報への制限付きアクセスを有し、前記当事者の前記状態は、前記他の当事者によって提供された情報の履歴を含み、前記当事者の前記可能な行動は、顧客への製品サービス推奨を提供するために前記他の当事者によって提供された前記情報の履歴に応じた可能な行動を含む、請求項1に記載の方法。
【請求項１１】
コンピュータシステムによって実行可能な1つまたは複数の命令を記憶した非一時的なコンピュータ読み取り可能な媒体であって、前記1つまたは複数の命令は、前記コンピュータシステムによって実行されると、前記コンピュータシステムに請求項１から１０のうちいずれか一項に記載の方法を行わせる、非一時的なコンピュータ読み取り可能な媒体。
【請求項１２】
1つまたは複数のコンピュータと、
前記1つまたは複数のコンピュータに相互動作可能に結合されるとともに、前記1つまたは複数のコンピュータによって実行されたときに以下の1つ又は複数の動作を行う前記1つまたは複数の命令を記憶した有形の非一時的なコンピュータ読み取り可能な媒体を有する1つまたは複数のコンピュータメモリ装置と
を備えるコンピュータ実装システムであって、
前記1つ又は複数の動作は、
複数の増分リグレットサンプルを第1のデータストアに記憶することであって、前記複数の増分リグレットサンプルの各々は、当事者の状態、および前記当事者の前記状態における可能な行動のリグレット値を含み、前記複数の増分リグレットサンプルは、前記当事者と少なくとも他の当事者との間の戦略的対話における戦略探索における反事実的リグレット最小化(CFR)アルゴリズムの2回以上の反復のうちの現在の反復において取得される新たな追加的なリグレットサンプルである、ことと、
複数の戦略サンプルを第2のデータストアに記憶することであって、前記複数の戦略サンプルの各々は、前記当事者の状態、および前記当事者の前記状態における可能な行動の戦略値を含む、ことと、
異なる反復にわたって取得されるリグレットサンプルに基づくのではなく、前記第1のデータストアの中の前記複数の増分リグレットサンプルのみに基づいて、前記当事者の状態における可能な行動のリグレット値を予測するための、第1のニューラルネットワークのパラメータを更新することと、
前記第2のデータストアの中の前記複数の戦略サンプルに基づいて、前記当事者の状態における可能な行動の戦略値を予測するための、第2のニューラルネットワークのパラメータを更新することとを含むコンピュータ実装システム。
【請求項１３】
2人以上の当事者の間の戦略的対話における戦略探索のための反事実的リグレット最小化(CFR)を実施するための装置であって、前記装置は、
複数の増分リグレットサンプルを記憶するための第1のデータストアであって、前記複数の増分リグレットサンプルの各々は、当事者の状態、および前記当事者の前記状態における可能な行動のリグレット値を含み、前記複数の増分リグレットサンプルは、前記当事者と少なくとも他の当事者との間の戦略的対話における戦略探索における反事実的リグレット最小化(CFR)アルゴリズムの2回以上の反復のうちの現在の反復において取得される新たな追加的なリグレットサンプルである、第1のデータストアと、
複数の戦略サンプルを記憶するための第2のデータストアであって、前記複数の戦略サンプルの各々は、前記当事者の状態、および前記当事者の前記状態における可能な行動の戦略値を含む、第2のデータストアと、
1つまたは複数のコンピュータメモリ装置に結合されるとともに、1つまたは複数のプロセッサによって実行されると以下の1つ又は複数の動作を行う1つ又は複数の命令を記憶した有形の非一時的なコンピュータ読み取り可能な媒体を有する1つまたは複数のプロセッサとを備え、
前記1つ又は複数の動作は、
異なる反復にわたって取得されるリグレットサンプルに基づくのではなく、前記第1のデータストアの中の前記複数の増分リグレットサンプルのみに基づいて、前記当事者の状態における可能な行動のリグレット値を予測するための、第1のニューラルネットワークのパラメータを更新することと、
前記第2のデータストアの中の前記複数の戦略サンプルに基づいて、前記当事者の状態における可能な行動の戦略値を予測するための、第2のニューラルネットワークのパラメータを更新することとを含む、
装置。
【国際調査報告】
2021509492.tif 000133
2021509492.tif 000134