Thread: Is there a bug in this part of my algorithm for connect 4?

  1. #1
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020

    Is there a bug in this part of my algorithm for connect 4?

    Hi,

    The following is a part of my algorithm for making a winning move in a game of connect four. However, it doen't really work. It can check make win moves if the line is a diagonal one, but not vertical or horizontal ones. I'd already spent some hours on it, but still can't figure out where it went wrong. I've already written a driver program to test the function for those who are willing to help me.

    Thnx in advance

    Code:
    #include <stdio.h>
    #include <conio.c>
    
    char board[ 7 ][ 6 ] = { {' ', ' ', ' ', 'X', 'X', 'X'   },
                             {' ', ' ', ' ', ' ', ' ', ' '   },
                             {' ', ' ', ' ', ' ', ' ', ' '   },
                             {' ', ' ', ' ', ' ', ' ', ' '   },
                             {' ', ' ', ' ', ' ', ' ', ' '   },
                             {' ', ' ', ' ', ' ', ' ', ' '   },
                             {' ', ' ', ' ', ' ', ' ', ' '   } };
    
    int makeWinMove( char currentPlayer, int mode )
    {
       int row;
       int col;
    
       /* check vertically */
       for ( col = 0; col < 7; col++ )
          for ( row = 5; row < 2; row-- ) {
    
             if ( board[ col ][ row ] == currentPlayer &&
                  board[ col ][ row - 1 ] == currentPlayer &&
                  board[ col ][ row - 2 ] == currentPlayer &&
                  board[ col ][ row - 3 ] != 'X' &&
                  board[ col ][ row - 3 ] != 'O' ) {
    
                  return 1; /* indicating success */
             }
    
          }
    
       /* check horizontally */
       for ( row = 0; row < 6; row++ )
          for ( col = 0; col < 4; col++ ) {
             if ( board[ col ][ row ] == currentPlayer &&
                  board[ col + 1 ][ row ] == currentPlayer &&
                  board[ col + 2 ][ row ] == currentPlayer &&
                  board[ col + 3 ][ row ] != 'X' &&
                  board[ col + 3 ][ row ] != 'O' &&
                  ( board[ col + 3 ][ row + 1 ] != ' ' || row == 6 )) {
    
                  return 1;
             }
             if ( board[ col ][ row ] == currentPlayer &&
                  board[ col + 1 ][ row ] == currentPlayer &&
                  board[ col + 3 ][ row ] == currentPlayer &&
                  board[ col + 2 ][ row ] != 'X' &&
                  board[ col + 2 ][ row ] != 'O' &&
                  ( board[ col + 2 ][ row + 1 ] != ' ' || row == 6 )) {
    
                  return 1;
             }
             if ( board[ col ][ row ] == currentPlayer &&
                  board[ col + 3 ][ row ] == currentPlayer &&
                  board[ col + 2 ][ row ] == currentPlayer &&
                  board[ col + 1 ][ row ] != 'X' &&
                  board[ col + 1 ][ row ] != 'O' &&
                  ( board[ col + 1 ][ row + 1 ] != ' ' || row == 6 )) {
    
                  return 1;
             }
             if ( board[ col + 3 ][ row ] == currentPlayer &&
                  board[ col + 1 ][ row ] == currentPlayer &&
                  board[ col + 2 ][ row ] == currentPlayer &&
                  board[ col ][ row ] != 'X' &&
                  board[ col ][ row ] != 'O' &&
                  ( board[ col ][ row + 1 ] != ' ' || row == 6 )) {
    
                  return 1;
             }
          }
    
       /* check diagonally (NE) */
       for ( row = 5; row > 2; row-- )
          for ( col = 0; col < 4; col++ ) {
             if ( board[ col ][ row ] == currentPlayer &&
                  board[ col + 1 ][ row - 1 ] == currentPlayer &&
                  board[ col + 2 ][ row - 2 ] == currentPlayer &&
                  board[ col + 3 ][ row - 3 ] != 'X' &&
                  board[ col + 3 ][ row - 3 ] != 'O' &&
                  ( board[ col + 3 ][ row - 3 + 1 ] != ' ' || row == 5 )) {
    
                  return 1;
             }
             if ( board[ col ][ row ] == currentPlayer &&
                  board[ col + 1 ][ row - 1 ] == currentPlayer &&
                  board[ col + 3 ][ row - 3 ] == currentPlayer &&
                  board[ col + 2 ][ row - 2 ] != 'X' &&
                  board[ col + 2 ][ row - 2 ] != 'O' &&
                  ( board[ col + 2 ][ row - 2 + 1 ] != ' ' || row == 5 )) {
    
                  return 1;
             }
             if ( board[ col ][ row ] == currentPlayer &&
                  board[ col + 3 ][ row - 3 ] == currentPlayer &&
                  board[ col + 2 ][ row - 2 ] == currentPlayer &&
                  board[ col + 1 ][ row - 1 ] != 'X' &&
                  board[ col + 1 ][ row - 1 ] != 'O' &&
                  ( board[ col + 1 ][ row - 1 + 1 ] != ' ' || row == 5 )) {
    
                  return 1;
             }
             if ( board[ col + 3 ][ row - 3 ] == currentPlayer &&
                  board[ col + 1 ][ row - 1 ] == currentPlayer &&
                  board[ col + 2 ][ row - 2 ] == currentPlayer &&
                  board[ col ][ row ] != 'X' &&
                  board[ col ][ row ] != 'O' &&
                  ( board[ col ][ row + 1 ] != ' ' || row == 5 )) {
    
                  return 1;
             }
    
          }
    
       /* check diagonally (NW) */
       for ( row = 5; row > 2; row-- )
          for ( col = 6; col < 2; col-- ) {
             if ( board[ col ][ row ] == currentPlayer &&
                  board[ col - 1 ][ row - 1 ] == currentPlayer &&
                  board[ col - 2 ][ row - 2 ] == currentPlayer &&
                  board[ col - 3 ][ row - 3 ] != 'X' &&
                  board[ col - 3 ][ row - 3 ] != 'O' &&
                  ( board[ col - 3 ][ row - 3 + 1 ] != ' ' || row == 5 )) {
    
                  return 1;
             }
             if ( board[ col ][ row ] == currentPlayer &&
                  board[ col - 1 ][ row - 1 ] == currentPlayer &&
                  board[ col - 3 ][ row - 3 ] == currentPlayer &&
                  board[ col - 2 ][ row - 2 ] != 'X' &&
                  board[ col - 2 ][ row - 2 ] != 'O' &&
                  ( board[ col - 2 ][ row - 2 + 1 ] != ' ' || row == 5 )) {
    
                  return 1;
             }
             if ( board[ col ][ row ] == currentPlayer &&
                  board[ col - 3 ][ row - 3 ] == currentPlayer &&
                  board[ col - 2 ][ row - 2 ] == currentPlayer &&
                  board[ col - 1 ][ row - 1 ] != 'X' &&
                  board[ col - 1 ][ row - 1 ] != 'O' &&
                  ( board[ col - 1 ][ row - 1 + 1 ] != ' ' || row == 5 )) {
    
                  return 1;
             }
             if ( board[ col - 3 ][ row - 3 ] == currentPlayer &&
                  board[ col - 1 ][ row - 1 ] == currentPlayer &&
                  board[ col - 2 ][ row - 2 ] == currentPlayer &&
                  board[ col ][ row ] != 'X' &&
                  board[ col ][ row ] != 'O' &&
                  ( board[ col ][ row + 1 ] != ' ' || row == 5 )) {
    
                  return 1;
             }
          }
    
       return 0;
    }
    
    int main()
    {
       int result;
    
       if ( ( result = makeWinMove( 'X', 0 ) ) == 1 )
          printf( "Made a win move...\n" );
    
       system("PAUSE");
       return 0;
    }
    Last edited by Nutshell; 04-26-2002 at 07:26 AM.

  2. #2
    Has a Masters in B.S.
    Join Date
    Aug 2001
    Posts
    2,263
    yeah, um

    for ( col = 0; col < 7; col++ )
    for ( row = 5; row < 2; row-- )

    will only loop once per 'col', since 'row' will never be less than 2

    if i can i'll try and look through again if i get time, heres some advice in the mean time,
    rethink the algorithm reconceptualize it and think on how your going to search it, then rewrite it again from scratch and see what you come up with. this is how i solve a lot of small code bugs, rewrite that section.(and yes i know why i do this in the first place)

    one other thing

    char board[ 7 ][ 6 ] = { {' ', ' ', ' ', 'X', 'X', 'X' },

    doesn't contain 4 'X''s...

    and how can i win if
    board[ col + 3 ][ row ] != 'X' &&

    my fourth piece cannot be counted.
    ADVISORY: This users posts are rated CP-MA, for Mature Audiences only.

  3. #3
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    I would suggest doing a loop instead of checking every element by itself. This makes the code shorter and easier to read.

    Start in the point where you last put your X.
    Make a loop in all 8 directions and calculate the number of X's until you reach an O or an empty tile.
    Sum the number of X's in Left+Right, Top+Bottom, NW+SE & NE+SW.
    If any of these numbers are greater or equal than 5 (or whatever number you want) then you've won.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  4. #4
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    Hi,

    Thnx for replying. You just helped found the bug. Although there are still some i suppose. i see that you didn't notice the function i posted is not to check if someone wins, it's for the computer to make a win move if possible, that means, to place a piece and win.

    I'll post again if i have any further problems. Thnx again.

    GOD THAT LIL '<' !!!

  5. #5
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020

    makeBlockMove problem

    I solved the problem for my makeWInMove function. However, there's my makeBlockMove function that is having trouble again. It's suppose to prevent the opponent from winning. Say if i've got
    Code:
    0 1 2 3 4 5 6
    
    - - - - - - - 0 
    - - - - - - - 1
    - - - - - - - 2
    - - - - O - - 3
    - - - O X - - 4
    - - O O X - - 5
    Is drops a piece in the second last column. I figure out that it thinks it has to place a piece in 6th col in order to block. But it forgot that there has to be a piece at col 5, row 3 in order to place another piece on top and win. But i already made sure i included the coding in the function. Just can't figure out the cause. THe code is not that short, the structures are the same. Pls give a hand.

    Thnx in advance
    Code:
    int makeBlockMove( char currentPlayer )
    {
       char enemyPiece;
       int row;
       int col;
    
       if ( currentPlayer == 'X' )
          enemyPiece = 'O';
       if ( currentPlayer == 'O' )
          enemyPiece = 'X';
    
       /* check vertically */
       for ( col = 0; col < 7; col++ )
          for ( row = 5; row > 2; row-- ) {
             if ( board[ col ][ row ] == enemyPiece &&
                  board[ col ][ row - 1 ] == enemyPiece &&
                  board[ col ][ row - 2 ] == enemyPiece &&
                  board[ col ][ row - 3 ] != 'X' &&
                  board[ col ][ row - 3 ] != 'O' ) {
                  dropPiece( col, currentPlayer, 0 );
                  gotoxy( 1, 24 );
                  printf( "made a block move...vertically\n" );
                  return 1; /* indicating success */
             }
    
          }
    
       /* check horizontally */
       for ( row = 0; row < 6; row++ )
          for ( col = 0; col < 4; col++ ) {
             if ( board[ col ][ row ] == enemyPiece &&
                  board[ col + 1 ][ row ] == enemyPiece &&
                  board[ col + 2 ][ row ] == enemyPiece &&
                  board[ col + 3 ][ row ] != 'X' &&
                  board[ col + 3 ][ row ] != 'O' &&
                  ( board[ col + 3 ][ row + 1 ] != ' ' || row == 5 ) ) {
                  dropPiece( col + 3, currentPlayer, 0 );
                  gotoxy( 1, 24 );
                  printf( "made a block move...horizontally\n" );
                  return 1;
             }
             if ( board[ col ][ row ] == enemyPiece &&
                  board[ col + 1 ][ row ] == enemyPiece &&
                  board[ col + 3 ][ row ] == enemyPiece &&
                  board[ col + 2 ][ row ] != 'X' &&
                  board[ col + 2 ][ row ] != 'O' &&
                  ( board[ col + 2 ][ row + 1 ] != ' ' || row == 5 ) ) {
                  dropPiece( col + 2, currentPlayer, 0 );
                  gotoxy( 1, 24 );
                  printf( "made a block move...horizontally\n" );
                  return 1;
             }
             if ( board[ col ][ row ] == enemyPiece &&
                  board[ col + 3 ][ row ] == enemyPiece &&
                  board[ col + 2 ][ row ] == enemyPiece &&
                  board[ col + 1 ][ row ] != 'X' &&
                  board[ col + 1 ][ row ] != 'O' &&
                  ( board[ col + 1 ][ row + 1 ] != ' ' || row == 5 ) ) {
                  dropPiece( col + 1, currentPlayer, 0 );
                  gotoxy( 1, 24 );
                  printf( "made a block move...horizontally\n" );
                  return 1;
             }
             if ( board[ col + 3 ][ row ] == enemyPiece &&
                  board[ col + 1 ][ row ] == enemyPiece &&
                  board[ col + 2 ][ row ] == enemyPiece &&
                  board[ col ][ row ] != 'X' &&
                  board[ col ][ row ] != 'O' &&
                  ( board[ col ][ row + 1 ] != ' ' || row == 5 ) ) {
    
                  dropPiece( col, currentPlayer, 0 );
                  gotoxy( 1, 24 );
                  printf( "made a block move...horizontally\n" );
                  return 1;
             }
          }
    
       /* check diagonally (NE) */
       for ( row = 5; row > 2; row-- )
          for ( col = 0; col < 4; col++ ) {
             if ( board[ col ][ row ] == enemyPiece &&
                  board[ col + 1 ][ row - 1 ] == enemyPiece &&
                  board[ col + 2 ][ row - 2 ] == enemyPiece &&
                  board[ col + 3 ][ row - 3 ] != 'X' &&
                  board[ col + 3 ][ row - 3 ] != 'O' &&
                  board[ col + 3 ][ row - 3 + 1 ] != ' ' ) {
                  dropPiece( col + 3, currentPlayer, 0 );
                  gotoxy( 1, 24 );
                  printf( "made a block move...NE\n" );
                  return 1;
             }
             if ( board[ col ][ row ] == enemyPiece &&
                  board[ col + 1 ][ row - 1 ] == enemyPiece &&
                  board[ col + 3 ][ row - 3 ] == enemyPiece &&
                  board[ col + 2 ][ row - 2 ] != 'X' &&
                  board[ col + 2 ][ row - 2 ] != 'O' &&
                  board[ col + 2 ][ row - 2 + 1 ] != ' ' ) {
                  dropPiece( col + 2, currentPlayer, 0 );
                  gotoxy( 1, 24 );
                  printf( "made a block move...NE\n" );
                  return 1;
             }
             if ( board[ col ][ row ] == enemyPiece &&
                  board[ col + 3 ][ row - 3 ] == enemyPiece &&
                  board[ col + 2 ][ row - 2 ] == enemyPiece &&
                  board[ col + 1 ][ row - 1 ] != 'X' &&
                  board[ col + 1 ][ row - 1 ] != 'O' &&
                  board[ col + 1 ][ row - 1 + 1 ] != ' ' ) {
                  dropPiece( col + 1, currentPlayer, 0 );
                  gotoxy( 1, 24 );
                  printf( "made a block move...NE\n" );
                  return 1;
             }
             if ( board[ col + 3 ][ row - 3 ] == enemyPiece &&
                  board[ col + 1 ][ row - 1 ] == enemyPiece &&
                  board[ col + 2 ][ row - 2 ] == enemyPiece &&
                  board[ col ][ row ] != 'X' &&
                  board[ col ][ row ] != 'O' &&
                  board[ col ][ row + 1 ] != ' ' ) {
                  dropPiece( col, currentPlayer, 0 );
                  gotoxy( 1, 24 );
                  printf( "made a block move...NE\n" );
                  return 1;
             }
          }
    
       /* check diagonally (NW) */
       for ( row = 5; row > 2; row-- )
          for ( col = 6; col > 2; col-- ) {
             if ( board[ col ][ row ] == enemyPiece &&
                  board[ col - 1 ][ row - 1 ] == enemyPiece &&
                  board[ col - 2 ][ row - 2 ] == enemyPiece &&
                  board[ col - 3 ][ row - 3 ] != 'X' &&
                  board[ col - 3 ][ row - 3 ] != 'O' &&
                  board[ col - 3 ][ row - 3 + 1 ] == ' ' ) {
                  dropPiece( col - 3, currentPlayer, 0 );
                  gotoxy( 1, 24 );
                  printf( "made a block move...NW\n" );
                  return 1;
             }
             if ( board[ col ][ row ] == enemyPiece &&
                  board[ col - 1 ][ row - 1 ] == enemyPiece &&
                  board[ col - 3 ][ row - 3 ] == enemyPiece &&
                  board[ col - 2 ][ row - 2 ] != 'X' &&
                  board[ col - 2 ][ row - 2 ] != 'O' &&
                  board[ col - 2 ][ row - 2 + 1 ] != ' ' ) {
                  dropPiece( col - 2, currentPlayer, 0 );
                  gotoxy( 1, 24 );
                  printf( "made a block move...NW\n" );
                  return 1;
             }
             if ( board[ col ][ row ] == enemyPiece &&
                  board[ col - 3 ][ row - 3 ] == enemyPiece &&
                  board[ col - 2 ][ row - 2 ] == enemyPiece &&
                  board[ col - 1 ][ row - 1 ] != 'X' &&
                  board[ col - 1 ][ row - 1 ] != 'O' &&
                  board[ col - 1 ][ row - 1 + 1 ] != ' ' ) {
                  dropPiece( col - 1, currentPlayer, 0 );
                  gotoxy( 1, 24 );
                  printf( "made a block move...NW\n" );
                  return 1;
             }
             if ( board[ col - 3 ][ row - 3 ] == enemyPiece &&
                  board[ col - 1 ][ row - 1 ] == enemyPiece &&
                  board[ col - 2 ][ row - 2 ] == enemyPiece &&
                  board[ col ][ row ] != 'X' &&
                  board[ col ][ row ] != 'O' &&
                  ( board[ col ][ row + 1 ] != ' ' || row == 5 )) {
                  dropPiece( col, currentPlayer, 0 );
                  gotoxy( 1, 24 );
                  printf( "made a block move...NW\n" );
                  return 1;
             }
           }
    
       return 0;
    }

  6. #6
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    I solved the problem now!!!!

    I figure out that i cannot do the following comparison, it will not work:
    Code:
    board[ col ][ row ] != ' '
    I can't compare if it is a space, but i dont' know why can't i.

    Anyway i'll finish the connect 4 game tonite. Hope i received nice comments when i post it.

    Thnx

  7. #7
    Has a Masters in B.S.
    Join Date
    Aug 2001
    Posts
    2,263
    >I can't compare if it is a space, but i dont' know why can't i.

    im not sure not haveing the opportunity to read through the code, but my uneducated(meaning unresearched) guess would be that since you are testing for a space to put it in it will skip it?

    >Anyway i'll finish the connect 4 game tonite. Hope i received nice comments when i post it.

    good luck.
    ADVISORY: This users posts are rated CP-MA, for Mature Audiences only.

  8. #8
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Originally posted by Nutshell
    I see that you didn't notice the function i posted is not to check if someone wins, it's for the computer to make a win move if possible, that means, to place a piece and win.
    Oops, my bad ...
    But it can be used to check a winning move too, if you end up with a number >= 5, then it's a winning move. Anyway, good luck!
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  9. #9
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    No-one, i didn't quite understand what you meant. What do you mean putting a space? I'm not putting a space, i'm checking if the current element in my 2d array contains the character space.

    thnx

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Read part of file
    By Martin Kovac in forum C Programming
    Replies: 1
    Last Post: 04-13-2009, 01:51 PM
  2. algorithm for duplicate file checking help
    By geekoftheweek in forum C Programming
    Replies: 1
    Last Post: 04-04-2009, 01:46 PM
  3. segmentation fault... first time with unix...
    By theMethod in forum C Programming
    Replies: 16
    Last Post: 09-30-2008, 02:01 AM
  4. a simple algorithm and questions
    By ustuzou in forum C++ Programming
    Replies: 0
    Last Post: 02-18-2002, 11:12 AM
  5. string searching algorithm......help
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 12-07-2001, 09:59 AM