Tic tac toe -- AI

I went a little beyond the exercise requirements here as a thought exercise, to increase my comfort with coding. Because tic-tac-toe is a solved game, I figured it should be relatively easy to design a computer AI system that never loses. I implemented a ComputerPlayer method possible_moves that returns an array of empty board positions. In my get_move method, I then iterate over this possible_moves array and return the first move that satisfies the criteria, in descending order of priority. (1. if you can win with a move, make that move 2. if the opponent wins with a certain move, make that same move 3. if you can create a fork with a move, make that move. 4. if the opponent can create a fork with a certain move, make that move. 5. take the center 6. if your opponent is in a corner, take the opposite corner 7. take an open corner 8. take the sides — for which i used possible_moves.sample, since if we’ve gotten this far, no other condition is true)

56%20PM

For the most part, this seems to work but I have three issues:

  1. Is there a more elegant way to express what I have written so far? I can use a case statement but decided against it because in my opinion, it looks even more clunky written out that way.

  2. Because the ComputerPlayer doesn’t have a way to evaluate game state, while my computer player avoids almost all losses, it doesn’t necessarily make the optimal move each turn; it is simply returning what I’ve hard-coded as the conditions for an optimal move in order of priority.

  3. Lastly, this may be a fringe case, but it is indicative of the second issue I mention. Suppose you are a human player going first and you go in the top left corner, the computer player is programmed to respond with a move in the center. Suppose you then take the bottom right corner. Because the computer player is programmed to block a potential opponent fork, it will respond with either the top right corner or the bottom left corner, because if you place your next move there, you will create a fork and thereby win. However, because the computer responds this way, it is actually allowing you to create a fork on your next move. Thus, rather than checking if the opponent can create a fork with a specific move and then blocking that move, it seems equally important to ensure any move will not eventually lead to an opposing fork. How can we program this?

Hi James,

I really like the initiative you’ve taken in this. Your approach looks great. I’ll briefly say something about questions 2 and 3 first: There are definitely approaches here that take care of this issue. However, they involve more advanced data structures than what comes built in with Ruby. But you’re in luck: We will actually be learning about these data structures at the end of week 1 of the main curriculum. And one of the projects on that day of the curriculum will involve writing an AI for Tic Tac Toe that can’t possibly lose! So stay tuned for that!

About your first question: I would probably refactor move == board.center and board.corners.include?(move) into its own little helper methods so that your code reads a bit more uniform. The only other thing I would change is stylistic: Make sure that none of your lines are longer than 80 characters, i.e. that they don’t go past the vertical line on the right. That will involve turning your blocks into do ... end blocks. However, if you do use { ... }, it’s customary to add a space after the { and another space before the }.

Hope this helps! Let me know if you have any other questions!

Thanks Matthias, it’s definitely helpful to read your feedback, and I’ll refactor as you mentioned to make the code read a little cleaner.

I looked into a bit further and found a helpful article on minimax functions here: https://www.neverstopbuilding.com/blog/2013/12/13/tic-tac-toe-understanding-the-minimax-algorithm13/

But to implement an algorithm similar to what is written here, it looks like I would have to reconfigure the instance variables and methods that the Game/ComputerPlayer/Board classes hold. If I correctly understand what this code is doing, it takes a given game board, and for each blank space (possible move) it will recursively fill out the remainder of the game board . As it does so it will populate a scores array and moves array, and eventually choose the move that corresponds with the highest score. What I don’t understand is why this function returns a score rather than a move. Am I missing something here?

I wasn’t familiar with this article, but it looks neat! I definitely encourage you to work through it if you have the time. The approach we’ll be taking to develop a Tic Tac Toe AI in the main curriculum will be different, so it’ll be fun to see an alternative approach.

About your question: Which function are you referring to that returns a score?

Within the minimax(game) method, the choice of the optimal move appears to be stored in the @choice instance variable, but the method itself seems to return the optimal score. I was wondering why one would choose to set up the method this way. 23%20PM

Apologies for the slow response! That is odd indeed. It strikes me that it would make more sense to return the choice instead of the score.