Thread: How to Make This code more efficient

  1. #1
    Registered User
    Join Date
    Jan 2010
    Posts
    103

    How to Make This code more efficient

    Hello, I'm working on a Connect 4 evaluation function, and this is the only code we have left. This code WORKS just fine, however, I am wondering if there is a more efficient way to write this code.
    Basically, this code takes in a game board that is 6x7 and when you insert a piece in a column, it look at the surrounding pieces and adds points accordingly to pieces it detects around it.

    However, this can create a whole bunch of out of bounds errors so we decided to specifically look at all 9 scenarios, 4 corners, 4 sides, and if its in the middle

    Is there a more efficient way to do this code? because it is ridiculously long and clustered.

    Don't be intimidated by the code. It LOOKS extremely long, but it's just a bunch of if/else if statements that do the same thing for each position

    Code:
    int evaluate(struct connect4 game, int row, int col) {
        int points = 0, baseVals[NUM_COLS] = {100, 300, 400, 500, 400, 300, 100};
        points += baseVals[col];
        
        if (row == 5 && col == 0) {
            if (game.board[4][1] == game.whoseTurn)
                points += DIAG_WIN;
            else if (game.board[4][1] == other(game.whoseTurn))
                points += DIAG_BLOCK;
            
            if (game.board[5][1] == game.whoseTurn)
                points += ROW_WIN;
            else if (game.board[5][1] == other(game.whoseTurn))
                points += ROW_BLOCK;
        }
        else if (row == 5 && col == 6) {
            if (game.board[4][5] == game.whoseTurn)
                points += DIAG_WIN;
            else if (game.board[4][5] == other(game.whoseTurn))
                points += DIAG_BLOCK;
            
            if (game.board[5][5] == game.whoseTurn)
                points += ROW_WIN;
            else if (game.board[5][5] == other(game.whoseTurn))
                points += ROW_BLOCK;
        }
        else if (row == 0 && col == 0) {
            if (game.board[1][1] == game.whoseTurn)
                points += DIAG_WIN;
            else if (game.board[1][1] == other(game.whoseTurn))
                points += DIAG_BLOCK;
            
            if (game.board[0][1] == game.whoseTurn)
                points += ROW_WIN;
            else if (game.board[0][1] == other(game.whoseTurn))
                points += ROW_BLOCK;
                
            if (game.board[1][0] == game.whoseTurn)
                points += COL_WIN;
            else if (game.board[1][0] == other(game.whoseTurn))
                points += COL_BLOCK;
        }
        else if (row == 0 && col == 6) {
            if (game.board[1][5] == game.whoseTurn)
                points += DIAG_WIN;
            else if (game.board[1][5] == other(game.whoseTurn))
                points += DIAG_BLOCK;
            
            if (game.board[0][5] == game.whoseTurn)
                points += ROW_WIN;
            else if (game.board[0][5] == other(game.whoseTurn))
                points += ROW_BLOCK;
                
            if (game.board[1][6] == game.whoseTurn)
                points += COL_WIN;
            else if (game.board[1][6] == other(game.whoseTurn))
                points += COL_BLOCK;
        }
        else if (row < 5 && row > 0 && col == 0) {
            if (game.board[row-1][col+1] == game.whoseTurn)
                points += DIAG_WIN;
            else if (game.board[row-1][col+1] == other(game.whoseTurn))
                points += DIAG_BLOCK;
                
            if (game.board[row+1][col+1] == game.whoseTurn)
                points += DIAG_WIN;
            else if (game.board[row+1][col+1] == other(game.whoseTurn))
                points += DIAG_BLOCK;
            
            if (game.board[row][col+1] == game.whoseTurn)
                points += ROW_WIN;
            else if (game.board[row][col+1] == other(game.whoseTurn))
                points += ROW_BLOCK;
                
            if (game.board[row+1][col] == game.whoseTurn)
                points += COL_WIN;
            else if (game.board[row+1][col] == other(game.whoseTurn))
                points += COL_BLOCK;
        }
        else if (row < 5 && row > 0 && col == 6) {
            if (game.board[row-1][col-1] == game.whoseTurn)
                points += DIAG_WIN;
            else if (game.board[row-1][col-1] == other(game.whoseTurn))
                points += DIAG_BLOCK;
                
            if (game.board[row+1][col-1] == game.whoseTurn)
                points += DIAG_WIN;
            else if (game.board[row+1][col-1] == other(game.whoseTurn))
                points += DIAG_BLOCK;
            
            if (game.board[row-1][col] == game.whoseTurn)
                points += ROW_WIN;
            else if (game.board[row-1][col] == other(game.whoseTurn))
                points += ROW_BLOCK;
                
            if (game.board[row+1][col] == game.whoseTurn)
                points += COL_WIN;
            else if (game.board[row+1][col] == other(game.whoseTurn))
                points += COL_BLOCK;
        }
        else if (col < 6 && col > 0 && row == 0) {
            if (game.board[row-1][col+1] == game.whoseTurn)
                points += DIAG_WIN;
            else if (game.board[row-1][col+1] == other(game.whoseTurn))
                points += DIAG_BLOCK;
                
            if (game.board[row+1][col+1] == game.whoseTurn)
                points += DIAG_WIN;
            else if (game.board[row+1][col+1] == other(game.whoseTurn))
                points += DIAG_BLOCK;
            
            if (game.board[row][col-1] == game.whoseTurn)
                points += ROW_WIN;
            else if (game.board[row][col-1] == other(game.whoseTurn))
                points += ROW_BLOCK;
                
            if (game.board[row][col+1] == game.whoseTurn)
                points += ROW_WIN;
            else if (game.board[row][col+1] == other(game.whoseTurn))
                points += ROW_BLOCK;
                
            if (game.board[row+1][col] == game.whoseTurn)
                points += COL_WIN;
            else if (game.board[row+1][col] == other(game.whoseTurn))
                points += COL_BLOCK;
        }
        else if (col < 6 && col > 0 && row == 5) {
            if (game.board[row-1][col-1] == game.whoseTurn)
                points += DIAG_WIN;
            else if (game.board[row-1][col-1] == other(game.whoseTurn))
                points += DIAG_BLOCK;
                
            if (game.board[row+1][col-1] == game.whoseTurn)
                points += DIAG_WIN;
            else if (game.board[row+1][col-1] == other(game.whoseTurn))
                points += DIAG_BLOCK;
            
            if (game.board[row][col-1] == game.whoseTurn)
                points += ROW_WIN;
            else if (game.board[row][col-1] == other(game.whoseTurn))
                points += ROW_BLOCK;
                
            if (game.board[row][col+1] == game.whoseTurn)
                points += ROW_WIN;
            else if (game.board[row][col+1] == other(game.whoseTurn))
                points += ROW_BLOCK;
        }
        else {
            if (game.board[row-1][col-1] == game.whoseTurn)
                points += DIAG_WIN;
            else if (game.board[row-1][col-1] == other(game.whoseTurn))
                points += DIAG_BLOCK;
                
            if (game.board[row+1][col-1] == game.whoseTurn)
                points += DIAG_WIN;
            else if (game.board[row+1][col-1] == other(game.whoseTurn))
                points += DIAG_BLOCK;
                
            if (game.board[row-1][col+1] == game.whoseTurn)
                points += DIAG_WIN;
            else if (game.board[row-1][col+1] == other(game.whoseTurn))
                points += DIAG_BLOCK;
                
            if (game.board[row+1][col+1] == game.whoseTurn)
                points += DIAG_WIN;
            else if (game.board[row+1][col+1] == other(game.whoseTurn))
                points += DIAG_BLOCK;
            
            if (game.board[row][col-1] == game.whoseTurn)
                points += ROW_WIN;
            else if (game.board[row][col-1] == other(game.whoseTurn))
                points += ROW_BLOCK;
                
            if (game.board[row][col+1] == game.whoseTurn)
                points += ROW_WIN;
            else if (game.board[row][col+1] == other(game.whoseTurn))
                points += ROW_BLOCK;
                
            if (game.board[row+1][col] == game.whoseTurn)
                points += COL_WIN;
            else if (game.board[row+1][col] == other(game.whoseTurn))
                points += COL_BLOCK;
        }
        
        return points;
    }

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    int insert( board, column, color )
    {
        if( !full( board, column ) )
        {
            int row, score = 0, left, right;
            
            for( row = bottom; row < top; row++or-- )
            {
                if( colorof( board, column, row ) == empty )
                {
                    set( board, column, row, color )
                    break;
                }
            }
    
            score = whatever for this column
            for( left = column - 1; column > left_bound; left-- )
                if( colorof( board, left, row ) == color )
                {
                    score += whatever for whatever;
                }
                else break;
    
            for( right = column + 1; column < right_bound; right++ )
                if( colorof( board, right, row ) == color )
                {
                    score += whatever for whatever;
                }
                else break;
    
            return score;
        }
        return -1;
    }
    This will take some work on your part, but it's easier to understand. Assuming of course, that this is actually what you're trying to do.


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User
    Join Date
    Jan 2010
    Posts
    103
    hmm, im not quite sure what left and right does in your program

    and ohhh umm, hmm, let me try to explain better. If it blocks/adds to a diaganol, column, or row it adds in a different number.

    Basically all it does is at the moment it looks at the pieces surrounding the piece and adds 75 points if its the same piece, 50 points if its an opponent's piece, 0 if it's empty. thats why i have so many if statements, to avoid stepping on out-of-bounds

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    So basically you're checking each of the eight directions and what piece is there. There's no need to do that differently in different places of the board. Just make sure, in your (say) down-and-to-the-left part, that if you would go over the line you don't do anything at all. That's not really that hard, doing nothing at all.

    (And if this is for a new move then the check for "up" is meaningless, unless you're playing in some strange gravity situation.)

  5. #5
    Registered User
    Join Date
    Jan 2010
    Posts
    103
    hmm, yes, we dont check upwards but i think we may have for the bottom two corners. That will be deleted if I find it there, but yes we don't check upwards in the middle, etc.

    And yes, this is exactly what our code does, but we don't know how to specify, for example, if you are on the bottom-most row, you dont try to check another row down. We do this with a lot of if/else if statements.

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    What's wrong with
    Code:
    if (row == 0)
      //hey we're on the bottom row
    (I mean, of course, that you would only just skip the downward check -- you wouldn't do a whole different set of checks.)

  7. #7
    Registered User
    Join Date
    Jan 2010
    Posts
    103
    hmm yes, i see, but i cant see a way to phrase it...T_T ahhh lolol Q_Q hmm...

    i think i can do something like this...ughhh lol :P i mean, does it matter, since it works?

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    The only way you can skip bounds checking -- which doesn't actually make anything more efficient -- is to pad the board +3 in all directions, and recenter the board. But that doesn't really save anything, except it stops you having to bounds check. But the cost of that is taht you have to add 3 to everything when you enter pieces. So the extra addition is going to negate anything you'd have gained by checking the bounds in the first place.

    Just use loops and sum up the score in each direction. If anything is equal to or greater than four, you win:
    Code:
    place( board, column, color )
    {
        row = firstempty( board, column )
        if( row < full )
        {
            use( board, column, row, color )
            return diagultolr( board, column, row, color ) > 3
            ||     diaglltour( board, column, row, color ) > 3
            ||     across(     board, column, row, color ) > 3
            ||     down(       board, column, row, color ) > 3
        }
        return -1
    }
    Each check is simple, you just loop adjusting the row and/or column count and incrementing 'score' as long as the colors match.

    Quzah.
    Hope is the first step on the road to disappointment.

  9. #9
    Registered User
    Join Date
    Jan 2010
    Posts
    103
    hmm ahh yes your logic makes a lot of sense now!! haha thnaks, i will see if i can duplicate it

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Soulzityr View Post
    Don't be intimidated by the code. It LOOKS extremely long, but it's just a bunch of if/else if statements that do the same thing for each position
    On the contrary; be afraid of this code, be very afraid! I shall attempt to make a point...

    Repetition it evil. Repetition it evil. Repetition it evil. Repetition it evil. Repetition it evil. Repetition it evil. Repetition it evil. Repetition it evil. Repetition it evil. Repetition it evil. Repetition it evil. Repetition it evil. Repetition it evil. Repetition it evil. Repetition it evil. Repetition it evil. Repetition it evil. Repetition it evil. Repetition it evil. Repetition it evil. Repetition it evil. Repetition it evil. Repetition it evil. Repetition it evil. Repetition it evil. Repetition it evil. Repetition it evil. Repetition it evil. Repetition it evil. Repetition it evil.

    Aw crap, I meant to write "is" rather than "it"...
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Edit stack code to make queue
    By mikeman in forum C++ Programming
    Replies: 1
    Last Post: 02-15-2010, 09:49 AM
  2. making programms faster
    By deian in forum C Programming
    Replies: 23
    Last Post: 10-09-2004, 12:19 AM
  3. How efficient is this code?
    By Morgan in forum C Programming
    Replies: 6
    Last Post: 05-23-2003, 04:47 AM
  4. How do I write more efficient code?
    By minesweeper in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 11:08 AM
  5. more efficient code
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 10-11-2001, 01:56 PM