In this Instructable I am going to show you how to build a Tic Tac Toe game with an AI using an Arduino. You can either play against the Arduino or watch the Arduino play against itself.
I am using an algorithm called “minimax algorithm”, which can be used not only to build an AI for Tic Tac Toe, but also for a variety of other games like Four in a Row, checkers or even chess. Games like chess are very complex and require much more refined versions of the algorithm. For our Tic Tac Toe game, we can use the simplest version of the algorithm, which is nonetheless pretty impressive. In fact, the AI is so good that it is impossible to beat the Arduino!
The game is easy to build. You only need a few components and the sketch that I’ve written. I also added a more detailed explanation of the algorithm, if you want to understand how it works.”

Link