TIC TAC TOE A.I.
Author
This might sound somewhat basic,
but where can I find the theory or description
for a TTT AI, or gameplan?
if you go about thinking of tic tac toe AI as there are tons and tons of possibiltities for each user to make (9 squares to pick from each turn) then it gets to be quite a large problem! over 6000 possibilities for the first 4 moves.
however, it doesnt have to be this complicated at all. in fact, you just need to look at like this. instead of 9 squares to pick from the first move, there are only 3 (a corner, a wall, and the center). if you work it like this, and just hard-wire the first two moves of the computer based on what its opponent moved, it should be quite simple. in fact, if you do it correctly, and it shouldnt be too hard at all, you can have your computer tic tac toe AI unbeatable. it will either win or there will be a tie.
hope this helps some... .
- jeremiah
http://fakemind.com
however, it doesnt have to be this complicated at all. in fact, you just need to look at like this. instead of 9 squares to pick from the first move, there are only 3 (a corner, a wall, and the center). if you work it like this, and just hard-wire the first two moves of the computer based on what its opponent moved, it should be quite simple. in fact, if you do it correctly, and it shouldnt be too hard at all, you can have your computer tic tac toe AI unbeatable. it will either win or there will be a tie.
hope this helps some... .
- jeremiah
http://fakemind.com
basically look at all the possible locations giving priority:
1. go for win
2. block a win
1. center square
3. corner
4. center
Edited by - a person on December 11, 2001 10:37:08 PM
1. go for win
2. block a win
1. center square
3. corner
4. center
Edited by - a person on December 11, 2001 10:37:08 PM
Well, the possible combinations for first moves are not nearly that many, because many will be exactly symetrical to other combinations. And many moves will lose you the game, so when it comes down to it from any given situation there''s only 2-3 viable moves.
In fact, me and a friend of mine got very competetive about tic tac toe once, and we both figured out how to not lose. Ever. It is very possible to either always win or always not lose. However, programming the computer AI to never lose would just be evil.
-----------------
The Goblin (madgob@aol.com)
-----------------
"Before critisizing somebody, walk a mile in their shoes. That way, when you do critisize them, not only will you be a mile away, but you''ll also have their shoes!"
In fact, me and a friend of mine got very competetive about tic tac toe once, and we both figured out how to not lose. Ever. It is very possible to either always win or always not lose. However, programming the computer AI to never lose would just be evil.
-----------------
The Goblin (madgob@aol.com)
-----------------
"Before critisizing somebody, walk a mile in their shoes. That way, when you do critisize them, not only will you be a mile away, but you''ll also have their shoes!"
yup, the symetry (sp?) will definately cut down the number of possibilities a whole heck of a lot.
i actually played a tic tac toe computer game that never lost. needless to say it wasnt fun.
- jeremiah
http://fakemind.com
i actually played a tic tac toe computer game that never lost. needless to say it wasnt fun.
- jeremiah
http://fakemind.com
I wrote a little tic-tac-to demo about a year ago. It had one of those evil A.I.s that refused to be beaten. You can download it at http://www.gamedev.net/community/gds/projects/default.asp?projectID=205 but I don''t think I included all of the files needed to build it. The AI portion is pretty simple:
void ComputerMoves(){ int i=5; //The game can''t take any longer if(MoveCount>8) return; //Go for the center, if available if(!XBoard&&!OBoard)<br> {<br> OBoard=true;<br> MoveCount++;<br> return;<br> }<br><br> //If there is a move which will win the game, make it.<br> for(i=1; i<9; i++)<br> {<br> if(!(XBoard||OBoard))<br> {<br> OBoard=true;<br> TestVictory();<br> if(OWins)<br> {<br> MoveCount++;<br> GameState=OVER;<br> return;<br> }<br> OBoard=false;<br> }<br> }<br><br> //If there is a move which will lose the game, block it.<br> for(i=1; i<9; i++)<br> {<br> if(!(XBoard||OBoard))<br> {<br> XBoard=true;<br> TestVictory();<br> if(XWins)<br> {<br> XWins=false;<br> XBoard=false;<br> OBoard=true;<br> MoveCount++;<br> return;<br> }<br> XBoard=false;<br> <br> }<br> }<br><br> //Make a random move.<br> while(XBoard||OBoard)<br> {<br> i=rand()%9+1;<br><br> }<br> OBoard=true;<br> MoveCount++;<br> return;<br><br>}</pre> </i>
Tic Tac Toe was the 1st program I wrote that was more than 100 lines long. You can make it as easy or as hard as you want by giving the program whatever degree of intelligence you feel is appropriate. I ended up writing about 40 if statements (which is the wrong way to do it..). I figure that there are basically 3 options-
1. Just make the computer make a random move each time. Add a little strategy so it will block 2-in-a-row, or win if it has 2-in-a-row.
2. Make sure the program knows to take the centre 1st, corners 2nd etc., add all the features above.. this is what I did, although it was a little rough, it worked really well.
3. I think this is the best soln. Give your game a little real AI. You will need to use classes for this- For each combination of moves that causes the computer to lose-make sure that it ''remembers'' for the next game and doesnt make the same sequence of moves again. Id love to try this to see if it works, but dont have time at the moment, have fun..
Jon
1. Just make the computer make a random move each time. Add a little strategy so it will block 2-in-a-row, or win if it has 2-in-a-row.
2. Make sure the program knows to take the centre 1st, corners 2nd etc., add all the features above.. this is what I did, although it was a little rough, it worked really well.
3. I think this is the best soln. Give your game a little real AI. You will need to use classes for this- For each combination of moves that causes the computer to lose-make sure that it ''remembers'' for the next game and doesnt make the same sequence of moves again. Id love to try this to see if it works, but dont have time at the moment, have fun..
Jon
If you want to learn some "real" AI algorithms, use MiniMax or AlphaBeta search, that also gives you the option of later on expanding the board from 3x3 to anything you want(bigger boards will of course slow the search down ALOT!).
Last year i made a Java Checkers game, it was pretty cool, because you could alter the board dimensions and it would still kick my arse
So unless you are ONLY interested in 3x3 TTT and nothing else, dont hardcode any strategy into the computers AI. Not much Artifical intelligence in hardcoded strategies if you ask me
Edited by - ziphnor on December 12, 2001 2:47:14 PM
Last year i made a Java Checkers game, it was pretty cool, because you could alter the board dimensions and it would still kick my arse
So unless you are ONLY interested in 3x3 TTT and nothing else, dont hardcode any strategy into the computers AI. Not much Artifical intelligence in hardcoded strategies if you ask me
Edited by - ziphnor on December 12, 2001 2:47:14 PM
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
