Hello, I'm a C++ programmer, and post alot in beginner's forum, but I know nothing about AI, nothing. I am trying to create a tic-tac-toe game, but don't know how to do the AI without hardcoding it with a bunch of cases. Is there a way to do it, that I don't see?

Any proper method of AI used for a tic-tac-toe game would be overkill, unless your purpose is just to learn AI. In that case, a neural net or MinMax would best suit your purpse for tic-tac-toe. If you just want to get something that works, I would imagine that randomly picking 3 squares from a list of available squares and then rating them according to some set of rules would be sufficient.





Good site for AI
MinMax algo
Neural nets in plain English .

[Edited by - bit64 on January 15, 2005 7:52:05 PM]

Is it bad if i dont understand Minmax? Its wierd lol..?

This link may explain it a little clearer for you, and it uses an example with tic-tac-toe (how appropriate :))

Its ok, there are simpler ways to implement tic-tac-toe ai.

For 3x3 ttt. there are only 19683 individual configurations (3^9).
Now, when each image is rotated, it is basically the same.

So, There should be about a quater of 19683, unique configurations (ie. one isn't a transposition of another).

Thats 4921. 4,921 configurations. (including illegal ones, these are the ABSOLUTE MAXIMUM unique configs for the board).

Now, that is SMALL.

You can basically Write off, each and every boardstate (legal ones, those are going to be a lot smaller then 4,921), which ones go to where.

Now that you have that (and have saved it), you can write your tic-tac-toe game.

Now, what you do, is you find the optimum path.

You basically run minimax (which you will understand, eventually...) on the data.

From that, you generate a decision tree.
That tree lets your bot make decistions. For eg: if he makes this move, make this other move.

Once you've got enough of those, you can have your bot making perfect moves in milliseconds.

From,
Nice coder

Ugh okay, I thought I understood it, but then went to code it, and I realized I'm going to have a neverending list of if statements


thats what i tried to start doing, but Ive stopped now.

Sorry if this post is a bit.... Disorginised...
First: You need to change the way youve got things.

Keep everything in a 1D bit array. (a long, 18bits used, the rest not used).

It makes it easier to use.

If you need to know if your number is in a squuare, then you just go

Me = Board & (1 << (square + square))
Comp = board & (2 << (square + square))

If one of them is > 0, then thats whose got the piece there.

To make yoru move is simplicity itself, its simply
board |= (1 << (square + square)) or
board |= (2 << (square + square)) for the comp.

If you want to know, wether you occupy a number of squares, its easy!

All you need to do, is bitwise & the board, with a set of bits corresponding
To the squares needed.

For eg,
01 10 00 00 00 00 10 01 00

Would be

O|X|N
N|N|N
X|O|N

Now, to explain the boards.

What you need, is that because each square inside it, takes up 2 bits, you have to multiply the square number by 2, in order to get the right offset.

Now, to check, if, say a diagonal was going to win, what you would do, is first
&& it with

X|0|0
0|X|0
0|0|X

Which would be 10 00 00 00 10 00 00 00 10

You then check if its the same.
if it is, then x wins.

If not, then x didn't win.

To check if your board is full, you go and try this

int x
Board = board << 1 //Rightshift board by one
for (x = 0; ((x = 8) | !(Board = board >> 1)); ++x);


//Keep looping until it finds a spot where the board is equal to zero (Ie. past any spots where theres occupied squares). Then the ! negitates it, and the | stops the loop.

I think. You might want to use another method. It takes longer, as the board gets more and more cluttered. You simply check, if X is equal to 8. if it is, then your game is drawn.

Use a copy of my fast eval function (its on one of the threads i just posted in).
It works with the least number of comparisons (especially if you use the 1D bit array, that would be really great at this)).

You would probably need a board struct.

Basically, your board long, your evaluation function data, and its score.

You could also get its sucessors, if you want to keep the whole things as a tree, and keep it after you've generated it. (so, you can search it without having to remake the tree).

I think this is clearish.
From,
Nice coder

Um, Okay you lost me there, could it be because I dont understand bitwise logic? It looks like greek to me, except the for loop, and I dont get half of it. =(

ok. 10cc's of logic, stat!

ok, i was a little displaced while doing that. Maybe this should be better.

Sq = (Board & (3 << (square + square))) >> (square + square)

This basically isolates the squareth 2 bit pair in board.
I use this to store the moves, Quickly.
How does it work?

3 is = 11 in binary

When i bitshift it to the left, by square + square (i'm skipping by two squares each time, so i use square + square, ot compensate), i end up with something like

110000000

Which then, when anded with a board position, say
0101010110

Results in
0100000000

I then need to rightshift it, to get the numbers on the right end of the scale, so i end up with

01

Which is, O.

(you can use if statements on this part)
If you don't understand this, then you should look up some tutorials on bitwise operations (google is your friend.)

When making a move, you need to change only those two bits. So, you go

Board |= y << (square + square)

Where y = 1 for O, or 2 for X.

I have no idea what the loops meant to do Sorry.

From,
Nice coder

There is also another solution...
It requeriers use of genetic algoritms.
In population every individual has information about board's configuration and how many times was succesful and what should we do.
Next we need to use genetic operators like crossing, mutation.
We are crossing only similar individuals (to keep interesting solutions alive;) )
(Using roulette rule for selecting candidates)
Mutation probabilty should be really low (below 0.03).

And finaly...
When chosing what to do we have to find individuals whit similar information about board and chose one of them (again by using rule of the roulette)

Next step is to prize successful candidates and punish loosers.
If we "survived" (in next 10 moves we didn't lose) - candidate was successful
If we lost - punish him.

Of course before someone can use it in game we have to "train" it.
Couple of thousands of steps should be enought;)

I have somewhere project which I made for Genetic Algorithm course, but it will take couple of days to find it if someone is interested.

Regards...
And sorry about my english...