Thread: not 3x3 tic tac toe game AI

  1. #1
    Unregistered
    Guest

    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?

  2. #2
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    You need to concentrate on where the points are.
    This is gomoku right?

  3. #3
    Registered User
    Join Date
    Aug 2001
    Posts
    47
    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.

  4. #4
    Unregistered
    Guest
    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

  5. #5
    Registered User
    Join Date
    Aug 2001
    Posts
    47
    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!

  6. #6
    Ryce
    Guest

    Lightbulb i got an idea..

    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.

  7. #7
    Registered User
    Join Date
    Aug 2001
    Posts
    47
    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.

  8. #8
    Registered User
    Join Date
    Aug 2001
    Posts
    47
    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."

  9. #9
    Unregistered
    Guest
    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.

  10. #10
    Unregistered
    Guest
    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!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help me with my simple Tic tac toe prog
    By maybnxtseasn in forum C Programming
    Replies: 2
    Last Post: 04-04-2009, 06:25 PM
  2. 2D RPG Online Game Project. 30% Complete. To be released and marketed.
    By drallstars in forum Projects and Job Recruitment
    Replies: 2
    Last Post: 10-28-2006, 12:48 AM
  3. tic tac toe AI roadblock >:-(|)
    By dark_rocket in forum Game Programming
    Replies: 5
    Last Post: 06-12-2006, 05:13 AM
  4. Tic Tac Toe AI
    By Isamo in forum C++ Programming
    Replies: 9
    Last Post: 01-01-2004, 11:32 AM
  5. Tic Tac Toe -- Can you guys rate this please?
    By Estauns in forum Game Programming
    Replies: 2
    Last Post: 09-15-2001, 10:22 AM