棋盘游戏“围棋”是？ NP完成？
周围有很多国际象棋人工智能，显然其中一些足以击败世界上最伟大的棋手。
我听说人们已经进行了许多尝试来为棋盘游戏围棋，但到目前为止，还没有想到任何超出平均业余水平的作品。
难道在围棋中用数学方法计算任意给定时间的最优走法的任务是一个 NP 完全问题吗？
There are plenty of Chess AI's around, and evidently some are good enough to beat some of the world's greatest players.
I've heard that many attempts have been made to write successful AI's for the board game Go, but so far nothing has been conceived beyond average amateur level.
Could it be that the task of mathematically calculating the optimal move at any given time in Go is an NP-complete problem?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
国际象棋和围棋都是EXPTIME 完成的。 IIRC，围棋有更多可能的走法，所以我认为它的复杂程度比国际象棋更高。 Wikipedia 有一篇关于 Go 复杂性的好文章。
Chess and Go are both EXPTIME complete. IIRC, Go has more possible moves, so I think it a higher multiple of that complexity class than chess. Wikipedia has a good article on the complexity of Go.
即使 Go 只是在
P中，它仍然可能是像O(n^m)这样可怕的东西，其中n是空格的数量，< code>m 是某个（大）固定数字。即使处于P中也无法进行合理的计算。Even if Go is merely in
Pit could still be something horrendous likeO(n^m)wherenis the number of spaces andmis some (large) fixed number. Even being inPdoesn't make something reasonable to compute.国际象棋或围棋人工智能在决定走棋之前都不会完全评估所有可能性。
国际象棋人工智能使用各种启发式方法来缩小搜索空间，并量化棋盘上给定位置的“好”程度。这可以通过评估前面 14-15 步可能的棋盘位置并选择通向良好位置的路径来递归地完成。
棋盘位置的量化方式有一点“魔力”，因此在顶层，人工智能可以简单地选择“移动 A > 移动 A”。因此，移动 B 让我们执行移动 A。但是，由于块的数量有限并且它们都具有可量化的值，因此可以实现“足够好”的算法。
但事实证明，对于一个程序来说，评估围棋中两个可能的棋盘位置并使得 A > A 是困难得多。乙计算。如果没有这个关键部分，人工智能的其余部分就很难发挥作用。
Neither Chess or Go AIs completely evaluate all possibilities before deciding on a move.
Chess AIs use various heuristics to narrow down the search space, and to quantify how 'good' a given position on the board happens to be. This can be done recursively by evaluating possible board positions 14-15 moves ahead and choosing a path that leads to a good position.
There's a bit of 'magic' in how a board position is quantified so the that at the top level, the AI can simply go Move A > Move B therefore lets do Move A. But since there's a limited number of pieces and they all have quantifiable value a 'good enough' algorithm can be implemented.
But it turns out to be a lot harder for a program to evaluate two possible board positions in Go and make that A > B calculation. Without that critical piece its a little hard to make the rest of the AI work.