Google AI Challenge 2010

The PlanetWars contest! Many languages were supported, the only requirement being simple ascii-based communication via stdin/stdout. This provided an enticingly low barrier of entry for what turns out to be a remarkably deep game. I briefly considered using the contest as an excuse to finally learn Haskell, but given the limited time and a desire to be marginally competitive I shelved that idea in favor of trusty C++.

In the end it looks like there were over 4600 entries! I’m happy to say that my bot Neverstu placed well at rank 29, far above my initial goals. You can see all of its games in the finals here. What follows is a description of the more interesting parts of my algorithm.

Debugging

The provided starter materials included some sample maps and bots that could be immediately used for testing. After eagerly unzipping the package I ran a few matches against those bots with the starter code. I threw together some simple file logging and set out to experiment with strategies.

As it turns out, text-based debugging for this problem is prohibitively difficult. 200 turns, 20+ planets, and loads of spatial analysis are not well-represented in text form. Surely something else would be needed. Luckily (so I thought), the starter materials also included a graphical visualizer. It had a number of deficiencies and a level of functionality far below that of even the Javascript-based visualizer on the contest website. I needed a way to get a high-level view of my bot’s logic, so the only natural conclusion was to write my own visualizer. This will likely be the topic of a future post – it was a lifesaver!

Test Arena

Shouts to dhartmei and McLeopold are deserved for providing the debug server environments. This became critical in the last weeks of the contest, as the official rankings became wildly unstable due to the frequent uploads and slow due to the handling of games for all 4000+ contestants. Testing against the starter kit was inadequate quickly, and testing against old versions of my bot provided very little real information. It was quite possible to make a change to my bot that caused it to be less successful against old versions, but significantly more successful against other competitors. The wide variety of maps and possible strategies necessitate pairings against actual opponents.

Game State

Upon receiving the turn information from the game engine, I predict the arrival of all fleets, resolve battles and create a list of future states. This is then used to generate a set of predicted planet takeovers, which are later transformed into resource requests. Future planet state is straightforward to reason with, and usually takes the place of explicit analysis of individual in-flight fleets.

Map Awareness

My initial observation was that the likelihood of a successful attack or defense was related to the proximity of a given planet to its neighbors. At a course level I deemed this the latency of a planet, given by:

latency = nearest_friendly - nearest_enemy;

When ( latency < 0 ) the planet is perfectly defendable: if by luck I have enough ships at the nearest friendly planet, I can defend any attack since I at least have a 1-turn response buffer. (Keeping this balance of ships is an entirely different problem!) Similarly when ( latency >= 0 ) I must assume the enemy will respond to any offensive attack I make.

Extrapolating the planet proximity issue, I noticed that many maps contained groups of closely-placed planets, such that an attack on any one often involved its immediate neighbors. For a while I had hopes that a clustering analysis of the board could provide some insight, however that did not pan out. All that seems to do is transform the issue of planet proximity to one of cluster proximity, with no advantage gained because of it. The new line-symmetric map generator cast the final nail in the coffin for this idea, as too many clusters could straddle the symmetry line.

Eventually I did implement a simple and remarkably effective metric to guide the expansion/control of the board. For each pair of planets, take the line segment between the two and find the perpendicular vectors to this segment from all other planets. Take the inverse length of each of these perpendicular vectors, sum per planet, and then normalize. This gives a very rough idea of positional relevance. Planets with a high score are more valuable because they are more “on-the-way” to or from other planets, making them likely candidates for supply hubs. This analysis is done on the first turn of the game only.

Evaluating Potential Moves

It was immediately obvious that move scoring would play a critical role in any successful strategy. Less obvious were the combination of parameters that would lead to good evaluation. After a lot of fairly time-consuming experimentation I settled on a very basic ratio of value/cost as shown below. An AttackPlan encapsulates a set of allocations from any number of source planets to attack a single target planet.

