tic-tac toe
May 17, 2005 09:13 PM
How should the AI work in tic-tac-toe? I've tried to think about it, but I suck at the game, so I don't know.
I hate signatures.
1,788
May 17, 2005 09:27 PM
Usually one uses a "minimax" search, possibly with "alpha-beta pruning" (though tic-tac-toe doesn't really need pruning). Google for those two terms and you will find a wealth of information.
205
May 18, 2005 12:04 AM
The funiest AI for tic-tac-toe I've seen was a defensive AI. There are specific heuristics that are triggered, like which moves would guarantee a loss, and when you have to block a player from winning. Apart from that, it just moved randomly.
Tic-tac-toe is actually a small enough problem in modern computing sense to be solved with just pure brute force.
Tic-tac-toe is actually a small enough problem in modern computing sense to be solved with just pure brute force.
May 20, 2005 03:06 PM
The problem is making it so the AI doesn't win every time.
I hate signatures.
142
May 20, 2005 06:41 PM
Quote: Original post by WeirdoFu
The funiest AI for tic-tac-toe I've seen was a defensive AI. There are specific heuristics that are triggered, like which moves would guarantee a loss, and when you have to block a player from winning. Apart from that, it just moved randomly.
Tic-tac-toe is actually a small enough problem in modern computing sense to be solved with just pure brute force.
That's how I did it the first time I made a tic-tac-toe game too! Well, plus obvious offense. It was something like:
If a move that will make me win this turn exists Make that move.Else if there is a move that the player can make next turn to win Block that move.Else Move randomly.I never got around to writing a game tree search. I probably should...
1,382
June 06, 2005 02:25 PM
Quote: Original post by TerranFuryQuote: Original post by WeirdoFu
The funiest AI for tic-tac-toe I've seen was a defensive AI. There are specific heuristics that are triggered, like which moves would guarantee a loss, and when you have to block a player from winning. Apart from that, it just moved randomly.
Tic-tac-toe is actually a small enough problem in modern computing sense to be solved with just pure brute force.
That's how I did it the first time I made a tic-tac-toe game too! Well, plus obvious offense. It was something like:If a move that will make me win this turn exists Make that move.Else if there is a move that the player can make next turn to win Block that move.Else Move randomly.
I never got around to writing a game tree search. I probably should...
I'd replace the "move randomly" thingy with a more advanced "if I ind a move which is obviously better than any other move, do it". For example, beeing the first who spots the central point of the board will guaranty you that your opponent will be left with only 4 remaining path to victory (you block 4 path with one move).
TTT do not require an AI, but a good strategy might help. Anyway, you'll face a situation where nothing but a random move is possible. Such random move might lead you to the defeat, or might block your opponent - this is based upon the previous moves he did.
(shameless plug) the TTT I put in the GDS uses brute force to defend itself. It is not very hard to win agains the computer - but it is still hard to win enough time to earn more than 2000 points. The source code of the game is on my driver, thus I can send it to anyone wants it.
Regards,
-- Emmanuel D. [blog, in French] [blog, very bad googlized translation]
21,607
June 06, 2005 02:41 PM
Another approach is solving the game completely. Consider a directed graph where each node represents a tic-tac-toe position and arrows represent legal moves. We can assign values to all the nodes by the following rules:
- If player 1 has three in a line, the value is +1.
- If player 2 has three in a line, the value is -1.
- If the board is full and neither player has three in a line, the value is 0.
- If it is player 1's turn, the value is the maximum of the values of the children of this node.
- If it is player 2's turn, the value is the minimum of the values of the children of this node.
There aren't that many nodes (in a rough representation you'll have 3^9 nodes, and 3^9=19683), so you can compute all the values in advance. A decent algorithm should take less than a second in a modern computer. Then your program should just pick a move at random among the moves that lead to positions with optimal score (highest if you are 1, lowest if you are 2).
- If player 1 has three in a line, the value is +1.
- If player 2 has three in a line, the value is -1.
- If the board is full and neither player has three in a line, the value is 0.
- If it is player 1's turn, the value is the maximum of the values of the children of this node.
- If it is player 2's turn, the value is the minimum of the values of the children of this node.
There aren't that many nodes (in a rough representation you'll have 3^9 nodes, and 3^9=19683), so you can compute all the values in advance. A decent algorithm should take less than a second in a modern computer. Then your program should just pick a move at random among the moves that lead to positions with optimal score (highest if you are 1, lowest if you are 2).
21,607
June 06, 2005 03:15 PM
Here's some code for a hybrid approach (recursion with memory). I use +1 to indicate that the player to move wins and -1 to indicate that the player to move loses. This trick simplifies the code a lot.
#include <cstring>struct Position{ int s[9]; bool is_won(int c) const{ if(s[0]==c){ if(s[1]==c && s[2]==c) return true; if(s[3]==c && s[6]==c) return true; } if(s[8]==c){ if(s[7]==c && s[6]==c) return true; if(s[5]==c && s[2]==c) return true; } if(s[4]==c){ if(s[0]==c && s[8]==c) return true; if(s[1]==c && s[7]==c) return true; if(s[2]==c && s[6]==c) return true; if(s[3]==c && s[5]==c) return true; } return false; }};signed char search(Position &p, int c){ // we'll keep memory of the values of all positions already analized static signed char memory[3][3][3][3][3][3][3][3][3]; static bool initialized=false; if(!initialized){ std::memset((char *)memory,-2,3*3*3*3*3*3*3*3*3); // -2 means "unknown" initialized=true; } // find the location of the current position in the memory signed char &value = memory[p.s[0]][p.s[1]][p.s[2]][p.s[3]][p.s[4]][p.s[5]][p.s[6]][p.s[7]][p.s[8]]; // if we remember this position, nothing to do if(value!=-2) return value; // if it's won for either side, we know the value if(p.is_won(c)) return value=+1; if(p.is_won(3-c)) return value=-1; // now take the maximum value of all the legal moves for(int i=0;i<9;++i){ if(p.s==0){ p.s = c; // do move signed char temp = -search(p, 3-c); // notice the sign change here! p.s = 0; // undo move // keep a running maximum; if(value<temp) value=temp; } } // if value is still -2, there were no legal moves (full board), so it's a draw if(value==-2) return value=0; return value;}This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
