Поиск стратегии в стратегическом взаимодействии между сторонами - RU2743626C1

H означает терминальные истории и любой член z Z не является префиксом любых других последовательностей. A(h) = {a : ha H} - является набором доступных действий после нетерминальной истории h H/Z. Функция P игрока назначает член каждой нетерминальной истории, где c обозначает идентификатор (ID) случайного игрока, который обычно может быть, например, -1. P(h) - игрок, который предпринимает действие после истории h.

[033] I_i истории {h

H: P(h) = i} - информационный раздел игрока i. Набор I_i I_i является набором информации игрока i. I_i(h) относится к набору I_i информации в состоянии h. В некоторых вариантах осуществления I_i может помнить только информацию, наблюдаемую игроком i, включая скрытую переменную игрока i и публичные действия. Следовательно, I_i обозначает последовательность в IIG, т.е. h^v_ia₀a₂...a_L−1. В некоторых вариантах осуществления для I_i I_iи для любого h I_i, набор A(h) может обозначаться через A(I_i), а игрок P(h) обозначается как P(I_i). Для каждого игрока i N функция u_i(z) полезности определяет выплату состояния терминала z. Более подробное объяснение этих обозначений и определений будет обсуждаться ниже, включая пример, показанный на фиг. 1.

[034] На фиг.1 показана схема 100, иллюстрирующая примеры частичных игровых деревьев 102 и 104 в One-Card Poker в соответствии с вариантами осуществления этого описания. One-Card Poker - это IIG покер для двух игроков. One-Card Poker - это пример игры в расширенной форме. Правила игры определены следующим образом. Каждый игрок получает одну карту из колоды Х карт. Первый игрок может объявить пас или сделать ставку. Если первый игрок делает ставку, второй игрок может сделать объявление козырной масти или сбросить карты. Если первый игрок объявляет пас, второй игрок может объявить пас или сделать ставку. Если второй игрок делает ставку, первый игрок может сбросить карты или объявить козырную масть. Игра заканчивается двумя объявлениями пас, объявлением козырной масти или сбросом карт. Сбросивший карты игрок потеряет 1 фишку. Если игра закончилась двумя объявлениями пас, игрок с более высокой картой выигрывает 1 фишку. Если игра заканчивается объявлением козырной масти, игрок с более высокой картой выигрывает 2 фишки.

[035] Дерево игры - это ориентированный граф. Узлы дерева игры представляют позиции (или состояния игрока) в игре, и дерево игры может представлять движения или действия игрока в игре. На фиг. 1 z_i обозначает узел терминала, представляющий состояние терминала, а h_iобозначает узел не терминала. Каждое из частичных игровых деревьев 102 и 104 имеет корневой узел h_0,представляющий шанс. В первом частичном дереве 102 имеется 19 различных узлов, соответствующих 9 узлам h_i не терминала, включая шансh₀, и 10 узлов z_i терминала в левомдереве.

[036] В первом частичном дереве 102 раздают два игрока (игрок 0 и игрок 1) (дама, валет), как показано как «0: Q 1: J» в левом поддереве, и (дама, король), как показано как «0: Q 1: K» в правом поддереве.

[037] Траектория от корневого узла к каждому узлу - это история действий. Действия представлены буквами (например, F, C, P и B) или представлениями (например, «0: Q 1: J») рядом с ребрами (обозначены стрелками) дерева игры. Буквы F, C, P, B обозначают сброс карт, объявление козырной масти, пас и ставку соответственно.

[038] В расширенной игре h_i относитсяк истории действий. Например, как показано в первом частичном дереве 102, h3 включает в себядействия 0: Q, 1: J и P. h7 включает всебя действия 0: Q, 1: J, P и B. h8 включаетв себя действия 0: Q, 1: K, P и B. В первом частичном дереве 102 h3

h7, тоесть h3 являетсяпрефиксом h7. A(h₃) = {P,B} указывает, что набор доступных действий после истории h7 не терминала - это P и B. P(h3) = 1 указывает, что игрок, которыйпредпринимает действие после истории h3, является игроком 1.

[039] В IIG личная карта игрока 1 невидима для игрока 0, поэтому h₇ и h₈ фактически одинаковы для игрока 0. Набор информации может использоваться для обозначения набора этих неотличимых состояний. Аналогично, h₁ и h₂ находятся в одном и том же наборе информации. Для правого частичного дерева 104

и находятся в одном и том же наборе информации; и и находятся в одном и том же наборе информации.

[040] Как правило, любойI_i

I может помнить только информацию, наблюдаемую игроком i, включая скрытые переменные игрока i и публичные действия. Например, как показано в первом частичном дереве 102, набор информации h₇ и h₈указывает последовательность 0:Q, P и B. Поскольку h₇ и h₈ не различаютсяигроком 0 вIIG, если I₀ является набором информации h₇ и h_8,, I₀=I₀(h₇) = I₀(h₈).

[041] Профиль σ = {σi | σi

Σ_i,i N} стратегии представляет собой коллекцию стратегий для всех игроков, где Σ_i - набор всех возможных стратегий для игрока i. σ - i относится к стратегии всех игроков_,кроме игрока i. Для игрока i N стратегия σ_i(I_i) является функцией, которая назначает распределение действия по A (I_i) набору I_i информации. σi (a | h) обозначает вероятность действия a, предпринятого игроком i в состоянии h. В IIG, если два или более состояний имеют одинаковый набор информации, эти два или более состояний имеют одинаковую стратегию. То есть ∀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₀ - это набор информации h7 и h8, I₀= I₀(h₇) = I₀(h₈), σ₀(I₀) = σ₀(h₇) = σ₀(h₈), σ₀(a|I₀) = σ₀(a|h₇) = σ₀(a|h₈). На фиг. 1 одинаковый цвет, отличный от серого, для каждого состояния в одном и том же наборе информации.

[042] Для игрока i ожидаемая игровая полезность профиля σ стратегии обозначается как

, что является ожидаемым плей-офф всех узлов терминала. При фиксированном профиле стратегии σ_−i любая стратегия σ_i^*= игрока i, которая достигает максимального плей-офф от , является наилучшим ответом. Для игр в расширенной форме двух игроков равновесие по Нэшу представляет собой профиль стратегии , так что стратегия каждого игрока является лучшим ответом оппоненту. - равновесие по Нэшу является приближением равновесия по Нэшу, чей профиль стратегии σ^* удовлетворяет следующим условиям:

[043] Возможность использования стратегии σ_i может быть определена как

. Стратегия неиспользуемая, если if . В больших играх двух игроков с нулевой суммой, таких как покер, может быть трудно вычислить. Однако, если игроки чередуют свои позиции, значение пары игр равно нулю, то есть . Возможность использования профиля σ стратегии может быть определена как .

[044] Для итерационных способов, таких как CFR, σ^tможет относиться к профилю стратегии на t-й итерации. Вероятность достижения состояния истории h может быть обозначена через π^σ(h), если игроки предпринимают действия в соответствии с σ. Для пустой последовательности π^σ(∅) = 1. Вероятность достижения может быть разложена на

согласно с вкладом каждого игрока, где

и .

[045] Вероятность достижения набора I_i информации (также называемая вероятностьюдостижения набора информации) может быть определена как

. Если h^’ h, вероятность достижения состояния интервала от состояния h^’до h может быть определена как π^σ(h^’,h), тогда π^σ(h^’,h)=π^σ(h)/π^σ(h^’). Вероятности достижения , и могут бытьопределены аналогично.

[046] В больших IIG с нулевой суммой доказано, что CFR является эффективным способом для вычисления равновесия по Нэшу. Доказано, что вероятность достижения состояния одного игрока пропорциональна апостериорной вероятности скрытой переменной оппонента, т.е. P (h-iv | Ii) ∝ π-iσ (h), где h^v_iи I_i указывают конкретный h.

[047] Для игрока i и профиля σ стратегии контрфактивное значение (CFV) v_i^σ(h) в состоянии h можно определить как

(1)

где

- ожидаемое вознаграждение игрока i в соответствии с приблизительным апостериорным распределением скрытой переменной оппонента. Значение контрфактивного действия принятия действия a можно обозначить как v_i^σ(a|h) = v_i^σ(ha), и сожаление о принятии этого действия составляет r_i^σ(a|h) = v_i^σ(a|h) − v_i^σ(h).

[048] Аналогично, CFV набора I_i информации можно определить как

, и сожаление о действии a для данного набора I_i информации можно определить как = (1a)

[049] Тогда совокупное сожаление действия а после T итераций может быть вычислено по уравнению (2):

(2)

где Ri0_{(a |}^{Ii) =}0. Определить R_i^T,+(a|I_i) = max(R_i^T(a|I_i),0), текущаястратегия (или стратегия поведения)на итерации T+1 может быть обновлена, например, на основе сопоставления сожаления, согласно уравнению (3) ниже:

иначе (3).

[050] Средняя стратегия

от итерации 1 до T может быть определена как:

(4)

где

обозначает вероятность достижения набора Ii информации на t_-й итерации и используется для взвешивания соответствующей текущей стратегии .

[051] Определить

как дополнительный числитель в итерации t, тогда совокупный числитель средней стратегии можно определить как

, (5)

где S⁰(a|I_i) = 0.

[052] При решении игры оригинальная CFR пересекает все дерево игры в каждой итерации. Таким образом, оригинальная CFR может не обрабатывать большие игры с ограниченной памятью. Монте-Карло CFR (MCCFR) был введен, чтобы минимизировать контрфактивное сожаление. MCCFR может вычислить непредвзятую оценку контрфактивного значения и избежать прохода по всему дереву игры. Поскольку на каждой итерации посещаются только поднаборы всех наборов информации, MCCFR требует меньше памяти, чем оригинальная CFR.

[053] Например, определить Q = {Q₁,Q₂,...,Q_m}, где Q_j

Z это блок выборки историй терминала в каждой итерации, так что Qj охватывает набор Z. Как правило, разныеQj могут иметь перекрытие в соответствиис конкретной схемой выборки. Можно использовать несколько схем выборки.

[054] Фиг.2 - схема 200, иллюстрирующая примеры различных схем выборки в соответствии с вариантами осуществления этого описания. В частности, вспомогательный рисунок A иллюстрирует пример схемы 202 внешней выборки дерева игры; вспомогательный рисунок B иллюстрирует пример схемы 204 выборки результатов дерева игры, а вспомогательный рисунок C иллюстрирует пример схемы 206 надежной выборки дерева игры.

[055] Как показано на фиг.2 круг представляет узел игрока 0, прямоугольник представляет узел игрока 1, а треугольник представляет случайный узел. Сплошные ребра или стрелки представляют выбранные действия, тогда как пунктирные ребра или стрелки представляют невыбранные действия. Затененные узлы представляют выбранные узлы, тогда как пустые узлы представляют невыбранные узлы.

[056] Возьмем в качестве примера обновление игрока 0 со схемой 202 внешней выборки, как показано на вспомогательном рисунке A, узел игрока 0 пересекает все ветви узла игрока 0, узла не-игрока 0 (например, узла игрока 1 и случайного узла) случайным образом выбирает ветвь в соответствии с соответствующей стратегией выборки.

[057] Схема выборки результатов не различает разных игроков. Как показано на вспомогательном рисунке B, схема 204 выборки результатов случайным образом выбирает одну ветвь для всех игроков в соответствии с соответствующей стратегией выборки. Таким образом, только одна траектория будет выбрана в рамках схемы выборки результатов.

[058] Как показано на вспомогательном рисунке C, схема 206 надежной выборки случайным образом выбирает k ветвей в соответствии с равномерным распределением для игрока 0 и выполняет случайную выборку в одной ветви для узла не игрока 0, в соответствии с соответствующей стратегией выборки. Изменяя значение k, схема надежной выборки может выбирать несколько путей или, например, один путь, в зависимости от фактических потребностей памяти или спецификации системы. В отличие от схемы внешней выборки, схема надежной выборки не требует знания всех возможных действий и переменных в точке принятия решения текущего игрока i' каждый раз.

[059] В некоторых вариантах осуществления в схемах внешней выборки и выборки результатов каждый блок Q_j

Q представляет раздел Z. Определить как вероятность рассмотрения блока Q_j, где . Определить как вероятность рассмотрения конкретной истории терминала z. В некоторых вариантах осуществления пустой CFR можно рассматривать как частный случай MCCFR, где Q = {Z} содержит только один блок и qQ1=1.

[060] В схеме выборки результатов будет выбрана только одна траектория, такая, что ∀Qj

Q, | Qj | = 1 и | Qj | = | Z |. Для набора Ii информации выборочная оценка контрфактивного значения имеет вид z).

[061] Доказано, что контрфактивное значение выборки в MCCFR является объективной оценкой фактического контрфактивного значения в CFR:

.

[062] Определить σ^rsкакпрофиль стратегии выборки, где σ_i^rs - стратегия выборки дляигрока i, а

- стратегии выборки для игроков кроме игрока i. В некоторых вариантах осуществления как для внешней, так и для выборки результатов . Сожаление о выбранном действии a A (Ii) может быть определено как:

,(6)

где

- новая функция полезности, взвешенная посредством . Выборочная оценка для совокупного сожаления о действии a после T итераций может быть определена как

с .

[063] Для надежной выборки профиль выборки может быть определен как

