Halite Home

So you've Improved the Random Bot. Now what?


#1

Prefer Python? See Alternative Halite Starter Package for Python3 for these same bots written in Python instead of JavaScript.

How to Win...

  1. Download a starter package
  2. Read and follow Improving the Random Bot
  3. ???
  4. Defeat djma

If you're currently in step 3, this post is for you!

Reduce Waste

Waste is unnecessary moves that don't improve your position and prevent you from maximizing your production each turn.

Some ways to reduce waste:

  1. don't attack cells you can't defeat
  2. don't move cells unless you have a use for them
  3. don't move cells further than you have to
  4. be careful of constantly moving cells over your high production areas
    or cells swapping repeatedly

Stay still when you can't defeat a cell

The Improved Bot took care of some waste over RandomBot by adding a rule about attacking a cell with more strength than you, but it doesn't cover every situation.

If a cell is on the border, let's have it wait until it can attack successfully.

function move(loc) {
    const site = gameMap.getSite(loc);
    let border = false;

    for (let d of CARDINALS) {
        const neighborSite = gameMap.getSite(loc, d);
        if (neighborSite.owner != id) {
            border = true;
            if (neighborSite.strength < site.strength) {
                return new Move(loc, d);
            }
        }
    }

    if (site.strength < (site.production * 5)) {
        return new Move(loc, STILL);
    }

    // if the cell isn't on the border
    if (!border) {
        return new Move(loc, Math.random() > 0.5 ? NORTH : WEST);
    }

    // otherwise wait until you can attack
    return new Move(loc, STILL);
}

Watch ImproveBot vs PatientBot

You can see that PatientBot, by staying still, is able to grow faster and defeat ImproveBot.

Move towards the border

Right now both Patient Bot and Improve Bot move in a northwesterly direction. In most games this means that a lot of production and time is wasted moving from the southeast to the northwest.

Instead of moving randomly, let's move towards the nearest border.

function findNearestEnemyDirection(loc) {
    let direction = NORTH;
    // don't get stuck in an infinite loop
    let maxDistance = Math.min(gameMap.width, gameMap.height) / 2;

    for (let d of CARDINALS) {
        let distance = 0;
        let current = loc;
        let site = gameMap.getSite(current, d);
        while (site.owner == id && distance < maxDistance) {
            distance++;
            current = gameMap.getLocation(current, d);
            site = gameMap.getSite(current);
        }

        if (distance < maxDistance) {
            direction = d;
            maxDistance = distance;
        }
    }

    return direction;
}

function move(loc) {
    const site = gameMap.getSite(loc);
    let border = false;

    for (let d of CARDINALS) {
        const neighborSite = gameMap.getSite(loc, d);
        if (neighborSite.owner != id) {
            border = true;
            if (neighborSite.strength < site.strength) {
                return new Move(loc, d);
            }
        }
    }

    if (site.strength < (site.production * 5)) {
        return new Move(loc, STILL);
    }

    // if the cell isn't on the border
    if (!border) {
        return new Move(loc, findNearestEnemyDirection(loc));
    }

    // otherwise wait until you can attack
    return new Move(loc, STILL);
}

Watch AmbiturnerBot vs PatientBot

AmbiturnerBot has higher production and territory just by moving in all directions. Derek Zoolander would be jealous.

Increase Growth Rate

Optimizing your growth rate is a great way to improve your standing in the rankings. Early, mid, and late game growth are crucial to defeating strong bots.

Early game growth

Early game growth is all about effectively using your resources to capture nearby valuable areas of the map. But what does valuable mean? The visualizer does a good job helping you identify metrics that may be valuable, namely territory, production, and strength.

The AmbiturnerBot optimizes for territory, usually capturing the lowest cost enemy cell it can. This is good because territory is how you win games but raw territory doesn't necessarily help much in the early game. Instead you probably want to optimize for production. Good early game production will fuel your bot through the rest of the game.

// I've taken a dependency on lodash https://lodash.com
function move(loc) {
    const site = gameMap.getSite(loc);

    const target = _.chain(CARDINALS)
        .map((direction) => ({
            direction,
            site: gameMap.getSite(loc, direction)
        }))
        // only enemy cells
        .filter((cell) => cell.site.owner !== id)
        // sort by production descending
        .orderBy([(cell) => cell.site.production], ['desc'])
        .first()
        .value();

    if (target && target.site.strength < site.strength) {
        return new Move(loc, target.direction);
    }

    if (site.strength < (site.production * 5)) {
        return new Move(loc, STILL);
    }

    // if the cell isn't on the border
    if (CARDINALS.every((d) => gameMap.getSite(loc, d).owner === id)) {
        return new Move(loc, findNearestEnemyDirection(loc));
    }

    // otherwise wait until you can attack
    return new Move(loc, STILL);
}

