1st place in the CodeCombat Criss-Cross tournament on the Ogres side http://blog.codecombat.com/a-good-new-fashioned-programming-throwdown

CodeCombat_CrissCross_HighSea.js

/*
Copyright (c) 2014 Michael Polyak. All Rights Reserved.
 
mpolyak@gmail.com
 
CodeCombat Criss-Cross, HighSea "Ogres"
*/

var GOLD = 128;
var SIZE = 6;

var VECTOR =
{
    humans:
    {
        x: 1, y: 0
    },

    ogres:
    {
        x: 0, y: 1
    }
};

var DETAILED = false;

var DEBUG = false;

function tileInList(tile, list)
{
    for (var i = 0; i < list.length; i ++)
    {
        if (list[i].id === tile.id)
            return true;
    }

    return false;
}

function traceRoutes(team, origin, vector, free, grid, ranks)
{
    var higher = function (a, b)
    {
        if (a.score == b.score)
        {
            if (a.team === b.team)
                return (a.rank < b.rank) - (a.rank > b.rank);

            return (a.team < b.team) - (a.team > b.team);
        }

        return (a.score < b.score) - (a.score > b.score);
    };

    var lower = function (a, b)
    {
        if (a.score === b.score)
            return (a.rank > b.rank) - (a.rank < b.rank);

        return (a.score > b.score) - (a.score < b.score);
    };

    var tiles = [{tile: origin}]; var visited = {};

    visited[origin.id] = origin;

    var i;

    var tile;

    while (tiles.length)
    {
        tile = tiles.shift().tile;

        if ((vector.x && tile.x === SIZE) || (vector.y && tile.y === SIZE))
        {
            // Slower but more accurate routes generation.
            if (DETAILED)
            {
                var list = [];

                for (i = 0; i < tiles.length; i ++)
                {
                    tile = tiles[i];

                    if (tile.team && ((vector.x && tile.tile.y !== SIZE) || (vector.y && tile.tile.x !== SIZE)))
                        list.push(tile);
                }

                tiles = list.sort(lower);

                continue;
            }
            else
                break;
        }

        var next;

        for (i = 0; i < tile.neighbors.length; i ++)
        {
            next = tile.neighbors[i];

            if ((next.owner && next.owner !== team) || visited[next.id])
                continue;

            visited[next.id] = tile;

            tiles.push({tile: next, team: next.owner === team ? 1 : 0, rank: ranks[next.x][next.y],
                score: (vector.x ? next.x : 0) + (vector.y ? next.y : 0)});
        }

        tiles = tiles.sort(higher);
    }

    var routes = [];

    for (i = 0; i <= SIZE; i ++)
    {
        var target = grid[vector.x ? SIZE : i][vector.y ? SIZE : i]; tile = target;

        if (!visited[tile.id])
            continue;

        var owned = []; var need = []; var used = null; var distance = 0; tiles = [];

        while ((vector.x && tile.x) || (vector.y && tile.y))
        {
            tiles.push(tile);

            if (tile.id === free.id) {
                need.push(tile); used = tile;
            }
            else
            {
                if (tile.owner === team) {
                    owned.push(tile);
                }
                else {
                    need.push(tile); distance ++;
                }
            }

            tile = visited[tile.id];
        }

        if (!tileInList(tile, tiles))
        {
            tiles.push(tile);

            if (tile.id === free.id) {
                need.push(tile); used = tile;
            }
            else
            {
                if (tile.owner === team) {
                    owned.push(tile);
                }
                else {
                    need.push(tile); distance ++;
                }
            }
        }

        routes.push({origin: tile, target: target, tiles: tiles, owned: owned, need: need, free: used, distance: distance});
    }

    return routes;
}

function rankGrid(team, free, grid)
{
    var vector = VECTOR[team];

    var table = [];

    for (var x = 0; x <= SIZE; x ++)
    {
        var column = [];

        for (var y = 0; y <= SIZE; y ++)
        {
            var tile = grid[x][y];

            if (tile.owner && tile.owner !== team) {
                column.push(0);
            }
            else
            {
                var rank = tile.owner === team || tile.id === free.id ? 2 : 0;

                for (var i = 0; i < tile.neighbors.length; i ++)
                {
                    var next = tile.neighbors[i];

                    if (next.id === free.id) {
                        rank += 1;
                    }
                    else if (next.owner)
                    {
                        if (next.owner === team) {
                            rank += 1;
                        }
                        else if ((vector.x && tile.x === next.x) || (vector.y && tile.y === next.y))
                            rank += 1;
                    }
                }

                column.push(rank);
            }
        }

        table.push(column);
    }

    return table;
}