, где игрок i может случайным образом выбрать k действий в соответствии со стратегией (Ii) для каждого набора Ii информации, а другие игроки могут случайным образом выбрать одно действие в соответствии состратегией σ_−i.

[064] В некоторых вариантах осуществления, если игрок i случайным образом выбирает min(k,|A(I_i)|) действия в соответствии с дискретным равномерным распределением unif(0,|A(I_i)|) в наборе

информации. То есть , тогда вероятность достижения набора Ii информации, если игрок i предпринимает действия в соответствии со стратегией выборки или профилем , может быть вычислена по формуле:

и взвешенная функция полезности

может быть постоянным числом в каждой итерации, учитывая профиль σ^rs(k) выборки, который имеет низкую вариативность. Кроме того, поскольку взвешенная функция полезности больше не требует явного знания стратегии оппонента, надежная выборка можетиспользоваться для минимизации сожалений онлайн.

[065] Чтобы упростить обозначения, пусть k=max относится к k = max_Ii∈I|A(I_i)|. Если k₌max и игрок i случайным образом выбирает k действий в соответствии с дискретным равномерным распределением unif(0,|A(I_i)|) на наборе Ii информации, I_i,

, то надежная выборка может быть аналогична внешней выборке, когда k = max_Ii∈I|A(I_i)|.

[066] Если k=1 и

, в этом случае отбирается только одна история z, тогда , ∃h I_i, для a A^rs(k)(I_i),

[067] Если действие a не выбрано в состоянии h, то есть a

A^rs(k)(I_i), сожаление представляет собой . В этом случае надежная выборка аналогична выборке результатов, когда k=1 и .

[068] Если k=1, и игрок i случайным образом выбирает одно действие в соответствии с дискретным равномерным распределением unif(0,|A(I_i)|) в информационном наборе I_i,.Тогда надежная выборка может быть аналогична выборке результатов. Например, если k=1, и игрок i случайным образом выбирает одно действие в соответствии с дискретным равномерным распределением unif(0,|A(I_i)|) в наборе Ii информации, то

является постоянной, ∃h I_i, для a A^rs(k)(I_i),

).

[069] Если действие a не выбрано в состоянии h, то есть a

A^rs(k)(I_i), сожаление равно . По сравнению с выборкой результатов, надежная выборка в этом случае имеет меньшую вариативность из-за постоянной .

[070] Фиг. 3 - псевдокод 300 примера надежной выборки MCCFR в соответствии с вариантами осуществления этого описания. Как показано в строках 1-5 псевдокода 300, общая надежная выборка MCCFR является итеративным алгоритмом с вводом общего числа итераций, t. В каждой итерации t для игрока 0 и игрока 1 (как показано в строках 3 и 4) вызывается функция надежной выборки MCCFR (RS-MCCFR), чтобы обновить совокупное сожаление

и числитель средней стратегии. Функция RS-MCCFR может быть определена, как показано в строках 6-30 псевдокода 300. Функция RS-MCCFR возвращает контрфактивное значение каждого набора информации, установленного в качестве вывода. В некоторых вариантах осуществления контрфактивное значение может использоваться для вычисления контрфактивного сожаления. Таким образом, совокупное сожаление и средняя по времени стратегия могут быть получены соответствующим образом.

[071] В частности, функция RS-MCCFR осуществляет выборку действий в соответствии со схемой надежной выборки, как описано выше в связи с фиг. 2. Как показано в строке 16 псевдокода 300, k различных действий могут быть выбраны и собраны как A^rs(k)(I_i) в соответствиисо стратегией

надежной выборки

[072] В некоторых вариантах осуществления схема зависимой от глубины выборки может использоваться для предоставления более сбалансированной или подробной информации об игре, представленной игровым деревом. Например, стратегия

выборки может быть функцией глубины состояния h в дереве игры. Например, стратегия выборки может быть спроектирована таким образом, чтобы состояние, более близкое к состоянию терминала, имело более высокую вероятность быть выбранным, чем состояние, близкое к начальному состоянию (например, представленное корнем дерева игры). В качестве примера, схема зависимой от глубины выборки, может быть реализована путем применения разных весовых коэффициентов к вероятностям выборки разных состояний с различной глубиной. Такая зависимая от глубины выборка может помочь предоставить больше информации о состояниях, более близких к состояниям терминала, что может быть полезным, поскольку обычно имеется больше состояний, более близких к состояниям терминала, чем состояний, которые ближе к начальному состоянию (например, из-за структуры разветвления дерева игры), и эти узлы имеют меньшую вероятность выборки, чем узлы, расположенные ближе к корневому узлу в выбранных траекториях при существующих схемах выборки.

[073] В некоторых вариантах осуществления схема зависимой от глубины выборки может использоваться в сочетании с надежной выборкой, выборкой результатов, внешней выборкой или любыми другими подходящими алгоритмами выборки. Например, схема зависимой от глубины выборки может дополнительно улучшить вариативность и скорость сходимости любой из надежной выборки, выборки результатов и внешней выборки, поскольку последние три схемы выборки больше фокусируются на горизонтальной выборке среди различных действий состояния игрока (например, представленной различными ветвями узла дерева игры).

[074] Фиг.4 - схема, иллюстрирующая пример 400 алгоритма двойной нейронной CFR, применяемого к дереву 410 игры в соответствии с вариантами осуществления этого описания. Алгоритм 400 двойной нейронной CFR использует две нейронные сети 420 и 430 для вычисления приблизительного равновесия по Нэшу IIG, такого как представлено деревом 410 игры. Как показано на фиг. 4, одна нейронная сеть 420 используется для получения совокупного сожаления и называется RegretSumNetwork (RSN). Другие нейронные сети 430 используются для получения средней стратегии и называются AveStrategyNetwork (ASN).

[075] В некоторых вариантах осуществления итеративные обновления алгоритма CFR поддерживают две стратегии: текущую стратегию σ_i^t(a|I_i), и среднюю стратегию

для ∀ ∀i N, ∀I_i I_i, ∀a A(I_i), ∀t {1,...,T}. Соответственно, нейронные сети 420 и 430 могут быть предназначены для записи этих двух стратегий итеративным образом. В некоторых вариантах осуществления пример 400 алгоритма двойной нейронной CFR можно отнести к алгоритму двойного инкрементного CFR, поскольку нейронные сети обучаются или оптимизируются на основе новых дополнительных выборок в каждой итерации.

[076] Согласно уравнению (3) текущая стратегия σ^t+1(a|I_i) может быть вычислена с помощью совокупного сожаления R^t(a|I_i). В некоторых вариантах осуществления только числитель в уравнении (3) отслеживается, поскольку нормализация в знаменателе может быть легко вычислена при использовании этой стратегии. При заданном наборе Ii информации и действии a нейронная сеть RSN 420, обозначаемая как

, может использоваться для изучения R^t(a|I_i), , где - параметр в RSN 420 при t-й итерации.

[077] Как показано на фиг. 4, память

может быть определена как = {(I_i,r˜_i^σt((a|I_i)|Q_j))|∀i N, ∀a A(I_i), h I_i, h v z, z Q_j}. Каждый член может включать в себя посещенный набор Ii информации и соответствующее сожаление , где Qj - выбранный блок в t-й итерации. Согласно уравнению (2) можно оценить с использованием следующей оптимизации:

,(7)

Согласно уравнению (4) приближенное равновесие по Нэшу является средневзвешенным значением всех предыдущих стратегий за T итераций. Подобно кумулятивному сожалению, другая нейронная сеть ASN 430, обозначенная как

, может использоваться для изучения числителя средней стратегии. Определить другую память как

.

Каждый член

может включать в себя посещенный набор Ii информации и значение π_i^σt(I_i)σ_i^t(a|I_i)_,где Q_jвыбранный блок в t_-й итерации. Тогда параметр для ASN 430 может быть оценен по следующей формуле:

, (8)

[078] В некоторых вариантах осуществления в каждой итерации как

, так и могут быть оптимизированы путем оптимизации целевой функции в уравнении (7) и уравнении (8) в соответствии со способом градиентного спуска, таким как способ мини-пакетного стохастического градиентного спуска, описанный со ссылкой на фиг. 7 ниже.

[079] В некоторых вариантах осуществления средняя стратегия не требует обновления в каждой итерации, если доступна большая память для агрегирования и сохранения

в течение множественных итераций. Если память заполнена, инкрементное значение можно узнать путем оптимизации уравнения (8).

[080] В некоторых вариантах осуществления в каждой итерации отбирается только небольшой поднабор наборов информации, что может привести к тому, что нейронные сети RSN 420 и ASN 430 забудут значения этих ненаблюдаемых или невыбранных наборов информации. Чтобы решить эту проблему, параметры нейронной сети из предыдущей итерации могут использоваться как инициализация текущей итерации, которая дает обновлениям онлайн-обучение/адаптацию. Кроме того, благодаря обобщающей способности нейронных сетей даже выборки из небольшого числа наборов информации могут использоваться для обновления новых нейронных сетей, а недавно обновленные нейронные сети могут давать хорошие значения для совокупного сожаления и средней стратегии в некоторых вариантах осуществления.

[081] В некоторых вариантах осуществления по мере увеличения числа итераций t значение R_i^t(a|I_i) может становитьсявсе более большим, что потенциально затрудняет обучение нейронной сети. Чтобы решить эту проблему, совокупное сожаление можно нормализовать с коэффициентом

чтобы сделать его диапазон более стабильным. Это можно понять из границы сожаления онлайн-обучения. Более конкретно, пусть ∆ = max_Ii,a,t|R^t(a|I_i) − R^t−1(a|I_i)|,∀I_i I,a A(I_i),t {1,...,T}. , где |A| = max_Ii∈I|A(I_i)|. В некоторых вариантах осуществления нейронная сеть RSN 420 может использоваться для отслеживания и обновления его с помощью

, (9)

где R^ˆ_i⁰(a|I_i) = 0.

[082] В некоторых вариантах осуществления в алгоритме двойного инкрементного CFR памяти

и могут очищаться после каждой итерации, например, из-за ограниченного размера памяти MRt и MSt. В некоторых вариантах осуществления для примера в большой игре, даже с алгоритмом двойного инкрементального CFR, который использует нейронные сети, чтобы узнать совокупные сожаления и среднюю стратегию, размер памяти и , возможно, все еще должен быть очень большим для записи совокупного сожаления и средних стратегий для каждой итерации.

[083] В некоторых вариантах осуществления, чтобы постоянно улучшать среднюю стратегию с ограниченной памятью, но бесконечными итерациями и/или для дополнительного снижения требования к объему памяти, можно использовать алгоритм CFR с двумя накопителями, который использует два накопителя M_Rи M_Sдля сохранения отобранных совокупных сожалений, а также усредненных стратегий на разных итерациях, и динамическое изучение совокупного сожаления и средней стратегии.

[084] В некоторых вариантах осуществления среднее совокупное сожаление после T итераций может быть получено согласно уравнению (10), переписав уравнение (2):

(10)

[085] Аналогично средняя стратегия может быть нормализацией совокупной стратегии, как показано в уравнении (4), которая является средневзвешенной стратегией

по ее вероятности достижения.

[086] В некоторых вариантах осуществления два однородных накопителя M_Rи M_S могут использоваться длясохранения выбранного

и , соответственно. В частности, M_R может быть накопителем для сохранения выборок в , и M_Sможет быть накопителем для сохранения выборок в . Новые выборки могут бытьвставлены в накопитель по алгоритму выборки накопителя. Выборка накопителя включает в себя семейство рандомизированных алгоритмов для случайного выбора k элементов из списка, содержащего n элементов. Например, если накопитель не заполнен, новые выборки могут быть добавлены непосредственно в накопитель. Если накопитель заполнен, новые выборки могут заменить старые выборки в соответствии, например, с принципом «первым пришел - первым обслужен» (FIFO) или в соответствии с равномерным случайным распределением или другим распределением.

[087] Следует обратить внимание, что как алгоритм двойного инкрементального CFR, так и алгоритм CFR с двойным накопителем используют идеи в онлайн-обучении и используют две нейронные сети для изучения обновления стратегии сожаления и средней стратегии, соответственно. В некоторых вариантах осуществления ASN не нужно обновлять на каждой итерации, в то время как RSN, возможно, необходимо оптимизировать после выборки по методу Монте-Карло, чтобы создать новую стратегию поведения. Например, когда для прохождения дерева игры используется новая стратегия поведения, RSN может потребоваться обновлять каждую итерацию. С другой стороны, ASN может использоваться в качестве окончательного приближенного равновесия по Нэшу, которое является средневзвешенным значением стратегии поведения. ASN может служить выходным значением алгоритма двойной нейронной CFR. Если имеется достаточно большое хранилище данных для сохранения всех выборок, необходимо только оптимизировать среднюю стратегию на последнем шаге. На практике для большой игры большое хранилище данных может быть очень дорогим. Таким образом, средняя стратегия может быть постепенно оптимизирована, если хранилище данных (например, накопитель

) заполнено. Таким образом, алгоритм двойной нейронной CFR может включать в себя два варианта. В алгоритме двойного инкремента нейронная сеть (например, одна или обе RSN и ASN) оптимизируется только с помощью инкрементальных выборок, в то время как при алгоритме с двойным накопителем нейронная сеть (например, одна или обе RSN и ASN) может быть оптимизирована с помощью всех выборок в накопителях.

