# Connect-n time!

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.

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.

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.

• 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


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

• Can you add functionality to determine which turn the game is on? – Conor O'Brien Dec 7 '15 at 22:32
• Already done, check the Player class to see all methods available. – J Atkin Dec 7 '15 at 22:34
• "a square 6x7" that's not a square – ev3commander Dec 8 '15 at 1:54
• Giving players the ability to "pass" by making an illegal move changes the dynamics a bit. Does the game end if everyone passes? – histocrat Dec 8 '15 at 4:57
• Yes, that is why is is very important to use ensureValidMove (unless your strategy is to pass this turn of course). – J Atkin Dec 8 '15 at 13:59

# 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) {
}
}
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) {
} else {
}
}
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;
}
}

• Very, very nice! +1 – J Atkin Dec 9 '15 at 19:52
• Something I noticed while I was playing around with UserBot and your bot was that after some point MaxGayne will throw away turns (e.g. after 15 moves it skips every turn until the game ends). – J Atkin Dec 12 '15 at 2:36
• The cause for this is probably a bug in CustomGame. It's using 0-based player ID's instead of 1-based like the main game. This simply breaks my bot. There are 2 more problems. javafx.util.Pair doesn't work in Eclipse because it's not considered as a part of the public API. And I have no idea where to look for sun.plugin.dom.exception.InvalidStateException. You probably meant java.lang.IllegalStateException. – Sleafar Dec 12 '15 at 8:13
• That seems a little odd... Anyways as for Pair, that is as close as I can get to the data type I want without rolling my own, so unless eclipse won't compile, I think it's OK. As for #3, you are right, my autocomplete in IntelliJ isn't always right. (most of the time it is, that's why I didn't check) – J Atkin Dec 12 '15 at 14:19
• @JAtkin Actually, the Pair problem really prevents compiling in Eclipse, unless you know the workaround. – Sleafar Dec 12 '15 at 16:27

# 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) {
} else {
row += 1;
}
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;
} else {
}
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;
} else {
}
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;
}
}


# 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;
}
}


# 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;
}
}


# 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;
}
}


## 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;
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;
break;
}
}
}
}

int temp = (int)Math.round(random()*boardSize[0]);
temp = (int)Math.round(random()*boardSize[0]);
if(ensureValidMove(temp)) {
}
}
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!

• Welcome to PPCG, you made me laugh with this answer, that's great ! Just be care with your conditions. I think the board is filled with -1 values by default, so if(board[col][row]!=null && board[col][row]!=id) Should be changed to if(board[col][row]!=-1..... Check in game.Game.genBoard() in OP's github if you wanna be sure. I don't know either if your random() will do what you want, maybe use (int)Math.random()*col? – Katenkyo Dec 8 '15 at 10:25
• @Katenkyo Thank you very much, I'm happy if it made you laughed! The random() method is in the Player class! So I think it will work =) But yeah, I wasn't confident in my conditions. I didn't find how it is defined in OP's code, but I'll check again. Thank you very much! – Keker Dec 8 '15 at 10:29
• The Player class define random() as public double random() {return ThreadLocalRandom.current().nextDouble();}. I don't know precisely how it works, but I assume it returns a value between 0 and 1, so would may need to do (int)random()*col :) – Katenkyo Dec 8 '15 at 10:37
• @Katenkyo Oh, I thought it did that already... My bad. I'll edit it when I have found the right value for an empty cell in the board, thank you again! – Keker Dec 8 '15 at 10:54
• @Katenkyo You are correct, nextDouble returns a number between 0 and 1. I included it because the simulations are run in parallel, and Math.random() is not thread safe. – J Atkin Dec 8 '15 at 13:45

# 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)) {
}
}
}

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;
}

}


# 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;
}
}

• @JAtkin Sorry, I had an older version of the code. – Conor O'Brien Dec 7 '15 at 23:26
• @JAtkin I rejected your edit. You should allow them to fix their code in their post. If you want to fix it for your controller, that's fine (I'd personally still leave a note), but outright modification of somebody's code on SE isn't allowed. – Nathan Merrill Dec 7 '15 at 23:37

# FairDiceRoll

Always returns 4.

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


# 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;
}
}


# 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;
}

}

• @JAtkin Thanks for pointing that, fixed :) – Katenkyo Dec 8 '15 at 14:16

# Steve

package connectn.players;

import java.util.Random;

import connectn.game.Game;

public class Steve extends Player {
@Override
public int makeMove() {
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;
}
}

• Steve is having a hard time, he scores under BasicBlockBot. – J Atkin Dec 8 '15 at 22:20