标签: minimax

我想为9名男子莫里斯比赛建造一个游戏树.我想在树上应用minimax算法来进行节点评估.Minimax使用DFS来评估节点.那么我应该首先构建树到达给定的深度然后应用minimax,还是构建树和评估的过程可以在递归的minimax DFS中一起进行？

谢谢Arvind

极小极大算法的描述说，两个玩家都必须发挥最优，这样算法才是最优的。直观上是可以理解的。但是有没有人能具体说明一下，或者证明如果 min 发挥不理想会发生什么？

谢谢

我想开发一个具有不完全信息的双人游戏 - "Stratego".

这场比赛"有些"像国际象棋,但最初我们对对手的棋子不了解.当一件作品被一些对手的作品攻击或攻击时,他们的等级被揭示出来并且较高等级的作品杀死/捕获较低等级的作品.有关游戏的更多细节可以在这里找到.

我做了一点研究.我读了JA Stankiewicz撰写的"Stratego中的对手建模".但我找不到关于如何开发游戏的完整教程.我已经成功开发了一款双人游戏 - "Othello"又名Reversi,我熟悉MINIMAX算法和alpha-beta修剪.

我发现蒙特卡罗树搜索也用于开发零和二玩家游戏.它可以用于像Strategiesgo这样的游戏吗？我可以获得相同的完整教程吗？

任何其他不涉及蒙特卡罗树搜索的教程也很有用:)

我必须做一个我们需要实现mancala棋盘游戏的项目,然后为它实现AI.

我们已经被指示我们需要修改或更改minimax树以便能够与mancala一起工作,因为在游戏中玩家可以连续多次转弯.

我已经实现了我的游戏逻辑和GUI,但是在我开始使用AI之前,我想尝试一下它背后的理论.我在网上搜索了非转弯的迷你最大树,我似乎无法找到任何东西.但是我看到很多人都在谈论使用minimax来制造mancala.

现在我理解了正常的minimax树以及每个级别如何在最小节点和最大节点之间交替.有了我现在需要的树,我会说: min > max > max > min > max如果第二个玩家得到两个转弯？

我们还需要能够指定Minimax树的给定层深度.我们还需要进行alpha beta修剪,但是一旦我实际拥有一棵树,那就是以后的修剪.

有一个我用java编程的游戏.游戏很简单(参见下图).有4只鸟和1只幼虫.这是一个2人游戏(AI vs Human).

• 幼虫可以沿对角线向前和对角向后移动
• 鸟只能向前倾斜
• 幼虫如果可以到达第1行(围栏)则获胜
• 如果鸟类没有动作,幼虫也会获胜
• 鸟不能"吃掉"幼虫.
• 如果幼虫没有向左移动(根本无法移动),鸟类会获胜

当比赛开始时,幼虫开始,然后一只鸟可以移动(任何一只),然后是幼虫等......

我已经实现了MiniMax(Alpha Beta Pruning),我使用了以下的evaluate()函数(启发式函数).

让我们给板上的每个方块提供以下数字.

因此,我们的评估功能将是

h(n)=幼虫的位置值 - 鸟的位置值1 - 鸟的位置值2 - 鸟的位置值3 - 鸟的位置值4

幼虫将尝试最大化启发式值,而鸟类将尝试最小化它

例:

但是,这是一个简单而天真的启发式方法.它不会以聪明的方式行事.我是AI的初学者,我想知道如何改进这个启发式功能？

什么是好的/知情的启发式？

我已经使用换位表实现了 alpha beta 搜索。

关于在表中存储截止值，我有正确的想法吗？

具体来说，我在发生表命中时返回截止值的方案是否正确？（同样，存储它们。）我的实现似乎与此冲突，但直观上对我来说似乎是正确的。

另外，我的算法从不存储带有 at_most 标志的条目。我应该什么时候存储这些条目？

这是我的（简化的）代码，演示了主要思想：

int ab(board *b, int alpha, int beta, int ply) {
    evaluation *stored = tt_get(b);
    if (entryExists(stored) && stored->depth >= ply) {
        if (stored->type == at_least) { // lower-bound
            if (stored->score >= beta) return beta;
        } else if (stored->type == at_most) { // upper bound
            if (stored->score <= alpha) return alpha;
        } else { // exact
            if (stored->score >= beta) return beta; // respect fail-hard cutoff
            if (stored->score …

https://leetcode.com/problems/guess-number-higher-or-lower-ii/#/description。

我们正在玩猜谜游戏。游戏如下：

我从 1 到 n 中选择一个数字。你必须猜出我选的是哪个号码。

每次你猜错了，我都会告诉你我选的数字是高还是低。

然而，当你猜到一个特定的数字 x 时，你猜错了，你要支付 $x。当你猜到我选的数字时，你就赢了。

给定一个特定的 n ? 1，找出您需要多少钱（至少）才能保证获胜。

我正在练习这个问题。我认为这个问题可以使用二分搜索来解决。特别是，对于最坏的情况，可以始终假设该数字位于每个拆分的右半部分。

示例：假设 n=5。那么你有

[1, 2, 3, 4, 5]。

第一次尝试= 3？然后第二次尝试 = 4。这会给你 7 美元的最坏情况。但是我看过解决方案，在我看来它们都使用动态编程。我想知道为什么在这种情况下二进制搜索算法不起作用？

我在游戏中使用alpha-beta修剪实现了迭代加深，并且还添加了一个“换位表”来存储已经评估过的板子。

现在，我正在执行以下操作：

1. 进行迭代加深时，深度= 0时，它将评估所有位置并将其分数存储在TT中。
2. 现在，当它以depth = 1重新运行时，如果TT中存在该板的值，我就简单地返回它。这将在深度= 0处停止算法，因为深度= 0板的所有值都已在TT中。

如果达到深度极限时，例如，我从TT返回值。depth = MAX_DEPTH，那么大子树将永远不会被剪切。

因此，我不了解如何重新使用TT中存储的值来提高游戏速度？

我最近报名参加了 CS50 AI python 课程，要做的项目之一是为井字棋游戏实现极小极大算法。我寻求帮助并搜索了 stackoverflow，但没有找到可以帮助我的答案。它的图形部分已经实现了，您需要做的就是对模板的给定功能进行编程，我相信除了算法部分之外我都做对了，功能如下：

import math
import copy

X = "X"
O = "O"
EMPTY = None


def initial_state():
    """
    Returns starting state of the board.
    """
    return [[EMPTY, EMPTY, EMPTY],
            [EMPTY, EMPTY, EMPTY],
            [EMPTY, EMPTY, EMPTY]]


def player(board):
    """
    Returns player who has the next turn on a board.
    """
    if board == initial_state():
        return X

    xcounter = 0
    ocounter = 0
    for row in board:
        xcounter += row.count(X)
        ocounter += row.count(O)

    if xcounter == ocounter:
        return …

我在 python 中创建了一个连接 4 AI，我为此使用了带迭代深化和 alpha beta 修剪的 minimax。对于更大的深度，它仍然很慢，所以我想实现一个换位表。在阅读它之后，我想我得到了一般的想法，但我还没有完全让它发挥作用。这是我的代码的一部分：（minimax 的最大化部分）：

    if(isMaximizing):
    maxEval = -99999999999
    bestMove = None
    # cache.get(hash(board)) Here's where i'd check to see if the hash is already in the table 
    # if so i searched for the best move that was given to that board before.

    # loop through possible moves
    for move in [3,2,4,1,5,0,6]:
        if moves[move] > -1:
            # check if time limit has been reached for iterative deepening
            if startTime - time.time() <= -10:
                timeout …