[088] Алгоритм двойной нейронной CFR и алгоритм CFR с двойным накопителем имеют разные коллекции выборок. Для двойного инкрементального CFR нейронная сеть оптимизируется на основе вновь добавленных выборок. Для CFR с двойным накопителем нейронная сеть оптимизируется на основе выборок в накопителях фиксированного размера. Кроме того, в способе с двойным накопителем средняя стратегия может быть оптимизирована по максимальному логарифмическому правдоподобию, а не по минимальной квадратичной ошибке.

[089] Фиг. 5 - псевдокод 500 примера алгоритма двойной нейронной CFR в соответствии с вариантами осуществления этого описания. Пример алгоритма двойной нейронной CFR включает в себя возможность использования алгоритма двойной нейронной CFR или алгоритма с двойным накопителем.

[090] Строки 3-7 псевдокода 500 показывают примеры стратегий инициализации в первой итерации. Например, если прогрев системы начинается с существующего способа CFR (например, способов табличного CFR или MCCFR или способа двойной нейронной CFR), нейронные сети могут быть инициализированы из существующего профиля стратегии для клонирования совокупных сожалений и стратегии. Если инициализация горячего старта отсутствует, алгоритм двойной нейронной CFR может запускаться путем случайной инициализации параметров в RSN и ASN на итерации t=1.

[091] В некоторых вариантах осуществления, если используется алгоритм CFR с двойным накопителем, как показано в строке 8 псевдокода 500, могут использоваться способы выборки, которые возвращают контрфактивное сожаление и числитель средней стратегии для выбранных наборов информации в этой итерации. Контрфактивное сожаление и числитель средней стратегии для выбранных наборов информации в этой итерации могут быть сохранены в памяти

и соответственно. Способы выборки могут включать в себя, например, алгоритм способа мини-пакетной надежной выборки, описанный со ссылкой на фиг. 7. В некоторых вариантах осуществления контрфактивные сожаления для выбранных наборов информации в этой итерации могут суммироваться, чтобы обеспечить совокупное значение в наборах информации, например, согласно уравнению (11) ниже и алгоритму мини-пакетной MCCFR, как описано со ссылкой на фиг. 7. В некоторых вариантах осуществления дублированные записи в могут быть удалены.

[092] В некоторых вариантах осуществления, если используется алгоритм CFR с двойным накопителем, можно сохранить контрфактивное сожаление и числитель средней стратегии для выбранных наборов информации в этой итерации (например, сохраненных в памяти

и в алгоритме двойного инкрементного CFR) в накопителях M_Rи M_S соответственно_.Выборку накопителей можно использовать, если один или оба накопителяM_RиM_S заполнены.

[093] Как показано в строках 13-15 псевдокода 500, эти контрфактивные сожаления и числитель средней стратегии для выбранных наборов информации в этой итерации могут использоваться алгоритмом NeuralAgent, как показано на фиг. 6, чтобы оптимизировать две нейронные сети RSN и ASN и возвратить параметры (например,

и ) для RSN и ASN (например, и ).

[094] Фиг.6 - псевдокод 600 примера алгоритма для оптимизации нейронной сети в связи с алгоритмом двойной нейронной CFR в соответствии с вариантами осуществления этого описания. Пример алгоритма называется алгоритмом NeuralAgent. Описанный алгоритм двойной нейронной CFR может использовать другие алгоритмы для оптимизации одной или обеих нейронных сетей, используемых в алгоритме двойной нейронной CFR.

[095] Определить βepoch как обучающий отчетный временной период, βlr как скорость обучения, βloss как критерии ранней остановки или завершения, βre как верхнюю границу для числа итераций от получения минимальных потерь в прошлый раз, θ^t−1в качестве параметра для оптимизации^,f(·|θ^t−1) в качестве нейронной сети, Mв качестве обучающей выборки, состоящей из набора информации и соответствующей цели. Чтобы упростить обозначения, используется β*для обозначения набора параметров нейронной сети. Например,

и β_S*относятся к наборам параметров в RSN и ASN соответственно. Эксперименты показывают, что тщательно разработанный алгоритм NeuralAgent может обеспечить относительно более высокую скорость сходимости для использования при оптимизации нейронных сетей RSN и ASN. Псевдокод 600 показывает подробности алгоритма NeuralAgent с пояснительными комментариями.

[096] В некоторых вариантах осуществления существующие оптимизаторы могут не возвращать относительно низкие потери из-за потенциальной седловой точки или локальных минимумов. Чтобы получить относительно более высокую точность и меньшие потери при оптимизации, планировщик специально разработан для уменьшения скорости обучения, когда потеря перестала уменьшаться. В частности, планировщик считывает величину метрики, например среднеквадратичную ошибку, и, если улучшение не наблюдается в течение ряда отчетных временных периодов, скорость обучения уменьшается на некоторый коэффициент. Кроме того, скорость обучения может быть сброшена как в оптимизаторе, так и в планировщике, как только потери прекращаются в β_reотчетных временных периодах. Механизм ограничения градиента может использоваться для ограничения величины градиента параметра и улучшения поведения оптимизатора вблизи крутых порогов. После каждого отчетного временного периода лучший параметр будет обновляться. Механизм ранней остановки используется, когда наименьшая потеря меньше заданного критерия β_loss потери.

[097] В экспериментах гиперпараметры нейронной сети могут быть установлены следующим образом. Например, для RSN размер нейронного пакета равен 256, а скорость обучения β_lr= 0,001. Планировщик, который снизит скорость обучения на основе количества отчетных временных периодов и скорости сходимости потерь, поможет нейронному агенту получить высокую точность. Скорость обучения может быть уменьшена на 0,5, когда потери перестают улучшаться после 10 отчетных временных периодов. Нижняя граница скорости обучения всех параметров в этом планировщике составляет 10⁻⁶. Чтобы избежать схождения алгоритма к потенциальным локальным минимумам или седловой точке, скорость обучения может быть сброшена, например, до 0,001 и помочь оптимизатору обучиться лучшей производительности_.^θ_best^T-лучшие параметры для достижения наименьших потерь после T отчетных временных периодов. Если средняя потеря для отчетного временного периода t меньше указанного критерияβ_loss=10⁻⁴, оптимизатор может иметь раннюю остановку. В качестве примера следует установить β_epoch= 2000 и обновить оптимизатор 2000 максимальных отчетных временных периодов.

[098] Для ASN критерии ранней остановки могут быть установлены как 10-⁵.Скорость обучения может быть уменьшена на 0,7, когда потери перестают улучшаться после 15 отчетных временных периодов. Другие гиперпараметры в ASN могут быть аналогичны таковым в RSN.

[099] Фиг.7 - псевдокод 700 примера алгоритма мини-пакетной MCCFR в соответствии с вариантами осуществления этого описания. Алгоритм мини-пакетной MCCFR (обозначается как Mini-Batch-MCCFR-NN) включает в себя алгоритм выборки для получения контрфактивного сожаления и числителя средней стратегии для выбранных наборов информации игры. В отличие от традиционной выборки результатов и внешней выборки, которые отбирают только один блок в итерации и обеспечивают несмещенную оценку исходного CFV, метод мини-пакетной выборки может случайным образом выбирать b блоков за одну итерацию. Пример алгоритма мини-пакетной MCCFR, показанный в псевдокоде 700, основан на надежной выборке, описанной выше. В некоторых вариантах осуществления алгоритм мини-пакетной MCCFR может использоваться в связи с другими схемами выборки, такими как схема зависимой от глубины выборки. Следует обратить внимание, что алгоритм мини-пакетной MCCFR является примером алгоритма получения контрфактивного сожаления и числителя средней стратегии для выбранных наборов информации игры. Алгоритм двойной нейронной CFR может использовать другие алгоритмы для получения контрфактивного сожаления и числителя средней стратегии для выбранных наборов информации игры.

[0100] Пусть Q^j обозначаетблок терминалов, выбранных в соответствии с схемой надежной выборки в j-й момент времени, тогда мини-пакет CFV с b мини-пакетами для набора I_i информации может быть определен как:

(11).

[0101] Кроме того, можно показать, что v˜_i^σ(I_i|b) является непредвзятой оценкой контрфактивного значения I_i: E_{Qj∼Robust Sampling}[v˜_i^σ(I_i|b)] = v_i^σ(I_i).

[0102] Аналогично совокупное мини-пакетное сожаление действия a

, (12)

где R^˜_i⁰((a|I_i)|b) = 0В некоторых вариантах осуществления мини-пакетная MCCFR может выполнять выборку b блоков параллельно и помогать MCCFR быстрее сходиться.

[0103] Следует обратить внимание, что мини-пакетная MCCFR использует алгоритм сопоставления сожалений для обновления накопленного мини-пакетного сожаления R^˜T,+((a|I_i)|b)_.В некоторых вариантах осуществления в качестве варианта мини-пакетного MCCFR алгоритм мини-пакетной MCCFR+ может использоваться для обновления совокупного мини-пакетного сожаления R^˜T,+((a|I_i)|b) до итерации T посредством:

(13)

где (x)⁺= max(x,0). В некоторых вариантах осуществления обнаружено, что мини-пакетная MCCFR+ сходится быстрее, чем мини-пакетная MCCFR, при указании подходящего размера мини-пакета.

[0104] Функция Mini-Batch-MCCFR-NN, показанная в псевдокоде 700, представляет метод мини-пакетной выборки, где b-блоки будут дискретизироваться (выбираться) параллельно. Этот мини-пакетный способ может помочь MCCFR достичь более точной оценки CFV. Параллельная выборка делает этот способ эффективным на практике.

[0105] Как показано в строках 1-6 псевдокода 700, Mini-Batch-MCCFR-NN является итеративным алгоритмом с вводом общего количества итераций, t. В пределах каждой итерации для игрока 0 и игрока 1 вызывается функция MCCFR-NN (как показано в строках 4 и 5), а контрфактивное сожаление и числитель средней стратегии для выбранных наборов информации в этой итерации возвращаются и сохраняются в памяти

и соответственно.

[0106] Функция MCCFR-NN может быть определена, как показано в строках 8-33 псевдокода 700. Функция MCCFR-NN проходит по дереву игры подобно табличной MCCFR, которая начинается с истории h = ∅ корня. Определить Ii как набор информации для h. Предположим, что игрок i выберет k действий в соответствии с надежной выборкой. Тогда функция может быть определена следующим образом. (1) Если история является терминальной (например, h

Z), функция возвращает взвешенную полезность. (2) Если история является случайным игроком (например, P(I_i) = -1), одно действие a A(Ii) может быть выбрано в соответствии со стратегией σ_−i(I_i). Тогда это действие будет добавлено в историю, т.е. h ← ha. (3) Если P(Ii) = i_,текущая стратегия может быть обновлена с помощью совокупного сожаления, прогнозированного RSN. Затем выполните выборку k действий в соответствии с заданным профилем стратегии выборки (например, надежная выборка с зависимой от глубины выборкой, или без нее). После рекурсивного обновления можно получить контрфактивное значение и сожаление для каждого действия в Ii. Для посещенного узла их контрфактивные сожаления и числители соответствующей средней стратегией могут быть сохранены в и соответственно. (4) Если P(Ii) является оппонентом, будет выбрано только одно действие в соответствии со стратегией σ_−i(I_i).

[0107] Фиг.8 - блок-схема последовательности операций примера процесса 800 выборки для выполнения MCCFR в соответствии с вариантами осуществления этого описания. Процесс 800 выборки может быть примером схемы зависимой от глубины выборки, описанной выше, для выполнения минимизации контрфактивного сожаления (CFR) для поиска стратегии в стратегическом взаимодействии между двумя или более сторонами. В некоторых вариантах осуществления стратегическое взаимодействие между двумя или более игроками может быть смоделировано с помощью несовершенной информационной игры (IIG), в которой участвуют два или более игроков. IIG может представлять один или несколько реальных сценариев, таких как распределение ресурсов, рекомендации по продукту/услуге, прогнозирование и/или предотвращение кибератак, маршрутизация трафика, администрирование мошенничества и т. д., в которых участвуют две или более сторон, где каждая сторона может иметь неполную или несовершенную информацию о решениях другой стороны. В качестве примера, IIG может представлять собой совместную услугу рекомендации по продукту-услуге, которая включает, по меньшей мере, первого игрока и второго игрока. Первым игроком может быть, например, интернет-магазин, который имеет информацию о клиенте (или пользователе), информацию о продукте и услуге, историю покупок клиентов и т. д. Вторым игроком может быть, например, платформа социальной сети, которая имеет данные социальных сетей клиентов, банк или другое конечное учреждение, которое имеет финансовую информацию о клиентах, автосалон или любые другие стороны, которые могут иметь информацию о клиентах в отношении предпочтений клиентов, потребностях, финансовом положении, местонахождении и т. д. в прогнозировании и рекомендации продуктов и услуг для клиентов. Первый игрок и второй игрок могут каждый иметь собственные данные, которыми не хотят делиться с другими. Второй игрок может предоставлять только частичную информацию первому игроку в разное время. Таким образом, первый игрок может иметь только ограниченный доступ к информации второго игрока. Для удобства процесс 800 будет описан как выполняемый устройством обработки данных, таким как система из одного или нескольких компьютеров, расположенных в одном или нескольких местах и запрограммированных соответствующим образом в соответствии с этим описанием. Например, компьютерная система 1000 на фиг. 10, соответствующим образом запрограммированная, может выполнять процесс 800.

[0108] На этапе 810 устройство обработки данных идентифицирует N1 возможных действий первого игрока в первом состоянии первого игрока. В некоторых вариантах осуществления IIG может быть представлена деревом игры (например, деревом 102, 104, 202, 204 или 206 игры). Первое состояние первого игрока может быть представлено первым узлом дерева игры (например, узлом h1 игрока 0 в дереве 102 игры), и возможным действием N1 могут быть ребра или ветви первого узла дерева игры (например, P и B ребра узла h1 игрока 0 в дереве 102 игры). В примере службы рекомендаций по совместному продукту-услуге первое состояние первого игрока включает в себя историю информации, предоставленной вторым игроком, и N1 возможных действий первого игрока включает в себя N1 возможных действий в ответ на историю информации, предоставляемой вторым игроком для предоставления клиентам рекомендаций по продукту-услуге. Первое состояние первого игрока и возможные действия могут включать в себя другие функции в других реальных сценариях, которые моделируются IIG.

[0109] На этапе 820 устройство обработки данных выбирает возможное действие из N1 возможных действий в первом состоянии первого игрока с первой вероятностью выборки. В некоторых вариантах осуществления устройство обработки данных может выбирать k1 возможных действий из N1 возможных действий в первом состоянии первого игрока, причем каждое из k1 возможных действий выбирается с аналогичной первой вероятностью выборки.

[0110] На этапе 830 устройство обработки данных идентифицирует N2 возможных действий первого игрока во втором состоянии первого игрока, причем первое состояние первого игрока ближе к начальному состоянию IIG, чем второе состояние первого игрока. В примере дерева 102 игры вторым состоянием первого игрока может быть, например, узел h7, который находится дальше от начального состояния (например, узла h0) дерева 102 игры, чем первое состояние первого игрока (например, узел h1 игрока 0 в дереве 102 игры).

[0111] На этапе 840 устройство обработки данных выбирает возможное действие из N2 возможных действий во втором состоянии первого игрока со второй вероятностью выборки, причем первая вероятность выборки меньше, чем вторая вероятность выборки. В некоторых вариантах осуществления устройство обработки данных выбирает k2 возможных действий из N2 возможных действий во втором состоянии первого игрока, причем каждое из k2 возможных действий выбирается с аналогичной второй вероятностью выборки.

[0112] На этапе 850 устройство обработки данных выполняет CFR на основе возможных действий из N1 возможных действий в первом состоянии первого игрока и возможного действия из N2 возможных действий во втором состоянии первого игрока. В некоторых вариантах осуществления CFR может выполняться согласно примерным методикам, описанным со ссылкой на фиг. 3 и/или фиг. 7.

[0113] В некоторых вариантах осуществления выводится стратегия первого игрока, полученная в результате решения IIG. Стратегия может включать в себя серию действий первого игрока в реальном сценарии, смоделированном IIG. Например, в сценарии совместной рекомендации продукта-услуги стратегия первого игрока, полученная в результате решения IIG, может включать в себя, например, серию действий в ответ на информацию, предоставленную вторым игроком, соответствующие рекомендации продукта-услуги клиентам на основе информации первого игрока и информации, предоставленной вторым игроком. Выходная стратегия первого игрока, полученная в результате решения IIG, может включать в себя другую информацию в других реальных сценариях, которые моделируются IIG.

[0114] В некоторых вариантах осуществления выполнение CFR на основе возможного действия из N1 возможных действий в первом состоянии первого игрока и возможного действия из N2 возможных действий во втором состоянии первого игрока включает в себя вычисление значения сожаления возможного действия из N1 возможных действий в первом состоянии первого игрока (например, согласно уравнению (1a) и/или уравнению (2)); вычисление значения сожаления возможного действии из N2 возможных действий во втором состоянии первого игрока (например, согласно уравнению (1a) и/или уравнению (2)); обновление первой стратегии первого игрока в первом состоянии на основе значения сожаления возможного действия из N1 возможных действий (например, в соответствии с уравнением (3)); и обновление второй стратегии первого игрока во втором состоянии на основе значения сожаления возможного действии из N2 возможных действий (например, согласно уравнению (3)).

[0115] В некоторых вариантах осуществления устройство обработки данных выполняет CFR на основе k1 возможных действий из N1 возможных действий в первом состоянии первого игрока и k2 возможных действий из N2 возможных действий во втором состоянии первого игрока.

[0116] В некоторых вариантах осуществления надежная выборка может быть выполнена в связи с зависимой от глубины выборкой. Например, первая вероятность выборки равна k1/N1, а вторая вероятность выборки равна k2/N2. Таким образом, возможные действия выбираются в соответствии с равномерным распределением.

[0117] В некоторых вариантах осуществления 2<= k1<= N1 и 2<= k2 <= N2, так что посещается более одного возможного действия для каждого состояния игрока.

[0118] В некоторых вариантах осуществления k1=k2, поэтому одинаковое количество выборок выбирается или посещается в первом состоянии и во втором состоянии первого игрока.

[0119] Аналогично, зависимая от глубины выборка может быть выполнена в связи со вторым игроком. Например, устройство обработки данных идентифицирует M1 возможных действий второго игрока в первом состоянии второго игрока. Устройство обработки данных выбирает возможное действие из M1 возможных действий в первом состоянии второго игрока с третьей вероятностью выборки. Устройство обработки данных идентифицирует M2 возможных действий второго игрока во втором состоянии второго игрока, при этом первое состояние второго игрока ближе к начальному состоянию IIG, чем второе состояние второго игрока. Устройство обработки данных выбирает возможное действие из M2 возможных действий во втором состоянии первого игрока с четвертой вероятностью выборки, причем третья вероятность выборки меньше, чем четвертая вероятность выборки.

[0120] В некоторых вариантах осуществления зависимая от глубины выборка может выполняться в связи как с первым игроком, так и со вторым игроком. В некоторых вариантах осуществления устройство обработки данных идентифицирует M1 возможных действий второго игрока в первом состоянии второго игрока, причем первое состояние первого игрока (например, состояние h1 игрока 0 в дереве 102 игры) ближе к начальному состоянию (например, состоянию h0) IIG, чем первое состояние второго игрока (например, состояние h4 игрока 1 в дереве 102 игры). Устройство обработки данных осуществляет выборку возможного действия из M1 возможных действий в первом состоянии второго игрока с третьей вероятностью выборки, причем третья вероятность выборки больше, чем первая вероятность выборки.

[0121] Фиг.9 - блок-схема последовательности операций примера алгоритма 900 двойной нейронной CFR для выполнения MCCFR в соответствии с вариантами осуществления этого описания. Процесс 900 выборки может быть примером алгоритма CFR с двойным накопителем, описанного выше со ссылкой на фиг. 4-7 для выполнения минимизации контрфактивного сожаления (CFR) для поиска стратегии в стратегическом взаимодействии между двумя или более игроками. В некоторых вариантах осуществления стратегическое взаимодействие между двумя или более игроками может быть смоделировано с помощью несовершенной информационной игры (IIG), в которой участвуют два или более игроков. IIG может представлять один или несколько реальных сценариев, таких как распределение ресурсов, рекомендация по продукту/услуге, прогнозирование и/или предотвращение кибератак, маршрутизация трафика, администрирование мошенничества и т. д., в которых участвуют две или более сторон, где каждая сторона может иметь неполную или несовершенную информацию о решениях другой стороны. В качестве примера, IIG может представлять собой совместную услугу рекомендации по продукту-услуге, которая включает, по меньшей мере, первого игрока и второго игрока. Первым игроком может быть, например, интернет-магазин, который имеет информацию о клиенте (или пользователе), информацию о продукте и услуге, историю покупок клиентов и т. д. Вторым игроком может быть, например, платформа социальной сети, которая имеет данные социальных сетей клиентов, банк или другое конечное учреждение, которое имеет финансовую информацию о клиентах, автосалон или любые другие стороны, которые могут иметь информацию о клиентах относительно предпочтений клиентов, потребностях, финансовом положении, местонахождении и т. д. в прогнозировании и рекомендации продуктов и услуг для клиентов. Первый игрок и второй игрок каждый могут иметь собственные данные, которыми не хотят делиться с другими. Второй игрок может предоставлять только частичную информацию первому игроку в разное время. Таким образом, первый игрок может иметь только ограниченный доступ к информации второго игрока. Для удобства процесс 900 будет описан как выполняемый устройством обработки данных, таким как система из одного или нескольких компьютеров, расположенных в одном или нескольких местах и запрограммированных соответствующим образом в соответствии с этим описанием. Например, компьютерная система 1000 на фиг. 10, соответствующим образом запрограммированная, может выполнять процесс 900.

[0122] На этапе 910 устройство обработки данных инициализирует параметры первой нейронной сети и параметры второй нейронной сети. Первая нейронная сеть (например, RegretSumNetwork (RSN) 420) может использоваться для прогнозирования значения сожаления возможного действия в состоянии игрока. В примере службы рекомендаций по совместному продукту-услуге состояние игрока включает в себя историю информации, предоставленной вторым игроком, и возможное действие игрока включает в себя возможное действие в ответ на историю информации, предоставленной вторым игроком для предоставления рекомендаций по продукту-услуге для клиентов. Вторая нейронная сеть (например, AveStrategyNetwork (ASN) 430) может использоваться для прогнозирования значения стратегии возможного действия в состоянии игрока. В некоторых вариантах осуществления устройство обработки данных инициализирует параметры в соответствии с горячим стартом, например, на основе параметров первой нейронной сети и параметров второй нейронной сети в предыдущей итерации или полученных на основе существующего алгоритма CFR, соответственно. В некоторых вариантах осуществления устройство обработки данных инициализирует параметры первой нейронной сети и параметры второй нейронной сети случайным образом.

[0123] На этапе 920 устройство обработки данных сохраняет некоторое количество выборок сожаления в первом хранилище данных (например, в накопителеM_R), причем каждая из количества выборок сожаления включает в себя состояние игрока и значение сожаления возможного действия в состоянии игрока. В некоторых вариантах осуществления значение сожаления возможного действия в состоянии игрока включает в себя контрфактивное значение сожаления возможного действия в состоянии игрока, вычисленное на основе контрфактивного значения возможного действия в состоянии игрока. Например, каждая выборка сожаления может включать в себя кортеж сожаления (I_i, r˜_i^σt(a|I_i)). В некоторых вариантахосуществления количество выборок сожаления получают в двух или более итерациях алгоритма минимизации контрфактивного сожаления (CFR) при поиске стратегии при стратегическом взаимодействии между игроком и, по меньшей мере, другим игроком. В некоторых вариантах осуществления алгоритм CFR включает в себя алгоритм CFR с надежной выборкой.

[0124] В некоторых вариантах осуществления в каждой из двух или более итераций алгоритма CFR при решении IIG устройство обработки данных выбирает возможное действие из некоторого количества возможных действий во втором состоянии игрока в соответствии со схемой выборки; вычисляет контрфактивное значение возможного действия во втором состоянии игрока (например, согласно уравнению (1)); вычисляет значение сожаления возможного действия во втором состоянии игрока на основе контрфактивного значения возможного действия во втором состоянии игрока (например, согласно уравнению (1a) и/или уравнению (2)); вычисляет обновленную стратегию возможного действия во втором состоянии игрока на основе значения сожаления возможного действия во втором состоянии игрока в соответствии с алгоритмом сопоставления сожаления (например, в соответствии с уравнением (3)); и вычисляет значение стратегии возможного действия во втором состоянии игрока на основе обновленной стратегии возможного действия во втором состоянии игрока (например, согласно уравнению (4) и/или уравнению (5)).

[0125] В некоторых вариантах осуществления устройство обработки данных может получить новую выборку сожаления (например, выполнив другую итерацию MCCFR). Устройство обработки данных может сохранять новую выборку сожаления в первом хранилище данных в соответствии с алгоритмом выборки накопителя. Например, сохранение новой выборки сожаления в первом хранилище данных согласно алгоритму выборки накопителя включает в себя: определение, заполнено ли первое хранилище данных; и в ответ на определение того, что первое хранилище данных заполнено, замену одной из количества выборок сожаления в первом хранилище данных новой выборкой сожаления.

[0126] На этапе 930 устройство обработки данных сохраняет некоторое количество выборок стратегий во втором хранилище данных (например, внакопителе M_S), причем каждая из количества выборок стратегии включает в себя состояние игрока и значение стратегии возможного действия в состояние игрока. В некоторых вариантах осуществления значение стратегии возможного действия в состоянии игрока включает в себя числитель средней стратегии. Например, каждая из количества выборок стратегии может включать в себя кортеж

стратегии.

[0127] На этапе 940 устройство обработки данных обновляет параметры первой нейронной сети для прогнозирования значения сожаления возможного действия в состоянии игрока на основании количества выборок сожаления в первом хранилище данных, например, согласно уравнению (7). В некоторых вариантах осуществления параметры первой нейронной сети могут обновляться в соответствии с алгоритмом NeuralAgent, показанным на фиг. 6, или любыми другими алгоритмами для оптимизации нейронной сети.

[0128] На этапе 950 устройство обработки данных обновляет параметры второй нейронной сети для прогнозирования значения стратегии возможного действия в состоянии игрока на основе количества выборок стратегии во втором хранилище данных, например, согласно уравнению (8). В некоторых вариантах осуществления параметры второй нейронной сети могут обновляться согласно алгоритму NeuralAgent, показанному на фиг. 6, или любым другим алгоритмам для оптимизации нейронной сети.

[0129] На этапе 960 устройство обработки данных идентифицирует первое состояние игрока и первое возможное действие в первом состоянии игрока.

[0130] На этапе 970 устройство обработки данных прогнозирует первое значение сожаления первого возможного действия в первом состоянии игрока, используя параметры первой нейронной сети. В некоторых вариантах осуществления прогнозированное первое значение сожаления первого возможного действия в первом состоянии игрока может использоваться в следующей итерации алгоритма CFR.

[0131] На этапе 980 устройство обработки данных прогнозирует первое значение стратегии первого возможного действия в первом состоянии игрока, используя параметры второй нейронной сети. В некоторых вариантах осуществления прогнозируемое первое значение стратегии первого возможного действия в первом состоянии игрока может использоваться на следующей итерации алгоритма CFR. В некоторых вариантах осуществления прогнозированное первое значение стратегии первого возможного действия в первом состоянии игрока может использоваться для вычисления приблизительного равновесия по Нэшу и служить в качестве вывода алгоритма CFR. В некоторых вариантах осуществления прогнозируемое первое значение стратегии первого возможного действия в первом состоянии игрока может включать в себя серию действий первого игрока в реальном сценарии, смоделированном IIG. Например, в сценарии рекомендации совместного продукта-услуги прогнозируемое первое значение стратегии первого возможного действия в первом состоянии игрока может включать в себя, например, серию действий в ответ на информацию, предоставленную вторым игроком, соответствующие рекомендации продукта-услуги для клиентов, основанные на информации первого игрока и информации, предоставленной вторым игроком. Прогнозированное первое значение стратегии первого возможного действия в первом состоянии игрока может включать в себя другую информацию в других реальных сценариях, которые моделируются IIG.

[0132] Фиг.10 изображает блок-схему, иллюстрирующую пример компьютерно-реализованной системы, используемой для обеспечения вычислительных функций, связанных с описанными алгоритмами, способами, функциями, процессами, потоками и процедурами в соответствии с вариантами осуществления этого описания. Фиг. 10 является блок-схемой, иллюстрирующей пример компьютерно-реализованной системы 1000, используемой для обеспечения вычислительных функций, связанных с описанными алгоритмами, способами, функциями, процессами, потоками и процедурами, согласно варианту осуществления настоящего раскрытия. В проиллюстрированном варианте осуществления система 1000 включает в себя компьютер 1002 и сеть 1030.

[0133] Проиллюстрированный компьютер 1002 предназначен для охвата любого вычислительного устройства, такого как сервер, настольный компьютер, лэптоп/ноутбук, беспроводной порт данных, смартфон, персональный информационный помощник (PDA), планшетный компьютер, один или несколько процессоров в этих устройствах, другое вычислительное устройство или комбинация вычислительных устройств, включая физические или виртуальные экземпляры вычислительного устройства, или комбинация физических или виртуальных экземпляров вычислительного устройства. Кроме того, компьютер 1002 может включать в себя устройство ввода, такое как консоль, клавиатура, экран касания, другое устройство ввода или комбинацию устройств ввода, которые могут принимать пользовательскую информацию, и устройство вывода, которое передает информацию, связанную с операцией компьютера 1002, включающую в себя цифровые данные, визуальные, звуковые данные, информацию другого типа или комбинацию типов информации, на пользовательском интерфейсе графического типа (UI) (или GUI) или другом UI.

[0134] Компьютер 1002 может выполнять роль в распределенной вычислительной системе в качестве клиента, сетевого компонента, сервера, базы данных или другой персистентности, другой роли или комбинации ролей для выполнения сущности изобретения, описанного в настоящем раскрытии. Проиллюстрированный компьютер 1002 связан с возможностью связи с сетью 1030. В некоторых вариантах осуществления один или несколько компонентов компьютера 1002 могут быть сконфигурированы для работы в среде, в том числе на основе облачных вычислений, локальной, глобальной, другой среде или комбинации сред.

[0135] На высоком уровне компьютер 1002 представляет собой электронное вычислительное устройство, работающее для приема, передачи, обработки, хранения или администрирования данных и информации, связанных с описанной сущностью изобретения. В соответствии с некоторыми вариантами осуществления, компьютер 1002 также может включать в себя или быть подсоединен с возможностью связи к серверу, в том числе сервер приложений, сервер электронной почты, веб-сервер, сервер кэширования, сервер потоковых данных, другой сервер или комбинацию серверов.

[0136] Компьютер 1002 может принимать запросы по сети 1030 (например, от клиентского программного приложения, выполняющегося на другом компьютере 1002) и отвечать на принятые запросы путем обработки принятых запросов с использованием программного приложения или комбинации программных приложений. Кроме того, запросы также могут отправляться на компьютер 1002 от внутренних пользователей (например, из командной консоли или с помощью другого способа внутреннего доступа), внешних или сторонних или других объектов, отдельных лиц, систем или компьютеров.

[0137] Каждый из компонентов компьютера 1002 может обмениваться данными с использованием системной шины 1003. В некоторых вариантах осуществления любой или все компоненты компьютера 1002, включая аппаратное обеспечение, программное обеспечение или комбинацию аппаратного и программного обеспечения, могут взаимодействовать по системной шине 1003 с использованием интерфейса прикладного программирования (API) 1012, сервисного уровня 1013, или комбинации API 1012 и сервисного уровня 1013. API 1012 может включать в себя спецификации для подпрограмм, структур данных и классов объектов. API 1012 может быть независимым или зависимым от компьютерного языка и относиться к полному интерфейсу, отдельной функции или даже набору API. Сервисный уровень 1013 предоставляет программные услуги компьютеру 1002 или другим компонентам (независимо от того, проиллюстрированы они или нет), которые связаны с возможностью обмена данными с компьютером 1002. Функциональные возможности компьютера 1002 могут быть доступны для всех потребителей услуг, используя сервисный уровень 1013. Программные сервисы, такие как сервисы, предоставляемые сервисным уровнем 1013, предоставляют повторно используемые, определенные функции через определенный интерфейс. Например, интерфейс может быть программным обеспечением, написанным на JAVA, C ++, другом вычислительном языке или комбинации вычислительных языков, предоставляющих данные в формате расширяемого языка разметки (XML), другого формата или комбинации форматов. Хотя проиллюстрировано как интегрированный компонент компьютера 1002, альтернативные варианты осуществления могут иллюстрировать API 1012 или сервисный уровень 1013 в качестве автономных компонентов по отношению к другим компонентам компьютера 1002 или другим компонентам (показаны или нет), которые подсоединены с возможностью связи к компьютеру 1002. Кроме того, любая или все части API 1012 или сервисного уровня 1013 могут быть реализованы как дочерний или подмодуль другого программного модуля, корпоративного приложения или аппаратного модуля, не выходя за рамки настоящего раскрытия.

[0138] Компьютер 1002 включает в себя интерфейс 1004. Хотя проиллюстрировано как единый интерфейс 1004, два или более интерфейсов 1004 могут использоваться в соответствии с конкретными потребностями, желаниями или конкретными вариантами осуществления компьютера 1002. Интерфейс 1004 используется компьютером 1002 для связи с другой вычислительной системой (показанной или нет), которая коммуникативно связана с сетью 1030 в распределенной среде. Обычно интерфейс 1004 выполнен с возможностью связи с сетью 1030 и включает в себя логику, закодированную в программном обеспечении, аппаратном обеспечении или комбинации программного и аппаратного обеспечения. Более конкретно, интерфейс 1004 может включать в себя программное обеспечение, поддерживающее один или несколько протоколов связи, связанных с обменом данными, так что сеть 1030 или аппаратное обеспечение интерфейса 1004 выполнено с возможностью сообщать физические сигналы внутри и снаружи проиллюстрированного компьютера 1002.

[0139] Компьютер 1002 включает в себя процессор 1005. Хотя проиллюстрировано как один процессор 1005, два или более процессоров 1005 могут использоваться в соответствии с конкретными потребностями, желаниями или конкретными вариантами осуществления компьютера 1002. Обычно процессор 1005 выполняет инструкции и манипулирует данными для выполнения операций компьютера 1002 и любых алгоритмов, способов, функций, процессов, потоков и процедур, как описано в настоящем раскрытии.

[0140] Компьютер 1002 также включает в себя базу данных 1006, которая может хранить данные для компьютера 1002, другой компонент, коммуникативно связанный с сетью 1030 (независимо от того, показан он или нет), или комбинацию компьютера 1002 и другого компонента. Например, база данных 1006 может быть базой данных в памяти, традиционной или другого типа базой данных, хранящей данные в соответствии с настоящим раскрытием. В некоторых вариантах осуществления база данных 1006 может представлять собой комбинацию двух или более разных типов баз данных (например, гибридной оперативной памяти и традиционной базы данных) в соответствии с конкретными потребностями, желаниями или конкретными вариантами осуществления компьютера 1002 и описанными функциональными возможностями. Хотя проиллюстрировано как одна база данных 1006, две или более баз данных аналогичных или разных типов могут использоваться в соответствии с конкретными потребностями, желаниями или конкретными вариантами осуществления компьютера 1002 и описанными функциональными возможностями. Хотя база данных 1006 иллюстрируется как неотъемлемый компонент компьютера 1002, в альтернативных вариантах осуществления база данных 1006 может быть внешней по отношению к компьютеру 1002. В качестве примера, база данных 1006 может включать в себя вышеописанный накопитель M_R 1016_,в котором хранятся выборки 1026 сожаления, и накопитель M_S 1018, в котором хранятся выборки 1028 стратегии.

[0141] Компьютер 1002 также включает в себя память 1007, которая может хранить данные для компьютера 1002, другого компонента или компонентов, коммуникативно связанных с сетью 1030 (независимо от того, проиллюстрированы они или нет), или комбинации компьютера 1002 и другого компонента. Память 1007 может хранить любые данные в соответствии с настоящим раскрытием. В некоторых вариантах осуществления память 1007 может представлять собой комбинацию двух или более различных типов памяти (например, комбинацию полупроводниковой и магнитной памяти) в соответствии с конкретными потребностями, желаниями или конкретными вариантами осуществления компьютера 1002 и описанными функциональными возможностями. Хотя проиллюстрировано как единая память 1007, две или более памяти 1007 или аналогичных или отличающихся типов могут использоваться в соответствии с конкретными потребностями, желаниями или конкретными вариантами осуществления компьютера 1002 и описанными функциональными возможностями. Хотя память 1007 проиллюстрирована как неотъемлемый компонент компьютера 1002, в альтернативных вариантах осуществления память 1007 может быть внешней по отношению к компьютеру 1002.

[0142] Приложение 1008 является алгоритмическим программным ядром, предоставляющим функциональные возможности в соответствии с конкретными потребностями, желаниями или конкретными вариантами осуществления компьютера 1002, в частности, в отношении функциональных возможностей, описанных в настоящем раскрытии. Например, приложение 1008 может служить одним или несколькими компонентами, модулями или приложениями. Кроме того, хотя приложение 1008 иллюстрируется как одно приложение 1008, оно может быть реализовано как множественные приложения 1008 на компьютере 1002. Кроме того, хотя оно проиллюстрировано как неотъемлемая часть компьютера 1002, в альтернативных вариантах осуществления приложение 1008 может быть внешним по отношению к компьютеру 1002.

[0143] Компьютер 1002 также может включать в себя блок 1014 питания. Блок 1014 питания может включать в себя аккумуляторную или неперезаряжаемую батарею, которая может быть сконфигурирована для замены пользователем или не пользователем. В некоторых вариантах осуществления блок 1014 питания может включать в себя схемы преобразования или администрирования питанием (включая зарядку, режим ожидания или другие функции администрирования питанием). В некоторых вариантах осуществления блок 1014 питания может включать в себя штепсельную вилку, позволяющую подключать компьютер 1002 к сетевой розетке или другому источнику питания, например, для питания компьютера 1002 или для перезарядки перезаряжаемой батареи.

[0144] Может быть любое количество компьютеров 1002, связанных или внешних по отношению к компьютерной системе, содержащей компьютер 1002, причем каждый компьютер 1002 обменивается данными по сети 1030. Кроме того, термин «клиент», «пользователь» или другая соответствующая терминология может использоваться взаимозаменяемо, в зависимости от случая, без отступления от объема настоящего раскрытия. Кроме того, настоящее раскрытие предполагает, что многие пользователи могут использовать один компьютер 1002 или что один пользователь может использовать несколько компьютеров 1002.

