Array programming - check winner in a Tic Tac Toe game for an nxn board with n players

Question

I am making a tic tac toe game for n number of players on a nxn board, but the winning condition is aways 3 on a row. My so far solution to the problem is: when a move is made the program will check the following square for 3 on a row.

(x-1,y+1) (x,y+1) (x+1,y+1)

 (x-1,y)   (x,y)   (x+1,y)

(x-1,y-1) (x,y-1) (x+1,y-1)

It will check the top (x-1,y+1) (x,y+1) (x+1,y+1) bottom(x-1,y-1) (x,y-1) (x+1,y-1) sides(x+1,y+1) (x+1,y) (x+1,y-1) , (x-1,y+1) (x-1,y) (x-1,y-1) , the diagonals and the ones going through the middle(x,y).

my code so far is:

   public int checkWinning() {
     for(int a = 1; a < size-1; a++){
        for(int b = 1; b < size-1; b++){
            if (board[a][b] == board[a+1][b] && board[a][b] == board[a-1][b]){
                return board[a][b];
            }else if(board[a][b] == board[a][b+1] && board[a][b] == board[a][b-1]){
                return board[a][b];
            }else if(board[a][b] == board[a+1][b-1] && board[a][b] == board[a-1][b+1]){
                return board[a][b];
            }else if(board[a][b] == board[a+1][b+1] && board[a][b] == board[a-1][b-1]){
                return board[a][b];
            }
        }
    }
    for(int d = 1; d < size-1; d++){
        if (board[0][d] == board[0][d-1] && board[0][d] == board[0][d+1]){
            return board[0][d];
        } else if (board[size-1][d] == board[size-1][d-1] && board[size-1][d] == board[size-1][d+1]){
            return board[size-1][d];
        }
    }

    for(int c = 1; c < size-1; c++){
        if (board[c][0] == board[c-1][0] && board[c][0] == board[c+1][0]){
            return board[c][0];
        }else if(board[c][size-1] == board[c-1][size-1] && board[c][size-1] == board[c+1][size-1]){
            return board[c][size-1];
            }
        }   
    return 0;
}

where the first section is where I check the ones through the middle and diagonals. the second section I check the top an bottom and the top and the thrid section checks the sides.

When it returns 0 is means that there are no winner yet.

@override
public void checkResult() {
    int winner = this.board.checkWinning();
    if (winner > 0) {
        this.ui.showResult("Player "+winner+" wins!");
    }
    if (this.board.checkFull()) {
        this.ui.showResult("This is a DRAW!");
    }
}

Board[x][y] -> 2-dimensional array representing the board, The coordinates are counted from top-left (0,0) to bottom-right (size-1, size-1), board[x][y] == 0 signifies free at position (x,y), board[x][y] == i for i > 0 signifies that Player i made a move on (x,y), just so you know it.

my problem is that when i expands the board to a size larger than 3x3 the program somehow overwrites it self or a does not check every thing sides top and bottom every time, and I can't seem too se why.

Answer 1

EDIT:

played with the app for a few minutes... interesting results

java -jar tic-tac-toe.jar 5 20

It was a cats game!!

|1|1|5|5|1|3|5|3|1|5|2|5|1|1|2|
|2|3|2|3|1|5|3|5|3|2|3|1|5|2|2|
|5|4|5|4|1|5|5|4|2|1|4|5|4|2|2|
|3|2|1|5|5|5|2|4|5|3|4|1|2|4|2|
|3|4|1|2|5|4|1|1|4|5|1|3|3|4|1|
|1|5|4|4|3|2|5|1|3|5|1|3|5|3|4|
|2|5|1|4|3|3|3|5|3|1|1|4|3|4|4|
|1|4|5|1|1|5|4|5|2|4|1|1|5|4|3|
|1|3|2|1|4|2|4|3|3|4|5|2|4|3|3|
|5|1|1|3|3|4|4|4|2|2|1|4|3|2|5|
|2|2|3|1|5|5|4|1|3|5|3|2|3|3|2|
|2|4|2|4|4|1|3|1|1|3|1|2|1|2|2|
|2|5|5|1|4|3|4|5|5|4|5|3|3|5|2| 
|4|5|2|1|5|3|2|1|3|2|2|2|2|4|4|
|4|1|1|4|5|4|5|4|2|2|3|3|2|2|3|

Played 100 games:
Number wins by Player1: 0
Number wins by Player2: 0
Number wins by Player3: 0
Number wins by Player4: 0
Number wins by Player5: 0
Number of ties: 100