function teamRoutes(team, free, grid)
{
    var vector = VECTOR[team];

    var i;

    var ranks = [];

    for (i = 0; i < free.length; i ++)
        ranks.push(rankGrid(team, free[i], grid));

    var j;
    var k;

    var list;

    var routes = []; var distance = -1;

    for (i = 0; i <= SIZE; i ++)
    {
        var origin = grid[vector.y ? i : 0][vector.x ? i : 0];

        if (origin.owner && origin.owner !== team)
            continue;

        for (j = 0; j < free.length; j ++)
        {
            list = traceRoutes(team, origin, vector, free[j], grid, ranks[j]);

            for (k = 0; k < list.length; k ++)
            {
                if (distance !== -1)
                {
                    if (list[k].distance <= distance) {
                        distance = list[k].distance;
                    }
                    else
                        continue;
                }
                else
                    distance = list[k].distance;
                
                routes.push(list[k]);
            }
        }
    }

    list = [];

    for (i = 0; i < routes.length; i ++)
    {
        if (routes[i].distance > distance)
            continue;

        if (!routes[i].free)
        {
            for (j = 0; j < list.length; j ++)
            {
                if (list[j].origin.id === routes[i].origin.id && list[j].target.id === routes[i].target.id && list[j].owned.length === routes[i].owned.length)
                {
                    for (k = 0; k < list[j].owned.length; k ++)
                    {
                        if (!tileInList(list[j].owned[k], routes[i].owned))
                            break;
                    }

                    if (k === list[j].owned.length)
                        break;
                }
            }

            if (j !== list.length)
                continue;
        }

        list.push(routes[i]);
    }

    return list.sort(function (a, b)
    {
        if (a.distance !== b.distance)
            return (a.distance > b.distance) - (a.distance < b.distance);

        if (a.owned.length !== b.owned.length)
            return (a.owned.length < b.owned.length) - (a.owned.length > b.owned.length);

        if (!a.free || !b.free)
            return a.free ? -1 : (b.free ? 1 : 0);

        var i;

        var tile;

        var foesA = 0;
        var foesB = 0;

        for (i = 0; i < a.free.neighbors.length; i ++)
        {
            tile = a.free.neighbors[i];

            if (tile.owner && tile.owner !== team && ((vector.x && a.free.x === tile.x) || (vector.y && a.free.y === tile.y)))
                foesA ++;
        }

        for (i = 0; i < b.free.neighbors.length; i ++)
        {
            tile = b.free.neighbors[i];

            if (tile.owner && tile.owner !== team && ((vector.x && b.free.x === tile.x) || (vector.y && b.free.y === tile.y)))
                foesB ++;
        }

        if (foesA === foesB)
        {
            var centerA = Math.pow(a.free.x - (SIZE / 2), 2) + Math.pow(a.free.y - (SIZE / 2), 2);
            var centerB = Math.pow(b.free.x - (SIZE / 2), 2) + Math.pow(b.free.y - (SIZE / 2), 2);

            if (centerA === centerB)
            {
                centerA = Math.abs((vector.x ? a.origin.y : a.origin.x) - (SIZE / 2));
                centerB = Math.abs((vector.x ? b.origin.y : b.origin.x) - (SIZE / 2));

                if (centerA === centerB)
                {
                    centerA = Math.abs((vector.x ? a.target.y : a.target.x) - (SIZE / 2));
                    centerB = Math.abs((vector.x ? b.target.y : b.target.x) - (SIZE / 2));
                }
            }

            return (centerA > centerB) - (centerA < centerB);
        }

        return (foesA < foesB) - (foesA > foesB);
    });
}

function adjacentFoes(team, tile)
{
    var vector = VECTOR[team];

    var foes = 0;

    for (var i = 0; i < tile.neighbors.length; i ++)
    {
        var next = tile.neighbors[i];

        if (next.owner && next.owner !== team && ((vector.x && next.x === tile.x) || (vector.y && next.y === tile.y)))
            foes ++;
    }

    return foes;
}

