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};

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.