Checkers solved
In high school, I solved tic tac toe in my 50 minute US history class.
Checkers is not a complex game I figure it is solvable as well.
Same with heads up poker. An argument can be made that in human versus human...the human poker pro would be able to extract more from the newbie human than a computer though. This is due to exploitative strategy.
Of course, in a multi way game there's no way a computer would win due its inability to predict wierd implicit alliances.