文章/答案/技术大牛

发布

社区首页 >问答首页 >在用于无值和交叉的极小极大算法中，节点存储为什么？

问在用于无值和交叉的极小极大算法中，节点存储为什么？
EN

Stack Overflow用户

提问于 2016-03-13 16:48:27

回答 1查看 556关注 0票数 1

我是java的初学者，所以可以随意更正我对这个问题的任何措辞。

无论如何，我正在创建一个无值和交叉/抽搐脚趾游戏与一个完美的人工智能对手，我的目标是使用一个α-β剪枝极小极大的算法。我认为我非常了解这个算法，但我无法解决如何将“节点”和“nodeChilds”合并到其中。这是维基百科上的伪码算法。

01 function minimax(node, depth, maximizingPlayer)
02     if depth = 0 or node is a terminal node
03         return the heuristic value of node

04     if maximizingPlayer
05         bestValue := −∞
06         for each child of node
07             v := minimax(child, depth − 1, FALSE)
08             bestValue := max(bestValue, v)
09         return bestValue

10     else    (* minimizing player *)
11         bestValue := +∞
12         for each child of node
13             v := minimax(child, depth − 1, TRUE)
14             bestValue := min(bestValue, v)
15         return bestValue

有人能对“节点”应该具有什么样的价值提供任何见解吗？在我目前使用的算法中，我调用minimax函数如下所示：

game.minimax(0, 1); //1 represents the computer's turn, equivalent to maximizingPlayer 

public int minimax(int depth, int turn)

任何帮助/解释都将是非常感激的，所以如果我没有提供足够的信息或解释我的问题，那么请原谅。

java

algorithm

recursion

回答 1

Stack Overflow用户

回答已采纳

发布于 2016-03-13 16:51:21

node是游戏树的状态。在无号和十字的情况下，它描述了董事会的现状。minimax算法需要一个具有以下信息的节点：

如果是终端节点(游戏结束)
下一个要玩的球员
将该节点与其他节点相比较的值或实用程序。你需要一个非终端板的启发值。
来自此节点的可能的下一个节点(子节点)

您可以使用该信息创建一个Node接口，并使用它创建一个通用的minimax实现。就像这样：

enum Player { MAX, MIN }

interface Node {
  boolean isTerminal();
  int utility();
  Player nextPlayer();
  List<Node> children();
}

然后，您将有一个为Node编写游戏规则的零和交叉实现。您可以将板存储为一个由9个整数组成的简单数组(例如，空空间为0，X为1，O为2)。

class NaughtsAndCrossesNode implements Node {
  private int[] board;

  // ....
}

重要的是要认识到，任何Node实现都应该是一个不可变的类。玩游戏(获取节点的子节点)会创建更多的实例，而不会改变现有的实例。

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/35972920

复制

相似问题

问在用于无值和交叉的极小极大算法中，节点存储为什么？
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在用于无值和交叉的极小极大算法中，节点存储为什么？EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在用于无值和交叉的极小极大算法中，节点存储为什么？
EN