(We recommend that you write your code in a separate text editor, then copy-paste it here.)
(This does not submit your player to the tournament. There are further directions below for that.)
Here is an example that finds the first vertex of our player's color with a neighboring empty vertex next to it:
//Don't change the function header (next line) at all.
function userGetMove(playerId, position) {
const graph = position.getGraph(); //instance of TriangularGridSubgraph
//search through the vertices of the graph
for (var columnIndex = 0; columnIndex < graph.getWidth(); columnIndex++) {
for (var rowIndex = 0; rowIndex < graph.getHeight(); rowIndex++) {
//get the color of the vertex we're looking at
const color = graph.getValue(columnIndex, rowIndex);
if (color == playerId) {
//the vertex is our color. Let's go look at the neighbors!
const neighborsCoordinates = graph.getNeighborCoordinates(columnIndex, rowIndex);
for (const coordinates of neighborsCoordinates) {
const neighborColumn = coordinates[0];
const neighborRow = coordinates[1];
const neighborColor = graph.getValue(neighborColumn, neighborRow);
if (neighborColor == CombinatorialGame.prototype.UNCOLORED) {
//the neighboring vertex is uncolored! Let's paint it our color and return the new position.
const optionGraph = graph.clone();
optionGraph.setValue(neighborColumn, neighborRow, playerId);
const option = new Fjords(0, 0, 0, true); //this starts with an empty underlying graph. That's fine because we're about to replace it.
option.graph = optionGraph;
return option;
}
}
}
}
}
//we (hopefully) shouldn't ever get here because we should always be given a graph we can move on.
console.log("ERROR: didn't find a move to make!");
}
Fjords is a partizan combinatorial game played on a subgraph of a triangular grid with some vertices colored Blue or Red. On their turn, the current player (Blue or Red) chooses an uncolored vertex next to one with their color, painting it their color. The last player to move wins. You can play Fjords here.
We are holding a computer player tournament as part of Sprouts 2027. People can use this to test their players. Instructions to submit a player are below.
You do not have to be present at Sprouts to enter your player into the tournament. It's often the case that the winning player authors are not present during the tournament.
You can work in a group or on your own.
The initial positions should each be on an 8x8 board, but different variations of edges will be removed.
We'll need players to run efficiently. For the actual conference tournament, if we run this with a bunch of contestants at the same time as we're running Zoom, it will get bogged down quickly. (And Kyle's laptop is not very powerful.) Please make sure your player takes their turn in close to 6 seconds or less on starting positions on your own machine. (If your machine isn't too overpowered, that should equate to about 15 seconds on my laptop.) If specific players are running too long, we'll have to exclude them from the tournament. (If you disagree with these rules, feel free to talk to me. We would much rather have more players than fewer!)
Below, you'll see the details for submitting your player class. It does not have to be "stateless"; you can definitely include fields that your player uses to make moves.
Check out the instructions below. (After this EFAQ.)
Yes, those directions are below!
Keep watching this space, or watch @CGTKyle@mathstodon.xyz (Mastodon) for updates.
Oh yeah. I got it working, but I definitely need to clean it up. Please don't tell my software engineering students! I'll refactor it when I have time (please don't check to see if this answer is the same as it was last year).
If you get a player working as above, you'll need to make a few changes to get it working for the actual Sprouts tournament.
By popular demand, we've included a way to pit two (or more) players against each other.
Here is the underlying JavaScript code for the Fjords class, which uses the prototype package to define objects. It is currently a part of the (very large) combinatorialGames.js file I maintain. For more details, please check out that file.
/**
* Implements the second phase of Fjords.
* @author Kyle Burke
*/
const Fjords = Class.create(CombinatorialGame, {
/**
* Constructor.
*/
initialize: function(width, height, numFarms, skipRemovingEdges) {
//console.log("launched init....");
//console.log("numFarms: " + numFarms);
if (numFarms === undefined || numFarms < 0) numFarms = (width + height) / 3;
if (numFarms * 2 > width * height) {
numFarms = Math.floor(width * height /2);
}
if (skipRemovingEdges === undefined) skipRemovingEdges = false;
//console.log("numFarms: " + numFarms);
this.playerNames = ["Blue", "Red"];
this.graph = new TriangularGridSubgraph(width, height, ((col, row) => CombinatorialGame.prototype.UNCOLORED));
//console.log("Created the graph...");
//remove some edges
/* */
for (var i = 0; i < 1* height * width && !skipRemovingEdges; i++) {
//console.log("removing " + (i+1) + "th edge...");
const randColumn = getRandomInt(0, width);
const randRow = getRandomInt(0, height);
const neighbors = this.graph.getNeighborCoordinates(randColumn, randRow);
if (neighbors.length > 0) {
const neighborCoords = randomChoice(neighbors);
const neighborCol = neighborCoords[0];
const neighborRow = neighborCoords[1];
this.graph.removeEdge(randColumn, randRow, neighborCol, neighborRow);
if (!this.graph.isConnected()) {
this.graph.addEdge(randColumn, randRow, neighborCol, neighborRow);
} else {
//TODO: these cases shouldn't happen anymore... can we remove them?
if (neighbors.length == 1) {
//remove the vertex
//console.log("removing a vertex: (" + randColumn + ", " + randRow + ")");
this.graph.removeVertex(randColumn, randRow);
//console.log(this.graph.hasVertex(randColumn, randRow));
}
//check to see whether we need to remove the neighbor.
const neighborNeighborCoords = this.graph.getNeighborCoordinates(neighborCol, neighborRow);
if (neighborNeighborCoords.length == 0) {
this.graph.removeVertex(neighborCol, neighborRow);
//console.log("removing a neighbor vertex: (" + neighborCol + ", " + neighborRow + ")");
}
}
}
}
/* */
//get the center of the board
var centerColumn = (width-1) / 2;
var centerRow = (height-1) / 2;
if (centerRow % 2 == 0) {
centerColumn += .5;
} else if (centerRow % 1 == .5) {
centerColumn += .25;
}
//add some starter colors in random places
for (var i = 0; i < numFarms; i++) {
var blueColumn;
var blueRow;
var redColumn;
var redRow;
while (true) {
blueColumn = getRandomInt(0, width);
blueRow = getRandomInt(0, height);
if ((!this.graph.hasVertex(blueColumn, blueRow)) || this.graph.getValue(blueColumn, blueRow) !== CombinatorialGame.prototype.UNCOLORED) continue; //restart the loop
var blueColumnDistanceFromEdge = Math.min(blueColumn, width - blueColumn - 1);
var blueRowDistanceFromEdge = Math.min(blueRow, height - 1 - blueRow);
const blueTotalDistance = blueColumnDistanceFromEdge + blueRowDistanceFromEdge;
//try another distance calculation
var blueColumnShifted = blueColumn;
if (blueRow % 2 == 0) blueColumnShifted += .5;
const blueHexRowDistanceToCenter = Math.abs(blueRow - centerRow);
const blueHexColumnDistanceToCenter = Math.abs(blueColumnShifted - centerColumn);
const blueHexDistanceToCenter = blueHexRowDistanceToCenter + Math.max(0, blueHexColumnDistanceToCenter - (blueHexRowDistanceToCenter/2));
redRow = getRandomInt(0, height);
const redHexRowDistanceToCenter = Math.abs(redRow - centerRow);
const redColumnPossibilities = [];
for (var j = 0; j < width; j++) {
var redColumnShifted = j;
if (redRow % 2 == 0) redColumnShifted += .5;
const redHexColumnDistanceToCenter = Math.abs(redColumnShifted - centerColumn);
const redHexDistanceToCenter = redHexRowDistanceToCenter + Math.max(0, redHexColumnDistanceToCenter - redHexRowDistanceToCenter / 2);
if (redHexDistanceToCenter == blueHexDistanceToCenter) {
redColumnPossibilities.push(j);
}
}
shuffleArray(redColumnPossibilities);
var foundOne = false;
for (const redColumnPossibility of redColumnPossibilities) {
redColumn = redColumnPossibility;
if (this.graph.hasVertex(redColumn, redRow) && this.graph.getValue(redColumn, redRow) === CombinatorialGame.prototype.UNCOLORED && (blueColumn != redColumn || blueRow != redRow)) {
foundOne = true;
//console.log("blueHexDistanceToCenter: " + blueHexDistanceToCenter);
break;
}
}
if (foundOne) break; //found one that worked!
}
//okay to add the blue and red vertices.... they are somewhat fair
this.graph.setValue(blueColumn, blueRow, CombinatorialGame.prototype.LEFT);
this.graph.setValue(redColumn, redRow, CombinatorialGame.prototype.RIGHT);
//console.log("Added vertices: (" + blueColumn + ", " + blueRow + ") and (" + redColumn + ", " + redRow + ")");
}
}
/**
* Returns the width of this board.
*/
,getWidth: function() {
return this.graph.getWidth();
}
/**
* Returns the height of this board.
*/
,getHeight: function() {
return this.graph.getHeight();
}
/**
* Returns a copy of the graph.
*/
,getGraph: function() {
return this.graph.clone();
}
/**
* Equals!
*/
,equals: function(other) {
return this.graph.equals(other.graph);
}
/**
* Clone.
*/
,clone: function() {
const copy = new Fjords(this.getWidth(), this.getHeight(), 0, true);
copy.graph = this.graph.clone();
return copy;
}
/**
* Gets the options.
*/
,getOptionsForPlayer: function(playerId) {
const options = [];
for (coordinates of this.graph.getVertexCoordinates()) {
const col = coordinates[0];
const row = coordinates[1];
if (this.graph.getValue(col, row) == playerId) {
const neighbors = this.graph.getNeighborCoordinates(col, row);
for (const neighbor of neighbors) {
const neighborCol = neighbor[0];
const neighborRow = neighbor[1];
if (this.graph.getValue(neighborCol, neighborRow) == CombinatorialGame.prototype.UNCOLORED) {
const option = this.clone();
option.graph.setValue(neighborCol, neighborRow, playerId);
options.push(option);
}
}
}
}
return options;
}
/**
* Determines whether a player can play at a position.
*/
,playerCanPlayAt: function(column, row, playerId) {
if (this.graph.hasVertex(column, row) && this.graph.getValue(column, row) == CombinatorialGame.prototype.UNCOLORED) {
const neighborCoordinates = this.graph.getNeighborCoordinates(column, row);
for (const neighbor of neighborCoordinates) {
const neighborColumn = neighbor[0];
const neighborRow = neighbor[1];
if (this.graph.getValue(neighborColumn, neighborRow) == playerId) {
return true;
}
}
}
return false;
}
/**
* Gets a single option, if it exists.
*/
,getOption: function(column, row, playerId) {
if (this.playerCanPlayAt(column, row, playerId)) {
const option = this.clone();
option.graph.setValue(column, row, playerId);
return option;
}
console.log("Fjords.getOption() tried to create an illegal option!");
}
/**
* Returns the value at a specific vertex.
*/
,getColorAt: function(column, row) {
return this.graph.getValue(column, row);
}
}); //end of Fjords