问题标签 [game-theory]

GAMBIT 文件具有 n 玩家战略形式游戏的输入。它由每个玩家策略的收益值组成。为了对数据进行操作，需要将数据有效地存储在某种数据结构中。

由于玩家的数量和动作的数量是用户输入的，这会带来一些问题。我无法想出比线性数组更好的数据结构来存储数据。任何帮助表示赞赏。

代码需要在 C/C++/Java 中。因此，任何有关在 MATLAB 或其他软件中执行此操作的建议都将无济于事。

对于那些需要了解 GAMUT 和 GAMBIT 的人，请参阅 http://gamut.stanford.edu/download.htm

谢谢。

我目前正在为一个名为Skat的基于技巧的纸牌游戏开发一个求解器，它在完美的信息情况下。虽然大多数人可能不知道这个游戏，但请多多包涵；我的问题是一般性的。

Skat简介：
基本上，每个玩家交替打一张牌，每三张牌形成一个花样。每张卡都有特定的价值。玩家获得的分数是相应玩家赢得的技巧中包含的每张牌的值相加的结果。我遗漏了一些对我的问题不重要的事情，例如谁和谁比赛或者我什么时候赢得一墩。
我们应该记住的是，有一个运行分数，并且在调查某个位置（->它的历史）时谁玩过什么与该分数相关。

我用 Java 编写了一个 alpha beta 算法，它似乎工作正常，但它太慢了。似乎最有希望的第一个增强是使用转置表。我读到，在搜索 Skat 游戏的树时，您会遇到很多已经调查过的位置。
这就是我的问题发挥作用的地方：如果我找到一个之前已经调查过的位置，那么导致这个位置的动作会有所不同。因此，一般来说，分数（以及 alpha 或 beta）也会有所不同。
这引出了我的问题：如果我知道相同头寸的价值，但历史不同，我如何确定头寸的价值？
换句话说：我怎样才能解耦从其路径到根的子树，以便可以将其应用于新路径？
我的第一个冲动是这是不可能的，因为 alpha 或 beta 可能受到其他路径的影响，这可能不适用于当前位置，但是......

似乎已经有一个解决方案
......我似乎不明白。在 Sebastion Kupferschmid 关于 Skat 求解器的硕士论文中，我发现了这段代码（可能是 C-ish / 伪代码？）：

这应该是不言自明的。succ(p)是一个返回当前位置所有可能移动的函数。t(q)是我认为是各个位置的跑分（庄家到目前为止所获得的分数）。因为我不喜欢在不理解的情况下复制东西，所以这应该只是对任何想帮助我的人的帮助。当然，我已经对这段代码进行了一些思考，但我无法理解一件事：通过在再次调用函数之前从 alpha/beta 中减去当前分数 [例如] ab_tt(q, res - t(q), beta - t(q))，似乎存在某种解耦上。但是，如果我们将位置的值存储在转置表中而不在这里也进行相同的减法，那么究竟有什么好处呢？如果我们找到了一个之前调查过的位置，为什么我们可以只返回它的值（如果它是VALID）或者使用 alpha 或 beta 的绑定值？在我看来，从转置表存储和检索值都不会考虑这些位置的特定历史。还是会？

文献：
几乎没有英文资料涉及 skat 游戏中的 AI，但我发现了这个：A Skat Player Based on Monte Carlo Simulation by Kupferschmid, Helmert。不幸的是，整篇论文，尤其是对转置表的阐述相当紧凑。

编辑：

为了让每个人都能更好地想象在所有牌都打完之前，在 Skat 游戏中比分是如何发展的，这里有一个例子。游戏进程显示在下表中，每行一招。每墩牌后的实际分数在左侧，其中+X是庄家的分数（-Y是防守方的分数，与alpha beta 无关）。正如我所说，一招的获胜者（宣布者或防守队）将这一招中每张牌的价值添加到他们的分数中。

卡值如下：

我在游戏中使用了 MinMax 算法，因为有很多可能性 MinMax 递归需要太长时间，即使是“alpha-beta pruning”

我的代码看起来像这样：

我知道有时您可以使用for循环而不是递归，但我找不到转换它的方法。

