Michael Heasell's CodeCombat Greed Code

greed_human.js

// constants -------------------------------------------------------------------

var alliedTypes = {
    peasant: 'peasant',
    soldier: 'soldier',
    knight: 'knight',
    librarian: 'librarian',
    griffinRider: 'griffin-rider',
    captain: 'captain'
};

var enemyTypes = {
    peasant: 'peon',
    soldier: 'munchkin',
    knight: 'ogre',
    librarian: 'shaman',
    griffinRider: 'fangrider',
    captain: 'brawler'
};

if (this.buildables.peasant === undefined) {
    var tmp = alliedTypes;
    alliedTypes = enemyTypes;
    enemyTypes = tmp;
}

// generic utility functions ---------------------------------------------------

// Searches the given array for the element with the maximum value
// as determined by the given function, f.
function maxkey(f, arr) {
    var winner = null;
    var winScore = -10000;
    for (var i = 0; i < arr.length; ++i) {
        var elem = arr[i];
        var score = f(elem);
        if (score > winScore) {
            winner = elem;
            winScore = score;
        }
    }
    
    return winner;
}

// Filters the given array of entities to those of the given type
function filterType(type, arr) {
    return arr.filter(function(x) { return x.type === type; }, arr);
}

// Filters the given array of entities to those NOT of the type
function filterNotType(type, arr) {
    return arr.filter(function(x) { return x.type !== type; }, arr);
}

// returns the linear interpolation from the start number to the end number
// according to the given fraction, a number from 0 to 1
function lerp(start, end, frac) {
    return start + ((end - start) * frac);
}

function clamp(val, low, high) {
    return Math.max(Math.min(val, high), low);
}

// removes and returns the given element from the array
function remove(elem, arr) {
    return arr.splice(arr.indexOf(elem), 1)[0];
}

// removes and returns the element at the given index from the array
function removeIndex(i, arr) {
    return arr.splice(i, 1)[0];
}

// combat utilities ------------------------------------------------------------

// Returns the heuristic value of the given type of fighter.
function valueFighter(type) {
    switch (type) {
        case "munchkin":
        case "soldier":
            return 10;
        case "knight":
        case "ogre":
            return 25;
        case "librarian":
        case "shaman":
            return 40;
        case "griffin-rider":
        case "fangrider":
            return 60;
        case "captain":
        case "brawler":
            return 100;
        case 'base':
            return 0;
        case "peasant":
        case "peon":
            return 50;
    }
}

// Returns the heuristic total value of the given collection of fighters.
function valuateFighters(fighters) {
    var score = 0;
    for (var i = 0, len = fighters.length; i < len; i++) {
        score += valueFighter(fighters[i].type);
    }
    
    return score;
}

// coin gathering utilities ----------------------------------------------------

function computeMinDistances(peasants, coins) {
    var dict = {};

    for (var i = 0, len = coins.length; i < len; i++) {
        var coin = coins[i];
        var winScore = 10000;
        for (var j = 0, pLen = peasants.length; j < pLen; j++) {
            var dist = coin.pos.distance(peasants[j].pos);
            if (dist < winScore) {
                winScore = dist;
            }
        }

        dict[coin.id] = winScore;
    }

    return dict;
}

function computeEnemyMult(ourDistance, enemyDistance) {
    var enemyDistFrac = (ourDistance + enemyDistance) / enemyDistance;
    if (enemyDistFrac > 2.2222222222) {
        return 0.5;
    }

    return enemyDistFrac;
}

function computeAttractionSquared(itemPos, attractorPos, attractorMass) {
    var distance = itemPos.distance(attractorPos);
    var strength = attractorMass / (distance * distance);
    var direction = Vector.normalize(Vector.subtract(attractorPos, itemPos));
    return Vector.multiply(direction, strength);
}

function computeSpringAssignments(friends, enemies, coins, computeAttraction) {
    var WALL_ATTRACTION = -1;
    var FRIEND_ATTRACTION = -5;

    var DIRECTION_CASTAHEAD = 6;
    
    var ARENA_WIDTH = 85;
    var ARENA_HEIGHT = 70;
    
    var limits = computeMinDistances(enemies, coins);
    
    var assignments = [];
    
    for (var i = 0, fLen = friends.length; i < fLen; i++) {
        var friend = friends[i];
        var friendPos = friend.pos;
        
        var force = new Vector(0, 0);
        
        for (var j = 0, cLen = coins.length; j < cLen; j++) {
            var coin = coins[j];
            var coinPos = coin.pos;
            var dist = friendPos.distance(coinPos);
            var enemyDist = limits[coin.id];
            var strength = (coin.bountyGold * computeEnemyMult(dist, enemyDist)) / (dist * dist);
            var direction = Vector.normalize(Vector.subtract(coinPos, friendPos));
            force = Vector.add(force, Vector.multiply(direction, strength));
        }
        
        for (var k = 0; k < fLen; k++) {
            if (k === i) {
                continue;
            }
            
            force = Vector.add(force, computeAttraction(friendPos, friends[k].pos, FRIEND_ATTRACTION));
        }
        
        // wall influence
        force = Vector.add(force, computeAttraction(friendPos, new Vector(-0.1, friendPos.y), WALL_ATTRACTION)); // left
        force = Vector.add(force, computeAttraction(friendPos, new Vector(ARENA_WIDTH + 0.1, friendPos.y), WALL_ATTRACTION)); // right
        force = Vector.add(force, computeAttraction(friendPos, new Vector(friendPos.x, -0.1), WALL_ATTRACTION)); // bottom
        force = Vector.add(force, computeAttraction(friendPos, new Vector(friendPos.x, ARENA_HEIGHT + 0.1), WALL_ATTRACTION)); // top
        
        var newPos = Vector.add(friendPos, Vector.multiply(Vector.normalize(force), DIRECTION_CASTAHEAD));
        newPos = new Vector(
            Math.min(Math.max(newPos.x, 0.0), ARENA_WIDTH),
            Math.min(Math.max(newPos.y, 0.0), ARENA_HEIGHT));
        
        assignments.push({src: friend, target: newPos});
    }
    
    return assignments;
}

