Archived

This topic is now archived and is closed to further replies.

Prozak

TIC TAC TOE A.I.

Recommended Posts

fakemind    122
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

Share this post


Link to post
Share on other sites
a person    118
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

Share this post


Link to post
Share on other sites
Goblin    122
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!"

Share this post


Link to post
Share on other sites
AEBergen1980    122
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[i])
{
OBoard[i]=true;
MoveCount++;
return;
}

//If there is a move which will win the game, make it.
for(i=1; i<9; i++)
{
if(!(XBoard[i]||OBoard[i]))
{
OBoard[i]=true;
TestVictory();
if(OWins)
{
MoveCount++;
GameState=OVER;
return;
}
OBoard[i]=false;
}
}

//If there is a move which will lose the game, block it.
for(i=1; i<9; i++)
{
if(!(XBoard[i]||OBoard[i]))
{
XBoard[i]=true;
TestVictory();
if(XWins)
{
XWins=false;
XBoard[i]=false;
OBoard[i]=true;
MoveCount++;
return;
}
XBoard[i]=false;

}
}

//Make a random move.
while(XBoard[i]||OBoard[i])
{
i=rand()%9+1;

}
OBoard[i]=true;
MoveCount++;
return;

}

Share this post


Link to post
Share on other sites
polly    532
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

Share this post


Link to post
Share on other sites
Ziphnor    122
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

Share this post


Link to post
Share on other sites
Beer Hunter    712
To everyone who thinks their AI is unbeatable - try this.

As the player, take the top-left corner on the first turn.
The AI must take the center, or it will lose.
As the player, take the bottom-right corner.

Does your AI commit suicide?

The correct way to handle that situation is to take one of the edges. Most human players, seeing that situation for the first time, will take a corner. I never understood why.

Less importantly, if your AI goes first, does it take the center or a corner? A corner is generally more effective, although maybe you could make it random.

Share this post


Link to post
Share on other sites
Shannon Barber    1681
Um... Tic-Tac-Toe is unwinnable when played by two competent players; as such, it's sometimes not even considered a game.

The AI can be made so that it never loses by using a recursive algorithm - the depth is limited to a maximum of 9, which means there's a maximum of 362880 cases (without eliminating reflections and rotations) on the first move. You can make it pick a random first move (since it doesn't matter) and there's only 7! boards it has to consider, which is a mere 5040; if the CPU goes second then you only have to calculate a maximum 40320 boards.
And you can stop once all sub-boards of a move result in a cats (draw) or win, and move on to the next sub-board of the parent once you find a lose case. Optionally, you can add-up the number of win boards and pick the route one with highest number.
This can work becuase TTT has a fixed number of steps.

Fast it isn't - perfect it is.

Magmai Kai Holmlor

"WOULD YOU... LIKE... TO... PLAY... A GAME?" - WarGames

Edited by - Magmai Kai Holmlor on December 12, 2001 8:14:21 PM

Share this post


Link to post
Share on other sites
Plasmadog    205
I once saw an article about a Tic Tac Toe AI that was based on the fact that the board can be represented as a magic square where each line totals 15 (i.e. the first row is 4,3,8, second row 9,5,1, third row 2,7,6). If you think about it this way, you can do away with the board altogether, as each player essentially picks any number between 1 and 9 that has not already been picked. The first player who can add any three of his chosen numbers to total 15 wins the game.
I don''t recall exactly how this concept was used in an AI, but it''s an interesting approach. The downside is that it can''t really be applied to any other game.

Share this post


Link to post
Share on other sites
polly    532
It is called Noughts and Crosses. Yanks get confused easily though, so you have to explain everything REALLY...SLOWLY.. and refer to things by names they''re familiar with.
And, yes, they do drive on the wrong side of the road..
Back to ''tic tac toe'', once youve done it, try writing a little Connect4 game as an expansion.. if you have to rewrite the whole thing, then you wrote tic tac toe wrong..
JOn

Share this post


Link to post
Share on other sites
Beer Hunter    712
Plasmadog - That sounds like it could be a good approach. I can''t see quite how it would be done, but I''ll look into that.

jonpolly99 - Yes, it is called "Noughts and Crosses". But it is also called "tic tac toe". Get over it, fool.

black_mage_s - You''re joking, right?

Share this post


Link to post
Share on other sites
Plasmadog    205
I agree with jonpolly99 about the connect4 type game. Any approach you take should be reasonably generic and/or scalable, otherwise you won''t learn anything useful from it. For example, the suggestions about corner squares first, etc. would work, but would not scale well to a 4x4 board, whereas the magic square approach could. And there are probably even better approaches that could be migrated to an arbitrarily sized/shaped board (I have this idea in the back of my mind about some sort of celular automaton that might be able to to this).
I guess it ultimatly comes down to why you want a Tic Tac Toe AI. Is it just because you want to play Tic Tac Toe, or do you really want a challenge that will teach you something about how to write an AI?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Beer Hunter- go away and grow a sense of humour..
The problem with making the game just make random moves is that its dull, you''ll almost always win. If you hardwire in a set of rules that makes it play well, then it''ll always be a draw/loss for you. If you code it so it learns the more games it plays, I think it would be a little more fun and rewarding..
Jon

Share this post


Link to post
Share on other sites
Stoffel    250
quote:
Original post by Plasmadog
I agree with jonpolly99 about the connect4 type game. Any approach you take should be reasonably generic and/or scalable, otherwise you won''t learn anything useful from it. For example, the suggestions about corner squares first, etc. would work, but would not scale well to a 4x4 board, whereas the magic square approach could. And there are probably even better approaches that could be migrated to an arbitrarily sized/shaped board (I have this idea in the back of my mind about some sort of celular automaton that might be able to to this).


This discussion just shot past my depth. How are they the same game? And what''s the "magic square" approach. I have 0 AI background.

PS: I think this is a great idea for a beginner program, so let''s try to encourage pentium3id, ''k all?

Share this post


Link to post
Share on other sites
Beer Hunter    712
quote:
Original post by Anonymous Poster
Beer Hunter- go away and grow a sense of humour..



The "Yanks get confused easily though, so..." part was clearly a joke, but "It is called Noughts and Crosses..." was not necessarily part of that joke. And if I don''t have a sense of humour, can you explain my answer to black_mage_s?

Share this post


Link to post
Share on other sites