[ubernostrum]

People have already put work into finding chess-like games, or variants of chess, that humans can play well (especially if they have some familiarity with chess) but that computers will struggle with.

Arimaa -- where computers did eventually reach the point of defeating humans -- is an example of this. Arimaa tried to attack both "opening books" and move-tree searches, by allowing the initial position to vary every game and by having each turn consist of up to four individual moves by potentially multiple pieces. The official challenges also required that computer Arimaa systems run on commodity hardware, and did not allow for modifying the computer "player" in between games of a challenge. It got through twelve yearly human-versus-computer challenges before the humans finally lost.