📜 ⬆️ ⬇️

Google AI Challenge two weeks later

As many already know , the Google AI Challenge recently started - a botting competition for the game Planet Wars, conducted by the University of Waterloo and supported by Google. Yesterday the second (of nine) week came to an end from the moment of the official start. The competition is increasingly beginning to resemble an arms race, and if at the beginning there was enough bot to get to the top 50, which in most cases just played with examples from the starting set, then now you will have to try. About how this can be done, as well as the news of the tournament under the cut.


The first weeks were marked by problems with the organizers: this is the server performance, and cases of dirty games, various starting sets and working environment conflicts with users, problems with sending code 12-13. But, to their credit, everything was resolved quickly enough. Well, or almost everything ... Until now, each bot plays on average about once per hour, which means that in order to understand how changes in the code affected the ranking, you have to wait a day or two (another server may be added next week). This problem is partially solved by an unofficial TCP server to which you can connect the bot directly from your computer. The frequency of games at the same time increases significantly and, as a plus, it is possible to save debug data. The main disadvantage is that the server does not have the majority of top bots, so the results make sense only for the time of testing or processing the code. And the latest news: during this time , long-awaited Lisp, Haskell, OCaml and CoffeeScript, as well as a little-known exotic, were added to the list of supported C ++, C #, Java and Python: PHP, Perl, Javascript and Ruby (or was it the other way around?).

Now a little about the utilities that were created by the participants. I’ll make a reservation that this is a Linux view and Windows-specific things are missing here. So:

About the development of bots

Next, I want to share the experience that I gained during the participation. He does not lay claim to the role of absolute truth; rather, it is food for thought. So what should be able to bot?


