Author |
Topic: Google AI Contest Galactic Conquest (Read 22549 times) |
|
Rednaxela
Forum Senior Member
Arimaa player #4674
Gender: 
Posts: 34
|
 |
Re: Google AI Contest Galactic Conquest
« Reply #75 on: Sep 17th, 2010, 6:07pm » |
 Quote  Modify
|
on Sep 17th, 2010, 11:48am, Hippo wrote:
In normal game time could be important so r-s-p subgames could be important even there.
|
|
Hmm... I'm finding the r-s-p scenarios mentioned here interesting. One little thought, is I imagine most bots will behave consistently or even deterministically to them. To counter this, perhaps some kind of opponent modeling would be suitable? It could be done by having an algorithm/heuristic to detect the r-s-p scenarios, and assume the opponent will behave with the same "category" of response as they did last.
|
|
 IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Google AI Contest Galactic Conquest
« Reply #76 on: Sep 17th, 2010, 6:29pm » |
Quote Modify
|
on Sep 17th, 2010, 9:13am, jdb wrote:I would agree that over extending is a big issue. I modified RageBot, so it takes over a neutral if the paybacktime is less than 10, otherwise it attacks. It beats my bot on 20 of the maps.
I put SuperRageBot on the TCP server playing as "jdb"
http://www.benzedrine.cx/planetwars/ |
|
Cool, good to see your initials up there. You are saying that your bot that plays on dhartmei's server loses 80% to your real bot? So your real bot is actually already 240 Elo stronger than the bot in the standings? Then you're only 453 Elo from the top! 
|
| « Last Edit: Sep 17th, 2010, 6:30pm by Fritzlein » |
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: Google AI Contest Galactic Conquest
« Reply #77 on: Sep 17th, 2010, 8:20pm » |
Quote Modify
|
on Sep 17th, 2010, 6:07pm, Rednaxela wrote:
... assume the opponent will behave with the same "category" of response as they did last. |
|
Unfortunately a bot is not allowed to save any information between games and does not know what opponent it is playing.
Janzert
|
|
IP Logged |
|
|
|
Eltripas
Forum Guru
Meh-he-kah-naw
Gender:
Posts: 225
|
|
Re: Google AI Contest Galactic Conquest
« Reply #78 on: Sep 17th, 2010, 8:40pm » |
Quote Modify
|
First of all, let me say that I have't read most of the content of this thread but I've played this http://www.galcon.com/flash/play.php for like 2 hours I don't know how similar is this game to the game on the contest but this are some thing I've leraned:
1. Big planets are very important, because they produce close to the double of the immediate smaller planet, so the smallest planets s lot of times don't worth the effort.
2. The maps are way more important that the strategy, I don't know if the map that are going to be use will be "balanced" but in that flash there are some maps were a "stupid" player will win against a good one just because of the planets placing, statistically a bot should get the same amounts of "good and bad "maps for him but is the bot has "bad or good" luck it can affect their ranking greatly.
3. The strategy changes a lot depending on the maps some planets have numbers so high that the best strategy is to wait for your opponent to start moving their ships to attack.
|
|
IP Logged |
|
|
|
Rednaxela
Forum Senior Member
Arimaa player #4674
Gender:
Posts: 34
|
|
Re: Google AI Contest Galactic Conquest
« Reply #79 on: Sep 17th, 2010, 8:53pm » |
Quote Modify
|
on Sep 17th, 2010, 8:20pm, Janzert wrote:
Unfortunately a bot is not allowed to save any information between games and does not know what opponent it is playing.
|
|
Yeah, I know that. (I am writing a bot for it now and thus have paid plenty of attention to the rules.) I meant learning how the opponent reacts to r-s-p situations within one game, not between multiple games.
Of course, thats only really helpful if such r-s-p situations are common enough to happen several times per game, but I think that's not far fetched. 
|
| « Last Edit: Sep 17th, 2010, 9:28pm by Rednaxela » |
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: Google AI Contest Galactic Conquest
« Reply #80 on: Sep 18th, 2010, 1:59am » |
Quote Modify
|
on Sep 17th, 2010, 8:53pm, Rednaxela wrote:
Yeah, I know that. (I am writing a bot for it now and thus have paid plenty of attention to the rules.) I meant learning how the opponent reacts to r-s-p situations within one game, not between multiple games.
Of course, thats only really helpful if such r-s-p situations are common enough to happen several times per game, but I think that's not far fetched. |
|
Learning history from r-s-p's so far and react deteerministically neednot be the best choice as opponent could confuse you. I think better way is to modify the probabilities appropriately to the risks they invoke.
There could be situations where you need to win k from l r-s-p's to achieve several goal. (It could be even more complicated as earlier r-s-p's have bigger influence to the goal than remaining. Generally the r-s-p results tree is really complicated).
Nash Equilibrium says how to choose probabilities of r-s-p's. But how to compute it? But I am sure the Equilibrium during the game would react to already lost/won r-s-p's better than deterministic way to do that.
What is important ... you don't have to won by a lot, you just have to won so you could take lower risks when leading, but higher when losing.
OK at least: Constant play would lose against player prepared for constant play, for any determnistic player there is counterstrategy.
http://ai-contest.com/visualizer.php?game_id=4537465 game ... McLeopold failed in flow attack as it was for very long distance and the opponent was able to take neutral planet in between to increase grow ratio fast enough not to lose the attacked planet.
I am still thinking about the easiest situation ... 2 isolated planets in distance D of the same growth rate G where the difference in number of ships is grater than D*G.
Let S is # of stronger player ships while W is # of weaker player ships.
Both players have option to try to conquer opposing planet at turn t+D. Investment at least D*G+1 is required (sufficient if the other player sents all ships to the air).
So options of defending player are send nothing or send any number of ships higher than D*G.
Options of attacking player are the same, but there is no reason to sent more than amout winning in the case opponent leaves all ships at home. So first option is to sent W+D*G+1. There is no reason to sent W to W+D*G ships as opponent never sends one to D*G ships. And winning by 1 is sufficient. So 2nd option is to sent W-1 ships.
This is why defender has no reason to sent amount between D*G+2 and 2*D*G+1 and ....
|
| « Last Edit: Sep 18th, 2010, 10:30am by Hippo » |
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: Google AI Contest Galactic Conquest
« Reply #81 on: Sep 18th, 2010, 11:13am » |
Quote Modify
|
I find this game quite uninteresting, I don't know why... I'm sure it has a lot of strategy, but it's hard to appreciate visually. Probably too much information to look at.
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Google AI Contest Galactic Conquest
« Reply #82 on: Sep 18th, 2010, 12:52pm » |
Quote Modify
|
I put the real bot up on the server as "jdb"
|
|
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: Google AI Contest Galactic Conquest
« Reply #83 on: Sep 18th, 2010, 3:53pm » |
Quote Modify
|
on Sep 18th, 2010, 12:52pm, jdb wrote:I put the real bot up on the server as "jdb"
|
|
You should better centralize your ships ... the ships on periphery are mostly useless. Just interrupt the flow when under attack and if not sufficient, sent some ships back to arive exactly on time. You also attack neutrals on periphery when center is under attack. Even more, you attack neutrals with insufficient power to take them on one turn.
(You don't have to minimize ships in air, but ships not in the center) ... Now I am going to read Fritz comments ...
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Google AI Contest Galactic Conquest
« Reply #84 on: Sep 18th, 2010, 3:54pm » |
Quote Modify
|
Very cool. I'll start re-playing games and giving commentary if I see anything interesting that looks fixable.
This loss would have been prevented by reinforcing the upper left planet with more ships from the home world on turn six. Yes, you did hold the planet long enough to defend it from the opposing home world and get payback, which was nicely done, but an even more precise defense would have turned the opening into a decisive victory for you. As soon as the opponent colonizes his first planet, he has a lauchpad for an attack that is closer to our upper left than any reinforcements are, so a pre-emptive defense is necessary. It is important to recognize the situation where the defense has to be launched before the enemy attack is launched. That demand on our defense is only temporary, though, because as soon as the second planet in the upper left is colonized, it gives a defensive buffer, as the growth rates of those two planets will protect each other.
Even after the enemy attack on turn 8 ensures that you will lose that key colony, your growth rate is still greater than his, so you might conceivably win anyway, but the turn 20 attack on the 25-troop neutral in his territory seems like over-reach to me, leaving too few troops to defend other home planets. On such a messy board with close contact and lots of places for player vs. player fighting, attacking neutrals seems out of place.
I'm trying to think of a strategic rule of thumb for ruling out attacking neutrals when combat is close, and I can't think of a good way to encode strategy. So if the tactical calculation of planet safety can't be improved to the point of seeing that another colonization loses some controlled planets, I don't know how to fix this.
The tactics of the ensuing brawl are hard to follow, but my general sense is of overly-aggressive play leaving controlled planets vulnerable. What is up with turn 26, launching an attack against the upper left, when little guys in the middle are in serious danger? Were the ships used in that attack considered "free" by the defensive calculation? If so, is there an easy way to fix the caclulation of what is needed to defend the middle?
I simply don't like launching attacks with too few troops to win. The stuff launched on turn 26 was not enough to win the fight. This is a more important error to my mind than the fact the even the follow-up attack came up one short. (Doh!) If you have send a followup attack to make your initial attack win (even given no enemy reinforcements), then you are strictly better off waiting until you have enough troops to win the battle and sending those all at once. Save up before committing to the attack in order to give yourself time to change your mind. Opportunity cost is huge.
My overall impression of this game is of a superior colonizer (jdb) losing to a superior fighter (8-12Bot). I stand by my impression that improving the defensive aspect of the fighting is most important. Since defense is more efficient than offense, it is more important to be good at that.
Anyway, you are only 476 Elo from the top with a very new bot. Seems to me like you're in great shape!
|
| « Last Edit: Sep 18th, 2010, 3:59pm by Fritzlein » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Google AI Contest Galactic Conquest
« Reply #85 on: Sep 18th, 2010, 4:37pm » |
Quote Modify
|
on Sep 18th, 2010, 3:53pm, Hippo wrote:| You should better centralize your ships ... the ships on periphery are mostly useless. Just interrupt the flow when under attack and if not sufficient, sent some ships back to arive exactly on time. You also attack neutrals on periphery when center is under attack. |
|
I agree with the strategic idea of centralizing ships, and this game proves that power radiates from the center. However, I still hold out hope that the strategic problem could be solved by a sufficiently good tactical calculation about what controlled planets are vulnerable to loss. My hunch is that improving the tactics of defense so that the bot centralizes ships because it must will be more efficient than having some strategic slider that tries to balance the colonization/fighting tradeoff. The strategy will always be fuzzy, but if there is a way to know precisely how many ships are needed on defense, then the best thing to do with with any leftover ships is usually to colonize rather than centralizing more.
In the game I linked, the central planet is going to be lost, more's the pity, but even then jdb should be able to hang on to his other four worlds to end up with the superior growth rate if he doesn't mistakenly colonize more. This necessary calculation seems to be in line with what I said earlier about pre-emptive defense: when the attacker is closer to your planet than your ability to reinforce, you have to send reinforcements before he launches an attack. Perhaps the "concentric circle" methodology I outlined before would calculate this properly, generating a reinforcement request that prevents the peripheral worlds from colonizing more rather than performing mandatory centralization.
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Google AI Contest Galactic Conquest
« Reply #86 on: Sep 18th, 2010, 6:09pm » |
Quote Modify
|
Thanks for all the comments.
Centralizing ships does look important. I'll have to add something for that.
I have to do some work on how it simulates the future. Cutting corners in that area looks like a mistake. Most of the attacks/defence it gets wrong are because it didn't factor something into the simulations. I'll work on that this weekend.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Google AI Contest Galactic Conquest
« Reply #87 on: Sep 18th, 2010, 6:25pm » |
Quote Modify
|
on Sep 18th, 2010, 6:09pm, jdb wrote:| I have to do some work on how it simulates the future. Cutting corners in that area looks like a mistake. Most of the attacks/defence it gets wrong are because it didn't factor something into the simulations. I'll work on that this weekend. |
|
I eagerly await the results. I'm sticking by my "tactics are more important than strategy" story until proven wrong. By tactics I mean precise calculation of how many ships are needed to defend/liberate a planet, as opposed to the fuzzy strategic tradeoffs such as fighting vs. colonizing or committing vs. waiting. I think it is good enough to have the relatively brain-dead strategy of trying to win by (A) never losing a planet, (B) colonizing as aggressively as is consistent with safety, and (C) only attacking an enemy planet that can be immediately and surely taken. That strategy plus excellent tactics will top the current ladder at any rate, and may even suffice to win the whole contest.
|
| « Last Edit: Sep 18th, 2010, 6:33pm by Fritzlein » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Google AI Contest Galactic Conquest
« Reply #88 on: Sep 18th, 2010, 6:59pm » |
Quote Modify
|
Vortex is the current leader on dhartmei's server. In this game, you had him beaten as of turn ten because you have a higher growth rate and all six of your planets are defensible against his four. But somehow your bot decides it is better to attack than defend, opening up vulnerabilities that keep the result in doubt. Finally the vulnerability is made critical by deciding to colonize two more planets in the middle of the donnybrook. Such a shame for a promising start! And only just seeing what it takes to keep all conquered planets would have turned it into a win...
|
|
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: Google AI Contest Galactic Conquest
« Reply #89 on: Sep 18th, 2010, 7:19pm » |
Quote Modify
|
After several hours of calculations I came to easy deterministic strategy for fast capture for the case two lonely planets:
Let growth rate of both planets is G, tehir distance D, stronger player has S ships while weaker player has W ships.
Stronger player sends ships in bunches of DG+S-W
until the number of ships in the air is higher than W+(D+k)*G on turn k. At that time the flow of ships is stopped.
Weaker player has choice to send remaining ships immediately, but in that case he loses 2*G times the differnece between home exchanges. The other possibility is to left so many ships that home is defended even on turn (k+D-1). But in that case only DG defender ships would remain at turn k+D so attacking player could send all ships back without fear of losing the conquered planet.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print