#1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2012
    Posts
    83
    Rep Power
    2

    Tic Tac Toe Game AI help


    following is the code I wrote for a tic tac toe game.
    the user is asked whether he wants to play with another human or CPU.

    I need some basic rules to make the CPU AI (as in what choices the cpu should make for different difficulty levels).

    It would be hard for anyone here to read all the code and write me a function for AI, so just tell me general rules for a tic tac toe game for a good cpu player.
    (I've added the code just in case someone wants to see what I already have. It is well commented I think.)

    note: I dont know how to make the spoiler thing to hide the code. if a mod can do it, then please do.

    Thanks in advance.
    Last edited by zedeneye1; December 18th, 2013 at 11:24 PM.
  2. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,891
    Rep Power
    481
    Good! The program can serve a game between human players.

    Improvement: simplify user input. With just 9 cells a single character a through i or digit is sufficient input.

    Bad! I haven't identified the cause of the first error (likely reading the y or end of file as a digit) and the second problem probably stems from stack overflow on the senseless needless recursion of main.
    Code:
    $ yes "1 1 y "|./ttt
    ...
    Instructions:
    Player 1 plays with <0> and Player 2 plays with <1>.
    
    
    yes: standard output: Broken pipe
    yes: write error
    Segmentation fault (core dumped)
    $ 
    $ time yes "1 1 1 1y "|./c > /dev/null
    yes: standard output: Broken pipe
    yes: write error
    Segmentation fault (core dumped)
    
    real	0m1.759s
    user	0m1.571s
    sys	0m0.053s
    $
    So fix the program before before you add an AI unit.

    Some years ago when I was a lot smarter than I am today I wrote ttt to learn BASICA on the IBM-PC. TTT is so simple with so few states that someone could build a Tinker toy computer to play it. My program never lost and tried to win. However, I did not enumerate all the states. When moving first it chose the center with high probability and a corner with lower probability. After that it searched for defense, then moves that would give two in a row ensuring victory. Surprise, surprise, the code showed me a trick I hadn't considered where I'd have automatically moved g instead of d
    Code:
    XOc
    XXf
    ghO
    Now we ask, do you want a general game solving strategy that will work for a many-state game like chess (the min-max algorithm with pruning is the algroithm I'm with which I'm familiar), or simply a way to get through tic-tac-toe?
    Last edited by b49P23TIvg; December 14th, 2013 at 04:48 PM. Reason: repair code tag
    [code]Code tags[/code] are essential for python code and Makefiles!
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2012
    Posts
    83
    Rep Power
    2
    Originally Posted by b49P23TIvg
    Good! The program can serve a game between human players.

    Improvement: simplify user input. With just 9 cells a single character a through i or digit is sufficient input.

    Bad! I haven't identified the cause of the first error (likely reading the y or end of file as a digit) and the second problem probably stems from stack overflow on the senseless needless recursion of main.

    <code removed for ease in reading>

    So fix the program before before you add an AI unit.

    Some years ago when I was a lot smarter than I am today I wrote ttt to learn BASICA on the IBM-PC. TTT is so simple with so few states that someone could build a Tinker toy computer to play it. My program never lost and tried to win. However, I did not enumerate all the states. When moving first it chose the center with high probability and a corner with lower probability. After that it searched for defense, then moves that would give two in a row ensuring victory. Surprise, surprise, the code showed me a trick I hadn't considered where I'd have automatically moved g instead of d
    Code:
    XOc
    XXf
    ghO
    Now we ask, do you want a general game solving strategy that will work for a many-state game like chess (the min-max algorithm with pruning is the algroithm I'm with which I'm familiar), or simply a way to get through tic-tac-toe?
    -Thanks. This was a class project (to make a simple ttt game for 2 humans). I want to add single player with a difficulty level setting just to impress the instructor and "be ahead of everyone else" hehehe.

    -I've played some ttt codes on the internet which had single digit input and I don't want the instructor to feel that I copy/pasted(cuz I didn't).

    -The code is running fine on my compiler dev c++ 5.4.2. I've rechecked just now by copy/pasting the code in OP and compiling, compiled without problem.

    -I already know the easy method of making a stupid cpu by simply using the random function. Every time it would make a random choice without thinking. I'm saving that for the difficulty level 1. For level 2, I plan to use 50% pure random moves and 50% properly thought out moves(so the user will have more difficulty but could win maybe half of the time). And for level 3, 100% fully thought out moves(should draw every time if the user knows ttt game well, saying this from my experience playing with another ttt expert on paper during childhood).

    -I've already figured out that if user inputs at a corner, make a center cpu move(I've actually added that in the AI function already). And I also know if the user has more than two in a row, the cpu should fill the place left. But I can't figure out CPU offensive. how can it win when it isn't given the first move. Naturally when the other guy makes the first move, you become defensive. And the game draws.

    -I need to know what to do if the user is not so clever and the first move he makes is not a corner, infact it is center (now cpu has good chance at winning).

    -I don't know algorithms, I'm just a beginner type of a guy. But if you can provide a link to the min-max algorithm you are talking of, I'll be interested in reading it.

    Thanks a lot for the help.
    Last edited by zedeneye1; December 14th, 2013 at 08:23 PM.
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2012
    Posts
    83
    Rep Power
    2
    bump.....
  8. #5
  9. Lord of the Dance
    Devshed Expert (3500 - 3999 posts)

    Join Date
    Oct 2003
    Posts
    3,663
    Rep Power
    1945
    Originally Posted by zedeneye1
    But I can't figure out CPU offensive. how can it win when it isn't given the first move. Naturally when the other guy makes the first move, you become defensive. And the game draws.
    That the "issue" with tic tac toe, if one player knows how to play, the player wont loose. If both player know the game, it will (should!) always end in a draw.
  10. #6
  11. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,891
    Rep Power
    481

    Simplification of prior post


    The program is incorrect. I can make it fail using your compiler.

    Use a loop instead of recursion on main.

    Offense (and defense as well): Win or block first. Then look ahead for a move that gives two opportunities to win. Move there as it will either win or block.

    min-max on youtube

    And the number of states after accounting for rotation/reflection/transposition is miniscule. Try them all with pen and paper.
    [code]Code tags[/code] are essential for python code and Makefiles!
  12. #7
  13. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2012
    Posts
    83
    Rep Power
    2
    Originally Posted by b49P23TIvg
    The program is incorrect. I can make it fail using your compiler.

    Use a loop instead of recursion on main.

    Offense (and defense as well): Win or block first. Then look ahead for a move that gives two opportunities to win. Move there as it will either win or block.

    min-max on youtube

    And the number of states after accounting for rotation/reflection/transposition is miniscule. Try them all with pen and paper.
    thanks for the help...
    but the code is compiling..

    here's a screen shot...



    I'll try this on the weekend...

    thanks again.
    Last edited by zedeneye1; December 17th, 2013 at 01:46 AM.
  14. #8
  15. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,891
    Rep Power
    481
    My posts say nothing about your program "not compiling". I actually gave my best effort to criticize using the formula "say two nice things, register complaint, follow with another nice compliment".

    Hence my first "bullet point", which you quoted (without understanding) [q u o t e=me]"Good! The program can serve a game between human players." From this you should infer that I compiled your program and played a game with it.

    Next I showed the output of your program (again, from your running compiled program) in two cases that core dump. I suspect different reasons for these failures. Correct tic-tac-toe programs do not core dump. Correct ttt programs access memory properly, and when they allow more than one game they allow an infinite number of games.

    I suppose passing off a unix pipe lined command is overly terse. You didn't ask for explanation, however. (pipes and io redirection have worked in DOS since version 2 and maybe were always available.) That leaves for explanation the yes command, which any sane Microsoft world living citizen would have written for self.

    yes is an input source just as /dev/null is an output sink.
    Code:
    $ yes  # yes writes y or the command line argument until interrupted
    y
    y
    y
    ^C
    $
    Code:
    $ yes "" | cat -n | head -8    # Unix pipe for numbering
         1	
         2	
         3	
         4	
         5	
         6	
         7	
         8	
    cat: write error: Broken pipe
    yes: standard output: Broken pipe
    yes: write error
    $
    Therefor my test
    $ yes "1 1 1 1y "|./c > /dev/null
    attempts to play your program indefinitely. Your program core dumps after a while. I am confident that the cause is stack overflow by the recursion on main for new games. Were I to write a program where the correct outcome is "core dump" the purpose would be to verify my understanding of a programming feature.
    Last edited by b49P23TIvg; December 17th, 2013 at 07:55 AM.
    [code]Code tags[/code] are essential for python code and Makefiles!
  16. #9
  17. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2012
    Posts
    83
    Rep Power
    2
    Originally Posted by b49P23TIvg
    .............
    so i need to fix it or else i loose marks in the project then? how about I put the entire thing in a function and that same function calls itself again and again for more games? wouldn't that be the exact same thing except its not the main function doing it?

    is it wrong to use a recursive main function?

    thanks for the help.
  18. #10
  19. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,891
    Rep Power
    481
    Here's a c program recursive on main. It's a seasonal program and safe to run.
    Code:
    #include <stdio.h>
    main(t,_,a)char *a;{return!0<t?t<3?main(-79,-13,a+main(-87,1-_,
    main(-86,0,a+1)+a)):1,t<_?main(t+1,_,a):3,main(-94,-27+t,a)&&t==2?_<13?
    main(2,_+1,"%s %d %d\n"):9:16:t<0?t<-72?main(_,t,
    "@n'+,#'/*{}w+/w#cdnr/+,{}r/*de}+,/*{*+,/w{%+,/w#q#n+,/#{l,+,/n{n+,/+#n+,/#\
    ;#q#n+,/+k#;*+,/'r :'d*'3,}{w+K w'K:'+}e#';dq#'l \
    q#'+d'K#!/+k#;q#'r}eKK#}w'r}eKK{nl]'/#;#q#n'){)#}w'){){nl]'/+#n';d}rw' i;# \
    ){nl]!/n{n#'; r{#w'r nc{nl]'/#{l,+'K {rw' iK{;[{nl]'/w#q#n'wk nw' \
    iwk{KK{nl]!/w{%'l##w#' i; :{nl]'/*{q#'ld;r'}{nlwb!/*de}'c \
    ;;{nl'-{}rw]'/+,}##'*}#nc,',#nw]'/+kd'+e}+;#'rdq#w! nr'/ ') }+}{rl#'{n' ')# \
    }'+}##(!!/")
    :t<-50?_==*a?putchar(31[a]):main(-65,_,a+1):main((*a=='/')+t,_,a+1)
      :0<t?main(2,2,"%s"):*a=='/'||main(0,main(-61,*a,
    "!ek;dc i@bK'(q)-[w]*%n+r3#l,{}:\nuwloca-O;m .vpbks,fxntdCeghiry"),a+1);}
    Recursive algorithms need a way to terminate with certainty before consuming all the stack space! If you had main call main until it played 40 games then the program complained it was tired and wouldn't play any more and then terminated I still would have advised you to use a loop to avoid unnecessary recursion. At least your program wouldn't core dump for that reason!

    Maybe your professor/teacher/teaching assistant is too busy/stupid to discover that your program will crash when played by persistent, tireless opponents. The loop works like this:
    Code:
    do play_game(); while(more_input());
    Not at all the same as
    Code:
    int main() {
      play_game();
      if (play_again())
        main();
      return 0;
    }
    Last edited by b49P23TIvg; December 17th, 2013 at 09:50 PM.
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo