Pop over to http://citeseer.nj.nec.com/ and do a search for Aske Plaat. He''s written hundreds of papers on various game-playing decision tree algorithms....

A*

it solves everything

A* to solve tic-tac-toe? Interesting....
What would your heurisitc be estimating, and could you give an example of an admissible heuristic?

I wrote a TTT game without AI.
The squares have a value. The computer picks the square that is open and has the highest value. It''s not that great since there is only one way to win.

http://agdn.cjb.net

I recently made a TTT game on a 30*30 board, 5 in a row not bounded at both ends by an opponent wins. Trying to assign a value to each square just won''t work, with that many squares its impossable to say which will be powerful in any given game. Just trying to win or block is also not too smart, anybody who has played TTT with more than 3 in a row wins knows that unless somebody makes a stupid mistake (which the AI will not do) the only way to win is to have 2 different locations that will win you the game, making the move unblockable. As such you AI will need to defend against this rather than just block at the end. for example if u opponent has

..XXX..

and four in a row win, you have already lost. Clearly there are more complex formations than this one.

I would seggest using mini max with a depth of about 4. The evaluation should be based around that idea of runs (number of peices in a row) that are not already blocked. Weighting should be given to longer runs and I would also weight runs by the opponent slightly higher than I would my own runs (creating a slightly defensive AI).

It''s not easy to describe how my TTT-AI works(B/c i''m only 15 and my mother-language isn''t english )

I will post the source-code in a few days (Have to write comments for it... )....

quote: Original post by Angel_of_Death
It''s not easy to describe how my TTT-AI works(B/c i''m only 15 and my mother-language isn''t english )

I will post the source-code in a few days (Have to write comments for it... )....

That would be interesting to see, Angel. Please do so.




Ferretman

ferretman@gameai.com
www.gameai.com
From the High, Cold, Snowy Mountains of Colorado

quote: Original post by cedricl
Building a tree of anything is probably not worth the effort.

1. Check if you can win in one shot
2. Check if your opponent can win in one shot and block

After that, there really aren''t many combinations left and you can check them manually.

Cédric

I agree that a tree is hardly worth the effort, though reading over the list of solutions I''m amazed at their variety.

When I''ve played on paper I''ve always either picked the center (as somebody else suggested) or picked a corner. Then follow the rules above and you''ll tend to win every time...I think a 3x3 TTT board devolves into something like 5 or 7 possible positions, right? You can just store them for something that small.




Ferretman

ferretman@gameai.com
www.gameai.com
From the High, Cold, Snowy Mountains of Colorado