Hacker News Reader

Comment by colllectorof | Hacker News Reader

Graph coloring problem is generic and is guaranteed to be useful in a myriad obvious applications. Plus, "polynomial time" is a specific criteria, whereas "somewhat better than a human champion" is an arbitrary milestone.

Besides, people who make advances in abstract problems like that do not release PR statements and get 1/1000th of the hype and coverage AlphaGo received recently.

View on HN

I'm not trying to troll you here, but have you ever actually played Go?? Go is so complex that the word 'complex' doesn't even begin to cover it. It's a game that requires equal parts creativity and logic. The sheer number of options absolutely dwarf anything else out there.

This achievement will be useful in a myriad of obvious applications. And, it is one of the greatest engineering feats that I have been alive to witness.

I have played Go and I understand that it is a complex and nuanced game. However, I also understand that it's a game very heavily based on patterns and pattern-matching.

Have you read the research paper and seen how much of AlphaGo's architecture was designed around the specifics of Go gameplay? (Including a set of handcrafted Go-specific training features.)

NxN Go is PSPACE-complete.[1] That's an even bigger deal than NP-complete.

[1] According to some comment in /r/MachineLearning the other day. I haven't looked into it myself.

That is with some bounds applied to it - if we allow unbounded games (ko, superko, etc) then it is EXPTIME-complete.

Yes. Source here: http://senseis.xmp.net/?ComplexityOfGo

To be fair, AlphaGo can only play 19x19 Go. It's unrelated to solving NxN Go.

Reply on news.ycombinator.com