Sign in to follow this  
Lemon Boy

AI in a tic-tac-toe type game

Recommended Posts

Hello people, i need your help! i've just finished a tic-tac-toe type game but the AI sucks, and i need to know what is the best way to approch this problem I wanted to make an impossible to beat computer (i.e. Impossible difficulty setting) plus easier modes, but the only way i thought to do that is through seting all possible combinations and since im using a 4*4*4 (64) grid thats 64! (factorial) which is a big ass number. so any suggestions in how to do this would be great and ill ive you credit in the game when its done, and no im not asking you to do it for me just point me in the right direction. Thanks!

Share this post


Link to post
Share on other sites
The first game I made was tic-tac-toa after a couple weeks learning VB. I just used a normal grid of 4 x 4 and I just used a whole shit load of if statements for the AI :P, but an perfect setting it was almost impossible to beat. Every once and a while there was a combo that would be at so I just added some more if statements. The only thing I could suggest is making some kind of loops that loops through all the tiles and does actions when they are full. That way you could mimize some of the work.

Jake

Share this post


Link to post
Share on other sites
Check out minimax (and, once you get that working, check out alpha-beta pruning). It's pretty much the standard for games like that.

To make the game harder or easier, you can change the search depth of the tree minimax creates. Deeper searches will result in a better player, but can take a LOT of time to run. A search with a depth of 4-5 will probably be a pretty decent opponent.

Share this post


Link to post
Share on other sites
You want a minimax algorith:
http://en.wikipedia.org/wiki/Minimax_algorithm
I suggest you implement it using Alpha-Beta pruning to reduce the number of nodes:
http://en.wikipedia.org/wiki/Alpha-beta_pruning

You probably can find all the info you need by googling for a time, maybe even a full tic-tac-toe implementation, good luck!

Share this post


Link to post
Share on other sites
I've written a ttt app that used a hand-made ann to work out the solutions. (of cource, it took forever to get the net to work properly).

I've also written another tt app which looks for patterns, then uses weighted squares.

What i would sugest (for a noobie such as yourself), if the weighted squares approach, with patterns once your used to it. (to patch up any faulty decision making).

You can adapt this for anything, from ttt to checkers. Some other games (like connect 4, virus, ect.), but most definatly not chess.

You can also use this in your evaluation function for ab. (well, use the weightings to determine points of interest, for eg. major attacks on squares vs. attacking a well protected square).

Heres a simple version.

Start off with a blank board.

Each square has a weighting.
These should go like this

1|0|1
0|1|0
1|0|1

Just to make it try and move in the corners or the center.

Now, the opponant makes a move.

So, O (your opponant) goes in the top square.

THe board is


O| |
| |
| |


now, you increment the weighting of the squares in the same row and coloumn by one

So, its now

2|1|2
1|2|0
1|0|1

For your move, you pick the square, that does not have a piece on it, and has the highest number. (if many do, then pick one at random)

So, say you pick the center.

The board is now

O| |
|X|
| |

And so on.
You an see that it made a mistake. (player goes in the lower right hand corner, bot goes in top right, player goes in lower left, then the player has 2 possible wins).

How do you correct this?

You use patterns.

So, for eg. one pattern would be
O| |
| |
| |

So, because that was what the board was like, we look at the accompnying table

which is

0|1|0
0|0|0
0|0|0

Which we then add to our normal grid.

This then gets it to favour the move, in the top center.
Which then leads it to a draw.

Overall, its a fast and simple approach.
And if you really want to do mm + ab, you can use this to decide in which order to make the moves. (which makes the search awhole lot faster, since it will usually lead the serch to find the best moves first.).

Also, once you get past 3x3, a full mm search is inpractical, but the weighted squares apprach would still work on 2000x2000.
From,
Nice coder

Share this post


Link to post
Share on other sites
Like people before me have stated, min-max is a good way to go. The reason for this is because in a game of perfect information like tic-tac-toe (everything is known to every player) it is hypothetically possible to achive "perfect" play. Tic tac toe is so simple and has so little board possibilities that it is actually trivial to use a complete min-max search, one that encapsulates all possible game states ever. Chess, which has many many more complexities, can still do so but only to a certain move depth ... top quality chess AI's can hit 6, 7, even 8 moves in advance. But a chess game is a bit more than 8 moves long, so you aren't necessarily playing perfectly, you are only maximizing a few moves into the future.

Share this post