如果有人有一个好主意，我会很高兴听到它！

谢谢，

编辑：这个问题不重复What is the best algorithm for the game 2048?

• 这个问题问'赢得比赛的最佳方式是什么？
• 这个问题问“我们如何才能计算出游戏的复杂性？”

它们是完全不同的问题。我对走向“胜利”状态需要哪些步骤不感兴趣——我有兴趣找出是否可以计算可能步骤的总数。

我一直在阅读这个关于游戏2048的问题，其中讨论了创建能够在游戏中表现良好的算法的策略。

接受的答案提到：

游戏是一个离散状态空间，完美信息，象棋一样的回合制游戏

这让我想到了它的复杂性。对于像国际象棋这样的确定性游戏，它可能（理论上）计算出所有可能导致获胜状态的移动并向后工作，选择持续导致该结果的最佳移动。我知道这会导致大量可能的移动（在宇宙中的原子数量范围内）.. 但是 2048 或多或少复杂？

伪代码：

在这一点上，我想我会在这里等待一段时间运行......

所以我的问题是——我将如何开始编写这个算法——哪种策略最适合计算游戏的复杂性？

我在 2048 和国际象棋之间看到的最大区别是，程序可以在添加新棋子时在 2 到 4 之间随机选择——这似乎增加了大量额外的可能移动。

最终，我希望程序输出一个数字，显示游戏中可能的排列数量。这可能吗？！

金盒问题（方法）

有“n”个金盒子排成一排，每个盒子都有不同数量的金币。

2名玩家玩游戏，目的是收集最大数量的金币。每个玩家都可以看到每个盒子里有多少硬币，但只能在轮到他的时候从任一端得到一个盒子。设计一个让玩家 1 获胜的策略（假设两个玩家都玩得很聪明）

这个问题在亚马逊的一次采访中被问到。我尝试了这种方法：

但我认为这是不对的，因为 player2 也很聪明。我错过了什么？

我一直在为一个编程竞赛（Andrew Stankevich Contest 21）中的一个问题苦苦挣扎，这个游戏如下所示：

尼克和彼得喜欢玩以下游戏 [...]。他们在一张纸上绘制一个无向二分图 G，并在其中一个顶点上放置一个标记。之后，他们轮流行动。尼克先行动。

移动包括沿图边缘移动标记。在它之后，标记在移动之前所在的顶点以及与其相关的所有边都从图中删除。没有有效动作的玩家输掉游戏。

给出了图表，现在的任务是寻找给定的起始节点，如果两个玩家都发挥最佳，起始玩家是赢还是输。总结

• 二分图
• 我们得到了起始节点（比如在左侧）
• 我们轮流移动，移动包括跟随一条边，但我们不能访问已经访问过的节点
• 不能移动的玩家输了

由于该图是二分图，Nick（第一个玩家）总是会从左侧删除一个节点，而 Peter 总是会从右侧删除一个节点。

该图最多可以有1000个节点（每边最多500个）和50000条边，所以需要一个好的多项式时间算法（这里的时间限制是2秒来解决所有起始位置，但我认为我们可以分享很多不同起始位置之间的信息）。

我很确定这可以简化为某种顶点覆盖或打包问题，因为该图是二分图，但我找不到与其中任何一个相关的策略。

我知道一个特殊情况的解决方案：假设边分别有n ₁和n ₂个顶点。如果存在大小为min(n ₁ , n ₂ )的匹配并且如果较小一方的玩家开始，则存在获胜策略：他只需遵循匹配的边缘并自动获胜。

有任何想法吗？

在游戏2048中，可以达到的最大牌是多少，假设玩家玩得最佳并且牌在最佳位置生成？

天真地我会说最大的可实现瓷砖是65536 * 2 = 131072因为似乎最好的板如下：

但我不确定是否

1. 这是正确的
2. 如何证明我的直觉确实是正确的。

（对不起，如果我应该在Gaming.stackexchange上提问，但这更像是一个 CS 问题，而不是一个游戏问题）

我正在用 Python 编写博弈论模拟。作为模拟的一部分，每一代，两个玩家配对并相互对抗（每个玩家都是Player1orPlayer2类的一个实例）。稍微简化一下，代码如下所示：

