How to check if a tic-tac-toe game has been won, on a board of 5x5? (without 500 if statements)

Unity Engine
1

Hey, I am making a sort of tic-tac-toe game, with a board of 5x5 and added features. But I am really struggling to check when a player has won. On a normal 3x3 board this is really easy, but when you expand the board it becomes much more difficult. I have a sort of solution but it involves tons and tons of if statements.
First check if the cell you are standing on is on the edge, in that case, only check on the other side.
Then check if you are one cell from the edge, in that case, only check one cell on that side and two on the other side.
And if you are in the middle, check two cells to the left and two cells to the right.
I had decided that I would only check for vertical and horizontal but that still would have been a lot of if statements and unreadable code.

So is there another way?
I was thinking of having 5 int arrays for each row and column and then whenever you place something the int in the array corresponding to the row or column you placed something on will be set to 1 if you are team 1 and 2 if you are team 2. Then after something has been placed you check the row and column in which you have placed something for if there are is a series of three 1’s or 2’s. You would end up with a grid that looks something like this.

Row1{ 1, 1, 1, 2, 0}
Row2{ 2, 1, 2, 0, 1}
Row3{ 0, 2, 1, 0, 0}
Row4{ 1, 0, 0, 2, 0}
Row5{ 2, 0, 1, 2, 0}

Indicating that on row 1 player 1 has a series on three and then won the game.

But how do you make this? And how do you adapt this to diagonals?

Thanks in advance,
Pepijn

2

Just a quick thought of how I’d probably set it up. Note this is just a quick thought and might require tweaking.
First I’d set up a grid so each spot knows what row and column it’s on.

When a player marks a spot (x or o), we should know what options are available. If you need to get a complete line of 5, then you simply need to use the start or the row or column to determine if it’s correct. So if I mark position 2-3, then I simply start at 1-3 and see if it matches x or o. If it matches my player, then go to 2-3, and continue to 5-3. If at any time I don’t have a match or I have an empty space, that line isn’t a win. Now check 2-1 and go through. For diagonal, only the center could match 5, but again, just going to 1-1 and 5-1 and moving along can check for that.

If only 3 in a row is required, then you just have to include logic to only go up to 2 away or 1 away. You might be able to get a better idea based on how match 3 games do this as it would be a similar concept. Heck, this may help you with it even if you want to match 5 in a row.

3

I’m actually not sure what the rules are to win a 5x5 tic tac toe game, but from what you wrote i assume it’s having 4 in a row. I would define the board as a grid, ie jagged arrays of jagged arrays, or a multidimensional array since performance shouldnt be a major issue here.
So each board[×][y] is then one of 3 states, which may either be enums containing something like None, O and X, or numbers as you did it so far, meaning 0 for undecided, or 1 or 2 for the player that took the field.

You can now simply write some method that goes trough each row and each column after another and counts the largest sequence of identical numbers. So something like 12221 would result in PlayerOne: 1, PlayerTwo: 3. The game ends if you find any sequence of 4 (assuming that’s the win condition, again i have no idea). You then also directly know which player won, and can probably use the same function to return the grid coordinates of the winning sequence.

If you want to handle diagonals, it works similar but is a tad trickier. You have a couple options here. You may either fully loop over the grid, just diagonally now, in which case you need to pay attention to out of bounds. Or you could hard-code either all diagonals that can even host a winning sequence (should only be 6?), or the indices they appear on, which would then be the starting / ending indices of your iterations. Either way, keep in mind that diagonals too have two directions, and that iterating them will require different starting locations, and in at least one case iterating x and y in different directions.

4

Hello,
I totally understand your discomfort with so many ‘if’ statements.
The problem scales up badly, especially if you want extra rules or trying a 3D TicTacToe.
I would have tried a different approach, with a 2D array and a checksum.

• You only need to check a few positions starting where the last player plays, and not the whole grid,
• You only need to check for the last player move
• You only have as many ‘if’ as you have rules, like “line right”, “line left”, “ascending”, “descending”, and so on… and you can add some you would invent as simply

I notice now the code is exactly similar as a connect the four, except here 1 is X, for example, and -1 the O. The checksum can be adapted if you want 5, 4, or tell the other player that his opponent is close to winning when the checksum reaches 2 or any other value.

I’ve made this fast test code (game in editor) for you to check what you think about it. It’s far from perfect and many checks must be made but you’d see the idea. It looks like it’s working.

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEditor;


/// <summary>
/// Player A is positive, Player B negative
/// </summary>
[ExecuteInEditMode]
public class TicTacToe : MonoBehaviour
{
    public int GRID_SIZE = 5;
    public int[,] board;