didn't scroll through all 100 games to find the winning board, but I thought this was interesting:

java -jar tic-tac-toe.jar 2 10

Player2 won the game!

|1|1|2|1|2|2| |2|1|2|
|2|2|2|2|2|2|2|2|2|2|
|2|1|2|2|2|1|1|1|1|1|
|1|1|1|1|2|1|2|1|1|1|
|2|2| |1|2|1|1|1|1|2|
|2|2|2|1|1|1| |1|2|2|
|2|2|1|2|2|2|2|2|1|1|
| | |2|2|2|2| |1|1|1|
|1|1|2|2|2|1|1|1|1| |
| | |1|1|1|1|1|2|1| |

Played 100 games:
Number wins by Player1: 0
Number wins by Player2: 1
Number of ties: 99

This does answer your question... but I took it a bit far... decided to implement the solution. Instead of counting matches... I just check from teh point the last player plays, if all marks in a row column and diagnal match the players, he wins.

package com.clinkworks.example;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class TicTacToe {

    private static final String TIE = "TIE";

    private static final Map<String, Integer> gamesToWinsMap = new HashMap<String, Integer>();


    /**
     * accepts input in the following format:
     * 
     * playerCount rowCount columnCount (sets the game with the n players, n columns, and n rows)
     *      - java -jar tic-tac-toe.jar 2 3 3
     * PlayerCount squareSize (defaults to a game with rows and cols the same as squareSize and the player count given)
     *       - java -jar tic-tac-toe.jar 2 3
     * PlayerCount (defaults to a 3 by 3 game)
     *       - java -jar tic-tac-toe.jar 2
     * no input (defaults to a 3 by 3 game with 2 players)
     *       - java -jar tic-tac-toe.jar
     * @param args
     */
    public static void main(String[] args) {

        int playerCount = 2;
        int rows = 3;
        int cols = 3;

        if(args.length == 3){
            playerCount = Integer.valueOf(args[0]);
            rows = Integer.valueOf(args[1]);
            cols = Integer.valueOf(args[2]);
        }

        if(args.length == 2){
            playerCount = Integer.valueOf(args[0]);
            rows = Integer.valueOf(args[1]);
            cols = rows;
        }

            if(args.length == 1){
                    playerCount = Integer.valueOf(args[0]);
            }


        for(int i = 1; i <= playerCount; i++){
            gamesToWinsMap.put("Player" + i, 0);
        }

        //lets play 100 games and see the wins and ties
        playGames(100, playerCount, rows, cols);

        for(int i = 1; i <= playerCount; i++){
            System.out.println("Number wins by Player" + i + ": " + gamesToWinsMap.get("Player" + i));
        }

        System.out.println("Number of ties: " + gamesToWinsMap.get(TIE));
    }

    public static void playGames(int gamesToPlay, int playerCount, int rows, int cols) {
        //play a new game each iteration, in our example, count = 100;
        for (int i = 0; i < gamesToPlay; i++) {
            playGame(playerCount, rows, cols);
        }
    }

    public static void playGame(int playerCount, int rows, int cols) {
        //create a new game board. this initalizes our 2d array and lets the complexity of handling that
        // array be deligated to the board object.


        Board board = new Board(playerCount, rows, cols);

        //we are going to generate a random list of moves. Heres where we are goign to store it
        List<Move> moves = new ArrayList<Move>();

        //we are creating moves for each space on the board.
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                moves.add(new Move(row, col));
            }
        }

        //randomize the move list
        Collections.shuffle(moves);

        //do each move
        for (Move move : moves) {
            board.play(move);

            if(gameOver(board)){
                break;
            }
        }
    }

    public static boolean gameOver(Board board){
        if (board.whoWon() != null) {
            System.out.println(board.whoWon() + " won the game!");
            System.out.println(board);

            Integer winCount = gamesToWinsMap.get(board.whoWon());
            winCount = winCount == null ? 1 : winCount + 1;

            gamesToWinsMap.put(board.whoWon(), winCount);

            return true;

        } else if (board.movesLeft() == 0) {
            System.out.println("It was a cats game!!");
            System.out.println(board);

            Integer tieCount = gamesToWinsMap.get(TIE);
            tieCount = tieCount == null ? 1 : tieCount + 1;
            gamesToWinsMap.put(TIE, tieCount);

            return true;
        }

        return false;
    }

    public static class Move {
        private int row;
        private int column;

        public Move(int row, int column) {
            this.row = row;
            this.column = column;
        }

        public int getRow() {
            return row;
        }

        public int getColumn() {
            return column;
        }

    }

    public static class Board {

        private final int rowSize;
        private final int columnSize;
        private final Integer[][] gameBoard;
        private int playerCount;
        private int currentPlayer;
        private String winningPlayer;

        public Board() {
            gameBoard = new Integer[3][3];
            currentPlayer = 1;
            winningPlayer = null;
            this.rowSize = 3;
            this.columnSize = 3;
            playerCount = 2;
        }


        public Board(int players) {
            gameBoard = new Integer[3][3];
            currentPlayer = 1;
            winningPlayer = null;
            this.rowSize = 3;
            this.columnSize = 3;
            playerCount = players;
        }

        public Board(int rowSize, int columnSize) {
            gameBoard = new Integer[rowSize][columnSize];
            currentPlayer = 1;
            winningPlayer = null;
            playerCount = 2;
            this.rowSize = rowSize;
            this.columnSize = columnSize;
        }            

        public Board(int players, int rowSize, int columnSize) {
            gameBoard = new Integer[rowSize][columnSize];
            currentPlayer = 1;
            winningPlayer = null;
            playerCount = players;
            this.rowSize = rowSize;
            this.columnSize = columnSize;
        }



        /**
        * 
        * @return the amount of empty spaces remaining on the game board, or if theres a winning player, zero.
        */
        public int movesLeft() {

            if(whoWon() != null){
                return 0;
            }

            int moveCount = 0;
            for (int x = 0; x < getRowSize(); x++) {
                for (int y = 0; y < getColumnSize(); y++) {
                    moveCount += getMoveAt(x, y) == null ? 1 : 0;
                }
            }
            return moveCount;
        }

        /**
        * If someone won, this will return the winning player.
        * 
        * @return the winning player
        */
        public String whoWon() {
            return winningPlayer;
        }

        /**
        * This move allows the next player to choose where to place their mark.
        * 
        * @param row
        * @param column
        * @return if the game is over, play will return true, otherwise false.
        */
        public boolean play(Move move) {

            if (!validMove(move)) {
                // always fail early
                throw new IllegalStateException("Player " + getCurrentPlayer() + " cannot play at " + move.getRow() + ", " + move.getColumn() + "\n" + toString());
            }

            doMove(move);

            boolean playerWon = isWinningMove(move);

            if (playerWon) {
                winningPlayer = "Player" + getCurrentPlayer();
                return true;
            }

            shiftPlayer();

            boolean outOfMoves = movesLeft() <= 0;

            return outOfMoves;
        }

        public int getRowSize() {
            return rowSize;
        }

        public int getColumnSize() {
            return columnSize;
        }

        public int getCurrentPlayer() {
            return currentPlayer;
        }

        public Integer getMoveAt(int row, int column) {
            return gameBoard[row][column];
        }

        private void doMove(Move move) {
            gameBoard[move.getRow()][move.getColumn()] = getCurrentPlayer();
        }

        private void shiftPlayer() {
            if(getCurrentPlayer() == getPlayerCount()){
                currentPlayer = 1;
            }else{
                currentPlayer++;
            }
        }

        private int getPlayerCount() {
            return playerCount;
        }


        private boolean validMove(Move move) {
            boolean noMoveAtIndex = false;
            boolean indexesAreOk = move.getRow() >= 0 || move.getRow() < getRowSize();
            indexesAreOk = indexesAreOk && move.getColumn() >= 0 || move.getColumn() < getColumnSize();
            if (indexesAreOk) {
                noMoveAtIndex = getMoveAt(move.getRow(), move.getColumn()) == null;
            }
            return indexesAreOk && noMoveAtIndex;
        }

        private boolean isWinningMove(Move move) {
            // since we check to see if the player won on each move
            // we are safe to simply check the last move
            return winsDown(move) || winsAcross(move) || winsDiagnally(move);
        }

        private boolean winsDown(Move move) {
            boolean matchesColumn = true;

            for (int i = 0; i < getColumnSize(); i++) {
                Integer moveOnCol = getMoveAt(move.getRow(), i);
                if (moveOnCol == null || getCurrentPlayer() != moveOnCol) {
                    matchesColumn = false;
                    break;
                }
            }

            return matchesColumn;
        }

        private boolean winsAcross(Move move) {
            boolean matchesRow = true;
            for (int i = 0; i < getRowSize(); i++) {
                Integer moveOnRow = getMoveAt(i, move.getColumn());
                if (moveOnRow == null || getCurrentPlayer() != moveOnRow) {
                    matchesRow = false;
                    break;
                }
            }
            return matchesRow;
        }

        private boolean winsDiagnally(Move move) {
            // diagnals we only care about x and y being teh same...
            // only perfect squares can have diagnals
            // so we check (0,0)(1,1)(2,2) .. etc
            boolean matchesDiagnal = false;
            if (isOnDiagnal(move.getRow(), move.getColumn())) {
                matchesDiagnal = true;
                for (int i = 0; i < getRowSize(); i++) {
                    Integer moveOnDiagnal = getMoveAt(i, i);
                    if (moveOnDiagnal == null || moveOnDiagnal != getCurrentPlayer()) {
                        matchesDiagnal = false;
                        break;
                    }
                }
            }

            return matchesDiagnal;
        }

        private boolean isOnDiagnal(int x, int y) {
            if (boardIsAMagicSquare()) {
                return x == y;
            } else {
                return false;
            }
        }

        private boolean boardIsAMagicSquare() {
            return getRowSize() == getColumnSize();
        }

        public String toString() {
            StringBuffer stringBuffer = new StringBuffer();
            for(int y = 0; y < getColumnSize(); y++) {
                for(int x = 0; x < getRowSize(); x++) {
                    Integer move = getMoveAt(x, y);
                        String moveToPrint = "";
                    if (move == null) {
                        moveToPrint = " ";
                    } else {
                        moveToPrint = move.toString();
                    }
                    stringBuffer.append("|").append(moveToPrint);
                }
                stringBuffer.append("|\n");
            }
            return stringBuffer.toString();
        }
    }
}

