Calculating Threats

Question

I have to implement connect4 with a simulated intelligence. It already works, but it is very slow. We have to get al the threats of the two Player. a threat is 3 coins ina row with a empty field between or at the ends of the row. I want to calculate only the new threats after every move and delete the threats which are no longer thhreats. I wrote some methods to check every direction if there is a new threat from the last move.

private Field row(int row, int column, String Player) {
        Field field = null;
        if(column - 1 >= 0 && column + 1 < board.getColumn() && board.getValue(row, column-1).equals(Player)
                && board.getValue(row, column+1).equals(Player)) {
            if(column -2 >= 0 &&board.getValue(row, column-2).equals(" ")) {
                return field = new Field(row, column -2);
            }
            else if(column + 2 < board.getColumn()&& board.getValue(row, column+2).equals(" ")) {
                return field = new Field(row, column +2);
            }
        }

        else if(column - 2 >= 0  && board.getValue(row, column-1).equals(Player)
                && board.getValue(row, column-2).equals(Player)) {
            if(column -3 >= 0 &&board.getValue(row, column-3).equals(" ")) {
                return field =  new Field(row, column -3);
            }
            else if(column +1 < board.getColumn()&& board.getValue(row, column+1).equals(" ")) {
                return field =  new Field(row, column +1);
            }
        }
        else if(column +2 < board.getColumn()  && board.getValue(row, column+1).equals(Player)
                && board.getValue(row, column+2).equals(Player)) {
            if(column -1 >= 0 &&board.getValue(row, column-1).equals(" ")) {
                return field =  new Field(row, column -1);
            }
            else if(column +3 < board.getColumn()&& board.getValue(row, column+3).equals(" ")) {
                return field =  new Field(row, column +3);
            }
        }
        else if(column - 2 >= 0  && column + 1 < board.getColumn() && board.getValue(row, column-2).equals(Player)
                && board.getValue(row, column+1).equals(Player)) {
            if(column -1 >= 0 &&board.getValue(row, column-1).equals(" ")) {
                return field = new Field(row, column -1);
            }

        }
        else if(column - 1 >= 0  && column +2 < board.getColumn() && board.getValue(row, column-1).equals(Player)
                && board.getValue(row, column+2).equals(Player)) {
            if(column +1 < board.getColumn() &&board.getValue(row, column+1).equals(" ")) {
                return field = new Field(row, column +1);
            }

        }

        else if(column - 3  >= 0 && board.getValue(row, column-2).equals(Player) && board.getValue(row, column-3).equals(Player)) {
            if(board.getValue(row, column-1).equals(" ")) {
                return new Field (row, column -1);
            }
        }
        else if(column-3 >= 0 && board.getValue(row, column-1).equals(Player) && board.getValue(row, column-3).equals(Player)) {
            if(board.getValue(row, column-2).equals(" ")) {
                return new Field(row, column - 2);
            }
        }
        else if(column + 3 < board.getColumn() && board.getValue(row, column+2).equals(Player) && board.getValue(row, column+3).equals(Player)) {
            if(board.getValue(row, column+1).equals(" ")) {
                return new Field(row, column + 1);
            }
        }
        else if(column + 3 < board.getColumn() && board.getValue(row, column+1).equals(Player) && board.getValue(row, column+3).equals(Player)) {
            if(board.getValue(row, column+2).equals(" ")) {
                return new Field(row, column +2);
            }
        }
        return field;
    }

private Field column(int row, int column, String Player) {
        Field field = null;
        if (row + 2 < board.getRow()
                && board.getValue(row + 1, column).equals(Player)
                && board.getValue(row + 2, column).equals(Player)) {
            if(row-1 >= 0 && board.getValue(row-1, column).equals(" ")) {
                return field =  new Field(row-1, column);
            }

        }
        return field;
    }

