5 ms·
Can a deep learning system play these particular NP-Hard games well?
by yters 9y ago
Can a deep learning system play these particular NP-Hard games well?
- petters 9y agoNo, they are far too complex.
- etatoby 9y agoCan we define human-level intelligence, which is the stated end goal of AI, as the ability to find more or less approximate solutions to NP-hard problems, as well as undecidable problems (we solve the halting problem every day as part of our job) in polynomial time?
- petters 9y agoNo, humans are pretty terrible at approximating e.g. TSP or max-cut. I don't think it is a good definition of intelligence.
- yters 9y agoSurprisingly, humans are actually pretty good at TSP, achieving better efficiencies than state of the art appriximization algorithms.
- yters 9y agoWould that imply the mind is non algorithmic?
- ot 9y agoDeepMind has produced a few agents playing well classic games. When the authors of this paper are saying that these games are NP-hard, they're taking some "poetic license": complexity classes are defined for problems that have instances of increasing sizes (as the complexity is defined as a function of the size). Super Mario is only one instance. So they analyze generalizations of the game, and as the game size grows to infinity it becomes very hard to play it. For the real games, DL does pretty well (and even simpler agents do well).
- CJefferson 9y agoOne very small sample -- I had a student try training tensorflow to solve NP-hard problems, we couldn't get it to do any better than random guessing. I wasn't really surprised, because you need to make many interlocked decisions, all in one go, and all correctly. Also, it's (at least for me as a human) almost useless to try to learn from other similar looking problems to spot patterns in answers.