AI tic-tac- toe

I''ve done this in the past, although I don''t have my code with me. My approach was:

- If the AI can win in one move, make that move.
- If the player could win on the next move, block it.
- Otherwise, find the board position, or a rotation/reflection of it, in a predefined list.

Making the list takes a little while, but there weren''t many positions on it.

I made a TicTacToe once too.

- If the AI can win in one move, make that move.
- If the player could win on the next move, block it.
- Otherwise, use a random place on the board that is free

The Sorcerer

Try here and here.

Miles

1. Make a winning move.
2. Block the player's winning move.
3. Get the first available corner.
4. Get the first available non corner.
5. Get the center.

If the computer gets the first move the best the player can do is draw.

I used a nine element array and lots of if statements.

When I did this in VB I used an array of label objects.

[edited by - murph on December 4, 2002 9:39:43 AM]

i want to ask how to write the block.

Use MinMax with AlphaBeta pruning to build a tree of the entire game and choose the best good move available. Plays perfectly. Can easily be extended to Four-In-A-Row.

Will

Yeah, but who wants to play against an AI that will automatically win if you make one mistake? Instead, do things like search depth proportional to difficulty, or let it learn which moves are bad or good by a training process. This method is obviously far more difficult to implement, but I think it will make for a far more enjoyable game.
Brendan

An ANN (artificial neural network) sounds like a good solution. You could also use a genitic algorithm to make it learn the more you play (www.ai-junkie.com should help).

One more thing; if you want to check for a win dont check each possibility -> in my gr 10 programming class we had to make a two player tic tac toe game and all you saw were students, except me typing like mad for half an hour trying to solve for a win. All you have to do is extend the tic tac toe grid, assign a value to x,o, and blank. Then add accross each grid and you can tell if there is a win if the ends of the grid add up to a certain value.




and as you can see the 3 represents a x win and if we had a -3 it would be a o win. Easy stuff

"Free advice is seldom cheap."
-- Rule of Acquisition #59

Well, it really depends on how complex you want it to be and whether you want it to be perfect or not. When I once did this, I was just assigning all free fields different weights, so I'd just go through each field and look if it was needed for blocking the player or for winning itself. If so, it got a high weight, if not, it was lower depending on the position and so on.
The actual move was chosen randomly based on the weights, which made the "better" moves far more likely than the bad ones but the AI could still make errors.
Worked fine.. Although you still have a lot of checks (probably even more than with the perfect ones), but it makes the play somewhat random.

[edited by - Wuntvor on December 5, 2002 8:04:21 AM]

quote:

---

Original post by Punty50
Yeah, but who wants to play against an AI that will automatically win if you make one mistake? Instead, do things like search depth proportional to difficulty, or let it learn which moves are bad or good by a training process. This method is obviously far more difficult to implement, but I think it will make for a far more enjoyable game.
Brendan

---

Did I miss something?? It''s Tic-Tac-Toe?!!! If you miss something, uhm, shouldn''t you loose? And, how do you miss something?

Will

I once wrote a tic-tac-toe program that computes the whole game graph and assigns the theoretical value for each position (like in chess endgames). I did it with a table with 2 * 3^9 positions. Actually, It can be done with less than that, but on modern computers it doesn''t matter. The generation takes about one second, and then playing perfectly is just a 1-ply search.

I do weird things when I''m bored...

Will,
I understand what you are saying in Tic-tac-toe, because it is such a small game space, but for a game like connect four, I think that the computer having full knowledge of the game tree would not make for the greatest play in the world. Adaptive NN''s are good ways of letting a program learn, so that at some point it probably will have all the information required to play a perfect game, but it gradually gets to that point.
Brendan

RPGeezus''s suggestion is the most sensible.

If you want to see a tic-tac-toe agent learning by its mistakes then have a go at using temporal difference (TD) learning. It''s a type of reinforcement learning. Here''s a link to an online book:

http://www-anw.cs.umass.edu/~rich/book/the-book.html

Just thought I''d throw another technique into the fray

---

ai-junkie.com

fup:
Thanks for the link. The short-commings of minmax are made apparent in his tic-tac-toe example.

Punty50:
Connect-4 is way to big for a game tree to solve. My younger sister (who is a Connect 4 fiend) can easily beat the game I wrote for her. Even if the program is looking ahead 20 moves, she can usually beat it.

Will

quote:

---

Original post by RPGeezus
Use MinMax with AlphaBeta pruning to build a tree of the entire game and choose the best good move available. Plays perfectly. Can easily be extended to Four-In-A-Row.

Will

---

hi how do i apply to the alpha and beta.how to write it with this.

It''s really hard to explain, especially in a forum. There are some excellent online examples of MinMax and AlphaBeta though, many with source examples. Do a search on Goggle for "MinMax AlphaBeta Java".

Cheers,
Will

quote:

---

Original post by RPGeezus
It''s really hard to explain, especially in a forum. There are some excellent online examples of MinMax and AlphaBeta though, many with source examples. Do a search on Goggle for "MinMax AlphaBeta Java".

Cheers,
Will

---

thx
do u have icq,so that we can exchange idea.there is no result about "MinMax AlphaBeta Java"

Just sticking my thoughts in to this discussion... I think that the first move is the most critical in the game of tic-tac-toe. If the AI has first move, I coded the AI to take the center grid... if the player had the first move and didn''t select the center grid, the AI did...

I''ll admit that I like the ideal of creating an AI for TTT that uses NN and learns from playing... of course, after a few sessions, the AI would absolutely crush the player – unless you coded the AI to have emotions. After stomping the poor human opponent a few times in a row it could “feel bad” and let loose on purpose *grin*


Dave "Dak Lozar" Loeser

Never mind having the computer solve TTT, I solved it myself by the time I''d finished Secondary School - It''s possible for the second player to force a draw having played in an edge square on his first move... (of course, it does rely on the first player having made a particular first move)

quote:

---

1. Make a winning move.
2. Block the player''s winning move.
3. Get the first available corner.
4. Get the first available non corner.
5. Get the center.

---

Not the perfect algorithm - if I play first against it, I can win easily - depending on how corners are ranked, I might even be able to beat it playing an edge move first...

If you put center move to 3 and move the others down in priority, it might work perfectly... I''d have to think a bit to see if I could fool it...

OK, can fool it if it orders the corners badly... As first player, it''d be unbeatable, but second player it would lose if it had a fixed ordering on the corners...