not 3x3 tic tac toe game AI

How do you make the AI for a tic tac toe game which isn't a 3x3 game but of unlimited size, and there it takes 5 in a row to win? Which algorithms to use?

You need to concentrate on where the points are.
This is gomoku right?

How 'bout this: If you can win in 1 move, place a stone in the place that would make you win. If the other player can win in 1 move, put your stone in the place that would make him win. Otherwise, check each of your stones, and if there are 4 open spaces in a line of which that stone is a part, then add a stone somewhere in that line.

Pretty simple, but it shoudn't be too bad.

Or you could use a brute force approach: Given board size X * Y, and this configuration of pieces on the board, which moves have I had the best win-to-loss ratio with in the past? (it's "memory" is a file) Of equally ranked moves, choose one at random. By "training" this against an entirely random oponnent overnight, you should end up with a pretty good AI. And the longer it trains, the better it gets.

Brute force is too large even on a 20x20 board.


This should show you how to build the ai
http://boardgames.about.com/gi/dynam...or/thesis.html

A 20x20 board would be 3 ^ (20 * 20) = 3 ^ 400 = 7.05508e+190 states. And if each state has two bytes in a file, one representig wins, and the other representing loses, then that would be, assuming my equation parser is working correctly, 1.31411e+182 gigabytes.

A little too big, you're right! ;)

I always figured you use a pick a random number for x, and a random number for y.
IE:
x = //random number between the x coords on your board
y = // random number between the y coords on your board

then just
if//if it is not one point from winning
{
// place x or y there
}
else
{
board[x][y] = // X or Y depending on whos turn
}

that might work, i think ym logic is at least right.

I made a simple Tic Tac Toe program with a (bad) AI, and it will move into a winning position if it sees oine; otherwise it will block you from winning. And if neither of those is the case, then it moves randomly. It works against stupid people. But anybody who's any good at Tic Tac Toe is sure to beat it. So I was trying to think of something better.

You could probably think of it as a pathfinding problem, actually, where "Winning" is the destination, the current state is the start, and all board states that can be reached from a given state are "adjacent tiles."

I actually coded a gomoku game 20x20 tiles which used alpha beta. It could

see ahead 3 or so moves but that's not enough to play good. I lost the source code to it, it was pretty bad. The best way, besides reading http://boardgames.about.com/gi/dyna...tor/thesis.html (you will

probably have to download ghostscript and I think winzip compresses unix style .Z files) is to concentrate on the stones that are near to each other. You can narrow the possible moves perhaps to 20 instead of 400 and reconize force positions.

Thanks, I've got to check that out. I've tested one whcih uses a good ai, which makes it almost impossible to win on the hardest level.

Yes, maybe alfa beta is a way to go.
Thanks!