问题标签 [game-theory]

我正在尝试学习人工智能以及如何在程序中实现它。最容易开始的地方可能是简单的游戏（在本例中为井字游戏）和游戏搜索树（递归调用；不是实际的数据结构）。我在有关该主题的讲座中发现了这个非常有用的视频。

我遇到的问题是对算法的第一次调用需要很长时间（大约 15 秒）才能执行。我已经在整个代码中放置了调试日志输出，似乎它调用了算法的某些部分的次数过多。

以下是为计算机选择最佳移动的方法：

makeMove如果该点为空并返回一个值（-1 - 人类获胜，0 - 平局，1 - 计算机获胜，-2 或 2 - 否则），则该方法进行移动。虽然我相信错误可能出在getAllLegalMoves方法中：

总而言之：是什么导致我的电话，选择最好的举动，花了这么长时间？我错过了什么？有没有更简单的方法来实现这个算法？任何帮助或建议将不胜感激，谢谢！

我正在尝试实现一个单人井字游戏，其中计算机玩家永远不会输（每次都强制平局或获胜）。在四处搜索之后，似乎使用极小极大策略是相当标准的，但我似乎无法让我的算法正常工作，这导致计算机选择了一个非常糟糕的举动。谁能帮我找出我的代码哪里出错了？

“O”是用户（最大），“X”是计算机（最小）

编辑：我重新发布了我的代码，我已经修复了 getComputerNextMove 中的一些东西和一些小错误......现在我的代码正在寻找更好的分数，但如果有人获胜，它并不总是会出现（这些功能似乎是好吧，我想我只是没有检查正确的位置）。它也没有选择最好的举动。底部有一些测试器功能可以查看极小极大如何工作/测试游戏状态（获胜者/平局）。

tictactoe.js：

索引.html：

CSS：

在Arthur 的建议下，我将我的Fixpoint关系改为一种相互Inductive关系，这种关系“建立”了游戏之间的不同比较，而不是“向下钻取”。

但现在我收到一条全新的错误消息：

我认为错误消息是说我需要为所有这些互归纳定义使用相同的确切参数。

我意识到有一些简单的技巧可以解决这个问题（未使用的虚拟变量，长函数类型，其中包含所有内容forall），但我不明白为什么我应该这样做。

有人可以解释这种对互归纳类型的限制背后的逻辑吗？有没有更优雅的方式来写这个？这种限制是否还意味着对彼此的归纳调用都必须使用相同的参数（在这种情况下，我不知道有任何黑客可以节省大量的代码重复）？

（所有类型和术语的定义，例如 compare_quest、game、g1side 等，与我在第一个问题中的定义没有变化。

在 CGT 中，通常两个玩家（名为Left和Right）轮流玩游戏，最后一步的玩家获胜。每个游戏（意味着游戏中的每个位置）都可以读为一组Left' 选项和一组Right' 选项写为{G_L | G_R}。在比较两个游戏时，他们可以通过以下四种不同方式中的任何一种进行比较：<、>、=或||。

一个游戏是A < BifB绝对比Afor好Left，不管谁先走。A > BifA比Bfor好Left。A = B如果两个游戏是等价的（从某种意义上说，游戏的总和A + -B是零游戏，所以先走的玩家输了）。而且，A || B如果哪个游戏更适合Left取决于谁先走。

检查两个游戏之间比较的一种方法如下：

• A <= B如果所有A的Left孩子都是<| B并且A <|所有的孩子都是B正确的孩子。

• A <| BifA有一个右孩子，<= B或者如果A <=有任何一个B左孩子。

• 并且，同样对于>=和>|。

因此，然后通过查看这对关系中的哪一对适用于两个游戏Aand B，可以确定是A < B( A<=Band A<|B)、A=B( A<=Band A>=B)、A > B( A>=Band A>|B) 还是A || B( A<|Band A>|B)。

这是关于 CGT 的 wiki 文章。

我过去曾在 LPC 中为 MUD 做过一些志愿者游戏编程，一切都很简单。如果我想要一个新项目，我会使用一个函数来加载（例如 NPC）任意多次。现在我想编写我自己的小游戏，我一生都无法确定我什至需要做什么。如果我得到的只是我想做的事情的名称，以便进行自己的进一步研究，那就足够了。在谈到所有这些之后，我的问题是：

