Connect-n time!

Question

https://en.wikipedia.org/wiki/Connect_Four

Does anyone remember the 2 player game connect 4? For those who don't it was a 6x7 board that stands vertical on a surface. The goal of connect 4 is to, well connect 4! The connection is counted if it is horizontal, diagonal, or vertical. You place your pieces on the board by inserting a piece at the top of a column where it falls to the bottom of that column. Our rules change 3 things in connect 4.

• Change #1 Winning is defined as the player with the most points. You get points by connecting 4 like in the rules - more on that later.
• Change #2 You have 3 players each round.
• Change #3 The board size is 9x9.

Scoring:

Score is based on how many you get in a row. If you have a 4 in a row group you get 1 point. If you have a 5 in a row group you get 2 points, 6 in a row 3 and so on.

Examples:

_{Note o and x are replaced with # and ~ respectively, for better contrast}

Example of empty board: (all examples are 2 player standard size board)

   a b c d e f g
6 | | | | | | | |
5 | | | | | | | |
4 | | | | | | | |
3 | | | | | | | |
2 | | | | | | | |
1 |_|_|_|_|_|_|_|

If we drop a piece in coll d, it will land in location1d.

   a b c d e f g
6 | | | | | | | |
5 | | | | | | | |
4 | | | | | | | |
3 | | | | | | | |
2 | | | | | | | |
1 |_|_|_|#|_|_|_|

If we now drop a piece in coll d again, it will land in location 2d. Here are examples of 4 in a row positions:

   a b c d e f g
6 | | | | | | | |
5 | | | | | | | |
4 | | | |~| | | |
3 | | |~|#| | | |
2 | |~|#|~| |#| |
1 |~|#|~|#|_|#|_|

In this case x gets 1 point diagonally (1a 2b 3c 4d).

  a b c d e f g
6 | | | | | | | |
5 | | | | | | | |
4 | | | |#| | | |
3 | | | |#| | | |
2 | | | |#| | | |
1 |_|~|_|#|~|_|~|

In this case, o gets 1 point vertically (1d 2d 3d 4d).

   a b c d e f g
6 | | | | | | | |
5 | | | | | | | |
4 | | | | | | | |
3 | | | | | | | |
2 | | |#|#|#|#| |
1 |_|_|~|~|~|~|~|

In this case o gets 2 points horizontally (1c 1d 1e 1f 1g) and x gets 1 point horizontally (2c 2d 2e 2f).

   a b c d e f g
6 | | |#| | | | |
5 | | |#| | | | |
4 | | |#| | | | |
3 | | |#| | |~| |
2 |~| |#| | |#|~|
1 |~|_|#|~| |~|~|

This time x gets 3 points for a 6 in a row (1c 2c 3c 4c 5c 6c).

Input / Output

You will have access to the board via a 2d array. Each location will be represented with an int representing a player id. You will also have your player id passed to your function. You make your move by returning which coll you want to drop your piece into. Each round 3 players will be chosen to play. At the end of the game, all players will have played an even amount of games.

For the moment 100k rounds will be run (note this takes a long time, you may want to reduce it for fast turnaround testing). Overall the winner is the player with the most wins.

The controller can be found here: https://github.com/JJ-Atkinson/Connect-n/tree/master.

Writing a bot:

To write a bot you must extend the Player class. Player is abstract and has one method to implement, int makeMove(void). In makeMove you will decide which coll you would like to drop your piece into. If you chose an invalid coll (e.g. coll does not exist, coll is filled already), your turn will be skipped. In the Player class you have many useful helper methods. A listing of the most important ones follows:

• boolean ensureValidMove(int coll): Return true if the coll is on the board and the coll is not filled yet.
• int[] getBoardSize(): Return a int array where [0] is the number of columns, and [1] is the number of rows.
• int[][] getBoard(): Return a copy of the board. You should access it like this: [coll number][row number from bottom].
• To find the rest, look at the Player class.
• EMPTY_CELL: The value of an empty cell

Since this will be multi-threaded, I have also included a random function if you need it.

Debugging your bot:

I have included some things in the controller to make it simpler to debug a bot. The first one is Runner#SHOW_STATISTICS. If this is enabled, you will see a printout of player groups played, including a count of bot wins. Example:

OnePlayBot, PackingBot, BuggyBot, 
OnePlayBot -> 6
PackingBot -> 5
BuggyBot -> 3
Draw -> 1

You can also make a custom game with the connectn.game.CustomGame class, you can see the scores and winner of each round. You can even add yourself to the mix with UserBot.

Adding your bot:

To add your bot to the lineup, go to the PlayerFactory static block and add the following line:

playerCreator.put(MyBot.class, MyBot::new);

Other things to note:

• The simulations are multi-threaded. If you want to turn that off, go to Runner#runGames() and comment this line (.parallel()).
• To change the number of games, set Runner#MINIMUM_NUMBER_OF_GAMES to your liking.

Added later:

• Communication among bots is disallowed.

Related: Play Connect 4!

================================

Scoreboard: (100 000 games)

MaxGayne -> 22662
RowBot -> 17884
OnePlayBot -> 10354
JealousBot -> 10140
Progressive -> 7965
Draw -> 7553
StraightForwardBot -> 7542
RandomBot -> 6700
PackingBot -> 5317
BasicBlockBot -> 1282
BuggyBot -> 1114
FairDiceRoll -> 853
Steve -> 634

================================

Answer 1

MaxGayne

This bot assigns a score to each position, based mainly on the length of connected parts. It looks 3 moves deep inspecting 3 best looking moves at each stage, and chooses the one with the maximum expected score.

package connectn.players;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class MaxGayne extends Player {
    private static final int PLAYERS = 3;

    private static class Result {
        protected final int[] score;
        protected int lastCol;

        public Result(int[] score, int lastCol) {
            super();
            this.score = score;
            this.lastCol = lastCol;
        }

        public Result() {
            this(new int[PLAYERS], -1);
        }

        public Result(Result other) {
            this(new int[PLAYERS], other.lastCol);
            System.arraycopy(other.score, 0, this.score, 0, PLAYERS);
        }

        public int getRelativeScore(int player) {
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < PLAYERS; ++ i) {
                if (i != player && score[i] > max) {
                    max = score[i];
                }
            }
            return score[player] - max;
        }
    }

    private static class Board extends Result {
        private final int cols;
        private final int rows;
        private final int[] data;
        private final int[] used;

        public Board(int cols, int rows) {
            super();
            this.cols = cols;
            this.rows = rows;
            this.data = new int[cols * rows];
            Arrays.fill(this.data, -1);
            this.used = new int[cols];
        }

        public Board(Board other) {
            super(other);
            this.cols = other.cols;
            this.rows = other.rows;
            this.data = new int[cols * rows];
            System.arraycopy(other.data, 0, this.data, 0, this.data.length);
            this.used = new int[cols];
            System.arraycopy(other.used, 0, this.used, 0, this.used.length);
        }

        private void updatePartScore(int player, int length, int open, int factor) {
            switch (length) {
                case 1:
                    score[player] += factor * open;
                    break;
                case 2:
                    score[player] += factor * (100 + open * 10);
                    break;
                case 3:
                    score[player] += factor * (10_000 + open * 1_000);
                    break;
                default:
                    score[player] += factor * ((length - 3) * 1_000_000 + open * 100_000);
                    break;
            }
        }

        private void updateLineScore(int col, int row, int colOff, int rowOff, int length, int factor) {
            int open = 0;
            int player = -1;
            int partLength = 0;
            for (int i = 0; i < length; ++ i) {
                int newPlayer = data[(col + i * colOff) * rows + row + i * rowOff];
                if (newPlayer < 0) {
                    if (player < 0) {
                        if (i == 0) {
                            open = 1;
                        }
                    } else {
                        updatePartScore(player, partLength, open + 1, factor);
                        open = 1;
                        player = newPlayer;
                        partLength = 0;
                    }
                } else {
                    if (newPlayer == player) {
                        ++ partLength;
                    } else {
                        if (player >= 0) {
                            updatePartScore(player, partLength, open, factor);
                            open = 0;
                        }
                        player = newPlayer;
                        partLength = 1;
                    }
                }
            }
            if (player >= 0) {
                updatePartScore(player, partLength, open, factor);
            }
        }

        private void updateIntersectionScore(int col, int row, int factor) {
            updateLineScore(col, 0, 0, 1, rows, factor);
            updateLineScore(0, row, 1, 0, cols, factor);
            if (row > col) {
                updateLineScore(0, row - col, 1, 1, Math.min(rows - row, cols), factor);
            } else {
                updateLineScore(col - row, 0, 1, 1, Math.min(cols - col, rows), factor);
            }
            if (row > cols - col - 1) {
                updateLineScore(cols - 1, row - (cols - col - 1), -1, 1, Math.min(rows - row, cols), factor);
            } else {
                updateLineScore(col + row, 0, -1, 1, Math.min(col + 1, rows), factor);
            }
        }

        private void updatePiece(int player, int col, int row) {
            updateIntersectionScore(col, row, -1);
            data[col * rows + row] = player;
            ++ used[col];
            lastCol = col;
            updateIntersectionScore(col, row, 1);
        }

        public Board updatePiece(int player, int col) {
            int row = used[col];
            if (row >= rows) {
                return null;
            } else {
                Board result = new Board(this);
                result.updatePiece(player, col, row);
                return result;
            }
        }

        private void updateBoard(int[][] board) {
            for (int col = 0; col < cols; ++ col) {
                for (int row = 0; row < rows; ++ row) {
                    int oldPlayer = data[col * rows + row];
                    int newPlayer = board[col][row] - 1;
                    if (newPlayer < 0) {
                        if (oldPlayer < 0) {
                            break;
                        } else {
                            throw new RuntimeException("[" + col + ", " + row + "] == "  + oldPlayer + " >= 0");
                        }
                    } else {
                        if (oldPlayer < 0) {
                            updatePiece(newPlayer, col, row);
                        } else if (newPlayer != oldPlayer) {
                            throw new RuntimeException("[" + col + ", " + row + "] == "  + oldPlayer + " >= " + newPlayer);
                        }
                    }
                }
            }
        }

        private Result bestMove(int depth, int player) {
            List<Board> boards = new ArrayList<>();
            for (int col = 0; col < cols; ++ col) {
                Board board = updatePiece(player, col);
                if (board != null) {
                    boards.add(board);
                }
            }
            if (boards.isEmpty()) {
                return null;
            }
            Collections.sort(boards, (o1, o2) -> Integer.compare(o2.getRelativeScore(player), o1.getRelativeScore(player)));
            if (depth <= 1) {
                return new Result(boards.get(0).score, boards.get(0).lastCol);
            }
            List<Result> results = new ArrayList<>();
            for (int i = 0; i < 3 && i < boards.size(); ++ i) {
                Board board = boards.get(i);
                Result result = board.bestMove(depth - 1, (player + 1) % PLAYERS);
                if (result == null) {
                    results.add(new Result(board.score, board.lastCol));
                } else {
                    results.add(new Result(result.score, board.lastCol));
                }
            }
            Collections.sort(results, (o1, o2) -> Integer.compare(o2.getRelativeScore(player), o1.getRelativeScore(player)));
            return results.get(0);
        }
    }

    private Board board = null;

    @Override
    public int makeMove() {
        if (board == null) {
            int[][] data = getBoard();
            board = new Board(data.length, data[0].length);
            board.updateBoard(data);
        } else {
            board.updateBoard(getBoard());
        }

        Result result = board.bestMove(3, getID() - 1);
        return result == null ? -1 : result.lastCol;
    }
}

