[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/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/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 - Tell us your secrets, unleash your bot's code!

It is currently Fri Jul 20, 2018 11:39 pm Advanced search

Tell us your secrets, unleash your bot's code!

Share and discuss ideas for your entries here.

Re: Tell us your secrets, unleash your bot's code!

Postby VegaForces » Mon Nov 29, 2010 5:04 pm

Bot name: VegaForces http://ai-contest.com/profile.php?user_id=12291
Unofficial Rank : Between 450 and 600 (going down in official contest apparently)
Language : Java

I used a very simple simulated annealing approach to decide on the moves at each turn.
Basically the process is the following:
1. Start with empty solution (no extra fleets)
2. Randomly add and remove fleets from current best solution
3. Estimate fitness of solution by projecting into the future, and estimating ratio of my units/total units with discount factor for uncertainty over time
4. If solution better than before keep it (annealing step, temperature etc...)
5. Keep searching until time runs out

Solutions are represented as a set of arrays that contains for each planet a normalized array of the proportion of fleets to send to each other planets.

The approach is quite effective for such a simple algorithm.
I played around with other versions that could take into account future orders. I also tried doing a co-search between my bot and the enemy bot (using the same algorithm). But in the end the original bot was doing better, and I didn't have time to work on it anymore :(
VegaForces
Cadet
 
Posts: 1
Joined: Mon Nov 29, 2010 4:50 pm

Re: Tell us your secrets, unleash your bot's code!

Postby Hippo » Mon Nov 29, 2010 10:28 pm

http://ai-contest.com/visualizer.php?game_id=9172739 an example of obvious bug ... mode changed to "FlowTurnAttack", stopping other actions, but when opponent has no planets the bot does nothing (expect defense). Normal mode would result in colonization of the cheap huge planets and easy win. Unfortunatelly I did only little number experiments with the "FlowTurnAttack" ... I would probably continue attacking nearest planet till it is surely conquered, not only till opponent has to make a defensive action ... this paralyses opponent well, but the other method would win much faster.

http://ai-contest.com/visualizer.php?game_id=9208537 one of the games when the "FlowTurnAttack" was invoked well.
http://ai-contest.com/visualizer.php?game_id=9210626 and an opposite one :(. Actually there was onother bug ... sending enough ships to plan capturing my neutrals let me wait till there were captured by enemy. I am almost sure I have thought about this option and codded against it, but I have not seen that against players in top 100 so may be it remained omited ...

http://ai-contest.com/visualizer.php?game_id=9167017 and this one ... after ships are sent to one planet, it is considered as defender for another, but without recomputation required information :( ... I hope the game was won.

http://ai-contest.com/visualizer.php?game_id=9164843 another kind of bug ... It didn't considered to attack my planets. The planet could not be defended so no defense action taken, but recapturing was not considered till I actually lost the planet. Unfortuantelly there were not ships for the action.
I must looked at the turn 33 for explanation ... it is something really surprising. Ohh :) ...
I have detected the planet is weak to be attacked, and planned number of ships on it required the action to take it ... unfortunatelly I didn't checked the planned ships are mine :( ... the check was done on several other similar places in code, but not here :roll:

