标签: alpha-beta-pruning

我目前正在使用min-max和Alpha-beta修剪为othello开发一个简单的AI.

我的问题与董事会状态的评估功能有关.

我目前正在考虑通过计算来评估它

1)光盘数

2)没有合法行动

3)特定职位的重要性

因此,假设根节点是初始游戏状态.第一个动作是AI的动作,而第二个动作是对手的动作.

                   0    
                  / \           AI's Action
                 1   1
                / \   \         Opponent's action
               2   2   2

在节点级别1,我是否会评估我的AI芯片的光盘数量以及它在完成操作后的时间点可以进行的合法移动数量？

在节点级别2,我是否评估对手的筹码的盘数以及在对手完成动作之后它可以进行的合法移动的数量？意思是AI移动 - >对手移动==>此时我评估对手的盘数和对手可以合法的数量.

只是想检查我是否在正确的道路上,因为计算刚刚完成一个动作的玩家的合法移动数量感觉很奇怪.

谢谢和问候,Nat

我想开发一个具有不完全信息的双人游戏 - "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修剪,但是一旦我实际拥有一棵树,那就是以后的修剪.

我理解杀手启发式背后的想法以及它为什么有帮助。我正在努力解决的是如何在 Alpha-Beta 搜索例程中实现它。特别是如何保证只先尝试兄弟节点的杀手级动作？伪代码会有很大帮助。

我写了一个极小与算法的alpha beta剪枝的游戏跳棋,现在我想使用重写它negamax方法.我期待这两者是等价的,因为negamax只是一种编写极小极大的技巧.但由于某种原因,我的两种算法表现不同.当我在相同的输入上运行它们时,negamax版本似乎评估了更多的状态,所以我认为alpha beta修剪必定是错误的.

下面的代码显示了算法(minimax和negamax函数),并在底部显示了play我称之为的函数.该evaluate函数是我用来评估两种算法中的状态的基本启发式算法.

任何有关发现错误的帮助都会受到很多关注.

#include "player.hpp"
#include <algorithm>
#include <limits>
#include <cstdlib>

namespace checkers
{

int evaluatedStates = 0;

int evaluate(const GameState &state)
{
    // FIXME: Improve heuristics.
    int redScore = 0;
    int whiteScore = 0;
    int piece = 0;
    for (int i = 1; i <= 32; ++i)
    {
        piece = state.at(i);
        if (piece & CELL_RED) {
            ++redScore;
            if (piece & CELL_KING)
                redScore += …

我正在使用Python为2048游戏编写AI.它比我预期的要慢很多.我将深度限制设置为5,仍然需要几秒钟才能得到答案.起初我认为我所有函数的实现都是垃圾,但我找出了真正的原因.搜索树上的叶子数量甚至超过了甚至可能的数量.

这是一个典型的结果(我计算了叶子,分支和扩展数量):

111640 leaves, 543296 branches, 120936 expansions
Branching factor: 4.49242574585
Expected max leaves = 4.49242574585^5 = 1829.80385192 leaves

和另一个,好的措施:

99072 leaves, 488876 branches, 107292 expansions
Branching factor: 4.55650001864
Expected max leaves = 4.55650001864^5 = 1964.06963743 leaves

正如您所看到的,搜索树上的叶子数量多于使用天真极小极大时的叶子数量.这里发生了什么？我的算法发布如下:

# Generate constants
import sys
posInfinity = sys.float_info.max
negInfinity = -sys.float_info.max

# Returns the direction of the best move given current state and depth limit
def bestMove(grid, depthLimit):
    global limit
    limit = depthLimit
    moveValues = {}
    # Match each move to its …

虽然我理解MiniMax树和alpha-beta修剪概念,但我不明白为什么在许多(例如维基百科)有关alpha-beta修剪的资源中存在像α> =β这样的条件.具体来说,平等是令人困惑的.据我所知,alpha beta返回minmax将返回的移动,但大部分时间更快.但这个例子与它相矛盾:

        .
      / |  \
    1   3*   2
  / |  / \   | \ \
  1 1 5   3  4 3 2

以上是原始的最小 - 最大树.正如我们所看到的,它将选择一个得分为3的移动.现在让我们做alpha-beta:

        .
      / |  \
    1   3*   3*
  / |  / \   | \
  1 1 5   3  4 3

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

维基百科的伪代码(以及许多其他资源)中的错字是什么？或者我在这里误解了一些非常大的东西.

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

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

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

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

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

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

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

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

例:

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

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

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

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

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

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

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

我正在编写一个程序来玩点和框，我想通过在迭代深化方案中基于启发式值对alphaBeta中考虑的移动进行排序来提高我的时间效率。本质上，我想进入搜索树，在每次迭代中增加深度，并使用alphaBeta评估每个节点。在每个后续迭代中，我认为节点的顺序将由上一次迭代中节点的启发式值决定。但是，我在理解如何实现方面有困难。有人可以提供伪代码来说明如何将标准alphaBeta程序修改为使用迭代加深进行搜索吗？谢谢！