Simple AI for tic-tac-toe...

Hi,

A few days ago i read a thread and someone posted a simple AI for the naughts and crosses game, which looks 'something' like this:

1) If computer can win, do so
2) IF computer can prevent player from winning, do so
3) Else, move to empty spot

BUt i can' remember it exactly. I tried to search for that thread but i still couldn't find it after 15mins of search. If that person read this thread could u please fill in the missing steps of the simple AI. Or if anyone knows something better or something to add on to the steps can u do so pls?

thnx in advance

Also there was a file available for download at that thread i was talking about as well. Can that person be kind enough to send to me? Coz i really want to learn from it. I ran the program once but now i lost it. Pls give a hand.

many thnx

Was it this one?

http://www.cprogramming.com/cboard/s...hlight=crosses

NO. The one i'm talking about has a a post actually outlining the steps or algorithm of the AI used in the game. Or if i got it wrong, it could be in a thread not exactly titled tic tac toe. And anyway the program is different to the one in the link above too.

thnx but can someone suggest another one?

GUys i found the source file!! I found it in the unzipped directory. Lucky i didn't empty that folder. Well i'll post it here anyway coz i think it's good. BUt can ppl still add to the above AI procedures if anything is missing?

you could also do a lot of if statments and treat the board as a 2d array
computer=1
player=2
empty=0
eg: if((board[1][1]==1)&&(board[1][2]==1))
{
board[1][3]=1;
}

if you did it this way you have to remeber to check to see if the comp can win first... then look for any player moves to block then if all this fails move to an open space

you wouldn't really need AI. Just an algorithm that you could work out to make the best move. Simple logic really - itt'l just be maybe an array of combinations and the best path, but that might make it too difficult. Computer's never make mistakes - you'd either never win, or you'd have to pick a random 1 or 0, then let them win.

Just write a program that will allow you to define moves, or write your own data file using edit.


0 1 2
3 4 5
6 7 8

Then you would define single moves -> those that only look for 1 opposite piece.

Check here If true, go here
1 , 4

But in Tic Tac Toe on single moves, if the player does not go in the middle, that's the best first single move. If he does, then move to the corners based on your single moves or just pick one of the four corners.

Then you check for double moves, moves that you must block or you will lose.

Check Check GoHere
0 4 8
2 4 6
6 4 2

This is hard-coding the moves, but hey it's tic tac toe and there aren't that many moves.

For varied difficulties you would set a percentage of the time that the computer actually moved to where it 'knew' to move based on your data. For instance at level 1, the percent might be 0 to 75. He has a 25% chance of actually going with what the data says, and a 75% chance of randomly picking a location. Very easy to beat. On level 9, you might reverse the odds, or even make them less. This would make the computer very hard, if not impossible to beat.


Since all of these data members fit into bytes, your data file would be very small and could be packed into integers or longs so that you could not read the dat file in a text editor. At runtime, just load the dat file into an array or 2 arrays, one for single moves and one for doubles. When the player moves, check for doubles first (unless it is the first move, doubles can only happen on second turn) since they can cause us to lose, and then check for singles, no danger of losing, make a move. You could also put in several single move choices instead of just one per check to make the computer do diff moves at diff times.

But all in all, since it is tic tac toe, every game can only be so different - just like in real life. So if the game is near unbeatable on level 9, you've prob done the job and it is time to move on to something more interesting.

I would recommend using an alpha beta search or minimax for practice and it will save typing.

http://www.seanet.com/~brucemo/topics/alphabeta.htm
It's pretty straitforward for ticktack toe.

HI,

What category does 'alpha-beta' types of programs fit in?

Second question, is there a quicker way, or actually a not-so-cubersome way of testing if anyone wins after each move? Currently, I have nine cases ( for each square on the board player just moved ) and for each case, have like 6 or 7 or more if statements testing if the square next to it ( horizontally, vertically or diagonally ) has the same symbol ( cross or a nought ). Is there a faster way?

thnx

Quote:

---

What category does 'alpha-beta' types of programs fit in?

---

Any type of game where the other player is trying to maximize
his position while trying to minimize the other players.

Quote:

---

Second question, is there a quicker way, or actually a not-so-cubersome way of testing if anyone wins after each move? Currently, I have nine cases ( for each square on the board player just moved ) and for each case, have like 6 or 7 or more if statements testing if the square next to it ( horizontally, vertically or diagonally ) has the same symbol ( cross or a nought ). Is there a faster way?

---

I think the fastest way is to represent a board having
9 bits for each player.

So

Code:

---

OOX
O O
XXO

---

has
nought = 110101001
cross = 001000110

Then to generate the empty spaces
empty_space = (~cross) & (~nought)

For example to determine if noughts won across the horizontal
(nought & 111000000) || (nought & 000111000)
|| (nought & 000000111).
As c only likes hex
(nought & 0x1C0) || (nought & 0x38) || (nought & 0x7)

This should be faster than using an array. By knowing who
did the last move and where other improvements could
be made.