... at least my code revealed a lot of possible bugs :(.

... I know this version does not consider ships in air to be resended by opponent (the version doing that was taken back for it's passivity) ... so that is not bug, but decission.

But the main problem (I expect around 100 positions) is waiting till the planet in the middle is available, than charging prematurelly and letting the planet to opponent ...
Last edited by Hippo on Mon Nov 29, 2010 11:47 pm, edited 7 times in total.
Hippo
Lieutenant-Colonel
 
Posts: 49
Joined: Wed Mar 03, 2010 6:42 pm

Re: Tell us your secrets, unleash your bot's code!

Postby CryBaby » Mon Nov 29, 2010 10:53 pm

I finally got around to commenting my source code. This is code I would be proud to show in a computer science classroom, so I had better comment it, right?

My focus was mostly on writing a clean, object-oriented framework. I think I succeeded at that, but the framework is incomplete. I didn't get a chance (or didn't take it) to expand the framework to a point where it would allow me to know everything I needed to know about the battlefield. As a result, my strategy is lacking some of the tactics I was hoping to implement, such as moving ships to the battlefront.

Of the tactics my bot is capable of, my favorite is allowing the enemy to "buy" a neutral planet for me. The enemy acquires the neutral planet at high cost, and I arrive one move later to take it at a discount. :lol:

Bot Name:
Language: PHP
CryBaby(PHP).zip
(8.22 KiB) Downloaded 140 times
CryBaby
Cadet
 
Posts: 4
Joined: Sun Nov 28, 2010 7:40 pm

Re: Tell us your secrets, unleash your bot's code!

Postby eburnette » Tue Nov 30, 2010 12:21 am

Bot name: eburnette on main server, Charmeleon, Infernape, Houndour, and lots of other mostly Pokemon names on TCP
Unofficial rank: Before new maps: 50-ish; after new maps: 150-ish
Profile: http://ai-contest.com/profile.php?user_id=7268
Language: Java
Source: Attached
Home page: http://www.zdnet.com/blog/burnette
Twitter: @eburnette

I ended up writing exactly 100 different bots and versions of bots, which are all contained in the zip file. The final submission was Charmeleon73. The most advanced one was Pichu2, but it wasn't as strong. During the final week, I played a couple thousand games with my best bots on the TCP servers and went with the one with the highest rating. Houndour6 was a runner up.

After a few early attempts, all my bots used a NegaMax (minimax) algorithm with Quiescence and Iterative Deepening. I counted 1 ply as a move by one player, i.e., the player's decision to send 0 or more fleets, so a turn is 2 plies. I basically ignored the simultaneous nature of the game by letting player 1 go first, then player 2, so player 2 should have an advantage. On every attack I simulated the results out to a horizon of 25 or 30 turns. I had a fan out of between 1 and 40 (usually about 3-5), and could plan and evaluate between 500 and 1000 moves per second.

Late in the contest I discovered doing nothing on the first move improved my scores by 200 Elo on the tcp servers, especially on the new style maps, even if the starting planets were far apart. I also discovered that doing fewer plies resulted in better game play, so I ended up limiting my submission bot to 2 plies. A 2-ply minimax should be equivalent to using a payout matrix.

I believe the place I struggled the most with was the evaluation function. In all minimax type algorithms, the evaluation function's purpose is to look at a game state and return a score. High positive numbers are good, lower or negative numbers are bad. You try and maximize your score while minimizing your opponent's maximum score at each ply. With a good evaluation function, even random move choice should result in good game play if you simulate enough of them. I tried a ton of different things but never got much better than "count all the ships at the time horizon" with a slight preference for taking the central planets. So I had to settle for trying to improve the move choice, assigning each planet a "sparkle" and going after the best planets first.

For the initial move I used a 0-1 Knapsack algorithm and a Dynamic programming solver. The unique thing I did was that instead of using a specific horizon for the Knapsack, I simulated two dozen different horizons ranging from 11 to 70 and then let the minimax pick the best. This worked really well with the old style point symmetric maps, but not so well with the new line symmetric maps.

Some of my later bots used coordinated attacks with future moves, but handling changes in plans proved to be an obstacle so they didn't work as well. Another problem I had was balancing safety and aggression. I could make an aggressive bot that could win against defensive bots, but put it against another aggressive bot like RageBot and it would often lose.

I'd like to thank the organizers for holding the contest. While I didn't do as well as I had hoped, I did learn a few tricks and look forward to the next one.
Attachments
shiva.20101125.2329.zip
(746.47 KiB) Downloaded 184 times
Last edited by eburnette on Tue Nov 30, 2010 1:03 am, edited 1 time in total.
eburnette
Captain
 
Posts: 22
Joined: Tue Sep 14, 2010 12:57 pm

Re: Tell us your secrets, unleash your bot's code!

Postby Alocaly » Tue Nov 30, 2010 1:01 am

Here is my version.

it's in python, and my current rank is around 180.
My biggest achievement is that I actually beated Iouri once in the TCP Server ( one of the latest version, BTW : iouri 95 I think. Did this version had a special bug for me :) ? )

My bot has nothing really fancy, but I had some ideas that I didn't had time to use that are perhaps interesting...

My current bot : (note nme means enemy ... )

An eval function to rate the neutral and enemy planets:
It basically evaluate how many ships I will earn from this planet in 34(???) turns.
So I compute how many ships it will take to win this planet, how long it will take, and how much I will get for the remaining time to the 34 turns.
If the planet is neutral, I substract the number of ships needed to conquer this planet ( because for an nme planet, it is not really a loss )
And for an enemy planet, I double the gain part, because it is both some new ships for me, and some ships the enemy won't have.
Last point, I substract also a defense potential, that is the distance to my closest planet. The point was to give an advantage to planets near me, because they should be easiest to defend.
It probably was a mistake, was I meant was to substract the ( distance to my closest planet - distance to the nme planet )

The algo :
* The first trame, I find how much ships need to stay on the first planet to prevent a rage like attack, and for the rest I evaluate all the planets, and sort them, and send ships to all of them.

* Other trame :
* Defense part, if a planet is attacked, I compute how many ships are needed to defend it. If it needs renforts, I send them from all the other planets starting with the closests. If not, I compute how many ships are available for attack / support.
* Attack / expansion part :
I compute the front line ( ie my planets that are the closest from at least one NME planet ),
then for each planet in the front line :
- I compute the main threat, ie the ships from the nearer NME planets. I will keep enough ships on this planet to counter this potential attack ( if possible )
- then with the other ships :
--I evaluate all the other neutral + NME planet in the front line, and I sort this list.
---For each of this planet, I evaluate how many ships I need to conquer it taking into account NME planets that are closer that me. If I have ships enough, I send them
--- If I'm leading both in growth and number of ships, I will attack the NME as much as possible, to make its number of ships going down in a relatively safe way.
--- If I'm only leading in growth and not in number of ships, I don't try to conquer neutral planets, or only if the NME is also trying to conquer a neutral planet ( so I still try to keep the advantage )
Last step : the non front line send their ships to the closest front line planet.

