[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4586: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4588: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4589: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4590: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
AI Challenge Forums • View topic - Complete overview of my script

It is currently Tue Sep 18, 2018 4:15 pm Advanced search

Complete overview of my script

Share and discuss ideas for your entries here.

Complete overview of my script

Postby Mistmanov » Mon Oct 04, 2010 7:57 pm

Here is my strategy for the main part of my current bot (link: http://ai-contest.com/profile.php?user_id=10032 ) It's in no way perfect (The most obvious major shortcoming is that it only looks at possibilities to attack from a single planet: it won't coordinate defense/offense by for example sending multiple fleets from multiple planets to a single planet so that they arrive at the same moment, but that's certainly not the only problem that I see with it..) but it still does ok (currently ranked 20th in the official ranking). Maybe it will be of help to someone else. =)

Super condensed overview of the bot:
-calculate the (possible) future and some parameters for every planet
-calculate possible offensive/defensive moves, and place them in a queue
-calculate possible "supplying the fronts" moves, and place them in the queue
-go through the queue, and execute the moves that have high scores

I start out with calculating a bunch of parameters for every planet:

1. For a bunch of future turns (the maximum distance between planets, to be precise), who the owner is and how many ships are on the planet. The algorithm goes something like this:
-for every turn..
Set the forces present on the planet to 0 for every player,
except the owner, who has planet.NumShips() as forces
-for every fleet, check if the fleet arrives at the current turn.
If so, add the fleet to the total size of the fleet owner's forces

Do the battle resolution thing (largest force minus second largest force is remaining number of ships on the planet. If remaining ships > 0, the new owner is the owner of the largest force.

2. Using the "future states" just calculated, also calculate the "minimum" state for each of my own planets. This will come in handy when deciding how many ships I can sent away. If I know that in 10 turns, the combination of enemy/friendly fleets arriving will reduce my fleet size on my planet to just 15 ships, I also know that I shouldn't sent away 20 ships to attack some other planet (or at least, I should be aware that that action is likely to lead to the loss of my planet)

3. For every planet, and every turn, calculate how many ships the enemy CAN sent to it's aid. My current algorithm calculting this is far from perfect (because it basically involves calculating an optimal strategy for the enemy), but even a crude calculation like...

-for every planet P
-for every turn T
-for every enemy planet EP
if pw.Distance(EP, P) < T
maxaid = maxaid+EP.NumShips()

is very handy. Numerous improvements to this can be made (including the growthrate of the enemy planets, including enemy ships that are currently underway, etc). This algorithm is essential in preventing the "sniping" as discussed in a thread by mcmillen. When you know that an enemy could sent 100 ships to planet P by turn T, and you know that capturing a neutral will only generate a profit after turn T+1, you should sent at least 101 ships =)

4. Territory scores for all planets. My algorithm is very rough, but it basically calculates which planets are "the front", and which planets are "the backland" that can supply the front with troops. As a basis, I'm using something like the ratio between the average distance to friendly planets and the average distance to enemy planets.

Ok, the preliminary calculations out of the way (takes about ~100 lines of code in my script, including comments and generous whitespace), it's time for the actual algorithm. This is also split in 2 main parts: the first part that calculates possible moves and assigns them a score, and the second part that takes all the possible moves, sorts them by score, and then executes them as long as I have ships left and the move is still needed, highest scores first (if we have multiple possible attacks on a single planet, just execute the one with the highest score, and then change some flag to indicate that further attacks on the planet shouldn't be executed). The advantage of this method is that it's relatively straight forward. The disadvantage is that the tactics generated will not be very cohesive - every attack takes place in a vacuum, without knowledge of other attacks that I'm ordering or consisdering in that turn. For example, attacking two planets at the same time so that enemy can't defend both of them at once is a move that my bot will never (conciously) generate.

Right. So the part where I generate possible moves. This is again split into two parts: calculating offensive/defensive moves, and calculating moves that supply the front with fleets. The supply moves are the simplest: if a planet isn't at the front (see 4.), look up how many ships I can safely send away (see 2.), and sent them to some more "fronty" planet. Or at least: enter the possible move into the possible-moves queue, and give it a low score. So it will only happen if the offensive/defensive algorithm doesn't find a better possibility.

The offensive/defense algorithm is actually pretty simple, after all the initial calculations are done. For each of my planets P, look up the future states of all other planets OP (using 1.) at pw.Distance(P, OP) turns in the future. If the planet will be neutral, the cost of conquering it will be the amount of neutral ships present. If the planet will be hostile, the cost will be 0. Then, determine how many ships the enemy can have on the planet before the turn that I will turn a profit (using a combination of 1. and 3.). Just to be clear: when the cost is 0, you're already making a profit 1 turn after conquering it, but when the cost is like.. 5 times the growthrate, you'll be only making a profit 5 turns after you conquered it. The amount of ships that the enemy can have on the planet before profit is the amount of ships that I want to send. If I can actually send so many ships without endagering P itself (see 2.), calculate a score that roughly indicates the advantage that I might get from such a move (influenced by distance between the planets, growthrates of both P and OP, etc..), and dump it in the possible moves queue. That's it.

One important point about the FuturePlanetState (FPS) calculation is that it just knows about the potential outcome of a certain turn, but it doesn't tell you how it came to be that way (at least, my implementation doesn't tell you directly). For example, if in 10 turns, an enemy fleet of 50 ships is going to hit a neutral that has 49 ships, my FPS will just say "in 10 turns, this planet will have 1 enemy ship on it". Which makes it a very tasty target. But sending 2 of my ships to conquer it would be a mistake: the end result would be 50 enemy ships, 49 neutrals, and 2 of mine: I'm clearly not going to win it. So you shouldn't attack when the planet is changing hands from neutral to enemy in pw.Distance(p,op) turns.