Answer 2

RowBot

Looks in all directions and determines the optimal column. Tries to connect his pieces, while not letting his opponents do the same.

package connectn.players;

import connectn.game.Game;
import java.util.ArrayList;
import java.util.List;

public class RowBot extends Player {

    @Override
    public int makeMove() {
        int[][] board = getBoard();
        int best = -1;
        int bestScore = -10;
        for (int col = 0; col < board.length; col++) {
            if (ensureValidMove(col)) {
                int score = score(board, col, false);
                score -= score(board, col, true);
                if (score > bestScore) {
                    bestScore = score;
                    best = col;
                }
            }
        }
        return best;
    }

    private int score(int[][] board, int col, boolean simulateMode) {
        int me = getID();
        int row = getLowestEmptyRow(board, col);
        List<Score> scores = new ArrayList<>();
        if (!simulateMode) {
            scores.add(getScoreVertical(board, col, row));
        } else {
            row += 1;
        }
        scores.addAll(getScoreHorizontal(board, col, row));
        scores.addAll(getScoreDiagonal(board, col, row));
        int score = 0;
        for (Score s : scores) {
            if (s.player == me) {
                score += s.points > 2 ? 100 : s.points * 5;
            } else if (s.player != Game.EMPTY_CELL) {
                score += s.points > 2 ? 50 : 0;
            } else {
                score += 1;
            }
        }
        return score;
    }

