Here are some, in increasing order of difficulty
- Magic The Gathering and Hearthstone. As far as I know, there is no meaningful work on AI here, but DeepMind is trying to read cards into code directly. Perhaps a first step. Somewhat easy because the game is turn based. But difficult because of the high number of possible combinations of plays, long term thinking needed, and incomplete information: you can’t see your opponent’s deck or hand, only what is on the board.
- Starcraft or Civilization. Right now Starcraft bots don’t stand a chance when faced with gosus. This will be hard to solve. Starcraft is not turn based, but real time, there is incomplete information, and it’s hard to the point of implausible to learn it by throwing lots of data at a Machine Learning algorithm that we know now, and then get good answers in real time. Probably something new would have to be developed. The AI would have an advantage in terms of micro and macro, just because it would be able to input data faster. But since what is of interest here is intelligence and understanding, and not inputting speed, you could cap the Actions Per Minute of the AI at the same level the player is playing at that given instant.
- Automated engineering. Given the laws of physics and tons of GPUs, plus some data to learn, the program would be given instructions to try to come up with the best design for a given machine. Say, you tell the AI to build an aircraft, and it would try to look for the best aircraft, or at least, a good enough one. Thing: You cannot simulate the full Navier-Stokes equations of fluid mechanics for an entire aircraft in a reasonable amount of time (which is why good ol’ wind tunnels are still in use). This may add a degree of complexity, but many approximations exist for this problem. Something like this, but more general. Also, coding a piece of software when given very broad instructions.
- Entrepreneurialism. The mother of all the problems. I don’t know if I’m the first in pointing this out. This challenge would be for an AI to detect a profit opportunity in the real world (e.g. opening a bakery in a neighbourhood, or figuring out that producing electric cars in two years in a particular place sourcing materials from particular suppliers,etc, is a good idea). This is a problem for AI because you don’t have lots of time to do calculations, the data you need to understand for your decision is noisy, and you don’t have access to all of the information existing in the world. Some random paper I just found have people claiming that the extended variant of this, the economic calculation problem, would require hypercomputation. This doesn’t mean the problem can’t be solved, you can still get good enough approximations. The question is: how good enough, and in what amount of time? Could AIs replace the distributed decisionmaking we have in markets today?
Finally, you can read this paper, Building Machines That Learn and Think Like People (Lake et. al 2016), where they explain what difficulties AI still has to overcome in order to advance. One good example is in skill acquisition. AlphaGo needed hundreds of millions of games to get really good. Lee Sedol has played, perhaps, fifty thousand (And Sedol uses a fraction of AlphaGo’s energy to run). For the game Frostbite, one of the Atari games that was ‘learned’ by a previous DeepMind AI, humans got a level of performance in two hours that the AI wasn’t able to match. To get to the maximum performance, 80% of the human level, the neural network they were using took about 462 hours. We could call this the Unreasonable Effectiveness of the Human Brain.