I made an unbeatable Tic Tac Toe AI (Minimax algorithm)

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.

[@nextProgram]

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!

[@joshmohamed]

nextProgram I’d love to see the chess AI

[@patsen29]

Chess AIs are very interesting, and it's a deep rabbit hole. Definitely like to see your take on it.

[@nextProgram]

Glitch Jomo noted!

[@iminni3459]

I demand a video on this!

[@Channel-dp3wc]

I would like to see this

[@StrangeIndeed]

smh just hard code every single possible outcome

[@KingJellyfishII]

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.

[@stickfigure42]

XKCD 832

[@philfrisbie4170]

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 😎

[@thesabre8458]

@@philfrisbie4170 tbh most humans prob know every position

[@jailee6438]

Sabre *positions?*

[@Firigion]

"if not winner == False:" is some strong coding XD

[@samuelzlota2306]

if winner:

[@Firigion]

@@samuelzlota2306 ye

[@nextProgram]

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

[@Firigion]

@@nextProgram I'm sure it did. Htat's like the only reason to do something like that. It's funny nevertheless.

[@paulstelian97]

@@nextProgram Also if the winner could be 0 that line wouldn't even work as "if winner:".

[@asherhovell]

Get two, put em against each other.

[@englishmotherfucker1058]

automatic chess draws

[@aydenzinter2849]

@@themblue8236 r/iamverysmart

[@LazoGT]

Ayden Zinter if you think that's a smart thing to say, then im scared for your future

[@luminatron]

@@LazoGT bruh, it's meant *sarcastically.* Every entry in that subreddit is pompous arrogant pseudo-intellectuals like that guy above.

[@LazoGT]

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.

[@kyler7473]

Tic Tac Toe is such an unbalanced and unfair game, the developers obviously had no idea what they were doing.

[@nextProgram]

Haha true

[@andarerYT]

How is a game that's always a tie unfair? Or am I missing some new meme?

[@woxpop8792]

@@andarerYT In my family we always allowed moving the pieces after the fourth one has been placed.

[@Opasidity]

There is to much lootboxes

[@hustrik4805]

well every game is a tie ( almost xD ) if both play perfect

[@Creeperman1524]

“The only winning move is not to play”

[@user-le8ul4nr5t]

too bad we don't see this algorithm play against itself...

[@gus9351]

@@user-le8ul4nr5t tic tac toe is very simple, once you get the hang of it then it's always a draw

[@tricky778]

in tic tac toe the winning move is to play first, in a corner.

[@gus9351]

@@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

[@gus9351]

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

[@beri4138]

"Searching thorugh 255k positions is ridiculous". Stockfish 11 running at 20M nodes per second "amateur".

[@alexfresh8951]

True

[@erikaordog8288]

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 👍

[@nextProgram]

Oh I didn't know that was a thing. Well I know how to use the % operator, so I guess so?

[@Lance0]

S a m e t h i n g %=mod

[@jordananderson2728]

@@nextProgram % is modulo So 3%2 == 3mod2 = 1

[@Starwort]

@@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

[@somdudewillson]

Tic-tac-toe is a solved game tho. There's just a simple 8-step plan that will provide perfect play.

[@Cup-of-Joe]

I was wondering about this. The person who goes first always wins...

[@somdudewillson]

@@Cup-of-Joe Well, no. If played optimally, it will always end in a draw.

[@Cup-of-Joe]

Ah, I wasn’t aware of that haha. I’ll have to look that up.

[@somdudewillson]

@@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.

[@nextProgram]

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

[@terminallychill8029]

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.

[@CubeverseTutorials]

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!

[@nextProgram]

Nice job!

[@lilecaz9547]

Hello it might be a little late but could you send me your program? Thats exactly what im looking for

[@tuzcu680]

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!

[@nextProgram]

Maybe I stole the idea from you ;)

[@arsam3292]

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

[@nextProgram]

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

[@reversev9778]

nextProgram It would’ve taken me longer than a month

[@Spacebar]

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.

[@Fireball248]

@@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.

[@con_pi_tour_dice7147]

Unbeatable chess AI (so far) has already been made. Check ALPHA 0 or Google deepmind.

[@ImAlexander_YT]

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....

[@erikaordog8288]

Impressive! Can’t wait for the chess video!

[@nextProgram]

Erika Ordog wow thanks!

[@TFWPLSSUB]

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

[@stevencvisuals]

