周围有很多国际象棋人工智能，显然有些足以击败一些世界上最伟大的棋手。
我听说已经为棋盘游戏Go编写了成功的 AI 进行了许多尝试，但到目前为止，还没有任何超出平均业余水平的构想。
在围棋中任何给定时间以数学方式计算最佳移动的任务是否是一个 NP 完全问题？
问问题
5042 次
3 回答
16
国际象棋和围棋都是EXPTIME 完整的。IIRC，围棋有更多可能的移动，所以我认为它比国际象棋复杂度更高。Wikipedia 上有一篇关于 Go 复杂性的好文章。
于 2009-11-12T23:28:18.280 回答
4
即使 Go 只是在其中，P它仍然可能是一些可怕的东西，比如空格的数量O(n^m)在哪里，并且是一些（大）固定数字。即使在里面也不能使计算合理。nmP
于 2009-11-13T04:52:17.703 回答
3
国际象棋或围棋 AI 在决定移动之前都没有完全评估所有可能性。
国际象棋 AI 使用各种启发式方法来缩小搜索空间，并量化棋盘上给定位置的“好”程度。这可以通过评估可能的棋盘位置 14-15 向前移动并选择通向良好位置的路径来递归地完成。
如何量化棋盘位置有一点“魔力”，因此在顶层，AI 可以简单地移动 A > 移动 B，因此让我们移动 A。但由于棋子数量有限，而且它们都有可量化的价值 可以实现“足够好”的算法。
但事实证明，程序要评估围棋中两个可能的棋盘位置并进行 A > B 计算要困难得多。如果没有这个关键部分，让 AI 的其余部分工作有点困难。
于 2009-11-28T05:28:53.867 回答