Author |
Topic: Google AI Contest Galactic Conquest (Read 22550 times) |
|
Fritzlein
Forum Guru
Arimaa player #706
Gender: 
Posts: 5928
|
 |
Re: Google AI Contest Galactic Conquest
« Reply #45 on: Sep 15th, 2010, 11:48pm » |
 Quote  Modify
|
on Sep 15th, 2010, 7:33pm, jdb wrote:| Its easier to iterate through destination planets. Then its easier to launch joint attacks on a planet. |
|
Yes, but if you go by destinations to coordinate attacks, it can ruin the calculation of coordinated defense. You might have two planets which are each safe with each other's help, but if you launch all the "free" ships from both of them, you make them both vulnerable. Meanwhile every ship on a doomed enemy planet becomes a free ship for attacking you. If you iterate by origin planets, then you know for later planets whether the reinforcements are coming, or available later, or already committed elsewhere.
I think generally coordinated attacks are less powerful than they seem anyway, because of mismatched distances. If the ships that arrive first aren't enough to do the job, and more ships from further away are necessary, at least the further ships should be launched first with the nearer ships launched just in time to arrive simultaneously. But unless the distances are close to equal, this will be only slightly superior to launching the further ships as reinforcements to the nearer planet.
The brawl you linked earlier had the player with the winning position lose it because he launched a coordinated attack on one opposing planet, which left three planets weak. The other player abandonded the planet under attack and took all three vulnerable planets. But the player with the better position had the higher growth rate and would have had enough ships to defend all controlled planets instead of attacking.
The moral is that defending a friendly planet can be done more efficiently than attacking an enemy planet. If you can find a way to iterate by destination without messing up calculation of home defense, then I'm all for it.
|
| « Last Edit: Sep 16th, 2010, 1:42am by Fritzlein » |
 IP Logged |
