问题标签 [game-theory]

在我们的游戏中有几个实例，我们希望在给定预期输出值的情况下随机化“支出”。例如，我们不是每次都奖励“10 个学分”，而是希望从长远来看平均奖励 10 个学分，并加入一些随机性，目的是让它变得更“有趣”，让它变得有点不可预测。

随意更改它甚至使其成为正态分布很容易，但这并没有真正针对“乐趣”进行优化。用户在 5 到 15 积分之间的效用差异相对较小，但如果有机会偶尔赢得 100 积分，那将是一个很大的抽奖，值得期待。

有没有针对赌徒优化的算法？它基本上是一个超级简单的老虎机——我希望有人做过研究，以确定是什么让这种东西上瘾和有趣，但我什至不知道从哪里开始寻找这样的东西。

假设我们有一个迷宫游戏，在 20*20 网格迷宫中有 1 只老鼠和 4 只猫。假设迷宫中的每个智能体都可以移动 N、E、S、W。对于这个巨大的博弈树中每个节点的子节点数量，您最好的猜测是什么？

这是我最好的猜测，但我不确定，有什么想法吗？

我是神经网络初学者。我想通过教计算机下跳棋来学习神经网络的基础知识。其实我想学的游戏是霸气和妖术。

这些游戏很容易存储，规则也比国际象棋简单得多，但玩的人并不多。如果我能把这个想法付诸实践，那对于试验组合博弈论将是非常棒的。

PyBrain似乎是 Python 神经网络的明显赢家，但谁能指导我如何为我的游戏任务设置神经网络？谷歌搜索在 2001 年出现了Blondie24，但它使用了一些遗传算法——我不想让事情复杂化。

我是机器学习初学者。我想通过教电脑玩跳棋来学习基础知识。其实我想学的游戏是霸气和妖术。我选择的语言是 Python

这些游戏很容易存储，规则也比国际象棋简单得多，但玩的人并不多。如果我能把这个想法付诸实践，那将非常适合尝试组合博弈论，看看是否有一台计算机并找到最佳移动。

我在 IBM 的一个人发现了1960 年代关于跳棋的这篇旧论文。最初我曾询问过神经网络，但他们说这是错误的工具。

编辑：机器学习可能不是正确的策略。在这种情况下，出了什么问题？什么是更好的方法？

最近学习了元素堆的 Nim 游戏的基本策略。然后必须选择一堆并从该堆中删除任意数量的元素。我发现了一些据说是 Nim 的问题，但我无法将其转换为代表堆的标准 Nim 问题。

问题说有一个像国际象棋一样的方形棋盘 - 这里只有典当。所以在每一列中都有两个棋子 - 一个白色的和一个黑色的。没有棋子可以超越它，但它可以来回移动，这与国际象棋不同，棋子只能向前移动。他们不能像国际象棋那样通过吃掉对手的棋子来改变列。当任何一方没有选择让步时，游戏结束。给定棋子的初始配置，程序需要输出获胜者 - 白/黑。

关于如何将其转换为标准的任何想法？

游戏名为 wizwoz：

两个玩家，红色（称为 r）和金色（称为 g）最初选择两个值 n 和 k。创建一个 n × n 的棋盘，其中 k“r”和 k“g”随机放置在棋盘上。从玩家 r 开始，每个玩家将他/她的字母（玩家 r 为“r”，付款人 g 为“g”）放在棋盘上的一个空方格中。棋盘填满后，每个玩家的分数等于棋盘上用该玩家颜色填充的最大连接区域（其中连接区域是一个区域中的任何两个方格都存在仅由 N/S/E 组成的路径/W 移动）。得分最高的玩家获胜，并获得他/她的得分与其他玩家得分之间的差额。下面显示了两个已完成游戏的示例，其中列出了每个玩家的最大连接区域。

我正在编写 alpha-beta 修剪算法并坚持使用评估函数。

有什么帮助吗？最好使用伪代码。

There are 3 popular beach resorts, A, B, and C, which reside on a line:

The distances between the resorts is 1k. John owns an ice-cream truck located in beach resort A and another located in beach resort C. Two busses full of ice-cream-craving children will arrive at the beach resorts (A, B, and C) tomorrow, but John does not know for which resort each bus is headed and when each bus will arrive (the busses can arrive at different times). He plans to dispatch an ice-cream truck from its current location to a beach resort as soon as a bus arrives at that resort. Each truck can only serve a single beach resort, that is, once a truck is dispatched to a beach resort it must remain there all day. John wants to design an algorithm that minimizes the sum of distances his trucks traverse in order to reach the busses’ locations.