// coin gathering main ---------------------------------------------------------

var items = this.getItems();
var friends = this.getFriends();
var enemies = this.getEnemies();

var enemyBase = this.getByType('base')[0];
var enemyGold = enemyBase ? enemyBase.gold : 0;

var peasants = this.getByType(alliedTypes.peasant);
var peons = this.getByType(enemyTypes.peasant);

var assignments = computeSpringAssignments(peasants, peons, items, computeAttractionSquared);
for (var i = 0; i < assignments.length; i++) {
    var as = assignments[i];
    this.command(as.src, 'move', as.target);
}

// gold prediction utils -------------------------------------------------------

function createRegressionFunc(points) {
    var n = points.length;
    
    var sumX = points.reduce(function(a, b) { return a + b.x; }, 0);
    var sumY = points.reduce(function(a, b) { return a + b.y; }, 0);
    var meanX = sumX / n;
    var meanY = sumY / n;
    
    var sumXSquared = points.reduce(function(a, b) { return a + (b.x * b.x); }, 0);
    
    var sumXY = points.reduce(function(a, b) { return a + (b.x * b.y); }, 0);
    
    var slope = (sumXY - ((sumX * sumY) / n)) / (sumXSquared - ((sumX * sumX) / n));
    
    var intercept = meanY - (slope * meanX);
    
    return function(x) {
        return (slope * x) + intercept;
    };
}

function estimateVariance(points, regFunc) {
    var mseSum = points.reduce(function(a, b) { var ms = b.y - regFunc(b.x); return a + (ms * ms); }, 0);
    var mse = mseSum / (points.length - 2);
    return mse;
}

function estimateHighLow(points, time) {
    var regFunc = createRegressionFunc(points);
    
    var deviation = Math.sqrt(estimateVariance(points, regFunc));
    var bound = deviation * 2; // ~95% coverage
    
    var start = regFunc(points[0].x);
    var lowStart = start - bound;
    var highStart = start + bound;
    
    var end = regFunc(points[points.length - 1].x);
    var lowEnd = end - bound;
    var highEnd = end + bound;
    
    var upperBound = lerp(lowStart, highEnd, (time - points[0].x) / (points[points.length - 1].x - points[0].x));
    var lowerBound = lerp(highStart, lowEnd, (time - points[0].x) / (points[points.length - 1].x - points[0].x));
    
    var estimate = regFunc(time);
    
    
    return [upperBound, estimate, lowerBound];
}

// base building ---------------------------------------------------------------

var militaryFriends = filterNotType(alliedTypes.peasant, friends);
var friendlySoldiers = filterType(alliedTypes.soldier, friends);
var militaryEnemies = filterNotType('base', filterNotType(enemyTypes.peasant, enemies));
var nearestEnemy = this.getNearest(militaryEnemies);

// gold prediction main --------------------------------------------------------

if (this.enemyGoldHistory === undefined) {
    this.enemyGoldHistory = [];
}

if (this.counter === undefined) {
    this.counter = 0;
}

var PREDICTOR_HISTORY_LENGTH = 25;
var PREDICTOR_SAMPLE_INTERVAL = 4;
var PREDICTOR_LOOKAHEAD_TIME = 17;

var enemyTotalWorth = 0;
if (enemyBase) {
    enemyTotalWorth = valuateFighters(enemyBase.built) + enemyGold;
}

if (this.counter++ % PREDICTOR_SAMPLE_INTERVAL === 0) {
    this.enemyGoldHistory.push({x: this.now(), y: enemyTotalWorth});
}

if (this.enemyGoldHistory.length > PREDICTOR_HISTORY_LENGTH) {
    this.enemyGoldHistory.shift();
}

var ourMilitaryStrength = valuateFighters(militaryFriends);
var enemyMilitaryStrength = valuateFighters(militaryEnemies);

