Brute force also works.

Unless you need your AI to be able to play on a board bigger than 3x3, then you don't need anything more than pattern-matching. If I remember correctly, there are only about 20 distinct patterns (some have wildcards) that really make a difference in Tic-Tac-Toe. Just rotate the board and see if it matches a pattern, rotate again, check for match..... then when you've rotated four times go to the next pattern.

You could just have a data file with each of these possibilities and just itereate through them. You could store data like
XO?
OX?
??#

And # would be where the AI should play. I don't remember if that is one of the patterns but that is a start. I'm sure you could find all the patterns somewhere if you looked.

And if you didn't want to rotate your board four times, you could store the rotations in the datafile. It would only be about 4 times as much data.

And, I consider a draw as not winning or losing, so an AI that can win or draw everytime IS UNBEATABLE in my opinion.

But if you want an AI that is fun to play against, then don't make it perfect, or give a choice of skill level.

Then again, how FUN is tic-tac-toe anyway? I would have never coded a tic-tac-toe game myself if it hadn't been an assignment.

--TheMuuj

[edited by - TheMuuj on April 5, 2002 12:17:06 PM]

rotate the board? uh...

well, i just used tictactoe to learn all of DX''s apis except d3d, the computer AI is what just missing, it also has a directplay in it

oki anyway i did understand the minimax now....

you just get the ''max'' out of the given ''mins'' so for exmaple there is a group of 5 ugly people, and you would like to get the most ugliest then the max there would be the most ugliest right?

and it depends how far you want to search for, if you want to search the deepest then you would get an unbeatable AI,

so for a given situation, there would be N number of paths to follow, search all these paths and get the MAX, if you got it, then follow the MAX path...

so this is my problem then... i just know the concept but err... how do i implement it in C/C++?

See recursion. Definition of recursion? See recursion.

Dave Mark
President and Lead Designer
Intrinsic Algorithm Development
"Reducing the world to mathematical equations!"

hmmm, InnocuousFox, yeah thanks am getting ideas now... so use recursion when searching,

but how do i draw the tree using C/C++? do i like put these in a text file?

x ox (this is the current state, parent)   xox  o (this is the child tree)= 1; then read it accordingly? so if the end of the child tree has a 1 value, it means take this path? 

i''m sorry but the algo is which is hard, hope you could help me out here

quote: Original post by mickey
rotate the board? uh...

I didn''t mean to physically rotate the board. I just meant that the number of possibilites is only 1/4 of the total number because the board and the game is symmetrical. You can make your AI look at the following situation in four ways:

X - O
O X X
- - -

One of them would be:
- O X
- X -
- X O

I don''t mean to actually move the data in memory, but you can write a function that returns the data from a cell based on two coordinates and a rotation number

int GetCell(int rowNumber, int colNumber, int rotation);

With rotation = 0, you would just return cell[rowNumber][colNumber].

But this is only useful for the brute force look-up-table approach to tic-tac-toe AI. I used it because our project was in ARC Assembly, and it was much more efficient to use LUT than to actually "think" about the problem (not to mention a lot easier to code).

--TheMuuj