Show that for every deterministic algorithm ALG, there is some scenario (i.e., schedule and locations of bus arrivals) in which the total distance John’s trucks traverse under ALG is 3OPT, where OPT is the value of the optimal solution in that scenario.

我一直在努力弄清楚 MinMax 算法是如何工作的，希望 alpha-beta 修剪算法能够工作。我对发生的递归感到困惑。

• 首先，每个中间板都得分吗？或仅终端游戏板。
• 其次，返回的究竟是什么？程序如何知道下一步该放在哪里？我看到我应该返回棋盘分数（在tictactoe中，-1,0,1）但是程序如何知道接下来应该播放哪个动作。

我曾尝试找到一个简单的 C 或 C++ 程序来证明这一点，但我运气不佳。我正在尝试学习这个算法，我可以为我的计算机编程课的其余部分创建一个演示文稿。

非常感谢！五

我在这里问这个，因为我在代码厨师论坛上没有得到答案。

在 codechef 的线程。

这是我解决的第一个问题。我收到 TLE 错误。

问题 - ASTRGAME。

所以我最初的方法是创建一个Min-Max 游戏树。这是我最近的解决方案。

伪码算法是：

（我认为这是正确的）。

所以想法是，它递归地分支出来，但如果它找到一个肯定会获胜的分支，那么它可以跳过该级别的其他分支。

但是，当然，我遇到了 TLE 错误，所以我在这里查看了执行此操作的指南。

社论建议使用Sprague-Grundy 定理。阅读了一些关于使用 SG 定理的内容。几个好的来源 ：一二 。

现在，这两个教程都在 Nim 游戏的背景下讨论 SG 定理。使用 Nim，-我知道您不需要递归地分支树来查找每个游戏的 grundy 数字，您可以从一开始就应用 XOR 函数，并立即解决它。（你不需要为 nim 扩展树的原因是因为你知道一堆 N 个硬币，有一个糟糕的 N - 你通过思考知道这一点 - 例如，一堆 3，扩展可以是一堆2、1还是0，一堆2可以是0、1，一堆1只能变成0，所以1的grundy数是1，2的grundy数是2，3有一个3 的脏数字...）。

同样，对于本教程中提到的马棋游戏，我们可以对棋盘上每个位置的粗略数字进行预处理，并为我们的棋盘配置查找这些粗略数字并应用 XOR 函数。

但是我发现我们如何将其应用于这个问题并不是那么清楚。甚至社论似乎也暗示涉及一些递归：

游戏分为两个子游戏，S(i, a-1) 和 S(b+1, j)。因为玩家可以在他/她的回合中选择任何游戏，所以游戏的 Grundy 数只是两个子游戏的 Grundy 数的 XOR。

即 - 它似乎仍然涉及扩展树直到你找到一个失败的位置，然后传递它。

即是这样的：

我看不出这与 min-max 解决方案有根本的不同。实际上 - 是不是 min-max更快？- 因为 min-max 一旦找到获胜的分支就可以退出，而 SG 需要继续尝试每个单词。

所以，要么我需要澄清我对 SG 定理的使用，要么这只是优化我当前算法的问题。例如，我认为我不需要每次迭代都进行字符串搜索，我可以只存储索引位置。

我正在尝试对下面的图形问题进行分类或找到其解决方案的提示。

有一个（邻接）矩阵可以包含 3 种类型的元素：单位、点和简单地形。

地形没有特定的含义。

单位有一个位置（x,y 由矩阵定义）和它们可以获取的点数。
点有一个位置（x,y 由矩阵定义）。
获取一个点的成本是一个点和一个单位之间的曼哈顿距离。
每个点只能由一个单位获得。

问题是：如何找到单位获取点的最小成本配置，使得单位的所有资源都被耗尽？

示例：
u1 可以获得 3 分
u2 可以获得 2 分

最佳解决方案之一是：

（此配置的最低要求）

注意：我已经尝试使用统一成本搜索和 A*（使用简单的启发式算法）来解决这个问题，但即使对于小尺寸的矩阵，我也会得到非常多的状态并且内存不足。