    private Score getScoreVertical(int[][] board, int col, int row) {
        return getScore(board, col, row, 0, -1);
    }

    private List<Score> getScoreHorizontal(int[][] board, int col, int row) {
        List<Score> scores = new ArrayList<>();

        Score left = getScore(board, col, row, -1, 0);
        Score right = getScore(board, col, row, 1, 0);
        if (left.player == right.player) {
            left.points += right.points;
            scores.add(left);
        } else {
            scores.add(left);
            scores.add(right);
        }
        return scores;
    }

    private List<Score> getScoreDiagonal(int[][] board, int col, int row) {
        List<Score> scores = new ArrayList<>();

        Score leftB = getScore(board, col, row, -1, -1);
        Score rightU = getScore(board, col, row, 1, 1);
        Score leftBottomToRightUp = leftB;
        if (leftB.player == rightU.player) {
            leftBottomToRightUp.points += rightU.points;
        } else if (leftB.points < rightU.points || leftB.player == Game.EMPTY_CELL) {
            leftBottomToRightUp = rightU;
        }

        Score leftU = getScore(board, col, row, -1, 1);
        Score rightB = getScore(board, col, row, 1, -1);
        Score rightBottomToLeftUp = leftU;
        if (leftU.player == rightB.player) {
            rightBottomToLeftUp.points += rightB.points;
        } else if (leftU.points < rightB.points || leftU.player == Game.EMPTY_CELL) {
            rightBottomToLeftUp = rightB;
        }

        if (leftBottomToRightUp.player == rightBottomToLeftUp.player) {
            leftBottomToRightUp.points += rightBottomToLeftUp.points;
            scores.add(leftBottomToRightUp);
        } else {
            scores.add(leftBottomToRightUp);
            scores.add(rightBottomToLeftUp);
        }
        return scores;
    }

