Thread: 5x5 Tic Tac Toe

  1. #1
    Registered User
    Join Date
    Mar 2007
    Posts
    32

    5x5 Tic Tac Toe

    http://rafb.net/p/N0Q9yA57.html

    I created this code, which I modified from the 3x3 version. However, whenever I enter my first move, I sit there and wait for almost 10 minutes while the program processes until I terminate it because the computer has not determined a move yet. The program uses alpha beta pruning, and for the 3x3 board it finds the computers move instantly. However, for the 5x5 board I just terminate it after awhile because it fails to find a move. With alpha beta pruning should it just take this long for a 5x5 board, or am I missing something in my code?

    Thanks.

  2. #2
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341
    Code:
    t.chooseMove( TicTacToe::COMPUTER, bestRow, bestCol );
    This doesn't match with the function definition
    Code:
    int TicTacToe::chooseMove( Side s, int & bestRow, int & bestColumn,
                               int alpha, int beta, int depth )
    Last edited by Brad0407; 03-25-2007 at 09:11 PM.
    Don't quote me on that... ...seriously

  3. #3
    Registered User
    Join Date
    Mar 2007
    Posts
    32
    Hmm, I don't get an error anywhere in my program so I'm not sure if it still lets me call this function with the syntax I have?

  4. #4
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341
    It shouldn't let you compile. You might want to change some settings on your compiler.
    Don't quote me on that... ...seriously

  5. #5
    pwns nooblars
    Join Date
    Oct 2005
    Location
    Portland, Or
    Posts
    1,094
    -Wall and -pedantic come to mind

  6. #6
    Registered User
    Join Date
    Dec 2005
    Location
    Colchester, Essex, United Kingdom.
    Posts
    31
    If that still doesn't work, please post your alphabeta function and any related code (i.e. any extra functions you use to generate, do, or undo moves). It will most likely be a very small problem in the way you adapted the 3x3 to work for a 5x5.
    Last edited by tomcant; 03-26-2007 at 09:53 AM.

  7. #7
    Registered User
    Join Date
    Mar 2007
    Posts
    32

  8. #8
    Registered User
    Join Date
    Dec 2005
    Location
    Colchester, Essex, United Kingdom.
    Posts
    31
    The first problem I can see is that you never call chooseMove() with a specified depth, other than when you call chooseMove() from within itself. When you ask the program for a best move, you need to specify a depth to search until. I would call the chooseMove() function with a depth of 4 or so to begin with. Then, if that works the way it should, increase it.

    Another (major) problem is that on each recursive call to chooseMove(), you pass `depth + 1' as the new depth parameter. This should be `depth - 1' if you ever plan for your program to reach a result.

    Fix those problems, then post back to let us know how it went.

  9. #9
    Registered User
    Join Date
    Mar 2007
    Posts
    32
    What should I pass in the values of alpha and beta as?

  10. #10
    Registered User
    Join Date
    Dec 2005
    Location
    Colchester, Essex, United Kingdom.
    Posts
    31
    When searching for a best move, alpha and beta should take initial values of -(LARGE_NUMBER) and +(LARGE_NUMBER), respectively. I'v written a few alphabeta searches before and what I like to do is define some constant in my code to represent this large number as you'll find that it can crop up in quite a few places. Something like: const int INFINITY = +1000000;, though for Tic-Tac-Toe it really doesn't need to be so big, +100 would do.

    The initial call to your alphabeta function should look like this then: (having already defined INFINITY and maxDepth)
    Code:
    TicTacToe::chooseMove(TicTacToe::COMPUTER, bestRow, bestCol, -INFINITY, +INFINITY, maxDepth);
    As I said in my previous post, let maxDepth be something relatively small for the moment, then increase it when you get the searcher working.

    That's all for the moment, I think.

  11. #11
    Registered User
    Join Date
    Mar 2007
    Posts
    32
    http://rafb.net/p/33KwCJ45.html

    Ok, so I made those changes and this is the code I have now. So I tried running it and it was still taking forever till the point where I decide to terminate the program....

  12. #12
    Registered User
    Join Date
    Dec 2005
    Location
    Colchester, Essex, United Kingdom.
    Posts
    31
    Ok, the next thing to do is to take each element of the program (i.e. the isAWin(), playMove(), boardIsFull() and positionValue() functions), and test each of them individually. Having had another look at the code, I see a problem here: (in the isAWin() function)
    Code:
    for( row = 0; row < 5; row++ )
        {
            if(board[row][0]==s && board[row][1]==s && board[row][2]==s && board[row][3]==s )
             {
              return true;
             }
            else if (board[row][1]==s && board[row][2]==s && board[row][3]==s && board[row][4]==s)
             {
              return true;
             }
           return false;
        }
    After checking the first row (or column, in the second for loop), you are assuming that there cannot be a 4-in-a-row further down the board, and you're returning false. This is surely wrong...?

  13. #13
    Registered User
    Join Date
    Dec 2005
    Location
    Colchester, Essex, United Kingdom.
    Posts
    31
    @tallguy: Could you let me know if that worked?

  14. #14
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Was that supposed to be 's' instead of just plain s?
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  15. #15
    Registered User
    Join Date
    Mar 2007
    Posts
    32
    Ok I fixed it and it still takes too long. Maybe it has something to do with the size of the table depth? Possibly making it larger?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help me with my simple Tic tac toe prog
    By maybnxtseasn in forum C Programming
    Replies: 2
    Last Post: 04-04-2009, 06:25 PM
  2. Tic Tac Toe... so close...
    By SlayerBlade in forum C Programming
    Replies: 14
    Last Post: 10-10-2005, 08:58 PM
  3. Help with Tic Tac Toe game
    By snef73 in forum C++ Programming
    Replies: 1
    Last Post: 04-25-2003, 08:33 AM
  4. look-ahead, recommend function for tic tac toe 5x5
    By portos69 in forum C Programming
    Replies: 2
    Last Post: 11-21-2002, 07:42 PM
  5. Need some help with a basic tic tac toe game
    By darkshadow in forum C Programming
    Replies: 1
    Last Post: 05-12-2002, 04:21 PM