Author |
Topic: Google AI Contest Galactic Conquest (Read 22528 times) |
|
Janzert
Forum Guru
Arimaa player #247
Gender: 
Posts: 1016
|
 |
Google AI Contest Galactic Conquest
« on: Sep 12th, 2010, 10:26pm » |
 Quote  Modify
|
I know there were a few people here that participated in the last Google AI contest based around Tron lightcycle racing. They have now started a new one that will run through November based on the game GalCon. The contest home page is at http://ai-contest.com/.
I'm not completely convinced this game has as much depth as the previous contest but it should be quite fun. There's also been quite a few of technical difficulties at the start of the contest, but hopefully that will smooth out soon.
Janzert
|
|
 IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Google AI Contest Galactic Conquest
« Reply #1 on: Sep 13th, 2010, 12:18am » |
Quote Modify
|
In the Tron contest, a few people demonstrated situations where the simultaneity of moves mattered, thus proving that trees built in typical turn-taking fashion can produce incorrect results even when the problem is small enough to search exhaustively. It is a bit disturbing to know that the algorithm you are using, even if given infinite time to complete, might output the wrong move. Nevertheless, in practice, alpha-beta searchers dominated, and not a single contestant reported performance gains from using proper game theory.
My immediate intuition for Planet Wars is that lookahead is useless. The branching factor, instead of being 3 as in Tron, is enormous. On the first turn of the game shown in the video, 50 ships must be allocated between 23 planets, which I believe means 73c23 = 5.7 x 10^18 legal first moves. I expect that the branching factor grows exponentially in the number of ships.
Second, even if the number of moves under consideration can heuristically be reduced to a manageable size, I expect game theory to be quite relevant. For example, when a planet is equidistant from both players' ability to reinforce/attack it, it would seem optimal to launch exactly one more ship than the opponent does, resulting in controlling a planet with only one ship, or contrariwise to launch no ships at all while the opponent sends many, resulting in him wasting many ships to control a single planet while you can divide your forces and control several planets with the same resources. This very probably means that a mixed (randomized) strategy is optimal.
To allocate CPU, one might first get an approximate idea of how large a game grid full of random evaluations can be solved in half the available time (1 second again?), then focus on using the first half of the time to select approximately that many strategies for each player and evaluate the result of each pair of strategies to fill in a grid for evaluation. As a first pass, I would rate iteration (extensive form) as complete overreach and instead focus all thoughts on static evaluation of the present move only, for both players (bimatrix form).
I believe there is no guaranteed polynomial-time algorithm to solve a game grid. I'm not sure how to deal with this. If the average solution time is pretty bad, i.e. near the worst case, then it might pay to limit the number of pure strategies so that the worst case is still doable. On the other hand, if the average case is much better than the worst case, it might pay to solve a small bimatrix game, then double the number of pure strategies allowed and try to solve again, etc. Or if solving game grids is simply too limiting, the best approach might be to chuck game theory and focus on static evaluation of moves for just one player, ignoring the opponent entirely.
Perhaps Planet Wars is not as deep as Tron, but we don't know until we try, do we? It turned out that the top Tron bots played far from optimally on large, irregular boards, despite all the effort that went into the contest. Therefore, I infer that Tron is deep. But is Planet Wars shallow? Is there an easy way to bust it? Will all serious competitors rapidly arrive at the same strategy? If so (since the boards appear symmetrical) every game will be drawn or decided quickly with equal winning chances like some huge rock-scissors-paper throw. My own expectation, however, is that the huge branching factor will keep Planet Wars far from being busted, such that better bots substantially outplay the weaker bots even among top bots at the end of the contest.
Janzert, if you are up for another collaboration, so am I. If you are ready for my thoughts on the evaluation function, you know my e-mail. 
|
| « Last Edit: Sep 13th, 2010, 12:21am by Fritzlein » |
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Google AI Contest Galactic Conquest
« Reply #2 on: Sep 13th, 2010, 8:47am » |
Quote Modify
|
I have a feeling my arimaa work will be on hold for a while.
The best bots, so far, still make moves that are clearly wrong. So there is still room for improvement.
During the opening phase, it should be possible to play pretty close to perfect. When the starting planets are close together it gets harder, since one can attack each other right away.
Once all the choice planets are taken, the number of strategies goes way up. Some advance planning will be required here.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Google AI Contest Galactic Conquest
« Reply #3 on: Sep 13th, 2010, 9:34am » |
Quote Modify
|
on Sep 13th, 2010, 8:47am, jdb wrote:| The best bots, so far, still make moves that are clearly wrong. So there is still room for improvement. |
|
Yes, I played through some games by the top bots, and I am confident they could be beaten by a good move-choosing heuristic that doesn't even consider the opponent's options. That is to say, no game theory required to top the current list. Of course, for Tron it was also true at the beginning that one could top the list with no alpha-beta search, because the competition was so bad, but it got much tougher toward the end of the contest. The top of the rankings was a rapidly-moving target.
One rule of thumb seems so obvious as to hardly be worth mentioning, except that even currently top bots violate it, is to never send fewer ships against a neutral planet than necessary to conquer it, and usually send only one more than necessary to conquer it.
A second heuristic for the opening: never send ships to a neutral planet nearer to the opponent than to you. He can sent a fleet timed to arrive one turn after your fleet to take the planet away from you after you have gone to the expense of wiping out the neutral ships. This is a subset of the more general (but harder to apply) rule of not taking a neutral planet if you won't have time to regrow as many ships as you lost taking it before the enemy retakes it from you.
A third heuristic would be to centralize fleets. It gives you more options, in particular the option to attack/defend against the opponent rather than fighting neutrals. When you fight the other player, you are guaranteed to come out even on casualties, but the victor has a double swing in growth rate, i.e. you not only gain the growth rate of the conquered planet, the opponent loses that growth rate. This is compared to taking over a neutral planet where it adds to your growth rate but the opponent loses nothing.
A strong opening move would seem to be ranking cost/benefit of taking over planets nearer to you than to the opponent and attacking as many of them as possible. Some players seem concerned about leaving their home planet undefended, but given the growth rates and distances, the opponent has to send nearly his entire fleet to take even an undefended home planet; on many boards the neutral planets are close enough to help grow a new home defense before an attack would arrive.
This suggests a fourth principle, that having fleets in the air has an opportunity cost that makes staying at home and taking short trips more desirable once there is contact between the players, but this is probably already getting unnecessarily sophisticated. It seems one could beat the present top bots with just the first three heuristics and a strong opening move, with no thought given to the simultaneity of moves, never mind to tree search.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Google AI Contest Galactic Conquest
« Reply #4 on: Sep 13th, 2010, 9:58am » |
Quote Modify
|
I see that even though the main site is having issues, you can test against other bots here: http://www.benzedrine.cx/planetwars/
That server was a late but important addition for Tron. In this contest I expect it to be invaluable, possibly the epicenter of all serious activity, because submissions to the main site just end up playing a lot of super-weak opponents that don't tell you anything about the strength of a strong bot.
I played through a game between top bots on this server, and it was of much, much higher quality than the games I played through on the contest site. See http://www.benzedrine.cx/planetwars/canvas?game_id=1284388837|bartw e.5.1|ademar I'm no longer sure about how trivial it would be to top the list with a few simple heuristics.
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Google AI Contest Galactic Conquest
« Reply #5 on: Sep 13th, 2010, 12:04pm » |
Quote Modify
|
on Sep 13th, 2010, 9:58am, Fritzlein wrote:I see that even though the main site is having issues, you can test against other bots here: http://www.benzedrine.cx/planetwars/
That server was a late but important addition for Tron. In this contest I expect it to be invaluable, possibly the epicenter of all serious activity, because submissions to the main site just end up playing a lot of super-weak opponents that don't tell you anything about the strength of a strong bot.
I played through a game between top bots on this server, and it was of much, much higher quality than the games I played through on the contest site. See http://www.benzedrine.cx/planetwars/canvas?game_id=1284388837|bartw e.5.1|ademar I'm no longer sure about how trivial it would be to top the list with a few simple heuristics. |
|
In the above game, red was doing fine until around turn 20(ish). Then he attacked the enemy planet on the far side of the board. That had zero chance of taking the planet, and just delayed taking over neutral planets.
Blue attacked the enemy even earlier, around turn 5(ish). I doubt this was the optimal play given the starting planets are so far apart.
The winner is almost always the one with the highest growth rate. At the start, if the enemy is far away, just try and maximize the growth rate. If the enemy is close, its a lot trickier. Tonight I'll try and find a map where they start close together.
I agree with your heuristics.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Google AI Contest Galactic Conquest
« Reply #6 on: Sep 13th, 2010, 3:54pm » |
Quote Modify
|
on Sep 13th, 2010, 12:04pm, jdb wrote:| The winner is almost always the one with the highest growth rate. At the start, if the enemy is far away, just try and maximize the growth rate. If the enemy is close, its a lot trickier. |
|
Agreed. I think some early bots are not nearly aggressive enough. On the other hand, when the top bot loses, it is often from being too aggressive, specifically from trying to take a neutral planet that it can't hold from the enemy. Purely trying to maximize the growth rate by taking neutral planets leaves one with temporarily fewer ships than the opponent, and therefore potentially vulnerable to having weak planets that one owns taken over cheaply by the enemy. There appears to be a genuine tradeoff between growth rate and fleet size, which might be where the depth of Planet Wars lies.
My hueristic was to never attack a neutral planet that is closer to the enemy than it is to you. In fact taking a neutral planet closer to the enemy than to you could be correct if the enemy couldn't retake it from you because they didn't have enough ships, and also if launching the invading force didn't make some other planet vulnerable. But when the players are just starting out in opposite corners with equal fleet size, equal growth rate, and symmetrical setup, I don't think the heuristic will often fail.
As you say, when the players are closer together it is trickier.
Quote:In the above game, red was doing fine until around turn 20(ish). Then he attacked the enemy planet on the far side of the board. That had zero chance of taking the planet, and just delayed taking over neutral planets.
Blue attacked the enemy even earlier, around turn 5(ish). I doubt this was the optimal play given the starting planets are so far apart. |
|
Good observations. I'm trying to think how to stretch this into a general rule about whether to attack a neutral planet, attack an enemy planet, or stand pat.
Perhaps one way to look at it is to make a rudimentary evaluation of how many of the ships currently on a planet need to stay on it to make it safe. That could be calculated quickly in terms of fleets already launched, ships still on planets on both sides, distances away, and the growth rate of the planet itself. (Probably adding in growth rates of other planets makes it too complicated.) One might determine that one can launch, say, 27 ships without making the planet unsafe.
If those "free" ships are sufficient to take over an enemy planet, that almost has to be the correct move. You kill as many ships as you lose, increase your growth rate, and decrease his growth rate.
If you can't take over an enemy planet, next one could look for neutral planets to take over. I believe the calculation should be how many turns the planet can be held before the enemy can take it. If you can grow back you investment in ships before losing it, it is probably correct to take it.
I can imagine a situation where neither player has enough free ships to do either of these things, e.g. taking over a neutral planet will leave the home planet vulnerable. Perhaps in that case both players must stand pat and eventually declare the game a draw.
What's going to be tricky is cases where one doesn't have enough "free" ships but aggression is still correct. For example, conquering a neutral planet might allow your home world to be taken, but the extra growth rate might be just sufficient for you to retake it, or something like that.
Using an insufficient force to attack a planet the other player controls is probably wrong most of the time, because of the opportunity cost; your ships could have been doing something more constructive. However, I can imagine it being correct given simultaneous moves when the opponent is being aggressive and potentially leaving owned planets weak.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Google AI Contest Galactic Conquest
« Reply #7 on: Sep 13th, 2010, 4:20pm » |
Quote Modify
|
on Sep 13th, 2010, 12:04pm, jdb wrote:| Tonight I'll try and find a map where they start close together. |
|
Here's a map where they start close together.
As of turn 12, deepblue had the higher growth rate and, I believe, should have won from there, but on turn 21 vortex launched an attack that provoked deepblue into a melee in which it got outplayed. If deepblue hadn't responded to the attack with a counter-attack, but had instead merely protected all of its home planets, deepblue's higher growth rate would have won the war.
This looks like a very complicated tactical fight where my heuristics will be pretty useless.
In this game, both bots colonized the same first five neutral planets at exactly the same speed using exactly the same force. From that point their paths diverged, however, and the principle of centralizing ships in order to fight the opponent won out over the principle of attacking additional neutral planets. I note that the extra ships needed to be sent toward the middle even before the planets there were taken over.
|
| « Last Edit: Sep 13th, 2010, 4:37pm by Fritzlein » |
IP Logged |
|
|
|
Rednaxela
Forum Senior Member
Arimaa player #4674
Gender:
Posts: 34
|
|
Re: Google AI Contest Galactic Conquest
« Reply #8 on: Sep 13th, 2010, 6:24pm » |
Quote Modify
|
Hmm... this game seems to me to be a more pure "combinational optimization" puzzle than most competitive games...
My current feeling is that a good approach would be looking into algorithms that give good approximate solutions to other combination optimization problems, like the traveling salesman problem. One class of algorithms that give very good results for the traveling salesman problem is known as "Ant colony optimization", which I think is general enough that it would perhaps be used in this ruleset effectively.
Hm.... this may just distract me from the Arimaa bot I've started...
|
| « Last Edit: Sep 13th, 2010, 6:55pm by Rednaxela » |
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Google AI Contest Galactic Conquest
« Reply #9 on: Sep 13th, 2010, 7:01pm » |
Quote Modify
|
on Sep 13th, 2010, 3:54pm, Fritzlein wrote:
Perhaps one way to look at it is to make a rudimentary evaluation of how many of the ships currently on a planet need to stay on it to make it safe. That could be calculated quickly in terms of fleets already launched, ships still on planets on both sides, distances away, and the growth rate of the planet itself. (Probably adding in growth rates of other planets makes it too complicated.) One might determine that one can launch, say, 27 ships without making the planet unsafe.
If those "free" ships are sufficient to take over an enemy planet, that almost has to be the correct move. You kill as many ships as you lose, increase your growth rate, and decrease his growth rate.
If you can't take over an enemy planet, next one could look for neutral planets to take over. I believe the calculation should be how many turns the planet can be held before the enemy can take it. If you can grow back you investment in ships before losing it, it is probably correct to take it.
I can imagine a situation where neither player has enough free ships to do either of these things, e.g. taking over a neutral planet will leave the home planet vulnerable. Perhaps in that case both players must stand pat and eventually declare the game a draw.
What's going to be tricky is cases where one doesn't have enough "free" ships but aggression is still correct. For example, conquering a neutral planet might allow your home world to be taken, but the extra growth rate might be just sufficient for you to retake it, or something like that.
Using an insufficient force to attack a planet the other player controls is probably wrong most of the time, because of the opportunity cost; your ships could have been doing something more constructive. However, I can imagine it being correct given simultaneous moves when the opponent is being aggressive and potentially leaving owned planets weak. |
|
The following information can easily by calculated for all planets within the one second allowed. For each individual planet all incoming fleets can be located. The "future" of the planet can be simulated given the incoming fleets. The maximum number of troops that a player can get to a planet at each future time step is also quick to calculate. It would be easy enough to only allow "free" troops to participate in the attack. Once the maximum attack is known for each player, it is also possible to simulate the "future" if both players attack with everything.
As you mentioned in your posts, the question boils down to where to send the troops.
1) Defend your own planets. They are worth 2*growthrate. Even losing a planet for a handful of steps is costly. Is there ever a situation where it is correct to give up a "core" planet? ie. On a symmetric map, a planet on your side of the board.
2) Attack an enemy planet, only if it can be captured. They are also worth 2*growthrate. Not sure how much it matters if it can be recaptured, if its an enemy "core" planet.
3) Capture a neutral planet. As you said, at a minimum it needs to be held long enough to get the troops back. The order the planets are taken is also important. If it takes more than 100 troops to get all the planets, then some form of calculation needs to be done to decide what order to take them in. The game ends at turn 200. So assuming the enemy doesn't attack (just a minor assumption!!) the best way to take the planets would maximize your troop count on move 200. This also assumes a symmetric planet layout. I am not sure how to handle planets that are equal distance from each starting world. They are likely very important.
Quote:
Here's a map where they start close together.
As of turn 12, deepblue had the higher growth rate and, I believe, should have won from there, but on turn 21 vortex launched an attack that provoked deepblue into a melee in which it got outplayed. If deepblue hadn't responded to the attack with a counter-attack, but had instead merely protected all of its home planets, deepblue's higher growth rate would have won the war.
This looks like a very complicated tactical fight where my heuristics will be pretty useless. |
|
This looks complicated. I'll have to take a longer look at this game.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Google AI Contest Galactic Conquest
« Reply #10 on: Sep 13th, 2010, 9:24pm » |
Quote Modify
|
on Sep 13th, 2010, 7:01pm, jdb wrote:| The following information can easily by calculated for all planets within the one second allowed. For each individual planet all incoming fleets can be located. The "future" of the planet can be simulated given the incoming fleets. The maximum number of troops that a player can get to a planet at each future time step is also quick to calculate. |
|
It seems that deepblue, the current leader on dhartmei's server, is winning by virtue of calculating this vision of the future more accurately than its opponents. Often it launches exactly enough ships toward a friendly planet to arrive on the exact turn needed to retain control of the planet with zero ships left. This extreme efficiency allows it to spread out more and try to control more planets.
Quote:| It would be easy enough to only allow "free" troops to participate in the attack. |
|
I don't know whether this is a good idea, but doing the opposite (i.e. launching attacks that left its own planet vulnerable) was deepblue's downfall in the melee I linked.
Quote:| Is there ever a situation where it is correct to give up a "core" planet? ie. On a symmetric map, a planet on your side of the board. |
|
Yes, I think it can be OK to leave a planet with a thin defense when it would be too costly for the opponent to attack it. Perhaps they would have to launch such a large fleet that would be in the air for such a long time, you would devastate him in spite of losing a home planet. However, I would not worry about the damage from playing it too safe until I saw my bot actually start losing because of it.
Quote:| The game ends at turn 200. So assuming the enemy doesn't attack (just a minor assumption!!) the best way to take the planets would maximize your troop count on move 200. |
|
Fortunately for the depth of Planet Wars, it does not seem to collapse into each player optimizing colonization on his own side of the galaxy. I'm pretty sure that a great colonizer but bad fighter will be beaten by a pretty good colonizer that is a good fighter. Combat apparently makes the capture of additional neutral planets late in the game essentially irrelevant, because troops are more needed to fight the opponent on non-neutral planets. I haven't seen any game yet that wasn't over by elimination before move 200, which means the winner has been decided by move 100 at the latest.
Quote:| I am not sure how to handle planets that are equal distance from each starting world. They are likely very important. |
|
I am guessing that the central planet and all other planets equidistant from the players are a trap to be avoided until symmetry has been broken and one player has much more power in the middle of the board. The correct strategy is to wait for the other player to launch a wasteful attack against the equidistant neutral planet, and one turn after that launch an overwhelming force to wipe out what he has left.
Deepblue has been incorrectly going after equidistant planets, and getting away with it by launching a small reinforcement the turn after. This means that the opponent who is (correctly) waiting to strike second but (incorrectly) sending the bare minimum to take over the planet if it is not reinforced is actually losing out because of the simultaneous arrival of reinforcements.
The way I figure, if the central planet has 30 neutrals on it and he shoots 31 ships at it to take it over, on the next turn I'm not going to send 5 ships to clean up his 1 ship plus growth, because then any amount of reinforcement will defeat me. Instead I'll send 31 ships of my own to take the planet away from him. If the situation was symmetrical before, I should have as many ships free to send to the center as he does, right? In fact, I should have more free ships to send than he has, because all the ships he threw in the air are no longer endangering the planets I control. In the rare case that he reinforced with enough to neutralize my big counterstrike, say another 30 ships the turn after, I'll send another 35. I should be able to outgun him because he sacrificed 30 ships fighting the neutrals and will only hold the planet for a couple of turns before losing the reinforcement war, thus regaining fewer than he sacrificed.
That's just my initial babbling, though. One would have to see how it actually worked in practice.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Google AI Contest Galactic Conquest
« Reply #12 on: Sep 14th, 2010, 11:41am » |
Quote Modify
|
on Sep 14th, 2010, 8:18am, jdb wrote:
Yes, I think Red was correct to come towards the middle before idiotically sending all ships back to his home planet. It appears to me too that Red had a winning attack against blue without ever conquering a second neutral planet, or at least not until after liberating Blue's two central planets.
Quote:
Agreed. It appears that Blue had enough forces to defend his central planets despite having diverted ships to take one more neutral planet than red. The attack against Red's planet was suicidal. Note that Blue launched his fleet while Red's was still in the air, not on turn 7 but on but on turn 4. The idea was to counter-attack the planet after Red depleted forces fighting the neutrals. But this only works against planets that are closer to you than to the opponent, to prevent reinforcement from arriving simultaneously to your attack.
This suggests an additional heuristic that I didn't think of before: if you are going to attack an enemy planet, only attack the closest one. If you can't take the closest one, you can't take any.
It's hard to tell with all the fleets flying, but possibly even after that Red messed up to attack Blue rather than take a neutral planet to pull even on growth rate. Blue had enough ships to defend and prevent losing inner planets even temporarily, but he left those available ships sitting on outer planets. Leaving ships way behind the front lines is bad strategy, but the more egregious error was the terrible tactic of leaving ships on the home world even though they were readily available to fend off the attack that was in the air.
I expect Planet Wars to be like Arimaa in at least one respect: the lowest hanging fruit is tactics. Be content with rudimentary strategy until you are darned good at tactical calculation. It sucks to have the better position and lose the brawl.
|
| « Last Edit: Sep 14th, 2010, 11:41am by Fritzlein » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Google AI Contest Galactic Conquest
« Reply #13 on: Sep 14th, 2010, 11:46am » |
Quote Modify
|
on Sep 13th, 2010, 6:24pm, Rednaxela wrote:| Hm.... this may just distract me from the Arimaa bot I've started... |
|
Heheh. It would be awesome to have multiple contest entries from the Arimaa community!
|
|
IP Logged |
|
|
|
Tuks
Forum Guru
Arimaa player #2626
Gender:
Posts: 203
|
|
Re: Google AI Contest Galactic Conquest
« Reply #14 on: Sep 14th, 2010, 2:44pm » |
Quote Modify
|
how exactly do you use his server? i downloaded the "server" file but have no idea what to do next, the only option that seems to have the ability to execute a command is "get game" in the htdocs folder but when i initiate it using my mac terminal it just gives me an error message.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print