function firstRoute(team, free, grid)
{
    var vector = VECTOR[team];

    var tiles = [];

    var i;

    for (i = 0; i < free.length; i ++)
    {
        tiles.push({tile: free[i], foes: adjacentFoes(team, free[i]),
            center: Math.pow(free[i].x - (SIZE / 2), 2) + Math.pow(free[i].y - (SIZE / 2), 2)});
    }

    var list = tiles.sort(function (a, b)
    {
        if (a.foes === b.foes)
            return (a.center > b.center) - (a.center < b.center);

        return (a.foes < b.foes) - (a.foes > b.foes);
    });

    tiles = [];

    for (i = 0; i <= SIZE; i ++)
        tiles.push(grid[vector.x ? i : list[0].tile.x][vector.y ? i : list[0].tile.y]);

    return {origin: tiles[0], target: tiles[SIZE], tiles: tiles, owned: [], need: [list[0].tile], free: list[0].tile, distance: SIZE};
}

function calculateBid(team, ourGold, foeGold, ourRoutes, forRoutes, ourShortest, foeShortest, gold, limit)
{
    if (!ourGold)
        return {debug: DEBUG ? " NO GOLD" : "", highlight: [], gold: 0, tile: null};

    var debug = ""; var highlight = [];

    var tile = null;

    var i;

    var ourRoute;
    var foeRoute;

    // We have routes.
    if (ourRoutes.length)
    {
        // We have a tile to bid on.
        if (ourRoutes[0].free)
        {
            // We are not on the last tile.
            if (ourRoutes[0].distance)
            {
                if (foeGold && foeRoutes.length)
                {
                    if (forRoutes[0].distance)
                    {
                        var foes = adjacentFoes(team, ourRoutes[0].free);

                        // Cross-reference opponent's routes with our and pick a common tile to bid on.
                        for (i = 0; i < foeRoutes.length; i ++)
                        {
                            foeRoute = foeRoutes[i];

                            if (!foeRoute.free)
                                continue;

                            for (var j = 0; j < ourRoutes.length; j ++)
                            {
                                ourRoute = ourRoutes[j];

                                if (!ourRoute.free)
                                    continue;

                                if ((foeRoute.distance === 1 && (ourRoute.free.id === foeRoute.free.id || tileInList(foeRoute.free, ourRoute.need))) ||
                                    (ourRoute.free.id === foeRoute.free.id && adjacentFoes(team, ourRoute.free) >= foes))
                                {
                                    if (DEBUG) {
                                        debug += " SHARED"; highlight = ourRoute.tiles;
                                    }

                                    tile = foeRoute.free;

                                    if (foeRoute.distance === 1)
                                    {
                                        if (DEBUG)
                                            debug += " STEAL";

                                        // Try to steal opponent's tile.
                                        if (foeRoute.free.id === ourRoute.free.id) {
                                            gold = Math.min(Math.floor(ourGold / Math.max(ourRoute.distance, 2)), foeGold + 1);
                                        }
                                        else
                                            gold = Math.min(Math.floor(ourGold / (ourRoute.distance + 1)), foeGold + 1);
                                    }
                                    else
                                    {
                                        if (DEBUG)
                                            debug += " SAME";

                                        // We're both going after the same tile.
                                        if (foes) {
                                            gold = Math.min(limit, Math.min(Math.floor(ourGold / (ourRoutes[0].distance + 1)), foeGold + 1));
                                        }
                                        else
                                            gold = Math.min(Math.min(gold, Math.floor(ourGold / (ourRoutes[0].distance + 1))), foeGold + 1);
                                    }

                                    break;
                                }
                            }

                            if (tile)
                                break;
                        }

                        if (!tile)
                        {
                            if (DEBUG) {
                                debug += " OPTIMAL"; highlight = ourRoutes[0].tiles;
                            }

                            if (ourShortest > 1 && foeRoutes[0].distance === 1 && foeRoutes[0].free)
                            {
                                if (DEBUG)
                                    debug += " STEAL";

                                // Try to steal opponent's tile.
                                gold = Math.min(limit, Math.min(Math.floor(ourGold / (ourShortest + 1)), foeGold + 1)); tile = foeRoutes[0].free;
                            }
                            else
                            {
                                if (ourShortest > 1 && ourGold >= foeGold && foeRoutes[0].distance === 1 && !foeRoutes[0].free)
                                {
                                    if (DEBUG)
                                        debug += " SKIP";
                                }
                                else
                                {
                                    tile = ourRoutes[0].free;

                                    // Bid on our most optimal tile.
                                    if (foes) {
                                        gold = Math.min(limit, Math.min(Math.floor(ourGold / (ourRoutes[0].distance + 1)), foeGold + 1));
                                    }
                                    else
                                        gold = Math.min(Math.min(gold, Math.floor(ourGold / (ourRoutes[0].distance + 1))), foeGold + 1);
                                }
                            }
                        }
                    }
                    else
                    {
                        if (DEBUG)
                            debug += " BLOCK"; highlight = foeRoutes[0].tiles;

                        // Try to block opponent's lat tile bid.
                        gold = Math.min(ourGold, foeGold + 1); tile = foeRoutes[0].free;
                    }
                }
                else
                {
                    // Our opponent has no tile to bid on.

                    if (DEBUG) {
                        debug += " OPTIMAL"; highlight = ourRoutes[0].tiles;
                    }

                    // Bid on our most optimal tile.
                    gold = Math.min(gold, Math.floor(ourGold / (ourRoutes[0].distance + 1))); tile = ourRoutes[0].free;
                }
            }
            else
            {
                if (DEBUG)
                    debug += " FINAL"; highlightRoutes = ourRoutes[0].tiles;

                // Bid everything on our last tile.
                gold = ourGold; tile = ourRoutes[0].free;
            }
        }
        else if (foeGold && foeRoutes.length && foeRoutes[0].free)
        {
            // We have no tile to bid on, bid on opponent's tile.

            foeRoute = foeRoutes[0]; tile = foeRoute.free;

            if (DEBUG) {
                debug += " NO ROUTE"; highlight = foeRoute.tiles;
            }

            if (foeRoute.distance)
            {
                var distance;

                if (foeRoute.distance === 1)
                {
                    // Our opponent is two tiles away from winning, attempt to steal this tile.

                    if (DEBUG)
                        debug += " STEAL";

                    if (ourRoutes[0].distance === 1)
                    {
                        // We are two tiles away from winning as well.
                        gold = Math.min(Math.floor(ourGold / 2), Math.floor(foeGold / 2) + 1);
                    }
                    else
                    {
                        distance = ourRoutes[0].distance + 1;

                        // See if opponent's tile is of use in any of our routes.
                        for (i = 0; i < ourRoutes.length; i ++)
                        {
                            ourRoute = ourRoutes[i];

                            if (tileInList(tile, ourRoute.need))
                            {
                                if (DEBUG)
                                    debug += " SHARED";

                                distance = ourRoute.distance;

                                break;
                            }
                        }

                        gold = Math.min(Math.floor(ourGold / distance), foeGold + 1);
                    }
                }
                else
                {
                    distance = ourRoutes[0].distance + foeRoute.distance + 1;

                    // See if opponent's tile is of use in any of our routes.
                    for (i = 0; i < ourRoutes.length; i ++)
                    {
                        ourRoute = ourRoutes[i];

                        if (tileInList(tile, ourRoute.need))
                        {
                            if (DEBUG)
                                debug += " SHARED";

                            distance = ourRoute.distance;

                            break;
                        }
                    }

                    gold = Math.min(gold, Math.floor(ourGold / distance));

                    // We can't afford to bid on opponent's tile.
                    if (ourGold - gold <= foeGold)
                    {
                        if (DEBUG)
                            debug += " EXPENSIVE";

                        gold = Math.max(0, (ourGold - foeGold) - 1);
                    }
                }
            }
            else
            {
                if (DEBUG)
                    debug += " BLOCK";

                // Bid enough to try to win opponent's last tile.
                if (ourGold > foeGold) {
                    gold = Math.min(ourGold - 1, foeGold + 1);
                }
                else
                    gold = ourGold;
            }
        }
    }
    else
    {
        // We are blocked.

        if (DEBUG)
            debug += " BLOCKED";

        if (foeGold && foeRoutes.length)
        {
            // Bid on any free opponent tile.
            for (i = 0; i < foeRoutes.length; i ++)
            {
                foeRoute = foeRoutes[i];

                if (DEBUG)
                    highlight = foeRoute.tiles;

                tile = foeRoute.tile;

                // Bid enough to try to win opponent tile.
                if (foeRoute.distance) {
                    gold = Math.min(ourGold, Math.floor(foeGold / (foeRoute.distance + 1)) + 1);
                }
                else
                    gold = Math.min(ourGold, foeGold + 1);

                break;
            }
        }
    }

    return {debug: debug, highlight: highlight, gold: gold, tile: tile};
}

