Давно увлекаюсь данными играми, когда-то заработал первый разряд по шахматам.
Вот тут есть интересная табличка - там игры расставлены в зависимости от разветвления дерева вариантов итд
http://en.wikipedia.org/wiki/Game_complexity
А по поводу шахмат и шашек для компьютерного анализа - так шахматисты уже лет пять и близко не могут подойти к уровню машины, поэтому даже игры переcтали проводить.
Касательно шашек, я недавно увлекся столбовыми шашками (инфу в сети найти легко) - невероятно увлекательный вариант, в разы более сложный и глубокий.