Which are some two- or one-player games, where humans far outperforms the best computer programs? And how does the relative edge scale with time allowed to think? (In time frame 1 sec to 8 hours per move)
What is the common theme in these games that make it hard to implement efficient algorithms? (Or easy for humans)
On
I know of one such game: Go. - http://en.wikipedia.org/wiki/Computer_Go
There is a beautiful discussion about Go between two mathematicians in the movie Pi http://www.imdb.com/title/tt0138704/.
On
Another game in which the best humans are still better than computers is Shogi. But the difference is decreasing even though the progress is hindered by restrictions from the Japanese Shogi Association.
Starcraft. It has the high branching factor of Go, the nonlocal nature of Shogi (being able to call in units to different places instantaneously), and the uncertainty aspect of Poker. There has been quite a bit of AI research over the past few years (particularly at Berkeley and Stanford) by top researchers, and best bots results are honestly quite weak.
It is probably possible for a computer program to win by using abusive micro tactics that take tens of thousands of actions per minute. However this is just exploiting a single weakness of humans, so a more fair comparison would to limit a computer program to the most actions per minute that a top human can execute, say 500 APM. In that case I wouldn't be surprised if the problem is harder than Go.