Watch AmbiturnerBot vs ProductionBot

But wait! ProductionBot lost! I thought you said production was good!?

Picking a heuristic

Production is good, but you can't focus on just production. AmbiturnerBot is winning because it uses a better heuristic.

How can we improve ProductionBot to start winning?

function heuristic(site) {
    return site.production / site.strength;
}

function move(loc) {
    const site = gameMap.getSite(loc);

    const target = _.chain(CARDINALS)
        .map((direction) => ({
            direction,
            site: gameMap.getSite(loc, direction)
        }))
        // only enemy cells
        .filter((cell) => cell.site.owner !== id)
        // sort by heuristic descending
        .orderBy([(cell) => heuristic(cell.site)], ['desc'])
        .first()
        .value();

    if (target && target.site.strength < site.strength) {
        return new Move(loc, target.direction);
    }

    if (site.strength < (site.production * 5)) {
        return new Move(loc, STILL);
    }

    // if the cell isn't on the border
    if (CARDINALS.every((d) => gameMap.getSite(loc, d).owner === id)) {
        return new Move(loc, findNearestEnemyDirection(loc));
    }

    // otherwise wait until you can attack
    return new Move(loc, STILL);
}

Watch AmbiturnerBot vs DiscerningBot

Well, DiscerningBot still lost, but it was leading in the beginning. Once it made contact with the enemy though, it looks like it just ran away!

We have a bug! When strength is 0 (like after enemies fight) our heuristic will make the value Infinity! Let's fix that.

function heuristic(site) {
    if (site.strength) {
        return site.production / site.strength;
    } else {
        return site.production;
    }
}

Watch AmbiturnerBot vs DiscerningBot - Round 2

Whoo! DiscerningBot has started winning!

Take Overkill Into Account

Combat is a huge part of Halite, and as we just saw, being bad at it can ruin an otherwise good bot.

One of the crucial things to know about combat is overkill:

each piece decreases the strength of every adjacent or coinciding opposing piece by its own strength

Let's update our heuristic to take overkill into account.

function heuristic(cell) {
    if (cell.site.owner === 0 && cell.site.strength > 0) {
        return cell.site.production / cell.site.strength;
    } else {
        // attacking an enemy
        let totalDamage = 0;
        for (let d of CARDINALS) {
            let site = gameMap.getSite(cell.loc, d);
            if (site.owner !== 0 && site.owner !== id) {
                totalDamage += site.strength;
            }
        }

        return totalDamage;
    }
}

function move(loc) {
    const site = gameMap.getSite(loc);

    const target = _.chain(CARDINALS)
        .map((direction) => ({
            direction,
            loc: gameMap.getLocation(loc, direction),
            site: gameMap.getSite(loc, direction)
        }))
        // only enemy cells
        .filter((cell) => cell.site.owner !== id)
        // sort by production descending
        .orderBy([(cell) => heuristic(cell)], ['desc'])
        .first()
        .value();

    if (target && target.site.strength < site.strength) {
        return new Move(loc, target.direction);
    }

    if (site.strength < (site.production * 5)) {
        return new Move(loc, STILL);
    }

    // if the cell isn't on the border
    if (CARDINALS.every((d) => gameMap.getSite(loc, d).owner === id)) {
        return new Move(loc, findNearestEnemyDirection(loc));
    }

    // otherwise wait until you can attack
    return new Move(loc, STILL);
}

Watch OverkillBot vs DiscerningBot

You'll notice that both bots behave almost identically until they start to fight, then OverkillBot takes DiscerningBot apart!

Next Steps

This is a pretty good start for our bot. More things to think about are:

Combining cells to attack sooner

Our bot spends a lot of time with cells at the border that are just waiting until they have enough strength to attack an enemy. What if we combined some of them together to attack sooner?

Moving inner cells to higher value border areas

Right now we move every cell to its nearest border, but what if the nearest border isn't particularly valuable? We should find ways to direct those resources towards valuable parts of the map.

Avoid combining cells together that exceed 255 strength

