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!
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 😎
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
@@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
@@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
@@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.
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!
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.
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!
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
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.
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, 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 :)
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.
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.
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
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
"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.
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
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
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.
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 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)
@@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)
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
@@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 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.
Why did your AI, even after searching all those games, still play a first move that is guaranteed to result in a draw? Would make sense for it to at least play something that can result in a win
Probably because the first moves that can result in a win requires move from the opponent that it will never do (assuming the opponent will always choose the best move) and so it could lead the AI to loose the game.
Dev with Martinus ah that makes sense... seeing as the game of tic tac toe can only be won through exploiting your opponents mistakes, and the database it searches through assumes no such mistakes; doing anything but moves that guarantee the best score (that being a neutral 0 seeing as positive scores aren’t even in the database), even if it’s technically still impossible for a perfect AI to ever lose and may even give it the option to win, would still only take into account it’s own mistakes and not the opponents, and therefore yield an average score of less than 0?
@@petfama4211 Sorry but I don't really understand what you mean. English is not my first language. Just keep in mind that minimax is a very basic algorithm, it can really "take into account its own mistake" or search through a database. There isn't a database actually, each turn the algorithm compute the possible states after X turn and choose the one that advantage it the most and disadvantage the opponent. This video explain it in details : ruclips.net/video/l-hh51ncgDI/видео.html
Dev with Martinus what i meant with database was simply the 200,000 or so games it searched through in order to set up the minimax algorithm to begin with, so really it’s just the algorithm. The main problem i think isn’t actually that it disregards the opponents mistakes; meaning you’d always wanna settle for a guaranteed score of 0 (a tie) as it’s the highest score possible (positive scores being impossible); but actually that the algorithm on an unequal basis factors in your own mistakes by leaving branches of the algorithm unoptimized in a way before deciding (don’t know how to explain it). If it treated you equally and ignored your possible mistakes as well (which makes sense for an AI) then other good moves would not yield an average of below zero, but actually 0 as well, and the AI could thus choose good moves at random, some of which would not 100% guarantee a draw.
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")
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
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.
You know that minimax would be better for more better outcome game right? I mean for tictactoes we can just use recursive backtracking and averaging the possible win for each branches possibility would be better it would start at center like people do bc it know it lead to more wins while minimax think it all the same
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.
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!
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
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
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.
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.
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)
this is over kill though, you can do it just by searching the current board. wikipedia explains the strategy. then again you probably already knew that
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
"Searching thorugh 255k positions is ridiculous".
Stockfish 11 running at 20M nodes per second "amateur".
True
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
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 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.
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 ;)
RUclips algorithm likes your algorithm
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.
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....
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
can you link the github/ or show us the full source code? That would be very helpful if you do!
Impressive! Can’t wait for the chess video!
Erika Ordog wow thanks!
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.
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.
I thought the scroll bar was mine and got really mad at youtube for it being in fullscreen.
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
now make that AI go against a clone of itself
Make it play against itself
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
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
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
"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
Can't wait for the chess one!!!
Philip Elbert coming soon!
Now computer plays against computer, always draws
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
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
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👍
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
You can make the board look nicer by using ASCII pipe characters instead of | and _.
Good idea
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
You can generate each endstate using itertools
Can we get a download link for this? It seems fairly interesting
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)
Very informative and entertaining! Your channel will be big, bro ;)
I appreciate that!
I hope your chem exam went well after that 2 AM programming session
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
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
Looking forward to your chess AI :)
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.
How long did this take?
It took a few days to make the program. The video took about 10 hours to make
Wow nice
shall we play a game?
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
What will happen, if 2 bots will play with each other?
A tie :)
Why did your AI, even after searching all those games, still play a first move that is guaranteed to result in a draw? Would make sense for it to at least play something that can result in a win
Probably because the first moves that can result in a win requires move from the opponent that it will never do (assuming the opponent will always choose the best move) and so it could lead the AI to loose the game.
Dev with Martinus ah that makes sense... seeing as the game of tic tac toe can only be won through exploiting your opponents mistakes, and the database it searches through assumes no such mistakes; doing anything but moves that guarantee the best score (that being a neutral 0 seeing as positive scores aren’t even in the database), even if it’s technically still impossible for a perfect AI to ever lose and may even give it the option to win, would still only take into account it’s own mistakes and not the opponents, and therefore yield an average score of less than 0?
@@petfama4211 Sorry but I don't really understand what you mean. English is not my first language.
Just keep in mind that minimax is a very basic algorithm, it can really "take into account its own mistake" or search through a database. There isn't a database actually, each turn the algorithm compute the possible states after X turn and choose the one that advantage it the most and disadvantage the opponent.
This video explain it in details : ruclips.net/video/l-hh51ncgDI/видео.html
Dev with Martinus what i meant with database was simply the 200,000 or so games it searched through in order to set up the minimax algorithm to begin with, so really it’s just the algorithm. The main problem i think isn’t actually that it disregards the opponents mistakes; meaning you’d always wanna settle for a guaranteed score of 0 (a tie) as it’s the highest score possible (positive scores being impossible); but actually that the algorithm on an unequal basis factors in your own mistakes by leaving branches of the algorithm unoptimized in a way before deciding (don’t know how to explain it). If it treated you equally and ignored your possible mistakes as well (which makes sense for an AI) then other good moves would not yield an average of below zero, but actually 0 as well, and the AI could thus choose good moves at random, some of which would not 100% guarantee a draw.
@@petfama4211 Yup that's the biggest cons of minimax is that it assumes that the opponent will choose the most rationale choice each time.
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")
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
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
You know that minimax would be better for more better outcome game right? I mean for tictactoes we can just use recursive backtracking and averaging the possible win for each branches possibility would be better it would start at center like people do bc it know it lead to more wins while minimax think it all the same
I can beat easly because in tic tac toe there are two tricks to wins start from any corner or from the middel
I made this with Q learning and 2 ais playing against each other. Worked really well.
Now have the AI play the AI
how did it search through 255k positions, if there are only less than 3^9=19k positions?
That’s a little spoopy
Yeah I guess
1:25 i just used a 1 dimensional array when i did it.
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.
Great TicTacToe program! Github Code?
Hey, there's an amazing course on game ai on kaggle using the game connect, I'm sure you'll love it
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.
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.
Could you make upload a copy of your tic tak toe code?
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
I did minimax "noughts and crosses" in GWBASIC on a 386 PC in 1993, for a varsity project.
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!
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.
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!
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
Which editor did you use?
This was Sublime
you could use ANSI Escape codes for a much better representation
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
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
This is awesome!
what is the initial value of alpha beta?
This is very cool, thank you very much
Glad you like it!
But , it is easy to stay unbeatable in tic tac toe ..
finally, a worthy opponent
Is the ai always starting? Or does the player start against the ai?
"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.
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.
What language is this?
It's Python
omfg i apologize in advance for being that person but.....
English
Nimbers?
Source code?
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
now make 3d tic tac toe AI
Am I the only one who thinks he sounds like 3blue1brown?
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
he uses sublime text omg liked and subbed
I too, am unbeatable in Tic Tac Toe. 😎
Can someone please help me I have an error in my code I cant find @t
You could've done
if winner != False:
actually yeah that could've worked too since winner is already a boolean in and of itself.
What year of school are you in?
I just finished my first year of university
At 3x3 everyone can only draw.
Can we get the code please?
are we gonna talk about
if not winner == False
Lol let’s not
this is over kill though, you can do it just by searching the current board. wikipedia explains the strategy. then again you probably already knew that