问题标签 [minmax]

I was wondering if anyone could help me go through this question. I looked up the Min Max theory, but I still don't know how to apply this concept to this question below.

The following tree represents possible moves in a competitive game, showing that player X currently has a choice between move A and move B. Following the move of player X, player Y is allowed to select a move, and then player X is allowed to select the last move of the game. The leaf nodes of the tree are labeled W, L, or T, depending on whether that ending represents a win, loss, or tie for player X.

Use the min-max search to determine if player X should move A or B to obtain the best result X can expect.

To review min-max search, see http://www.nada.kth.se/kurser/kth/2D1350/progp02/lecture2.pdf

Player X should move A.

Player X should move B.

我正在尝试让 minmax 算法（计算机 AI）在我的井字游戏中发挥作用。我已经坚持了好几天了。本质上，我不明白为什么计算机 AI 只是简单地将其标记 ( "O") 从棋盘中按顺序放置0-8。

例如，作为人类玩家，如果我选择1，那么计算机会选择0：

接下来，如果我选择4，那么计算机将选择2：

等等：

我已经尽可能多地调试了 minmax 算法，但是很难理解正在发生的事情。

这是ComputerPlayer带有算法的类（并且没有我的所有打印语句）。该minmax方法是我遇到很多麻烦的地方。（我不是 100% 确定使用worst_score甚至相关的逻辑。）

我最近遇到了以下问题：

假设我有一个随机长度 (L) 为 0 和 1 的向量随机分布（例如 [0,1,1,1,0,0,1,0]），我需要将向量分成两个子索引 K 处的向量，因此以下条件有效：

• 左子向量必须包含来自 K 的逆序元素的最大数量，例如零的数量必须大于或等于 1 的数量
• 右子向量必须包含从 K+1 开始的最大元素个数，例如 1 的个数必须大于或等于零的个数

例如， [1,1,1,1,1,1,1,1,1,0,1,0,0,0,0,0,0,0,0] 拆分位于索引 9，左侧向量为[1,0]，右向量为[0,1]

我编写了以下解决方案，但复杂度为 O(L^2)。我认为可能有一个复杂的最坏情况 O(L) 的解决方案，但我找不到任何可以帮助我的东西。任何想法？谢谢

我正在尝试使用转置表实现增强的 alpha-beta min-max 修剪。我使用这个伪代码作为参考：

http://people.csail.mit.edu/plaat/mtdf.html#abmem

该算法的三个问题：

1. 我相信我应该在每个保存的转置表条目中存储深度（= 到叶层的距离），并且仅在 entry.depth>=currentDepth （= 条目与叶层的距离更大或相等）时才使用条目。上面的伪代码中没有显示，也没有在那里讨论，我想确保我理解正确。

2. 我想为每个位置存储最佳移动，以将其用于移动排序并在搜索停止后提取最佳移动。在纯粹的 min-max 中，哪个动作是最好的很明显，但是当使用 alpha-beta 截止值迭代时哪个动作是最好的？我可以假设给定位置的最佳移动是循环结束时找到的最佳移动（有或没有截止）吗？

3. 在迭代深化方案中执行此算法时 - 我应该在每次深度增加之前清除转置表吗？我认为不是，我希望您使用先前迭代中存储的位置，但我不确定这些信息是否足以进行更深入的搜索（应该在检查表条目深度时）？

将转置表和 MTD(f) 添加到国际象棋的纯 alpha beta 修剪中的预期性能增益是多少？

在我的纯 alpha beta 修剪中，我使用以下移动排序：

• 主要变化（来自先前的迭代深化迭代）
• 换位表的最佳移动（如果有的话）
• 捕获：最高捕获然后最低捕获
• 杀手锏
• 历史启发式

通过上述设置，我得到以下深度 9 的平均结果：

• 纯 alpha beta：访问的 X 个节点
• alpha beta+TT：访问了 0.5*X 个节点
• MTDF(f)：访问了 0.25*X 个节点

我期望得到更好的结果，我想确定它是否能得到最好的结果，或者我的实现是否有问题？

我以 0.1 pawn 的精度搜索。

需要在列表标签​​中找到最小和最大日期 像这样在一列 Min Date:01/01/2015 / Max Date:01/05/2015

需要将 Min dt 和 Max dt 作为“PoRequiredDate”添加到一列

虽然我了解 MiniMax 树和 alpha-beta 修剪概念，但我不明白为什么在许多（例如维基百科）关于 alpha-beta 修剪的资源中存在像 α >= β 这样的条件。具体来说，等于是令人困惑的。据我了解， alpha beta 返回移动 minmax 会返回，但大多数情况下它会更快。但这个例子与之矛盾：

上面是原始的 min-max 树。正如我们所看到的，它会选择得分为 3 的一步。现在让我们进行 alpha-beta：

它切断了最右边的移动，因为 3 >= 3。但是算法可以在 2 个移动之间进行选择，因为它们具有相同的分数，但是正如我们在 min-max 中看到的那样，正确的选择稍微差一些。如果算法仅指定 α > β，则不会发生这种情况，因此它也需要搜索 2。

那么这是维基百科伪代码（和许多其他资源）中的错字吗？或者我在这里误解了一些非常大的东西。

在以下代码中，我无法接受来自控制台的输入列表值。

IndexError : 列表参数索引超出范围。

找不到索引超出范围的位置。请帮助，在此先感谢。

Is there a way to only return the min/max values of an array where the min is in a lower index position than the max?

For instance, let's say we have:

If we did .minmax on this array we would get the following:

However, I'm only interested in getting the minimum value that has a lower index than the maximum value, in this case:

I've been trying to think about different ways to do this but haven't had much luck. I tried to find a way to get the min/max values where the difference between the two returns a negative value but couldn't find a way to do that.

Edit: To clarify, this is essentially intended to be a stock picker. The array elements are the prices of a stock each day. I'm interested in maximizing the difference between a min/max in the array (buy on the day when stock = 3, sell on the day when stock = 15). The values may not be the absolute min or max.

我理解#max、#min、#minmax。我理解<=>。但它是如何在其中一个函数中的一个块中工作的呢？

也就是说，下面第三行发生了什么？#min <=> 在做什么？

来自http://ruby-doc.org/core-2.2.3/Enumerable.html#method-i-min的示例

它对一组数字有什么行为？