function firstBid(gold, route)
{
    var fraction = 0.5 * (1 - ((Math.sqrt(Math.pow(route.free.x - (SIZE / 2), 2) + Math.pow(route.free.y - (SIZE / 2), 2))) / Math.sqrt(SIZE * 3)));

    return {debug: DEBUG ? " FIRST" : "", highlight: DEBUG ? route.tiles : [],
        gold: Math.floor((gold / (SIZE + 1)) * fraction) + 1, tile: route.free};
}

function maximumBid(team, gold, turns)
{
    var bids = [];

    var average = 0;
    var stddev = 0;

    var i;

    var bid;

    for (i = 0; i < turns.length; i ++)
    {
        bid = team === "humans" ? turns[i].ogreBid.bid : turns[i].humanBid.bid;

        if (!isNaN(bid) && bid) {
            bids.push(bid); average += bid;
        }
    }

    if (!bids.length)
        return turns.length ? turns[0][team === "humans" ? "humanBid" : "ogreBid"].bid * 2 : gold;

    average /= bids.length;

    for (i = 0; i < bids.length; i ++) {
        bid = bids[i]; stddev += Math.pow(bid - average, 2);
    }

    stddev = Math.sqrt(stddev / bids.length);

    if (stddev < average)
        return Math.min(gold, Math.max(Math.floor(stddev), bid) + 1);

    return gold;
}