private Field diagonalRight(int row, int column, String Player) {
        Field field = null;
        if(row - 1 >= 0 && column - 1 >= 0 && row + 1 < board.getRow() && column + 1 < board.getColumn()
                && board.getValue(row+ 1, column-1).equals(Player)&& board.getValue(row-1, column+1).equals(Player)) {
            if(row + 2 < board.getRow() && column - 2 >= 0 && board.getValue(row+2, column-2).equals(" ")) {
                return field = new Field(row+2, column - 2);
            }
            else if (row - 2 >=0 && column + 2 < board.getColumn() && board.getValue(row-2, column+2).equals(" ")) {
                return field = new Field(row-2, column + 2);
            }
        }
        else if(row + 2 < board.getRow() && column - 2 >= 0 && board.getValue(row+ 1, column-1).equals(Player)&& board.getValue(row+2, column-2).equals(Player)) {
            if(row +3 < board.getRow() && column - 3 >= 0 && board.getValue(row+3, column-3).equals(" ")) {
                return field = new Field(row+3, column - 3);
            }
            else if (row - 1 >=0 && column + 1 < board.getColumn() && board.getValue(row-1, column+1).equals(" ")) {
                return field = new Field(row-1, column + 1);
            }
        }
        else if(row - 2 >= 0 && column +2 < board.getColumn() && board.getValue(row- 1, column+1).equals(Player)&& board.getValue(row-2, column+2).equals(Player)) {
            if(row -3>= 0 && column + 3 < board.getColumn() && board.getValue(row-3, column+3).equals(" ")) {
                return field = new Field(row-3, column +3);
            }
            else if (row + 1 < board.getRow() && column -1 >=0 && board.getValue(row+1, column-1).equals(" ")) {
            return field = new Field(row+1, column -1);
            }
        }

        else if(row - 2 >= 0 && column - 1 >= 0 && row + 1 < board.getRow() && column + 2 < board.getColumn()
                && board.getValue(row+ 1, column-1).equals(Player)&& board.getValue(row-2, column+2).equals(Player)) {


             if (row - 1 >=0 && column + 1 < board.getColumn() && board.getValue(row-1, column+1).equals(" ")) {
                return field = new Field(row-1, column + 1);
            }
        }
        else if(row + 2 < board.getRow() && column -2 >= 0 && row - 1 >= 0 && column + 1 < board.getColumn()
                && board.getValue(row+ 2, column-2).equals(Player)&& board.getValue(row-1, column+1).equals(Player)) {


             if (row + 1 < board.getRow() && column - 1 >= 0 && board.getValue(row+1, column-1).equals(" ")) {
                return field = new Field(row+1, column - 1);
            }
        }

        else if(row + 3 < board.getRow() && column  + 3 < board.getColumn() && board.getValue(row + 2, column+2).equals(Player) && board.getValue(row+3, column+3).equals(Player)) {
            if( board.getValue(row+1, column+1).equals(" ")) {
                return new Field(row+1, column +1);
            }

        }
        else if(row + 3 < board.getRow() && column + 3 < board.getColumn() && board.getValue(row+3, column+3).equals(Player) && board.getValue(row+1, column+1).equals(Player)) {
            if(board.getValue(row+2, column+2).equals(" ")) {
                return new Field (row +2, column + 2);
            }
        }
        else if(row - 3 >= 0 && column - 3 >= 0 && board.getValue(row-3, column-3).equals(Player) && board.getValue(row-2, column-2).equals(Player)) {
            if(board.getValue(row-1, column-1).equals(" ")) {
                return new Field(row-1, column -1);
            }
        }
        else if(row-3 >=0 && column -3>= 0 && board.getValue(row-3, column-3).equals(Player) && board.getValue(row-1, column-1).equals(Player)) {
            if(board.getValue(row-2, column-2).equals(" ")) {
                return new Field (row-2, column - 2);
            }
        }
        return field ;

    }

