问题标签 [game-theory]

https://www.hackerrank.com/challenges/chessboard-game-again-1

我以以下方式尝试了上述问题，但答案被评估为错误。（我不是在寻求解决方案，而是在寻求方法中的缺陷）；

我的代码（请忽略 c99 错误）

我的方法是继续使所有硬币的所有移动都成为可能，直到我们到达无法移动的地步。但这在某些测试用例中给出了错误的答案。

我有一个问题，其目的是计算由圆的一组点形成的轴对齐最小边界框的面积。

IE

x - x 坐标，y - y 坐标和半径

关于如何处理的任何提示？

总结一下这个游戏，有 N 个高度为 M 的塔，每回合玩家可以将塔减少到除以它的高度但不等于它的高度的数字，目标是让你的对手在轮到他了。

例如，如果N=2,M=2第一个玩家输了，因为他唯一能做的就是将其中一个塔降低到高度 1，之后另一个玩家可以做的唯一动作是将另一个塔降低到高度 1，现在第一个玩家有没有动作可做。

我开始写这个，但它变得太复杂了，我无法真正看到非素数M的“模式”，例如4. 有没有更好的方法我应该考虑这个？

我计算玩家 1 或 2 是否会赢的方法是

编辑：哇，我只是做了一个疯狂的猜测

它通过了挑战问题的所有测试用例。所以我在不明白为什么的情况下“解决”了它。

一个天真的脱落纸牌游戏

给定一个简单版本的脱落型纸牌游戏（实际上是中国最流行的游戏斗地主的幼稚版本（https://en.wikipedia.org/wiki/Dou_dizhu）），我们如何确定获胜者（每个玩家最多可以有 20 张牌）（是否存在解决问题的线性算法）？

游戏的目的是在对手面前摆脱手上的所有牌。玩家分别称为 A 和 B。牌的等级是：

3 < 4 < 5 < 6 < 7 < 8 < 9 < T < J < Q < k < A < 2 < r < R （其中 T 是 10，r，R 是小百搭和大百搭）

定义1 ：可以丢弃任何符合Give-Out-Rule的牌的玩家称为First Discard玩家，而只能丢弃比之前丢弃的牌更高等级的牌的玩家称为Beat Discard玩家。

A 是第一个弃牌的玩家，因此 A 在开始时始终是 First Discard 玩家。如果一个人选择不弃牌（因为他选择不弃牌或找不到有效的牌可以弃牌），那么另一个人成为First Discard 玩家。

给出规则1：每个玩家最多可以丢弃一张牌，即使你有多张相同等级的牌，你也只能丢弃其中一张。

示例 1：B 获胜者 4,4,5 < B：3,4,4,8,T

说明：B 永远是赢家，因为对于 A 可以选择的任何策略，B 总能找到导致 B 获胜的弃牌策略。

Example2: A 赢家 4,4,5,R > B: 3,4,4,8,T

说明：A 永远是赢家，因为存在一种策略 A 可以选择使用导致 A 获胜的策略，而不管 B 选择反应的策略。

红色和蓝色表示 A 和 B 的状态（手中的牌）。

多边形和盒子形状表示播放器处于FirstDiscard 播放器状态和BeatDiscard 播放器状态。

拖卡组的相对图(A: 4,4,5,R > B: 3,4,4,8,T)

1. 每张卡的 Bp 值表示该卡可以用来击败对手的卡的可能性。

2. 具有相同 Bp 值的卡片形成一个块。

研究进展

目前，我只能使用游戏搜索树方法来确定获胜者，但这些方法处理时间太长。Give out Rule1其实是我研究的第一步，下面的研究给出的规则是：

定义2 ：单卡定义为具有特定等级且计数为1的卡。而pair-card、trio-card、four-card被定义为具有特定等级的卡片，其计数为二、三、四。

定义3 ：单卡、双卡、三卡、四卡也称为独立卡

出规则2：每位玩家每次只能弃一张独立牌，如果玩家处于BeatDiscard玩家状态，他只能弃掉之前弃牌的同种独立牌，等级较高。不允许使用拆分卡。（如果你有三张牌555，你不能把这张牌分成单牌5和对牌55）

发放规则 3：与发放规则2 相同，但允许拆分卡。

定义4 ：单卡的三卡称为三单踢卡，等级与三卡相同。

定义5 ：有对子牌的三人牌称为三人对踢牌，名次与三人牌相同。

定义6 ：四张两张单卡称为四二单踢卡，等级与四张相同。

定义7 ：四张有两张对子的叫四张二对起脚牌，点数与四张相同。

放弃规则 4：与放弃规则3 相同，允许丢弃四种额外的卡类型（从 Def4 ~ Def7）。

定义8：四张牌也叫炸弹牌，可以用来打败所有其他牌类和四张牌（6666可以打败33、5555、3331、8888KJ）

定义9：rocket-card是 r 和 R 的组合，它可以击败所有其他卡类型。

