locked
Tic Tac Toe Bot RRS feed

  • Question

  • Okay im building a tic tac toe but i want the singleplayer to be 100% not win able so i started prediceted EVERY move thats done http://h1.ripway.com/call/Bot.vb in a module witch will return what move it will do so i just want to know how can i make this simple instead of writing 1000 lines +  to get this module done so the bot will defensive and aggrsive and random same time.

    board variable is the board from 1 to 9. 0 equal to whos turn it is.

    -Tuck
    Thursday, May 7, 2009 9:21 AM

Answers

  • Hi Tuck,

    Sorry there is no chance I can create an example. Just don't have the time.

    I see though that your board is linear, a 1 dimensional array. Thats not the way in which the naughts and crosses board should be. It should be a 2 dimensional array.

    [0,0,0]
    [0,0,0]
    [0,0,0]

    It actually looks like the board if you imagine the lines.

    I guess it doesn't really matter as long as you can access the board in the correct ways. This was important. You need to be able to access the board through columns, rows, and diagonals. With the array above the diagonal going from top left to bottom right would be...

    board[0,0]
    board[1,1]
    board[2,2]

    You have the correct idea with giving the user and robot a numeric value to indicate inputs. This is what I was basically getting at. These numeric values of user and robot can be used to calculate a value that helps decide the next move, the calculated value is known as a heuristic value, an idea taken from AI.

    However the numbers 1 for user and 2 for robot aren't very good. It's very difficult to determine the state of a line from these values. Here is an example:

    Lets take a single row; the user has placed two naughts on the row. using the value of 1 to represent a users naught then the total for that row would be 2 (1+1+0). When the application checks that number it doesn't know whether the line is two user inputs (1+1+0 =2) or a single robot input (2+0+0 = 2).

    If you choose a positive number for the robot, say 3, and a negative number for the user, say -1, then it's very easy to determine whats happening on the line. Two user naughts -1+-1+0 = -2; no robot input can create that value so the application knows for sure that two user naughts are there and so it needs to add a cross to stop the user winning.

    Do you get me now?

    naughts and crosses is the Brits tic tac toe. naught is o and cross is x


    www.dsmyth.net | www.dsmyth.net/wiki
    • Marked as answer by Tuck. _ Thursday, May 7, 2009 9:44 PM
    Thursday, May 7, 2009 8:37 PM
  • Hope this shows up ok and clears things up. This is the scenario above, user is o, bot is x, bots move. (Diagonals not considered)

    o o     -1 -1 0   -2  Danger! About to lose!
    x       3 0 0   3    
            0 0 0   0    
                         
            2 -1 0        
                         
    o o x   -1 -1 3   1  Whew!!  
    x       3 0 0   3    
            0 0 0   0    
                         
            2 -1 3        
                         
    o o x   -1 -1 3   1    
    x o     3 -1 0   2    
            0 0 0   0    
                         
            2 -2 3        
              Danger!, About to Lose  
                         
    o o x   -1 -1 3   1    
    x o     3 -1 0   2    
      x     0 3 0   3    
                         
            2 1 3        
              Whew!!        

    www.dsmyth.net | www.dsmyth.net/wiki
    • Edited by Derek Smyth Thursday, May 7, 2009 9:09 PM
    • Marked as answer by Tuck. _ Thursday, May 7, 2009 9:44 PM
    Thursday, May 7, 2009 9:08 PM
  • Here is another example with a win, same as before user is o, bot is x, bot just placed an x.

      x o   3 -1 0 2
    x     3 0 0 3
      0 0 0 0
     
    6 -1 0    
    Aye Aye, chance to win!!
    x o   3 -1 0 2
    x     3 0 0 3
    o   -1 0 0 -1
     
    5 -1 0    
    Arg!
    x o   3 -1 3 5
    x x   3 3 0 6 Aye Aye, chance to win!!
    o   -1 0 0 -1
     
    5 2 3    
    x o   3 -1 3 5
    x x   3 3 0 6 He he!! There's a 6 and it's my move!!
    o o -1 -1 0 -2
     
    5 1 3    
    x o   3 -1 3 5
    x x x 3 3 3 9 w00t!
    o o -1 -1 0 -2
     
    5 1 6            
                               

    www.dsmyth.net | www.dsmyth.net/wiki
    • Marked as answer by Tuck. _ Thursday, May 7, 2009 9:45 PM
    Thursday, May 7, 2009 9:18 PM

