反事实遗憾 (CFR)

在 Rust 中为两人零和博弈不完整信息游戏提供反事实遗憾最小化求解器。这是一个 Rust 库和二进制程序，用于计算两人零和博弈不完整信息游戏的近似纳什均衡。

用法

库

要使用此包的库部分，请在您的 Cargo.toml 中添加以下内容。

[dependencies]
cfr = { version = "0.1.0", default-features = false }

然后实现 IntoGameNode，用于表示您游戏树中的节点类型（或可以生成新节点）。

最后执行

use cfr::{Game, IntoGameNode};
struct MyData { ... }
impl IntoGameNode for MyData { ... }
let game = Game::from_root(...)?;
let strategies = game.solve_external();
let info = strategies.get_info();
let regret = info.regret();
let [player_one, player_two] = strategies.as_named();

二进制程序

此包也可以作为具有几种不同输入格式的二进制程序使用。使用以下命令安装：

$ cargo install cfr

解决游戏将生成对玩家一期望效用的估计，以及以 JSON 格式找到的遗憾和策略。

$ cfr -i game_file
{
  "expected_one_utility": 0.05555555727916178,
  "player_one_regret": 1.186075528125663e-06,
  "player_two_regret": 8.061797025377127e-05,
  "regret": 8.061797025377127e-05,
  "player_one_strategy": { ... },
  "player_two_regret": { ... }
}

命令行工具可以解释自定义的 JSON DSL 和 gambit .efg 文件。

JSON 格式

DSL 由以下定义

node     ::= terminal || chance || player
terminal ::= { "terminal": <number> }
chance   ::= {
               "chance": {
                 "infoset"?: <string>,
                 "outcomes": {
                   "<named outcome>": { "prob": <number>, "state": node },
                   ...
                 }
               }
             }
player   ::= {
               "player": {
                 "player_one": <bool>,
                 "infoset": <string>,
                 "actions": { "<named action>": node, ... }
               }
             }

一个最小示例，突出显示所有类型的节点，但是一个不有趣的游戏：

{
  "chance": {
    "outcomes": {
      "single": {
        "prob": 1.0,
        "state": {
          "player": {
            "player_one": true,
            "infoset": "none",
            "actions": {
              "only": {
                "terminal": 0.0
              }
            }
          }
        }
      }
    }
  }
}

在这个游戏中，有 100% 的概率得到 "single" 结果，然后是玩家一的移动，他们没有信息 "none"，只有一个动作："only"。选择该动作后，他们获得收益 0。

Gambit 格式

Gambit 格式遵循标准的 gambit 扩展形式游戏格式，有一些轻微的限制。

• Gambit 指定动作是可选的，但这要求每个玩家和机会节点都指定其动作。
• 动作必须唯一，并对非冲突信息集名称有一些非常轻微的限制（见 重复信息集）。
• 博弈格式允许任意玩家、非固定和的扩展形式博弈，但这仅允许两人固定和完美记忆博弈。
• 为了效率，使用双精度浮点数，因为均衡是近似的，因此在极端情况下，收益可能无法表示。

示例

如果实现IntoGameNode对您的游戏来说很 confusing，这里有一些更复杂的游戏示例，这些游戏在文档中并不完全符合

• Kuhn Poker - 这也可以使用 cargo run --example kuhn_poker -- 运行。
• Liar's Dice - 这被实现为一个基准，以允许使用 nightly APIs。

错误

本节详细介绍了命令行可能返回的错误。

JSON 错误

此错误发生在 JSON 不符合预期的读取格式时。有关规范详情，请参阅JSON 格式，并确保您提供的 JSON 符合该规范。

博弈错误

此错误发生在无法解析博弈文件时。应该有关于错误发生位置的确切信息。有关格式的更多详情，请参阅gambit 格式。

自动错误

游戏文件无法被任何已知游戏格式解析。为了获得有关解析失败的更详细错误，请尝试再次运行并使用--input-format <format>来获取更精确的错误。

重复的信息集

gambit .efg 文件不需要命名信息集，但 cfr 需要对每个信息集使用字符串名称。它将默认使用信息集编号的字符串版本，但如果该信息集名称已被占用，则将失败。例如

...
p 1 1 "2" { ... } 0
p 1 2 { ... } 0
...

将产生此错误，直到在别处为信息集 2 定义名称。

固定和

反事实后悔最小化仅适用于固定和游戏。由于 gambit 文件独立定义收益，因此会验证每个配置的收益总和的范围小于单个玩家收益范围的 0.1%。如果您遇到此错误，则 cfr 不会为此游戏运行。

游戏错误

此错误发生在游戏规范存在问题，使得创建紧凑游戏变得不可能时。有关详细信息，请参阅 GameError 的文档。

求解错误

如果存在求解问题，将发生此错误。这只会发生在您请求了太多线程或线程无法生成时。有关详细信息，请参阅 SolveError 的文档。

待办事项

• 随着折扣 CFR 的实现，增量后悔更新发生的频率更低。我们应该检查一定次数迭代后的真正后悔。这需要进行一些重构，以及一些基准测试，以确保不会在后悔计算上浪费时间。
• 我们目前随意设置线程数量很高，但在我们决定要生成多少线程之前，我们已经有了完整的游戏树，因此我们可以更智能地设置最大值，并基于树的大小设置负载因子。
• 当前要求infosets和actions是可哈希的，并且根据使用情况，可克隆。大多数函数可以重写为接受Hash、Ord或Clone的组合，并根据特质约束使用性能最佳的选项。这似乎没有特别有用的地方，而且工作量很大，所以目前省略了这一部分。