3
\$\begingroup\$

This code is part of a tic tac toe game. It uses a 2D array for the board.

The functionality of the following code is to check for a win on the board, in rows, columns and diagonals. How can I improve it?

public bool WhoWon(Cell cell) 
{
    for (int i = 0; i < 3; i++) 
    {
        for (int j = 0; j < 3; j++) 
        {
            if (_board[i, 0] == cell && _board[i, 1] == cell && _board[i, 2] == cell) 
            {
                return true;
            } 
            else if (_board[0, j] == cell && _board[1, j] == cell && _board[2, j] == cell) 
            {
                return true;
            }
        }
    }

    if (_board[0, 0] == cell && _board[1,1] == cell && _board[2,2] == cell) 
    {
        return true;
    }
    else if (_board[0, 2] == cell && _board[1, 1] == cell && _board[2, 0] == cell) 
    {
        return true;
    }
    return false;
}
\$\endgroup\$
  • \$\begingroup\$ You'll receive better reviews if you show a complete example. For example, I recommend that you edit to show the necessary definitions/imports, and a main() that shows how to call your function. It can really help reviewers if they are able to compile and run your program. \$\endgroup\$ – Toby Speight Feb 21 '18 at 13:24
5
\$\begingroup\$
public bool WhoWon(Cell cell) 

The nameWhoWon suggests that it returns the player that won, but instead it returns a boolean. A better name would be HasWon.


When looping over a 2-dimensional array, it is good to use x and y for the loop variables, instead of i and j, because they are more intuitive coordinates.


The loops are obsolete, and do the same checks multiple times. Because your board is just 3x3 big, I suggest to just do the 8 checks, which would just be 8 more readable lines. If you do want to use for-loops for the rows and columns, you only need one for each, so two sequential loops, not nested ones. For the diagonals, as you did correctly, there is no reason to use a loop.

I added suggestions at the end of the answer for how to implement the loops correctly, for when the board size is not known or might change.


When checking the diagonals, your conditions are not mutually exclusive, so there is no need for the else if. Also, you are returning true in both cases, so you can combine both conditions to a single expression, and return the result of the expression.

return _board[0, 0] == cell && _board[1,1] == cell && _board[2,2] == cell
       || _board[0, 2] == cell && _board[1, 1] == cell && _board[2, 0] == cell;

You can further improve it (in terms of performance) and reduce redundace by first checking the middle cell, because it is required to be set for both diagonals. However, the performance gain is negligible, and the readibility arguably is reduced. If you do it this way, I recommend putting it into another private method where the method name tells you what it does (e. g. CheckDiagonals).

return _board[1,1] == cell
       && (_board[0, 0] == cell && _board[2,2] == cell
           || _board[0, 2] == cell && _board[2, 0] == cell);

You say you want to adapt the code for different board sizes. In that case, a loop that goes along the diagonals is needed (I first assumed you meant looping over diagonals as a whole, i. e. for each diagonal do this).

Think about what defines a diagonal, not in terms of geometry, but coordinates. Both coordinates are the same (or they have the same absolute value, depending on the direction). So you only need one loop, and use it for both the x and y coordinate. Then you

for (int i = 0; i < width; i++)
{
    // Use i as your x and y coordinate. (Might as well use i directly, this is for illustrative purposes.)
    int x = i;
    int y = i;

    // We try to "disprove" that "cell" has won.
    // If we couldn't disprove it until the end of the row, "cell" has won.
    if (_board[x, y] != cell) { break; }
    if (y == width - 1) { return true; }
}

This assumes that width and height are the same, otherwise it gets more complicated. Also, you need to use int x = i; int y = -i; when you loop over the other diagonal, as the direction changes.

Doing the same for rows and columns when the width and height might change, you can do the following:

for (int x = 0; x < width; x++)
{
    for (int y = 0; y < height; y++)
    {
         if (_board[x, y] != cell) { continue; }
         if (y == height - 1) { return true; }
    }
}
\$\endgroup\$
  • \$\begingroup\$ Although true, I would argue that keeping the 2 diagonal checks separate is more readable. Your final return statement isn't obvious at all that it is checking for diagonals. \$\endgroup\$ – Imus Feb 21 '18 at 12:14
  • \$\begingroup\$ I agree. I will try to be more explicit. \$\endgroup\$ – Raimund Krämer Feb 21 '18 at 12:15
  • \$\begingroup\$ I did not understand your last edit with the for-loop. \$\endgroup\$ – Winston Smith Feb 21 '18 at 12:26
  • \$\begingroup\$ Which part exactly? This one? for (int i = 0; i < width; i++). \$\endgroup\$ – Raimund Krämer Feb 21 '18 at 12:35
  • \$\begingroup\$ Yes, the one for diagonals. \$\endgroup\$ – Winston Smith Feb 21 '18 at 12:37
