My "Diamond tier" bot submission for https://2016.halite.io, @twosigma's artificial intelligence programming challenge
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
argh @ a2c412c
eigen @ ae9889a
iheap @ 941a8a5
src
tinyformat @ 3a33bbf
.gitignore
.gitmodules
LICENSE
Makefile
README.md

README.md

Overview

The main strategy of this bot consists of two steps:

  1. Assess the "exterior" (outside region currently not under control), and determine the relative appeal of each neighborhood. This results in a score for each "outskirt" site (site right outside of the border).
  2. Move units in the "interior" outwards, proportionally to the outskirt score.

In addition, the bot also adopts certain tactics (often with greedy heuristics) to obstruct suicidal moves, to maximize "overkill" output, to minimize overkill damage by other players, and to reduce the strength-255 overflow.

Assessing the exterior

The exterior assessment is performed by the function evaluate_outskirt in src/hlt.cpp.

The basic idea is to partition the whole exterior region into separate parts, one connected to each outskirt site. If we can come up with a reward function for individual exterior sites, the partition then makes it possible to assign a score to each outskirt site by summing the reward function over its share of the exterior.

To partition the exterior, think of the lattice of sites as a graph, with the weight of each vertex (site) given by its strength. The "strength distance" defined by these weights measures the total effort it takes to conquer one site starting from another. If we now introduce a fictitious node "interior" and connect it to all outskirt sites, then for any exterior site, the minimum distance path connecting it to "interior" gives in a sense the optimal route to conquer it. Crucially, if we further disconnect edges that link one outskirt site to another, the minimum distance path connecting "interior" to any exterior site always passes through a single outskirt site. These geodesic paths then define a partition of the exterior based on the (strength distance) proximity to the outskirt sites.

The geodesic paths to all n exterior sites can be found in O(n log n) time in a single Dijkstra pass starting from the fictitious "interior" node, regardless of the number of the outskirt sites. The Dijkstra implementation here (evaluate_outskirt_distance in src/hlt.cpp) uses an indexed binary heap.

With the exterior partition and the strength distances, the neighborhood assessment is reduced to assigning a score to each exterior site based on its production, strength, BFS distance, "strength distance", and perhaps some other features, and summing these scores over the Dijkstra tree. (The design of this score function is where I wish I had spent more time...)

Moving units in the interior

The bot needs to push units outwards, and preferably to push more units towards the outskirt sites with a higher score. To translate the scores on the outskirt to movements in the interior, we consider the following physics analogy.

At each interior site, place a positive charge proportional to its strength, and at each outskirt site, place a negative charge proportional to its score. With proper charge normalization (to ensure overall neutrality), the electric field lines of this setup strongly resembles the ideal pattern of unit movements.

Notice that Maxwell's equation dictates that the total flux emanating from each interior site sums up to the site strength, and the total flux absorbed by each outskirt site sums to its score. This is in parallel to the conservation of total strength during unit movements, and it guarantees that each outskirt site has a basin of attraction with total strength proportional to its score.

Under this analogy, minimizing production spoilage when moving units around corresponds to having a vorticity-free electric field, which can be expressed as the gradient of a potential function - ∇ϕ. We now just have to solve a 2D discrete Poisson equation ∇²ϕ = -ρ over the domain consisting of the interior and the outskirt sites, with Neumann no-flow boundary condition ∂_n ϕ = 0. The local electric field - ∇ϕ then gives the ideal direction to move each unit.

The Poisson linear system is constructed and solved in the function solve_poisson in src/hlt.cpp (see also evaluate_interior). Note that the Laplacian ∇² has a zero mode, and thus the corresponding matrix is not positive definite. Physically this originates from the fact that the Neumann boundary condition does not specify a reference point for the potential ϕ. To fix this, we pick an "anchor" point in each connected component of the Poisson domain and pin its ϕ value to zero, as done here.