Gorgons Computer Tournament!

Round 0

Standings Summary


0 - 0
  • Random #0
  • Random #1
  • Random #2
  • Random #3
  • Random #4
  • Depth One #0
  • Depth One #1
  • Depth One #2
  • Depth One #3

Matches


Full Standings

  1. Depth One #2: (0 - 0, opp matches: 0 - 0, games: 0 - 0, opp games: 0 - 0)
    • Random #2: (0 - 0, opp matches: 0 - 0, games: 0 - 0, opp games: 0 - 0)
      • Random #3: (0 - 0, opp matches: 0 - 0, games: 0 - 0, opp games: 0 - 0)
        • Random #4: (0 - 0, opp matches: 0 - 0, games: 0 - 0, opp games: 0 - 0)
          • Depth One #1: (0 - 0, opp matches: 0 - 0, games: 0 - 0, opp games: 0 - 0)
            • Random #1: (0 - 0, opp matches: 0 - 0, games: 0 - 0, opp games: 0 - 0)
              • Random #0: (0 - 0, opp matches: 0 - 0, games: 0 - 0, opp games: 0 - 0)
                • Depth One #0: (0 - 0, opp matches: 0 - 0, games: 0 - 0, opp games: 0 - 0)
                  • Depth One #3: (0 - 0, opp matches: 0 - 0, games: 0 - 0, opp games: 0 - 0)

                    Make-Your-Own Player

                    (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 gorgon that can make a move and makes the first move it sees:

                    function userGetMove(playerId, gorgonsPosition) {
                        const directions = gorgonsPosition.getDirections();
                        const gorgonLocations = gorgonsPosition.getGorgons(playerId);
                        for (var i = 0; i < gorgonLocations.length; i++) {
                            const gorgonLoc = gorgonLocations[i];
                            for (var j = 0; j < directions.length; j++) {
                                const direction = directions[j];
                                if (gorgonsPosition.canFace(gorgonLoc, direction)) {
                                    const stoneLoc = gorgonsPosition.toStone(gorgonLoc, direction);
                                    return gorgonsPosition.getOptionFromMove(gorgonLoc, stoneLoc, gorgonLoc);
                                }
                            }
                        }
                    }

                    EFAQ: Expected Frequently-Asked Questions

                    What is Gorgons?

                    Gorgons is a partizan combinatorial game played on a square grid. On their turn, the current player chooses one of their gorgons to use. They then choose a direction for that gorgon to face, then move it in that direction (or leave it standing still). Before the gorgon moves, however, their gaze turns a space to stone. That space is either the first other gorgon (of either team) or the last empty space in the chosen direction. The first player who cannot move loses. You can play Gorgons here.

                    What is this for?

                    We are holding a computer player tournament as part of Sprouts 2024. People can use this to test their players. Instructions to submit a player are below.

                    Can I work on a team, or do I have to work independently?

                    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.)

                    How big will the boards be in the tournament? How many games will be played per match?

                    We're going to go with 8x8 boards with 15 three Gorgons on each team..

                    I wrote a brute-force player that always finds the optimal solution. Do I win?

                    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!)

                    What if I want to add more details to my player than just what current move to make? Does it have to be stateless?

                    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.

                    I got a player working real well! How do I submit it to your tournament?

                    Check out the instructions below. (After this EFAQ.)

                    I actually have two players and I would like to test them out against each other. Can I do that?

                    Yes, those directions are below!

                    How do I get updates about the tournament?

                    Keep watching this space, or watch @CGTKyle@mathstodon.xyz (Mastodon) for updates.

                    Kyle, this code is awful! Did you write this? I see tons of scripting code in the HTML source and inline styling. What have you done?

                    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).


                    Submitting Your Player to the Actual Tournament

                    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.

                    1. Choose a name for your player. The name should (1) be something no one else will choose, (2) be in PascalCase, and (3) be appropriate to read and speak in an academic setting. We reserve the right to drop players without notice, and vulgar or inappropriate language is part of that. We recommend keeping the name length to 15 characters.
                    2. Your class will need to subclass the ComputerPlayer class I've created, so you'll need to add some extra code to wrap your function in. Copy/paste the following code into a text file named <YourPlayerName>.js, with <YourPlayerName> replaced by the name you chose above.
                      //author: <Your name or your team's name>, yourcontactemail@example.com
                      var <YourPlayerName> = Class.create(ComputerPlayer, {
                          initialize: function() {
                              //nothing needed here, but you can add things
                              //if you want a stateful player
                          },
                      
                          givePosition: function(playerIndex, position, referee) {
                              //don't modify this method.
                              referee.moveTo(this.userGetMove(position));
                          },
                      
                          userGetMove: function(playerId, flagColoringPosition) {
                              //paste your code in here.
                          },
                      
                          getName: function() {
                              return "<YourPlayerName>";
                          },
                      
                          getAuthor: function() {
                              return "<Your name or your team's name>";
                          }
                      });
                    3. Copy paste the body of your userGetMove function into the function of the same name there. Feel free to add to your player's initialize (constructor) if you need to hold any info between moves.
                    4. Modify the name of the class to be your player's name. Modify the body of getName to also return your player's name as a string. Modify the body of getAuthor to return your name or your team's name. Finally, modify the first line to include your team name and a contact email address so we can get in touch with you if necessary.
                    5. If you make significant modifications, ensure again that your player makes moves within 6 seconds on a 10 x 10 board.
                    6. Use our Dropbox to submit your code. By submitting your player to us, you are giving us permission to run the code in a public setting. As mentioned above, we reserve the right to not include your submission in the tournament. Please use this Dropbox link to submit your player.
                    7. In order to be sure to get your player included in the tournament, please submit by 11:59pm (Eastern US Time) Thursday, April 18, 2024. The link above will continue to work after that time but if you miss the deadline, please reach out to me via email (paithanq@gmail.com) so we'll be notified of your late submission. If we are able to, we'll include your player! (Most years so far we are low on the number of players and would be excited to get more.)
                    8. If you create an even better player, please resubmit your code with the same (file) name. If this system works, we'll use the latest version provided before the deadline above.

                    Testing Two Players

                    By popular demand, we've included a way to pit two (or more) players against each other.


                    Gorgons code

                    Here is the underlying JavaScript code for the Gorgons class, which uses the prototype package to define objects:

                    /**
                     * Game of Gorgons .
                     * 
                     * Grid is represented as:
                     *  - board 2D grid of board contents as strings (columns as first index).  Each element can be either empty ("blank"), blue gorgon ("gorgon blue"), red gorgon ("gorgon red"), stone block ("stone blank"), stone blue gorgon ("stone gorgon blue"), or stone red gorgon ("stone gorgon red").
                     * @author Kyle Burke
                     */
                    var Gorgons = Class.create(CombinatorialGame, {
                       
                        /**
                         * Constructor.
                         */
                        initialize: function(size, numBlueGorgons, numRedGorgons) {
                            numRedGorgons = numRedGorgons || numBlueGorgons;
                            this.playerNames = Gorgons.prototype.PLAYER_NAMES;
                            const width = size;
                            const height = size;
                            if (numBlueGorgons < 0 || numRedGorgons < 0) {
                                console.log("ERROR: trying to create a game with negative gorgons!");
                                return;
                            } else if (Math.max(numBlueGorgons, numRedGorgons) > (width + height) / 2) {
                                console.log("ERROR: too many gorgons chosen, so we're going down to " + size + " gorgons per side.");
                            }
                            this.board = [];
                            for (var i = 0; i < width; i++) {
                                const column = [];
                                for (var j = 0; j < height; j++) {
                                    column.push("blank");
                                }
                                this.board.push(column);
                            }
                            const evenWidthAbove = width % 2 == 0 ? width : (width + 1);
                            const evenWidthBelow = width % 2 == 0 ? width : (width - 1);
                            for (var i = 0; i < numRedGorgons; i++) {
                                //place a red gorgon
                                var row = Math.floor( (2*i) / width);
                                var column = (2 * i) % evenWidthAbove;// + Math.pow(-1, row);
                                this.board[column][row] = "gorgon red";
                            }
                            for (var i = 0; i < numBlueGorgons; i++) {  
                                //place a blue gorgon
                                row = height - 1 - Math.floor( (2 * i) / evenWidthBelow);
                                column = (2 * i + 1) % evenWidthBelow;
                                this.board[column][row] = "gorgon blue";
                            }
                        }
                        
                        /**
                         * Returns the width of this board.
                         */
                        ,getWidth: function() {
                            return this.board.length;
                        }
                        
                        /**
                         * Returns the height of this board.
                         */
                        ,getHeight: function() {
                           return this.board[0].length;
                        }
                        
                        /**
                         * Returns the number of pieces for a player.
                         */
                        ,getNumGorgons: function(playerId) {
                            var count = 0;
                            const pieceName = "gorgon " + ( playerId == 0 ? "blue" : "red");
                            for (var i = 0; i < this.getWidth(); i++) {
                                for (var j = 0; j < this.getHeight(); j++) {
                                    if (this.board[i][j] == pieceName) {
                                        count ++;
                                    }
                                }
                            }
                            return count;
                        }
                        
                        /**
                         * Equals!
                         */
                        ,equals: function(other) {
                            if (this.getWidth() != other.getWidth() || this.getHeight() != other.getHeight()) {
                                return false;
                            }
                            for (var i = 0; i < this.getWidth(); i++) {
                                for (var j = 0; j < this.getHeight(); j++) {
                                    if (this.board[i][j] != other.board[i][j]) {
                                        return false;
                                    }
                                }
                            }
                            return true;
                        }
                        
                        /**
                         * Clone.
                         */
                        ,clone: function() {
                            var clone = new Gorgons(this.getWidth(), 0);
                            clone.board = [];
                            for (var i = 0; i < this.getWidth(); i++) {
                                const col = [];
                                for (var j = 0; j < this.getHeight(); j++) {
                                    col.push(this.board[i][j]);
                                }
                                clone.board.push(col);
                            }
                            return clone;
                        }
                        
                        /**
                         * Returns whether two sets of coordinates are equal.
                         */
                        ,coordinatesEquals: function(coordsA, coordsB) {
                            return coordsA[0] == coordsB[0] && coordsA[1] == coordsB[1];
                        }
                        
                        /**
                         * Returns a list of the locations of spaces a gorgon can stone.
                         */
                        ,stoneTilesForGorgon: function(gorgonLoc) {
                            const directions = this.getDirections();
                            const stoneTiles = [];
                            for (var i = 0; i < directions.length; i++) {
                                const direction = directions[i];
                                if (this.canFace(gorgonLoc, direction)) {
                                    stoneTiles.push(this.toStone(gorgonLoc, direction));
                                }
                            }
                            return stoneTiles;
                        }
                        
                        /**
                         * Returns the coordinates of the space that would be stoned, [col, row].  Coordinates is a 2-vector.  Direction is a 2-vector where the values are either 0, 1, or -1 in any combination except for [0, 0].
                         */
                        ,toStone: function(source, direction) {
                            var current = source;
                            var next;
                            //console.log("source: " + source);
                            //console.log("direction: " + direction);
                            while(true) {
                                next = [current[0] + direction[0], current[1] + direction[1]];
                                //console.log("current: " + current);
                                //console.log("next: " + next);
                                if (next[0] == -1 || next[0] == this.getWidth() || next[1] == -1 || next[1] == this.getHeight()) {
                                    //next is off the board
                                    if (this.coordinatesEquals(current,source)) {
                                        //console.log("The gorgon can't stone in this direction!");
                                        return undefined; //we don't want to return the source.  This gorgon can't move in that direction.
                                    } else {
                                        return current;
                                    }
                                } else {
                                    const content = this.board[next[0]][next[1]];
                                    if (content.substring(0, 5) == "stone") {
                                        //the next space is a stone.  Return the prior one.
                                        if (this.coordinatesEquals(current, source)) {
                                            return undefined; //not if we're at the same place
                                        } else {
                                            return current;
                                        }
                                    } else if (content != "blank") {
                                        return next;
                                    }
                                }
                                current = next;
                            }
                            console.log("Shouldn't reach here!  (End of toStone)");
                        }
                        
                        /**
                         * Determines whether a gorgon at a given location [col, row] can turn to the specified direction [col, row].
                         */
                        ,canFace: function(source, direction) {
                            const neighborSpace = [source[0] + direction[0], source[1] + direction[1]];
                            return !(neighborSpace[0] == -1 || neighborSpace[0] == this.getWidth() || neighborSpace[1] == -1 || neighborSpace[1] == this.getHeight() || this.board[neighborSpace[0]][neighborSpace[1]].substring(0,5) == "stone");
                        }
                        
                        /**
                         * Returns the eight possible directions.
                         */
                        ,getDirections: function() {
                            return [[0, 1], [0, -1], [1, 0], [-1, 0], [1, 1], [1, -1], [-1, 1], [-1, -1]];
                        }
                        
                        /**
                         * Returns the locations of the gorgons for a specified player.
                         */
                        ,getGorgons: function(playerId) {
                            const gorgons = [];
                            const gorgonName = "gorgon " + (playerId == 0 ? "blue" : "red");
                            for (var i = 0; i < this.getWidth(); i++) {
                                for (var j = 0; j < this.getHeight(); j++) {
                                    const contents = this.board[i][j];
                                    if (contents == gorgonName) {
                                        gorgons.push([i, j]);
                                    }
                                }
                            }
                            return gorgons;
                        }
                        
                        /**
                         * Returns the options from a gorgon facing in one direction.
                         */
                        ,getOptionsForGorgonInDirection: function(gorgonLoc, direction) {
                            if (!this.canFace(gorgonLoc, direction)) {
                                return [];
                            }
                            //console.log("gorgonLoc: " + gorgonLoc);
                            //console.log("direction: " + direction);
                            const options = [];
                            const baseWithStone = this.clone();
                            const toStone = baseWithStone.toStone(gorgonLoc, direction);
                            //console.log("toStone: " + toStone);
                            baseWithStone.board[toStone[0]][toStone[1]] = "stone " + baseWithStone.board[toStone[0]][toStone[1]];
                            options.push(baseWithStone); //gorgon doesn't move
                            var moveTo = [gorgonLoc[0] + direction[0], gorgonLoc[1] + direction[1]];
                            while (!this.coordinatesEquals(moveTo, toStone)) {
                                //console.log("moveTo: " + moveTo);
                                const option = baseWithStone.clone();
                                const gorgon = option.board[gorgonLoc[0]][gorgonLoc[1]]; //gorgon's name
                                option.board[gorgonLoc[0]][gorgonLoc[1]] = "blank";
                                option.board[moveTo[0]][moveTo[1]] = gorgon;
                                options.push(option);
                                moveTo = [moveTo[0] + direction[0], moveTo[1] + direction[1]];
                                //console.log("option added!");
                            }
                            return options;
                        }
                        
                        /**
                         * Gets the direction from between two locations.
                         */
                        ,getDirectionFromPoints: function(source, destination) {
                            const difference = [destination[0] - source[0], destination[1] - source[1]];
                            //check for illegal differences
                            if (difference[0] != 0 && difference[1] != 0 && (Math.abs(difference[0]) != Math.abs(difference[1]))) {
                                //illegal combination!
                                return "Nope!";
                            } else {
                                const direction = [];
                                direction.push(difference[0] / (Math.max(1, Math.abs(difference[0]))));
                                direction.push(difference[1] / (Math.max(1, Math.abs(difference[1]))));
                                return direction;
                            }
                        }
                        
                        /**
                         * Gets the options.
                         */
                        ,getOptionsForPlayer: function(playerId) {
                            const gorgons = this.getGorgons(playerId);
                            const options = [];
                            const directions = this.getDirections();
                            for (var i = 0; i < gorgons.length; i++) {
                                const gorgon = gorgons[i];
                                //console.log("i: " + i);
                                for (var j = 0; j < directions.length; j++) {
                                    //console.log("j: " + j);
                                    const direction = directions[j];
                                    if (this.canFace(gorgon, direction)) {
                                        const newOptions = this.getOptionsForGorgonInDirection(gorgon, direction);
                                        for (var k = 0; k < newOptions.length; k++) {
                                            //console.log("k: " + k);
                                            options.push(newOptions[k]);
                                        }
                                    }
                                }
                            }
                            return options;
                        }
                        
                        /**
                         * Returns the option for moving a gorgon.  All three parameters are [row, col] cooredinates.
                         */
                        ,getOptionFromMove: function(gorgonSource, newStoneLoc, gorgonDest) {
                            const direction = this.getDirectionFromPoints(gorgonSource, newStoneLoc);
                            console.log("direction: " + direction);
                            if (this.canFace(gorgonSource, direction)) {
                                const option = this.clone();
                                option.board[newStoneLoc[0]][newStoneLoc[1]] = "stone " + option.board[newStoneLoc[0]][newStoneLoc[1]];
                                const gorgonString = option.board[gorgonSource[0]][gorgonSource[1]];
                                option.board[gorgonSource[0]][gorgonSource[1]] = "blank";
                                option.board[gorgonDest[0]][gorgonDest[1]] = gorgonString;
                                return option;
                            } else {
                                return null;
                            }
                        }
                        
                        /**
                         * Returns whether two sets of coordinates are equal.
                         */
                        ,coordinatesEquals: function(coordsA, coordsB) {
                            return coordsA[0] == coordsB[0] && coordsA[1] == coordsB[1];
                        }
                        
                    }); //end of Gorgons class
                    Gorgons.prototype.PLAYER_NAMES = ["Blue", "Red"];