本公司董事会游戏“进入” NP完全性？

Question

有大量的国际象棋AI的周围，显然有些不够好，击败了一些世界上最伟大的球员。

我听说许多尝试已经进行了写成功AI对棋盘游戏去，但至今没有被设想超出平均业余水平。

难道的数学计算在转到任何给定时间的最优移动任务是一个NP完全问题？

Answer 1

象棋和Go二者 EXPTIME完整。 IIRC，围棋有更多可能的行动，所以我认为它是复杂类比国际象棋的更高的倍数。维基百科对围棋的复杂好文章。

Answer 2

即使Go是仅仅P它仍可能是一些可怕像O(n^m)其中n是空格和m数量就是若干（大）固定数目。即使在P是不会使一些合理的计算。

Answer 3

无论象棋或转到认可决定移动之前完全评估所有的可能性。

象棋认可使用各种试探法来缩小搜索空间，并量化“好”在基板上的给定位置如何恰好是。这可以通过递归地向前移动14-15评估可能仓板，并选择导致了良好的位置的路径来进行。

有是在一个板位置如何量化有点“神奇”，因此，在顶层，人工智能可以简单地去移动>移动因此，B可以做移动A.但是因为有件数有限，它们都具有“足够好”的算法可以实现量化的值。

但事实证明是困难得多一个程序，以评估在Go两个可能的仓板，使该A> B的计算。如果没有关键部分的稍用力使AI工作的其余部分。