KoTH: Gomoku (Five in a row)

Question

Gomoku or Five in a row is a board game played by two players on a \$15 \times 15\$ grid with black and white stones. Whoever is able to place \$5\$ stones in a row (horizontal, vertical or diagonal) wins the game.

Rules

In this KoTH we'll play the Swap2 rule, meaning that a game consists of two phases: In the initial phase the two players determine who goes first/who plays black, after that they'll place one stone each round starting with the player who picked black.

Initial phase

Let the players be A & B and A shall open the game:

• A places two black and one white stone on the board
• B can choose one of the following three moves:
  • player B decides to play black: initial phase is over
  • player B decides to place a white stone and plays white: initial phase is over
  • player B decides to play one black and one white stone: A gets to pick the color

Game phase

Each player places one stone of their colour on the board, starting with the player who plays black, this goes on until there are no more free spaces to play (in which case it's a tie) or one player manages to play \$5\$ stones in a row (in which case that player wins).

A row means either horizontal, vertical or diagonal. A win is a win - it doesn't matter whether the player managed to score more than one row.

KoTH game rules

• each player plays against each other player twice:
  • initially it will be randomly decided who goes first
  • in the next game the player that got to play last goes first
• a win is worth 2 points, a tie 1 and a loss 0
• the goal is to score as many points as possible

Your bot

To make this challenge accessible for as many languages as possible input/output will be via stdin/stdout (line-based). The judge program will prompt your program by printing a line to your bot's stdin and your bot will print one line to stdout.

Once you receive an EXIT message you'll be given half a second to finish writing to files before the judge will kill the process.

Randomness

To make the tournaments verifiable the judge uses seeded randomization and your bot must do too, for the same reason. The bot will be given a seed via command-line argument which it should use, please refer to the next section.

Arguments

The bot receives two command-line arguments:

1. opponent's name
2. seed for randomness

User state

Because your program will always be started new for each game you'll need to use files to persist any information you want to keep. You are allowed to read/write any files or create/remove sub-folders in your current directory. You are not allowed to access any files in any parent-directory!

Input/Output format

BOARD will denote a list of the current stones, it only lists the positions where a stone is placed and each entry will be of the form ((X,Y),COLOR) where X and Y will be an integer in the range \$[0,15)\$ and COLOR will either be "B" (black) or "W" (white).

Furthermore SP denotes a single space, XY a tuple (X,Y) of two integers each in the range \$[0,15)\$ and | denotes a choice.

In the initial phase there are three different kinds of messages:

Prompt (judge) -> Answer (bot)
"A" SP "[]"  -> XY XY XY
"B" SP BOARD -> "B" | "W" SP XY | XY XY
"C" SP BOARD -> "B" | "W"

• The first message asks for three tuples, the first two will be the positions of the black stones and the third one the position for the white one.
• The second message asks either for:
  • "B" -> pick black
  • "W" SP XY -> pick white and place a white stone at XY
  • XY XY -> place two stones (first one black and second one white)
• The last one just asks for which colour you want to play

---

After that the regular game will begin and the messages will become much simpler

N BOARD -> XY

where N is the number of the round (beginning with \$0\$) and XY will be the position where you place a stone.

---

There is one additional message which does not expect an answer

"EXIT" SP NAME | "EXIT TIE"

where NAME is the name of the bot that won. The second message will be sent if the game ends due to nobody winning and no more free spaces to place stones (this implies that your bot can't be named TIE).

Formatting

Since messages from the bot can be decoded without any spaces, all spaces will be ignored (eg. (0 , 0) (0,12) is treated the same as (0,0)(0,12)). Messages from the judge only contain a space to separate different sections (ie. as noted above with SP), allowing you to split the line on spaces.

Any invalid response will result in a loss of that round (you'll still receive an EXIT message), see rules.

Example

Here are some examples of actual messages:

A []
B [((0,0),"B"),((0,1),"W"),((14,14),"B")]
1 [((0,0),"B"),((0,1),"W"),((1,0),"B"),((1,1),"W"),((14,14),"B")]

Judge

You can find the judge program here: To add a bot to it simply create a new folder in the bots folder, place your files there and add a file meta containing name, command, arguments and a flag 0/1 (disable/enable stderr) each on a separate line.

To run a tournament just run ./gomoku and to debug a single bot run ./gomoku -d BOT.

Note: You can find more information on how to setup and use the judge in the Github repository. There are also three example bots (Haskell, Python and JavaScript).

Rules

• on each change of a bot^* the tournament will be rerun and the player with the most points wins (tie-breaker is first submission)
• you may submit more than one bot as long as they don't play a common strategy
• you are not allowed to touch files outside of your directory (eg. manipulating other player's files)
• if your bot crashes or sends an invalid response, the current game is terminated and you lose that round
• while the judge (currently) does not enforce a time-limit per round, you are advised to keep the time spent low as it could become infeasible to test all the submissions^**
• abusing bugs in the judge program counts as loophole

_{* You are encouraged to use Github to separately submit your bot directly in the bots directory (and potentially modify util.sh)!}

_{** In case it becomes a problem you'll be notified, I'd say anything below 500ms (that's a lot!) should be fine for now.}

Chat

If you have questions or want to talk about this KoTH, feel free to join the Chat!

Answer 1

KaitoBot

It uses a very crude implementation of MiniMax principles. The depth of the search is also very low, because otherwise it takes way too long.

Might edit to improve later.

It also tries to play Black if possible, because Wikipedia seems to say that Black has an advantage.

I have never played Gomoku myself, so I set up the first three stones randomly for lack of a better idea.

const readline = require('readline');
const readLine = readline.createInterface({ input: process.stdin });

var debug = true;
var myColor = '';
var opponentColor = '';
var board = [];
var seed = parseInt(process.argv[3]);

function random(min, max) {
    changeSeed();
    var x = Math.sin(seed) * 10000;
    var decimal = x - Math.floor(x);
    var chosen = Math.floor(min + (decimal * (max - min)));
    return chosen;
}

function changeSeed() {
    var x = Math.sin(seed++) * 10000;
    var decimal = x - Math.floor(x);
    seed = Math.floor(100 + (decimal * 9000000));
}

function KaitoBot(ln) {
    var ws = ln.split(' ');

    if (ws[0] === 'A') {
        // Let's play randomly, we don't care.
        var nums = [];
        nums[0] = [ random(0, 15), random(0, 15) ];
        nums[1] = [ random(0, 15), random(0, 15) ];
        nums[2] = [ random(0, 15), random(0, 15) ];
        while (nums[1][0] == nums[0][0] && nums[1][1] == nums[0][1])
        {
            nums[1] = [ random(0, 15), random(0, 15) ];
        }
        while ((nums[2][0] == nums[0][0] && nums[2][1] == nums[0][1]) || (nums[2][0] == nums[1][0] && nums[2][1] == nums[1][1]))
        {
            nums[2] = [ random(0, 15), random(0, 15) ];
        }
        console.log('(' + nums[0][0] + ',' + nums[0][1] + ') (' + nums[1][0] + ',' + nums[1][1] + ') (' + nums[2][0] + ',' + nums[2][1] + ')');
    }
    else if (ws[0] === 'B') {
        // we're second to play, let's just pick black
        myColor = 'B';
        opponentColor = 'W';
        console.log('B');
    }
    else if (ws[0] === 'C') {
        // the other player chose to play 2 stones more, we need to pick..
        // I would prefer playing Black
        myColor = 'B';
        opponentColor = 'W';
        console.log('B');
    }
    else if (ws[0] === 'EXIT') {
        process.exit();
    }
    else {
        board = [];
        var json = JSON.parse(ws[1].replace(/\(\(/g,'{"xy":[')
                .replace(/"\)/g,'"}')
                .replace(/\),/g,'],"colour":'));
        // loop over all XYs and make a board object I can use
        for (var x = 0; x < 15; x++) {
            var newRow = []
            for (var y = 0; y < 15; y++) {
                var contains = false;
                json.forEach(j => {
                    if (j.xy[0] == x && j.xy[1] == y) {
                        contains = true;
                        newRow[newRow.length] = j.colour;
                    }
                });
                if (!contains) {
                    newRow[newRow.length] = ' ';
                }
            }
            board[board.length] = newRow;
        }
        // If we never picked Black, I assume we're White
        if (myColor == '') {
            myColor = 'W';
            opponentColor = 'B';
        }
        var bestMoves = ChooseMove(board, myColor, opponentColor);
        var chosenMove = bestMoves[random(0, bestMoves.length)];
        console.log('(' + chosenMove.X + ',' + chosenMove.Y + ')');
    }
}

function IsSquareRelevant(board, x, y) {
    return (board[x][y] == ' ' && 
        ((x > 0 && board[x - 1][y] != ' ') 
        || (x < 14 && board[x + 1][y] != ' ') 
        || (y > 0 && board[x][y - 1] != ' ') 
        || (y < 14 && board[x][y + 1] != ' ')
        || (x > 0 && y > 0 && board[x - 1][y - 1] != ' ') 
        || (x < 14 && y < 14 && board[x + 1][y + 1] != ' ') 
        || (y > 0 && x < 14 && board[x + 1][y - 1] != ' ') 
        || (y < 14 && x > 0 && board[x - 1][y + 1] != ' ')));
}

function ChooseMove(board, colorMe, colorOpponent) {
    var possibleMoves = [];
    for (var x = 0; x < 15; x++) {
        for (var y = 0; y < 15; y++) {
            if (IsSquareRelevant(board, x, y)) {
                possibleMoves[possibleMoves.length] = {X:x, Y:y};
            }
        }
    }
    var bestValue = -9999;
    var bestMoves = [possibleMoves[0]];
    for (var k in possibleMoves) {
        var changedBoard = JSON.parse(JSON.stringify(board));
        changedBoard[possibleMoves[k].X][possibleMoves[k].Y] = colorMe;
        var value = analyseBoard(changedBoard, colorMe, colorOpponent, colorOpponent, 2);
        if (value > bestValue) {
            bestValue = value;
            bestMoves = [possibleMoves[k]];
        } else if (value == bestValue) {
            bestMoves[bestMoves.length] = possibleMoves[k];
        }
    }
    return bestMoves;
}

function analyseBoard(board, color, opponent, nextToPlay, depth) {
    var tBoard = board[0].map((x,i) => board.map(x => x[i]));
    var score = 0.0;
    for (var x = 0; x < board.length; x++) {
        var inARow = 0;
        var tInARow = 0;
        var opponentInARow = 0;
        var tOpponentInARow = 0;
        var inADiago1 = 0;
        var opponentInADiago1 = 0;
        var inADiago2 = 0;
        var opponentInADiago2 = 0;

        for (var y = 0; y < board.length; y++) {
            if (board[x][y] == color) {
                inARow++;
                score += Math.pow(2, inARow);
            } else {
                inARow = 0;
            }
            if (board[x][y] == opponent) {
                opponentInARow++;
                score -= Math.pow(2, opponentInARow);
            } else {
                opponentInARow = 0;
            }
            if (tBoard[x][y] == color) {
                tInARow++;
                score += Math.pow(2, tInARow);
            } else {
                tInARow = 0;
            }
            if (tBoard[x][y] == opponent) {
                tOpponentInARow++;
                score -= Math.pow(2, tOpponentInARow);
            } else {
                tOpponentInARow = 0;
            }

            var xy = (y + x) % 15;
            var xy2 = (x - y + 15) % 15;
            if (xy == 0) {
                inADiago1 = 0;
                opponentInADiago1 = 0;
            }
            if (xy2 == 0) {
                inADiago2 = 0;
                opponentInADiago2 = 0;
            }

            if (board[xy][y] == color) {
                inADiago1++;
                score += Math.pow(2, inADiago1);
            } else {
                inADiago1 = 0;
            }
            if (board[xy][y] == opponent) {
                opponentInADiago1++;
                score -= Math.pow(2, opponentInADiago1);
            } else {
                opponentInADiago1 = 0;
            }
            if (board[xy2][y] == color) {
                inADiago2++;
                score += Math.pow(2, inADiago2);
            } else {
                inADiago2 = 0;
            }
            if (board[xy2][y] == opponent) {
                opponentInADiago2++;
                score -= Math.pow(2, opponentInADiago2);
            } else {
                opponentInADiago2 = 0;
            }


            if (inARow == 5 || tInARow == 5) {
                return 999999999.0;
            } else if (opponentInARow == 5 || tOpponentInARow == 5) {
                return -99999999.0;
            }
            if (inADiago1 == 5 || inADiago2 == 5) {
                return 999999999.0;
            } else if (opponentInADiago1 == 5 || opponentInADiago2 == 5) {
                return -99999999.0;
            }
        }
    }

    if (depth > 0) {
        var bestMoveValue = 999999999;
        var nextNextToPlay = color;
        if (nextToPlay == color) {
            nextNextToPlay = opponent;
            bestMoveValue = -999999999;
        }
        for (var x = 0; x < board.length; x++) {
            for (var y = 0; y < board.length; y++) {
                if (IsSquareRelevant(board, x, y)) {
                    var changedBoard = JSON.parse(JSON.stringify(board));
                    changedBoard[x][y] = nextToPlay;
                    var NextMoveValue = (analyseBoard(changedBoard, color, opponent, nextNextToPlay, depth - 1) * 0.1);

                    if (nextToPlay == color) {
                        if (NextMoveValue > bestMoveValue) {
                            bestMoveValue = NextMoveValue;
                        }
                    } else {
                        if (NextMoveValue < bestMoveValue) {
                            bestMoveValue = NextMoveValue;
                        }
                    }
                }
            }
        }
        score += bestMoveValue * 0.1;
    }
    return score;
}

readLine.on('line', (ln) => {

    KaitoBot(ln);

});

EDITS: Made the seed change dynamically because otherwise when seeds exceeded 2^52 javascript couldn't handle the increment correctly