Author |
Topic: Google AI Contest Galactic Conquest (Read 22545 times) |
|
Fritzlein
Forum Guru
Arimaa player #706
Gender: 
Posts: 5928
|
 |
Re: Google AI Contest Galactic Conquest
« Reply #60 on: Sep 17th, 2010, 12:17am » |
 Quote  Modify
|
on Sep 16th, 2010, 8:04pm, jdb wrote:| 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. |
|
I'm not sure about that. If I am calculating correctly, map 30 has the home worlds 5 apart. That means each player could use 25 ships for something else and still be in no danger of losing the home planet. There is only one planet on the map that can be taken for so little, and it happens to be distance 14 from us and distance 14.002 = 15 from him. Therefore we can send 21 ships to it, and if he tries to take it from us, we match him ship for ship with a one-turn lag, so our reinforcements arrive simultaneous to his attack.
Sending ships away from the center give the opponent more freedom, because now he can send off 25+21=46 ships without losing his home world. But there are no neutrals that can be conquered for just 46, except his symmetrical planet for 21.
I believe, therefore, that the only correct move in the opening of map30 is to take the cheapest neutral planet way on the edge of the board. However, if both players do this, it might not break the stalemate. One player who uses the production from the neutral to attack the opposing homeworld may force an equal reinforcement that leaves each player with only 30 free ships, not enough to take a second neutral.
Extrapolating this example, every game is theoretically drawn unless the homeworlds are far enough apart or the neutrals are cheap enough and near enough. A symmetrical player-vs.-player combat with no colonization should always be drawn. It is only when the players must make decisions about ships vs. growth (i.e. fighting vs. colonization) that there is room for strategy.
|
|
 IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Google AI Contest Galactic Conquest