|
|
|
Rednaxela
Forum Senior Member
Arimaa player #4674
Gender:
Posts: 34
|
|
Re: Google AI Contest Galactic Conquest
« Reply #46 on: Sep 16th, 2010, 12:14am » |
Quote Modify
|
on Sep 15th, 2010, 11:48pm, Fritzlein wrote:
Yes, but if you go by destinations to coordinate attacks, it can ruin the calculation of coordinated defense. |
|
That type of reason is why I think any methods that do a simple iteration through planets to allocate resources are going to be limited by biases in the decision ordering even with the best heuristics for the decision ordering.
I think such issues are nicely avoided when using things like simulated annealing or other global optimization methods to do the final resource allocation. Essentially, my point is that committing to any part of a move before considering the whole situation, is going to have problems when the situation is non-trivial.
|
| « Last Edit: Sep 16th, 2010, 12:21am by Rednaxela » |
IP Logged |
|
|
|
Sconibulus
Forum Guru
Arimaa player #4633
Gender:
Posts: 116
|
|
Re: Google AI Contest Galactic Conquest
« Reply #47 on: Sep 16th, 2010, 12:39am » |
Quote Modify
|
"Wait, why are many small, cheap planets worse than a few big, expensive planets? If I take five planets of growth rate 1, each with payback time 9, am I not better off than if I take one planet with growth rate 5 and a payback time of 10?"
In both cases, the total growth rate is 5, at least in my mind. My argument was that, assuming two planets are equidistant from your base, and both can be considered "safe" You would rather take a planet with growth rate 5 and 19 troops on it than one with growth rate 2 and 5 troops on it. The payback time on the smaller planet is one turn sooner, but two turns after that the larger planet has netted you one more ship, and will net you three each turn thereafter.
As far as attacking the enemy homeworld goes... I'd prefer to colonize well to maximize growth and then hopefully cut the enemy off from as many neutral planets as possible. Perhaps some of the territory control strategies learned from the Tron competition could be useful, although then again, perhaps not.
|
|
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: Google AI Contest Galactic Conquest
« Reply #48 on: Sep 16th, 2010, 12:50am » |
Quote Modify
|
on Sep 15th, 2010, 6:05pm, Fritzlein wrote:
1) Keep myself safe from ships already launched, taking into account also reinforcements launched toward me by planets further from the front.
2) Send ships to reinforce a friendly planet threatened by enemy ships already launched, but only if they will get there in time and the planet will otherwise be lost.
3) Keep myself safe from ships that haven't yet launched, in the concentric circle definition above.
4) Take an enemy planet that I can conquer by myself.
5) Take the neutral planet with the lowest stpg cost that I can conquer by myself and keep long enough for payback. (possibly more than one if ships are free)
6) Send all available ships towards a planet that is in closer contact to the enemy. (possibly the planet we should reinforce is a presently-neutral planet we are going to conquer with ships already in the air that will be close to a presently-neutral planet the opponent is going to conquer with ships already in the air)
|
|
I essentially agree with that. What is not explicitly noted in the safety circles calculation is that you could redistribute ships among your planets (toward the center) even when these ships are not available for sending elsewhere.
In the scenario with exchanged home planets there is also option to evacuate the grown ships to new home planet and continue with their flow to neutral planets attackced by enemy. I am too lazy to calculate this, but I hope you could capture them so you won on his investment which didn't fully returned.
So I guess ACD<<H.
|
| « Last Edit: Sep 16th, 2010, 12:53am by Hippo » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Google AI Contest Galactic Conquest
« Reply #49 on: Sep 16th, 2010, 1:31am » |
Quote Modify
|
on Sep 16th, 2010, 12:39am, Sconibulus wrote:| My argument was that, assuming two planets are equidistant from your base, and both can be considered "safe" You would rather take a planet with growth rate 5 and 19 troops on it than one with growth rate 2 and 5 troops on it. The payback time on the smaller planet is one turn sooner, but two turns after that the larger planet has netted you one more ship, and will net you three each turn thereafter. |
|
Well, sure, but what were you doing in the mean time with the 14 extra ships that you saved by going after the smaller planet? Maybe they were taking a planet with growth rate 3 and 10 troops on it, so in total taking smaller planets comes out ahead!
My prioritizing colonization by STPG (ship-turns-per-growth) makes the assumption that all ships not used for one thing can be used for something else. Of course this won't always hold true: sometimes the value of ships is greater than others. Sometimes you don't have 20 ships to spare to take a big planet so sending 6 to take a small one is the best you can do. Sometimes if you send 6 ships to take a small planet, the 14 you have left over will have no good job. It can cut either way. But I think by and large the assumption of a homogeneous value of ships is a pretty good approximation.
Indeed, if we had a one-player game of colonization where the bot was totally ignorant of geography and couldn't plan ahead, but instead only ranked neutral planets to colonize by some formula on distance, ships and growth, I'll go out on a limb to claim that STPG would colonize more efficiently than your proposed metric, thus ending with more ships after 200 turns. Probably JDB will not consider that a useful experiment to run, though, so I am safe staking a claim on something that will never be disproven. 
|
| « Last Edit: Sep 16th, 2010, 3:50am by Fritzlein » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Google AI Contest Galactic Conquest
« Reply #50 on: Sep 16th, 2010, 1:36am » |
Quote Modify
|
I just noticed that the bot that was tops on dhartmei's server three days ago is 300 elo points behind the current top bot. One hundred elo improvement per day? This competition is already fierce!
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: Google AI Contest Galactic Conquest
« Reply #51 on: Sep 16th, 2010, 1:40am » |
Quote Modify
|
Note though that due to a change in the server software all previous game and ranking information was wiped in between. At this point I think the rankings are still sorting themselves back out from that so it's really important at the moment to take pay attention to the confidence intervals as well.
Janzert
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Google AI Contest Galactic Conquest
« Reply #52 on: Sep 16th, 2010, 2:23am » |
Quote Modify
|
on Sep 15th, 2010, 4:52pm, Fritzlein wrote:If opportunity cost is ships*turns, then attacking planet B costs me 20 ship-turns while attacking planet A costs me 65 ship-turns. In general for a neutral with growth rate G, distance D, and ships S, the opportunity cost will be approximately
(D+1)*(S+1) + (S)(S-1)/2G
At the end of that phase we will have has many ships as at the start, but our growth rate will have increased by G. So our lost ship-turns per growth (STPG) is
((D+1)*(S+1) + (S)(S-1)/2G)/G
Applying that to map 88, we get desirability ratings of
planet troops growth distance stpg
a 8 5 6 15
c 4 4 14 20
d 31 5 4 69
e 30 5 7 84
f 29 4 9 126
b 67 5 8 299 |
|
I just read the rules and realized that ships get to their destination one turn faster than I thought. The (D+1) in my formula should therefore be simply D. STPG should be
(D*(S+1) + (S)(S-1)/2G)/G
I have updated my table, and added PaybackTime (pbt) and Sconibulus's suggestion (scon) for comparison
planet ship grow dist stpg pbt scon
------ ---- ---- ---- ---- --- ----
a 8 5 6 13.0 7.6 2.2
c 4 4 14 18.3 14.8 -24.4
d 31 5 4 62.8 10.2 -5.6
e 30 5 7 78.2 13.0 -14.0
f 29 4 9 118.3 14.8 -24.4
b 67 5 8 285.7 21.4 -39.2
All three formulas like A the most and FB the least. The difference for this map is that stpg orders the middle planets CDE, with C far ahead, whereas pbt and scon order them DEC, with C far behind.
I believe that C is a great planet to take, since so few ships are required for a four growth rate, but I can't think of any theoretical arguments why C is better than D and E besides what I have already said about opportunity cost. Probably I will just have to watch a bunch of different scenarios play out to get a good intuition.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Google AI Contest Galactic Conquest
« Reply #53 on: Sep 16th, 2010, 3:18am » |
Quote Modify
|
on Sep 16th, 2010, 1:40am, Janzert wrote:| Note though that due to a change in the server software all previous game and ranking information was wiped in between. At this point I think the rankings are still sorting themselves back out from that so it's really important at the moment to take pay attention to the confidence intervals as well. |
|
OK, so maybe the pace of improvement isn't as great as I thought. Also playing through some of the games makes it clear that the best bots are still making plenty of strategic mistakes. In particular, bots love to launch futile attacks against enemy planets. I think they must wipe out a lot of weak competition in this way. But if both bots know how to defend well, and they aren't in close contact, the correct strategy appears to be taking an additional neutral planet in your home area, even an expensive one.
I guess roughly speaking, if the players are about 10 spaces apart and they each have a growth rate of 15 in their cluster of home planets, it would take a surplus of about 150 ships to win an enemy planet, assuming competent defense. So even if the cheapest remaining neutral planet on your side is 70 for 3 additional growth, you should be able to take it and still hold on to everything, eventually outgrowing your opponent.
Futile attacks on the opponent was the more subtle strategic error I saw; the gross error I saw was attacking neutral planets closer to the enemy than to the attacker's ability to reinforce, thereby immediately losing a conquered neutral to a counter-strike. So it is important to know how to punish an opponent that ventures on to your side of the board.
Watching a few more games is changing my mind a little bit about strategy: precision defense and aggressive colonization of defensible planets is gaining ground in my thinking relative to attacking the opponent. I'm not seeing the benefit of attacks that leave one vulnerable to counter-attack or attacks that have no chance of success against an aware defender.
Yes, I saw some earlier games where the better colonizer lost to a better fighter. But the lag time it takes ships to travel while every planet grows seems to mean that a good defense generally nullifies a good offense. When fighting tends to stalemate despite one side having a few more ships, focusing on a higher growth rate makes more sense to me.
Perhaps the balance between offense vs. defense+colonization is essentially a function of how close the players are to one another. The closer the contact, the less one can afford a temporary ship deficit. The greater the separation, the more colonization will have time to pay back without losing anything.
|
| « Last Edit: Sep 16th, 2010, 3:54am by Fritzlein » |
IP Logged |
|
|
|
Manuel
Forum Guru
Arimaa player #4020
Gender:
Posts: 58
|
|
Re: Google AI Contest Galactic Conquest
« Reply #54 on: Sep 16th, 2010, 8:49am » |
Quote Modify
|
on Sep 15th, 2010, 6:40pm, Fritzlein wrote:
Hmmm, that looks correct, except I would say
AC < ACD < ACDE <<< AC
That is to say, it would be like scissors losing to rock by one, rock losing to paper by one, but paper losing to scissors by ten. Game theoretically, you would end up almost always doing rock, or in this case, almost always attacking ACD on the first turn.
|
|
Actually, I think I don't agree that ACDE <<< AC.
The reason would be that the opponent could then take over my home, isn't it? But so what? Then I own ACDE and the opponent owns ACHH, which have the same value. Only the ships count is against me, but the growth rate is equal!
And if the opponent attacks my home with all he has, it seems to me that I can then attack and hold F, giving me the advantage again. (this last remark I could be miscalculating by a few ships...)
If the opponent attacks with just the right amount, I cannot take F, but then everything is stable and I am only behind a few ships (ok, about 30 ships..), so ACDE < AC, but not ACDE <<< AC.
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Google AI Contest Galactic Conquest
« Reply #55 on: Sep 16th, 2010, 12:20pm » |
Quote Modify
|
I've almost got a first draft working. Just need a couple more things. Here is the way things work.
1) All player planets are analyzed. Available troop levels are set so that fleets in the air are defended. If there is only one planet, available troop levels are set to defend against maximum attack.
2) All player planets are analyzed to see if they require additional support to defend fleets in the air. A list of TroopRequests is generated. After all TroopRequests have been issued, they are prioritized and we attempt to fill them in order. Requests are filled drawing troops from the closest planet first, moving outwards if required.
3) Enemy planets are analyzed to see if they can be captured. TroopRequests are issued and handled the same as before.
4) Neutral planets are analyzed. Same system of TroopRequests.
So, I need some method of ranking the following:
A) Player planets to defend.
B) Enemy planets to attack.
|
|
IP Logged |
|
|
|
Oystein
Forum Full Member
Arimaa player #3272
Gender:
Posts: 21
|
|
Re: Google AI Contest Galactic Conquest
« Reply #56 on: Sep 16th, 2010, 1:45pm » |
Quote Modify
|
on Sep 16th, 2010, 12:50am, Hippo wrote:In the scenario with exchanged home planets there is also option to evacuate the grown ships to [...] neutral planets attacked by enemy. I am too lazy to calculate this, but I hope you could capture them so you won on his investment which didn't fully returned.
So I guess ACD<<H. |
|
I use upper case for planets closest to player P and lowercase those closest to player p.
Considering P goes for A, C and D.
The planets pays off very quickly specially A and C. Even D repays before p can take it, but p does not have to fight off neutrals, so I think it should be viewed as a small loss. If p sends all his ships towards H, A, D and C then P should be able to take h, a, d and c and end up with more ships. But p have one option I did not consider. He can leave his doomed h planet and go after a and c. The result looks best for p, but it is not trivial to evaluate so I have to agree jdb:
on Sep 15th, 2010, 7:44pm, jdb wrote:| I don't know what will happen here. The fight could get very complicated. |
|
|
|
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: Google AI Contest Galactic Conquest
« Reply #57 on: Sep 16th, 2010, 2:11pm » |
Quote Modify
|
I have calculated AC against ACDE for several turns, but seems simulation would be better. I am not sure what happens if AC player sents all of his ships to ACDE home and ACDE player also moves all his ships there.
Of course AC player gains the planet at first, but I am not sure reinforcements from AC arives at time not to lose it back.
Actually one would not sent all ships at the same time, but the result would be as described. *
If AC player could hold the planet the game results in stalemate, nobody would be powerfull enough to capture any neutral planet. The growth would be same so AC player wins otherwise he loses quickly.
(AC player would have more ships, but on longer flights so not available).
* you should maintain invariant to have enough ships to cover C and your original home and only excess ships could be resent, but it could be sent at bunches of 9 while neither of the planets is attacked.
After opponent's home is taken there is no more danger for C and your own home (troops could return fast enough) so all grown ships could be immediately sent to the original home of opponent.
My simulation (by hand) leads to conclusion the AC player would lose the opponent original home planet.
So sending reinforcements this direction does not help and taking E1 would be better.
AC could hold the H2 exactly for 9 turns gaining 90 ships from opponent, but losing on noninvesting to neutrals. As E would be taken 9 turns delayed so it loses 45 ships in return. If he sends first 9 ships rather to D1 than to fight it could hold opponent's home 2 turns less losing 20 ships. But gaining D1 ... (3 turns later than opponent so losing 15 more ships)
45+15=60 so AC player won 10 ships. In that variant.
With both players holding HACDE.
Oops D costs 32 not 9 ... and due to possible counterattack the opponent's home could be hold just for 6 turns delaying expansion to D by 10 turns and to E by 8 turns so gain 60, loss 90 ... AC<ACDE
holding for 5 turns allows delaying expansion to D just for 8 turns so gain 50, loss 80 ... AC<ACDE.
OK so what is counterstrategy against ACDE?
Is ACH (sending 70 ships) good enough? It will gain 10 more ships so holding longer and allowing faster colonisation... or may be just AH?
Do due to my calculations it ACH would lead to 6 turns holding opponent's base and delaying D by 3 turns and E by 7 turns leading to loss of 50 and gain of 60.
|
| « Last Edit: Sep 16th, 2010, 4:59pm by Hippo » |
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Google AI Contest Galactic Conquest
« Reply #58 on: Sep 16th, 2010, 5:13pm » |
Quote Modify
|
Good luck with this contest guys. It would be cool to see a few teams from the Arimaa community place near the top.
If you communicate with the organizers, let them know about Arimaa and possibly using it as a future game for the AI challenge. I guess the games would have to be at Blitz or Lightning speed for a contest like this.
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Google AI Contest Galactic Conquest
« Reply #59 on: Sep 16th, 2010, 8:04pm » |
Quote Modify
|
I have a first draft working.
It loses to RageBot on three maps, map26,map44 and map 61.
They all have very close starting positions. The first draft only defended player planets from fleets already sent. This is not enough for these maps.
As a side note, map30 is an interesting map. I think the best opening move is to do nothing. The first player who leaves their home planet loses.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print