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.

Community

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:

• JBotManager - recording and viewing games, client for TCP server, allows you not to deal with the command line and will be useful at the very beginning
• GUI front-end card generator
• visualizers, which are no longer counted:
  • PlanetWars pastebin allows you to download the PlayGame.jar output and view it online.
  • engine with a visualizer rewritten in C ++ - just works faster
  • another one made on Qt - displays the numbers of the planets and their increments
  • and the last one based on HTML5 - converts the engine output to the format of the official Javascript player, works from the command line
• convenient crutch for debugging - converts the engine output into a dataset that the bot received during the game. By submitting this data to the bot's input, you can run it without the engine in debug mode. It works, of course, only for bots with unambiguous behavior
• multi-threaded python script to test bots

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?
')

Simulation

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 ;
else
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 ;
}

Logging

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 ;
else
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:

• interception attacks on a neutral planet. The idea is to send the fleet at such a moment so that it can reach the next turn after the conquest of the planet by the opponent. In this case, you get it at the lowest possible price;
• protect your own planets. This is where the simulation comes in handy. Having calculated on which turn your planet will be captured and what the total number of ships will be, you will only need to send an overlapping number from the nearest planets for protection;
• rushing of controversial planets. When both bots are smart enough to protect their planets and attack profitable aliens, there are points for which there is a struggle, and fleets sent to them by opponents are balanced. For such cases, you need to be able to calculate the limit of the "wave" that your opponent will be able to reflect and, of course, give him a little more;
• transfer of fleets from distant planets. This solves the problem of large maps, when the front of action goes beyond the radius, according to which you choose sources to send fleets, and the planets remaining behind him simply increase their power, but do not send it anywhere. The simplest way is to count how many fleets are sent from each of the planets and send from those planets where this number is zero to where it is more, taking into account the distance.

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.)

Conclusion

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.