13
\$\begingroup\$

What you've done here is listed all possible checks, but you've compiled it into a single method. Ideally, you should split this up into separate tasks, as there are three categories of similar checks:

  • Horizontal checks
  • Vertical checks
  • Diagonal checks

Maybe the current example is just simple enough to not fully warrant it, but especially if you had had many different win conditions (e.g. another rule that states making a 2x2 square also counts as a win), you'd understand why you need to break your validation into smaller (logically coherent) parts.


The method

public bool WhoWon(Cell cell) 

I agree with the other answers here. The name of the method does not match its return type. WhoWon should return a player. HasWon should return a boolean.

I'm also not a fan of the "cell" name. Looking at the code, cell seems to contain the player's letter (X or O). That is not immediately apparent by calling it a cell, a cell would be a box on the board.

E.g. board[1,1] is a cell, as it represents a box on the board. But I would call the value of board[1,1] a token, i.e. the symbol that is contained within (if it's not empty).

You haven't shared the how Cell is defined. This may already be close to what I'd prefer to use. Based on this, let me suggest an improvement:

public enum Token { X, O, Empty }

public Token[,] _board = new Token[3,3];

public bool HasWon(Token token)
{
    // ...
}

Notice that you could also implement WhoWon() based on HasWon():

public Token WhoWon()
{
    if(HasWon(Token.X)) 
        return Token.X;

    if(HasWon(Token.O)) 
        return Token.O;

    return Token.Empty;
}

The method body

I suggest splitting this up, as it will dramatically simplify the validation logic and make it easier to parse.

public enum Token { X, O, Empty }
public Token[,] _board = new Token[3,3];

public bool HasWon(Token token) 
{
    return
        IsHorizontalVictory(token)
        || IsVerticalVictory(token)
        || IsDiagonalVictory(token);

}

private bool IsHorizontalVictory(Token token)
{
    for(int y = 0; y <= 2; y++)
    {
        if(_board[0,y] == token && _board[1,y] == token && _board[2,y] == token)
            return true;
    }

    //No victory condition hit = no victory.
    return false;
}

private bool IsVerticalVictory(Token token)
{
    for(int x = 0; x <= 2; x++)
    {
        if(_board[x,0] == token && _board[x,1] == token && _board[x,2] == token)
            return true;
    }

    //No victory condition hit = no victory.
    return false;
}

private bool IsDiagonalVictory(Token token)
{
    if(_board[0,0] == token && _board[1,1] == token && _board[2,2] == token)
        return true;

    if(_board[0,2] == token && _board[1,1] == token && _board[2,0] == token)
        return true;

    //No victory condition hit = no victory.
    return false;
}

Comments:

  • You could further abstract this, e.g. by making the dimensions of the board variable. However, TicTacToe is always played on a 3x3 board, so this seems unnecessary at the moment.
  • Instead of using a multidimensional array, you could create a full OO representation of the board with its cells. This is going to cost some effort to put together, but it will make board operations (such as checking for victory) nicer to read. Index-based retrieval is nice when simple, but can become horrendously complex to follow if the logic gets to be too big.
  • Some things could have been rewritten, e.g. the IsDiagonalVictory() method could have merged the two checks (+ the false return value) into one boolean: return (logic_for_diag_1) || (logic_for_diag_2). However, this would've storngly affected the readability of the code. As the performance difference is negligible, I therefore chose the most readable option.

This was a headscratcher

for (int i = 0; i < 3; i++)  //A
{
    for (int j = 0; j < 3; j++)   //B
    {
        //A
        if (_board[i, 0] == cell && _board[i, 1] == cell && _board[i, 2] == cell) 
        {
            return true;
        } 

        //B
        else if (_board[0, j] == cell && _board[1, j] == cell && _board[2, j] == cell) 
        {
            return true;
        }
    }
}

It took me a while to understand what your intention was here. You've combined two completely separate for-loops, and have for some reason decided to intwine them.

I marked them A and B in the code, because these two are completely separate pieces of logic. Splitting them up:

for (int i = 0; i < 3; i++)  //A
{
    if (_board[i, 0] == cell && _board[i, 1] == cell && _board[i, 2] == cell) 
    {
        return true;
    }         
}

for (int j = 0; j < 3; j++)   //B
{
    if (_board[0, j] == cell && _board[1, j] == cell && _board[2, j] == cell) 
    {
        return true;
    }
}

You may be wondering, does it matter?

Yes, it does. First of all, splitting them dramatically enhances the readability of the code.

Secondly, you're going to end up doing less loops.

  • Nested for-loops are multiplicative. 3 loops for A times 3 loops for B = 9 loops. Furthermore, each of the 9 loops is doing two checks, thus resulting in 18 checks occurring.
  • Separate for-loops are additive. 3 loops for A plus 3 loops for B = 6 loops. Each loop only does one check, thus resulting in 6 checks occuring.

Your nested loops were performing every unique check three separate times (18 / 6 = 3), which serves no functional purpose.

Let's look at only the vertical check:

if (_board[i, 0] == cell && _board[i, 1] == cell && _board[i, 2] == cell)

This was being executed for every pair of i,j, while you only needed to test for every value of i.

This is a comparison of the pairs (i,j) and what the vertical check actually did:

(0,0)   =>   Checks vertical column 0
(0,1)   =>   Checks vertical column 1
(0,2)   =>   Checks vertical column 2
(1,0)   =>   Checks vertical column 0
(1,1)   =>   Checks vertical column 1
(1,2)   =>   Checks vertical column 2
(2,0)   =>   Checks vertical column 0
(2,1)   =>   Checks vertical column 1
(2,2)   =>   Checks vertical column 2

Notice how it repeats the same thing for every value of j (0,1,2), even though the value of j has no impact on the outcome of the result.

This is a comparison of the values of i and what the vertical check actually did:

(0)   =>   Checks vertical column 0
(1)   =>   Checks vertical column 1
(2)   =>   Checks vertical column 2

By not observing the value of j, we haven't repeated the same check for every distinct value of j.

\$\endgroup\$
  • \$\begingroup\$ What if the board size different than 3? How would you check the diagonals? \$\endgroup\$ – Winston Smith Feb 21 '18 at 13:42
  • \$\begingroup\$ @WinstonSmith: All the logic should be rewritten if the dimensions of the board change. Most notably; if the board's dimensions change in a way that it's no longer a square, the diagonals won't really exist anymore (in a way that adheres to current TTT rules) \$\endgroup\$ – Flater Feb 21 '18 at 13:44
  • 1
    \$\begingroup\$ @WinstonSmith: Essentially, if you want a variable board size, you're going to have to find all occurences of the fixed number 3 (the array dimensions, the amount of loops in a for-loop, the number of fields that are checked in a given row/column/diagonal) and parametrize those. \$\endgroup\$ – Flater Feb 21 '18 at 13:46
  • \$\begingroup\$ @Flater that assumes however that you are still looking for 3 in a row, even if your board is 10x10. I would assume that a "tic-tac-toe extreme" would need 10 in a row to win. \$\endgroup\$ – Raimund Krämer Feb 21 '18 at 13:49
  • 1
    \$\begingroup\$ I'm not a C# user, but those commas in the for loops look wrong. Should those be semicolons? \$\endgroup\$ – Adrian McCarthy Feb 21 '18 at 22:15
2
\$\begingroup\$

There was a previous question that I answered regarding Tic-Tac-Toe that I'm too lazy to look up, but this is a common enough subject (as you are apparently aware, there's even a tag for it) that you might want to take a look at other questions and see what applies to your program.

