Excellent question! Once again, late to the party, but here are my thoughts:
It's very hard to come up with any board game where humans would beat computers, let alone an interesting one. Board games, by their nature, are discretized and usually perfect information. This type of game is not only solved by AI, but solved by essentially a single algorithm. Card games with mixed strategy equilibrium like Poker do a little better, although Poker has been solved the algorithm doesn't generalize to other card games without significant feature engineering.
If I were to design a board game to stump AIs, I would use these elements:
- Incomplete information, with the possibility of information gathering ("scouting") at a cost (like in Starcraft 2) to invalidate Markov property
- Lengthy gameplay (number of moves) to make the credit assignment problem as bad as possible for RL agents
- Patterns that require abstract reasoning to discern (e.g. the pigeonhole principle lets you conclude immediately that 1001 pigeons don't fit in 1000 pigeonholes; an insight that can't practically be learned through random exploration of permutations)
The last element in particular is a subtle art and must be used with caution, because it trades off intractability for RL against intractability for traditional AI: If the pattern is too rigid the programmer could just hard-code it into a database.
If we considered video games instead, the task becomes much easier. DOTA 2 and Starcraft 2 AIs still can't beat human professionals at the full game despite the news hype, although they probably can beat the average human player. Some games, such as Chronotron or Ultimate Chicken Horse, might be impossible for current AI techniques to even achieve average human level performance on.