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.
 
[email protected]
 
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};

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.