Hacker News Reader

Comment by inimino | Hacker News Reader

Games like go and chess are necessarily solveable by definition, right? If you mean solveable in our lifetimes, by current technology, that's something else entirely, and much less likely.

Beating human players in go is like finding a good heuristic for an NP-complete problem. Solving 19*19 go is like proving P!=NP, i.e. we don't even have tools that can approach the problem.

View on HN

Not sure if this is true for Go. I'm not sure, but it seems to me that at some point a problem becomes "too complex" to solve. I.e. Go has about 2.08168199382×10^170 legal positions [1] and the number of atoms in the observable universe is only up to ~4×10^81.

I don't know if there are some theorems, thoughts, philosophies about whether this means it can't be solved, but at least it must be extremely difficult.

[1] https://en.wikipedia.org/wiki/Go_and_mathematics#Legal_posit...

In a theoretical sense, Go is certainly solvable, as we can easily construct a Turing machine that plays out every possible move, and provably terminates (given an appropriate ruleset). Practically, the universe will certainly be expected to terminate first.

There may be other ways to solve the game, but we don't know what they are. Because we know it is theoretically solvable, we cannot rule out a practical approach to solving it by some mathematical magic even if we have no idea what that would look like.

By analogy, we can prove many things about infinitely many integers by mathematical induction, but if we didn't have that technique, such proofs might seem impossible.

While mind-boggling, I'm not sure it's generally meaningful to compare counts of actual things (even atoms) with counts of possible arrangements. The latter are in a world of their own[1].

[1] https://en.m.wikipedia.org/wiki/Orders_of_magnitude_(numbers...

Reply on news.ycombinator.com