放弃规则 5：与放弃规则4 相同，允许丢弃额外的卡类型（从 Def8 ~ Def9）。

给出规则6：玩家C加入B的队友，他将在B之后弃牌，B或C首先弃掉所有手牌将成为B和C的赢家。

我相信Give out Rule1~Rule3存在线性算法，有人可以提供这样的方法和相关信息，或者证明问题是指数的。

好的，所以我正在用 Java 创建一个程序，它应该接受一个标准输入

其中第一个数字表示必须执行 IESDS，第二个输入 (2) 表示玩家数量，3 3 分别表示每个玩家的动作数。下面的矩阵是收益矩阵。

我真的被困在如何通过矩阵并根据纯或混合严格支配策略确定应该删除哪个动作。我想不出一种方法来遍历 2d 矩阵并比较玩家 1 的行和玩家 2 的列。我知道第一个淘汰应该是最后一列

玩家 2 的第三个动作。留下下面的矩阵进行下一次迭代：

我刚刚看到了关于游戏树和 MinMax 算法的 MIT 讲座，其中讨论了 Alpha Beta 修剪和渐进深化。
https://www.youtube.com/watch?v=STjW3eH0Cik

因此，如果我理解正确，渐进深化是当您尝试在每个级别近似答案并尝试根据您移动的时间限制深入叶节点时。在任何时候都有一些答案很重要。现在，在36:22 ，教授讨论了我们没有足够时间的情况，我们只去了第 (d-1) 层，其中 d 是树的深度。然后他还建议我们可以在每个级别都有一个临时答案，因为我们应该在任何时间点都有一些近似答案。

我的问题是我们如何在不去叶节点的情况下得到任何答案，因为只有在叶节点我们才能断定谁可以赢得比赛。认为这是井字游戏。在第 (d-1) 级，我们没有足够的信息来决定直到 (d-1) 节点的这一系列移动是否会赢得我或输掉比赛。在更高的水平上说在（d-3）它更加模糊！当我们下降时，一切皆有可能。不是吗？因此，如果算法决定计算直到 (d-1) 层，那么所有这些路径选项都是相等的！没有什么能保证赢，也没有什么能保证在（d-1）级输，因为如果我理解正确，只能在叶节点上计算输赢。在纯 MinMax 算法中尤其如此。

那么我们将如何在第（d-1）级或说第（d-5）级获得“近似答案”？

我想知道是否有一种简单的方法可以在这里看到这种模式。我已经考虑了好几个小时，但无法完全制定它。

游戏的运作方式是有 2 个玩家，N石头塔，当轮到玩家时，他必须从塔中移除至少 1 块石头，移除最后一块石头的玩家获胜。

这是我到目前为止绘制的内容，作为获胜者的塔高度地图：

我得出的事实：

• 如果每座塔有1个石头，如果塔数为奇数，则轮到的玩家获胜，否则输
• 如果塔的数量是N并且任何塔的高度大于N+1，则结果与该塔的高度相同N+1

除此之外，我想不出足够的模式来编写线性解决方案。

有什么帮助吗？

我目前正在研究组合博弈论，并且正在尝试使用神经网络开发人工智能。我最初的方法是获取游戏的统计数据并将其用作输入，并训练我的神经网络为这些输入开发最佳权重配置，以获得这些输入的最大输出值。每组输入代表一个动作，通过将每个动作（输入 x 权重）传递给神经网络，我可以找出哪个动作具有最大值。因此，这一举措将是最好的举措。

这都是理论上的，我只是好奇在不知道期望值的情况下构建神经网络是否是可能的。如果这看起来不合理，是否有任何其他算法我应该研究这类问题？

感谢您的任何反馈，在此先感谢您。

我正在尝试为类似于井字游戏的游戏编写 AI 代码。你可以在这里看到它的规则。

我正在使用的 min-max 算法和分析函数可以在这里找到

到目前为止我尝试过的方式：

1. 我已经建立了一些对当前玩家有益的模式。（在 Python 中）

例如my_pattern = " ".join(str(x) for x in [piece, None, piece, piece, None])

2. 我将这些图案与每块六角游戏板上的所有 6 个可能方向进行匹配（而不是空格）。准确地说，匹配my_pattern6 个不同的阵列（每个阵列代表 6 个不同方向之一）。

现在，这个分析函数实际上应该计算什么？

1. 整个棋盘状态的得分？
2. 船上最后一步的得分？

如果有人可以准确地描述分析功能的目的，那就太好了。

我正在为比赛设计一个决策系统，要求玩家瞄准不同的目标。在不同目标上得分的概率各不相同，每个目标上得分的球员越多，在那个目标上得分的概率就会降低。球员的尝试机会有限。

我想到的只有马尔可夫链和博弈论，但我不知道如何实现它们，我想知道是否有任何其他数学技术可以最大化我的分数。

我将非常感谢任何指导。