"Correct" Way to Wire a Tic-Tac-Toe AI
Posted by Sprawcketz@reddit | learnprogramming | View on Reddit | 18 comments
I'm working on a simple Tic-Tac-Toe game that includes a one-player mode against the computer.
I've got three levels of AI skill:
- Newbie - AI just selects a random available square
- Intermediate - Every time it moves, the AI will (in order):
- Try to play a winning move
- Or else, try to block an opponent's winning move
- Or else, play a move in any "open lane"
- Or else, play a random available move
- Masterful - ...and as you'd guess, this one is where I'm getting lost.
At first, my thought process what going something like:
"Phyiscally write out a bunch of potential move patterns and try to codify the optimal plays into the program using switching."
But that feels like the wrong way to do it. Also it could produce a BIG and UGLY set of nested switches. So then I thought:
"After each opponent move, give the AI player a "copy" of the board to play against itself and find the winning (or at least drawable) strategies and choose one (win > draw)."
But that feels like it'd wasting compute time (I know, probably trivial in human time), or like there should be a way that's more elegant than re-crunching everything after every move, every game. So then I thought:
"Ok, make the AI play itself a WHOLE LOT of times using some combination of random moves and mandatory opponent blocking and record the optimals / patterns that produce a forced-win."
But.... that sounds like programming a statistical neural network, which I'm not sure my limited and mathematically un-gifted experience is up to.
So my question is this: What is considered an "appropriate" strategy for building this kind of an AI player? Did I get it right with one of these thoughts, and I'm just to dumb to know it? Or is there a sweet-spot that I'm just missing?
(I've seen something about "Minimax" on Google, but.... I'm regrettably not trained professionally in any of this and don't have an algorithm education at all.)
CptMisterNibbles@reddit
Shoot, what’s the name of the machine learning “ai” for tic tac toe? This was one of the first attempts at machine learning; it went something like
1) have a little box for every possible game state,
2) in each box have a marker that says ‘if in this state, you may play here’. Choose randomly amongst possible choices.
3) if the machine looses a game, remove that as a choice marker the last time a choice was made.
4) if a box is empty, that means the computer cannot win for this state, so concedes.
Each time it plays and loses it learns what were bad choices, and eventually the only remaining chains of states are ones it will win, or must lose*
As tic tac toe is solved, I believe the computer cannot always force a draw, so a mature algorithm as above will eventually be unbeatable.
I saw this demonstrated by Steve Mould on an episode of Qi and meant to quickly program it. I may have some of the details a little off. I think this “machine” solver was made well over 100 years ago.
daniel14vt@reddit
After watching that video I had my computer science students build this. Very fun
BadBoyJH@reddit
https://www.youtube.com/watch?v=R9c-_neaxeU
randomjapaneselearn@reddit
what you mentioned is similar to Minimax algorithm https://en.wikipedia.org/wiki/Minimax
as other users said is pointless for this game because is too simple and short, but you can try to implement it for the game "connect four" which is kinda simple game.
-you will need a "valid moves generator" function (basically try to play in every column one by one)
-a scoring function (this can be as simple as: four pieces in line = 4 score, 3=3, 2=2 ....)
for details check wikipedia.
you can also add a "number of moves" bonus to the score so winning in 2 moves is better than winning in 8 moves, if you do this you need to set a different scoring function.
finally you can do minimax ab to make it faster: https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning
Usual_Ice636@reddit
Tic Tac Toe is too simple to need an algorithm. Theres just a list of moves to make where you always either win or tie.
Sprawcketz@reddit (OP)
So my first line of thinking was actually the most correct?
doPECookie72@reddit
only issue i see is, there is a "correct" choice for the first turn of each player that this does not account for. Going first, center is definitely preferred, and second, the corners are better than the edges.
worseboat@reddit
First move is a corner, second person plays center to tie, anywhere else is lose.
Usual_Ice636@reddit
For tic tac toe, yes. That is by far the most optimal way. Its one of the very few games simple enough for that to be the right answer.
Its not even that complicated of a system.
Sprawcketz@reddit (OP)
Got it – figures I'd over-complicate it (a "talent" of mine). Thank you!
Usual_Ice636@reddit
Almost any other game you'd be right its a bad idea, but Tic Tac Toe specifically has a simple flowchart of how to always win or tie. Its literally impossible to beat a computer thats not on easy mode.
multiple people have even taught chickens that "always win at tic tac toe" flowchart once.
SomeRandomUNa@reddit
Yes, and with 2 perfect players it will therefore always end in a tie.
dmazzoni@reddit
That may be true, but that doesn't mean it wouldn't be good practice to implement a more general algorithm like Minimax.
git_nasty@reddit
I don't play tic tac toe often, so let's give it a shot.
There are only six starting states for tic tac toe and the next move in optimal play is predetermined by the first move.(X or O, center, side, corner)
Priority is always third in a row, followed by blocking a potential three in a row. Next priority depends on board start.
Diagonal: Second player will want center, then side of opposite diagonal if it is third move. The rest of the moves are random if not covered by previous priority. First player will want opposite diagonal if possible. If not, any other diagonal. Any other diagonal again. Then random if not covered by previous priority.
I don't want to map out side/center, but same thing. You have a general if (make 3), if (block 3), then one or two optimal moves to decide the game based on starting turn.
Towel_Affectionate@reddit
When I did my version of the game, I did random cell for Easy and minmax for Hard. For medium I made computer roll d100 and based on the results either select random or use minmax.
lurgi@reddit
Tic-Tac-Toe is very simple and can be handled by a very simple algorithm, but
Minimax is the way to go for a lot of games. Unnecessary for Tic-Tac-Toe, but why should you let that stop you?
dmazzoni@reddit
You're basically on the right track here.
That's what Chess engines do, for example.
There are ways to make it more efficient, but essentially it's making millions of copies of the board and exploring all of the possible permutations of moves, in order to see which is best.
Basically: if I go here, then you go there, then I go here...and so on.
There isn't a more elegant way to do that in general, unless you find a shortcut for a particular game. There are only clever ways to optimize it to be as efficient as possible.
Tychotesla@reddit
So, as others said, tic-tac-toe is a simple game. But if it wasn't...
One way to think of problems like these is that you're navigating a directed graph, searching it for a solution. For example if you're playing chess, if you start with a node that's "move knight to put their king in check", the edges from that node only lead to nodes in which they move their king or they capture the knight.
This "Search AI" can be done with variations on standard graph search algorithms like BFS and DFS (lots of interesting elements to that). The real problem here is that in a game like chess, the graph becomes near infinitely large, so you need AI that can operate in near infinite space to hone in on the prize. "A*" search (pronounced "A star") is a simple and elegant solution that provides the core for a lot of search AIs. In really simple terms A* search says "search the graph in the direction of a good solution first".