5
\$\begingroup\$

I am working on designing a simple version of a Connect 4 game.

Here is my first draft code. I would like some feedback on it, and also required modification for these follow up questions:

  1. Add some intelligence in the players to select the column optimally.
  2. How will you make the game generic so that it can check for 16 points in a row/column/diagonal
  3. How will you handle a huge grid?

Regarding item3, I think since I am not storing the whole grid, my approach is scalable. I appreciate for any recommendations or feedback.

class Connect4 {

vector <pair<int, map< pair<int,int>,int > > > rows;
vector <pair<int, map< pair<int,int>,int > > > cols;
vector <pair<int, map< pair<int,int>,int > > > diag;
int r;
int c;
int player;
public:
  Connect4 (int rr, int cc):r(rr), c(cc){
     rows = vector <pair<int, map< pair<int,int>,int > > >  (rr);
     cols = vector <pair<int, map< pair<int,int>,int > > > (cc);
     diag = vector <pair<int, map< pair<int,int>,int > > > (min (rr,cc));
  }
  
  int move(int row, int col, int player){
      int score = (player ==1)?1:-1;   // count player-1 socres with positive and player-2 with negative numbers 
      
      rows[row].first +=score;
      rows[row].second[{row,col}]=score;
      if (abs(rows[row].first) ==4 && isValid(rows[row].second) )
            return player;
      
      cols[col].first += score;
      cols[col].second[{row,col}]=score;
      if (abs(cols[col].first) ==4 && isValid(cols[col].second) )
            return player;
      
      if(row ==col+2){
        diag[0].first +=score; 
        if (abs(diag[0].first) ==4 ) //if the score is 4 no extra checking is needed
            return player;
           
      } else if (row ==col+1) {
        diag[1].first += score; 
        if (abs(diag[1].first) ==4 && isValid(diag[1].second) )
            return player;
        
      } else if (row ==col) {
         diag[2].first += score;  
         if (abs(diag[2].first) ==4 && isValid(diag[2].second) )
            return player;
         
      } else if (row+1 ==col) {
         diag[3].first += score; 
         if (abs(diag[3].first) ==4 && isValid(diag[3].second) )
            return player;
         
      } else if (row+2 ==col) {
         diag[4].first += score;
         if (abs(diag[4].first) ==4 && isValid(diag[4].second) )
            return player;
         
      } else if (row+3 ==col) {
        diag[5].first += score; 
        if (abs(diag[5].first) ==4 )
            return player;
      }
  }
  
  bool isValid(map<pair<int,int>, int> verify) {
      int cnt=1;
      map<pair<int,int>, int>::iterator itr = verify.begin();
      int prev= itr->second;
      itr++;
      for (;itr!= verify.end(); ++itr){
        int score = itr->second ; 
        if(prev == score){
            cnt++;
            if(cnt ==4)
              return true;
        } else {
           cnt=0;
        } 
        prev = score;
      }
      return (cnt>=4);
  }
};

The logic behind calculating the diagonal is discussed here: in a grid of 6x7, we can have diagonal score of >=4 only in following matrix indices:

If we have same scores in following (X,Y):

  • (2,0), (3,1), (4,2), (5,3) -> diag[0]
  • (1,0), (2,1), (3,2), (4,3), (5,4)
  • (0,0), (1,1), (2,2), (3,3), (4,4), (5,5)
  • (0,1), (1,2), (2,3), (3,4), (4,5), (5,6)
  • (0,2), (1,3), (2,4), (3,5), (4,6)
  • (0,3), (1,4), (2,5), (3,6) -> diag[6]
\$\endgroup\$
3
  • 3
    \$\begingroup\$ Why are you using those complicated types? A vector (either R*C elements with custom indexing, or a vector<vector<int>>) would be easier to use and consume less memory. \$\endgroup\$ – 1201ProgramAlarm Feb 27 at 3:08
  • \$\begingroup\$ @ 1201ProgramAlarm That is a good question. Here are my points: >> Using a 2D vector is a straight forward approach, but you may need to check all the rows and columns and diagonal elements after each move. >> With the given approach you only need to check a single row, column, or diagonal line once its corresponding score is 4. This checking is only needed since we need to verify if the coins are located right beside each other. >> Also the given idea can be expanded in case of having larger boards in which defining a large 2D vector could be a big problem. \$\endgroup\$ – Ashkan Feb 27 at 6:25
  • 2
    \$\begingroup\$ A flat vector of rows makes it easy to check straight lines - the stride between elements is 1 for a horizontal line, cols for a vertical, cols+1 for a leading diagonal and cols-1 for a trailing diagonal. Just make sure you get the start and end positions correct, and you're set to go. \$\endgroup\$ – Toby Speight Feb 27 at 13:05