Answer 2

You can simplify this a fair amount by breaking the logic up a bit.

First realize that you only need to check for a win around the piece you just placed.

Now we need a way to check whether that move is a winner.

First we need a simple function to check whether a cell matches a given value, returning true if its within bounds and matches.

 private boolean cellMatches(int x, int y, int val) {
    if (x<0||x>boardWidth)
       return false;
    if (y<0||y>boardHeight)
       return false;
    return board[x][y]==val;
 }

Now a function that you give a starting position (x and y) and a delta (dx, dy) and it checks up to two cells in that direction returning a count of how many in a row matched value. The for loop may be overkill for two checks but it would easily allow you to expand up to longer lines being used.

private int countMatches(int x, int y, int dx, int dy, int val) {
   int count = 0;
   for (int step=1;step<=2;step++) {
     if (cellMatches(x+dx*step, y+dy*step, val) {
       count++;
     } else {
       return count;
     }
   }
   return count;
}

Now we can use the previous method. When we place a new piece we can just count out in each matching pair of directions. The combined count is the total number in a row. (i.e. two in a row top + 1 bot = a total run length of 4). If any of those run lengths is three then it is a winning move.

private boolean makeMove(int x, int y, int val) {
   board[x][y] = val;
   int runlength=countMatches(x,y,0,1,val) + countMatches(x,y,0,-1,val);
   if (runLength >= 2)
      return true;
   int runlength=countMatches(x,y,1,0,val) + countMatches(x,y,-1,0,val);
   if (runLength >= 2)
      return true;
   int runlength=countMatches(x,y,1,1,val) + countMatches(x,y,-1,-1,val);
   if (runLength >= 2)
      return true;
   int runlength=countMatches(x,y,1,-1,val) + countMatches(x,y,-1,1,val);
   if (runLength >= 2)
      return true;
   return false;
}

Note that because we need to count the center piece that we placed we just need a run length of two or more.

Answer 3

I have to revise my answer. If you want to have three in a row regardless of your board size, your loop code might be sufficient, but you are always checking whether the values of the fields are the same but never make a difference between empty and non-empty fields.

So “empty” can win too, which would effectively hide a possible win of a player. In other words, your code does not work correctly, even for a field size of three. You didn’t test it enough.

If I initialize the board as

int[][] board={
    { 1, 1, 1 },
    { 0, 0, 0 },
    { 0, 0, 0 },
};

your code returns 0 as the second row contains three zeros. I assumed that 0 represents the empty field but the actual value for “empty” doesn’t matter. You have to exclude empty fields from the three-in-a-row check.