现在有很多国际象棋 AI，而且很明显，有些 AI 已经足够优秀，可以击败一些世界上最伟大的棋手。

我听说人们已经尝试了很多次编写成功的围棋 AI，但到目前为止，还没有任何东西能够超越业余平均水平。

难道是因为在围棋中，数学上计算任何给定时刻的最佳走法是一个 NP 完全问题？

回答：

国际象棋和围棋都是 EXPTIME 完全。 我记得，围棋有更多的可能走法，所以我认为它的复杂度是国际象棋的更高倍数。 维基百科上有一篇关于围棋复杂度的好文章。