It is interesting to study the computational complexity of board games - chess, checkers, even tic-tac-toe present a challenge to analyze and solve. Theoretical computer science work at Columbia has shown many results, such as: