问题标签 [game-theory]

今年 9 月我将开始我在大学的最后一年，所以我需要为我的论文做一个项目。我查看了去年 uni 建议的项目列表，我没有发现其中任何一个很有趣。再加上我对“理论”计算机科学作为一个整体的“热爱”，让我想到，如果能在暑假的最后一个月更深入地研究一些 cs 领域，那就太好了。到目前为止，在大学里，关于计算机科学更“理论”的一面，我们主要研究了搜索和排序算法、字符串匹配、博弈论、软件工程的设计模式和迷宫求解算法。明年的课程大纲包括生物信息学、编译器和机器学习。我对所有这些都有一个想法，但没有什么令人难以置信的详细信息（即，我们根本没有进行算法设计）。所以，我在想，与其从列表中选择一个项目，或者选择一个业余爱好者也可以做的项目，为什么不研究一些计算机科学领域并在此过程中进行头脑风暴呢？

如果您能指出关于以下领域的可用资源（书籍、电子书、pdf、在线社区等），或者甚至建议要探索的新领域，我将不胜感激。

请注意，我只想了解它们是关于什么的，而不是解决技术问题。

田野：

• 网络语义

• 算法（分析、设计等）

• 机器学习

• 进化计算

• 博弈论

• 其他 （？？？）

给定一个任意的钉子纸牌配置，计算导致“游戏结束”位置的任何一系列移动的最有效方法是什么。

例如，标准起始位置是：

而“结束游戏”的位置是：

Peg solitare 在这里有更详细的描述：维基百科，我们正在考虑“英语板”变体。

我很确定在一台合理的计算机上，比如一台 P4 3Ghz，可以在几秒钟内解决任何给定的起始板。

目前这是我最好的策略：

这是一个跳棋游戏。查看旧版本代码的修订历史。

我正在尝试使用深度 0，并且在大约一半的比赛中得分是正确的，然后突然之间它开始搞砸了。其中一名球员将开始宣称他的分数高于实际分数。为什么只能玩半场？！

我正在尝试为跳棋游戏实现NegaMax。我现在只是在深度为 0 的情况下对其进行测试，这意味着当前玩家只是评估他的所有动作，而不考虑其他玩家接下来可能会做什么。它在大约一半的游戏中完美运行（正确计算分数），然后在它的中途开始吐出无意义的答案。

例如，白方可能还剩 1 件，而黑方将有 5 件，但它会将白方的走法评估为 7 分，例如，当白方的棋步都应该为负时，因为他输了。黑方下一步可能会获胜，但它会将获胜的一步评估为 -4，即使它应该是 1000。

我可以理解它一直在输出垃圾，但为什么它会在前几轮工作，然后开始搞砸？

我在 6x6 板上隔离了它不喜欢的板状态：

看起来这不是时间或移动次数的问题，它只是不喜欢特定的棋盘状态。不过，我看不出这种状态有什么特别之处。

在这种状态下，它将黑方的所有 4 步棋评估为 -13。如果你看看我是如何得分的，它说每人 2 分，每个国王 3 分，如果由其他玩家拥有，则为负数。看起来好像它把所有的碎片都当作白色......这是获得 13 的唯一方法。

我发现了另一个线索。在棋盘评分方法中，我让它打印出它所看到的......这就是它告诉我的：

棋盘格的编号如下：

我认为这确实是在说黑色的部分是白色的……现在要弄清楚是什么原因造成的。

所以......现在我知道颜色是错误的，但仅限于BoardScore功能。我的正常显示程序从未对此有所了解，否则我会在数小时前发现问题。我在想它可能是在ApplyMove颜色被切换的功能中..

但这也没有多大意义……这件作品只是从开始位置复制到结束位置。需要调查什么m.Color是......也许它会提供更多线索！我觉得自己像个侦探。

我正在尝试重新创建这个征服俱乐部（风险类）游戏：

http://conquerclub.barrycarter.info/ONEOFF/7460216.html

换句话说，我想知道每个时间点谁拥有每个领土，以及他们在该领土上拥有多少军队。我的主要信息来源是游戏日志。笔记：

% 它不在游戏日志中，但所有领土都以 3 名部队开始。

% 由于我们在游戏结束时知道领地拥有者，并且游戏日志中提到了所有拥有者的变化，因此在任何时间点确定领地拥有者都很容易。

% 挑战是在给定时间找到领土上的部队数量。

% 游戏日志提供关于部队部署、增援和征服的信息。

%但是，游戏日志不完整。假设 X 领土攻击 Y 领土没有成功，但在此过程中两个领土都失去了兵力。游戏日志不会提及这一点。

