Author |
Topic: Google AI Contest Galactic Conquest (Read 22543 times) |
|
Fritzlein
Forum Guru
Arimaa player #706
Gender: 
Posts: 5928
|
 |
Re: Google AI Contest Galactic Conquest
« Reply #90 on: Sep 18th, 2010, 8:56pm » |
 Quote  Modify
|
on Sep 18th, 2010, 3:54pm, Fritzlein wrote:| Anyway, you are only 476 Elo from the top with a very new bot. Seems to me like you're in great shape! |
|
You must be swapping in improvements as you go; five hours later you are only 226 Elo from the top of dhartmei's server. Impressive.
|
| « Last Edit: Sep 18th, 2010, 8:56pm by Fritzlein » |
 IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: Google AI Contest Galactic Conquest
« Reply #91 on: Sep 19th, 2010, 2:38am » |
Quote Modify
|
on Sep 18th, 2010, 7:19pm, Hippo wrote: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. |
|
Actually attackers goal is to exceed the number of ships in air limit L by a move where attacker sends at most A=W+(D+k)*G ships. So r-s-p game speedup is straitforward ... send any amount between A and L+G-A.
If defender sends such amount that air limit L is not exceeded, attacker saved corresponding time. But I am not sure sacrifying sometimes 2G ships for gaining one more exchange round would not be worth while for defender.
So don't exceed A too much too often  .
|
| « Last Edit: Sep 19th, 2010, 2:39am by Hippo » |
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: Google AI Contest Galactic Conquest
« Reply #93 on: Sep 19th, 2010, 8:05am » |
Quote Modify
|
Oooo Adumlah in the contest, it would be difficult to win ...
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Google AI Contest Galactic Conquest
« Reply #94 on: Sep 19th, 2010, 10:25am » |
Quote Modify
|
Fixed up some things.
Taking neutral planets. It calculates how many troops the enemy can get there on the turn after it is captured. It sends enough troops to prevent the enemy from taking the planet on the next turn.
Defending planets. It now allows partial fill on orders for defense. This allows the defense to be sent over a number of turns instead of all at once. This also applies to neutrals that we are taking and the enemy has launched an attack against.
|
|
IP Logged |
|
|
|
Rednaxela
Forum Senior Member
Arimaa player #4674
Gender:
Posts: 34
|
|
Re: Google AI Contest Galactic Conquest
« Reply #95 on: Sep 19th, 2010, 10:48am » |
Quote Modify
|
on Sep 19th, 2010, 10:25am, jdb wrote:
Taking neutral planets. It calculates how many troops the enemy can get there on the turn after it is captured. It sends enough troops to prevent the enemy from taking the planet on the next turn.
|
|
Hmm... would I be correct that the only net consequence of that, compared to sending the reinforcements on the next turn, is causing some enemies to not try, thus reducing trading of troops? If so, perhaps it would be worth not sending the extra when winning, because any resulting trading of ships will tend to work against whoever has fewer in the first place.
|
| « Last Edit: Sep 19th, 2010, 10:54am by Rednaxela » |
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Google AI Contest Galactic Conquest
« Reply #96 on: Sep 19th, 2010, 12:33pm » |
Quote Modify
|
on Sep 19th, 2010, 10:48am, Rednaxela wrote:
Hmm... would I be correct that the only net consequence of that, compared to sending the reinforcements on the next turn, is causing some enemies to not try, thus reducing trading of troops? If so, perhaps it would be worth not sending the extra when winning, because any resulting trading of ships will tend to work against whoever has fewer in the first place.
|
|
I suppose sending them on the next turn would work too.
Sometimes the decision to send has to be made before the opponent needs to launch the attack. It could be 10 turns for the player to get there and say 8 for the defender.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Google AI Contest Galactic Conquest
« Reply #97 on: Sep 19th, 2010, 1:44pm » |
Quote Modify
|
I have yet to replay a game lost by jdb-bot due to colonizing more slowly than the opponent and getting behind on growth rate. All losses appear due to colonizing planets that can't be held, and/or using troops needed to defend owned planets for colonization instead.
Just sayin'...
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Google AI Contest Galactic Conquest
« Reply #98 on: Sep 19th, 2010, 2:20pm » |
Quote Modify
|
on Sep 19th, 2010, 1:44pm, Fritzlein wrote:I have yet to replay a game lost by jdb-bot due to colonizing more slowly than the opponent and getting behind on growth rate. All losses appear due to colonizing planets that can't be held, and/or using troops needed to defend owned planets for colonization instead.
Just sayin'... |
|
I'm working away at it. Here are a couple situations, that pretty much lost the game each time.
http://72.44.46.68/canvas?game_id=44421
In the above game, on move 24, red goes after the neutral 38 planet in the upper left corner. Red already has a fleet on the way to the 35 planet in the upper left. Blue has a fleet on the way to the 73 in the upper left. Both those planets are involved in the fight.
http://72.44.46.68/canvas?game_id=45417
On turn 3, red attacks the center planet. On turn 5, blue counterattacks. Red does nothing, not good.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Google AI Contest Galactic Conquest
« Reply #99 on: Sep 19th, 2010, 2:59pm » |
Quote Modify
|
on Sep 19th, 2010, 2:20pm, jdb wrote:
Awesome. I think your chances are pretty good given how far you have come in such a short time. I note that you already ranked ahead of bartwe.6, which was topping the standings a few days ago.
Quote:
Unrelated comment on this game. What is up with your turn-11 attack on the neutral planet with 81 troops and 4 growth instead of the neutral planet with 51 troops and 5 growth rate? Are you using PaybackTime to rank planets? If so, this looks to me like an argument against PaybackTime and for STPG for ranking desirability of colonization.
But back to the point of defense, dhartmei has been hovering near the top of the standings by colonizing conservatively and saving troops for a counter-strike. I think ultimately the "second strike" philosophy loses to an opponent that colonizes as aggressively as is consistent with safety. Against the current field, however, dhartmei is winning a ton by taking advantage of overly-aggressive opponents and inaccurate defense.
Quote:| In the above game, on move 24, red goes after the neutral 38 planet in the upper left corner. Red already has a fleet on the way to the 35 planet in the upper left. Blue has a fleet on the way to the 73 in the upper left. Both those planets are involved in the fight. |
|
Turn 24, colonizing the upper right, does not appear to be a mistake. At that point all of your planets can still be protected. Turn 32, however, was pure suicide. Already two of your planets are under attack, both the upper right and the central planet. You have the troops to defend them all. But instead of guaranteeing a higher growth rate (and thus the eventual victory) by defending your defensible planets, you launch 119 ships against an enemy planet that dhartmei can defend!
Defense is more efficient than attack. A defender can hang on to everything he has even when he has fewer ships than the opponent. An attacker, on the other hand, needs a substantial superiority in ships to win. Getting the defensive calculation right will beat second-strike bots like dhartmei.
Quote:
Yes, I think that the doctrine of pre-emptive defense must be invoked for equidistant planets, not just for planets that are closer to the enemy than to you. When the planet is equidistant, you can't wait until the turn after an attack to defend that attack. You have to send reinforcements sufficient to fend off the biggest attack he could launch in that turn.
That is to say, I think turn 6 is already too late to respond, which is probably why the bot didn't respond. The defense has to come simultaneous with the (potential) attack of the opponent. Such a defense is by no means too costly; you have the ships to spare if you use them correctly.
Exactly the same problem later cost you your homeworld in this game. You sent "just-in-time" defenders for all the ships in the air, but he had an attacker that was equidistant to your nearest defender and you failed to launch a pre-emptive defense. When it was too late to defend you gave up, which is a problem, but not the primary problem. The ships were available to defend but were not used.
|
| « Last Edit: Sep 19th, 2010, 3:09pm by Fritzlein » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Google AI Contest Galactic Conquest
« Reply #100 on: Sep 19th, 2010, 3:35pm » |
Quote Modify
|
I guess a simple way of expressing pre-emptive defense in terms of troop requests
(A) When the opponent is equidistant to the nearest reinforcements, consider his troops already launched
(B) When the opponent is closer than the nearest reinforcements, consider his troops plus G*(D-d) as being launched (D-d) turns from now.
This doesn't capture all of the complexity of the situation, but it gets closer.
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Google AI Contest Galactic Conquest
« Reply #101 on: Sep 19th, 2010, 3:37pm » |
Quote Modify
|
Quote:| Yes, I think that the doctrine of pre-emptive defense must be invoked for equidistant planets, not just for planets that are closer to the enemy than to you. When the planet is equidistant, you can't wait until the turn after an attack to defend that attack. You have to send reinforcements sufficient to fend off the biggest attack he could launch in that turn. |
|
I agree about the equidistant planets. In this game, red just got killed in the opening. Its on the list.
http://72.44.46.68/canvas?game_id=47710
In this game, the other bot was sending out pre-emptive defence.
http://72.44.46.68/canvas?game_id=47491
What is the correct opening move for this map (map77)?
http://72.44.46.68/canvas?game_id=47757
The two 14's in the middle are growth 5 and are 16 turns from one player and 17 turns from the other.
I've been using paybacktime to select planets, but it is way wrong for this map.
|
| « Last Edit: Sep 19th, 2010, 3:48pm by jdb » |
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: Google AI Contest Galactic Conquest
« Reply #102 on: Sep 19th, 2010, 3:54pm » |
Quote Modify
|
on Sep 19th, 2010, 2:20pm, jdb wrote:
In this game the ships on the top right corner were totaly useless sending them back to nearest big planet while you don't have better target. If you suppose you will need these ships next turn, let them at planet otherwise sent them. the distance difference implied by wrong decision is usually less important than the flexibility.
Attacks to the 81 on right as well as to the top middle 15 were not optimal. You have to lend at the same time, not to start at the same time. You could send less ships from further planet and more from nearer one.
Were the bot planning to colonize 81 when ships were sent to top middle 15? If so, concentrating ships on home planet would speed the goal.
But seems to me colonizing the top 51 through the top middle 15 would be more effective.
It seems to me plannig what could be good targets and moving ships to their neighbourhoods but invoking attack to capture them by one strike when ready. Would help. It allows you to change the plan if needed and you could organize the flow in the way planet would be captured at the same turn.
on Sep 19th, 2010, 3:37pm, jdb wrote:
What is the correct opening move for this map (map77)?
http://72.44.46.68/canvas?game_id=47757
The two 14's in the middle are growth 5 and are 16 turns from one player and 17 turns from the other.
|
|
Yes, it's difficult decision, but the middle planets are in pairs 15+48 able to support one another. I would concentrate on them. Taking the 75 planet is bad as it implies you would lose all 4 huge centrals. Taking the distant 11 and 14 is bad as well. May be optimal choice is to sent 49+16 on near pair and wait on opponent's move. The nearby planets could hold themself and are near the other pair so if opponent attacks something alse you could take all 4.
If opponent takes his 15 and saves enough ships in reserve, I would try to create base at 31.
... these are just guesses
http://72.44.46.68/canvas?game_id=48552
2nd turn bug you don't consider ships on air to lend?
If trying to capture the central planet ... all forces should be concentrated there.
|
| « Last Edit: Sep 19th, 2010, 4:29pm by Hippo » |
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: Google AI Contest Galactic Conquest
« Reply #103 on: Sep 19th, 2010, 4:03pm » |
Quote Modify
|
Wow, jdb is now in fourth place, well done!
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Google AI Contest Galactic Conquest
« Reply #104 on: Sep 19th, 2010, 4:44pm » |
Quote Modify
|
on Sep 19th, 2010, 3:37pm, jdb wrote:What is the correct opening move for this map (map77)?
http://72.44.46.68/canvas?game_id=47757
The two 14's in the middle are growth 5 and are 16 turns from one player and 17 turns from the other. |
|
Wow, that is tricky. I have been babbling about how "second strike" is not a good idea, but here it seems whoever tries to take one of the central 14's loses to player who passes turn one for an all-out second strike on turn two. One turn waiting plus one turn extra distance means the second strike of 105 arrives on turn 18. First-strike forces are 105 - 14 + 2*5 growth, i.e. a loss. Or am I figuring that incorrectly? My first instinct was to send all 100 to the nearer central 14, but that appears not to work.
It is conceivable that the game is drawn, because if one player waits while the other player colonizes any planet other than the central 14's, the player who waited suddenly has sufficient force to take and hold the nearer central 14 by launching everything at it. Since that gives the second striker a 5-growth planet in the middle, it should be more profitable than whatever the other guy did.
I'm not at all sure about that, though. I've been way wrong about opening strategy several times so far.
Regardless of what the correct strategy is for this map, I have no idea how to encode it in a robust way. This isn't an issue of determining what planets can be held (highest priority), or safely taken (high priority), or ranking the order in which to colonize multiple planets (moderate priority), but rather a strategic decision of whether to commit troops or keep them in reserve as a deterrent to the opponent doing something. Even if we can work out the correct answer for this map, how would one decide in general?
Well, it will be soon enough to work on strategy when you have fixed the glaring tactical issues.
|
| « Last Edit: Sep 19th, 2010, 4:51pm by Fritzlein » |
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print