    private Score getScore(int[][] board, int initCol, int initRow, int colOffset, int rowOffset) {
        Score score = new Score();
        outerLoop: for (int c = initCol + colOffset;; c += colOffset) {
            for (int r = initRow + rowOffset;; r += rowOffset) {
                if (outside(c, r) || board[c][r] == Game.EMPTY_CELL) {
                    break outerLoop;
                }
                if (score.player == Game.EMPTY_CELL) {
                    score.player = board[c][r];
                }

                if (score.player == board[c][r]) {
                    score.points++;
                } else {
                    break outerLoop;
                }

                if (rowOffset == 0) {
                    break;
                }
            }
            if (colOffset == 0) {
                break;
            }
        }
        return score;
    }

    private boolean outside(int col, int row) {
        return !boardContains(col, row);
    }

    private int getLowestEmptyRow(int[][] board, int col) {
        int[] rows = board[col];
        for (int row = 0; row < rows.length; row++) {
            if (rows[row] == Game.EMPTY_CELL){
                return row;
            }
        }
        return -1;
    }

    private class Score {
        private int player = Game.EMPTY_CELL;
        private int points = 0;
    }
}

Answer 3

OnePlayBot

This bot has only one play - place its piece in the leftmost cell that is valid. Oddly enough it does pretty good ;)

