[kybernetikos]

Arimaa is a good choice - it can be played on a chess board, has quite a bit of variety, and is deep as well.

[jamii]

It's also interesting for HN because there is a $11k prize for the first AI to win the annual mixed human-AI tournament.