On the other hand, this quirk of the FPS calculation also gives you a free defensive mechanism. If 10 turns from now, 30 enemy ships are going to hit my 29 defensive ships, the FPS will just return that the planet has 1 enemy ship on it. A tasty target that my algorithm will attack with (at least) 2 ships. But what will actually happen is that in ten turns, the 29 defending ships will be joined by my "attacking" fleet of 2 ships, and the enemy fleet of 30 also arrives. In total I will have 31 ships against the enemy 30, so I will win that fight without giving up the planet for a single turn (and thus not losing 1 turn worth of growthrate). So while my algorithm thinks it's attacking an enemy planet, it's actually defending one of my planets. Oh well.

Ok this is getting much too long already, but I think the main ideas have been illustrated. If anyone wants to know some more detail, feel free to ask. =)
Mistmanov
Colonel
 
Posts: 70
Joined: Fri Sep 24, 2010 6:50 pm

Re: Complete overview of my script

Postby cobracom » Mon Oct 04, 2010 8:58 pm

It's amazing how much my bot resembles yours (pretty much the same scoring mechanism, and tactics), but yet I'm only at the 120 place.
On the other hand, this gives me hope :)
cobracom
Lieutenant
 
Posts: 14
Joined: Fri Sep 10, 2010 3:46 pm

Re: Complete overview of my script

Postby athena » Tue Nov 09, 2010 10:42 pm

How do you handle re-evaluation of the calculated future every time you execute a move?
User avatar
athena
Lieutenant-Colonel
 
Posts: 41
Joined: Wed Sep 29, 2010 10:37 pm
Location: Copenhagen, Denmark

Re: Complete overview of my script

Postby Mistmanov » Wed Nov 10, 2010 8:28 am

Mistmanov
Colonel
 
Posts: 70
Joined: Fri Sep 24, 2010 6:50 pm


Return to Strategy

Who is online

Users browsing this forum: No registered users and 1 guest

cron