java - 如何递归地遍历一棵树、创建节点、调用函数并进行更深入的研究？

Question

目前，我正在尝试为类似于国际象棋的游戏开发人工智能，我基本上尝试提前计算几步，然后通过 alpha beta 获得最佳可能的返回。

目前我的策略是，每 1 个 Action ，做出 4 个最佳结果 Action ，暂时改变“棋盘”，然后对于这 4 个 Action ，再次调用 4 个，然后运行这些 Action ，每个 Action 再调用 4 个。 ...

对于递归函数来说，这似乎非常自然，我正在尝试向下挖掘 10 步左右。但到目前为止，我已经写了 3 个步骤(轮到我，你的，我的)，而且我的代码已经崩溃了。我需要对每个新 Action 计算新 Action 的部分进行编码。无论如何，我是否可以截断下面的代码，以便它可以类似于递归调用(...)，并以最大级别检查作为基本情况？

这是我当前的迭代 3 步代码，假设有一个树结构，每个 Action 内部都包含一个包含 4 个最佳反击 Action 的数组列表。

 for (i = 0; i < root.children.size(); i++) {
        root.children.get(i).runStrat();
        root.children.get(i).printNode();
        for (int lvl1 : root.children.get(i).currOtherPieces) {
            root.children.get(i).addChild(lvl1,root.children.get(i).level + 1);         
            }
        for (j = 0; j < root.children.get(i).children.size(); j++) {
            root.children.get(i).children.get(j).runStrat();
            System.out.print("    ");
            root.children.get(i).children.get(j).printNode();
            for (int lvl2 : root.children.get(i).children.get(j).currSelfPieces) {
                root.children.get(i).children.get(j).addChild(lvl2, root.children.get(i).children.get(j).level + 1);
            }
            for (k = 0; k < root.children.get(i).children.get(j).children.size(); k++) {
                root.children.get(i).children.get(j).children.get(k).runStrat();
                System.out.print("            ");
                root.children.get(i).children.get(j).children.get(k).printNode();
            }
        }
    }

正如你所看到的，我可以继续编写 7 层 for 循环，但也许有一个聪明的方法来递归地放置它。有什么帮助吗？谢谢!

(带空格的sys.out只是为了我调试，可以省略...)

Answer 1

你所做的就是所谓的“行为树遍历”或“解决方案空间搜索”，即枚举所有可能的下一步 Action 并评估它们。行为树遍历只是tree traversal methods的一个应用.

虽然建议您充分了解广度优先树遍历和深度优先树遍历策略，但我可以快速回答您的问题。

在处理树遍历时，您可能更喜欢迭代算法而不是递归算法，因为如果不进行尾递归优化，可能会遇到堆栈溢出问题。

遍历树时，您应该使用一个称为“边缘”的队列，其中包含下一个要访问的节点。

Queue<Node> fringe = new LinkedList<Node>();

起初，边缘仅包含根节点。

fringe.add(root);

然后，您可以通过以下方式迭代边缘:

while(fringe.isEmpty() == false) {
  Node current = fringe.poll();

  // Evaluate the current move, e.g. if it leads to an improvement of your gameplay
  boolean result = doSomething(current); 

  if(result && !current.getChildren().isEmpty()) {
     fringe.addAll(current.getChildren();
  }
}

该算法是 BST(广度优先遍历)的简单实现，这意味着您在移动到下一个树级别之前先访问给定树级别的所有子节点。 DFS(深度优先遍历)版本的边缘使用了 FIFO 数据结构。

Stack<Node> fringe = new LinkedList<Node>();
fringe.push(root);

while(fringe.isEmpty() == false) {
  Node current = fringe.pop();

  // Evaluate the current move, e.g. if it leads to an improvement of your gameplay
  boolean result = doSomething(current); 

  if(result && !current.getChildren().isEmpty()) {
     for(Node child: current.getChildren()) {
        fringe.push(child);
     }
  }
}

这两种算法有大量的优化，例如根据某些指标(启发式方法，例如 A star )处理具有不同顺序的子级的算法，其他算法跟踪已访问的节点以避免循环，以及等等。

为了更好地掌握解决方案空间访问，我建议您阅读"Artificial Intelligence: A Modern Approach" by Stuart Russel and Peter Norvig .

为了记录搜索的深度，您可以使用一个名为 level 的字段来扩展 Node 对象，对于 root 来说，该字段为 0。当探索节点的子节点时，在将它们插入边缘之前，只需将它们的级别设置为父节点的级别 + 1，如果这大于你的最大等级，请避免将它们放在边缘。