    void Start()
    {
        board = new int[GRID_SIZE,GRID_SIZE];
    }

    public void WonPosition(int x, int y, int value)
    {

        // line right
        if (x + 2 < board.GetLength(0)
            && board[x + 1, y] + board[x + 2, y] + value == 3)
            Debug.Log("Player A wins");
        if (x + 2 < board.GetLength(0)
            && board[x + 1, y] + board[x + 2, y] + value == -3)
            Debug.Log("Player B wins");

        // line left
        if (x - 2 > 0
            && board[x - 1, y] + board[x - 2, y] + value == 3)
            Debug.Log("Player A wins");
        if (x - 2 > 0
            && board[x - 1, y] + board[x - 2, y] + value == -3)
            Debug.Log("Player B wins");

        // Diagonal ascending right
        if (x + 2 < board.GetLength(0) && y + 2 < board.GetLength(1)
            && board[x + 1, y + 1] + board[x + 2, y + 2] + value == 3)
            Debug.Log("Player A wins");
        if (x + 2 < board.GetLength(0) && y + 2 < board.GetLength(1)
           && board[x + 1, y + 1] + board[x + 2, y + 2] + value == -3)
            Debug.Log("Player B wins");

        // and so on
    }


#if UNITY_EDITOR
    private void OnEnable() => Start();
#endif

}

#if UNITY_EDITOR
[CustomEditor(typeof(TicTacToe))]
public class TicTacToeEditor : Editor
{
    TicTacToe ttt;
    int testPosX, testPosY;
    bool playerA = true;
    public override void OnInspectorGUI()
    {
        ttt = (TicTacToe) target;
        for(int y = 0; y < ttt.GRID_SIZE; y++)
        {
            EditorGUILayout.BeginHorizontal();
            for(int x = 0; x < ttt.GRID_SIZE; x++)
            {
                ttt.board[x, y] = EditorGUILayout.IntField(ttt.board[x, y]);
            }
            EditorGUILayout.EndHorizontal();
        }
        EditorGUILayout.BeginHorizontal();
        testPosX = EditorGUILayout.IntField(testPosX);
        testPosY = EditorGUILayout.IntField(testPosY);
        playerA = EditorGUILayout.Toggle(playerA);
        if(GUILayout.Button("Test Position"))
        {
            ttt.WonPosition(testPosX, testPosY, playerA ? +1 : -1);
        }
        EditorGUILayout.EndHorizontal();
    }
}
#endif
1 Like
5

What I am working on is as you have done it quite a few of if statements, because it just seems like the easier approach. I would have liked to write an algorithm that would have calculated it though. But I sadly don’t have the time to figure it out. Thanks for your reply!

6

You would have to win by having 3 in a row, I made the board 5x5 and added some special moves but you still win by the original rules.

7

i like to see some machine learning ai for this , you play against your AI or just player vs player?

8

I play player vs player it will be multiplayer, after this, I can finally start working on the networking. It is more of a project to learn networking, not necessarily to make a great game. But Yes machine learning would be awesome on that.

9

I have written practically the same code as you have, but I have made use of the things I already had in my project.
Piece = a piece you play, this piece will have an x and y pos, it has a place in the PieceArray (a 2Darray with al the pieces placed on the board). And it has a team int. Where 1 is player1 and 2 is player2.

wPiece is the piece you have just placed,
wPA is the piece array that holds all the placed pieces.
GameManager.BoardSize is the size of the grid. Since the grid starts at 0 I subtracted 1 for easier reading in the if statements.

    public static void CheckIfWon(BasePiece wPiece, BasePiece[,] wPA)
    {
        int x = wPiece.x;
        int y = wPiece.y;
        int bs = GameManager.boardSize - 1;

        if (x != 0 && wPA[x - 1, y] != null && wPA[x - 1, y].team == wPiece.team)
            Debug.Log("One to the left");
        if (x != 1 && x != 0 && wPA[x - 2, y] != null && wPA[x - 2, y].team == wPiece.team)
            Debug.Log("One two to the left");
        if (x != bs && wPA[x + 1, y] != null && wPA[x + 1, y].team == wPiece.team)
            Debug.Log("One to the right!");
        if (x != bs - 1 && x != bs && wPA[x + 2, y] != null && wPA[x + 2, y].team == wPiece.team)
            Debug.Log("One two to the right");
    }

This will sometimes work and sometimes it won’t. It also sometimes reacts to pieces that are placed above or below the piece that was just placed. But that shouldn’t work at all since I never do anything with the y variable.
I hope I just don’t see something obvious and if someone could point that out that would be awesome. I have been bashing my head against this for way to long…
Thanks in advance!

10