我想制作游戏中对象（例如人）的动态实例，一些由计算机处理，另一些由玩家处理。我发现很多关于游戏编程的帮助都是关于让精灵移动和处理碰撞检测。这一切都很棒，但是我想编写一个策略游戏，因此我更感兴趣的是在我的游戏中创建一些沙盒灵活性并编写 AI 以提供兴趣，而不是嗖嗖的图形和令人敬畏的声音等。我想设置具有可变数量的随机生成的人供玩家互动的游戏。到目前为止，我已经创建了一个类来处理这些人，但我现在陷入困境，因为该类的每个实例都需要一个唯一的名称，而我在其中进行编程意味着数字中没有随机性。

我需要查找什么来实现我所追求的？它会叫什么？我什至用任何程度的雄辩来解释自己？

预先感谢您对我的任何潜在帮助。

马特。

爱丽丝和鲍勃正在玩游戏。他们被赋予了 n (<50) 个介于 1-1000 之间的数字。在一个回合中，他们可以执行以下
任一操作 1.将数字减 1。2.
擦除 2 个数字并写下它们的总和。
数字达到 0 时会自动删除。如果玩家无法完成这 2 个动作中的任何一个，则该玩家输了。给定 Alice 先下棋，如果双方都打得最好，我们怎么知道谁会赢呢？

如果一个人不知道博弈论算法，这个问题可以做吗？

我试图解决这个线性规划问题：

max cx : Ax <= b, x >= 0

这是这个不错的LPP 求解器的片段：

其中第三个参数是'c'，第四个是'A'，第六个是'b'。第五给出方向'<='。

我也试过这些：

http://algs4.cs.princeton.edu/65reductions/Simplex.java.html

和

我不能在这里写它，因为我的声誉太低（http: slash slash lpsolve dot sourceforge dot net slash 5.5 slash）

第一个抛出“给定的 LPP 是无限的”错误。最后两个给出了这个结果：

原始的：{0.0, 0.1, 0.1, 0.0, 0.0, 0.3, 0.0, 0.0, 0.0, 0.0, 0.0, 0.3}

和价值：0.8。

我将这些用于其他各种示例并得到了相同的结果。

什么是正确的解决方案？我错过了什么？

我正在尝试这个关于位操作的问题是通过这个来解决的：

数字的美是该数字中设置的位数。A 和 B 开始玩游戏，棋盘上写着数字 N，轮到移动的玩家走到棋盘上写一个新的数字 NK，其中 k<=N，K 的美为 1。这也很重要NK的美必须等于N的美。最后成功完成他的动作的玩家赢得了比赛。

他们都以最佳方式玩游戏。

PS我不是在这里寻找代码。我想知道如何解决这个问题？

我一直在尝试解决http://www.spoj.com/problems/MATGAME/这个关于 spoj 的问题。这个问题可以使用 sprague grundy 定理来解决。计算每行的 sprague Grundy Number，如果这些值的 XOR(^) 为 0，则第二个玩家首先获胜。我不明白如何获得每一行的脏数字。

我正在写一篇博文来解释如何使用 Sprague-Grundy 定理来解决各种游戏问题，但我无法理解自己，我们如何定义复合游戏。

这是我到目前为止所得到的：

Sprague grundy theorem，可以用以下几点来概括

• 公平游戏中的任何位置都可以简化为一个 grundy 数字（或 nimber），其中 grundy 数字 0 是一个失败的位置（也就是说，如果对手完美地发挥，你将永远失败）。

• 任何位置都可以评估为该位置子节点的最小排他（或 mex）。例如，具有 grundy 值为 0、1、3 的子节点的位置的 grundy 值为 2。具有 grundy 值为 1、2、3 的子节点的位置的 grundy 值为 0。

现在，我想要了解的下一点是，可以将一个位置拆分为复合位置，并将该位置的 grundy 数字评估为这些复合位置的XOR。

例如：对于有两堆的 nim 游戏：

2 xor 1 = 3，因此是一个获胜的位置。

1 xor 1 = 0，因此是一个失败的位置。

我们可以使用mex方法得出这个结论：即。2,1 的子位置是：

1, 1 (0)

2, 0 (2)

0, 1 (1)

墨西哥是 3。

然而，xor 方法的重点是在不必评估子定位的情况下得出这个结论。

我们如何定义这种游戏的复合位置？

最近我遇到了一个有趣的问题。有几堆石头。两名玩家轮流从随机堆中拾取一块石头。如果玩家移动后只剩下一堆，他就赢了。这是一个例子。假设有 3 个桩。

这是问题。如果两个玩家都很聪明，那么第一个玩家是否有获胜策略？

这个问题听起来像 Nim-game 问题，但规则不同。我是博弈论的新手，所以我希望得到一个清晰易懂的答案。

感谢您的时间和关注。