Minimax is Drinking My Tears

This morning I told my mentor that minimax would be listed on my tombstone as the cause of my death. Yes, that's where I'm at right now. I don't expect any updates on that for a long while. That attitude may be part of why I'm struggling with the concepts of recursion and minimax, but maybe being honest about my feelings will eventually help me out of this rut.

I'm working on my tic tac toe game in Ruby. I'm working on a feature that will allow a user to play against a computer. Given the opportunity to win or tie the game, the computer will win or tie the game. Essentially I have to build an algorithm that will make the computer player unbeatable. There are several ways to address this problem, but typically this is done by writing a minimax algorithm. This algorithm will consider all possible moves at any given state of the board, evaluate each move, and return the best move that will result in a win or a draw. At least, this is my understanding of the algorithm up to this point. My other basic understanding is that this algorithm is recursive, meaning that it will invoke itself (hopefully until a base case is reached). One pain point for me is the fact that there are thousands of possible game states. The algorithm will run through numerous game states as it evaluates the result of one move. How can I avoid an endless loop that results in my computer yelling at me over disk space?

My other pain point is the inability to break this algorithm down into chunks. I prefer to break things down into smaller pieces. It doesn't seem as though I'm going to be able to break down this algorithm. It's all or nothing with minimax. This is a bothersome attribute. However, starting out with near terminal game states will help me determine if my algorithm is correctly coded.

So I have a few main questions. I think once these are answered, I'll be closer to building a successful algorithm.

1. What is recursion and what more do I need to understand about recursion?
2. What are my base cases?
3. How will I evaluate each move and what will I do with that information?
4. How will I keep my move evaluation from being overwritten?
5. How will I avoid stack overflow?
6. What system will help me distinguish players and game states as I mark the board?
   
   These are a few questions that have been at the forefront of my research. So far, I have abstracted a plan that seems popular across articles and tutorials that I've found. These are the basic things that my algorithm will need to do in order to return a computer move:
   
   
7. The recursive method will take in a board and an object with scores from moves as parameters.
8. Return a base case: arbitrary numbers to represent a terminal state (0 for draw or -1 for a win).
9. Get the number of available spaces on the board.
10. For each space, update the board; collect the score from that move by calling the recursive method and store the best score in a move score object. Property/value being move and score respectively.
11. Reset the board space as to prepare for the next available space to be evaluated.
12. Return the best move or highest score value, depending on the level of recursion.
    
    So that's where my head is at right now. I'm hoping to start coding today after reviewing my resources for the upmteenth time. Talking about my pain points are helping me think of additional questions and visualize my knowledge gaps.
    
    My resources thus far have included:
13. Negamax with Pruning
14. How to Make Your Tic Tac Toe Game Unbeatable
15. Minimax Algorithm in Game Theory
16. Recursive Backtracking
17. Exhaustive Explanation of Minimax
18. Minimax with Alpha Beta Pruning
19. Search: Games, Minimax, and Alpha-Beta
20. Recursion is Not Hard