can you link the github/ or show us the full source code? That would be very helpful if you do!

[@HeilmwaterStudios]

KZbin algorithm likes your algorithm

[@huydh]

Very informative and entertaining! Your channel will be big, bro ;)

[@nextProgram]

I appreciate that!

[@filipe_paixao]

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

[@Philyshark7]

Can't wait for the chess one!!!

[@nextProgram]

Philip Elbert coming soon!

[@-_lIl_-]

now make that AI go against a clone of itself

[@Hyrtsi]

Looking forward to your chess AI :)

[@anonymous-ds3mc]

I remember as my school project i made a person vs person tic tac toe in c++, never decided to do the ai tho

[@vibaj16]

@C Lopez Hard coding that perfect game takes more code (although easier to do) than using minimax

[@anonymous-ds3mc]

"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.

[@angel-ig]

XD

[@puppergump4117]

I thought the scroll bar was mine and got really mad at youtube for it being in fullscreen.

[@JakeFace0]

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.

[@stickfigure42]

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.

[@stickfigure42]

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

[@MSFTSTRIO]

You can generate each endstate using itertools

[@Knights_of_the_Nine]

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.

[@matejnovosad9152]

I made this with Q learning and 2 ais playing against each other. Worked really well.

[@monochromeart7311]

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

[@dikshantraj6005]

Hey, there's an amazing course on game ai on kaggle using the game connect, I'm sure you'll love it

[@SrikarMaddula]

Now computer plays against computer, always draws

[@kairu_b]

This is awesome!

[@user-qr7zm9wo6z]

Make it play against itself

[@TextGuy]

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 :)

[@nextProgram]

Awesome!

[@beri4138]

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.

[@anidea8012]

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

[@mohammedjawahri5726]

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

[@widecat1404]

Can we get a download link for this? It seems fairly interesting

[@ccuuttww]

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

[@ttshs]

I have a strategy that wins in every circumstance except for one, which you tie in.

[@xeilot5358]

yes because if both players know each optimal strategy it always ends in a draw

[@developerx962]

This is very cool, thank you very much

[@nextProgram]

Glad you like it!

[@AaronWGaming]

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

[@Jack-rn3rm]

You should definitely try an AI for ultimate tic tac toe ;)

[@nextProgram]

That would be interesting haha

[@That_Guy977]

Is that the one with a big grid with 9 small ones?

[@gagidoo4757]

Tic tac toe toc

[@Jack-rn3rm]

@@That_Guy977 yeah, big 3x3 grid full of 3x3 grids it's good fun

[@That_Guy977]

@@Jack-rn3rm I've played it on coolmathgames as strategic tic tac toe i think, it's great

[@Neto_69]

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?

[@pokemonrampagemake]

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.

[@angel-ig]

Well, just recalculate the branches

[@teamdoodz]

You can make the board look nicer by using ASCII pipe characters instead of | and _.

[@nextProgram]

Good idea

[@teddieo7647]

That’s a little spoopy

[@nextProgram]

Yeah I guess

[@wassim5928]

I can beat easly because in tic tac toe there are two tricks to wins start from any corner or from the middel

[@arnoldsianturi2181]

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)?

[@abbasuccess3155]

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.

[@arnoldsianturi2181]

@@abbasuccess3155 Lol thanks a lot for this answer, i really appreciate it 😇 but thank god, i've been graduated my study on computer science 😂🤍

[@abbasuccess3155]

@@arnoldsianturi2181 good for you👍

[@jumhig]

I did minimax "noughts and crosses" in GWBASIC on a 386 PC in 1993, for a varsity project.

[@thyden2k]

finally, a worthy opponent

[@yit6]

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.

[@angel-ig]

Yeah, this "rule-setted" AIs were the ones in the 80s. Now there is minimax as well as machine learning like neural networks ;)

[@tricky778]

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

[@gregistopal]

Now have the AI play the AI

[@Mastervitro]

And here I thought there were only 512 possible games of Tic Tac Toe

[@ferencgazdag1406]

There are 512 possible end states of tic-tac-toe, but there are 3⁹=19683 possible states and even more possible games.

[@beri4138]

@@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?

[@ferencgazdag1406]

@@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.

[@ferencgazdag1406]

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.

[@Schnorzel1337]

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.

[@BlunderMunchkin]

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.

[@nextProgram]

This code isn’t really that complicated, it’s just a basic minimax algorithm

[@corniferjr3300]

