Do you know any abstract multi- or single-player game that is hard to play for AI/computer but not so hard for humans?
Being simple and popular is better.
Probably your best bet is arimaa which is specifically designed to be hard for AI's.
Arimaa (pronounced Ah-REE-ma) is a very deep strategy game with simple rules. It was designed to be: Playable with a standard chess set. Easy to learn. Difficult for computers (the $10,000 programming challenge is still available). Fun and interesting for humans.
The creation of Arimaa was inspired by the Deep Blue vs Gary Kasparov match in which the computer defeated the world chess champion. Arimaa was created to show that humans can still outplay computers using a chess set and provide the next challenge to the AI community.
Why is Arimaa hard for computers?
- On average there are over 17,000 possible moves compared to about 30 for chess; this significantly limits how deep computers can think, but does not seem to affect humans.
- Opening books are useless since the starting position is not fixed. There are over 64 million ways to start the game.
- End game databases are not helpful since a game can end with all pieces still on the board.
- Research papers on Arimaa suggest it is more of a strategic and positional game with less emphasis on tactics.
- Arimaa is proposed as a more difficult challenge for AI than chess.
- A challenge prize invites AI researchers to develop a program that can defeat the top human players.
- A yearly challenge match is held to give teams a chance to win the challenge prize.
- Humans have decisively won each year. A yearly computer championship tournament is held to select the best Arimaa playing program.
Go is famous for being extraordinarily hard to create a decent AI for. It's perhaps one of the most abstract and elegant games ever created; you place stones on a grid in an effort to capture territory from your opponent.
Early Go AI research was driven by competitions which offered prizes as large as 1.4 million dollars. The best achievement in the field to-date is a program which reached 6 dan (I'm not sure how that rank fits into the grand scheme of things, but it sounds impressive) on a major Go server. Most Go AIs are beaten by lower - though still very skilled - players, even with significant handicaps.
Go is by no means easy to master for a human, but it fits what you're looking for, for this reason: were a person to spend some amount of time learning the game, and an equivalent amount of time put into developing a Go AI, the human player would surely win.
Arimaa and Go are hard for computers, but good progress is being made. My candidate for a game that will remain difficult for computers is "Volo" which you can play at Boardspace.net.
In addition to the "vast number of moves" problem, Volo has the property that most moves have to be obviously a step backward from the goal of the game, which is to unite all your pieces.