java - TreeNode 的井字游戏解决方案

Question

我正在创建一个 tic tac toe 程序，它是播放器与 pc。电脑需要计算出他能做的最好的动作，然后去做。要计算每个可能的步骤，TreeNode 听起来很完美，但问题是在每个级别之后，孩子的数量越来越少，例如：

^ 表示为空

^ X O 
O O X
^ X ^

对于这种情况，我需要一棵有 3 个孩子的树，但对于这种情况：

^ ^ ^
^ X ^
^ ^ ^

我需要一棵有 8 个孩子的树。那么可以改变孩子的数量吗？在问这个问题时，我认为将 null 放在不想要的孩子上会是一个解决方案，但你有更好的建议吗？或者甚至树不是我情况的最佳选择？

Answer 1

是的，这很容易实现。不要使用数组来保存节点的子节点，而是使用可变大小的List实现，例如ArrayListor LinkedList。

或者，您甚至可以只使用一个数组，但将孩子的数量作为参数传递给TreeNode. 你知道如果TreeNode a有 8 个孩子，那么每个孩子最多有 7 个孩子。

Answer 2

您应该实现自己的 Tree 对象，该对象由包含子节点数组的节点组成。通过这种方式，您还可以实施 Euristic 方法以从最佳解决方案获得近似距离度量。