« Reply #61 on: Sep 17th, 2010, 12:31am » |
Quote Modify
|
The discussion about map 88 has convinced me that it is bad sometimes to defend against both all fleets that are in the air and all fleets that could be launched. The exceptions so far seem to rely on trading planets, i.e. your defense is strong enough to trade with an attack that is strong enough.
Let d be the separation distance, S your ships, G your growth, s his ships, g his growth. Then he needs S+D*G+1 to beat you and needs to leave S+G-1-(D+1)*g to stop a counter-attack next turn, so you should be OK as long as s < 2S + (D+1)*(G-g), or equivalently S > (s - (D+1)*(G-g))/2. For the home worlds on map88 (or for that matter on any map) the G=g, so the term goes away and you can send away half your ships knowing that it will just be a trade.
Looking forward, though, if only the ships involved in trading the homeworlds continue to fight each other, there are several possible scenarios. (A) He is no longer strong enough to retake his home world, so all he gained was one turn of producing 10 more ships than you. (B) He is now strong enough to retake his homeworld while keeping yours. (C) He is strong enough to retake his home world, but this will again allow you to trade back, so we will just net another ten ships. The trades can volley back and forth until landing in case (A) or (B).
Map 88 stops this kind of trading and re-trading quickly because planet D is closer to each homeworld than they are to each other, while planet A is extremely cheap and not very far off either, meaning that other planets which have been colonized determine the outcome of the battle between homeworlds. If however, the neutral planets weren't so near, cheap, and powerful, we would have a purer player vs. player fighting situation that required a better bound on necessary home defense than S > s/2.
I'm glad jdb chose this map for discussion, because it illustrates many complications that arise when players are close.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Google AI Contest Galactic Conquest
« Reply #62 on: Sep 17th, 2010, 1:21am » |
Quote Modify
|
on Sep 16th, 2010, 12:20pm, jdb wrote:So, I need some method of ranking the following:
A) Player planets to defend.
B) Enemy planets to attack. |
|
Despite the analysis of map 88 which has shown that playing safe (attack only AC) is sub-optimal, I still advocate building your first-pass bot on the principle of defense-first. The best anyone will do against that opening is equal our growth rate with an extra five or ten ships when the dust settles. That won't be enough of an advantage for them to take any of our planets, so we will have plenty of time to outplay them after that. Meanwhile not playing defense-first makes it very difficult to avoid game-losing mistakes, and also leaves us with extra unallocated ships to take advantage of game-losing mistakes by the opponent.
If you can defend all of the planets you control against all the fleets in the air plus all possible enemy attacks that could be launched, allocate ships to that first. Note that by "planets you control", I include also neutrals and enemy planets that your ships in the air are going to take. These are just as important to defend as the ones you already literally control.
If you can't defend all of your planets, you are probably going to lose the game, but a simple way to rank them would be to abandon the planet it will be the most turns until you lose if you do nothing. Then see whether dropping that one from the list allows you to defend all the rest. Iterate until you have a defensible set of planets. For any planet you have decided to abandon, immediately evacuate all friendly ships in pursuit of some other objective, or at least as many ships as you can evacuate without speeding up the time at which the planet will be lost. (Possible exception: don't evacuate an indefensible planet until the enemy ships necessary to conquer it are in the air. Otherwise the evacuation might provoke an attack the opponent is too dumb to hit on by himself.)
Only after allocating the troops necessary to defend the largest possible set of planets you already control, consider what free ships you have and whether those might take an enemy planet. If you have enough free ships to take more than one enemy planet, you are probably already won, but I suggest prioritizing by the same cost metric as for neutrals: ship-turns-per-growth. (D*(S+1) + (S)(S-1)/2G)/G The difference is that you double the G in the formula to reflect that you are taking growth away from him too.
Often the only planet you can take from the enemy will be a neutral he is mistakenly attacking although it is closer to you. This is a tricky business, because you must launch a counter-attack to arrive one turn after him. If you launch it too soon, you will fight the neutrals and him. Sometimes this means waiting a bit before launching the counter-attack, but if you are waiting it is important not to expend those ships on another purpose such as colonizing a neutral or centralizing. So the ships you intend to send later should be earmarked and left in place.
A tricky case appears to be an enemy planet that you can take if the opponent waits for the turn after you attack to reinforce, but can't take if he launches reinforcements simultaneous with your attack. I advocate taking the most desirable such planet and launching every free ship you have for the task. This will be a good way to debug the calculation of "free ships" you made in the defense phase. If you were off by one, some opponent will probably teach you. 
Any free ships that were superfluous and/or inadequate for defense, and then also superfluous and/or inadequate for conquering enemy planets can then be allocated to conquering neutrals, ordered in preference by some one of the formulas that have been suggested.
Any free ships which were too little/too much for defense, attack, or colonization, should be centralized, perhaps. Alternatively they could be accumulated for a specific objective, such as colonizing and/or attacking a planet at a later date. I don't at all approve of behavior I see from some bots of launching a few ships at a target, too few to take it, and then launching more later. The neutral planet is not colonized any sooner because some ships got there first. An enemy that is not conquered is made more efficient by the fact that your ships are in the air and his aren't If all the necessary ships had arrived simultaneously, it would simply have delayed committing troops until the last possible moment for changing one's mind, maximizing flexibility. So maybe we will need a new heuristic for free-free-free ships to determine what goal they should be saved up for.
My guess is that before working out a better strategy than this, it would pay to make sure you can execute this simple strategy perfectly, i.e. with excellent calculations for ships necessary to defend and attack. One should first be asking whether the algorithm thought it needed more/less for defense/attack than it actually did, and get darned good at that, before tweaking the relative priority of objectives and strategizing in more complex ways. Tactics is the lowest-hanging fruit.
P.S. I hope all this babbling is helpful. I trust you to ignore all of it that is not helpful. 
|
| « Last Edit: Sep 17th, 2010, 2:15am by Fritzlein » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Google AI Contest Galactic Conquest
« Reply #63 on: Sep 17th, 2010, 1:36am » |
Quote Modify
|
I just replayed this game between the top two players on dhartmei's server. An opening move of taking the three planets closest to home would have beaten either of those bots, because both incorrectly attacked the central planet. On our second turn, we could have sent all our remaining troops to the middle to take it from him the turn after he depleted himself fighting neutrals. It seems that the general plan of being conservative, waiting for the enemy to over-extend, then hitting him with full force, might be good enough to get a bot past all the current opponents.
|
|
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: Google AI Contest Galactic Conquest
« Reply #64 on: Sep 17th, 2010, 1:56am » |
Quote Modify
|
on Sep 17th, 2010, 12:17am, Fritzlein wrote:
I'm not sure about that. If I am calculating correctly, map 30 has the home worlds 5 apart. That means each player could use 25 ships for something else and still be in no danger of losing the home planet. There is only one planet on the map that can be taken for so little, and it happens to be distance 14 from us and distance 14.002 = 15 from him. Therefore we can send 21 ships to it, and if he tries to take it from us, we match him ship for ship with a one-turn lag, so our reinforcements arrive simultaneous to his attack.
Sending ships away from the center give the opponent more freedom, because now he can send off 25+21=46 ships without losing his home world. But there are no neutrals that can be conquered for just 46, except his symmetrical planet for 21.
I believe, therefore, that the only correct move in the opening of map30 is to take the cheapest neutral planet way on the edge of the board. However, if both players do this, it might not break the stalemate. One player who uses the production from the neutral to attack the opposing homeworld may force an equal reinforcement that leaves each player with only 30 free ships, not enough to take a second neutral.
Extrapolating this example, every game is theoretically drawn unless the homeworlds are far enough apart or the neutrals are cheap enough and near enough. A symmetrical player-vs.-player combat with no colonization should always be drawn. It is only when the players must make decisions about ships vs. growth (i.e. fighting vs. colonization) that there is room for strategy. |
|
It seems to me 30 is more tricky opponent could sent more ships to the attacked planet than you ... of course 46 on 2nd turn ... So you must at first wait several turns to have enough ships to hold the planet long enough to pay back.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Google AI Contest Galactic Conquest
« Reply #65 on: Sep 17th, 2010, 2:10am » |
Quote Modify
|
on Sep 17th, 2010, 1:56am, Hippo wrote:| It seems to me 30 is more tricky opponent could sent more ships to the attacked planet than you ... of course 46 on 2nd turn ... So you must at first wait several turns to have enough ships to hold the planet long enough to pay back. |
|
No, if he sends 46 on the second turn, we reinforce with 36 on the third turn. Since we are one unit closer, our 36 arrive at the same time as his 46. Plus we had two turns of growth for 10 more ships, so his whole attack fails. This is very solid and reliable, since we will always have enough free ships to reinforce the turn after he attacks.
Even if he was psychic and sent 46 ships on the first turn to the planet where we sent 21, we could reinforce with 41 on the second turn and still be guaranteed control of the planet.
It doesn't get tricky until the planets are equidistant. Then there is a benefit to being psychic, but for the non-mind-readers, being second to attack is better unless the troops on the equidistant neutral are less than its growth rate.
|
|
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: Google AI Contest Galactic Conquest
« Reply #66 on: Sep 17th, 2010, 2:29am » |
Quote Modify
|
on Sep 17th, 2010, 2:10am, Fritzlein wrote:
No, if he sends 46 on the second turn, we reinforce with 36 on the third turn. Since we are one unit closer, our 36 arrive at the same time as his 46. Plus we had two turns of growth for 10 more ships, so his whole attack fails. This is very solid and reliable, since we will always have enough free ships to reinforce the turn after he attacks.
Even if he was psychic and sent 46 ships on the first turn to the planet where we sent 21, we could reinforce with 41 on the second turn and still be guaranteed control of the planet.
It doesn't get tricky until the planets are equidistant. Then there is a benefit to being psychic, but for the non-mind-readers, being second to attack is better unless the troops on the equidistant neutral are less than its growth rate. |
|
OK so 30 was not that tricky But at least it demonstrated the principle.
Suppose the only possible neutral planet growth rate is 1 not 5. In that case scenario when you must wait for proper turn would be optimal. As you had to reply with 43 ships to his 46, on turn 3 enemy sends nothing so no reaction and on turn 4 next 43 ships are sent so reinforcement of 41 is required on turn 5. Next 41 attacking ships on turn 6 and 39 reinforcements on turn 7 required.
This needs 21+43+41+39>135 ships. So attacking player would hold the planet for 7 turns with return 7 and investment 20.
|
| « Last Edit: Sep 17th, 2010, 2:31am by Hippo » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Google AI Contest Galactic Conquest
« Reply #67 on: Sep 17th, 2010, 2:33am » |
Quote Modify
|
on Sep 17th, 2010, 2:29am, Hippo wrote:OK so 30 was not that tricky But at leat it demonstrated the principle.
Suppose the only possible neutral planet growth rate is 1 not 5. In that case scenario when you must wait for proper turn would be optimal. As you had to reply with 43 ships to his 46, on turn 3 enemy sends nothing so no reaction and on turn 4 next 43 ships are sent so reinforcement of 41 is required on turn 5. Next 41 attacking ships on turn 6 and 39 reinforcements on turn 7 required.
This needs 21+43+41+39>135 ships. So attacking player would hold the planet for 7 turns with return 7 and investment 20. |
|
Ah, very good. I didn't realize the high growth rate was required to make the plan pay off. It seems everything about this game is more complicated than it appears. I think Janzert can rest assured that it is deep enough to survive the scrutiny of the contest as well as Tron survived it.
|
|
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: Google AI Contest Galactic Conquest
« Reply #68 on: Sep 17th, 2010, 3:05am » |
Quote Modify
|
So on 30 with 1 grow rate on neutral planet one should wait several ... well defined number of turns.
But if nothing happens till then the rock-scissor-paper again appears (not calculated).
You can chose where to sent the 21 troops ... if opponent does expected attack, this increases his stock need by 21 troops so he probably loses the planet one turn earlier than he expects ... losing 2 ships to his expectation.
But with stalemate winning by 2 is good enough.
Oh wait it is not by 2, the planet is lost forever.
Yes this is very risky counterstrategy as waiting one more turn leads to much higher victory.
But again in stalemate the size of victory does not matter.
It just demonstrates that the strategy does not dominate all remaining.
So send to yours, send to enemies, do nothing seems to be correct options for turn X. I don't think attacking both neutrals on turn X could be helpful, but I could be wrong.
Yes attacking both loses to attacking opponent only as well as to do nothing. While attacking opponent's loses only to do nothing.
Attacking yours wins against do nothing (by 1 ship).
|
| « Last Edit: Sep 17th, 2010, 3:28am by Hippo » |
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Google AI Contest Galactic Conquest
« Reply #69 on: Sep 17th, 2010, 9:13am » |
Quote Modify
|
on Sep 17th, 2010, 1:36am, Fritzlein wrote:| I just replayed this game between the top two players on dhartmei's server. An opening move of taking the three planets closest to home would have beaten either of those bots, because both incorrectly attacked the central planet. On our second turn, we could have sent all our remaining troops to the middle to take it from him the turn after he depleted himself fighting neutrals. It seems that the general plan of being conservative, waiting for the enemy to over-extend, then hitting him with full force, might be good enough to get a bot past all the current opponents. |
|
This game was played on map11.
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/
|
| « Last Edit: Sep 17th, 2010, 9:40am by jdb » |
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: Google AI Contest Galactic Conquest
« Reply #70 on: Sep 17th, 2010, 10:22am » |
Quote Modify
|
map30 with slow grow ratio of the only distant planet to conquer is even much more interesting:
On each turn expanded player must sent reinforcements the rock-scissors-paper appears. Opposing player could sent ships at the same time winning grow ratio of distant planet ships if expanded player sent reinforcements.
If the reinforcements were not sent, opposing player loses his home and the game in short time.
As this includes repeated rock-scissors-paper games, the randomized choice wins against static one in long term perspective. ... If k of the l 5 r-s-p games should be won, best choice seems to be to chose randomly k numbers from 1 to l+1 and risk only on corresponding r-s-p's. ... hmmm even this r-s-p games are not so easy.
|
| « Last Edit: Sep 17th, 2010, 10:27am by Hippo » |
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: Google AI Contest Galactic Conquest
« Reply #71 on: Sep 17th, 2010, 11:48am » |
Quote Modify
|
on Sep 17th, 2010, 12:31am, Fritzlein wrote:
Let d be the separation distance, S your ships, G your growth, s his ships, g his growth. Then he needs S+D*G+1 to beat you and needs to leave S+G-1-(D+1)*g to stop a counter-attack next turn, so you should be OK as long as s < 2S + (D+1)*(G-g), or equivalently S > (s - (D+1)*(G-g))/2.
|
|
Situation of two home planets without fast support is following: X on one Y on the other. If |X-Y|<=d*g both planets are safe. Otherwise suppose X>Y+d*g.
There is following scenario how deterministicaly win. With possibilities to dalay and counterpossibilities to speed up the decay.
Stronger player sents Y+d*g+1 ships to weaker home (with high probability). Weaker player waits (with higher probabilty or sents all ships against stronger player).
Best case for weaker is both player waits, second best is both are sending ships.
Quickly losing is only weaker sends and Slowly losing is only stronger sends.
Suppose stronger player goes for best worst case so he sends the ships, while weaker sents as well.
After d turns both planets changed owners, but stronger player let grown ships at home while weaker player sent them to air (d*g ships regularly spreat).
(If weaker player waited, he loses one turn so 2*g ships due to it, if weaker player is not strong enough he fails to conquer)
The r-s-c scenario repeats, but now waiting for stronger player is even worse. So suppose for ease he sents ships immediately back as well as weaker player.
Now after d turns there are 2d*g weaker player ships in the air. ... After k exchanges weaker player has k*d*g ships in the air. For k high enough his amount of available ships does not suffice to conquer the opponent's home. (The home fails several turns later as the ships arrive in bunch of k*g's, but he lost 2*gx ships for x days delayed recapture.)
So after next d turns the situation is much worse and recapturing is delayed more and more until it is not possible at all.
In normal game time could be important so r-s-p subgames could be important even there.
|
| « Last Edit: Sep 17th, 2010, 1:01pm by Hippo » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Google AI Contest Galactic Conquest
« Reply #72 on: Sep 17th, 2010, 12:36pm » |
Quote Modify
|
on Sep 17th, 2010, 11:48am, Hippo wrote:Situation of two home planets without fast support is following: X on one Y on the other. If |X-Y|<=d*g both planets are safe. Otherwise suppose X>Y+d*g.
There is following scenario how deterministicaly win.
[...]
In normal game time could be important
|
|
I agree that when X > Y+d*g the stronger player can eventually conquer both worlds. The strategy of trading planets is not a true defense, only a delaying tactic.
I also agree that time is important in a normal game, specifically that a delaying tactic can be a game winner, because the player with the fewer ships will often have the higher growth rate. Indeed, it might be the case that one player explicitly left his planet vulnerable for the sake of that higher growth rate, knowing that the losses from the planet-on-planet fight would be less than the gain from colonization. On map88 this is why ACD > H (apparently).
|
| « Last Edit: Sep 17th, 2010, 12:37pm by Fritzlein » |
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: Google AI Contest Galactic Conquest
« Reply #73 on: Sep 17th, 2010, 1:10pm » |
Quote Modify
|
OK, what is good to know is how fast the weaker home planet is lost in the worst case scenario for the stronger player. In the full game complexity it would be staring point for other calculations. May be the average scenario with all r-s-p games played would be even beter approximation for close games.
May be the time when the home planet is lost definitively is not the final measure, but rather the difference D in turns the home planets were held ... as that means 2D*g ships imballance.
Of course higher total grow ratio of defender could mean he produces more ships than the imbalance but if it's less than 2g and ships are not back fast enough to recapture any of starting planets, the final bigger grows of attacker would probably dominate.
As analysis of 88map with AC<ACDE<ACH because of comparison of lost ships due to delayed expansion compared to gained ships from opponent's home this really needs good estimates.
|
| « Last Edit: Sep 17th, 2010, 1:22pm by Hippo » |
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: Google AI Contest Galactic Conquest
« Reply #74 on: Sep 17th, 2010, 2:17pm » |
Quote Modify
|
Mc Leopold centralizes his forces much betterthan his opponents ... but has more ships in air than required ... sending in almost opposite directions.
|
| « Last Edit: Sep 17th, 2010, 2:22pm by Hippo » |
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print