[0145] Фиг.11 - схема примера модулей устройства 1100 в соответствии с вариантами осуществления этого описания. Устройство 1100 может быть примерным вариантом осуществления устройства обработки данных для выполнения минимизации контрфактивного сожаления (CFR) для поиска стратегии в стратегическом взаимодействии между двумя или более игроками. В некоторых вариантах осуществления стратегическое взаимодействие между двумя или более игроками может быть смоделировано с помощью несовершенной информационной игры (IIG), в которой участвуют два или более игроков. В качестве примера, IIG представляет собой совместную услугу рекомендации по продукту-услуге, которая включает в себя, по меньшей мере, первого игрока и второго игрока, причем первый игрок имеет ограниченный доступ к информации второго игрока. Устройство 1100 может соответствовать вариантам осуществления, описанным выше, и устройство 1100 включает в себя следующее: первый модуль 1101 идентификации для идентификации N1 возможных действий первого игрока в первом состоянии первого игрока; первый модуль 1102 выборки для выборки возможного действия из N1 возможных действий в первом состоянии первого игрока с первой вероятностью выборки; второй модуль 1103 идентификации для идентификации N2 возможных действий первого игрока во втором состоянии первого игрока, при этом первое состояние первого игрока ближе к начальному состоянию IIG, чем второе состояние первого игрока; второй модуль 1104 выборки для выборки возможного действия из N2 возможных действий во втором состоянии первого игрока со второй вероятностью выборки, причем первая вероятность выборки меньше, чем вторая вероятность выборки; и модуль 1105 обработки для выполнения CFR на основе возможных действий из N1 возможных действий в первом состоянии первого игрока и возможного действия из N2 возможных действий во втором состоянии первого игрока. В некоторых вариантах осуществления первое состояние первого игрока включает в себя историю информации, предоставленной вторым игроком, и N1 возможных действий первого игрока включает в себя N1 возможных действий в ответ на историю информации, предоставленной вторым игроком для предоставления рекомендаций по продукту-услуге для клиентов.

[0146] В необязательном варианте осуществления модуль обработки включает в себя: первый модуль вычисления для вычисления значения сожаления возможного действия из N1 возможных действий в первом состоянии первого игрока; второй модуль вычисления для вычисления значения сожаления возможного действия из N2 возможных действий во втором состоянии первого игрока; первый модуль обновления для обновления первой стратегии первого игрока в первом состоянии на основании значения сожаления возможного действия из N1 возможных действий; и второй модуль обновления для обновления второй стратегии первого игрока во втором состоянии на основе значения сожаления возможного действия из N2 возможных действий.

[0147] В необязательном варианте осуществления первый модуль выборки выбирает k1 возможных действий из N1 возможных действий в первом состоянии первого игрока, причем каждое из k1 возможных действий выбирается с аналогичной первой вероятностью выборки; и второй модуль выборки выбирает k2 возможных действий из N2 возможных действий во втором состоянии первого игрока, причем каждое из k2 возможных действий выбирается с аналогичной второй вероятностью выборки.

[0148] В необязательном варианте осуществления модуль обработки выполняет CFR на основе k1 возможных действий из N1 возможных действий в первом состоянии первого игрока и k2 возможных действий из N2 возможных действий во втором состоянии первого игрока.

[0149] В необязательном варианте осуществления первая вероятность выборки равна k1/N1, а вторая вероятность выборки равна k2/N2.

[0150] В необязательном варианте осуществления 2<= k1<= N1 и 2<= k2 <= N2.

[0151] В необязательном варианте осуществления k1=k2.

[0152] В необязательном варианте осуществления устройство 1100 дополнительно включает в себя следующее: третий модуль идентификации для идентификации M1 возможных действий второго игрока в первом состоянии второго игрока; третий модуль выборки для выборки возможного действия из M1 возможных действий в первом состоянии второго игрока с третьей вероятностью выборки; четвертый модуль идентификации для идентификации M2 возможных действий второго игрока во втором состоянии второго игрока, причем первое состояние второго игрока ближе к начальному состоянию IIG, чем второе состояние второго игрока; и четвертый модуль выборки для выборки возможного действия из M2 возможных действий во втором состоянии первого игрока с четвертой вероятностью выборки, причем третья вероятность выборки меньше, чем четвертая вероятность выборки.

[0153] В необязательном варианте осуществления устройство 1100 дополнительно включает в себя следующее: пятый модуль идентификации для идентификации M1 возможных действий второго игрока в первом состоянии второго игрока, причем первое состояние первого игрока ближе к начальному состоянию IIG, чем первое состояние второго игрока; и пятый модуль выборки для выборки возможного действия из M1 возможных действий в первом состоянии второго игрока с третьей вероятностью выборки, причем третья вероятность выборки больше, чем первая вероятность выборки.

[0154] Система, устройство, модуль или блок, проиллюстрированные в предыдущих вариантах осуществления, могут быть реализованы с использованием компьютерного чипа или объекта или могут быть реализованы с использованием продукта, имеющего некоторую функцию. Типичным вариантом осуществления устройства является компьютер, и компьютер может быть персональным компьютером, ноутбуком, сотовым телефоном, телефоном с камерой, смартфоном, персональным цифровым помощником, медиаплеером, навигационным устройством, устройством приема и отправки электронной почты, игровой приставкой, планшетным компьютером, носимым устройством или любой комбинацией этих устройств.

[0155] Для процесса варианта осуществления функций и ролей каждого модуля в устройстве могут быть сделаны ссылки на процесс варианта осуществления соответствующих этапов в предыдущем способе. Детали опущены здесь для простоты.

[0156] Поскольку вариант осуществления устройства в основном соответствует варианту осуществления способа, для связанных частей могут быть сделаны ссылки на связанные описания в варианте осуществления способа. Ранее описанный вариант осуществления устройства является просто примером. Модули, описанные как отдельные части, могут быть или не быть физически отдельными, а части, отображаемые как модули, могут быть или не быть физическими модулями, могут быть расположены в одной позиции или могут быть распределены по нескольким сетевым модулям. Некоторые или все модули могут быть выбраны на основе фактических требований для достижения целей решений этого описания. Специалист в данной области техники может понять и реализовать варианты осуществления настоящей заявки без творческих усилий.

[0157] Обращаясь снова к фиг. 11, ее можно интерпретировать как иллюстрацию внутреннего функционального модуля и структуры устройства обработки данных для выполнения минимизации контрфактивного сожаления (CFR) для поиска стратегии в стратегическом взаимодействии между двумя или более игроками. В некоторых вариантах осуществления стратегическое взаимодействие между двумя или более игроками может быть смоделировано с помощью несовершенной информационной игры (IIG), в которой участвуют два или более игроков. По существу, исполнительным органом может быть электронное устройство, и электронное устройство включает в себя следующее: один или несколько процессоров; и память, сконфигурированную для хранения исполняемой инструкции одного или нескольких процессоров.

[0158] Один или несколько процессоров сконфигурированы для идентификации N1 возможных действий первого игрока в первом состоянии первого игрока; выборки возможного действия из N1 возможных действий в первом состоянии первого игрока с первой вероятностью выборки; идентификации N2 возможных действий первого игрока во втором состоянии первого игрока, при этом первое состояние первого игрока ближе к начальному состоянию IIG, чем второе состояние первого игрока; выборки возможного действия из N2 возможных действий во втором состоянии первого игрока со второй вероятностью выборки, при этом первая вероятность выборки меньше, чем вторая вероятность выборки; и выполнения CFR на основе возможных действий из N1 возможных действий в первом состоянии первого игрока и возможных действий из N2 возможных действий во втором состоянии первого игрока.

[0159] Необязательно, один или несколько процессоров сконфигурированы для вычисления значения сожаления возможного действия из N1 возможных действий в первом состоянии первого игрока; вычисления значения сожаления возможного действия из N2 возможных действий во втором состоянии первого игрока; обновления первой стратегии первого игрока в первом состоянии на основе значения сожаления возможного действия из N1 возможных действий; и обновления второй стратегии первого игрока во втором состоянии на основе значения сожаления возможного действия из N2 возможных действий.

[0160] Необязательно, один или более процессоров сконфигурированы для выборки k1 возможных действий из N1 возможных действий в первом состоянии первого игрока, причем каждое из k1 возможных действий выбирается с аналогичной первой вероятностью выборки; и выборки k2 возможных действий из N2 возможных действий во втором состоянии первого игрока, причем каждое из k2 возможных действий выбирается с аналогичной второй вероятностью выборки.

[0161] Необязательно, один или более процессоров сконфигурированы для выполнения CFR на основе k1 возможных действий из N1 возможных действий в первом состоянии первого игрока и k2 возможных действий из N2 возможных действий во втором состоянии первого игрока.

[0162] Необязательно, первая вероятность выборки равна k1/N1, а вторая вероятность выборки равна k2/N2.

[0163] Необязательно, 2<= k1<= N1 и 2<= k2 <= N2.

[0164] Необязательно, k1=k2.

[0165] Необязательно, один или несколько процессоров сконфигурированы для идентификации M1 возможных действий второго игрока в первом состоянии второго игрока; выборки возможного действия из M1 возможных действий в первом состоянии второго игрока с третьей вероятностью выборки; идентификации M2 возможных действий второго игрока во втором состоянии второго игрока, при этом первое состояние второго игрока ближе к начальному состоянию IIG, чем второе состояние второго игрока; и выборки возможного действия из M2 возможных действий во втором состоянии первого игрока с четвертой вероятностью выборки, при этом третья вероятность выборки меньше, чем четвертая вероятность выборки.

[0166] Необязательно, один или более процессоров сконфигурированы для: идентификации M1 возможных действий второго игрока в первом состоянии второго игрока, причем первое состояние первого игрока ближе к начальному состоянию IIG, чем первое состояние второго игрока; и выборки возможного действия из M1 возможных действий в первом состоянии второго игрока с третьей вероятностью выборки, причем третья вероятность выборки больше, чем первая вероятность выборки.

[0167] Фиг. 12 является схемой на примере модулей другого устройства 1200 в соответствии с вариантами осуществления этого описания. Устройство 1200 может быть примерным вариантом осуществления устройства обработки данных для выполнения минимизации контрфактивного сожаления (CFR) для поиска стратегии при стратегическом взаимодействии между двумя или более игроками. Устройство 1200 может соответствовать вариантам осуществления, описанным выше, и устройство 1200 включает в себя следующее: первый модуль 1201 хранения для хранения некоторого количества выборок сожаления в первом хранилище данных, где каждая из упомянутого количества выборок сожаления включает в себя состояние игрока и значение сожаления возможного действия в состоянии игрока, причем количество выборок сожаления получают в двух или более итерациях алгоритма минимизации контрфактивного сожаления (CFR) при поиске стратегии в стратегическом взаимодействии между игроком и, по меньшей мере, другим игроком; второй модуль 1202 хранения для хранения некоторого количества выборок стратегии во втором хранилище данных, причем каждая из упомянутого количества выборок стратегии включает в себя состояние игрока и значение стратегии возможного действия в состоянии игрока; первый модуль 1203 обновления для обновления параметров первой нейронной сети для прогнозирования значения сожаления возможного действия в состоянии игрока на основе количества выборок сожаления в первом хранилище данных; и второй модуль 1204 обновления для обновления параметров второй нейронной сети для прогнозирования значения стратегии возможного действия в состоянии игрока на основе количества выборок стратегии во втором хранилище данных. В некоторых вариантах осуществления стратегическое взаимодействие между двумя или более игроками может быть смоделировано с помощью несовершенной информационной игры (IIG), в которой участвуют два или более игроков. В качестве примера, IIG представляет собой совместную услугу рекомендации по продукту-услуге, которая включает, по меньшей мере, игрока и второго игрока, причем игрок имеет ограниченный доступ к информации второго игрока, причем состояние игрока включает в себя историю информации, предоставленной вторым игроком, и при этом возможное действие игрока включает в себя возможное действие в ответ на историю информации, предоставленной вторым игроком для предоставления рекомендаций по продукту-услуге для клиентов.

[0168] Вышеизложенные и другие описанные варианты осуществления могут, каждый, необязательно, включать в себя одну или несколько из следующих особенностей:

[0169] В необязательном варианте осуществления устройство 1200 дополнительно включает в себя следующее: модуль идентификации для идентификации первого состояния игрока и первого возможного действия в первом состоянии игрока; первый модуль прогнозирования для прогнозирования первого значения сожаления первого возможного действия в первом состоянии игрока с использованием параметров первой нейронной сети; и второй модуль прогнозирования для прогнозирования первого значения стратегии первого возможного действия в первом состоянии игрока с использованием параметров второй нейронной сети.

[0170] В необязательном варианте осуществления, в котором первый модуль хранения способен получать новую выборку сожаления; и сохранение новой выборки сожаления в первом хранилище данных в соответствии с алгоритмом выборки накопителя.

[0171] В необязательном варианте осуществления, в котором сохранение новой выборки сожаления в первом хранилище данных в соответствии с алгоритмом выборки накопителя включает в себя: определение, заполнено ли первое хранилище данных; и в ответ на определение того, что первое хранилище данных заполнено, замену одной из количества выборок сожаления в первом хранилище данных новой выборкой сожаления.

[0172] В необязательном варианте осуществления, в котором алгоритм CFR включает в себя алгоритм CFR с надежной выборкой.

[0173] В необязательном варианте осуществления, в котором значение стратегии возможного действия в состоянии игрока включает в себя числитель средней стратегии.

[0174] В необязательном варианте осуществления, в котором значение сожаления возможного действия в состоянии игрока включает в себя контрфактивное значение сожаления возможного действия в состоянии игрока, вычисленное на основании контрфактивного значения возможного действия в состоянии игрока.

