棋盘游戏"Go“NP完成了吗？

Question

有很多国际象棋人工智能，显然有些足够好，可以击败一些世界上最伟大的棋手。

我听说已经有很多人尝试为棋盘游戏Go编写成功的人工智能，但到目前为止，还没有人构思出超过业余水平的东西。

在围棋中计算任何给定时间的最优走法的数学任务是NP完全问题吗？

Answer 1

国际象棋和围棋都是EXPTIME complete。IIRC，围棋有更多的可能走法，所以我认为它比国际象棋复杂程度的倍数更高。维基百科上有一个关于Go复杂性的good article。

Answer 2

即使Go仅仅是在P中，它仍然可能是一些可怕的东西，比如O(n^m)，其中n是空格的数量，m是一些(大的)固定数字。即使是在P中，也无法进行合理的计算。

Answer 3

无论国际象棋还是围棋，在决定下一步棋之前，都不能完全评估所有的可能性。

国际象棋人工智能使用各种启发式方法来缩小搜索空间，并量化棋盘上给定位置的“好”程度。这可以通过评估前14-15步可能的棋盘位置并选择一条通向好位置的路径来递归完成。

在如何量化棋盘位置上有一点“魔力”，因此在顶层，AI可以简单地移动A >移动B，因此让我们移动A。但是由于棋子的数量有限，并且它们都有可量化的值，所以可以实现“足够好”的算法。

但事实证明，对于一个程序来说，评估围棋中两个可能的棋盘位置并进行A>B计算要困难得多。没有这个关键部分，AI的其余部分就很难正常工作。