Tic tac toe minimax

Tic tac toe minimax
0.0 0

#1

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.


#2

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.


#3

You do not have to use minimax algorithm for this project. You can create your own logic for the computer. Some campers don’t worry that their computer player can not beat or tie the player every game. They just have the computer randomly select an open square.

If you want the computer to always either win or tie, then you can search google for tic tac toe strategies (basically algorithms) and convert them into code.


#4

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


#5

#6

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


#7

I beat it.

image


#8

damn. thanks for trying it


#9

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!


#10

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:


#11

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.


#12

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


#13

I mentioned this in my first reply to you.


#14

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


#15

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


#16

Here is what I said above. Like @lynxlynxlynx said, the specifications (user stories) give you the basic requirements, but you are free to decide how the computer makes any move. Get it to do random open squares first and make it look nice. Then later, come back to the project once you have learned more about JavaScript and try to create a computer AI which always either wins or ties (using your own custom logic) or minimax.

For certificate purposes, do the minimum requirements for the projects. When it comes time to start showing off your portfolio to potential employers, pick a few projects you are most pround of and make them better with extra features and refactored code which is readable and concise as possible.


#17

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.


#18

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


#19

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.