void EvaluateResourceRequest( const GameState& g, const MapAnalysis& map, const AttackPlan& plan, ResourceRequestEvaluation& eval )
{
	const Planet& pl = g.Current().GetPlanet( plan.target );

	eval.value = pl.GrowthRate() * map.planets[ plan.target ].relevance_score;
	eval.cost = PlanInvestmentInTurns( g, plan );

	if( plan.request.type != A_Growth )
	{
		eval.value *= 2.0f;
	}
}

int PlanInvestmentInTurns( const GameState& g, const AttackPlan& plan )
{
	const Planet& pl = g.Current().GetPlanet( plan.target );
	const int num_ships = CountPlanShips( plan );
	const int dist = plan.arrival - g.Current().Turn();

	return dist + (int)ceil( (float)num_ships/(float)Max( pl.GrowthRate(), 1 ) );
}

No real surprises here. As introduced above, the planet’s relevance_score is a value between 1.0f (the edge of the map, between no other planets) and 2.0f (centrally located between many pairs of planets). This means for example I would rather take a positionally-important 3-growth planet than an out-of-the-way 5-growth planet. This is actually the source of some losses if a match degrades to a growth contest; I may skip a higher-growth planet during my initial expansion. The possible values for plan.request.type are:

enum AttackType
{
	A_Defense,
	A_Offense,
	A_Growth,
};

Growth is de-prioritized, which should be obvious when one considers that planets which switch owners have double the impact on growth rate balance as neutral planets do.

Plan Packing

There was a fair amount of discussion on the contest forums about the binary knapsack problem. While the discussion was limited to its use in the first turn of the game, this did not seem like a promising direction to me. This is at least a continuous quadratic knapsack problem since you must consider the opportunity cost of travel time from the various source planets in arbitrary divisions, asynchronously-available resources, and balance of board positioning of all planets related to a given attack. Yeesh.

So instead of going down that path I implemented a simple iterative greedy plan fulfillment algorithm. What is somewhat novel is that it behaves well on all turns of the game, and can deal with ship allocations across many turns.

As shown above, in order to properly evaluate a plan I must know two things: its value (profit) and its cost. Value is straightforward and available immediately. Cost is not so straightforward; this is not known until after formulating a plan for the move, since this will tell me the travel time, and the number of ships needed on the turn I finally arrive.

First I compute a naive evaluation of plans to all possible targets (whether offense, defense or growth – this is handled uniformly) without any consideration of other moves. Assuming that each of these plans is greedy with its resource requests, this will yield a (roughly) minimum cost for each one. Then I iteratively select the lowest cost/highest value plan and recompute its resource requests from scratch. We will often find that a prior plan fulfillment has taken some resources, and this new plan may now be more expensive. If it continues to be the best bet, permanently allocate it. If not, put it back and try another.

void GeneratePlansFromRequests( const GameState& g, const MapAnalysis& map, const ResourceRequestList& requests, AttackPlanList& new_plans )
{
	Assert( new_plans.empty() );
	std::priority_queue< ResourceRequestEvaluation > plan_evaluation;

	for( ResourceRequestList::const_iterator i=requests.begin(); i!=requests.end(); ++i )
	{
		const ResourceRequest& r = *i;

		MapResourceAvailability resources;
		CalculateResourceAvailability( g, map, new_plans, resources );

		AttackPlan p = GenerateNewPlan( g, map, r, resources );
		if( !p.sources.empty() )
		{
			ResourceRequestEvaluation eval;
			eval.request = r;
			EvaluateResourceRequest( g, map, p, eval );
			plan_evaluation.push( eval );
		}
	}

	while( !plan_evaluation.empty() )
	{
		ResourceRequestEvaluation eval = plan_evaluation.top();
		plan_evaluation.pop();

		MapResourceAvailability resources;
		CalculateResourceAvailability( g, map, new_plans, resources );

		AttackPlan p = GenerateNewPlan( g, map, eval.request, resources );
		if( !p.sources.empty() )
		{
			EvaluateResourceRequest( g, map, p, eval );

			if( eval < plan_evaluation.top() )
			{
				// try again later
				plan_evaluation.push( eval );
			}
			else
			{
				// this is the lowest cost with the latest allocations. make this permanent!
				new_plans.push_back( p );
			}
		}
	}
}