Link to post
Share on other sites
Quote:
Original post by The Reindeer Effect
Like people before me have stated, min-max is a good way to go. The reason for this is because in a game of perfect information like tic-tac-toe (everything is known to every player) it is hypothetically possible to achive "perfect" play. Tic tac toe is so simple and has so little board possibilities that it is actually trivial to use a complete min-max search, one that encapsulates all possible game states ever. Chess, which has many many more complexities, can still do so but only to a certain move depth ... top quality chess AI's can hit 6, 7, even 8 moves in advance. But a chess game is a bit more than 8 moves long, so you aren't necessarily playing perfectly, you are only maximizing a few moves into the future.


Unfortunaly 4x4 ttt is too big to minimax to work effectively.

16! possible moves = 2.09227899 × 10^13 = 20,922,789,900,000 possible moves.

3*3 ttt, = 362,880 moves.

Now, since you might be able to do 3*3 ttt in about a second.

It would take you, maybe 240.083262 Years to do 4x4 ttt.

And quite a bit longer for 5x5 and 6x6 ttt.
For eg. 5*5 ttt = 1.35447672 × 10^13 years
6*6 ttt = 3.24833652 × 10^29 years

Weighted squares would work out a winning approach in < 1 second.

It is the best alternitive for games like this. Easy to code, easy to get working.

Applying minimax with alpha-beta to this problem is like trying to kill an ant with a nuclear missle, it works, its just overkill!.

From,
Nice coder

Share this post


Link to post
Share on other sites
well thanks for the detailed tips nice coder!
the thing is that the game has a 4*4*4 grid (i.e. 3 dimentions)
so i think ill try the weighted apporach to get the AI to place pieces in the corners and middle.

I havnt checked the MM approach yet, but ill do that now.
Thanks again for the help and keep the idea coming!

Share this post


Link to post
Share on other sites
Each square can be X, O or empty. There are 64 squares. Thus, there are at most 3^64 possible combinations -- still big, but smaller than 64 factorial!

In the opening, you probably want to use an "opening book" of known good ways to play and ways to counter them -- don't start searching until you're about three moves into the game, else the search space is too much and not very useful.

Share this post


Link to post
Share on other sites
yeah i know there are 64 spaces but there are 64 factorial different possible moves if you module a whole game will ALL possibilities
i read the minimax disscription but it just confused me so im gonna do more reasearch on it.
And i already thought that its best to use it a few moves into the game, but thanks for mentioning it!

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
You don't have to do a full search with minimax (you can stop at a certain depth and use an evaluation function). Plain minimax (without alpha beta) is pretty easy to code, and I bet it would be very hard ot beat with a reasonable depth.

Share this post


Link to post
Share on other sites
Quote:
Original post by Nice Coder
It would take you, maybe 240.083262 Years to do 4x4 ttt.



Well, thats assuming you dont take advantage of symmetry or anything like that. I believe you could optimize one to be pretty quick.

Quote:


Weighted squares would work out a winning approach in < 1 second.

It is the best alternitive for games like this. Easy to code, easy to get working.

Applying minimax with alpha-beta to this problem is like trying to kill an ant with a nuclear missle, it works, its just overkill!.

From,
Nice coder


This much I cant really disagree with ;)

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
You don't have to do a full search with minimax (you can stop at a certain depth and use an evaluation function). Plain minimax (without alpha beta) is pretty easy to code, and I bet it would be very hard ot beat with a reasonable depth.


I also bet it would be at the very least a hundred thousand times slower then an optimised compiled pattern matching. (Which lets you implement weighted squares, really easy).

:-)

How to do compiled pattern matching:

For eg. For the pattern

O| |
| |
| |

Replace O with 10
Spaces with 00
And x with 01

Then convert to bianry

So, its 100000000000000000Binary

For a 4*4*4 = 64 board, that means that you need 128 bits to do it.

This is probably the fastest way you'd ever have to make it work.

For eg. checkiong to see if the above pattern matches the board

O|X|
| |
|X|O

First, convert to binary

100100000000000110
100000000000000000
-------------------- Binary and
100000000000000000

Therefore the patterns match. (and you add the corresponding weightings to your squares).


This works wonders with things like connect 4 (you can make an almost unbeatable opponant.), esp because you only have a few squares as well as only a few possible moves.

Remember: You don't need to do one addition per square. You can squeeze them all into an int64. (you can squeze 8 into an int64, so you need only 8 additions in order to update all the squares).