OK...
The weakness of my bots ( beside not being intelligent enough ):
* when there are several fronts, I should balance the ships I send to each front line planets so both are able to resist and prepare an attack
* No pathfinding : pathfinding cost you in speed ( as ships are not going in strait lines ), but give you more flexibility : it's easier to change your mind, to go from a defense part to an attack part or vice versa )
* Defense and attack / expand are separated : so my bot defend a 1 growth planet when it could have instead attacked and win a 5 growth planet !
* My eval function is not good enough, and I often capture low growth planets, when I should have wait to get a bigger one... I even conquer 0 growth planet :( ( ok, in some cases, it surely can be strategic, but not in my case !! )
* I don't deal correctly with the center planet, that I too easily let the other bot capture...


Some Ideas I had for evaluation that I feel were interesting :
* making a kind of static heat map with the planet growth (at the first frame ) : a kind of map where all planets will increase the score of its neighbour, based on its distance. The goal is to valuate more the groups of planets, and above all the group of big growth planets !
* Give a score for all planets as its growth / (total growth of the map ). The goal here is to say a 5 growth planet on a very sparse populated map is much more important that a 5 growth planet on another map.
* making a dynamic kind of heat map with negative values for NME planets and positive values for mines. This shoud (?) allow to find threat from the two sides more easily.

Last point : I used the apinkin python package, that was great. But I only find last friday that there was a bug with it, that I had to fix as soon as possible !!

Alocaly / Emmanuel

Ps: by the way, thanks for the contest organisation, for benzedrine for TCP Server, for the starter packages, for all the tools from all over the community !
Attachments
googleSoum18.zip
(36.12 KiB) Downloaded 151 times
Alocaly
Cadet
 
Posts: 2
Joined: Mon Nov 29, 2010 11:59 pm

Re: Tell us your secrets, unleash your bot's code!

Postby iouri_ » Tue Nov 30, 2010 2:09 am

iouri_
Brigadier-General
 
Posts: 105
Joined: Thu Feb 11, 2010 4:16 pm
Location: Toronto, Canada

Re: Tell us your secrets, unleash your bot's code!

Postby Barefoot_Halibut » Tue Nov 30, 2010 3:24 am

Barefoot_Halibut
Cadet
 
Posts: 4
Joined: Fri Nov 12, 2010 5:46 pm

Re: Tell us your secrets, unleash your bot's code!

Postby dmj » Tue Nov 30, 2010 3:28 am

Here is my bot.



I cleaned it up quite a bit from my final submission, but it should basically be the same.

This bot contains many hacks that appeared to keep it in the top 10 before the finals... A description of what I tried to do would be best without the hacks, I think :/
dmj
Lieutenant-Colonel
 
Posts: 41
Joined: Thu Feb 11, 2010 11:36 am

Re: Tell us your secrets, unleash your bot's code!

Postby deccan » Tue Nov 30, 2010 3:49 am

Attachments
java_starter_package - 2.5 - New.zip
(8.67 KiB) Downloaded 165 times
deccan
Lieutenant
 
Posts: 18
Joined: Tue Nov 30, 2010 1:30 am

Re: Tell us your secrets, unleash your bot's code!

Postby RebelXT » Tue Nov 30, 2010 3:56 am

Name: RebelXT
Profile: http://ai-contest.com/profile.php?user_id=5853
Rank: about 50 (unofficial)
Language: Python
Source code: https://github.com/apinkin/google_ai_bot

Hey All, here is my bot. It's full of relatively simple heuristics. The main features are coordinated attacks and defense using fleet scheduling (with multiple fleets arriving on the same turn), ship funneling, and DP knapsack for the first turn only.

* When attacking, it uses a simple formula to make sure that it can get more ships to the target planet than enemy within a number of turns. Multiple planets are used for coordinated attacks, and the bot is always trying to minimize the max distance of the attacking planets to the target.
* Fleets are scheduled a number of turns into the future. A nice side effect is that it won't capture any neutral it can if there is a better neutral to capture in a few turns.
* When acquiring neutrals it also takes its cost into account to make sure that it can actually hold the planet long enough to make profit.
* When defending, it also coordinates defensive moves and schedules multiple fleets from nearby planets. It tries to send reenforcement as late as possible so that enemy does not detect reinforcing fleets too early.
* When evaluating attack on a planet, it uses a simple but effective scoring function with a limited horizon: (70 - attack_distance) * growth - cost. Attack score is doubled for enemy planets.
* Ship funneling logic is pretty simple - it tries to move all excess ships from back planets to front planets but avoids long flights.

Good luck in the final tourney, everyone! And looking forward to another challenge next year.
RebelXT
Colonel
 
Posts: 81
Joined: Fri Sep 10, 2010 2:05 pm

PreviousNext

Return to Strategy

Who is online

Users browsing this forum: No registered users and 1 guest

cron