(To be nit-picky it is not strictly true that plan cost will monotonically increase as we add more resource commitments. However it is very often the case, and is a reasonable simplification to avoid exhaustively searching all possible configurations)

It may be more clear to look at a set of allocations for a single planet. Here we have a 5-growth planet that may receive 3 reinforcements per turn starting at Turn 5. “Reinforcements” in this case represents the possible inflow/outflow of resources for the planet, which will usually also contain potential attackers. In my code a more complete version is handled in GetSpeculativeAttackersAndReinforcements().


Looking from the current turn out to a reasonable horizon gives a minimum number of ships available for attack plans while still keeping control of the source planet. During the first iteration of plan fulfillment, we may decide to schedule an allocation of 20 ships on Turn 3.


This will affect the resource availability from Turn 3 onwards. On the second iteration of plan fulfillment we may decide to schedule an additional allocation of 29 ships on Turn 7.


In practice, future allocations are rarely used, and instead scheduling is mainly performed at the current turn. In the code, GetAvailableSources() will attempt to schedule either an immediate departure if possible or instead a departure that synchronizes many attacker fleets to a single arrival turn.

Finer granularity of ship departures is possible but I found it created a bit of ineffective “scattering” in my bot, as too many plans were started but then not carried out. This can be solved by keeping the future allocations persistent across turn updates (rather than being discarded and recomputed with updated game state knowledge), however this is not ideal because it gives up the advantage of deferred allocations in the first place, which is allowing for last-minute responses or adjustments.

One fascinating difference between this and the winning bot is that while our scheduling algorithms are quite similar (most competitive bots appeared to arrive at similar systems), all his departures are intentionally delayed by one or two turns. This idea seems so counter-productive that it did not occur to me to actually test this type of permutation. Lesson learned!

Center Planets

Handling the center planets is critically important. It is usually best to allow the enemy to take a center planet first, then snipe it at a low cost. However this is not the case in certain maps, or with low-cost center planets. My handling of this situation is quite simple; if a neutral planet is either equidistant from the enemy or closer to the enemy, I treat it as an enemy planet and assume that I will need to overwhelm the possible reinforcements it may receive. You can see the calculation of necessary ships in AdjustPlanSources(). While not completely accurate, I found it to work well. Some attempts to make this calculation more accurate actually resulted in “paralysis” as my bot became too scared to take any risks.

Supply Lines

After watching a few crushing losses it became clear that a method of getting ships from remote planets to those more at the “front line” was needed. As noted above, even playing perfect defense (the most obvious thing to do at first) requires snappy resource availability. My first idea was to use a simple minimum spanning tree to mark the distribution lines, then use those lines whenever I had spare ships. This turns out to be wholly ineffective. While it’s true that an MST gives a shortest overall distance to all nodes, it is not true that I actually want to visit all the nodes!

In the end I settled on a more ad-hoc geometric solution. For each planet that has extra ships at the end of a turn, compute the “direction” of threats. This is given by the sum of the vectors to all enemy planets weighted by number of ships and inverse distance. Then look in a 90-degree cone in that direction. Take all the planets I own in that cone and within the radius to the nearest enemy planet, and distribute everything to the single “best” planet as defined by relevance and inverse distance.

This is done in GenerateSupplyPlan(). An important detail is that the determination of supply-able planets is done by first extrapolating my current orders. I assume that all my attacks are successful and distribute accordingly. While occasionally wrong on account of being too optimistic, this actually very often helps resolve conflicts in my favor when I arrive with many extra ships on the attack turn.

Source

You can get the full source here. The PlanetWars.cc/h are mostly unmodified from the starter kit, with the exception of the turn advancement algorithm. Additionally I integrated the Configurable Math Library so I could work naturally with vector classes, though most of that library’s power is not utilized here.

This entry was posted in C++. Bookmark the permalink.

Comments are closed.