All replies

  • Hi Tuck,

    I wrote something like this a long time ago in C++ and unfortunately lost the source code. I remember a little bit about how I did it though. The bot is able to determine it's next move based on the state of the current board.

    The idea is to calculate a heuristic value for each row, column, and diagonal based on the state of the board and then use that heuristic value to determine the best move. Here is an example...

    Computer is o, player is x, computers move  (o is given a heuristic value of 3, x is given a heuristic value of -1)

    oo-
    x--
    x--

    col 1: o x x = 3 + -1 + -1 = 1
    col 2: o - - = 3 + 0 + 0 = 3
    col 3: - - - = 0

    row 1: o o - = 3 + 3 + 0 = 6
    row 2: x - - = -1 + 0 + 0 = -1
    row 3: x - - = -1 + 0 + 0 = -1

    and the same for diagonals

    The program can then determine from this how best to get a row or col to 9 (a winning value). From the above it can determine it's greatest chance of a win is row 1, the closest value to 9 (and also a multiple of 3).

    The idea is to have a unique value for the different variations of a row/col/diag. 
    o o x has a different value from x x o
    o x x has a different value from o x o
    o o x has the same value as o x o

    Get the idea?

    Hope that helps it was a while ago.
    www.dsmyth.net | www.dsmyth.net/wiki
    Thursday, May 7, 2009 11:11 AM
  • didn't get it sorry i have a board variable containing the board values 0 as nothing, 1 as user, 2 as robot it self
    The Board bellow shows that Board(0) it equal to user have the choice but i got that covered so from 1 to 9 is the board with values:
    Board() = {1,
    0, 0 ,0,
    0, 0 ,0,
    0, 0, 0}

    Could you make an small example or something :)

    -Tuck
    Thursday, May 7, 2009 2:12 PM
  • i reread your post and all got it a bit better now but i dont get how u would determ what spot i tried this

    1 2 3     - - -
    4 5 6     - - -
    7 8 9     - - -

    o o -     1 + 2 + 0 = 3 -- as you see it counted to row 3 witch is correct number of a row and is also the correct move.
    x - -     -1 + 0 + 0 = -1
    x - -     -1 + 0 + 0 = -1

    but then i tripped over the real math:
    this bellow i get nothing to go up it need to give row 7 somehow >.<
    o x o     1 + -2 + 3 = 2
    x o x     -1 + 2 - 3 = -2
    - - -     0 + 0 + 0 = 0
    also tried:
    o x o     1 + -1 + 3 = 3
    x o x     -1 + 2 - 1 = 0
    - - -     0 + 0 + 0 = 0

    -Tuck
    Thursday, May 7, 2009 8:35 PM
  • Hi Tuck,

    Sorry there is no chance I can create an example. Just don't have the time.

    I see though that your board is linear, a 1 dimensional array. Thats not the way in which the naughts and crosses board should be. It should be a 2 dimensional array.

    [0,0,0]
    [0,0,0]
    [0,0,0]

    It actually looks like the board if you imagine the lines.

    I guess it doesn't really matter as long as you can access the board in the correct ways. This was important. You need to be able to access the board through columns, rows, and diagonals. With the array above the diagonal going from top left to bottom right would be...

    board[0,0]
    board[1,1]
    board[2,2]

    You have the correct idea with giving the user and robot a numeric value to indicate inputs. This is what I was basically getting at. These numeric values of user and robot can be used to calculate a value that helps decide the next move, the calculated value is known as a heuristic value, an idea taken from AI.

    However the numbers 1 for user and 2 for robot aren't very good. It's very difficult to determine the state of a line from these values. Here is an example:

    Lets take a single row; the user has placed two naughts on the row. using the value of 1 to represent a users naught then the total for that row would be 2 (1+1+0). When the application checks that number it doesn't know whether the line is two user inputs (1+1+0 =2) or a single robot input (2+0+0 = 2).

    If you choose a positive number for the robot, say 3, and a negative number for the user, say -1, then it's very easy to determine whats happening on the line. Two user naughts -1+-1+0 = -2; no robot input can create that value so the application knows for sure that two user naughts are there and so it needs to add a cross to stop the user winning.

    Do you get me now?

    naughts and crosses is the Brits tic tac toe. naught is o and cross is x


    www.dsmyth.net | www.dsmyth.net/wiki
    • Marked as answer by Tuck. _ Thursday, May 7, 2009 9:44 PM
    Thursday, May 7, 2009 8:37 PM
  • Hope this shows up ok and clears things up. This is the scenario above, user is o, bot is x, bots move. (Diagonals not considered)

    o o     -1 -1 0   -2  Danger! About to lose!
    x       3 0 0   3    
            0 0 0   0    
                         
            2 -1 0        
                         
    o o x   -1 -1 3   1  Whew!!  
    x       3 0 0   3    
            0 0 0   0    
                         
            2 -1 3        
                         
    o o x   -1 -1 3   1    
    x o     3 -1 0   2    
            0 0 0   0    
                         
            2 -2 3        
              Danger!, About to Lose  
                         
    o o x   -1 -1 3   1    
    x o     3 -1 0   2    
      x     0 3 0   3    
                         
            2 1 3        
              Whew!!        

    www.dsmyth.net | www.dsmyth.net/wiki
    • Edited by Derek Smyth Thursday, May 7, 2009 9:09 PM
    • Marked as answer by Tuck. _ Thursday, May 7, 2009 9:44 PM
    Thursday, May 7, 2009 9:08 PM
  • Here is another example with a win, same as before user is o, bot is x, bot just placed an x.

      x o   3 -1 0 2
    x     3 0 0 3
      0 0 0 0
     
    6 -1 0    
    Aye Aye, chance to win!!
    x o   3 -1 0 2
    x     3 0 0 3
    o   -1 0 0 -1
     
    5 -1 0    
    Arg!
    x o   3 -1 3 5
    x x   3 3 0 6 Aye Aye, chance to win!!
    o   -1 0 0 -1
     
    5 2 3    
    x o   3 -1 3 5
    x x   3 3 0 6 He he!! There's a 6 and it's my move!!
    o o -1 -1 0 -2
     
    5 1 3    
    x o   3 -1 3 5
    x x x 3 3 3 9 w00t!
    o o -1 -1 0 -2
     
    5 1 6            
                               

    www.dsmyth.net | www.dsmyth.net/wiki
    • Marked as answer by Tuck. _ Thursday, May 7, 2009 9:45 PM
    Thursday, May 7, 2009 9:18 PM
  • woot dude even i had to take some time to read all you wrote and understand it its the coolest way and as my array is 1 to 9 it will be easy to use with this THX ALOT MAN =D
    -Tuck
    Thursday, May 7, 2009 9:44 PM
  • Hey Tuck, no worries man, glad to help. It was an interesting project when I did it.

    There is a little more. It's worth while adding 'rules' to the application/bot as well.

    In the second example

      x o   3 -1 3 5
    x x   3 3 0 6
    o o -1 -1 0 -2
     
    5 1 3            
                       

    The 6 is given a higher precedence than the -2. Thats like a rule, take the win over blocking a loss.

    Other 'rules' might be marking the middle square as it has more advantages than the outer squares.

    And so on... certain behaviour that a human might make.



    You can even go one step further and generate all the different variations of the boards state and using a heuristic value determine the probability of which move is more likely to result in a win. You don't need to do that with tic tac toe, it's very simple.

    If you think chess then given the positions of the pieces on the board the application can create a number of 'next move' scenarios and using heuristics the application can work out which scenario is more likely to result in a win, again applying certain rules to the scenario. 

    The application builds whats known as a decision tree.
    http://en.wikipedia.org/wiki/Decision_tree

    It can get very complex though doing that but it's very powerful. In the chess example some software I imagine would maybe look 5 or 10 moves ahead, maybe even more. It's less valuable looking far ahead the more pieces there are.

    That was just for information if your interested in becoming a game programmer.
    I haven't thought about this in years so man glad to help!!
    www.dsmyth.net | www.dsmyth.net/wiki
    Friday, May 8, 2009 1:01 PM