Thread: TicTacToe AI

  1. #1
    Registered Abuser Loic's Avatar
    Join Date
    Mar 2007
    Location
    Sydney
    Posts
    115

    TicTacToe AI

    I’m making my first little game and I have gotten up to the part where I am trying to work out how I am going to do the AI, as I am new to this im not to sure how to go about it… the best way that I can think of would be to use quite a few if statements to determine where the “cpu” will go next…

    Eg:
    Code:
    if (pos[0][0] && pos[0][1] == 'X') {pos[0][2] = 'O';}
    Where pos[0][0] is row “0” column “0”

    Is that the best way to create “AI” for a tictactoe game? Or is there a better more effect method?

  2. #2

  3. #3
    Registered User
    Join Date
    Nov 2004
    Location
    Pennsylvania
    Posts
    434
    You gotta minimax it, and it's tricky for a new programmer, i've been at this for years and (well this just goes to show i suck =P) still havent gotten it completely down.
    "Anyone can aspire to greatness if they try hard enough."
    - Me

  4. #4
    Registered Abuser Loic's Avatar
    Join Date
    Mar 2007
    Location
    Sydney
    Posts
    115
    Quote Originally Posted by Junior89 View Post
    You gotta minimax it, and it's tricky for a new programmer, i've been at this for years and (well this just goes to show i suck =P) still havent gotten it completely down.
    Yeah, i am just going through that wikipedia page on it... just a little bit lost.. hahaha

    But hopefully i can find something broken down a little more / more in depth...

  5. #5
    Registered User
    Join Date
    Nov 2004
    Location
    Pennsylvania
    Posts
    434
    It's tricky, it consists of creating a tree (minimax tree) of Every possible move one can make with every possible move leading from there, etc. etc.

    If you have experience with Linked Lists, and Binary Trees specifically, what you're going to do is learn that first, and learn it very well. Then you basically take a binary tree but instead of each leaf having 2 nodes, each has however many possible moves exist. Obviously writing the tree itself by hand would be tricky, so you need an algorithm to create the tree in the program, than a form of a minimax algorithm to judge and sort the tree as the game is played, determining the best move as you go along.

    One would assume such a simple game would be easy, ha, it isn't such a piece of cake however.


    Good luck!
    "Anyone can aspire to greatness if they try hard enough."
    - Me

  6. #6

  7. #7
    Registered User
    Join Date
    Dec 2005
    Location
    Colchester, Essex, United Kingdom.
    Posts
    31
    I posted in a thread here not so long ago. I basically explain how to get a variation of the minimax algorithm up and running. This variation is called AlphaBeta and produces exactly the same output as minimax, but in a much faster time. If you have any particular problems with the code, just ask. Good luck!
    If it wasn't for C, we'd be using BASI, PASAL and OBOL.

  8. #8
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    Tic tac toe is a solved game, you don't actually need a minimax tree, you can precompute everything and just look up your next move in a table.

  9. #9
    Registered User
    Join Date
    Dec 2005
    Location
    Colchester, Essex, United Kingdom.
    Posts
    31
    Quote Originally Posted by Perspective View Post
    Tic tac toe is a solved game, you don't actually need a minimax tree, you can precompute everything and just look up your next move in a table.
    And how are you going to compute that information? A minimax tree perhaps?
    If it wasn't for C, we'd be using BASI, PASAL and OBOL.

  10. #10
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    so long as you don't do any pruning you could use a tree method, otherwise I could make your AI vomit by making a non-optimal move. The alternative is just exhaustive enumeration of board states, TTT is relatively small. You can also exploit symetries to make it even smaller.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Simple space combat AI
    By VirtualAce in forum Game Programming
    Replies: 5
    Last Post: 01-06-2009, 12:54 AM
  2. chess ai contest
    By Raven Arkadon in forum Contests Board
    Replies: 7
    Last Post: 07-09-2005, 06:38 AM
  3. AI Contest Proposal
    By MadCow257 in forum Contests Board
    Replies: 4
    Last Post: 03-13-2005, 03:27 PM
  4. Game Design Topic #1 - AI Behavior
    By TechWins in forum Game Programming
    Replies: 13
    Last Post: 10-11-2002, 10:35 AM
  5. Technique of all board-like games?
    By Nutshell in forum Game Programming
    Replies: 28
    Last Post: 04-24-2002, 08:19 AM