This problem set is not really a problem set. It’s pointers to some major milestones in AI, and game-playing AI in particular, that are directly related to the algorithms you’re implementing for TicTacToe. There’s nothing to turn-in here, but don’t skip on these assignments as they show you just how far these algorithms can go.

DeepBlue

We’ve already seen a short film about Deep Blue. At the start of the semester you were given a paper titled Deep Blue (see syllabus). Give this paper a quick read. Spend a little extra time on the following sections as they touch on the parts of the system most closely related to your tic-tac-toe studies:

  • Sections 1-2 - History and System overview.
  • Section 4 - Software Search details
  • Section 7 - Evaluation Function

Chinook

We’ll start the Relatively Prime podcast episode titled Chinook in class. Finish it and learn about the process of going from playing checkers to solving checkers. Then, give the paper Checkers is Solved a quick read to get some of the technical details of the proof; it uses AI search. You’re strongly solving tic-tac-toe, but most games are too complex for such a result. Checkers is one of the most complex games that has been at least weakly solved.