complexity-theory - 如何手动查找井字游戏中决策树的复杂度？

Question

我知道游戏树大小的上限是 9！= 3X3 井字游戏中的 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-queens 问题https://en.wikipedia.org/wiki/Eight_queens_puzzle当您扩大电路板时，没有解决方案数量的分析解决方案。