Thread: Help with algorithm to check if there's a winner in the Connect 4 game

  1. #1
    Registered User
    Join Date
    Jan 2005
    Posts
    204

    Help with algorithm to check if there's a winner in the Connect 4 game

    It's easy to check the lines and the columns but I am having a hard time with the diagonals? The board size varies so I can't have any buried numbers. Do you guys have any suggestions? Thanks.

  2. #2
    Been here, done that.
    Join Date
    May 2003
    Posts
    1,164
    Do the same with rows and columns. For diags you add to both index values. If either is outside your bounds, stop.
    Definition: Politics -- Latin, from
    poly meaning many and
    tics meaning blood sucking parasites
    -- Tom Smothers

  3. #3
    Registered User
    Join Date
    Jan 2005
    Posts
    204
    This is what I have so far:
    Code:
    #define N   6 /* lines */
    #define M   7 /* columns */
    
    int matrix[N][M];
    Code:
    int check_win(int matrix[][M], int play)
    {
    	int i;
    	int j;
    	int counter;
    
    	/* horizontally */
    	for(i = 0, counter = 0; i < N; i++) {
    		for(j = 0; j < M; j++) {
    			if(matrix[i][j] == matrix[i][j + 1])
    				counter++;
    
    			if(counter == 4)
    				return 1;
    		}
    	}
    
    	/* vertically */
    	for(i = 0, counter = 0; i < M; i++) {
    		for(j = 0; j < N; j++) {
    			if(matrix[j][i] == matrix[j + 1][i])
    				counter++;
    
    			if(counter == 4)
    				return 1;
    		}
    	}
    
    	return 0;
    }
    Can you show me what you mean please? Thanks.

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Start at a square. Move diagonally by incrementing or decrementing the needed variables one at a time to check for a match. If you don't find a match, stop counting. Repeat until done. There's nothing to show (aside from writing the whole thing for you).

    Seriously, work it out on paper how you'd check for a win yourself in a linear method.

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

  5. #5
    Registered User
    Join Date
    Jan 2005
    Posts
    204
    After trying on my own for a lot of time, I was able to come up with this. It works *sometimes*, my head really hurts and I am going crazy over this. Can someone tell me what I am doing wrong? Thank you.
    Code:
    /* N is the number of lines amd M the number of columns */
    
    int check_win(int matrix[][M], int play)
    {
    	int i;
    	int j;
    	int counter;
    	char player;
    
    	for(i = 0; i < N; i++) {
    		if(matrix[i][play] != '.')
    
    			player = matrix[i][play];
    	}
    
    	for(j = 0; j < M - 3; j++) {
    		for(i = 0; i < N - 3; i++) {
    			counter = 1;
    
    			while((counter < 4) && matrix[i + counter][j + counter] == player)
    				counter++;
    
    			if(counter == 4)
    				return 1;
    		}
    	}
    
    	for(j = 0; j < M - 3; j++) {
    		for(i = 3; i < N; i++) {
    			counter = 1;
    
    			while((counter < 4) && matrix[i - counter][j + counter] == player)
    				counter++;
    
    			if(counter == 4)
    				return 1;
    		}
    	}
    
    	counter = 1;
    	for(i = 0; i < N; i++) {
    		for(j = 0; j < M; j++) {
    			if(matrix[i][j] == player && matrix[i][j + 1] == player)
    				counter++;
    
    			else
    				continue;
    
    			if(counter == 4)
    				return 1;
    		}
    	}
    
    	counter = 1;
    	for(i = 0; i < M; i++) {
    		for(j = 0; j < N; j++) {
    			if(matrix[j][i] == player && matrix[j + 1][i] == player)
    				counter++;
    
    			else
    				continue;
    
    			if(counter == 4)
    				return 1;
    		}
    	}
    
    	return 0;
    }

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Code:
    int isValidCoord ( int x, int y ) {
      return x >= 0 && x < M && y >= 0 && y < M;
    }
    
    int checkWinningLine ( int matrix[][M], int play, int x, int y, int dx, int dy ) {
      int count = 0;
      int ix, iy;
      for ( ix = x, iy = y ; count < 4 && isValidCoord(ix,iy) ; ix += dx, iy += dy ) {
        if ( matrix[iy][ix] != play ) break;
      }
      return count == 4;
    }
    Now create two more functions

    1. A function "A" to call checkWinningLine() for a given xy position, varying dx and dy to scan in 8 different directions.
    2. A function "B" to call function "A" for all possible start positions on the board.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  7. #7
    The C-er
    Join Date
    Mar 2004
    Posts
    192
    I was going to suggest breaking up your code into more functions, but couldn't be bothered to think about how. Very nice of Salem to show the way.
    2. A function "B" to call function "A" for all possible start positions on the board.
    You might be able to miss this function, just use the position of the last counter placed during an actual game.

  8. #8
    Registered User
    Join Date
    Jan 2005
    Posts
    204
    Salem, I thank you for trying to help. The problem is that I have to use some predefined functions and nothing more. I am almost done now. My program detects horizontal and vertical wins perfectly but I am still having problems with the diagonals. I'll post the whole thing so anyone willing to help can have a better idea of what is going on. Thanks a lot.
    Code:
    #include <stdio.h>
    
    #define N 6
    #define M 7 
    
    void write_board(int board[N][M]);
    int is_full(int board[N][M]);
    int get_move(int player);
    int valid_move(int board[N][M], int column);
    void make_move(int board[N][M], int player, int column);
    int win(int board[][M], int move);
    
    int main(void)
    {
    	int i;
    	int j;
    	int move;
    	int player;
    	int winner = 0;
    	int board[N][M];
    
    
    	for(i = 0; i < N; i++) {
    		for(j = 0; j < M; j++)
    			board[i][j] = '.';
    	}
    
    	do {
    		player = 1; 
    	    write_board(board);
    
    		do {
    			move = get_move(player);
    		}while(valid_move(board, move) == 0);
    
    		move -= 1;
    		
    		make_move(board, player, move);
    		
    		if(win(board, move) == 1) {
    			winner = 1;
    			printf("\n");
    			write_board(board);
    			break;
    		}
    
    		printf("\n");
    
    		player = 2;
    		write_board(board);
    
    		do {
    			move = get_move(player);
    		}while(valid_move(board, move) == 0);
    		
    		move -= 1;
    
    		make_move(board, player, move);
    		
    		if(win(board, move) == 1) {
    			winner = 2;
    			printf("\n");
    			write_board(board);
    			break;
    		}
    
    		printf("\n");
    
    	}while(is_full(board) == 0);
    
    	if(winner == 1)
    		printf("\nEnd! 1\n");
    
    	else if(winner == 2)
    		printf("\nEnd! 2\n");
    
    	else
    		printf("\nDraw!\n");
    
    	return 0;
    }
    
    void write_board(int board[][M])
    {
    	int i;
    	int j;
    
    	for(i = 0; i < M; i++)
    		printf("%d ", i + 1);
    
    	printf("\n");
    	for(i = 0; i < N; i++) {
    		for(j = 0; j < M; j++)
    			printf("%c ", board[i][j]);
    		printf("\n");
    	}
    }
    
    int is_full(int board[N][M])
    {
    	int i;
    	int j;
    
    	for(i = 0; i < N; i++) {
    		for(j = 0; j < M; j++)
    			if(board[i][j] == '.')
    				return 0;
    	}
    
    	return 1;
    }
    
    int get_move(int player)
    {
    	int column;
    
    	printf("%d> ", player);
    	scanf("%d", &column);
    
    	return column;
    }
    
    int valid_move(int board[N][M], int column)
    {
    	int i;
    	int ocupado = 0;
    
    	if(column > M) {
    
    		printf("\nInvalid move\n");
    		return 0;
    	}
    
    	for(i = 0; i < N; i++) {
    		if(board[i][column - 1] != '.')
    			ocupado++;
    	}
    
    	if(ocupado == N) {
    		printf("\nJogada inv%clida\n", 160);
    		return 0;
    	}
    
    	else
    		return 1;
    }
    
    void make_move(int board[N][M], int player, int column)
    {
    	int i;
    	char ch;
    
    	if(player == 1)
    		ch = 'O';
    	else
    		ch = 'X';
    
    	for(i = N; i >= 0; i--) {
    		if(board[i][column] == '.') {
    			board[i][column] = ch;
    			break;
    		}
    	}
    }
    
    int win(int board[][M], int move)
    {
    	int i;
    	int line;
    	int column;
    	int counter;
    	char player = '\0';
    
    	for(i = 0; i < N; i++) {
    		if(board[i][move] != '.') {
    			player = board[i][move];
    			break;
    		}
    	}
    
    	counter = 0;
    	line = i;
     
    	column = move;
    	while((counter < 5) && (board[line][column] == player)) {
    		counter++;
    		column--;
    
    		if(counter == 5)
    			return 1;
    	}
    
    	column = move;
    	while((counter < 5) && (board[line][column] == player)) {
    		counter++;
    		column++;
    
    		if(counter == 5)
    			return 1;
    	}
    
    	counter = 0;
    	column = move;
    
    	while((counter < 5) && (board[line][column] == player)) {
    		counter++;
    		line--;
    
    		if(counter == 5)
    			return 1;
    	}
    
    	line = i;
    
    	while((counter < 5) && (board[line][column] == player)) {
    		counter++;
    		line++;
    
    		if(counter == 5)
    			return 1;
    	}
    
    	counter = 0;
    
    	line = i;
    	column = move;
    
    	while((counter < 4) && (board[line][column] == player)) {
    		counter++;
    		line++;
    		column--;
    
    		if(counter == 4)
    			return 1;
    	}
    
    	line = i;
    	column = move;
    
    	while((counter < 5) && (board[line][column] == player)) {
    		counter++;
    		line--;
    		column++;
    
    		if(counter == 5)
    			return 1;
    	}
    
    	counter = 0;
    
    	line = i;
    	column = move;
    
    	while((counter < 4) && (board[line][column] == player)) {
    		counter++;
    		line++;
    		column++;
    
    		if(counter == 4)
    			return 1;
    	}
    
    	line = i;
    	column = move;
    
    	while((counter == 5) && (board[line][column] == player)) {
    		counter++;
    		line--;
    		column--;
    
    		if(counter == 5)
    			return 1;
    	}
    
    	return 0;
    }

  9. #9
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    To move diagonally from upper left to lower right, increment both X and Y, where X is the column, and Y is the row. (Typically these are reversed when you're looping through an entire grid. The outer loop being Y.)

    To move diagonally from lower left to upper right, decrement Y and increment X.
    To move diagonally from lower right to upper left, decrement both Y and X.
    To move diagonally from upper right to lower left, decrement X and increment Y.

    It's not hard. You just have to stop and think it out. Didn't you ever learn anything about plotting coordinates in [insert some somewhat basic math course here]?

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

  10. #10
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > just use the position of the last counter placed during an actual game.
    Except you can place a piece in the middle of a row of 4, and still generate a winning line.

    > The problem is that I have to use some predefined functions and nothing more.
    Well if you don't say up front "I have to use these bizarre function names and other weird tutor imposed rules", what can you expect?
    Just unroll my code into your already massively long "win" function and let your ill-informed tutor sort it out.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  11. #11
    The C-er
    Join Date
    Mar 2004
    Posts
    192
    Except you can place a piece in the middle of a row of 4, and still generate a winning line.
    Good point. I guess it's been a while since I played connect 4.

  12. #12
    Registered User
    Join Date
    Jan 2005
    Posts
    204
    Take a look at this piece of code please:
    Code:
    counter = 0;
    line = i;
     
    column = move;
    while((column >= 0) && (board[line][column] == player)) {
    	counter++;
    	column--;
    
    	if(counter == 5)
    		return 1;
    }
    This will test a line going to the left. Did you guys notice that inside the while loop I am comparing variable counter with number 5? But hey, this is a connect FOUR game so wasn't I supposed to exit the loop when counter equals 4? Well, if I do that, my game gives a win to whoever have three pieces in a row. I don't understand why that is happening. Can someone enlighten me? Thanks.

  13. #13
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Take a look at the code for the connect four contest a while ago. It has been tested thoroughly.

    If you perform the check every round, you only have to check around the last placed marker.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. beach bar (sims type game)
    By DrKillPatient in forum Game Programming
    Replies: 1
    Last Post: 03-06-2006, 01:32 PM
  2. PC Game project requires c++ programmers
    By drallstars in forum Projects and Job Recruitment
    Replies: 2
    Last Post: 02-22-2006, 12:23 AM
  3. My Memory Game
    By jazy921 in forum C Programming
    Replies: 0
    Last Post: 05-05-2003, 05:13 PM
  4. need algorithm for game of life
    By Unregistered in forum C Programming
    Replies: 9
    Last Post: 05-18-2002, 11:27 PM
  5. My tic tac toe game, please check this out.
    By Leeman_s in forum C++ Programming
    Replies: 1
    Last Post: 11-05-2001, 11:14 PM