Also,
For difficulty levels, make your if statement something like

if (wei[x] > best) || (((wei[x] == best) && (random() < 0.5)) || ((wei[x] < best) && random() < factor)) {

Factor would be around 0 (for best play) to 1 (for really badish play), so you can just drag a scrolbar across from best to worst.

And remember, you can make an intellegent bot.
So, when it looses, it looks at the moves its opponant makes, and adds them. (or, if it already knows it, it increases the strength of moving in the same spot the human went).

I made a bot that did that once,
Worked really good. (tho after awhile it learned how to force a tie, so you needed to reset it).

From,
Nice code


Share this post


Link to post
Share on other sites
Quote:
Original post by Nice Coder
Applying minimax with alpha-beta to this problem is like trying to kill an ant with a nuclear missle, it works, its just overkill!.

From,
Nice coder


actually u r quite wrong
a/b prunin wiht minimax is the best thing to handle tic tac toe coz it stores all possible solutions and minimax is implemented by most board games (such as checkers) i made an implementation in minimax + a/b pruning for checkers and tic tac toe and they both run smoothly
a tic tac toe with depth = 9 still runs and finds solutions in les than a second as a/b will just cut off the search tree and u wont do the extra checks.
and checkers is 8x8 + some extrac moves as player can have special moves when he reaches the end and still it runs smoothly till bout a dpeth of 5 then it will take round 2-10 secs to find the best solution :)
a gd advanced game would implement minimax + a/b + some fuziness in deciding the depth thus will be more human and interactive then u can change the degree functions of fuzzy logic to make it harder and harder :)

Share this post


Link to post
Share on other sites
Ok people i have done my research and what not and im going to post me findings and decisions of which you may correct me if im wrong but anyway here goes:

Fristly i need to correct an error on my part, the game i produced is more like connect four and tic-tac-toe, in that it is a 4*4*4 grid (64 spaces) but the spaces in the top can only be filled if the spaces bellow it are filled (ala connect 4), thus in any given turn there is a max of 16 possible moves.

now i read and read about minimax and i noticed that it reiles on a tree of all possible moves (which is somthing i wanted to aviod) and the alpha-beta pruning works on the basis of cutting out the brances of the tree that yeld scores less than your best score, thus stopped the scanning on the whole tree on every AI call.

am i right so far? no anyway....

as for the weighted sqaures routine, that is similar but cuts out the tree of the entire game and focuses on game states where the computer may loose, but i have the impresstion at this approach is more defensive rather than trying to win the game. but as i am new to this AI stuff i understand the weighted squares stuff better than the minimax, not to mention the fact i avoid a tree of an entire game.
so i will use the weighted sqaures and post a link to a game on this forum when i have decent enough AI, i doubt ill use the patterns of the bat but i intend to use them if i can figure out the best way to implement them with rotational-sysmetry! anyone know of a way to that that?


anyway i've typed loads now so if i've miss understood anything please let me know, plus tips rotational-sysmetry will help!

Thanks!!

Share this post


Link to post
Share on other sites
Quote:
Original post by ZeRaW
Quote:
Original post by Nice Coder
Applying minimax with alpha-beta to this problem is like trying to kill an ant with a nuclear missle, it works, its just overkill!.

From,
Nice coder


actually u r quite wrong
a/b prunin wiht minimax is the best thing to handle tic tac toe coz it stores all possible solutions and minimax is implemented by most board games (such as checkers) i made an implementation in minimax + a/b pruning for checkers and tic tac toe and they both run smoothly
a tic tac toe with depth = 9 still runs and finds solutions in les than a second as a/b will just cut off the search tree and u wont do the extra checks.
and checkers is 8x8 + some extrac moves as player can have special moves when he reaches the end and still it runs smoothly till bout a dpeth of 5 then it will take round 2-10 secs to find the best solution :)
a gd advanced game would implement minimax + a/b + some fuziness in deciding the depth thus will be more human and interactive then u can change the degree functions of fuzzy logic to make it harder and harder :)