5
\$\begingroup\$

Naming things

Avoid single-character variable names, unless it's something that is very commonly used, like i for a loop index. Consider r and c, even if you guess it has something to do with coordinates, are those positions or sizes? I would personally use width and height here as unambiguous names for the size of the grid.

Note that in the constructor's initializer list, you can use the same name for the parameter as for the member variable, like so:

int width;
int height;

public:
Connect4(int width, int height): width(width), height(height) {...}

Not everyone likes this style; some people want to disambiguate between parameter and member variable by writing:

Connect4(int width_, int height_): width(width_), height(height_) {...}

And you also see projects where all member variables are prefixed with m_, so it will look like:

int m_width;
int m_height;

public:
Connect4(int width, int height): m_width(width), m_height(height) {...}

Other variable names that could be improved:

  • cnt -> count
  • itr -> it (the latter is more idiomatic)
  • diag -> diagonal
  • verify -> line

Create an enum class for the possibly contents of a grid cell

An enum, and even better an enum class, allow you to specify the possible values of a grid cell up front, with names instead of integer values. I suggest you write the following:

class Connect4 {
    enum class Cell: char {
       EMPTY,
       PLAYER1,
       PLAYER2,
    };
};

The above also explicitly sets the type to char, so only one byte is necessary to store it.

Storing the grid

There are several things wrong with how you store the grid. The data structure you are using is very inefficient, both for large and small grids, and for checking for a winning condition. The best way is to use a single vector to store all the grid cells:

std::vector<Cell> grid;

This ensures things are laid out very compactly in memory, and to look up an arbitrary grid cell, the CPU only has to do one multiplication and two additions, which is very cheap on contemporary processors, and as Toby Speight already mentioned, to check horizontal, vertical and diagonal lines is very easy as well; just calculate the start point, end point and stride to use, and then every step along the line only a single addition has to be done to find out the grid cell to check.

I would add a function to get a reference to a grid cell given its coordinates, like so:

Cell &at(int row, int col) {
    return grid[row * c + col];
}

Handling huge grids

The first thing to consider when dealing with huge grids/arrays/matrices is whether the data structure is going to be densely or sparsely populated. It's easy to think that it should be sparse, after all you start with the grid being completely empty. But consider that during the end game of connect 4, you will probably have used more than half of the grid cells, so a dense grid is likely the best way to store the state.

With the above Cell type, you use one byte per grid cell. Since a cell only has three possible states, you could pack up to five cells in a byte (since 3⁵ = 243) relatively easily, at the cost of some extra calculations when reading/writing a given cell. With this, a 100,000 by 50,000 grid fits in a little less than a gigabyte.

You might also think about compressing the grid somehow, but again consider what a connect 4 game looks like near the end. For sure there won't be runs of more than 3 cells with the same color in a row, otherwise there would already have been a winner. And you rarely see a repetitive pattern appearing. So it basically looks like noise, which is not compressible. Perhaps predictive coding could be used to compress the sequence of moves made by the players, but the compressed data would most likely not be in a form suitable for displaying the grid and checking winning conditions.

The only option I see for significantly reducing the amount of data is to consider that the bulk of the grid cells where players have already played will never be part of the 4 connected cells of the same color. For example, you could mark all cells that are more than 3 positions away (both horizontally and vertically) from any empty cells as being "dead". This way, that in principle, instead of having to store \$\mathcal{O}(W \cdot H)\$, you only have to store \$\mathcal{O}(W + H)\$ grid cells. But that would mean that you cannot show exactly all the moves made so far anymore.

Checking for a winning condition

Your idea of keeping a per-line score is unfortunately not really helpful. It is quite easy to create a line where the total score would be four, but there are no 4 consecutive cells with the same player, for example, representing players 1 and 2 with O and X respectively:

X O O X O O X O O X O O

There are 8 pieces of player 1, and 4 of player 2, so your way of counting score would result in 4 or -4, but clearly no player has won yet. However, if player 1 adds two more O's to this line:

X O O X O O X O O X O O O O

Then player 1 has 4 in a row, but the "line score" would be 6 or -6. So the line score is not useful.

The simple solution is to just always check the 9x9 area surrounding the latest move for a horizontal, vertical or diagonal line with 4 in a row. This might seem a bit wasteful in the very early game when only few moves have been made, it doesn't really matter in the long run.

\$\endgroup\$
1
  • \$\begingroup\$ thanks for the feedback. Just a quick comment regarding "Checking for a winning condition". The isValid() function checks if there are 4 consecutive of same players score in a row, col or diagonal. And i intentionally checked first if the score is 4 or -4 and then calling isValid(). In other words isValid is called if and only if the abs(score_value) is equal to 4 \$\endgroup\$ – Ashkan Feb 27 at 18:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.