[0175] В необязательном варианте осуществления устройство 1200 дополнительно включает в себя следующее: дополнительно включая в себя: в каждой из двух или более итераций алгоритма минимизации контрфактивного сожаления (CFR) при поиске стратегии при стратегическом взаимодействии между игроком и, по меньшей мере, другим игроком, модуль выборки для выборки возможного действия из некоторого количества возможных действий во втором состоянии игрока в соответствии со схемой выборки; первый модуль вычисления для вычисления контрфактивного значения возможного действия во втором состоянии игрока; второй модуль вычисления для вычисления значения сожаления возможного действия во втором состоянии игрока на основе контрфактивного значения возможного действия во втором состоянии игрока; третий модуль вычисления для вычисления обновленной стратегии возможного действия во втором состоянии игрока на основе значения сожаления возможного действия во втором состоянии игрока в соответствии с алгоритмом сопоставления сожаления; и четвертый модуль вычисления для вычисления значения стратегии возможного действия во втором состоянии игрока на основе обновленной стратегии возможного действия во втором состоянии игрока.

[0176] В необязательном варианте осуществления устройство 1200 дополнительно включает в себя следующее: дополнительно включая в себя: первый модуль инициализации для инициализации параметров первой нейронной сети на основе параметров первой нейронной сети в предыдущей итерации; и второй модуль инициализации для инициализации параметров второй нейронной сети на основе параметров второй нейронной сети в предыдущей итерации.

[0177] Система, устройство, модуль или модуль, проиллюстрированный в предыдущих вариантах осуществления, могут быть реализованы с использованием компьютерного чипа или объекта или могут быть реализованы с использованием продукта, имеющего некоторую функцию. Типичным вариантом осуществления устройства является компьютер, и компьютер может быть персональным компьютером, ноутбуком, сотовым телефоном, телефоном с камерой, смартфоном, персональным цифровым помощником, медиаплеером, навигационным устройством, устройством приема и отправки электронной почты, игровой приставкой, планшетным компьютером, носимым устройством или любой комбинацией этих устройств.

[0178] Для процесса варианта осуществления функций и ролей каждого модуля в устройстве могут быть сделаны ссылки на процесс варианта осуществления соответствующих этапов в предыдущем способе. Детали опущены здесь для простоты.

[0179] Поскольку вариант осуществления устройства в основном соответствует варианту осуществления способа, для связанных частей могут быть сделаны ссылки на связанные описания в варианте осуществления способа. Ранее описанный вариант осуществления устройства является просто примером. Модули, описанные как отдельные части, могут быть или не быть физически отдельными, а части, отображаемые как модули, могут быть или не быть физическими модулями, могут быть расположены в одной позиции или могут быть распределены по некоторому количеству сетевых модулей. Некоторые или все из модулей могут быть выбраны на основе фактических требований для достижения целей решений этого описания. Специалист в данной области техники может понять и реализовать варианты осуществления настоящей заявки без творческих усилий.

[0180] Обращаясь снова к фиг. 12, ее можно интерпретировать как иллюстрацию внутреннего функционального модуля и структуры устройства обработки данных для выполнения минимизации контрфактивного сожаления (CFR) для поиска стратегии в стратегическом взаимодействии между двумя или более игроками. Исполнительский орган, по сути, может быть электронным устройством, а электронное устройство включает в себя следующее: один или несколько процессоров; и память, сконфигурированную для хранения исполняемой инструкции одного или нескольких процессоров.

[0181] Один или несколько процессоров сконфигурированы для хранения некоторого количества выборок сожаления в первом хранилище данных, в котором каждая из количества выборок сожаления включает в себя состояние игрока и значение сожаления возможного действия в состоянии игрока, причем количество выборок сожаления получено в двух или более итерациях алгоритма минимизации контрфактивного сожаления (CFR) в поиске стратегии в стратегическом взаимодействии между игроком и, по меньшей мере, другим игроком; хранения некоторого количества выборок стратегии во втором хранилище данных, причем каждая из количества выборок стратегии включает в себя состояние игрока и значение стратегии возможного действия в состоянии игрока; обновление параметров первой нейронной сети для прогнозирования значения возможного действия в состоянии игрока на основе количества выборок сожаления в первом хранилище данных; и обновления параметров второй нейронной сети для прогнозирования значения стратегии возможного действия в состоянии игрока на основе количества выборок стратегии во втором хранилище данных. В некоторых воплощениях стратегическое взаимодействие между двумя или более игроками может быть смоделировано несовершенной информационной игрой (IIG), в которой участвуют два или более игроков. Например, IIG представляет собой совместную услугу рекомендаций по продукту-услуге, которая включает по меньшей мере игрока и второго игрока, причем игрок имеет ограниченный доступ к информации второго игрока, причем состояние игрока включает в себя историю информации, предоставленной вторым игроком, и при этом возможное действие игрока включает в себя возможное действие в ответ на историю информации, предоставленной вторым игроком для предоставления рекомендаций по продукту-услуге для клиентов.

[0182] Необязательно один или несколько процессоров сконфигурированы для: идентификации первого состояния игрока и первого возможного действия в первом состоянии игрока; прогнозирования первого значения сожаления первого возможного действия в первом состоянии игрока, используя параметры первой нейронной сети; и прогнозирования первого значения стратегии первого возможного действия в первом состоянии игрока, используя параметры второй нейронной сети.

[0183] Необязательно один или несколько процессоров сконфигурированы для: получения новой выборки сожаления; и хранения новой выборки сожаления в первом хранилище данных в соответствии с алгоритмом выборки накопителя.

[0184] Необязательно, один или несколько процессоров сконфигурированы, чтобы: определить, заполнено ли первое хранилище данных; и в ответ на определение, что первое хранилище данных заполнено, заменить одну из количества выборок сожаления в первом хранилище данных новой выборкой сожаления.

[0185] Необязательно алгоритм CFR включает в себя алгоритм CFR с надежной выборкой.

[0186] Необязательно значение стратегии возможного действия в состоянии игрока включает в себя числитель средней стратегии.

[0187] Необязательно, значение сожаления возможного действия в состоянии игрока включает в себя контрфактивное значение сожаления возможного действия в состоянии игрока, вычисленное на основе контрфактивного значения возможного действия в состоянии игрока.

[0188] Необязательно, один или несколько процессоров сконфигурированы, чтобы: в каждой из двух или более итераций алгоритма минимизации контрфактивного сожаления (CFR) в поиске стратегии в стратегическом взаимодействии между игроком и, по меньшей мере, другим игроком, выбирать возможное действие из некоторого количества возможных действий во втором состоянии игрока в соответствии с схемой выборки; вычислять контрфактивное значение возможного действия во втором состоянии игрока; вычислять значение сожаления возможного действия во втором состоянии игрока на основе контрфактивного значения возможного действия во втором состоянии игрока; вычислять обновленную стратегию возможного действия во втором состоянии игрока, на основе значения сожаления возможного действия во втором состоянии игрока в соответствии с алгоритмом сопоставления сожаления; и вычислять значение стратегии возможного действия во втором состоянии игрока на основе обновленной стратегии возможного действия во втором состоянии игрока.

[0189] Необязательно, один или несколько процессоров сконфигурированы для инициализации параметров первой нейронной сети на основе параметров первой нейронной сети в предыдущей итерации; и инициализации параметров второй нейронной сети на основе параметров второй нейронной сети в предыдущей итерации.

[0190] Описанные варианты осуществления сущности изобретения могут включать в себя один или несколько особенностей, по отдельности или в комбинации. Например, в первом варианте осуществления компьютерно-реализованный способ выполнения минимизации контрфактивного сожаления (CFR) для поиска стратегии при стратегическом взаимодействии между двумя или более игроками. Способ включает в себя: сохранение некоторого количества выборок сожаления в первом хранилище данных, при этом каждая из количества выборок сожаления включает в себя состояние игрока и значение сожаления возможного действия в состоянии игрока, причем количество выборок сожаления получают в двух или более итерациях алгоритма минимизации контрфактивного сожаления (CFR) при поиске стратегии в стратегическом взаимодействии между игроком и, по меньшей мере, другим игроком; сохранение некоторого количества выборок стратегии во втором хранилище данных, причем каждая из количества выборок стратегии включает в себя состояние игрока и значение стратегии возможного действия в состоянии игрока; обновление параметров первой нейронной сети для прогнозирования значения сожаления возможного действия в состоянии игрока на основании количества выборок сожаления в первом хранилище данных; и обновление параметров второй нейронной сети для прогнозирования значения стратегии возможного действия в состоянии игрока на основе количества выборок стратегии во втором хранилище данных.

[0191] Вышеизложенные и другие описанные варианты осуществления могут, каждый, необязательно, включать в себя одну или несколько из следующих особенностей:

[0192] Первая особенность, комбинируемая с любой из следующих особенностей, дополнительно включает в себя: идентификацию первого состояния игрока и первого возможного действия в первом состоянии игрока; прогнозирование первого значения сожаления первого возможного действия в первом состоянии игрока с использованием параметров первой нейронной сети; и прогнозирование первого значения стратегии первого возможного действия в первом состоянии игрока, используя параметры второй нейронной сети.

[0193] Вторая особенность, комбинируемая с любой из следующих особенностей, дополнительно включает в себя: получение новой выборки сожаления; и сохранение новой выборки сожаления в первом хранилище данных в соответствии с алгоритмом выборки накопителя.

[0194] Третья особенность, комбинируемая с любой из следующих особенностей, в которой сохранение новой выборки сожаления в первом хранилище данных в соответствии с алгоритмом выборки накопителя включает в себя: определение, заполнено ли первое хранилище данных; и в ответ на определение того, что первое хранилище данных заполнено, замену одной из количества выборок сожаления в первом хранилище данных новой выборкой сожаления.

[0195] Четвертая особенность, комбинируемая с любой из следующих особенностей, в которой алгоритм CFR включает в себя алгоритм CFR с надежной выборкой.

[0196] Пятая особенность, комбинируемая с любой из следующих особенностей, в которой значение стратегии возможного действия в состоянии игрока включает в себя числитель средней стратегии.

[0197] Шестая особенность, комбинируемая с любой из следующих особенностей, в которой значение сожаления возможного действия в состоянии игрока включает в себя контрфактивное значение сожаления возможного действия в состоянии игрока, вычисленное на основе контрфактивного значения возможного действия в состоянии игрока.

[0198] Седьмая особенность, комбинируемая с любой из следующих особенностей, дополнительно включает в себя: в каждой из двух или более итераций алгоритма минимизации контрфактивного сожаления (CFR) в поиске стратегии при стратегическом взаимодействии между игроком и, по меньшей мере, другим игроком, выборка возможного действия из некоторого количества возможных действий во втором состоянии игрока согласно схеме выборки; вычисление контрфактивного значения возможного действия во втором состоянии игрока; вычисление значения сожаления возможного действия во втором состоянии игрока на основе контрфактивного значения возможного действия во втором состоянии игрока; вычисление обновленной стратегии возможного действия во втором состоянии игрока на основе значения сожаления возможного действия во втором состоянии игрока в соответствии с алгоритмом сопоставления сожаления; и вычисление значения стратегии возможного действия во втором состоянии игрока на основе обновленной стратегии возможного действия во втором состоянии игрока.

[0199] Восьмая особенность, комбинируемая с любой из следующих особенностей, дополнительно включающая в себя: инициализацию параметров первой нейронной сети на основе параметров первой нейронной сети в предыдущей итерации; и инициализацию параметров второй нейронной сети на основе параметров второй нейронной сети в предыдущей итерации.

[0200] Во втором варианте осуществления система включает в себя: один или несколько процессоров; и одну или несколько машиночитаемых памятей, подсоединенных к одному или нескольким процессорам и содержащих хранимые на них инструкции, которые могут выполняться одним или несколькими процессорами для выполнения способа любого из первого варианта осуществления и его необязательной комбинации одной или нескольких особенностей, описанных выше.

[0201] В третьем варианте осуществления устройство для выполнения минимизации контрфактивного сожаления (CFR) для поиска стратегии в стратегическом взаимодействии включает в себя двух или более игроков, в том числе: первый модуль хранения для хранения некоторого количества выборок сожаления в первом хранилище данных, причем каждая из количества выборок сожаления включает в себя состояние игрока и значение сожаления возможного действия в состоянии игрока, при этом количество выборок сожаления получают в двух или более итерациях алгоритма минимизации контрфактивного сожаления (CFR) при поиске стратегии в стратегическом взаимодействии между игроком и, по меньшей мере, другим игроком; второй модуль хранения для хранения некоторого количества выборок стратегий во втором хранилище данных, причем каждая из количества выборок стратегии включает в себя состояние игрока и значение стратегии возможного действия в состоянии игрока; первый модуль обновления для обновления параметров первой нейронной сети для прогнозирования значения сожаления возможного действия в состоянии игрока на основе количества выборок сожаления в первом хранилище данных; и второй модуль обновления для обновления параметров второй нейронной сети для прогнозирования значения стратегии возможного действия в состоянии игрока на основании количества выборок стратегии во втором хранилище данных. В некоторых вариантах осуществления стратегическое взаимодействие между двумя или более игроками может быть смоделировано с помощью несовершенной информационной игры (IIG), в которой участвуют два или более игроков. В качестве примера, IIG представляет собой совместную услугу рекомендации по продукту-услуге, которая включает в себя, по меньшей мере, игрока и второго игрока, причем игрок имеет ограниченный доступ к информации второго игрока, причем состояние игрока включает в себя историю информации, предоставленной вторым игроком, и при этом возможное действие игрока включает в себя возможное действие в ответ на историю информации, предоставленной вторым игроком для предоставления рекомендаций по продукту-услуге для клиентов.

