Dec 4, 2010

Two bots for Planet Wars AI Challenge 2010

Table of Contents

1. Introduction
2. Java bot
3. C++ bot
4. Further reading

1. Introduction

This is a short source walk-through of my 2 bots for Google AI Challenge 2010 (a.k.a. Planet Wars). First bot is written in Java and was ranked 350 in the finals. Second one is in C++, uses different algorithm, and was hovering around rank 700 when I removed it. It didn't participate in the finals, since several submissions per contestant were forbidden.

The code is available here: Java, C++. Coarse-grained explanation follows:

2. Java bot

This is a simple heuristics-based bot, taking 50-100ms per turn, i.e. not spending an entire time available per turn. A code walk-through of important features follows:

  • Entry point is bot.TestingBot. When run, it takes two optional parameters, timeout in msecs, and a verbosity flag:

    >java -cp bin bot.TestingBot 1000 true

  • Usual classes shared.Planet, shared.Fleet, albeit starter package classes were not used.

  • Utility classes continuous.Adjacency (holding static state as planets' adjacency lists), continuous.Dijkstra and continuous.Knapsack - more on these later.

  • Class shared.FutureOrder, representing an order to be sent from an allied planet at some point in future. Every FutureOrder has an unique ID, and stored in two Planet objects - source and destination.

    In case a source planet can't send a future order, the order is removed from the list and a corresponding arriving order is removed from the list of the destination planet too.

  • Class simulate.Simulator is capable of simulating of a given planet's future (yes, it simulates a single planet only), based on currently known game state. Two important features are:

    • When simulated, FutureOrders of a planet are taken into account.

    • Since some FutureOrders could fail, because they were created some time ago, and game state has changed since, the simulator has a failTolerant mode, in which failing FutureOrders are removed. As this can in turn invalidate other FutureOrders, the method is applied in a loop, see TestingBot.cleanupInvalidFutureOrders().

    The Simulator uses pre-defined constant number of turns to look ahead.

  • Simulator uses listeners mechanism to react when various events are triggered, for example:

    • simulate.EndTurnListener.endTurn() is called at the end of every simulation turn, allowing it to record planet's state at that turn if needed.

    • simulate.OwerChangeListener and its subclasses are called when owner of a planet is changed, allowing to define a convenient attack time.

    • simulate.MinShipsListener is used to track amount of ships which can safely depart from a planet (considering only the current game state).

  • A bunch of SimulatorBot.Algorithms, used for main bot's logic, and allowing to change the overall strategy easily:

    • bot.algorithms.FastExpand - handles 1st turn by using knapsack packing (continuous.Knapsack class) to define best planets to safely expand to.

    • bot.algorithms.SneakAttack - also known as "sniping", handles both defence against sniping and sniping attacks.

    • bot.algorithms.Reacquire - handles cases when our planet is lost and we can't "snipe" it back right away - but reacquiring can happen later.

    • bot.algorithms.Expand - expansion logic, takes arbitrary list of planets to expand as input (neutrals or enemy or mixed).

    • bot.algorithms.WaitingAttack - helper algorithm, able to construct an attack from several planets in future. This is required to counteract back planets sending all their available ships as reinforcements to the front and never capturing nearby neutrals/enemies.

    • bot.algorithms.Reinforce - used for moving ships from back to the front, using modified Dijkstra algorithm (class continuous.Dijkstra). It simply gives preference to paths with minimal maximum segment length (not necessarily a shortest path). The idea here was to create a pipeline, so that planets along the reinforcing path don't stay naked for too long.

  • A bunch of scoring functions, used to sort planets' lists by some criteria, for example:

    • compare.SimpleCloseness - gives bigger score if a target planet is closer to the specified list of planets.

    • compare.GrowthFieldCloseness - taking each planet's growth rate as an electical charge, calculates score as electrical field.

    • etc, all this is designed to be easily interchangeable, as they all implement compare.IScore<Planet> interface.

    • Utility class utils.Visualiser used to visually represent various scoring functions for debugging. Here are some cool pictures of it in action:

      Figure 2. A couple of scoring methods visualized


Now, the main bot's logic is simple (see bot.TestingBot::doTurn()):

  • 1st turn - just use FastExpand algorithm.

  • Send any future orders scheduled for the turn, and cleanup future orders which became invalid because of enemy actions.

  • Do sniping and defend from sniping where possible. Starting from this point, any stage except the last one can generate future orders.

  • Try to reacquire planets lost to enemy which we weren't able to defend without losing.

  • Expand to neutrals.

  • Expand to enemies.

  • Send reinforcements to the front line.

Note, the bot doesn't consider enemy moves except for known from the game state ones. Also it doesn't do any searching of its own possible moves, just generates one, giving preferences to actions in a hard-coded way above.

At each stage, composition of target planet lists, scoring, and lists' cut-off logic is governed by some mixture of constant parameters, like minimum radius of attack, maximum turns to wait, safety thresholds and so on.

At earlier stages of the contest, this was enough to be ranked around 50. At later stages - not so much.

3. C++ bot

This bot uses somewhat different approach - something along the lines of 2-ply minimax algorithm. It tries to fully utilize allowed time (1 second) per turn, and is capable of beating all versions of the Java bot 90% of the time. Entry point is MyBot::do_turn(). The bot takes an optional command line parameter - name of a config file (default config is 'default.cfg').

Main features are:

  • Simulator class - similar to the first bot, but simulates states of all planets at once. Provides information on:

    • planet states at each turn,

    • available ships for enemy and allied planets for each turn. "Available" means the ships one can safely send at a given turn without losing a planet, based on current game state + possible moves known at the simulation's start,

    • "safely available" ships (same as available ships, but taking into account possible not-yet-known attack from the enemy in some region around the target).

    Also, a planet can be marked as an "evacuation" planet, meaning that all ships are marked as safe to depart, even if we lose the planet as a result. A planet is marked for evacuation if we see that we can't hold it anyway. It doesn't necessarily mean that the ships will depart - only when they are needed somewhere else.

  • FutureOrder - represents an order to be sent at turn 0 (current turn) or later in the future. Can belong to enemy or ally.

    Same safety measures are required for the Simulator here - see Simulator::simulate_safe().

  • Move class - holds a vector of future orders. Moves can be combined together and can consist of both enemy's and ally's orders.

    An important feature of the Simulator here is that it allows the simulation to start not from the clean game state, but from game state + some Move.

  • The bot uses same knapsack packing approach for the first move (fastexpand.cpp).

  • It also has several sorting functions (file sortfuncs.h), similar to the ones used in Java bot.

  • It uses only two kinds of attack - exact_attack(), when ships arrive exactly when specified and waiting_attack(), when ships are allowed to arrive at a specified turn or at some point in time in future.

  • Reinforcing to the front line is performed directly, basically from the furthest to enemy planets to the nearest ones.

Now, to what is different from the Java bot. In summary, this bot works like this:

  • Prepare a set of possible Moves for player 1 (ally).

  • For each Move of player 1, prepare a set of possible moves for player 2 (enemy). Note, that the enemy here is supposedly knows everything about our prospective move, including all future orders.

  • Now create the table, where each row corresponds to a single ally move, and each cell in the row - to some enemy move in the context of this row's move.

  • Using the simulator, calculate projected difference of ships at turn 200. Here combined allied and enemy Moves for the cell are used as a starting point for the simulation.

  • When the table is filled, pick up the best ally move (row) using maximin. I.e. we pick up the best turn in a rather pessimistic assumption that the enemy will inflict maximum possible damage to us, knowing all our plans beforehand.

The exact logic of targets selection at steps 1 and 2 above is very similar to the Java bot - there are only 3 possible target types - sniping attack, sniping defence, and expand. All this information is provided by the simulator. But now we have a freedom to play around with various sorting/cutoff modes, and generate a number of possible Moves for each player.

Also, there are two hard-coded things for allied moves selection:

  • Since at every turn we probably have some future orders from the previous turn, which are stored in the single Move object, we obviously use it as a starting point of simulation when selecting targets.

    But, to make up for the fact that situation could have changed because of unexpected enemy behavior, I gradually reduce this Move object to generate several starting states. Finally, starting state with all future orders completely discarded is considered.

    Having said that, defence against sniping is still enforced for every starting move generated, because the idea is that sniping defence is always good.

  • Second hard-coded feature is sending ships to reinforce the front line. For every allied move generated, I create a second variant of the same move, with ships reinforcement orders created in the end.

This bot turned out to be pretty good against my own Java bot, probably because, being based on same principles, it managed to predict the Java bot's actions very well. However, as it performed worse that the Java bot on official server and on dhartmei's TCP server, I've decided against it for the finals.

4. Further reading

Labels: , , ,

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)