Taking a broader look than the other answers to your question, why are you even checking for a win in the first place? If your program is running this function after every move, that's horribly wasteful. All you have to do is check whether the new move creates a win. You only have to check the lines the new move is in, and you only have to check two locations for each line (you know that wherever the current player just moved has their symbol in it, by definition).

Also, any time you have if X then return ..., you don't need an else; if the first if is satisfied you won't reach the rest anyway.

\$\endgroup\$
  • \$\begingroup\$ While I get your point about checking unchanged rows, there is a complexity argument here. Since we're talking about a 3x3 grid here (8 lines total),the added work is negligible. However,the logic required to figure out which lines could now result in a victory, is not as easy to define as it seems at first glance. You need separate logic for center, edge and corner cells. And for edge and corner cells, you need additional logic based on which side of the gridn the cell is located. Realistically, this is going to end up with you having to hardcode all possible lines for a given updated cell. \$\endgroup\$ – Flater Jul 4 '18 at 15:37
  • \$\begingroup\$ @Flater The complexity of listing each line that each cell is in is pretty much the same as listing each cell that is in each line, and the latter is what the OP is doing. \$\endgroup\$ – Acccumulation Jul 5 '18 at 15:36
  • \$\begingroup\$ Either you define the possible lines per cell, or you iterate over all possible lines to find those which are affected by the cell. If it's the former, that requires triple the mapping. If it's the latter, you're still iterating over all lines anyway so the performance gain is negligible. Checking all 8 lines is a less dynamic approach and more likely to be optimized by the compiler in the ens anyway. \$\endgroup\$ – Flater Jul 5 '18 at 19:10

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.