如何在井字游戏中手动找到决策树的复杂性？

Question

我知道游戏树的大小的上限是9！ = 3,3井字游戏中的362,880。扣除无效案例以及轮换和反思后，只剩下26,830个可能的游戏。因此，3X3 Tic Tac Toe中决策树的复杂度为5，这是叶节点的位数（26,830）。我的结论正确吗？

如果是这样，我如何在不绘制完整决策树的情况下计算4X4 Tic Tac Toe的决策树复杂度？

对不起我的转储问题

Answer 1

[您可能想使用某种模型检查器，它可以计算解决方案，例如#SAT求解器https://en.wikipedia.org/wiki/Sharp-SAT。除了使用对称性之外，我认为除了探索状态空间之外，没有任何其他技巧（但这只会减轻探索）。

这就像N皇后问题https://en.wikipedia.org/wiki/Eight_queens_puzzle，当您按比例放大电路板时，没有解决方案数目的解析解决方案。