文章/答案/技术大牛

发布

社区首页 >问答首页 >如何手动发现Tic Tac Toe中决策树的复杂性？

问如何手动发现Tic Tac Toe中决策树的复杂性？
EN

Stack Overflow用户

提问于 2018-11-06 17:40:12

回答 1查看 691关注 0票数 1

我知道在3X3 Tic Tac Toe中，游戏树大小的上限是9！= 362,880。在扣除无效情况和旋转和反射后，只剩下26830个可能的游戏。因此，3X3 Tic Tac Toe中决策树的复杂度为5，这是叶节点的位数(26,830)。我的结论对吗？

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

很抱歉我的转储问题

发布于 2019-12-13 02:37:23

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

这就像N-queens problem https://en.wikipedia.org/wiki/Eight_queens_puzzle一样，当你放大电路板时，没有关于解的数量的解析解。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/53169245

复制

相似问题

问如何手动发现Tic Tac Toe中决策树的复杂性？EN