[0202] Вышеизложенные и другие описанные варианты осуществления могут, каждый, необязательно, включать в себя одну или несколько из следующих особенностей:

[0203] Первая особенность, комбинируемая с любой из следующих особенностей, дополнительно включающая в себя: модуль идентификации для идентификации первого состояния игрока и первого возможного действия в первом состоянии игрока; первый модуль прогнозирования для прогнозирования первого значения сожаления первого возможного действия в первом состоянии игрока с использованием параметров первой нейронной сети; и второй модуль прогнозирования для прогнозирования первого значения стратегии первого возможного действия в первом состоянии игрока с использованием параметров второй нейронной сети.

[0204] Вторая особенность, комбинируемая с любой из следующих особенностей, в которой первый модуль хранения способен получать новую выборку сожаления; и сохранять новую выборку сожаления в первом хранилище данных в соответствии с алгоритмом выборки накопителя.

[0205] Третья особенность, комбинируемая с любой из следующих особенностей, в которой сохранение новой выборки сожаления в первом хранилище данных в соответствии с алгоритмом выборки накопителя включает в себя: определение, заполнено ли первое хранилище данных; и в ответ на определение того, что первое хранилище данных заполнено, замену одной из упомянутого количества выборок сожаления в первом хранилище данных новой выборкой сожаления.

[0206] Четвертая особенность, комбинируемая с любой из следующих особенностей, в которой алгоритм CFR включает в себя алгоритм CFR с надежной выборкой.

[0207] Пятая особенность, комбинируемая с любой из следующих особенностей, в которой значение стратегии возможного действия в состоянии игрока включает в себя числитель средней стратегии.

[0208] Шестая особенность, комбинируемая с любой из следующих особенностей, в которой значение сожаления возможного действия в состоянии игрока включает в себя контрфактивное значение сожаления возможного действия в состоянии игрока, вычисленное на основе контрфактивного значения возможного действия в состоянии игрока.

[0209] Седьмая особенность, комбинируемая с любой из следующих особенностей, дополнительно включающая в себя: в каждой из двух или более итераций алгоритма минимизации контрфактивного сожаления (CFR) при поиске стратегии при стратегическом взаимодействии между игроком и, по меньшей мере, другим игроком, модуля выборки для выборки возможного действия из некоторого количества возможных действий во втором состоянии игрока согласно схеме выборки; первый модуль вычисления для вычисления контрфактивного значения возможного действия во втором состоянии игрока; второй модуль вычисления для вычисления значения сожаления возможного действия во втором состоянии игрока на основе контрфактивного значения возможного действия во втором состоянии игрока; третий модуль вычисления для вычисления обновленной стратегии возможного действия во втором состоянии игрока на основе значения сожаления возможного действия во втором состоянии игрока в соответствии с алгоритмом сопоставления сожаления; и четвертый модуль вычисления для вычисления значения стратегии возможного действия во втором состоянии игрока на основе обновленной стратегии возможного действия во втором состоянии игрока.

[0210] Восьмая особенность, комбинируемая с любой из следующих особенностей, дополнительно включающая в себя: первый модуль инициализации для инициализации параметров первой нейронной сети на основе параметров первой нейронной сети в предыдущей итерации; и второй модуль инициализации для инициализации параметров второй нейронной сети на основе параметров второй нейронной сети в предыдущей итерации.

[0211] Варианты осуществления изобретения, а также действия и операции, описанные в этом описании, могут быть реализованы в цифровых электронных схемах, в материально-воплощенном компьютерном программном обеспечении или встроенном программном обеспечении, в компьютерном оборудовании, включая структуры, раскрытые в этом описании, и их структурные эквиваленты или в комбинациях одного или нескольких из них. Варианты осуществления изобретения, описанного в этом описании, могут быть реализованы в виде одной или нескольких компьютерных программ, например, одного или нескольких модулей инструкций компьютерной программы, закодированных на носителе компьютерной программы, для выполнения или для управления работой устройства обработки данных. Например, носитель компьютерной программы может включать в себя один или несколько машиночитаемых носителей данных, на которых закодированы или сохранены инструкции. Носителем может быть материальный постоянный машиночитаемый носитель, такой как магнитный, магнитооптический или оптический диск, твердотельный накопитель, оперативное память (ОЗУ), постоянное память (ПЗУ) или другие виды СМИ. Альтернативно или в дополнение, несущая может быть искусственно сгенерированным распространяемым сигналом, например, сгенерированным машиной электрическим, оптическим или электромагнитным сигналом, который генерируется для кодирования информации для передачи в подходящее приемное устройство для исполнения устройством обработки данных. Компьютерный носитель данных может быть или быть частью машиночитаемого запоминающего устройства, подложки машиночитаемого запоминающего устройства, устройства памяти с произвольным или последовательным доступом или комбинации одного или нескольких из них. Компьютерный носитель данных не является распространяемым сигналом.

[0212] Компьютерная программа, которая также может упоминаться или описываться как программа, программное обеспечение, программное приложение, приложение, модуль, программный модуль, движок, сценарий или код, может быть написана на любом языке программирования, включая компилируемые или интерпретируемые языки или декларативные или процедурные языки; и она может быть развернута в любой форме, в том числе как отдельная программа или как модуль, компонент, механизм, подпрограмма или другое устройство, подходящее для выполнения в вычислительной среде, причем эта среда может включать в себя один или несколько компьютеров, соединенных данными сеть связи в одном или нескольких местоположениях.

[0213] Компьютерная программа может, но не обязательно, соответствовать файлу в файловой системе. Компьютерная программа может храниться в части файла, которая содержит другие программы или данные, например, в одном или нескольких сценариях, хранящихся в документе на языке разметки, в одном файле, выделенном для рассматриваемой программы, или в нескольких скоординированных файлах, например файлы, в которых хранится один или несколько модулей, подпрограмм или частей кода.

[0214] Процессоры для выполнения компьютерной программы включают в себя, например, как микропроцессоры общего и специального назначения, так и любой один или несколько процессоров любого типа цифрового компьютера. Как правило, процессор будет принимать инструкции компьютерной программы для выполнения, а также данные с невременного машиночитаемого носителя, подключенного к процессору.

[0215] Термин «устройство обработки данных» охватывает все виды аппаратур, устройств и машин для обработки данных, в том числе, например, программируемый процессор, компьютер или несколько процессоров или компьютеров. Устройство обработки данных может включать в себя логические схемы специального назначения, например, FPGA (программируемая пользователем вентильная матрица), ASIC (специализированная интегральная схема) или GPU (графический процессор). Устройство может также включать в себя, помимо аппаратного обеспечения, код, который создает среду выполнения для компьютерных программ, например код, который составляет микропрограммное обеспечение процессора, стек протоколов, систему управления базой данных, операционную систему или комбинацию одного или нескольких из них.

[0216] Процессы и логические потоки, описанные в этом описании, могут выполняться одним или несколькими компьютерами или процессорами, выполняющими одну или несколько компьютерных программ для выполнения операций, оперируя входными данными и генерируя выходные данные. Процессы и логические потоки также могут выполняться с помощью логических схем специального назначения, например FPGA, ASIC или GPU, или с помощью комбинации логических схем специального назначения и одного или нескольких программируемых компьютеров.

[0217] Компьютеры, подходящие для выполнения компьютерной программы, могут быть основаны на общих или специализированных микропроцессорах или на обоих, или на любом другом типе центрального процессора. Как правило, центральный процессор будет получать инструкции и данные из постоянной памяти или из оперативной памяти или из обеих. Элементы компьютера могут включать в себя центральный процессор для выполнения инструкций и одной или нескольких памятей для хранения инструкций и данных. Центральный процессор и память могут быть дополнены или включены в логические схемы специального назначения.

[0218] Как правило, компьютер также будет включать в себя или будет оперативно подсоединен для приема данных или передачи данных на одно или несколько устройств хранения. Памяти могут быть, например, магнитными, магнитооптическими или оптическими дисками, твердотельными накопителями или любым другим типом постоянных, машиночитаемых носителей. Однако компьютеру не нужно иметь такие устройства. Таким образом, компьютер может быть подсоединен к одному или нескольким запоминающим устройствам, такими как одна или несколько памятей, которые являются локальными и/или удаленными. Например, компьютер может включать в себя одну или несколько локальных памятей, которые являются неотъемлемыми компонентами компьютера, или компьютер может быть подсоединен к одной или нескольким удаленным памятям, которые находятся в облачной сети. Кроме того, компьютер может быть встроен в другое устройство, например мобильный телефон, персональный цифровой помощник (PDA), мобильный аудио- или видеоплеер, игровую приставку, приемник глобальной системы позиционирования (GPS) или портативное устройство хранения данных, например, флэш-накопитель с универсальной последовательной шиной (USB), и это лишь некоторые из них.

[0219] Компоненты могут быть «подсоединены» друг к другу, будучи коммутативно такими, как электрически или оптически соединенные друг с другом, либо напрямую, либо через один или несколько промежуточных компонентов. Компоненты также могут быть «подсоединены» друг к другу, если один из компонентов интегрирован в другой. Например, компонент хранения, который интегрирован в процессор (например, компонент кэша L2), «подсоединен» к процессору.

[0220] Чтобы обеспечить взаимодействие с пользователем, варианты осуществления сущности изобретения, описанной в этом описании, могут быть реализованы или сконфигурированы для связи с компьютером, имеющим устройство отображения, например, монитор LCD (жидкокристаллический дисплей) для отображения информации для пользователя и устройство ввода, с помощью которого пользователь может обеспечить ввод в компьютер, например клавиатуру и указательное устройство, например мышь, трекбол или консоль. Другие виды устройств также могут использоваться для обеспечения взаимодействия с пользователем; например, обратная связь, предоставляемая пользователю, может быть любой формой сенсорной обратной связи, например, визуальной обратной связи, слуховой обратной связи или тактильной обратной связи; и ввод от пользователя может быть получен в любой форме, включая акустический, речевой или тактильный ввод. Кроме того, компьютер может взаимодействовать с пользователем, отправляя документы и принимая документы с устройства, которое используется пользователем; например, путем отправки веб-страниц в веб-браузер на устройстве пользователя в ответ на запросы, принятые из веб-браузера, или путем взаимодействия с приложением, запущенным на пользовательском устройстве, например смартфоном или электронным планшетом. Кроме того, компьютер может взаимодействовать с пользователем, отправляя текстовые сообщения или другие формы сообщений на персональное устройство, например смартфон, на котором запущено приложение обмена сообщениями, и принимать ответные сообщения от пользователя в ответ.

[0221] В данном описании используется термин «сконфигурированный для (чтобы)» в связи с системами, устройствами и компонентами компьютерной программы. Если система из одного или нескольких компьютеров сконфигурирована для выполнения конкретных операций или действий, это означает, что система установила на нее программное обеспечение, встроенное программное обеспечение, аппаратное обеспечение или их комбинацию, которые при работе вынуждают систему выполнять операции или действия. Для одной или нескольких компьютерных программ, которые должны быть сконфигурированы для выполнения конкретных операций или действий, это означает, что одна или несколько программ включают в себя инструкции, которые при выполнении устройством обработки данных вынуждают устройство выполнять операции или действия. Если логические схемы специального назначения должны быть сконфигурированы для выполнения конкретных операций или действий, это означает, что схема имеет электронную логику, которая выполняет операции или действия.

[0222] Хотя это описание содержит много конкретных деталей вариантов осуществления, их не следует истолковывать как ограничения объема заявленного, что определяется самой формулой изобретения, а скорее как описания признаков, которые могут быть специфическими для конкретных вариантов осуществления. Некоторые признаки, которые описаны в этом описании в контексте отдельных вариантов осуществления, также могут быть реализованы в комбинации в одном варианте осуществления. И наоборот, различные признаки, которые описаны в контексте отдельных вариантов осуществления, также могут быть реализованы в нескольких вариантах осуществления отдельно или в любой подходящей субкомбинации. Более того, хотя признаки могут быть описаны выше как действующие в некоторых комбинациях и даже первоначально заявлены как таковые, один или несколько признаков из заявленной комбинации могут в некоторых случаях быть исключены из комбинации, и формула может быть направлена на субкомбинацию или вариацию субкомбинации.

[0223] Аналогично, хотя операции изображены на чертежах и изложены в формуле изобретения в конкретном порядке, это не следует понимать как требование, чтобы такие операции выполнялись в конкретном показанном порядке или в последовательном порядке, или чтобы выполнялись все проиллюстрированные операции, чтобы достичь желаемых результатов. В некоторых обстоятельствах многозадачность и параллельная обработка могут быть выгодными. Кроме того, разделение различных системных модулей и компонентов в описанных выше вариантах осуществления не следует понимать как требующее такого разделения во всех вариантах осуществления, и следует понимать, что описанные программные компоненты и системы, как правило, могут быть объединены вместе в одном программном продукте или упакованы в несколько программных продуктов.

[0224] Конкретные варианты осуществления сущности изобретения были описаны. Другие варианты осуществления находятся в пределах объема следующей формулы изобретения. Например, действия, изложенные в формуле изобретения, могут выполняться в другом порядке и при этом достигать желаемых результатов. В качестве одного примера, процессы, изображенные на прилагаемых фигурах, не обязательно требуют конкретного показанного порядка или последовательного порядка для достижения желаемых результатов. В некоторых случаях многозадачность и параллельная обработка могут быть полезными.