Tic tac toe minimax

This project is killing me. I dont want to learn web development anymore. For days i dont know what to do and im wasting my time looking at the screen and that stupid blog post https://www.neverstopbuilding.com/blog/2013/12/13/tic-tac-toe-understanding-the-minimax-algorithm13. How to implement it??? i dont understand pseudocode, what is what or where to call that minimax function.

I felt the same way, don’t worry. If it’s killing you, maybe take a break a couple of days. I would advice to make sure that you have a good handle on recursions before implementing it.
Tomorrow I’ll try to find time and explain a bit more if someone else wouldn’t have done it by tomorrow :D.

please check if you can beat it and if its ok https://codepen.io/dodo14/pen/NYPJmG

https://codepen.io/dodo14/pen/NYPJmG please check if you can beat it and if its ok

damn. thanks for trying it

I beat it once too after 15-20 tries, It’s really hard tho, I tried to find a pattern and I did, it doesn’t work every time but if you make the first move at the center square and then at the bottom right one, it’s winnable.

Like askeroff said, take a break, let the algorithm just sink in your brain, the brain processes information subliminally too, a lot of times I have woken up in the morning having found the solution to an algorithm/problem I had a couple days before, or having understood an explanation that the previous day I couldn’t! :stuck_out_tongue:

Good luck!

thank you. i will take a break, maybe even do the simon game and then get back to this. I’ve had literally dreaming about minimax last 2 days i swear :frowning:

It’s just poor instructions from FCC. The point of the exercise is not to get you into AI coding, but frontend, so like it was already said, there’s no need to write an optimal strategy algorithm.

For the same reason it was removed from beta and is now completely optional, hidden in the interview section.

so my tic tac toe doesnt have to be unbeatable to complete the challange and eventually get front end certificate?

oh i thought you meant i dont have to use minimax to make it unbeatable but some other algorithm. sorry i misunderstood you.

Take it as a lesson in reading specifications. Nowhere did the instructions say what kind of moves the computer must play.

1 Like

For minimax in short:

  1. you need a function that can check who has won the game
  2. I kept also who is AI and who plays the user.
  3. Each time recursive minimax starts I check the current board state (and then later with recursion the next possible generated state of the boad) and see who has won with the function I mentioned in the first item. If the AI has won the game then return 10 - depth, if the user has won then depth - 10, if it’s a draw then return zero. What’s depth is the level of your recursive function. First called is zero, then + 1 after that.
  4. Also, you need a way to make sure that a board cell is empty
  5. Keep arrays for moves and for score
  6. Inside this recursive version you need to constantly flip who the current player is. Basically, the AI always player after the user, so when you first call it nexPlayer is AI, then user, then AI. Basic if condition wil suffice to flip them constantly with each recursive call.
  7. Then, what happens is the recursion itself. There are gonna be a lot of recursions, so if you want debug this process, use browser debugger, don’t put console.log in there, for me it really slowly kills the browser.
    8 The recursion itself: for this recursive function you pass depth as I mentioned earlier, first time 0. a board (keep the board as the array of your choosing, I chose one dimensional array from 0 to 8 for each spot). Also you need to pass nextPlayer, as I mentioned earlier you need to keep an eye on who is next whilst generating states.
  8. More of the this recursion: For each board go through a loop for all avialable spots that are not empty, put nextPlayer there, push this move (choose by the current index inside of for loop, within 1 dimensional array that works fine) and push to scores the result of this recursive function. It means that inside this foor loop you create a copy of the passed board, determine who is nextPlayer and if there is empty sport available call the recursive function with this copied board, nextPlayer and depth + 1. and push the result to scores.
  9. After all these calls are done your scores will be populated with values, based on the first condition I mentioned. If the winner is AI the depth - 10 (positive score), if the winner is player then depth - 10 (negative)< else zero.
  10. After all this recursive hell is done, you are back in your first call of the function with the depth zero but scores alreade populated. Check for that, and if you are there, choose nextMove based on maximum value in the scores array.

There are probably things I left out and I’m not sure if I explained it any good, check out my code or somebody else’s for this thing. Try to go through line by line if you really want to implement it.
If not, then just come back to it later, or don’t do it at all. As mentiond earlier, in the specs of this project, nobody mentions that is should be unbeatable.

1 Like

thx man. one day i will definitely try minimax cause it pisses me off.

Minimax is one of the things I’m most proud of overcoming.

The challenge to understand how and why it works is equally as hard as making it work that way.

But eventually, once I realized that for each space on the board, there is at least one move that is optimum for either the player, or the computer, and the minimax function identifies it by cascading down the tree of possible moves that step from each open space.

Then, based on the best possible result for the AI (assuming the player will pick the most optimum move when they play, will be a tie) it will pick that square to move. At some point if everyone plays the optimum move, there will be a square where the AI will have to move to, otherwise the player will and will lose. That is the “min” part of “minmax”, and will be the only non-zero square available of all the empties.

However, you need the “max” part of the function in order to catch a mistake by the player. If the player leaves a spot open for the AI to win, the AI needs to catch values greater than zero to move there instead, and thus, win the game.

It’s very clever, and it was very challenging to code for me.

1 Like