I made an unbeatable Tic Tac Toe AI (Minimax algorithm)
Vložit
- čas přidán 24. 07. 2024
- This video shows how I made my tic tac toe algorithm in Python. I used the minimax algorithm with alpha beta pruning to search through all possible game states and find the best move for the computer to make. The game can still end in a draw, but it should be impossible to win against it.
Minimax is a recursive algorithm -- it calls itself thousands of times for each turn the computer takes. This is a similar process to how basic chess AI's are created.
I keep calling it an AI (artificial intelligence) but I think technically it's just an algorithm. - Zábava
Update: the chess program is finished and I think it's working. I might put the video on hold for a bit, though. I'll probably still make it if there's a demand for it, so let me know!
nextProgram I’d love to see the chess AI
Chess AIs are very interesting, and it's a deep rabbit hole. Definitely like to see your take on it.
Glitch Jomo noted!
I demand a video on this!
I would like to see this
smh just hard code every single possible outcome
I once did that, it was horrific.
Well not really I just told it every possibility of two Xs or Os in a row and told it to either win or block.
XKCD 832
I did just that 40 years ago using BASIC, I was in high school. It is really easy once you realize that the 3x3 square board only has three starting locations: center, corner, side, and the corners and sides are just rotations 😎
@@philfrisbie4170 tbh most humans prob know every position
Sabre *positions?*
"if not winner == False:" is some strong coding XD
if winner:
@@samuelzlota2306 ye
Yeah I did that because I designed the function that produces the value for winner kind of weirdly. You'd need to see the code but that line made it slightly more readable in my opinion, haha
@@nextProgram I'm sure it did. Htat's like the only reason to do something like that. It's funny nevertheless.
@@nextProgram Also if the winner could be 0 that line wouldn't even work as "if winner:".
Get two, put em against each other.
automatic chess draws
@@themblue8236 r/iamverysmart
Ayden Zinter if you think that's a smart thing to say, then im scared for your future
@@LazoGT bruh, it's meant *sarcastically.* Every entry in that subreddit is pompous arrogant pseudo-intellectuals like that guy above.
Trinitrotoluene Monomania i know, but he's saying that he's trying to sound smart but is actually dumb, when it's not something smart to say at all.
Tic Tac Toe is such an unbalanced and unfair game, the developers obviously had no idea what they were doing.
Haha true
How is a game that's always a tie unfair? Or am I missing some new meme?
@@andarerYT In my family we always allowed moving the pieces after the fourth one has been placed.
There is to much lootboxes
well every game is a tie ( almost xD ) if both play perfect
“The only winning move is not to play”
too bad we don't see this algorithm play against itself...
@@user-le8ul4nr5t tic tac toe is very simple, once you get the hang of it then it's always a draw
in tic tac toe the winning move is to play first, in a corner.
@@tricky778 actually no, there is no winning move, you can place right about anywhere and you'll win, if you're second move, the safest move is middle because there's this thing that we call "Absolute Control" in which if I play for example in any corners, and if then the enemy does not play middle then there is at LEAST one square that would make the enemy block that move(hence controlling them) but you have to make sure that square does not connect to their first move because they would also gain absolute control and the game is tied so Absolute control a square that does not connect to the enemie's first move. Now you can win middle but there's no absolute control, it's only rng on where your enemy plays so if the enemy knows everything (which takes about 5 minutes to be learned) then game becomes boring, I only find it fun when in parties and playing and betting with random people, I'm always first move to secure victory and it's a great time always to win 10 bucks because of a tic tac toe game
Also if you're second and your enemy is naive, you can probably absolute control them if they somehow doesn't absolute control in moves 2 and 3
Do you know about modular arithmetic? That’s the idea you use for identifying the numbers 1 through 9 with a spot in the grid 👍
Oh I didn't know that was a thing. Well I know how to use the % operator, so I guess so?
S a m e t h i n g
%=mod
@@nextProgram % is modulo
So 3%2 == 3mod2 = 1
@@nextProgram you could simplify lines 52 and 53 into:
row, col = divmod(index - 1, 3)
Also the operator // is integer division, which you could have used on line 52 to remove the int cast
"Searching thorugh 255k positions is ridiculous".
Stockfish 11 running at 20M nodes per second "amateur".
True
I really like that you take the time to discuss the mistakes that you made. Even though they're sometimes elementary, they're usually informative to people who are starting out. This channel is great.
Tic-tac-toe is a solved game tho. There's just a simple 8-step plan that will provide perfect play.
I was wondering about this. The person who goes first always wins...
@@Cup-of-Joe Well, no. If played optimally, it will always end in a draw.
Ah, I wasn’t aware of that haha. I’ll have to look that up.
@@Cup-of-Joe en.wikipedia.org/wiki/Tic-tac-toe#Strategy
I still have a very old command-line player vs AI tic-tac-toe game that implements it on my hard drive.
This project was more about trying to implement the minimax algorithm haha. If you've seen my chess AI video, I used it for that
I saw this video in my recommended and instead of watching it, I attempted to make this myself in java. It took hours upon hours, but I finally made it unbeatable and even gave the whole thing a simple GUI. This is a great video, and it was interesting to see your approach in tackling this!
Nice job!
Hello it might be a little late but could you send me your program? Thats exactly what im looking for
I made a minimax dots-and-boxes AI a couple of years ago and this video was surreal to watch because i basically had the exact same console interface where I would print the entire grid at each turn and had numbers representing places on the grid. It all came back to me when I saw your function names because I think I also had a "check diagonals". Didn't have time to implement pruning though. Great video!
Maybe I stole the idea from you ;)
I just have to say, your channel is AMAZING. I found you when I was watching the DEVLOG of KARLSON. I still want to see more on keeper! keeper' up....
Impressive! Can’t wait for the chess video!
Erika Ordog wow thanks!
An unbeatable chess AI would probably take forever, Cant wait to see how long it takes you, also was your exam in person? cause if it was i feel bad for you considering the virus going on
Yeah it's been a lot of work so far. I'm posting a Unity devlog next week for a new game I'm making, so it should be ready 2 weeks from now. And no, the exam was online haha
nextProgram It would’ve taken me longer than a month
An unbeatable chess engine would need to run on a supercomputer for a long time, as this algorithm needs to calculate all the possible moves branching off of each next move to calculate the perfect move.
@@Spacebar you can get pretty close to unbeatable engines with deep learning, as seen in Deepmind's AlphaZero etc., but obviously it's not a perfect solution. However, it is extremely close and can beat the vast majority, if not all, human and traditional AI players and runs in a fraction of the time of traditional engines, as it considers only a few thousand moves as opposed to millions per turn.
Unbeatable chess AI (so far) has already been made. Check ALPHA 0 or Google deepmind.
Looking forward to your chess AI :)
Very informative and entertaining! Your channel will be big, bro ;)
I appreciate that!
can you link the github/ or show us the full source code? That would be very helpful if you do!
The reason using “is” didn’t give you an error is because it checks if the thing is same or not, like using == to compare numbers and strings only gives False
Hey just so you know: In python you can replace int(a/b) with a//b. The // operator is an integer divide operator. It returns the floor of a/b and (I think) is more computationally efficient as it uses something similar to repeated subtraction rather than doing a computationally expensive floating point division.
There's no particularly notable efficiency difference, it's just nice to be able to write it that way. The more important consideration for some people is that if you're working with *really* big numbers, a // b will give you the correct answer, and int(a / b) will give you the wrong answer.
For example:
>>> 10 ** 1000 // 2
(5 with 999 zeros)
>>> int(10 ** 1000 / 2)
Traceback (most recent call last):
File "", line 1, in
OverflowError: integer division result too large for a float
Can't wait for the chess one!!!
Philip Elbert coming soon!
CZcams algorithm likes your algorithm
I guess you're new to Python, welcome!
A language that did 90% of the heavy lifting for you and I love to use for servers
I remember as my school project i made a person vs person tic tac toe in c++, never decided to do the ai tho
@C Lopez Hard coding that perfect game takes more code (although easier to do) than using minimax
This is awesome!
"Early challenges, taking the number of the space wanted and convert to 2d array" I just hard coded 1 to 0,0; 2 to 0,1 etc and made a function that returns it.
XD
Hey, there's an amazing course on game ai on kaggle using the game connect, I'm sure you'll love it
I know in C that "=" basically sets a value. So while(x = 0) will always move to the next instruction because it will MAKE x 0 and then because it's false it'll move on instead of loop. While(x == 0) will loop though as long as x is 0.
I don't know how it works in python yet =p.
hey, i just made a Chess AI and a video about it few days ago, it is my first time and its quite a fun project to do, but its quite complicated for me , because chess has so many possibilities and i am quite stuck in the finishing state ,will love to see yours :)
Awesome!
You just need a search algorithm and an evaluation function.
Use Alpha Beta search and a simple evaluation that counts the material.
You can then add various bonuses and penalties to the evaluation.
For example: doubled pawns bad -0.5, backwards pawns bad -0.5, passed pawns good +0.7, etc.
Also look into "move ordering" so your program searches the most promising variations first and only then the weird moves.
You can also add tablebases and an opening book to make your program play stronger.
This is very cool, thank you very much
Glad you like it!
Can we get a download link for this? It seems fairly interesting
tic tac toe + rock paper scissors. = kinda a best game
Chose your position in tic tac toe, then play rock paper scissors, if you win you maintain your position, if you lose your can't chose that position and play rock paper scissors again after choosing another one, in case no position is left your adversary choses your position for you. In case of ties just play again
I am new to coding and I have a question. After the alfa-beta pruning and some branches are "cut off", what happens if the player doesnt make an optimal move and chooses a branch that the AI didnt consider?
This has happened before for chess AI, usually they have a database to record the moves, so in the future they’d be able to identify it in the future, also, once the move is played, the AI goes back to check it to figure out its next move.
Well, just recalculate the branches
Hey at 3:30 the minimax function
is it necessary to do winner = checkGameIsOver(board) in every recursion?
If we can skip in some recursion we can speed up the caculation
I have an old I3 CPU PC it takes 3 seconds to finish
I made this with Q learning and 2 ais playing against each other. Worked really well.
You can make the board look nicer by using ASCII pipe characters instead of | and _.
Good idea
You should definitely try an AI for ultimate tic tac toe ;)
That would be interesting haha
Is that the one with a big grid with 9 small ones?
Tic tac toe toc
@@That_Guy977 yeah, big 3x3 grid full of 3x3 grids
it's good fun
@@Jack-rn3rm I've played it on coolmathgames as strategic tic tac toe i think, it's great
Instead of , You can use this , new index = Column_index + row_index * Number of column ; by this way you convert 2d array into single array
For anyone reading this in the future it's good to think about what it represents so you'll never have to memorize it
You are essentially checking how far down the 2d grid you are (how many rows in) and multiplying that by the width. Because each row you go down represents crossing all of the width cells right above you. Hence row*width skips all the rows above you, then you add the current col to represent how far along you are in the current column
now make that AI go against a clone of itself
That’s a little spoopy
Yeah I guess
I wanna ask, I kinda confuse. How can we determine the score (in the leaves of the tree) of TicTacToe? Isn't the score/value should be +1 (for winning) or 0 (for draw) or -1 (for losing)?
Yeah I know this is late, but you could just give a value, like the number of empty squares, multiplied by 1 for winning, 0 for tie and -1 for losing.
That way the ai can make moves that help it win the fastest, cause if it can win when there are 4 squares left, that move would have a score of 4 as compared to a later winning move when there are 2 squares left with a score of 2.
@@abbasuccess3155 Lol thanks a lot for this answer, i really appreciate it 😇 but thank god, i've been graduated my study on computer science 😂🤍
@@arnoldsianturi2181 good for you👍
Now computer plays against computer, always draws
I did minimax "noughts and crosses" in GWBASIC on a 386 PC in 1993, for a varsity project.
Umm it is easy to do since there is only 3 moves players can start with center corner side, starting side gives opponent the chance to win center gives NO CHANCE as it leaves opponent with 2 moves (Corner/ side) one leads to a tie and the other (side) causes X to win always. Corner and side give opponents 5 different moves each
You can generate each endstate using itertools
Could you make upload a copy of your tic tak toe code?
Hi, Can you explain a bit more why you used: return -10 + depth and return 10 - depth
What is its logic? i need this, will really appreciate your help!!!
Thank You!
Hey! If I remember correctly, that will allow the algorithm to prioritize winning the game in fewer moves. The depth will always be less than 10 since there are only 9 possible slots. Basically, the algorithm won't choose a move that wins in 5 moves if it can win in 3 moves, because the score will be higher for the 3 move case!
Make it play against itself
Make a tic tac toe ai have a tic tac toe gladiator fight against him self!
Legendary spud it would end with a tie every time since they both always do the best possible outcome to counter the best possible outcome.
Hey man, can you explain to me why you made a 2d array instead of a list?
you could just do
list = []
x = 0
while x < 9:
list.append(x)
x += 1
for arg in list:
print("""
{0} | {1} | {2}
-----|------|-----
{3} | {4} | {5}
-----|------|------
{6} | {7} | {8}""").format(list[0], list[1], list[2], list[3], list[4], list[5], list[6], list[7], list[8])
if not x == 8:
IntToChange = input("which booth do you want?: ")
list.replace(IntToChange, "o")
I have a strategy that wins in every circumstance except for one, which you tie in.
yes because if both players know each optimal strategy it always ends in a draw
1:20
Could you help me understand why you couldn’t do something similar to
user_input = input(“choose from 1-9 ”)
position = user_input -1
Edit: oh I think I just realized it’s because your board is a bit more complicated
Edit 2:
Well actually you could keep a 0-8 list and just make a display_board with the board, eg:
positions = [1, 2, 3 etc]
display_board = positions(1) + “||” + positions(2) etc
I got this stuff built into my brain tho
Ngl I've only really lost when I was young
Now I only tie and win
we are all like that
what is the initial value of alpha beta?
I can beat easly because in tic tac toe there are two tricks to wins start from any corner or from the middel
how did it search through 255k positions, if there are only less than 3^9=19k positions?
I made a tic tac toe algorithm one time. It was unbeatable, what it did was win if it could, then it would block, then go in a corner.
Yeah, this "rule-setted" AIs were the ones in the 80s. Now there is minimax as well as machine learning like neural networks ;)
You can beat it if you go first, if it goes first it can win but you can force a draw, but the strategy you gave can lose even if it goes first. The best first mover is: corner, opposite corner, block or else 3rd corner, win or else block until a draw
I hope your chem exam went well after that 2 AM programming session
awsome!
Hey I use Java but want to start some python. What software are you using to code?
Im not the creator of the video but eclipse with the pyDev Extensions works as you expect.
finally, a worthy opponent
Hi. I'm making similar alogorithm as yours. But I've got a problem with MemoryError: Stack overflow. Have you get it? If yes how did you solve it?
My guess is that that’s an issue with an infinite loop or infinite recursion!
he uses sublime text omg liked and subbed
you could use ANSI Escape codes for a much better representation
But can you make a program where CPU always win against human (Draw isn't included)? Whenever I play tic tac toe, the game usually end in draw.
Hanafi Fadzillah Nope, the only thing you can guarantee is that the CPU never loses. The algorithm is unbeatable, but it doesn’t necessarily always win. Like you said, it’ll end in a draw if both players are skilled
And here I thought there were only 512 possible games of Tic Tac Toe
There are 512 possible end states of tic-tac-toe, but there are 3⁹=19683 possible states and even more possible games.
@@ferencgazdag1406 How did you get that number? There are 9 possible first moves, 8 possible second moves, 7 possible third moves, etc.
So the number of positions is obviously 9x8x7x6x5x4x3x2 = 362880.
Do you even math bro?
@@beri4138 But each position on the board can be achieved indifferent ways, so the number of possible positions is less. It is also possible, that a sequence of moves can not be carried out, because the game is won halfway thru, so the number of possible moves is also inaccurate. 512 is assuming, that at the end of the game each tile is filled, so it is 2⁹, but it doesn't have to be this way, and there are 3⁹ possible states, but not really, because
OOO
XXX
is not a possible state what can arise during a normal game, or as an end result.
It is difficult.
What i have found, is that at the fifth move, where a game can be won, there are 630 board states and 15120 possible games, and got stuck there, gone to sleep.
You should consider symmetry that way there are 3 moves at the start: In the mid, a corner or between two corners. For those you can get: Mid 2, Corner 4 , between 5. So implementing a simple rotation and mirroring routine would reduce the number of possible games drasticly.
I thought the scroll bar was mine and got really mad at youtube for it being in fullscreen.
I wrote a neural network which played against itself so that it'd learn to never lose a tic tac toe game :)
(In python - the superior language - of course)
Did it take long to train? How many blocks and nodes?
@@beri4138 actually not that bad. It's quite simple, 9 input nodes, 2 hidden layers of 9 nodes, and one output layer of 9 nodes. I trained it against a random bot for about an hour (a few thousand games)
lol my attempt at minmax worked in reverse the bot always tried to lose and never to win
If the bot is trying to lose, make sure you have the minimizing player vs. maximizing player right, and that minimizing vs. maximizing the score works, and if what you mean is that it just picks the next spot in order, not that it actively moves away from a line of 2 when that is the next spot, then I don't know how to help you, because that's exactly the problem mine has.
Can someone please help me I have an error in my code I cant find @t
Great TicTacToe program! Github Code?
Is the ai always starting? Or does the player start against the ai?
Now have the AI play the AI
Can i get this code?
What will happen, if 2 bots will play with each other?
A tie :)
Can you send me the code please?
shall we play a game?
Can we get the code please?
How long did this take?
It took a few days to make the program. The video took about 10 hours to make
Wow nice
Hypothetically would it be possible to beat a minimax AI with alpha beta pruning by taking paths that it had already pruned?
Mudak The Multiplier Nope, it only prunes moves that have to be worse than ones it’s already found. It assumes the opponent is playing perfectly, so if the opponent plays worse than perfectly then it still works
@@nextProgram presumably this only works with games that can be "solved" then?
Mudak The Multiplier Kind of. You can also use it for chess, for example
Source code?
Which editor did you use?
This was Sublime
if you wanna check out a really clean Python tic tac toe (no AI tho) i just made one a few days ago, it's on github.com/tusharsadhwani/tic.py
Did this on a 48K sinclair spectrum when I was 10. Just made an array with every game state in it and pruned every path from a losing state back to the initial state leaving all the winning moves only.
cool
There is way less states I made a tic tac toe ai a month ago and there os maximum of 3^9 states. Which is acctually less because not all are valid.
www.jesperjuul.net/ludologist/2003/12/28/255168-ways-of-playing-tic-tac-toe/#:~:text=Here's%20a%20document%20with%20every,player%2C%20and%2046%2C080%20are%20drawn.
@@nextProgram ok I commented and then coded this from scratch and yeah there is that many games possible, although not as many *unique* end states.
now make 3d tic tac toe AI
Bruder i have all the tic tac toe strategies memorized its easy
i did my IB math IA on torus tic tac toe and learned way too much about the game, so i greatly enjoyed this. (spoiler alert: player 1 wins every time without fail in torus tic tac toe)
Torus tic tac toe? :o
why use a 2D array instead of partitioning a 1D array into 3 sections?
i don't know his reason
but printing the board will change and there are likely other reasons
Nimbers?
"is" is usually for type checking, if I'm not mistaken
is is actually for finding if two variables are the exact same. So setting a variable to True, and then checking if variable is True will result in True, because they both reference the same memory location. Setting variable c = [1,2,3] then a = c and then running a is c will result in true, whereas setting a = list(c) will result in false (because you made a new list object in memory, instead of just referencing the first object). Running id() on variables helps to find which two would return True with is.
@@nythepegasus Ya, I haven't used Python yet, but been programming in swift and it's obviously a bit different.
I too, am unbeatable in Tic Tac Toe. 😎
I’m perfect at tic tac toe too, it’s pretty easy
Am I the only one who thinks he sounds like 3blue1brown?
The thing I don't get is if they can beat you every time, if you do the same thing the AI does, can't you beat anyone every time too?
Not quite. It can’t beat you every time, it just never loses. So the game could end in a tie if both players are playing perfectly
30 years ago a bunch of people at MIT built an unbeatable Tic-Tac-Toe computer. They built it out of Tinker Toys. Your algorithm might be more complicated than it needs to be.
This code isn’t really that complicated, it’s just a basic minimax algorithm
Wow I just made this in python some time ago😂
Cool!
are we gonna talk about
if not winner == False
Lol let’s not
But , it is easy to stay unbeatable in tic tac toe ..