收益被保留为玩家的一个属性。在每一轮结束时，根据玩家的移动，游戏将继续或结束（play_game将分别返回 True 或 False）。

如何使此代码并行运行？也就是说，我怎样才能同时玩超过 1 对玩对方？我用谷歌搜索了一下，发现了 Python多处理库，但我不知道如何将它应用到这段代码中。

谢谢！

问题定义

我有n容量相同的水桶m，一个接一个。我可以将水从一个桶倒到它右边的那个。目标是将它们全部倒入另一个容器中，但只能清空最右边的桶。它们每个都有一定的初始水量w，其中0 <= w <= m和w是整数。从某种意义上说，如果您遇到以下情况：6 6 -> 3 9，您只倒 3，则您不能进行部分移动，这是不允许的。如果你倒，你必须尽可能多地倒，所以合法的移动是 6 6 -> 2 10。

为了清空所有的桶，我必须做的最少移动次数是多少？桶的最大数量为 1000，最大容量为 100。

例子

示例 1

4 桶容量 10 与以下水量：4 0 6

答案是 4 0 6 -> 0 4 6 -> 0 0 10 -> 0 0 0，即三步。

示例 2

3 桶容量 10, 8 9 3

8 9 3 -> 8 2 10 -> 0 10 10 -> 0 10 0 -> 0 0 10 -> 0 0 0 = 总共 5 次移动

我首先尝试使用不同类型的算法（贪婪、动态、回溯等），但似乎都没有。我以为我找到了一个非常直观的解决方案，但检查这些答案的程序告诉我这是错误的，所以我可能错了。另一件事是这个程序以前拒绝了正确的答案，所以我不太确定。

这是我的解决方案：

计算每个桶之前所有桶的总和，然后将该数字的上限除以桶的容量，然后将所有这些数字相加。

例如：6 6 6 6 6 -> 6 12 18 24 30

ceil(6/10) ceil(12/10) ceil(18/10) ceil(24/10) ceil(30/10) = 1 + 2 + 2 + 3 + 3 = 11

这是正确的答案：6 6 6 6 6 -> 6 2 10 6 6 -> 0 8 10 6 6 -> 0 8 10 2 10 -> 0 8 2 10 10 -> 0 0 10 10 10 -> 0 0 10 10 0 -> 0 0 10 0 10 -> 0 0 10 0 0 -> 0 0 0 10 0 -> 0 0 0 0 10 -> 0 0 0 0 0 = 11 步

逻辑是，如果L在某个桶之前有一升水，那么至少必须有ceil(L/Capacity)经过该位置的移动。到目前为止，我已经尝试了大约 30 个测试用例，它们都奏效了。每次我以为我找到了一个反例，我手动尝试了几次后才意识到我错了。问题是，虽然我很确定这是正确的答案，但我不知道如何证明这样的事情，否则我可能只是错了。

有人可以告诉我这个答案是否正确吗？

在可转移效用特征函数博弈（合作博弈论）中，最著名的解决方案概念是博弈的核心，定义为任何联盟都无法改进的可行收益分配的集合。在几何上，核心是一个封闭的凸多面体： http: //www.jstor.org/stable/2630190

在这些游戏中，收益分配要么在核心，要么不在。TUGlab 工具集有一个命令可以计算支付分配是否在核心中： http ://webs.uvigo.es/mmiras/TUGlab/ 但是没有命令可以告诉你确切的一定的收益分配距离是核心。如果核心的几何表征是一个封闭的凸多面体，那么应该有一种方法可以将点与该多面体之间的几何距离计算为特征函数的“到核心的距离”。不幸的是，我没有找到任何论文真正向我展示了我可以在 MATLAB 中实现的计算这个距离的公式或算法。

我的猜测是斯蒂芬卡梅隆的代码中可能有一个计算两个多面体之间距离的线索。但我的问题应该比这更简单：只是一个点和一个多面体之间的距离。最后，我需要一个 MATLAB 程序，将 a) 特征函数和 b) 收益分布作为输入，然后将收益分布与特征函数核心之间的距离作为输出。当然假设核心是非空的。