Tic Tac Toe using recursion

Discussion in 'C++' started by jbutler67, Aug 3, 2004.

  1. jbutler67

    jbutler67 Guest

    Does anyone have C++ source code for a Tic Tac Toe game where
    recursion is used?

    I am just learning C++ and have been trying to write a program where
    the user plays against the computer. The program uses recursion to
    assess all possible moves before making a move.

    This is not for a course... it is a starting program that I am using
    to learn C++ basics on my own.

    Thanks in advance.
     
    jbutler67, Aug 3, 2004
    #1
    1. Advertisements

  2. If you're really trying to learn, you shouldn't be asking for
    completed source code. You should try to solve it yourself, and post
    here when you get stuck.

    Jonathan
     
    Jonathan Turkanis, Aug 3, 2004
    #2
    1. Advertisements

  3. jbutler67

    jbutler67 Guest

    Is the following approach on the right track?

    Use a recursive function to finish out all possible remaining moves to
    assess the end result as one of three possible options:
    1) -1 if end result would be a loss
    2) 0 if end result would be a tie
    3) +1 if end result would be a win

    Then choose one of the possible remaining moves that would result in
    eitther a +1 or 0. (If more than one possible "win" moves remains,
    use a random number to pick the move to go with

    In the first few moves of a game, assuming the human player goes
    first, the program would use recursion to assess all 8 follow up
    moves, with all folow ups to each reply move.

    Example, a starting move of the following:

    X | |
    -----------------
    | |
    -----------------
    | |

    would be possible countered by one of 8 follow up moves


    X | O |
    -----------------
    | |
    -----------------
    | |

    or...

    X | | O
    -----------------
    | |
    -----------------
    | |

    or...

    X | |
    -----------------
    O | |
    -----------------
    | |

    or...
    X | |
    -----------------
    | O |
    -----------------
    | |

    etc.....


    And for EACH of the 8 possible follow up moves, there will be 7 reply
    moves, with each of the 7 reply moves having 6 follow up moves....
    etc.
     
    jbutler67, Aug 3, 2004
    #3
  4. Sound reasonable so far.
    Generally, as soon as you find a winning move, you can stop searching.
    Okay, but it doesn't have to be random. You could just use the first
    acceptable move discovered.
    Why don't you start by writing down the signature for the function,
    describing exactly what it does, and writing code which uses the
    function to select the computer's next move.

    Jonathan
     
    Jonathan Turkanis, Aug 3, 2004
    #4
  5. jbutler67

    Buster Guest

    wrote:

    The algorithm to find an optimal move in a two-player zero-sum
    perfect-information game like Tic Tac Toe or chess is called "minimax".
    There are plenty of examples in code on the web. Good luck.
     
    Buster, Aug 3, 2004
    #5
  6. jbutler67

    jbutler67 Guest

    Game Trees and minimax method... exactly what I was looking for!

    Thanks!
     
    jbutler67, Aug 7, 2004
    #6
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.