static class OnePlayBot extends Player {
    @Override
    int makeMove() {
        int attemptedMove = 0;

        for (int i = 0; i < getBoardSize()[0]; i++)
            if (ensureValidMove(i)) {
                attemptedMove = i;
                break;
            }

        return attemptedMove;
    }
}

Answer 4

RandomBot

Just put a piece anywhere that is valid.

static class RandomBot extends Player {
    @Override
    int makeMove() {
        int attemptedMove = (int)Math.round(random() * getBoardSize()[0]);
        while (!ensureValidMove(attemptedMove))
            attemptedMove = (int)Math.round(random() * getBoardSize()[0]);

        return attemptedMove;
    }
}

Answer 5

StraightForwardBot

Similar to the OnePlayBot but takes into account the last move and plays the next column over that is valid.

static class StraightForwardBot extends Player {
    private int lastMove = 0;

    @Override
    int makeMove() { 
        for (int i = lastMove + 1; i < getBoardSize()[0]; i++) {
            if (ensureValidMove(i)) {
                lastMove = i;
                return i;
            }
        }
        for (int i = 0; i < lastMove; i++) {
            if (ensureValidMove(i)) {
                lastMove = i;
                return i;
            }
        }
        return 0;
    }
}

Answer 6

JealousBot

This bot hates the other player. And he doesn't like that he drops pieces on the board. So he tries to be the last one who have drop a piece in a column.

public class JealousBot extends Player {

    @Override
    public int makeMove() {
        int move = 0;
        boolean madeMove = false;
        int[] boardSize = getBoardSize();
        int id = getID();
        int[][] board = getBoard();

        if(getTurn()!=0) {
            for(int col = 0; col<boardSize[0]; col++) {
                for(int row = 0; row<boardSize[1]; row++) {
                    if(ensureValidMove(col)) {
                        if(board[col][row]!=EMPTY_CELL && board[col][row]!=id) {
                            move = col;
                            madeMove = true;
                            break;
                        }
                    }
                }
                if(madeMove) break;
            }

            if(!madeMove) {
                int temp = (int)Math.round(random()*boardSize[0]);
                while(madeMove!=true) {
                    temp = (int)Math.round(random()*boardSize[0]);
                    if(ensureValidMove(temp)) {
                        madeMove = true;
                    }
                }
                move = temp;
            }
        } else {
            move = (int)Math.round(random()*boardSize[0]);
        }

        return move;
    }
}

It's my first time on CodeGolf, so I hope this answer will be good enough. I couldn't test it yet, so please excuse me if there are any mistakes.

EDIT : Added a line to break the second for.

EDIT 2 : Figured out why the while was infinite. It is now complete and can be used!

Answer 7

BasicBlockBot

A simple (and naive) block bot. He doesn't know you can make a 4 in a row horizontally or diagonally!

static class BasicBlockBot extends Player {
    @Override
    int makeMove() {
        List<Integer> inARows = detectInARows();
        double chanceOfBlock = 0.5;

        if (inARows.isEmpty())
            chanceOfBlock = 0;

        if (random() < chanceOfBlock) {
            return inARows.get((int)Math.round(random() * (inARows.size() - 1)));
        } else {
            return (int)Math.round(random() * getBoardSize()[0]);
        }
    }