private Field diagonalLeft(int row, int column, String Player) {
        Field field = null;
        if(row - 1 >= 0 && column - 1 >= 0 && row + 1 < board.getRow() && column + 1 < board.getColumn()
                && board.getValue(row+ 1, column+1).equals(Player)&& board.getValue(row-1, column-1).equals(Player)) {
            if(row + 2 < board.getRow() && column + 2 < board.getColumn() && board.getValue(row+2, column+2).equals(" ")) {
                return field = new Field(row+2, column + 2);
            }
            else if (row - 2 >=0 && column - 2 >=0 && board.getValue(row-2, column-2).equals(" ")) {
                return field = new Field(row-2, column - 2);
            }
        }
        else if(row + 2 < board.getRow() && column + 2 < board.getColumn()&& board.getValue(row+ 1, column+1).equals(Player)&& board.getValue(row+2, column+2).equals(Player)) {
            if(row +3 < board.getRow() && column + 3 < board.getColumn() && board.getValue(row+3, column+3).equals(" ")) {
                return field = new Field(row+3, column + 3);
            }
            else if (row - 1 >=0 && column - 1 >=0 && board.getValue(row-1, column-1).equals(" ")) {
                return field = new Field(row-1, column - 1);
            }
        }
        else if(row - 2 >= 0 && column -2 >=0 && board.getValue(row- 1, column-1).equals(Player)&& board.getValue(row-2, column-2).equals(Player)) {
            if(row -3>= 0 && column - 3 >= 0 && board.getValue(row-3, column-3).equals(" ")) {
                return field = new Field(row-3, column -3);
            }
            else if (row + 1 < board.getRow() && column +1 <board.getColumn() && board.getValue(row+1, column+1).equals(" ")) {
                return field = new Field(row+1, column +1);
            }
        }

        else if(row - 1 >= 0 && column - 1 >= 0 && row + 2 < board.getRow() && column + 2 < board.getColumn()
                && board.getValue(row- 1, column-1).equals(Player)&& board.getValue(row+2, column+2).equals(Player)) {


             if (row + 1 < board.getRow() && column + 1 < board.getColumn() && board.getValue(row+1, column+1).equals(" ")) {
                return field = new Field(row+1, column + 1);
            }
        }
        else if(row + 1 < board.getRow() && column -2 >= 0 && row - 2 >= 0 && column + 1 < board.getColumn()
                && board.getValue(row- 2, column-2).equals(Player)&& board.getValue(row+1, column+1).equals(Player)) {


             if (row - 1 >= 0 && column - 1 >= 0 && board.getValue(row-1, column-1).equals(" ")) {
                return field = new Field(row-1, column - 1);
            }
        }

        else if(row - 3 >=0 && column  + 3 < board.getColumn() && board.getValue(row - 2, column+2).equals(Player) && board.getValue(row-3, column+3).equals(Player)) {
            if( board.getValue(row-1, column+1).equals(" ")) {
                return new Field(row-1, column +1);
            }

        }
        else if(row - 3 >=0 && column + 3 < board.getColumn() && board.getValue(row-3, column+3).equals(Player) && board.getValue(row-1, column+1).equals(Player)) {
            if(board.getValue(row-2, column+2).equals(" ")) {
                return new Field (row -2, column + 2);
            }
        }
        else if(row + 3 < board.getRow() && column - 3 >= 0 && board.getValue(row+3, column-3).equals(Player) && board.getValue(row+2, column-2).equals(Player)) {
            if(board.getValue(row+1, column-1).equals(" ")) {
                return new Field(row+1, column -1);
            }
        }
        else if(row+3 < board.getRow() && column -3>= 0 && board.getValue(row+3, column-3).equals(Player) && board.getValue(row+1, column-1).equals(Player)) {
            if(board.getValue(row+2, column-2).equals(" ")) {
                return new Field (row+2, column - 2);
            }
        }
        return field;
    }

the methods are really high and there is a mistake as well.. but i can't find it. Could you give me some tips how I can implement these methods better? Thank you

edit 1:

perhebs you should only have look over the first method. I take the last move and check if tehre is any threat which includes the last move. so I chek if there are two more coins in the row of the same Player which create a threat. the big A is the last Move and I want to check if tehre are the small a so that they create a threat:

| |a|A |a| | | | for example I check if the field right of A is an a and the field left of A is an a, and if this is true I check if there is a empty field arround it so that you could get 4 in a row

| | |A |a|a| | |

|a|a|A | | | | |

| | |A |a| |a| |

| | |A | | |a|a|

and so on.. i check every possibility of a threat. And after the row I do it for the column and for the diagonal

Do you see any better solution?

edit 2:

private Field row(int row, int column, int Player) {
        Field field = null;
        int j = 0;
        boolean check = false;
        if(column + 3 < board.getColumn()) {
            for(int i = column; i< column + 4; i++) {
                if(board.getValue(row, i).equals(Player)){
                    j++;
                }
                else if(board.getValue(row, i).equals(" ") && check == false) {
                    j++;
                    check = true;
                    field = new Field(row,i);
                }
            }
            if(j == 4) {
                return field;
            }
        }
        return null;
    }

I will call the method from 4 different points. do you this it will work?

I think this is too much code for anyone to go over. Please add an explanation of what your logic is doing and the general approach you've taken in the solution. — juan.facorro, Mar 11 '14 at 13:33
if you post your algorithm (short as compared to source code) we will be in a better possition to help — Srinath Ganesh, Mar 11 '14 at 13:34

score 2 · Answer 1 · answered Mar 11 '14 at 13:42

2

Why in the name of everything that is holy do you have the same bloody code copy-pasted N times? The only difference is that the bloody numbers change. Rewrite them in a loop, then there's only a single point to check for correctness.

