In this game two players compete to eat the most points worth of tokens, but there's a twist! Eating multiple tokens in a row of the same color gives an ever-growing bonus, but watch out, or your opponent will thwart your plans by eating the tokens you want before you can!
Rules:
- 1 versus 1
- n by n board (random size between 5x5 and 15x15)
- You and your opponent will spawn in the same random cell
- Throughout the board will be randomly generated numbers in some cells ranging in value from 1-3
- 2 * (the width of the board) tokens will be generated, but there can be overrides, so there may be fewer by chance.
- Each number will be one of 3 colors: Red, Green, or Blue, in hex RGB format
- Each round, player 1 moves and the board is updated, then player 2 moves, and the board is updated. So each player can effectively tell what move the previous player made based on the change in the board state. This continues until the game ends, as described later.
- You have 6 possible actions for a turn: UP, RIGHT, DOWN, LEFT, EAT, and PASS
- The 4 move commands are self-explanatory, and you CAN pass your turn. If you return a nonsensical move, we will assume you meant pass. If you try to move off the edge of the board, you will not move. The edges don't wrap.
- EAT consumes the number you are currently in the same space as
- You gain as many points as the number you consume
- If you eat 2 numbers in a row of the same color, you get +1
- If you eat 3 numbers in a row of the same color, you get +2
- If you eat m numbers in a row of the same color, you get +(m-1)
- These bonuses are added cumulatively, so getting m numbers in a row leads to m*(m-1)/2 in total bonus by the time you eat a different color.
- Game end conditions:
- All numbers are consumed
- 4 * (the width of the board) turns have gone by with no effective eating (just saying “EAT” with no token where you are doesn't count) occurring by either player (any token is reachable in 2 * (the width) moves, so this bound will only be surpassed if both players have no single target token in mind)
- Your AI should take less than a second to make a move, else PASS will be assumed as your choice.
The tournament will be round robin with a large number of rounds, say 100 or 1000. A random board is generated, and each ordered pair of different players is run on that board. After the tournament completes we will rank people by their total score. So even if you are player 2 for a game, your goal is still to get as many points as possible.
AI Submission: The language my controller supports is Javascript. Multiple submissions are allowed. Everyone submits a constructor for an object like this:
function (player1) {
this.yourMove = function (b) {
return "MOVE";
}
}
The input player1
is a boolean saying whether you are player 1 or not.
Your constructor must have the yourMove
function, but it can have
any number of additional functions or values as well. Don't define any
global variables, just put them as variables on your object. A new version
of your object will be created at the beginning of each match, and
yourMove
will be called on it, with the current board as input, on each of your turns, and should return a valid move.
b
, the input to yourMove
, is a copy of the current board, here are the
constructors, with input examples, though you can't call them yourself:
function token(color, points) {
this.color = color; //"#FF0000"
this.points = points; //5
}
function player(pos, score, colorBonus, lastColor) {
this.pos = pos; //[5, 5]
this.score = score; //9
this.colorBonus = colorBonus; //i.e. 2 if you just ate 3 blue tokens in a row
//0 if you just ate two different colors.
this.lastColor = lastColor; //"#00FF00", is "#000000" at start
}
function board(player1, player2, tokens) {
this.player1 = player1; //new player([5, 5], 9, 2, "#00FF00")
this.player2 = player2; //new player([5, 5], 9, 2, "#00FF00")
this.tokens = tokens; //[[new token("#0000FF", 5), false],
// [new token("#0000FF", 5), false]]
}
The token array has "false" for any empty squares, and tokens[a][b] is the token at x = a, y = b, numbered starting from the upper-left corner.
Controller: Here's a link to the controller in GitHub. It's an html file that you can run to see how the game and the round-robin works, and it comes with two AIs, a random one that moves in a random direction each turn but eats tokens at its position, and a naive algorithm that goes for the nearest token that gives the most points. I will add in each AI as it is submitted.
Below is a snippet that allows you to run the controller on the default AI. Current AIs:
- KindaRandomAI
- NaiveAI
- MirrorBot
- HungryBot
<!DOCTYPE html>
<html>
<body>
<canvas id="myCanvas" width="700" height="600" style="border:1px solid #c3c3c3;">
Your browser does not support the HTML5 canvas tag.
</canvas>
<script>
// AI Array, put in at least two constructor functions as described in the
// data file, and it will do round robin on them.
// Also, you can adjust some variables for testing purposes only.
var interval = 1; // in milliseconds per turn
var matches = 10; // number of matches for each pairing
var aiArray = [];
myAI = function(player1) {
this.player1 = player1;
this.yourMove = function(b) {
var me;
if (this.player1) {
me = b.player1;
} else {
me = b.player2;
}
var d = 0;
var tokenP;
while (tokenP == undefined) {
var arr = this.findTokensAtDistance(me.pos, d)
tokenP = this.findBestToken(arr, b.tokens, me);
d += 1;
}
return this.startAndGoalToCommand(me.pos, tokenP);
}
this.findTokensAtDistance = function(p, d) {
if (d == 0) {
return [
[p[0], p[1]]
];
}
var myArr = [];
for (i = 0; i <= d; i++) {
myArr[i] = [i, d - i];
}
var mySecArr = [];
for (i = 0; i <= d; i++) {
mySecArr[i] = [myArr[i][0] + p[0], myArr[i][1] + p[1]];
}
mySecArr[mySecArr.length] = [myArr[0][0] + p[0], -myArr[0][1] + p[1]];
for (i = 1; i < myArr.length - 1; i++) {
mySecArr[mySecArr.length] = [-myArr[i][0] + p[0], myArr[i][1] + p[1]]
mySecArr[mySecArr.length] = [myArr[i][0] + p[0], -myArr[i][1] + p[1]]
mySecArr[mySecArr.length] = [-myArr[i][0] + p[0], -myArr[i][1] + p[1]]
}
mySecArr[mySecArr.length] = [-myArr[myArr.length - 1][0] + p[0], myArr[myArr.length - 1][1] + p[1]];
return mySecArr;
}
this.findBestToken = function(arr, t, player) {
var tokenPos;
for (i = 0; i < arr.length; i++) {
if (arr[i][0] >= 0 && arr[i][0] < t.length && arr[i][1] >= 0 && arr[i][1] < t.length) {
if (t[arr[i][0]][arr[i][1]] != false && ((tokenPos == undefined) || (this.tokenScore(player, t[arr[i][0]][arr[i][1]]) > this.tokenScore(player, t[tokenPos[0]][tokenPos[1]])))) {
tokenPos = [arr[i][0],
[arr[i][1]]
];
}
}
}
return tokenPos;
}
this.tokenScore = function(player, token) {
if (player.lastColor == token.color) {
return player.colorBonus + 1 + token.points;
} else {
return token.points;
}
}
this.startAndGoalToCommand = function(start, goal) {
var diff = [goal[0] - start[0], goal[1] - start[1]];
if (diff[0] > 0) {
return "RIGHT";
} else if (diff[1] > 0) {
return "DOWN";
} else if (diff[1] < 0) {
return "UP";
} else if (diff[0] < 0) {
return "LEFT";
} else {
return "EAT";
}
}
}
aiArray[0] = myAI;
// This is a really stupid AI, used to test that the round-robin selected
// it is the worst by far
myStupidAI = function(player1) {
this.player1 = player1;
this.yourMove = function(b) {
var me;
if (this.player1) {
me = b.player1;
} else {
me = b.player2;
}
if (b.tokens[me.pos[0]][me.pos[1]] != false) {
return "EAT";
} else {
var dirs = this.getViableDirections(b, me.pos);
var rand = Math.floor(Math.random() * dirs.length);
return dirs[rand];
}
}
this.getViableDirections = function(b, p) {
var dirs = [];
if (p[0] > 0) {
dirs.push("LEFT");
}
if (p[1] > 0) {
dirs.push("UP");
}
if (p[1] < b.tokens.length - 1) {
dirs.push("DOWN");
}
if (p[0] < b.tokens.length - 1) {
dirs.push("RIGHT");
}
return dirs;
}
}
aiArray[1] = myStupidAI;
mirrorBot = function(player1){
this.hasStarted=0;
this.player1 = player1;
this.yourMove = function(b){
this.op = this.player1 ? b.player2 : b.player1;
var out = "EAT";
if(this.hasStarted){
if(this.opl.pos[0] < this.op.pos[0]) out = "LEFT";
if(this.opl.pos[0] > this.op.pos[0]) out = "RIGHT";
if(this.opl.pos[1] < this.op.pos[1]) out = "UP";
if(this.opl.pos[1] > this.op.pos[1]) out = "DOWN";
}
this.opl = this.op;
this.hasStarted = 1;
return out;
}
}
aiArray[2] = mirrorBot;
hungryBot = function(first) {
// Set up "self"
var self = this;
// Determine player order
this.player = -(first - 2);
this.enemy = first + 1;
// Action associative array
this.actions = ['EAT', 'LEFT', 'RIGHT', 'UP', 'DOWN'];
//Logic handler
this.yourMove = function(board) {
// Determine player object
var player = board['player' + self.player];
var enemy = board['player' + self.enemy];
// Point value action grid
var actions = [0, 0, 0, 0, 0]; // Associative with "this.actions"
// Board dimensions
var size = board.tokens.length;
var maxDist = size * 2;
// Colors remaining
var colors = {
'#FF0000': 0,
'#00FF00': 0,
'#0000FF': 0
};
// Averaged value weight
var average = [0, 0];
// Total points
var points = 0;
// Token holder
var tokens = [];
// Token parser
for (var i = 0, x = 0, y = 0; i < size * size; i += 1, x = i % size, y = i / size | 0) {
if (!board.tokens[x][y]) {
continue;
} else {
var token = {};
token.points = board.tokens[x][y].points;
token.color = board.tokens[x][y].color;
token.x = x - player.pos[0];
token.y = y - player.pos[1];
token.distX = Math.abs(token.x);
token.distY = Math.abs(token.y);
token.dist = token.distX + token.distY;
token.distE = Math.abs(x - enemy.pos[0]) + Math.abs(y - enemy.pos[1]);
token.value = -token.points - (player.colorBonus + 1) * (token.color == player.lastColor) * ((token.dist == 0) + 1) * 1.618 - (enemy.colorBonus + 1) * (token.color == enemy.lastColor);
tokens.push(token);
colors[token.color] += 1;
points += token.points;
average[0] += x * token.points;
average[1] += y * token.points;
}
}
// Determine actual average
average[0] = average[0] / points | 0;
average[1] = average[1] / points | 0;
// Pick best token
var best = 0;
// Calculate point values of tokens
for (i = 0; i < tokens.length; i++) {
var token = tokens[i];
// Add remaining numbers of tokens of color as factor
token.value -= (colors[token.color] / tokens.length) * 1.618;
// Subtract distance as a factor
token.value += token.dist;
// Add distance to average to value
token.value += (Math.abs(average[0] - (token.x + player.pos[0])) + Math.abs(average[1] - (token.y + player.pos[1]))) / Math.sqrt(2);
// Consider them higher value if we are closer, and lower if they are
token.value += ((token.dist - token.distE) / (token.dist + token.distE + 0.001)) * token.dist;
// Don't go for it if enemy is already there
token.value += (token.distE == 0 && token.dist > 0) * 100;
if (tokens[best].value > tokens[i].value || (tokens[best].value === tokens[i].value && Math.round(Math.random()))) {
best = i;
}
}
// Set token to best token
var token = tokens[best];
// What to respond with
var response = 'PASS';
// Find best action to get token
if (token.dist == 0) {
response = 'EAT'; // We're on the token
} else if (token.distX >= token.distY) { // Token is more horizontal
if (token.x < 0) { // Token is left
response = 'LEFT';
} else if (token.x > 0) { // Token is right
response = 'RIGHT';
}
} else if (token.distX < token.distY) { // Token is more vertical
if (token.y < 0) { // Token is above
response = 'UP';
} else if (token.y > 0) { // Token is below
response = 'DOWN';
}
}
// Return response
return response;
}
};
aiArray[3]=hungryBot;
for (i = 0; i < aiArray.length; i += 1) {
Object.freeze(aiArray[i]);
}
// This is the actual code to run the program. You shouldn't mess with it,
// or your AI might not work during the actual competition.
// Also note that you can't access this code at all in your AI.
// Feel free to make suggestions and we'll try to incorporate them,
// and let us know if something isn't working correctly.
Object.freeze(aiArray);
setInterval((function() {
function token(color, points) {
this.color = color;
this.points = points;
}
function player(pos, score, colorBonus, lastColor) {
this.pos = pos;
this.score = score;
this.colorBonus = colorBonus;
this.lastColor = lastColor;
}
function board(player1, player2, tokens) {
this.player1 = player1;
this.player2 = player2;
this.tokens = tokens;
}
function copyBoard(b) {
return new board(copyPlayer(b.player1), copyPlayer(b.player2), copyTokens(b.tokens));
}
function copyTokens(t) {
var tokens = [];
for (i = 0; i < t.length; i++) {
tokens[i] = [];
for (j = 0; j < t[i].length; j++) {
tokens[i][j] = t[i][j];
}
}
return tokens;
}
function copyPlayer(p) {
return new player([p.pos[0], p.pos[1]], p.score, p.colorBonus, p.lastColor);
}
function endGame(b) {
if (b.player1.score > b.player2.score) {
var c = document.getElementById("myCanvas");
var ctx = c.getContext("2d");
ctx.font = 20 + "px Arial";
ctx.textAlign = "left";
ctx.fillStyle = "#000000";
ctx.fillText("Player 1", 601, 160);
ctx.fillText("wins!", 601, 180);
} else if (b.player1.score < b.player2.score) {
var c = document.getElementById("myCanvas");
var ctx = c.getContext("2d");
ctx.font = 20 + "px Arial";
ctx.textAlign = "left";
ctx.fillStyle = "#000000";
ctx.fillText("Player 2", 601, 160);
ctx.fillText("wins!", 601, 180);
} else {
var c = document.getElementById("myCanvas");
var ctx = c.getContext("2d");
ctx.font = 20 + "px Arial";
ctx.textAlign = "left";
ctx.fillStyle = "#000000";
ctx.fillText("It's a", 601, 160);
ctx.fillText("draw!", 601, 180);
}
}
function genTokenArray(size) {
var temp = [];
for (i = 0; i < size; i++) {
temp[i] = [];
for (j = 0; j < size; j++) {
temp[i][j] = false;
}
}
return temp;
}
function genRandomTokenArray(size) {
var temp = genTokenArray(size);
for (i = 0; i < size * 2; i++) {
var rand = Math.floor(Math.random() * temp.length);
var points = Math.floor(Math.random() * 3 + 1);
var rand2 = Math.floor(Math.random() * 3);
var color;
var rand3 = Math.floor(Math.random() * temp[rand].length);
if (rand2 == 0) {
color = "#FF0000"
} else if (rand2 == 1) {
color = "#00FF00"
} else {
color = "#0000FF"
}
temp[rand][rand3] = new token(color, points);
}
return temp;
}
function countTokens(tokenArr) {
var x = 0;
for (i = 0; i < tokenArr.length; i++) {
for (j = 0; j < tokenArr[i].length; j++) {
if (tokenArr[i][j] != false) {
x += 1
}
}
}
return x;
}
function actPlayer(b, p, s) {
if (s == "UP" && p.pos[1] > 0) {
p.pos[1] -= 1;
} else if (s == "RIGHT" && p.pos[0] < b.tokens.length - 1) {
p.pos[0] += 1;
} else if (s == "DOWN" && p.pos[1] < b.tokens.length - 1) {
p.pos[1] += 1;
} else if (s == "LEFT" && p.pos[0] > 0) {
p.pos[0] -= 1;
} else if (s == "EAT" && b.tokens[p.pos[0]][p.pos[1]] != false) {
if (p.lastColor == b.tokens[p.pos[0]][p.pos[1]].color) {
p.colorBonus += 1;
p.score += p.colorBonus;
} else {
p.lastColor = b.tokens[p.pos[0]][p.pos[1]].color;
p.colorBonus = 0;
}
p.score += b.tokens[p.pos[0]][p.pos[1]].points;
b.tokens[p.pos[0]][p.pos[1]] = false;
}
}
function drawEmptyRect() {
var c = document.getElementById("myCanvas");
var ctx = c.getContext("2d");
ctx.clearRect(0, 0, 700, 600);
}
function drawToken(t, x, y, g) {
drawEntity(x, y, t.points, t.color, "#000000", 300 / g, g);
}
function drawLittleEntity(x, y, label, fillColor, labelColor, size, cX, cY, g) {
var delta = 600 / g;
var x1 = x * delta + cX * delta / 4;
var y1 = y * delta + cY * delta / 4;
var c = document.getElementById("myCanvas");
var ctx = c.getContext("2d");
ctx.beginPath();
ctx.arc(x1, y1, size / 2, 0, 2 * Math.PI);
ctx.stroke();
ctx.fillStyle = fillColor;
ctx.fill();
ctx.font = delta / 2 + "px Arial";
ctx.textAlign = "center";
ctx.fillStyle = labelColor;
ctx.fillText(label, x1, y1 + delta * 3 / 16);
}
function drawEntity(x, y, label, fillColor, labelColor, size, g) {
var delta = 600 / g;
var x1 = x * delta + delta / 2;
var y1 = y * delta + delta / 2;
var c = document.getElementById("myCanvas");
var ctx = c.getContext("2d");
ctx.beginPath();
ctx.arc(x1, y1, size, 0, 2 * Math.PI);
ctx.stroke();
ctx.fillStyle = fillColor;
ctx.fill();
ctx.font = delta + "px Arial";
ctx.textAlign = "center";
ctx.fillStyle = labelColor;
ctx.fillText(label, x1, y1 + delta * 3 / 8);
}
function drawAllTokens(arrToken) {
for (i = 0; i < arrToken.length; i++) {
for (j = 0; j < arrToken[i].length; j++) {
if (arrToken[i][j] != false) {
drawToken(arrToken[i][j], i, j, arrToken.length);
}
}
}
}
function drawGrid(g) {
var delta = 600 / g;
for (i = 0; i <= g; i++) {
var canvas = document.getElementById("myCanvas");
var ctx = canvas.getContext("2d");
ctx.beginPath();
ctx.moveTo(i * delta, 0);
ctx.lineTo(i * delta, 600);
ctx.stroke();
}
for (j = 0; j <= g; j++) {
var canvas = document.getElementById("myCanvas");
var ctx = canvas.getContext("2d");
ctx.beginPath();
ctx.moveTo(0, j * delta);
ctx.lineTo(600, j * delta);
ctx.stroke();
}
}
function drawPlayer1(b, g) {
drawLittleEntity(b.player1.pos[0], b.player1.pos[1], "F", "#000000", "#FFFFFF", 300 / g, 1, 1, g);
}
function drawPlayer2(b, g) {
drawLittleEntity(b.player2.pos[0], b.player2.pos[1], "S", "#000000", "#FFFFFF", 300 / g, 3, 3, g);
}
function drawScore(b) {
var canvas = document.getElementById("myCanvas");
var ctx = canvas.getContext("2d");
ctx.font = "20px Arial";
ctx.fillStyle = "#000000";
ctx.textAlign = "left";
ctx.fillText("P" + indices[0] + " Score:", 601, 50);
ctx.fillText(b.player1.score, 601, 70);
ctx.fillText("P" + indices[1] + " Score:", 601, 100);
ctx.fillText(b.player2.score, 601, 120);
}
function drawScoreNum(s, i) {
var canvas = document.getElementById("myCanvas");
var ctx = canvas.getContext("2d");
ctx.font = "20px Arial";
ctx.fillStyle = "#000000";
ctx.textAlign = "left";
ctx.fillText("P" + i + " Score:", 601, i * 50 + 50);
ctx.fillText(s, 601, i * 50 + 70);
}
function redraw(b, g) {
drawEmptyRect();
drawGrid(g);
drawScore(b);
drawAllTokens(b.tokens);
drawPlayer1(b, g);
drawPlayer2(b, g);
drawScoreNum()
}
function nextPair(pair, total) {
var pairRes = [pair[0], (pair[1] + 1) % total];
if (pairRes[1] == 0) {
pairRes[0] = pairRes[0] + 1;
}
return pairRes;
}
function nextGameUnfair() {
scores[indices[0]] = scores[indices[0]] + currBoard.player1.score;
scores[indices[1]] = scores[indices[1]] + currBoard.player2.score;
if (matchCount >= matches) {
matchCount = 0;
indices = nextPair(indices, aiArray.length);
if (indices[0] == indices[1]) {
indices = nextPair(indices, aiArray.length);
}
if (indices[0] >= aiArray.length) {
return false;
}
player1Turn = true;
timeWithoutEating = 0;
firstAI = new aiArray[indices[0]](true);
secondAI = new aiArray[indices[1]](false);
currBoard = genBoard();
} else {
matchCount++;
player1Turn = true;
timeWithoutEating = 0;
firstAI = new aiArray[indices[0]](true);
secondAI = new aiArray[indices[1]](false);
currBoard = genBoard();
}
return true;
}
function nextGameFair() {
scores[indices[0]] = scores[indices[0]] + currBoard.player1.score;
scores[indices[1]] = scores[indices[1]] + currBoard.player2.score;
indices = nextPair(indices, aiArray.length);
if (indices[0] == indices[1]) {
indices = nextPair(indices, aiArray.length);
}
if (indices[0] >= aiArray.length) {
indices = [0, 1];
matchCount++;
if (matchCount >= matches) {
return false;
}
player1Turn = true;
timeWithoutEating = 0;
currBoard = genBoard();
} else {
player1Turn = true;
timeWithoutEating = 0;
currBoard = savedBoard;
}
firstAI = new aiArray[indices[0]](true);
secondAI = new aiArray[indices[1]](false);
savedBoard = copyBoard(currBoard);
return true;
}
function genBoard() {
var rand = Math.floor(Math.random() * 11 + 5);
var randX = Math.floor(Math.random() * rand);
var randY = Math.floor(Math.random() * rand);
return new board(new player([randX, randY], 0, 0, "#000000"),
new player([randX, randY], 0, 0, "#000000"),
genRandomTokenArray(rand));
}
var running = true;
var indices = [0, 1];
var scores = []
for (i = 0; i < aiArray.length; i++) {
scores.push(0);
}
var matchCount = 0;
var firstAI = new aiArray[0](true);
var secondAI = new aiArray[1](false);
var player1Turn = true;
var currBoard = genBoard();
var savedBoard = copyBoard(currBoard);
var timeWithoutEating = 0;
return function() {
if (running) {
var numTokens = countTokens(currBoard.tokens);
if (numTokens <= 0) {} else if (player1Turn) {
actPlayer(currBoard, currBoard.player1, firstAI.yourMove(copyBoard(currBoard)));
} else {
actPlayer(currBoard, currBoard.player2, secondAI.yourMove(copyBoard(currBoard)));
}
player1Turn = !player1Turn;
redraw(currBoard, currBoard.tokens.length);
if (numTokens > countTokens(currBoard.tokens)) {
timeWithoutEating = 0;
} else {
timeWithoutEating += 1;
}
if (numTokens <= 0 || timeWithoutEating > 4 * currBoard.tokens.length) {
running = nextGameFair();
}
} else {
drawEmptyRect();
for (i = 0; i < scores.length; i++) {
drawScoreNum(scores[i], i);
}
}
}
})(), interval);
</script>
</body>
</html>
player1
boolean is the constructor for your AI, which will have ayourMove
function that takes the current board as input, asb
. \$\endgroup\$