Tic-Tac-Toe AI
Author
I started making a two player tic-tac-toe (naughts and crosses or what ever its called) about 2 days ago, as my first attempt at making something "worthwhile" in c++. Now I have finished, I was thinking of adding in an AI opponent, and I came here for a bit of guidance.
The only way I can think of coding an opponent, is to use lots of if statements or something to that effect, to give a "priority" to every square, and then have it choose the highest priority square.
My "grid" is stored as a single vector or int's. Is there a more efficient/straight forward way than all those if statements and would it be easier/better if my grid was stored as three vectors in another vector?
Thanks for any help you might give.
Using a single vector would be the best way really, its more efficient and not exactly difficult to use.
If I remember correctly tic tac toe is one of those games where if you're clever enough then you can never lose at it, only draw or win. As a result a computer could easily be made to never lose which would (for this game atleast) be utterly unfun.
To be honest I think that you could achieve the illusion of a worthy opponent simply by randomly choosing one of the free squares. You could continually pick squares at random until you find a free one or have a list of available squares (which may scale better) and just pick one.
If I remember correctly tic tac toe is one of those games where if you're clever enough then you can never lose at it, only draw or win. As a result a computer could easily be made to never lose which would (for this game atleast) be utterly unfun.
To be honest I think that you could achieve the illusion of a worthy opponent simply by randomly choosing one of the free squares. You could continually pick squares at random until you find a free one or have a list of available squares (which may scale better) and just pick one.
Choosing a random square is simpler for sure, but it's not artificial intelligence. There's actually a simple algorithm that is used for the AI in many games, from tic-tac-toe to chess and beyond. It's called minimax. Wikipedia has a good description of the algorithm, along with some pseudocode:
http://en.wikipedia.org/wiki/Minimax
Then, when you get that working you could try using the alpha-beta pruning algorithm, which will make your minimax code more efficient.
[Edited by - pkfx on September 27, 2007 12:45:58 AM]
http://en.wikipedia.org/wiki/Minimax
Then, when you get that working you could try using the alpha-beta pruning algorithm, which will make your minimax code more efficient.
[Edited by - pkfx on September 27, 2007 12:45:58 AM]
The first and most important thing - the thing the player notices the most if you don't get it right - is that if the AI can make a winning move, it probably should. So that's the first thing the AI can do, is look for winning moves it could make, and if it finds one, make it.
The second thing, if there are no moves that would cause an immediate win, is to look for moves the other player could make that would be a win. If one is found, make it yourself to block their win. (If there are multiple, then pick any; the AI's lost anyway at that point).
Once those are out of the way, it's a bit less clear what kind of move should be made. The center square can be used in 4 winning lines, the diagonals each in 3, and the laterals each in 2, so you should probably prioritize the squares accordingly.
The second thing, if there are no moves that would cause an immediate win, is to look for moves the other player could make that would be a win. If one is found, make it yourself to block their win. (If there are multiple, then pick any; the AI's lost anyway at that point).
Once those are out of the way, it's a bit less clear what kind of move should be made. The center square can be used in 4 winning lines, the diagonals each in 3, and the laterals each in 2, so you should probably prioritize the squares accordingly.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
