Thread: Simple AI for tic-tac-toe...

  1. #1
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020

    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

  2. #2
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    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

  3. #3
    It's full of stars adrianxw's Avatar
    Join Date
    Aug 2001
    Posts
    4,829
    Wave upon wave of demented avengers march cheerfully out of obscurity unto the dream.

  4. #4
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    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?

  5. #5
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    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?

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

  7. #7
    Registered User
    Join Date
    Sep 2001
    Posts
    4,912
    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.

  8. #8
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    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.

  9. #9
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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.

  10. #10
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    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

  11. #11
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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.

    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. tic tac toe
    By holden in forum A Brief History of Cprogramming.com
    Replies: 8
    Last Post: 05-09-2004, 09:59 AM
  2. Help with Tic Tac Toe game
    By snef73 in forum C++ Programming
    Replies: 1
    Last Post: 04-25-2003, 08:33 AM
  3. Tic Tac Toe Help
    By aresashura in forum C++ Programming
    Replies: 1
    Last Post: 11-21-2001, 12:52 PM
  4. not 3x3 tic tac toe game AI
    By Unregistered in forum Game Programming
    Replies: 9
    Last Post: 08-29-2001, 04:02 AM
  5. tic tac toe
    By bart in forum Game Programming
    Replies: 2
    Last Post: 08-27-2001, 07:53 PM