Tic-Tac-Toe

No Move Computer Win

During a data structures and algorithms course at Champlain College, I implemented a Computer vs. Player Tic-Tac-Toe game using a minimax tree. It's implemented so that the computer always counters a player's attempt to win. A tie is the best outcome the player can earn in the game's current state.

    Difficulty

    The program is configured to maximize the computer's chances, while minimizing the user's (i.e., a 1-ply lookahead). The AI could be weakened if the program was configured to use more than 1-ply, which would create a more practical game. Adjusting the difficulty would be more applicable to games like Chess or Checkers, where there are significantly more moves than in Tic-Tac-Toe.

    Choosing a Move

    The computer chooses a move by looking at the one that maximizes the chance of winning. When the board is empty, there are technically nine different possible moves, but only three of those are unique.

                  |   |
                ---------
                  |   |
                ---------
                  |   |
    
                   /|\
                  / | \
                 /  |  \
                /   |   \
               /    |    \
              /     |     \
    
              o-----------o
     x|   |   |   |   |   |   |   |
    --------- | --------- | ---------
      |   |   |   | x |   |   |   |x
    --------- | --------- | ---------
      |   |   |   |   |   |   |   |
              o-----------o
    
                 maximum
    
       (-1)        (1)         (-2)
    

    The best move is chosen by looking at the possible responses to a move. By using a simple calculation:

    for all unique player responses
        max = computer possible win states - player possible win states
    take lowest max as maximum for move
    
            |   |
          ---------
            | x |
          ---------
            |   |
    
             / \
            /   \
    
      |   |       |   |
    ---------   ---------
     o| x |       | x |
    ---------   ---------
      |   |      o|   |
    
    6 - 4 = 2   5 - 4 = 1
    
    maximum for move = 1
    

    The computer chooses to play the center of the board for the first move, because it provides the highest chance of winning (i.e., 1 > -1 and -2). If there were two moves that had the same maximum, then the computer would have to find the move that minimizes the opponents chance of winning.

    Improvements

    The game could use the option to adjust difficulty, which can be accomplished by tweaking the amount of lookahead used when determining the computers next move. In addition, it would be nice to allow either the computer or the player to make the initial move, thus providing some variety in the gameplay.

    Source

    April 02, 2011 | project

    Hi, I am Chris Brough. I am a twenty-one year old senior studying Game Programming at Champlain College in Burlington, Vermont.

    I've had an immense interest in technology and video games for as long as I can remember. When I'm not developing my knowledge in programming, I enjoy drawing and playing video games.

    Among the many interests I have in programming, I'm currently focused on data-oriented design, networking, and 3D graphics.

    Contact info: chris@chrisbrough.com