(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 we're planning on having.)
Here is an example that just changes the color of the top-left region to the first neighboring color it finds:
Flag Coloring is an impartial combinatorial game played on a rectangular array colored cells. On their turn, the current player chooses a region (any cell in that colored region is equivalent) and a neighboring color to that region. Then the selected region becomes that new color. If that move results in only one color on the board, then there are no more moves and the player who just changed the color wins! manually play Flag Coloring.
We are holding a computer player tournament as part of Sprouts 2023. People can use this to test their players. Instructions to submit a player are below.
You can work in a group or on your own. There are two categories for players, so you may want to consider that ahead of time. (Details are below.)
I think 6x8 is pretty good, and 15 games seems to work pretty well. This could change, however, so you should program your player to work for any board size.
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 less than 6 seconds on a 10x10 board 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. You can definitely include fields that your player uses to make moves.
Check out the instructions below. (After this EFAQ.)
Right now I don't have any place to do that easily. I'll try to get working on that! In the meantime, you can manipulate the Javascript on your own to include your player twice.
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 (famous last words).
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 FlagColoring class, which uses the prototype package to define objects:
/**
* Flag Coloring.
*
* Grid is stored as a 2D array of strings.
* @author Kyle Burke
*/
var FlagColoring = Class.create(CombinatorialGame, {
/**
* Constructor.
*/
initialize: function(height, width, colorsList) {
this.colorsList = colorsList || ["red", "yellow", "green", "blue", "black", "white"];
this.playerNames = ["Left", "Right"];
this.columns = new Array();
for (var colI = 0; colI < width; colI++) {
var column = new Array();
for (var rowI = 0; rowI < height; rowI++) {
column.push(this.colorsList[Math.floor(Math.random() * this.colorsList.length)]);
}
this.columns.push(column);
}
}
/**
* Returns the width of this board.
*/
,getWidth: function() {
return this.columns.length;
}
/**
* Returns the height of this board.
*/
,getHeight: function() {
if (this.getWidth() == 0) {
return 0;
} else {
return this.columns[0].length;
}
}
/**
* Equals!
*/
,equals: function(other) {
//check that the dimensions match
if (this.getWidth() != other.getWidth() || this.getHeight() != other.getHeight()) {
return false;
}
//now check that all the cells are equal
for (var col = 0; col < this.columns.length; col++) {
for (var row = 0; row < this.columns[col].length; row++) {
if (!this.columns[col][row] == other.columns[col][row]) {
return false;
}
}
}
return true;
}
/**
* Clone.
*/
,clone: function() {
var width = this.getWidth();
var height = this.getHeight();
var other = new FlagColoring(height, width, this.colorsList);
for (var col = 0; col < width; col++) {
for (var row = 0; row < height; row++) {
other.columns[col][row] = this.columns[col][row];
}
}
return other;
}
/**
* Gets two lists, a list of the vertices in the same region as the current vertex and the neighbors of that region.
*/
,getRegionAndNeighbors: function(column, row) {
//unmark all the vertices
var marks = [];
for (var i = 0; i < this.getWidth(); i++) {
var columnMarks = [];
for (var j = 0; j < this.getHeight(); j++) {
columnMarks.push(false);
}
marks.push(columnMarks);
}
//clone the current board (might not need this)
var clone = this.clone();
//grow the region out from the current vertex
var region = [];
var neighbors = [];
var regionColor = this.columns[column][row];
this.getRegionAndNeighborsHelper(column, row, regionColor, marks, region, neighbors);
return [region, neighbors];
}
/**
* Helper function for getRegionAndNeighbors. This is void, instead modifying marks, region, and neighbors.
*/
,getRegionAndNeighborsHelper: function(column, row, regionColor, marks, region, neighbors) {
if (marks[column][row]) {
return;
}
marks[column][row] = true;
//check whether we're in the same region
if (regionColor == this.columns[column][row]) {
//yes! Add and keep expanding
region.push([column, row]);
//check the four adjacent vertices to keep expanding
//first to the left
var nextCol = column - 1;
var nextRow = row;
if (nextCol >= 0) {
this.getRegionAndNeighborsHelper(nextCol, nextRow, regionColor, marks, region, neighbors);
}
//next above
nextCol = column;
nextRow = row-1;
if (nextRow >= 0) {
this.getRegionAndNeighborsHelper(nextCol, nextRow, regionColor, marks, region, neighbors);
}
//next right
nextCol = column + 1;
nextRow = row;
if (nextCol <= this.getWidth() - 1) {
this.getRegionAndNeighborsHelper(nextCol, nextRow, regionColor, marks, region, neighbors);
}
//next below
nextCol = column;
nextRow = row + 1;
if (nextRow <= this.getHeight() - 1) {
this.getRegionAndNeighborsHelper(nextCol, nextRow, regionColor, marks, region, neighbors);
}
} else {
//we're just a neighbor
neighbors.push([column, row]);
}
}
/**
* Gets the options.
*/
,getOptionsForPlayer: function(playerId) {
var options = new Array();
var width = this.getWidth();
var height = this.getHeight();
//check which vertices we've already seen using an array of booleans
var inRegionAlreadySeen = [];
for (var col = 0; col < width; col++) {
var inRegionAlreadySeenColumn = [];
for (var row = 0; row < height; row++) {
inRegionAlreadySeenColumn.push(false);
}
inRegionAlreadySeen.push(inRegionAlreadySeenColumn);
}
//traverse all vertices and add the options there if we haven't yet
for (var col = 0; col < width; col++) {
for (var row = 0; row < height; row++) {
if (!inRegionAlreadySeen[col][row]) {
var regionAndNeighbors = this.getRegionAndNeighbors(col, row);
var region = regionAndNeighbors[0];
var neighbors = regionAndNeighbors[1];
//get all the neighboring colors
var neighborColors = [];
for (var i = 0; i < neighbors.length; i++) {
var neighbor = neighbors[i];
var neighborColor = this.columns[neighbor[0]][neighbor[1]];
var hasColor = false;
for (var j = 0; j < neighborColors.length; j++) {
if (neighborColors[j] == neighborColor) {
hasColor = true;
break;
}
}
if (!hasColor) {
neighborColors.push(neighborColor);
}
}
//add moves to each color
for (var i = 0; i < neighborColors.length; i++) {
var option = this.colorRegion(region, neighborColors[i]);
options.push(option);
}
//mark all vertices in the region as already seen
for (var i = 0; i < region.length; i++) {
var vertex = region[i];
inRegionAlreadySeen[vertex[0]][vertex[1]] = true;
}
}
}
}
return options;
}
/**
* Gets a new position where the given region (list of coordinates) is colored.
*/
,colorRegion: function(region, color) {
var clone = this.clone();
for (var i = 0; i < region.length; i++) {
var vertex = region[i];
clone.columns[vertex[0]][vertex[1]] = color;
}
return clone;
}
}); //end of FlagColoring class