在树中正确实现 Min-Max

Question

我在一棵树上实现了最小-最大算法。我创建的算法按预期工作，返回树中对应于最小值和最大值的路径。但我的问题是感觉不对。
我的问题是，这是 min-max 算法的正确实现吗？
我无法在由节点组成的树结构中找到该算法的纯实现。在我设法找到的示例中，人们实现了算法来解决与游戏 (tic-tac-toe) 相关的问题。老实说，我觉得我很愚蠢，我无法建立联系。
我使用了 2 个函数，
1->evaluations_function 遍历树并为没有的节点添加值（a.k.a。所有不是叶子的节点）。
2->print_optimal 遍历树和 returns 路径 .

public void evaluation_function(Node root, int maxHeight, int rootHeight) {
        if (root.childrenList.Count != 0) {
            foreach (Node node in root.childrenList) {
                evaluation_function(node, maxHeight, rootHeight);
            }
        }
        if (root.height != rootHeight) {
            if ((root.height % 2) == 0) {
                if (root.value < root.parent.value || root.parent.value == 123456) {
                    root.parent.value = root.value;
                }
            } else if ((root.height % 2) != 0) {
                if (root.value > root.parent.value || root.parent.value == 123456) {
                    root.parent.value = root.value;
                }
            }
        }
    }

这里是print_optimal

public void print_optimal(Node root) {
        int maxValue = 0;
        int minValue = 9999;
        if (root.childrenList.Count != 0) {
            if (root.height % 2 == 0) {
                foreach (Node child in root.childrenList) {
                    if (child.value > maxValue) { maxValue = child.value; }
                }
                foreach (Node child in root.childrenList) {
                    if (child.value == maxValue) {
                        Console.WriteLine("Selected node " + child.name
                            + " with value = " + child.value + " as MAX player");
                        print_optimal(child);
                    }
                }
            } else {
                foreach (Node child in root.childrenList) {
                    if (child.value < minValue) { minValue = child.value; }
                }
                foreach (Node child in root.childrenList) {
                    if (child.value == minValue) {
                        Console.WriteLine("Selected node " + child.name
                            + " with value = " + child.value + " as MIN player");
                        print_optimal(child);
                    }
                }
            }
        }
    }

我不想用代码来解决这个问题，因为我的问题是理论性的。但是如果你想查看数据结构或想测试算法，你可以在这里找到它：https://github.com/AcidDreamer/AI_Exercises/tree/master/1.2.1/Exercise1_2_1/Exercise1_2_1

改进
evaluation_function 改为

public void evaluation_function(Node root, int rootHeight) {
        if (root.childrenList.Count != 0) {
            foreach (Node node in root.childrenList) {
                evaluation_function(node, rootHeight);
            }
        }
        if (root.height != rootHeight || root.childrenList.Count != 0) {
            int maxValue = 0, minValue = 999;
            if ((root.height % 2) == 0) {
                foreach (Node child in root.childrenList) {
                    if (maxValue < child.value) {
                        maxValue = child.value;
                        root.value = maxValue;
                        root.bestChild = child;
                    }
                }
            } else if ((root.height % 2) != 0) {
                foreach (Node child in root.childrenList) {
                    if (minValue > child.value) {
                        minValue = child.value;
                        root.value = minValue;
                        root.bestChild = child;
                    }
                }
            }
        }
    }

为当前节点赋值。
print_optimal 使用 bestChild 字段有了巨大的改进，并更改为

public void print_optimal(Node root) {
        if (root.bestChild != null) {
            Console.Write(root.name + "->");
            print_optimal(root.bestChild);
        } else {
            Console.WriteLine(root.name);
        }
    }

Answer 1

我发现接收节点作为输入的 evaluation_function 实际上更新 parent 节点的值有点不自然。

我觉得更好的方法是让该函数改为更新当前节点。

如果当前节点是叶节点，它应该什么也不做。

否则，它应该遍历所有 children（就像它当前在第一个循环中所做的那样），并且在每次递归调用 child 之后，它还应该检查当前是否应该更新节点值（即刚刚遇到一个更好的值，对于当前child）。

此外，可以为每个节点添加一个额外的字段，例如 bestChild，或bestMove，以避免re-iterating 通过 children 在调用 print-optimal 时。

Answer 2

总的来说你的代码很好（你知道的，因为它有效），但我有一些关于改进的评论：

evaluation_function：你根本不用maxHeight。使用它或删除参数。函数更改当前节点的 parents 很奇怪（一种不好的做法）。它应该查看 children 的值（如果不是叶子的话），并据此更新当前节点的值。此外，您可以添加一个字段来跟踪最佳 child（甚至是选定的叶子路径）以避免 print_optimal.

中的匹配过程

print_optimal()：如果 2 children 具有相同的值，您目前遇到问题：您将打印它们并探索两棵树。检查 if (child.value < minValue) { minValue = child.value; } 是没有用的，因为您假设您已经使用了 evaluation_function()，如果您忘记这样做，检查 "replace" evaluation_function 是不够的。

在树中正确实现 Min-Max

Correct implementation of Min-Max in a tree

algorithm

tree

minmax