One additional detail about the 255 cap - the cap applies before combat occurs so if 2 200 strength cells attack one 220 strength cell in the same turn, the resulting cell will have 35 strength, not 180 strength.

Watch your bot and other bots compete

Look for inefficiencies in your playstyle. Look for ways to improve your heuristic. Take past and future moves into account.

Bonus: watch all 6 bots compete

May the best bot win!


Perimeter Optimization during Expansion
Tips for climbing the ladder - spoiler free
How your starting position impacts your bot's performance
Confused about the Production Bot from erdman's alt-python3 halite starter package
Java: How do you store more than 1 direction in a variable/location?
Neighbors of a Square
Game with bots doing the exact same thing
#2

An absolutely beautiful post.

One thing I'd like to add under the set of "Next Steps" would be having your bot ensure that strength is not lost to the 255 cap; I've noticed that OverkillBot loses a lot of strength (especially when routing pieces) to combining pieces whose strengths sum to over 255. Avoiding this could make a big difference.


#3

What language are you using here?


#4

JavaScript


#5

Hi,

Your links to matches are not working for me.


#6

same, I downloaded the games and ran them locally.
e.g. the 6 bot game link is
https://nmalaguti.github.io/halite-visualizer/?url=https%3A%2F%2Fdl.dropboxusercontent.com%2Fu%2F57961%2F131612-3893351690.hlt

so the link to the game is:
https%3A%2F%2Fdl.dropboxusercontent.com%2Fu%2F57961%2F131612-3893351690.hlt
which also won't work, but if you translate it, it will, e.g.
https://dl.dropboxusercontent.com/u/57961/131612-3893351690.hlt
%2F becomes / and %3A becomes :


#7

Should be fixed! Thanks for the heads up.


Welcome to Halite Forums
#8

that works for me now, thanks


Alternative Halite Starter Package for Python3
#9

There is one more thing I would like to add.
Yesterday I wrote a small script that executes x amount of games of my current bot against older bots and collects the results.
I wish I would have done this way earlier as I can get feedback in a very short amount of time if a change is better or even slightly better.
Especially small changes in heuristics may be seen after 50 / 100 or even 200 games.


#10

Sadly random luck plays a big role in such tests: suppose two equally matched bots play 100 games - there's a 13% chance of the result being 58-42 or worse.


#11

Thats true...for bigger improvements though, it is reasonable :slight_smile:


#20

#21

I can't get why we are using
totalDamage += site.strength
in calculating total damage for overkill bot? If I am correct and we want to maximize total damage for enemy should't we use something else instead of enemy strength here?


#22

OverkillBot is trying to maximize the damage it could do to the enemy. You always receive damage equal to the damage you do. When taking overkill into account, you can output more damage than you have strength, but that also means that your piece will receive more damage than it has strength. Because once you have zero strength you're dead no matter what, the extra damage done to you doesn't matter.

The heuristic for OverkillBot is simple and doesn't take into account the piece that will be doing the damage. If we kept track of that, we could more accurately estimate the real damage done by taking

totalDamage += Math.min(site.strength, mySite.strength)

Does that answer your question?


#23

Thanks, nmalaguti. Math.min(...) is what I've implemented based on your tutorial, so thanks for confirming it.


#24

I was reading through this again today and decided to look at some of the games in the original post with the new graphs that have since been added.

The thing that struck me was the Overkill graph. Actually, OverkillBot loses to DiscerningBot when it comes to Overkill. It must be winning for other reasons.

I have some theories as to why this might be the case (what makes the heuristic better) but I'm not really sure, so thought I'd re-open conversation on this topic. What's going on?


#25

Watching the replay, you can see how the big strength pieces of the two bots behave once combat begins. The reason that OverkillBot wins, even though it technically does less overkill damage, is that it is always seeking out and attacking the high strength enemy pieces. DiscerningBot is going after any unowned pieces it can capture, which is a worse strategy.

So while OverkillBot may or may not do more overkill damage in practice, it is trying to attack the enemy's strength - which is good enough.


#26

That makes sense, I believe that. I was thinking something along similar lines, but it was much more fuzzily articulated in my mind.


#27

This really was my goal when I first started. I remember how excited I was when my bot overtook djma. I would never have believed that so many people would pass him on the charts. Right now he is ranked 29. The quality of the bots is incredible.

Closing in on 10,000 games on v3, I'm still looking out for a djma v4 bot.