I wonder that your current code does not throw and IndexOutOfBounds exception. How are you handling the edges?

Here is an idea for an algorithm. Make a 7x7 grid. Fill it with 0s. For the team spots only use the central 5x5 grid. Fill team one spots with -1, team two spots with +1. Now all your algorithm has to do is sum the lines for each local grid (horizontal, vertical and diagonal). If it’s 3 or -3 then you have a winner. Only apply the algorithm to each spot in central 5x5 grid. You can easily extend it to 4, or 5. The trick with the 7x7 grid and the 0s is that you won’t have to worry about edge cases which makes your If statements a lot simpler.

11

I am handling the edges at the start of the if statements, I am checking if the current piece is for example far enough from the left side (x == 0) to check to the left. If(x != 0) meaning if the current piece isn’t on the first row (from the left) we can check the first row for if there is another piece.

So the if statement is first checking where the piece that has just been placed is. If it is too far to the right or too far to the left to check for pieces to the right or to the left.
Then it is checking if there is a piece on the cell to the right or left.
Then it is checking if that piece belongs to the same team.

12

It may be easier to ignore the last move and instead check the entire board for a win every time. Checking each row is a simple nested loop with an “in-a-row” counter. So is checking columns and both diagonals. It will easily generalize to any size board (even 5x7). It seems wasteful, but it’s going to be plenty fast and less error-prone.

Without testing, a simple “does any player have a line of 3 in any row?”:

const int NUM_TO_WIN=3;
const int X_MAX=7, Y_MAX=7; // for real these are defined elsewhere

// used by loops to count "x in a line for a player":
int prevVal=0; // 1=player1, 2=player2, 0=no owner. Player who occupied the previous space
int numInRow=0; // how many of prevValue has we seen before this