% （一般而言）在给定时间找到一个领土上的确切部队人数可能是不可能的，所以我正在寻找一个范围。

% 我尝试将数据作为一系列不等式提供给 Mathematica，但正如手册警告的那样，计算时间随着不等式的数量呈指数增长。即使有相当少的不等式，它也会挂起。另外，我不相信 Mathematica 是正确的工具。

％ 有什么想法吗？另一个例子是： http ://conquerclub.barrycarter.info/ONEOFF/7562013.html

％我知道http://userscripts.org/scripts/show/83035，但只跟踪\所有者，而不是部队人数。

我有一个有趣的概念问题，我想知道是否有人可以帮我量化它。基本上，我在玩一组游戏……对于每场比赛，我都知道我赢的概率、打平的概率和输球的概率（每场比赛都有不同的概率）。

在高层次上，我想知道的是：我应该关注哪些游戏？例如，我不会在我有 0% 获胜机会的游戏（或我有 100% 获胜机会的游戏）上投入任何精力。但是对于一个 50/50 的比赛，我会很在意，并且想付出最大的努力。如果不涉及平局，则很简单：“关心能力”=我获胜的几率接近 50%？但是有了关系，事情就变得复杂了。

我不确定这是否绝对必要，但如果你需要，你可以假设胜利是 0 分，平局会给你 1 分，胜利会给你 2 分。换句话说，从输到平和从平到赢一样有价值。

你也可以假设所有游戏都是独立的。基本上，我只是在寻找“护理能力”的定量指标（例如从 0 到 1 的值）。

有人对如何处理这样的事情有任何想法吗？如果你是一名经济学人，你可以想象我可以花在提高赢得比赛机会上的钱是有限的。您将如何在游戏中分配这些资金以最大化您的预期结果？

提前致谢！

编辑：对不起，我已经意识到这是一个措辞相当糟糕的问题。我没有具体说明额外投资和产出之间的关系。我想假设这是一个线性关系，但在这种情况下，你投资哪个游戏并不重要，因为它总是会以同样的方式增加你的预期价值。我的实际问题有点复杂，我需要重新考虑一下。感谢所有帮助并提出好主意的人！

是否有 Python 库可以解决两人零博弈的纳什均衡？我知道解决方案可以用线性约束写下来，理论上，scipy 应该能够优化它。但是，对于两人零博弈，解决方案是精确且唯一的，但某些求解器无法针对某些问题收敛。

我不想在 Python 网站上列出任何关于线性编程的库，而是想知道哪个库在易用性和速度方面最有效。

我最近遇到了 Gambit - http://www.gambit-project.org/doc/index.html - 一个 C++ 算法博弈论 API。

有人知道 .NET 博弈论库吗？

我知道这不是问这个问题的正确地方，但也许一个聪明的人会遇到并有解决方案。

我正在尝试编写一个电脑游戏，我需要一个算法来解决这个问题：

游戏在 2 名玩家之间进行。每边有 1.000 美元。共有三个“盒子”，每个玩家写下他要放入这些盒子的金额。然后比较这些数量。谁把更多的钱放在一个盒子里，谁得 1 分（如果每人抽半分）。谁得分多，谁就赢得他的对手 1.000 美元。示例游戏：

玩家 A: [500, 500, 0] 玩家 B: [333, 333, 334]

玩家 A 获胜，因为他赢得了 Box A 和 Box B（但输掉了 Box C）。

问题：放置资金的最佳策略是什么？

我还有更多问题要问（与算法相关，与数学无关），但我需要先知道这个问题的答案。

更新（1）：经过更多研究，我了解到这些类型的问题/游戏被称为Colonel Blotto Games。我尽了最大的努力，发现关于这个主题的（高度技术性的）文档很少。简而言之，我遇到的问题（如上所述）被称为简单的 Blotto 游戏（只有三个具有对称资源的战场）。困难的是那些拥有 10 多个非对称资源的战场。我读过的所有文件都说简单的 Blotto 游戏很容易解决。问题是，他们都没有真正说出那个“简单”的解决方案是什么。

更新（2）：我写了一个小的 actionscript 文件来演示 Tom Sirgedas 提到的论文中的策略。您可以在megaswf对其进行测试。说明：单击三角形内的一个点。红色区域代表获胜案例。蓝色区域代表失败案例，白色细线代表平局。

我们有一片生根的树林。两名玩家根据以下规则交替移动：一个移动是切割顶点及其所有子节点。最后一步（没有顶点）的玩家获胜。

我们如何计算游戏中位置的 Grundy 函数？

假设我们有一棵树，我们需要说当前位置是赢还是输？