This BoardgameGeek thread discusses: http://www.boardgamegeek.com/article/2230504#2230504
I think that it's likely that all nonrandom pure abstracts can be eventually "solved" once computing power and program sophistication improve enough.
Checkers apparently is there already and chess is nearly so. Go has had a reputation for being deeper than chess and the difficulty programmers have had creating skilled AI for it supports that view.
But without random elements any game is subject to having its decision tree mapped out completely in theory, although in practice it may involved too many variables to be doable. Consider, for example, a super chess that has double the number of pieces or adds new pieces such as Warmaster. The possible games might approach the number of atoms in the galaxy.
This is why the 9x9 game of Go will be solved long before the 19x19 game, unless, of course, programmers can discover the organizing principles that human minds use to narrow the number of choices to a manageable number. It may turn out that intuition may be quantifiable. For example, chess masters can more easily remember the locations of pieces when they are in legal positions than illegal setups because of the pattern recognition involved.
Pattern recognition is the secret to human intelligence and computers are likely to have trouble competing in tasks involving this skill until it's secret is discovered.