1. You no speeky teh engrish! (or else, noone will ever, ever, ever, take you seriously. Ever go to a job interview and say 'I am teh 1337 h4x0r h1r3 m3!!! ?)


2. Minimax aint the best thing for some games.

3. Fuzzyness in the depth? i want what your smoking!

4. Degree functions of fuzzy logic? I really want what your smoking!

Sorry, you just seem a little... silly.

From,
Nice coder

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Something else you might consider is temporal difference learning:

http://www.research.ibm.com/massive/tdl.html

http://www.cs.ualberta.ca/%7Esutton/book/ebook/node108.html

http://www.cs.ualberta.ca/%7Esutton/book/ebook/node109.html

It's even more overkill than minimax / alpha beta, but it's also really, really cool.

It also actually bears a little bit of a resemblence to nice coder's idea for updating square weights as you play. I imagine you could come up with some kind of explanation for the square weight updates in terms of temporal difference learning.

Share this post


Link to post
Share on other sites
Quote:
Original post by Lemon Boy
Ok people i have done my research and what not and im going to post me findings and decisions of which you may correct me if im wrong but anyway here goes:

Fristly i need to correct an error on my part, the game i produced is more like connect four and tic-tac-toe, in that it is a 4*4*4 grid (64 spaces) but the spaces in the top can only be filled if the spaces bellow it are filled (ala connect 4), thus in any given turn there is a max of 16 possible moves.

now i read and read about minimax and i noticed that it reiles on a tree of all possible moves (which is somthing i wanted to aviod) and the alpha-beta pruning works on the basis of cutting out the brances of the tree that yeld scores less than your best score, thus stopped the scanning on the whole tree on every AI call.

am i right so far? no anyway....

as for the weighted sqaures routine, that is similar but cuts out the tree of the entire game and focuses on game states where the computer may loose, but i have the impresstion at this approach is more defensive rather than trying to win the game. but as i am new to this AI stuff i understand the weighted squares stuff better than the minimax, not to mention the fact i avoid a tree of an entire game.
so i will use the weighted sqaures and post a link to a game on this forum when i have decent enough AI, i doubt ill use the patterns of the bat but i intend to use them if i can figure out the best way to implement them with rotational-sysmetry! anyone know of a way to that that?


anyway i've typed loads now so if i've miss understood anything please let me know, plus tips rotational-sysmetry will help!

Thanks!!



Weighted squares has about 0 to do with a tree.
Thats why its so fast in games like Go, connect 4, ect. (where you can have pretty good moves, while waiting for < 1ms.)

Just remember, you are using COMPILED BOARDS ONLY.
Don't even try to do string/string matching cause its incredibly slow. (and thats the only way you'd get outdone by minimax. Even though this would probably be about the same time as its eval function :-))

I had some psudocode, but from what i've posted before you should figure out how to do it well within a few minutes.

From,
Nice coder

Share this post


Link to post
Share on other sites
Yeah nice coder i have figured out how to use the weighted squares you suggested, and i started programing it so i should have a working demo which i can upload by the end of the day, (but i have to work :( ).
but anyway i wanted to ask you with the patterns i add on, shall i use patterns based on the WHOLE board or based just on the sixteen avlible moves?
i was think the former be the better option but for different difficulty levels i could programme in the later also??

any views?

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
Something else you might consider is temporal difference learning:

http://www.research.ibm.com/massive/tdl.html

http://www.cs.ualberta.ca/%7Esutton/book/ebook/node108.html

http://www.cs.ualberta.ca/%7Esutton/book/ebook/node109.html

It's even more overkill than minimax / alpha beta, but it's also really, really cool.

It also actually bears a little bit of a resemblence to nice coder's idea for updating square weights as you play. I imagine you could come up with some kind of explanation for the square weight updates in terms of temporal difference learning.


i second the coolness of tdl.

From,
Nice coder

Share this post


Link to post
Share on other sites
Quote:
Original post by Lemon Boy
Yeah nice coder i have figured out how to use the weighted squares you suggested, and i started programing it so i should have a working demo which i can upload by the end of the day, (but i have to work :( ).
but anyway i wanted to ask you with the patterns i add on, shall i use patterns based on the WHOLE board or based just on the sixteen avlible moves?
i was think the former be the better option but for different difficulty levels i could programme in the later also??

any views?


Whole board.

The patterns are for the whole board, and the avalible moves array is for the entire board.

Have you done mvp before?

From,
Nice coder

Share this post


Link to post
Share on other sites
A brute force way is to store all the patterns of tic-tac-toe that lead to wins for a computer. There really aren't that many if you consider symmetry. The computer can look up the answer in this database each time.

For example, if the player starts out the game with an X in the middle, the computer looks up a pattern with an X in the middle that lead to a win and sees what his move should be.

Oops, well I think someone already mentioned this... after reading this long thread hehe

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this