= 27d567bc2d48d9f40e9ccc20ea370b15)
JohannesDahlstrom comments on Fundamentally Flawed, or Fast and Frugal? - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (74)
You're confusing optimality in terms of results and efficiency in terms of computing power with your use of "NP-hard". Something like the travelling salesman problem is NP-hard in that there's no known way to solve them beyond a certain efficiency in terms of computing power (how to do optimally on them in terms of results is easy). It doesn't apply to chess or go in that there is no known way to get optimal results no matter how much computing power you have. These are two completely different things.
Surely there is a known way to play chess and go optimally (in the sense of always either winning or forcing a draw). You just search through the entire game tree, instead of a sub-tree, using the standard minimax algorithm to choose the best move each turn. This is obviously completely computationally infeasible, but possible in principle. See Solved game