for(int j=0;j<Y_MAX;j++) { // every row
  prevVal=0; // at row start we aren't counting in-a-row for either player
  for(int i=0;i<X_MAX;i++) { // walk through this row:
    int curVal=Board[i][j];
    if(curVal!=prevVal) { prevVal=curVal; numInRow=1; }
    else { // we found a repeat:
      numInRow++;
      if(numInRow>=NUM_TO_WIN) { do win stuff
    }
  }

The same code would work for columns, then roughly the same (more math to find the board space) for diagonals going left, then right. Four sets of this, total.

13

Well, I fixed it with this:

  •       if (x != 0 && wPA[x - 1, y] != null && wPA[x - 1, y].team == wPiece.team)
          Debug.Log("One to the left");
      if (x != 1 && x != 0 && wPA[x - 2, y] != null && wPA[x - 2, y].team == wPiece.team)
          Debug.Log("One two to the left");
      if (x != bs && wPA[x + 1, y] != null && wPA[x + 1, y].team == wPiece.team)
          Debug.Log("One to the right!");
      if (x != bs - 1 && x != bs && wPA[x + 2, y] != null && wPA[x + 2, y].team == wPiece.team)
          Debug.Log("One two to the right");


This code is currently only for the x-axis, to make it work on the y and diagonal you would need additional code.
In the end it had nothing to do with the if statements but with a single wrongly named variable in another script... oh well at least it is fixed, thanks to everyone that posted replies!
14

A simpler idea might be to write a function checking “is space x,y on my team?”. I’d go with geo’s idea of adding extra padding around the sides. That way you can never go off the edge. Then the code would be:

bool isOnMyTeam(int x, int y, team_t myTeam) {
  // range-check if we don't want padding:
  if(x<0 || y<0 || x>=bs || y>=bs) return false;
  return wPA[x,y]!=null && wPA[x,y].team==myTeam;
}

bool left1=isOnMyTeam(x-1,y, wPiece.team);
bool left2=isOnMyTeam(x-2,y,wPiece.team);
bool right1=isOnMyTeam(x+1,y,wPiece.team);
// ... and so on

if(left2 && left1) win=true;
if(left1 && right1) win=true;
if(right1 && right2) win=true;

It’s clunky – a loop would be better. But it’s a nice example of using what you have now but simplifying with a function and the “save IF’s in bools for later” trick.

15

Pseudo:

var directions = {(0,-1), (1,-1), … array with all 8 directions

foreach dir in directions
match = 1;
for (int step = 1; step <= 2; step++)
testPos = playedPos + dir * step;
If (IsValid(testPos) && IsColor(testPos, playedColor) match++

if (match == 3)
Won = true
Break;

16

Sorry if it sounds dumb or unrelated to the topic, but wouldn’t it be “easier” to just check the spacing between the O’s and the X’s and see if the desired state outcome rules apply? Considering that most of the information that is “generated” during a game of Tic-Tac-Toe is filler info, it might make more sense to have a set of conditions under which a win is impossible and a set of conditions that state that someone has won.

For example:

(taken from https://play.google.com/store/apps/details?id=com.benjaminwirtschafter.tictactoefivebyfive)

Most of what happened in the example above does not matter for the winning condition. The only three ways to win the game are to establish a horizontal, a vertical or a diagonal line. Considering that this is a 5x5 field, there is no reason to check for 2x2 conditions, so why not have a “scan” each turn for any 3x3 line to be found on the field, determine whether the line is diagonal, horizontal or vertical and then check if the cells next to the endpoints of the line have met the conditions for a 4 cell line depending on the line type? In a case of the vertical and the horizontal lines, considering there has to be one cell in contact with the edges of the field, you need to have a check for the cell in contact with the fields edge (in the vertical or horizontal direction, depending on the detected line type) and if a cell that is not in contact with the edge has a similar cell (X or O) in the required direction. The same logic applied to the diagonal line adjusted for diagonal lines ( :slight_smile: ).

While i understand that you might not want to use if statements, may i interest you in states implemented using a switch statement instead? You’ll need 6 states for this: is it a diagonal line, is it a vertical line, is it a horizontal line, neighbouring cell checks for horizontal/diagonal/vertical lines.

While looking for a suitable image, i also found this: java - Tic Tac Toe winning condition change when scalable board is larger than 4x4 - Stack Overflow. (It’s in Java but there are some good approaches in there)

17

had a moment, not properly tested & first time I use this dotnetfiddle (not using the Unity libraries)

using System;
using System.Numerics;
                  
public class Program
{
    public static void Main()
    {
        //board Setup as per your example
        const int boardSize = 5;
        int[,] board = new int[boardSize, boardSize] {
            { 1, 1, 1, 2, 0},
            { 2, 1, 2, 0, 1},
            { 0, 2, 1, 0, 0},
            { 1, 0, 0, 2, 0},
            { 2, 0, 1, 2, 0}};
        Vector2[] directions = { new Vector2(0, 1), new Vector2(1, 1), new Vector2 (1, 0), new Vector2(1, -1)};
        int winLineLength = 3;
      
        // player last move
        Vector2 playedPos = new Vector2 (0,1); // note this is (y,x) the way the array is initialized - so in the code the x/y logic is inconsistent dont get confused.
      
        foreach (var dir in directions) {
            int matches = 1;
            for (int changeDir = -1; changeDir <= 1; changeDir += 2)
            {
                for (int step = 1; step < winLineLength; step++) {
                    var testPos = playedPos + dir * step * changeDir;
                    if (IsValid(testPos, boardSize) && IsMatch(board, testPos, playedPos)) matches++;
                        else break;
                }
            }
            if (matches >= winLineLength) Console.WriteLine("Player " + board[(int)playedPos.X, (int)playedPos.Y] + " won! ");
            else Console.WriteLine("attention: only checked last played position for win condition, not the entire board");
        }
    }
  
    public static bool IsValid(Vector2 testPos, int boardSize)
    {
        return (testPos.X < 0 || testPos.X >= boardSize || testPos.Y < 0 || testPos.Y >= boardSize) ? false : true;
    }
  
    public static bool IsMatch (int[,] board, Vector2 testPos, Vector2 playedPos)
    {
        return (board[(int)testPos.X, (int)testPos.Y] == board[(int)playedPos.X, (int)playedPos.Y]) ? true : false;
    }
}
A more elegant null check?
Falling Mechanic with ECS
18

sngan, doesn’t that assume the recent move was in the middle of a line of 3? I mean, it only checks the 8 spaces around it, right? There could be a win with 2 x’s to the left (or above or in any direction). One would need to check 2 spaces away from the recent move to test for at-end-or-start-of-winning-line. But then a simple count-to-3 won’t work, since you could have “xoxox” or even “xxoxx”.

19

No, it should cover those cases. I have not tested it much (only in my mind the logic makes sense). It should work for any board size and win condition I.e. length of connected pieces.

The script example uses OP 5x5 board and streak of 3.
it considers the last played piece as the center and then walks 2 steps in one direction and counts same player pieces and then the same in the opposite direction. Note the break statement, it only considers connected pieces. If 3 or more connected it’s a win.

the pseudo code is too simplified, the actual script should work

20

I’m making a Tic Tac Toe Multiplayer class that contains a 3 by 3 rectangular exhibit of numbers and is played by 2 human players. “1” is utilized for the main player’s turn and “2” is utilized for the subsequent player’s turn. At present, I am stuck and have no idea on the most proficient method to decide/check whether the game has been won or whether its a draw after every single action has been made.