Can't figure out minimax code for tictactoe

1

I’ve been trying to figure out the code minimax (to be used in the tictactoe assignment) but I just can’t seem to grasp it. I’ve consulted so many sources from wikipedia and other websites (an example is this article: https://medium.freecodecamp.org/how-to-make-your-tic-tac-toe-game-unbeatable-by-using-the-minimax-algorithm-9d690bad4b37) to kind of understand how it works but I just can’t seem to get it inside my head. Right now, I feel like I’m failing a class since it’s taking way too long for me to solve this.

If anyone can help me with this problem, I’d be truly grateful. I want to really understand how it works and unfortunately videos or reading material is not doing it for me. Here is my code for minimax: https://codepen.io/qwirkyrabbit/full/prNqjx/

If anyone is able to review it and let me know what I’m doing wrong, then I’ll be so happy. For now, I’m testing tictactoe board scenarios manually (without the interface yet) and checking my results on the console. Please don’t be angry at my code, I know it’s messy but I will clean it as soon as I figure it all out.

2

All i can say is I feel your pain, I had the same problem, I spent days pouring through the minimax algo and just could not wrap my brain around it to save my life, and I refused to use anything in my project I could not understand and be able to explain.

So after banging my head against the wall, I ditched the idea of using minimax and set out to write my own algo. Its not perfect, I still need to tweak it a bit and Im sure that when Im refreshed and go back to it Ill be able to make it so much better, but as intimidating as that sounds to do, writing my own code was a million times less stressful than trying to understand minimax.

1 Like
3

Maybe this would help?

4

Unless you have a very strong understanding of the algo it’ll be difficult - look at other implementations of the algo and try to write something similar and you’ll get something put together that works. Good luck :slight_smile:

5

Hey midnite,

Don’t feel that you have failed a class! FreeCodeCamp is very different from a traditional class in that you really are learning on your own and coding projects from scratch.

I would suggest that you start over with a clean slate. If your code is well organized and you have your variables set up and know what to do, you can accomplish this much more easily.

Here is what I did. First, I figured out how to represent a game state as a string of numbers. The numbers corresponded to the moves the players made. I represented the squares on the board with a magic square:

2 7 6
9 5 1
4 3 8

which makes it easier to test for a won game (more on that later). So, if X goes first, then X picking the top left corner, O picking the center, and then X picking the top right corner, the state of the game would be represented by “256”. If X picks the center left and then O picks the bottom right, the state of the game would be “98”. If nobody has moved, the state is “”.

Then you need to figure out how to “evaluate” these positions represented by strings. We will store the evaluations in a JavaScript Map. A Map is simply a bunch of key-value pairs, in this case string-integer pairs. The strings are the game states mentioned above, and the integers will be the game evaluations. The reason why we store these values into a Map is to access them later without having to recalculate everything.

Now on to the actual evaluations. An evaluation is an evaluation of the position for the player that just moved. The evaluation represents the outcome with best play from both sides from here on. If the position is an eventual forced win (or an actual win right there), the evaluation is positive: 10 minus the total number of turns for the eventual win. If a win cannot be forced and the opponent cannot force a win, the evaluation is 0. If a win cannot be forced but the opponent can force a win, the evaluation is negative: -10 plus the total number of turns for the eventual loss. We worry about the number of turns because we want the computer to force a win as quickly as possible, if it can in fact force a win.

So, the evaluation of “2651” is -5 because the second player just allowed the first player to win by playing 8, which is a win in 5 moves. Remember that the evaluation is for the player that had just moved.

To calculate an evaluation, first see if the position is an immediate win or draw for the player that just moved. One can check for a win by seeing if any triplet of numbers for the player who just moved add up to 15. This is because of the magic square property of the number labeling. One can check for a draw if the string has length 9 i.e. all moves have been played. If there is no immediate win or draw, then we use recursion.

This is where minimax comes in. We want to take our string i.e. “45” and try every possibility for the next move: “451”, “452”, “453”, “456”, “457”, “458”, “459”. We evaluate recursively all of these positions. Then, we select the minimum of the negatives of these evaluations. We select the minimum of the negatives because that would be the best move for player 1, and so player 2, who just played 5 in “45”, has to take into account player 1’s best possible response. A win for player 1 is a loss for player 2, and vice-versa.

Now that positional evaluation is taken care of, the last requirement is to be able to make moves. This means turning a string “3” into a string “35”. I.e. if player 1 moved by selecting number 3, then the computer (player 2) should respond by selecting number 5. In my program, a move is chosen at random amongst the possible moves that have the negative of the same positional evaluation as the previous position, so that the computer ensures it’s making one of the best possible choices. This is a nice feature, so that the computer doesn’t play the same way every time, yet still plays perfectly.

My codepen with just the tic-tac-toe engine is here. It shouldn’t require many lines of code: mine took about 60, and generally speaking, it shouldn’t take more than 100…

Let me know if you have any questions.

6

Thanks @cndragon! Yeah, I was initially thinking if it would have been easier to write my own code from the get go but if I used the minimax algorithm and fully understood it, then I’d be one step closer to solve more complex algorithmic problems like the ones in technical interviews and such just like the pros do.

Awesome @sgoldber61, i’ll look into your codepen and start figuring it out and see if I can implement my tictactoe algorithm in a way that will be understandable. Oh man, I can’t even begin to tell you how happy I am that someone took the time to give me a descriptive answer. I’ll review it and update you with questions if any. Thanks!

2 Likes
7

Good luck!

One more thing: I saw earlier that you edited out a statement that said that what I wrote didn’t look like anything you’ve seen before. I don’t mind giving further clarification.

What I have is a minimax algorithm, and operates exactly the same as any other minimax algorithm in any sort of tic-tac-toe game or other decision-problem game.

I’ve just gone into detail explaining a way how to implement minimax for tic-tac-toe in a specific way. In minimax, one needs to define game states and one needs to figure out how to make evaluations. I’ve given a particular way of doing it: representing game states by a number string that represents the moves made. A lot of stuff here is similar to what’s described in this article I found: http://neverstopbuilding.com/minimax i.e. storing evaluations as 10 minus the number of moves it took. The only thing I’ve added in my post is a specific way of storing the game states and evaluating the game states.

Of course, you are free to use whatever resources you want/need, and you’ll in the end make the design decision of how to represent and store your game states.

Best!
-Sam.

8

The disadvantage of reading up on algorithms before actually trying your best at a solution of your own however clunky or inefficient is you lose the opportunity to really struggle and slog through a problem - this is something every serious programmer does on a regular basis to earn their worth

it’s quite easy to fool yourself into thinking that just understanding and implementing an algorithm is an adequate substitute for solving a problem yourself

2 Likes