[AstralStorm]

Perfect information problem solving is not interesting anymore.

Did they manage to extend it to games with hidden and imperfect information?

(Say, chess with fog of war also known as Dark Chess. Phantom Go. Pathfinding equivalent would be an incremental search.)

Edit: I see they are working on it, predictive state memory paper (MERLIN) is promising but not there yet.

[dgacmu]

Strongly disagree. There are a lot of approximation algorithms and heuristics in wide use - to the tune of trillions of dollars, in fact, when you consider transportation and logistics, things like asic place & route, etc. These are all intractable perfect info problems that are so widespread and commercially important that they amplify the effect of even modest improvements.

(You said problems, not games...)

[AstralStorm]

Indeed, there are a few problems where even with perfect information you will be hard pressed to solve them. But that is only a question of computational power or the issue when the algorithm does not allow efficient approximation (not in APX space or co-APX).

The thing is, an algorithm that can work with fewer samples and robustly tolerating mistakes in datasets (also known as imperfect information) will be vastly cheaper and easier to operate. Less tedious sample data collection and labelling.

Working with lacking and erroneous information (without known error value) is necessarily a crucial step towards AGI; as is extracting structure from such data.

This is the difference between an engineering problem and research problem.

[dgacmu]

Perhaps a unifying way of saying this is: it's a research problem to figure out how to get ML techniques to the point they outperform existing heuristics on "hard" problems. Doing so will result in engineering improvements to the specific systems that need approximate solutions to those problems.

I completely agree about the importance of imperfect information problems. In practice, many techniques handle some label noise, but not optimally. Even MNIST is much easier to solve if you remove the one incorrectly-labeled training example. (one! Which is barely noise. Though as a reassuring example from the classification domain, JFT is noisy and still results in better real world performance than just training on imagenet.)

[eitland]

> Perfect information problem solving is not interesting anymore.

I guess in the same way as lab chemistry isn't interesting anymore ? (Since it often happens in unrealistically clean equipment :-)

I think there is nothing preventing lab research from going on at the same time as industrialization of yesterday's results. Quite on the contrary: in the long run they often depend on each other.

[nl]

There’s plenty of interesting work on poker bots.

[AstralStorm]

Poker bots actually deal with a (simple) game with imperfect information. It is not the best test because short memory is sufficient to win at it.

The real challenge is to devise a general algorithm that will learn to be a good poker player in thousands of games, strategically, from just a bunch of games played. DeepStack AI required 10 million simulated games. Good human players outperform it at intermediate training stages.

And then the other part is figuring out actual rules of a harder game...