You need to know what will happen with any of the planets in a few moves, taking into account the gains and the flying ships. Without this, it is impossible to correctly estimate the cost of defense or attack. In a simplified form (without taking into account the rule of simultaneous attacks on a neutral planet), it might look like this:
public void simulate () {
// List <Fleet> fleets - fleets flying to the target planet
if ( fleets. size () == 0 )
return ;
sortFleets ( ) ;

// variables with the current calculated state
int owner = target. owner ;
int shipCount = target. shipCount ;
// stores the current move to accumulate results
int lastGrowth = 0 ;

for ( int i = 0 ; i < fleets. size ( ) ; i ++ ) {
// if the results of the move are counted - save the state
if ( lastGrowth < fleets. get ( i ) . turnsRemaining ) {
if ( i > 0 )
states. add ( new PlanetState ( shipCount, owner, lastGrowth ) ) ;
// increment only on players' planets
if ( target. owner > 0 )
shipCount + = target. growthRate *
( fleets. get ( i ) . turnsRemaining - lastGrowth ) ;
// this move will be calculated further
lastGrowth = fleets. get ( i ) . turnsRemaining ;
if ( owner ! = fleets. get ( i ) . owner )
shipCount - = fleets. get ( i ) . numShips ;
shipCount + = fleets. get ( i ) . numShips ;
// change owner
if ( shipCount < 0 ) {
shipCount * = - 1 ;
owner = fleets. get ( i ) . owner ;
if ( i == fleets. size ( ) - 1 )
states. add ( new PlanetState ( shipCount, owner, lastGrowth ) ) ;
By the way, the code with Cyrillic comments is not compiled on the server, so be careful before sending. After the state changes are calculated, it is quite simple to get a forecast for any move:
public PlanetState getInfoForTurn ( int turn ) {
int growth = target. growthRate ;
// cases when there were no incoming fleets and
// when the request goes to turn before the arrival of the first fleet
if ( states. size ( ) == 0 || states. get ( 0 ) . turn > turn ) {
// on neutral planets there is no increase
if ( target. owner == 0 )
growth = 0 ;
return new PlanetState ( target. shipCount + turn * growth,
target. owner , turn ) ;
int last = states. size ( ) - 1 ;
// move after the arrival of the last fleet
if ( turn > = states. get ( last ) . turn ) {
if ( states. get ( last ) . owner == 0 )
growth = 0 ;
return new PlanetState ( states. get ( last ) . shipCount +
( turn - states. get ( last ) . turn ) * growth,
states. get ( last ) . owner , turn ) ;
// move between the arrival of the first and last fleets
for ( int i = 1 ; i < = last ; i ++ )
if ( states. get ( i ) . turn > turn ) {
if ( states. get ( i - 1 ) . owner == 0 )
growth = 0 ;
return new PlanetState ( states. get ( i - 1 ) . shipCount +
( turn - states. get ( i - 1 ) . turn ) * growth,
states. get ( i - 1 ) . owner , turn ) ;
return null ;


First of all, this is one of the ways to get debug information and the “correct” log is more convenient to analyze than visualization in the player (although they are not mutually exclusive: there were links to patches on the official forum that allowed displaying debug information in the player). And secondly, the logs allow for batch checking of game results. In general, test automation saves a lot of time and nerves.

Switching game styles

Already hear the objections. In fact, you are right, and you can get along ... but the fact that the rules of the game have been adjusted by the rules (200 moves), the fact that it is easier to brute in the opening, as well as the differences in the size of the cards force you to change the style. For example:
if ( myPlanets. size ( ) < 4 )
mode = BotMode. bmStart ;
else if ( myPower > enemyPower * 3 && turn > 50 )
mode = BotMode. bmFinishHim ;
else if ( turn > 180 || myPower * 5 < enemyPower * 4 )
mode = BotMode. bmRegenerate ;
mode = BotMode. bmNormal ;

Evaluation functions

Whatever approach to the solution of the problem is used, it becomes necessary to choose more preferred options for action among those found. This concerns the choice of targets for an attack, the planets from which to conduct it, targets for moving the fleet (see below), etc. This is what the evaluation functions are needed for, which can be separated from other code. They certainly will be hardcoded parameters that during testing can be passed through the command line of the launch of the bot, so you can automatically run a lot of their combinations and choose the best.

Standard Techniques

In addition to, obviously, attacks, it is desirable to implement such standard techniques as:

Modification of the starter kit

It is desirable to rewrite the code provided by the organizers for parsing and performing the simplest operations with game objects. Judging by Java, the starter kit is really crooked. Given that the language and so is not the fastest, it is better to finish. By the way, for many languages ​​there are already modified starter kits where these problems are solved.

What next?

The above is more than enough (yet) for getting into the top 50. Next, original approaches and the use of the mathematical apparatus will come in handy. From the main areas in which you can develop a bot, I note:
  1. Story. Accounting for the results of past moves allows you to monitor flows, identify traffic concentration points and real growths according to the principle
    realGrowth = growthRate + (fleetsInMy - fleetsInEnemy - fleetsOut) / historySize
  2. Map analysis. In the simplest case, this problem is solved by introducing an estimate function, which takes into account the average and minimum distance to one's own and others' planets, the increments and the number of ships on them. In the case of more complicated problems arise of finding the optimal path and maximum flow in the graph.
  3. Analysis of possible moves. After selecting the targets, for each of them you can generate several sets of the most successful planets from which you can launch an attack. In addition, for each set there will be an assessment of the effectiveness and the number of ships that need to be sent to capture or protect (and this number can be redistributed between the planets). There is a problem of choosing such a set of moves, which when sending the available number of ships will bring maximum benefit. This is a slightly modified packaging task.
  4. Waiting There are bots that every move the entire increase from each of the planets is sent to the most priority areas. There is a feeling that they all "work", but is this true? Sent fleets are much easier to cheat on the opponent: they already have a goal, unlike those who are waiting. At the same time, it is possible to wait for such a goal, which you can certainly (well, or almost certainly) capture or, on the contrary, remain on the defensive. Therefore, it is important to understand that the attack in small portions is rather evil, because you still will not achieve the result until the total mass exceeds a certain level. So why not wait for the moment when this mass you have accumulated. And one more fact: the fleet sent until the goal is reached is out of the game, so it is important to consider distances so that there are no situations when an attack by superior forces reaches the goal by the time you are wiped into dust.
  5. Calculations between moves. According to the rules, the timeout for a turn is 1000 ms and bots cannot use threads. But it can be counted at the moments when, after completion of the move, the engine processes them. At these moments, you can work with history, calculate and cache values ​​that rarely change (for example, distances between planets, flows, priorities of neutral planets, etc.)


And about the "AI" in the title. It makes little sense to use neural networks or genetic algorithms to implement general logic of work (for this purpose, procedures or multi-agent systems are much better suited), but they can be used to solve distinguished path / flow search problems, recognize and evaluate targets, and also packaging tasks. The approaches associated with AI are currently not used by anyone, or they do not bring significant benefits, or so far the heuristic search for subsequent bruteforce still fits into timeouts and allows for victory. In any case, the next will be even more interesting. Let's see if the name will justify itself in a month or two. I hope only that after the publication the number of Russian-speaking participants will increase.

Source: https://habr.com/ru/post/104861/

All Articles