I hope your chem exam went well after that 2 AM programming session

[@ToriKo_]

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

[@30svich]

how did it search through 255k positions, if there are only less than 3^9=19k positions?

[@saveerjain8168]

Hey I use Java but want to start some python. What software are you using to code?

[@Schnorzel1337]

Im not the creator of the video but eclipse with the pyDev Extensions works as you expect.

[@VerrouSuo]

shall we play a game?

[@mukeshtandale2325]

you could use ANSI Escape codes for a much better representation

[@okboing]

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

[@general5503]

we are all like that

[@MACHINEBUILDER]

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]

Did it take long to train? How many blocks and nodes?

[@MACHINEBUILDER]

@@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)

[@tricky778]

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.

[@Krishan_Verma]

what is the initial value of alpha beta?

[@vigintinek3718]

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?

[@nextProgram]

My guess is that that’s an issue with an infinite loop or infinite recursion!

[@legendaryspud3462]

Make a tic tac toe ai have a tic tac toe gladiator fight against him self!

[@oyungogdfrust4136]

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.

[@lubu682]

awsome!

[@darexleon]

Great TicTacToe program! Github Code?

[@snalgae]

What will happen, if 2 bots will play with each other?

[@nextProgram]

A tie :)

[@juliankaiser1323]

Is the ai always starting? Or does the player start against the ai?

[@lau4996]

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")

[@teddieo7647]

How long did this take?

[@nextProgram]

It took a few days to make the program. The video took about 10 hours to make

[@teddieo7647]

Wow nice

[@danifalkjensen]

lol my attempt at minmax worked in reverse the bot always tried to lose and never to win

[@matthewweitzner8956]

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.

[@ericj4094]

he uses sublime text omg liked and subbed

[@matschbirne5363]

1:25 i just used a 1 dimensional array when i did it.

[@mudasarahmad4419]

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!

[@nextProgram]

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!

[@acumen8566]

Could you make upload a copy of your tic tak toe code?

[@allennelson1987]

Nimbers?

[@hanafifadzillah1621]

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.

[@nextProgram]

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

[@hamzaabbaszaidi8788]

Which editor did you use?

[@nextProgram]

This was Sublime

[@pe3akpe3et99]

now make 3d tic tac toe AI

[@matejnovosad9152]

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.

[@nextProgram]

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.

[@matejnovosad9152]

@@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.

[@suryakiran3085]

But , it is easy to stay unbeatable in tic tac toe ..

[@pyrodynamic4144]

Am I the only one who thinks he sounds like 3blue1brown?

[@MudakTheMultiplier]

Hypothetically would it be possible to beat a minimax AI with alpha beta pruning by taking paths that it had already pruned?

[@nextProgram]

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

[@MudakTheMultiplier]

@@nextProgram presumably this only works with games that can be "solved" then?

[@nextProgram]

Mudak The Multiplier Kind of. You can also use it for chess, for example

[@mytypeofjordan]

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)

[@nextProgram]

Torus tic tac toe? :o

[@JustinSletcherMusic]

"is" is usually for type checking, if I'm not mistaken

[@nythepegasus]

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.

[@JustinSletcherMusic]

@@nythepegasus Ya, I haven't used Python yet, but been programming in swift and it's obviously a bit different.

[@Rahul-lg1nw]

Source code?

[@DylansLappalterCopium]

I too, am unbeatable in Tic Tac Toe. 😎

[@sadhlife]

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

[@aniketsahu9316]

Can we get the code please?

[@bensmart2829]

are we gonna talk about if not winner == False

[@nextProgram]

Lol let’s not

[@mateuszabramek7015]

At 3x3 everyone can only draw.

[@Vescena]

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?

[@nextProgram]

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

[@greengriffon7179]

Bruder i have all the tic tac toe strategies memorized its easy

[@petfama4211]

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

[@DevWithMartinus]

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.

[@petfama4211]

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?

[@DevWithMartinus]

​@@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 : kzbin.info/www/bejne/ol7LmWhno8iaeqs

[@petfama4211]

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.

[@DevWithMartinus]

@@petfama4211 Yup that's the biggest cons of minimax is that it assumes that the opponent will choose the most rationale choice each time.

[@davidkedra3001]

Can someone please help me I have an error in my code I cant find @t

[@Mark-wy7oq]

Can you send me the code please?

[@usamasom59]

Can i get this code?

[@ExamSolutions.e]

cool