function freeTiles(tiles)
{
    var free = [];

    for (var i = 0; i < tiles.length; i ++)
    {
        if (!tiles[i].owner)
            free.push(tiles[i]);
    }

    return free;
}

this.printRoute = function (route, debug)
{
    var tiles = "";

    for (var i = 0; i < route.tiles.length; i ++)
        tiles += "[" + route.tiles[i].id + "]";

    var text = route.origin.id + " -> " + route.target.id + ": " + route.distance +
        " (" + route.owned.length + ")" + (route.free ? " (" + route.free.id + ")" : "") + (tiles ? " " + tiles : "");

    if (debug || debug === undefined)
        this.debug(text);

    return text;
};

var foeGold = this.turns.length ?
    this.turns[this.turns.length - 1][this.team === "humans" ? "ogreGold" : "humanGold"] : GOLD;

var free = freeTiles(this.tileGroups[tileGroupLetter]);

var ourRoutes = this.myTiles.length ?
    teamRoutes(this.team, free, this.tileGrid) : [firstRoute(this.team, free, this.tileGrid)];

var they = this.team === "humans" ? "ogres" : "humans";

var foeRoutes = this.opponentTiles.length ?
    teamRoutes(they, free, this.tileGrid) : [];

if (this.turns.length === 0)
{
    this.ourShortest = SIZE + 1;
    this.foeShortest = SIZE + 1;
}
else
{
    if (ourRoutes.length && ourRoutes[0].distance < this.ourShortest)
        this.ourShortest = ourRoutes[0].distance;

    if (foeRoutes.length && foeRoutes[0].distance < this.foeShortest)
        this.foeShortest = foeRoutes[0].distance;
}

var foeBid = calculateBid(they, foeGold, this.gold, foeRoutes, ourRoutes,
    this.foeShortest, this.ourShortest, foeGold, foeGold);

var maxBid = maximumBid(this.team, this.gold, this.turns, this.debug);

var ourBid;

if (!this.myTiles.length && !this.opponentTiles.length && !this.highBidder) {
    ourBid = firstBid(this.gold, ourRoutes[0]);
}
else
{
    ourBid = calculateBid(this.team, this.gold, foeGold, ourRoutes, foeRoutes, this.ourShortest, this.foeShortest,
        Math.min(maxBid, !this.highBidder && foeBid.tile ? foeBid.gold + 1 : this.gold), foeBid.tile ? foeBid.gold + 1 : this.gold);
}