    /**
     * Very limited - just detects vertical in a rows
     *
     * @return A list of colls that have 4 in a row vertical
     */
    private List<Integer> detectInARows() {
        List<Integer> ret = new ArrayList<>();
        int[][] board = getBoard();

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                int currId = board[i][j];
                if (currId != -1 && is4InARowVertical(i, j, board)) {
                    ret.add(i);
                }
            }
        }

        return ret;
    }

    private boolean is4InARowVertical(int coll, int row, int[][] board) {
        int id = board[coll][row];

        for (int i = 0; i < 4; i++) {
            int y = row + i;
            if (!boardContains(coll,y) || board[coll][y] != id)
                return false;
        }
        return true;
    }

}

Answer 8

Progressive

Progressive is... progressive. He likes looking at everything, and some! (I'm not sure of the methodology of this. It worked against a friend, once.) And, for some reason, it works decently.

static class Progressive extends Player{
    @Override
    int makeMove(){
        int move = 0;
        boolean statusBroken = false;
        for(int n=getBoardSize()[0];n>2;n-=2){
            for(int i=0;i<getBoardSize()[0];i+=n){
                if(ensureValidMove(i)){
                    move = i;
                    statusBroken = true;
                    break;
                }
                if(statusBroken) break;
            }
        }
        return move;
    }
}

Answer 9

FairDiceRoll

Always returns 4.

static class FairDiceRoll extends Player {
    private int lastMove = 0;
    @Override
    int makeMove() { 
        return 4;
    }
}

Answer 10

BuggyBot

A sample bot for you to beat (FYI: it's not hard ;)

static class BuggyBot extends Player {
    @Override
    int makeMove() {
        return getBoardSize()[1] - 1;
    }
}

Answer 11

PackingBot

This bot isn't aiming for points directly. He tries to pack a maximum of tokens until the board is filled. He understood that simply going up again and again is stupid, so he will randomly put tokens around his "domain".

He should be able to get some points in all directions, but will not be the best !

(Not tested)

package connectn.players;

static class PackingBot extends Player
{
    @Override
    int makeMove()
    {
        int move = 0;
        int[] sizes = getBoardSize();
        if(getTurn()==0)
            return sizes[0]/2+sizes[0]%2;

        int[][] board = getBoard();
        int[] flatBoard =new int[sizes[0]];
        //Creating a flat mapping of my tokens
        for(int i=0;i<sizes[0];i++)
            for (int j=0;j<sizes[1];j++)
                if(board[i][j]!=getID())
                    flatBoard[i]++;

        int max=0;
        int range=0;
        for(int i=0;i<flatBoard.length;i++)
        {
            if(flatBoard[i]!=0)
                range++;
            if(flatBoard[i]>flatBoard[max])
                max=i;
        }

        int sens = (Math.random()>0.5)?1:-1;
        move=((int)(Math.random()*(range+1)*sens))+max;

        while(!ensureValidMove(move))
        {
            move=(move+1*sens)%sizes[0];
            if(move<0)
                move=sizes[0]-1;
        }
        return move;
    }


}

Answer 12

Steve

package connectn.players;

import java.util.Random;
import java.util.concurrent.ThreadLocalRandom;

import connectn.game.Game;

public class Steve extends Player {
    @Override
    public int makeMove() {
        Random r=ThreadLocalRandom.current();
        int attemptedMove = 0;
        int[][]board=getBoard();
        int ec=Game.EMPTY_CELL;
        for(int c=0;c<board.length;c++){
            int j=board[c].length-1;
            for(;j>=0;j--){
                if(board[c][j]!=ec)break;
            }

            if(j>2+r.nextInt(3)&&r.nextDouble()<0.8)return c;
        }
        int k=-2+board.length/2+r.nextInt(5);
        if(ensureValidMove(k))return k;
        for (int i = 0; i < getBoardSize()[0]; i++)
            if (ensureValidMove(i)) {
                attemptedMove = i;
                break;
            }

        return attemptedMove;
    }
}