var ourStrength = ourMilitaryStrength + this.gold;
var enemyStrength = enemyMilitaryStrength + enemyGold;
var enemyStrengthForecast = null;

if (this.enemyGoldHistory.length >= PREDICTOR_HISTORY_LENGTH) {
    var highLowE = estimateHighLow(this.enemyGoldHistory, this.now() + PREDICTOR_LOOKAHEAD_TIME);
    var futureEnemyBonus = highLowE[0] - enemyTotalWorth;

    enemyStrengthForecast = enemyStrength + futureEnemyBonus;
}

// subsumption behaviours ------------------------------------------------------

var doNothingState = {
    name: "doNothing",
    
    wantsControl: function() {
        return true;
    },
        
    selectBuildType: function() {
        return null;
    }
};

var collectState = {
    name: "collect",
    
    wantsControl: function(base) {
        // always build the initial peasant
        if  (peasants.length < 1) {
            return true;
        }
        
        // build another if we're behind on the enemy
        if (enemyGold <= 70 && peasants.length < peons.length && peasants.length < 6) {
            return true;
        }
        
        // build another if we think there is enough free gold
        // to be worth it.
        var coinsPerPeasant = items.length / peasants.length;
        if (coinsPerPeasant >= 2) {
            return true;
        }
        
        return false;
    },
        
    selectBuildType: function(base) {
        return alliedTypes.peasant;
    }
};

var pokeState = {
    name: "poke",
    
    wantsControl: function(base) {
        return !base.poked;
    },
        
    selectBuildType: function(base) {
        if (base.gold >= 10) {
            base.poked = true;
            return alliedTypes.soldier;
        }
        
        return null;
    }
};

var stockpileState = {
    name: "stockpile",
    
    wantsControl: function(base) {
        var strengthRatio = (ourMilitaryStrength + base.gold) / enemyMilitaryStrength;
        
        if (strengthRatio <= 1.2) {
            return true;
        }
        
        return false;
    },
        
    selectBuildType: function(base) {
        return null;
    }
};

function decideMilitaryToBuild(base) {
    var soldierPercent = friendlySoldiers.length / militaryFriends.length;
    
    if (friendlySoldiers.length < 3 || soldierPercent <= 0.45) {
        return alliedTypes.soldier;
    }
    
    var friendlyLibs = filterType(alliedTypes.librarian, militaryFriends);
    var libPercent = friendlyLibs.length / militaryFriends.length;
    
    if (friendlyLibs.length < 2 || libPercent <= 0.33) {
        return alliedTypes.librarian;
    }
    
    var friendlyGrif = filterType(alliedTypes.griffinRider, militaryFriends);
    var grifPercent = friendlyGrif.length / militaryFriends.length;
    
    if (grifPercent < 0.125) {
        return alliedTypes.griffinRider;
    }
    
    var friendlyKnight = filterType(alliedTypes.knight, militaryFriends);
    var knightPercent = friendlyKnight.length / militaryFriends.length;
    if (knightPercent < 0.100) {
        return alliedTypes.knight;
    }
    
    return alliedTypes.soldier;
}

var attackState = {
    name: "attack",
    
    wantsControl: function(base) {
        // last ditch attack if the game is almost over
        if (base.now() >= 140) {
            return true;
        }
        
        // if we think that by the time our military gets there
        // we will still have an advantage, then attack
        var threshold = (base.currentState && base.currentState.name === "attack") ? 0 : 20;
        if (enemyStrengthForecast && ourStrength - enemyStrengthForecast >= threshold) {
            return true;
        }
        
        return false;
    },
        
    selectBuildType: decideMilitaryToBuild
};

var defendState = {
    name: "defend",
    
    wantsControl: function(base) {
        var nearEnemies = militaryEnemies.filter(function(x) { return base.distance(x) < 55; });
        
        var militaryRatio = ourMilitaryStrength / valuateFighters(nearEnemies);
        
        // if the enemy is near and we don't have enough defenders, build more
        if (nearestEnemy && base.distance(nearestEnemy) <= 40 && militaryRatio < 1.2) {
            return true;
        }
        
        return false;
    },
    
    selectBuildType: decideMilitaryToBuild
};

// subsumption main ------------------------------------------------------------

var states = [
    attackState,
    defendState,
    stockpileState,
    collectState,
    pokeState,
    doNothingState
];

this.updateState = function() {
    for (var i = 0, sLen = states.length; i < sLen; i++) {
        var st = states[i];
        if (st.wantsControl(this)) {
            this.currentState = st;
            break;
        }
    }
};

// base building main ----------------------------------------------------------

this.updateState();

var type = this.currentState.selectBuildType(this);

if (type && this.gold >= this.buildables[type].goldCost) {
    this.build(type);
}

//var n = this.now();
//if (this.lastRunTime !== undefined) {
//    this.say("Last run: " + (n - this.lastRunTime));
//}

//this.lastRunTime = n;

maxkey doesn't seem to get used at all... - any reason it got to stay in anyway?