if (this.turns.length === 1)
{
    var our = this.turns[0][this.team == "humans" ? "humanBid" : "ogreBid"].bid;
    var foe = this.turns[0][this.team == "humans" ? "ogreBid" : "humanBid"].bid;

    if (isNaN(our))
        our = 0;

    if (isNaN(foe))
        foe = 0;

    this.highBidder = our !== Math.floor(GOLD / (SIZE + 1)) && our < foe;
}

if (DEBUG)
{
    var debug = this.round + "/" + this.turns.length + ": OUR GOLD " + this.gold + " FOE GOLD " + foeGold;

    debug += " OUR SHORTEST " + this.ourShortest;
    debug += " FOE SHORTEST " + this.foeShortest;

    if (ourRoutes.length)
        debug += " OUR ROUTE " + this.printRoute(ourRoutes[0], false);

    if (foeRoutes.length)
        debug += " FOE ROUTE " + this.printRoute(foeRoutes[0], false);

    if (foeBid.tile)
        debug += " FOE BID " + (foeBid.gold + 1);

    debug += " MAX BID " + maxBid + ourBid.debug;

    if (ourBid.tile) {
        debug += " OUR BID " + ourBid.tile.id + " @ " + ourBid.gold;
    }
    else
        debug += " NO BID";

    this.debug(debug);

    for (var i = 0; i < ourBid.highlight.length; i ++)
        this.highlightTile(ourBid.highlight[i]);
}
else if (!ourBid.gold || !ourBid.tile)
    return null;

return {gold: ourBid.tile ? ourBid.gold : 0, desiredTile: ourBid.tile};

Solution description:

I was very excited to see another CodeCombat tournament after participating in the Greed challenge earlier and I really enjoyed it having not done any game related development in years.

Off the bat the problem seemed like it would require a more computationally intensive solution, since I would need to traverse a 7x7 grid with an additional set of up to 7 available tiles to take into account at each turn of the game.

My first step was to implement a route calculation system based on the A* algorithm with a bias towards picking tiles that are already owned by me or are adjacent to those that I own, or tiles that could possibly block my opponent in his direction of travel.

I calculated routes for my team, and my opponent's team at each turn and fed them in to the next step of my solution, which is determining the most optimal tile to bid on.

When determining a tile to bid on I focused on the shortest possibly route that I could make as well as taking into account my opponent's routes that I calculated previously. So that if I could bid on a tile that would be both beneficial to him and myself, I would bid on it over picking any other tile. I also made bidding on a tile that could potentially block my opponent's route be of higher priority, paying special attention to the second before last tile and trying to steal it to prevent him from completing his most optimal route.

By extension how useful a tile was to my opponent and myself determined how much gold I was willing to bid. Which brings us to the last part of my solution, calculating the least amount of gold required to bid at each turn of the game.

I used the same tile determination model from the previous step and calculated it for my opponent's team, this gave me an upper bound of gold that I would use as a limit when placing a bid for a tile. In a sense I made an assumption that my model would provide the optimal tile to bid on for either team and used that information to adjust the maximum amount of gold I should bid for a tile at each turn.

In addition, I also performed a standard deviation calculation of my opponent's previous bids to see if his bidding strategy was consistent, this information allowed me to literally one up his previous bid in the next turn's bid amount for those tiles that were not of high priority.

Keeping my bids as low as possible is what allowed me come up ahead in the later stages of the game where most routes where established and only a few tiles remained on the board for the taking.

https://github.com/mdzw/criss-cross

Very interesting!

I knew mdz had some element of future prediction for determining bid amount, and I suspected he was keeping that one extra piece of gold for tie-breaks!

In order to win consistently against his solution I would have to introduce my own future prediction to the bid calculation, and I'm glad that my current solution has an element of randomness to it when deciding how much to bid on the initial tile based on the bidding of my opponent in the previous round; the intent was to confuse any pattern analysis of my bidding strategy.

Interesting, indeed!

It sounds like we have similar strategies for ranking tiles (my paths vs opponent's paths). I like that your bid calculation seems more closely tied to the value of the tile -- there are only a few specific instances where I change my bid based on its value to me or the opponent, and I feel like I miss a few opportunities that way.

Congratulations on the win Matt! It was a great competition.