answered Mar 11 '14 at 13:42

Tassos Bassoukos

16,017
2
36
40

how can I write that in a loop? – user3406330 Mar 11 '14 at 13:44
Given x,y,dx,dy,n, check that forall i in 0..n the tile in (x+idx,y+idy) has the value of the target player. When (dx,dy)=(1,0) it's a row, when (0,1) it's a column. What are (1,1) and (-1,1)? – Tassos Bassoukos Mar 11 '14 at 13:56

score 2 · Answer 2 · edited May 23 '17 at 12:27

I think your code would be a lot nicer if you had a different concept, eg:

1, methods for checking directions: diagonalChecker (2x), verticalChecker, horizontalChecker. These methods are checking the threat from one direction in a loop (like coulmn is x, row is

for(row = n; row<n+4; row++) {
...
}

2, break from these methods if you know they won't be a threat

3, invoke these methods from different starting points around your new coin. Possibly with a loop.

+1: maybe you should check this solution and get some ideas

If your solution is clearer it will be easier to spot the errors too.

Update to your update: I would do roughly something like this (didn't tested, just for the idea):

It would be nicer to use enum for the different players.

enum Player {
    RED, BLUE
}

Make rowCheck as simple as it can be:

private boolean rowCheck(int row, int column, Player player) {
    boolean isThreeOfTheSameInOneRow = true;

    for (int i = column; i < column + 4; i++) {
        if (!boundariesCheck(row, i) || !board.getValue(row, i).equals(player)) {
      isThreeOfTheSameInOneRow = false;
      break;
    }

    return isThreeOfTheSameInOneRow;
}

This way you're checking the boundaries in one place. You might want to split it in 2 (column and row).

private boolean boundariesCheck(int row, int column) {
        boolean result = false;
        if (0 < column && column < board.getColumn() && 0 < row && row < board.getRow()) {
            result = true;
        }
        return result;
    }

@user3406330 : I just edited my answer, pls check the +1 point with the link, I think you can find a nice solution there. Hope I could help! — user2424380, Mar 11 '14 at 13:59

score 0 · Answer 3 · answered Mar 11 '14 at 14:23

You could simplify these things a lot. Primarily by using for-loops and maybe some utility methods that do the bounds checking.

At a larger scope: What you have been doing there is only one small step of a "real artificial intelligence". In fact, when you want to write an AI for such a simple board game, there are only 3 things that must be possible:

You must be able to do a move
You must be able to evaluate the current situation (That is: Is it good or bad for a player?)
You must be able to undo a move

These three, simple methods already allow you to implement the MiniMax algorithm (http://en.wikipedia.org/wiki/Minimax). For a simple game like "Connect Four", even the simplest implementation of this algorithm will easily defeat any casual player. (And... are there serious players of "Connect Four"?). It may even be extended to use Alpha-Beta-Pruning (http://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning) if you want a more sophisticated AI.

However: You might want to consider combining the check whether a player has already won, and the check that you attempted there - namely whether a player could win if he placed is piece at a particular position. When you already have a method that checks whether a player has won, you can check whether a player could win by

"Virtually" performing the move in question
Checking if the player has won
Undoing the "virtual" move

An implementation of this could roughly look like this. (Not optimized for elegance or efficiency, but for simplicity and hopefully intuitiveness...)

private boolean canWinByPlacingOn(String player, int r, int c)
{
    if (board.getValue(r, c).equals(" "));
    {
        board.setValue(r, c, player);
        boolean hasWon = hasWon(player);
        board.setValue(r, c, " ");
        if (hasWon)
        {
            return true;
        }
    }
    return false;
}

private boolean hasWon(String player)
{
    int maxR = board.getRow()-4;
    int maxC = board.getColumn()-4;
    for (int r=0; r<maxR; r++)
    {
        for (int c=0; c<maxC; c++)
        {
            if (startsLineAt(player, r, c, 1, 0))
            {
                return true;
            }
            if (startsLineAt(player, r, c, 0, 1))
            {
                return true;
            }
            if (startsLineAt(player, r, c, 1, 1))
            {
                return true;
            }
        }
    }
    return false;
}

private boolean startsLineAt(String player, int r, int c, int dr, int dc)
{
    for (int i=0; i<4; i++)
    {
        String current = board.getValue(r, c);
        if (!current.equals(player))
        {
            return false;
        }
        r += dr;
        c += dc;
    }
    return true;
}

Calculating Threats

3 Answers3