|
||||||||||
|
Title: Google AI Contest Galactic Conquest Post by Janzert on Sep 12th, 2010, 10:26pm 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 (http://www.galcon.com/). 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 |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 13th, 2010, 12:18am 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. :-) |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by jdb on Sep 13th, 2010, 8:47am 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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 13th, 2010, 9:34am on 09/13/10 at 08:47:46, jdb wrote:
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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 13th, 2010, 9:58am 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|bartwe.5.1|ademar I'm no longer sure about how trivial it would be to top the list with a few simple heuristics. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by jdb on Sep 13th, 2010, 12:04pm on 09/13/10 at 09:58:47, Fritzlein wrote:
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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 13th, 2010, 3:54pm on 09/13/10 at 12:04:14, jdb wrote:
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:
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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 13th, 2010, 4:20pm on 09/13/10 at 12:04:14, jdb wrote:
Here's a map where they start close together. (http://www.benzedrine.cx/planetwars/canvas?game_id=1284409358|deepblue|vortex.9) 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 (http://www.benzedrine.cx/planetwars/canvas?game_id=1284403419|deepblue|bartwe.4), 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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Rednaxela on Sep 13th, 2010, 6:24pm 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 (http://en.wikipedia.org/wiki/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... |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by jdb on Sep 13th, 2010, 7:01pm on 09/13/10 at 15:54:17, Fritzlein 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 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:
This looks complicated. I'll have to take a longer look at this game. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 13th, 2010, 9:24pm on 09/13/10 at 19:01:58, jdb wrote:
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:
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:
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:
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 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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by jdb on Sep 14th, 2010, 8:18am Here are some games where the starting planets are close. http://www.benzedrine.cx/planetwars/canvas?game_id=1284468368|shakey2-13|TracerBot11.1 On the opening move, blue sends his fleets everwhere. Red sends his troops towards the enemy. On turn 4, I think red could launch a winning attack? Its hard to tell, since the troops are covered by the planets. http://www.benzedrine.cx/planetwars/canvas?game_id=1284467476|TracerBot11.1|antimatroid1.3 Blue was doing great until turn 7, when he attacked the enemy planet. He had fewer troops in the area, so that attack had no chance. When the planets are close, it looks like one mistake can be fatal. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 14th, 2010, 11:41am on 09/14/10 at 08:18:23, 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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 14th, 2010, 11:46am on 09/13/10 at 18:24:31, Rednaxela wrote:
Heheh. It would be awesome to have multiple contest entries from the Arimaa community! |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Tuks on Sep 14th, 2010, 2:44pm 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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by jdb on Sep 14th, 2010, 3:00pm on 09/14/10 at 14:44:22, Tuks wrote:
This is a link to the forum thread about the server. http://www.ai-contest.com/forum/viewtopic.php?f=18&t=424 |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by chessandgo on Sep 14th, 2010, 3:03pm on 09/12/10 at 22:26:15, Janzert wrote:
Wow, just reading the rules this game seems a lot more diffcult to me than tron ... Not that I know anything about either game though :) Looks really fun in any case, I had never heard about it. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 14th, 2010, 6:31pm Sorry I have not read full the thread ... so may be all thoughts are already included. So basics: 1) From the long perspective who has higher growth wins. 2) Attacking opponent's plannet with small number of ships does not cause problems as it costs this number of ships both sides. So with higher production ratio there is no problem to do that. 3) Attacking neutral planets may be risky ... you must hold it long enough to produce So especially planets whose distance to opponent is at most one turn higher than our. For nearer planets one could sent sufficient amount to conquer and react to opponent's moves not to let him to conquer it. Bigger the difference safer to conquer it. 4) It's very important to look at the opponent's moves, especially conquering neutral planets to gain from badly invested ships. 5) When your base is far away from the perspective planets, it could be good to sent almost all your ships there as sending them further would be much faster. 6) Bunch of planets near one another is much more difficult to conquer as they could redistribute their ships in response to attacks. The growth ratio of the whole attacking and defending system should be taken into account. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by jdb on Sep 14th, 2010, 7:14pm on 09/14/10 at 18:31:59, Hippo wrote:
I believe one must hold the neutral planet long enough to get back all the invested ships. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 14th, 2010, 7:20pm on 09/14/10 at 19:14:38, jdb wrote:
Oh yes, you are right :) silly me ... I both added the produced ships and subtracted them from opponent's ... |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Rednaxela on Sep 14th, 2010, 8:21pm Here are couple thoughts I've had which I don't think have came up yet: 1) If a planet of yours can get reinforcements in shorter notice than enemies can attack it, then don't bother leaving any ships on it at end of turn. - Justification: Freeing up the force for the "front lines" is valuable and there's no reason to waste any resources defending a planet that you can get reinforcements to quicker than the opponent can attack it. - Cautionary note: Be careful. Don't assume any allied planet can send reinforcements. Consider how many units the other planets can afford to spare (but include growth and anticipated arrivals in that) 2) Similarly, attacking an enemy planet which is closer to reinforcements than you are, should be a last resort. - Justification: It may not be as risky as a neutral planet, but it's useless unless you have either vastly superior numbers or are trying to imbalance a 'barricade'. Hmm... thinking about it some... It may be useful to calculate what I'd call "tiered quotas/budgets" for planets. For example, for every non-neutral planet, calculating the number of additional ships required to hold OR capture the planet: 1) Assuming the enemy doesn't send anything to it beyond what's already in flight 2) Assuming the enemy keeps sending a similar amount to what it has in the last few turns 3) Assuming the enemy sends as much as it can afford to send If the planet is one you can afford to send units from, or is an enemy planet you don't need to send more to, then the numbers could be negative. Based on those numbers, one should be able to tune a function to estimate "probability of holding/capturing" for a given number of ships you send (or if negative, remove). I think calculating both "worst case", "best case" and "reasonably expected case" are all valuable. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 15th, 2010, 1:39am I agree expect the attacking enemy issue. Attacking enemy means both players ship total is reduced by the same amount. Lesser that amount is, smaller are the possibilities. So with higer growth ratio you can attack enemy almost arbitrary. The only condition one should be afraid of is losing a planet so your grow ratio felt under opponents. So maintain safe amount required to defend your planets and to retake neutral planets on the frontier and sent excess ships to nearest valuable enough opponent plannet. Interesting case is starting position with opponents nearby and only expensive planets nearby. In that case sending all ships on opponent should be considered. This reduces the game to starting without ships so the growing ratio is the only factor. If opponent sent at most the number of ships created during the transport he won the openning as you didn't conquer his planet and you colonize neutral planets later than him. Of course if he sended ships to neutral planets whose you could not recapture. So you have 3 options ... full charge to opponent, small charge(s) to cheap safe neutral planet, higher charge to gain high growing ratio quickly (to safe neutral planets). It's stone, paper, scissors there what option to select. OK, the third option could be losing to both other in the case sending remaining ships to opponent's planet on 2nd turn leads to it's capture... of course the grow ratio of conquered neutral planets and the waste of time till they are conquered should be considered. There could be case sending all ships to bunch of connected neutral planets is better starting option. Uff it is nontrivial. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by jdb on Sep 15th, 2010, 8:31am So I need a method/formula for deciding which neutral planets to capture. This analysis will use map88.txt from the contest. The distance between the starting planets is 8 turns. The following planets can be captured first. They can also be held forever, even if the enemy attacks with everything. There is no point in sending troops to a neutral planet if it can't be held. Planet,Troops,Growth,Distance A,8,5,6 B,67,5,8 C,4,4,14 D,31,5,4 E,30,5,7 So there are 5 neutral planets that can be taken. There are only 40 troops available from the home planet, since the starting worlds are 8 steps apart. (The enemy could send 100 troops towards the home planet on turn 1, so 60 must remain to guard the home planet) The question is where to send the troops? One possible ranking is the total gain in troops the planet will produce in the remainder of the game. Currently the limit is 200 turns, but any large number will work. This gives the following formula: Fitness = (200 - Distance) * GrowthRate - Troops Troops Required is one more than the troops on the planet. Planet,Fitness,Troops Required A,962,9 B,893,68 C,740,5 D,949,32 E,935,31 So is the best move to attack A and E right away? |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 15th, 2010, 8:41am jdb@ I cannot find the map file, can you provide link please. I cannot find x,y coordinates. And they are generally important for the decision. Occupying planets near one another is more preferable than occuppying only single planet. I am not sure attacking C instead of E at the openning could be better. E could be attacked on 2nd turn and C would produce units earlier. Fitness giving total number of produced ships by a planet is not accurate ... Extreme case: suppose you could attack planet at distance 199, producing 1000000 units per turn. It would have the best fitness, but I would not invest to it. I would probably use sum of time ship is yours as the fitness (ship at time 200-i has value i). The counterexample would still hold, ... I have not read the exact rules ... who has most ships at the end wins. So another counterexample ... suppose all planets are in the line, the most distant is the 1000000 producing one ... You could conquer all planets on the way an achieve the last planet as well. Oops sorry, C,4,4,14 does not mean distance 4, troops 4, growth 4 :( ... as it is furthest than E the choice of E is better In A) case I would send all troops to enemy In B) case I would send to D only on first turn and if opponent didn't sent troops to me, I would attack A following turn. In C) case I would attack A only on first turn hoping to send all troops on enemy following turn In D) case I would attack A,D,E at the same time being vulnerable to both A) case and C) case attacks, but better than B) case. In E) case sent troops to D and to your enemy. If D itself would hold against enemy attacks you could sent 32 to D and 68 to enemy. In F) sent to D, A and rest to the enemy... I like the E variant especially in cases there is more resources around D than against home planet. on 09/15/10 at 08:31:06, jdb wrote:
I don't agree, your opponent could not be passive only so his troops must operate elsewhere so the condition could not be ... don't attack what could opponent gain with all his forces. But rather don't attack what would opponent capture with forces he likes to spent. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by jdb on Sep 15th, 2010, 10:30am on 09/15/10 at 08:41:45, Hippo wrote:
Download this file, and unzip it. The maps are in the maps directory. http://www.ai-contest.com/starter_packages/java_starter_package.zip Quote:
The winner is the side with the most ships after 200 turns. (Most of the time the game ends early because one side is reduced to zero.) Just to be clear, ship equals troops. The number of planets owned does not effect the winning condition. Quote:
This would depend on if the enemy could get to it. If they enemy could not get to it, then it would be a very good move. I am still reading over the rest of your interesting comments. Thanks for taking the time to make them. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Sconibulus on Sep 15th, 2010, 11:13am Couldn't you also take A and D? You'd leave yourself with 59 troops on the homeworld, but distance between worlds is 8, and distance to D is only 4, so you should be able to send the one remaining ship back to reinforce the homeworld up to 60 instantaneously upon capture, arriving simultaneously with the potential 100 enemies and resulting in a draw, with control maintained? Or is it possible I'm misunderstanding how the system works? :Edited to fix math |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by jdb on Sep 15th, 2010, 1:07pm on 09/15/10 at 11:13:17, Sconibulus wrote:
I was not sure how the game mechanics worked in this situation, so I made up two bots to simulate this situation. Your scenario is correct. The one ship makes it back at the same time the enemy arrives, resulting in retained control with zero ships. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 15th, 2010, 1:19pm Please, I have not seen exact rules. What happens when the distance is not integer. Are the distances rounded up or to nearest integer ... when calculating turn of arival? I probably forgot to write: I would consider some kind of cost of sending k ships to distance d equal k*d as the troops are not available for this period elsewhere. This is motivation for sending small amount of ships repeatedly to some destination when the time is not so important as flexibility (especially to nonneutral planets). Reorganizing troops such that they are near frontline is very important as it allows fast attacks to opponent planets such that he is not able react quickly enough not to lose the planet at least temporarily. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 15th, 2010, 1:43pm on 09/15/10 at 11:13:17, Sconibulus wrote:
Oh yes, you are right. But I am not sure if sending to A, to D and rest to the opponent is not even better :). And sending all created troops through base planet to opponent base planet afterwards. (except if path through base plannet is longer (rounded) than direct path. And if opponent's planet becomes yours continue flow through this planet to opponent's nearest one. Of course watch enemy actions and send enough ships not to lose any of your planets even for a turn. ... getting an opponent planet makes twice its grow ratio difference per turn ... taking neutral planet gives only once the grow ratio. Attacking several opponent planets without gaining any of them is much worse than sure gaining of one of them ... this is why concentration of ships is important. On the other side if the planets are supported one other, attacking either of them consumes the same number of ships so attacking nearest is preferable as it consumes opponent's ships earlier. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Oystein on Sep 15th, 2010, 2:01pm on 09/15/10 at 13:19:15, Hippo wrote:
http://ai-contest.com/specification.php |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 15th, 2010, 2:13pm on 09/15/10 at 08:31:06, jdb wrote:
Games never last 200 turns, so a formula looking that far ahead is bound to be weak. Long-term payoff will be weighted far too much relative to short-term sacrifice. My inclination is the complete opposite, namely to make the fitness function entirely which planet pays off first. PaybackTime = Distance + Troops/GrowthRate Whichever has the smallest PaybackTime is the best. Planet,Troops,Growth,Distance,PaybackTime A,8,5,6,7.6 D,31,5,4,10.2 E,30,5,7,13 C,4,4,14,15 B,67,5,8,21.4 Planets A and D are best to take. Note that even if we feel compelled to delay one turn to take D because we are concerned about home defense, D still pays back sooner than E. If Sconibulus' method of calculating planet safety is not too complicated to incorporate, that would be excellent in that it allows slightly more aggression. Insuring home safety might still be slightly more conservative than optimal, but barely so. For example, some bots are coded to empty out their home world on turn one to take as many neutrals as possible. Against such an opponent, we could send 65 ships on turn two to take their home world, a far better investment than attacking any neutral planet. We could get marginally dinged if we attack two neutrals while they attack three. Then they will still have enough for home defense and be ahead in the colonization race. However, on turn two we would sense the safety of our home world and launch against a third and fourth neutral planet, only one turn behind them. Optimal play is probably some sort of rock-scissors-paper situation where have some probability of not launching any colonization on turn one, just to keep them honest by having enough in reserve to attack their home world on turn two if they deplete it. However, I wouldn't really worry about optimal play at this point. Being one turn behind on colonizing one world when the opponent anticipates exactly what we will do is likely to be dominated (at the current level of bots) by not making the mistake of losing our homeworld and capitalizing on some opponents making the mistake of losing their homeworld. I have become convinced that it is most practical to leave the game theory of simultaneous moves out of it for the present. Having given a fairly simple fitness function, let me complicate it by suggesting that planets nearer the center of the board are better to take than planets on the periphery. We generally don't want to attack neutrals that are closer to the enemy than to us. However, if we colonize toward the center while the enemy colonizes away from the center, that brings more neutrals within our range while taking neutrals out of his range. The planets we control are safer, i.e. he is farther from attacking us, so our behind-the-lines ships are almost all free to move about. The planets he controls are less safe, because we have a central base for attacking them, so he is less free to move about. The strategic advantage of having more troops in the center is worth some sacrifice of not having the larger and/or faster-growing army. If the opponent's strength/growth is all on the edge, we will often be able to take central planets from him before his reinforcements arrive. I'm not sure what the proper balance between the two is, but I am confident it is important. It will be like chess: when you have centralized pieces, good things will happen later on, even if you can't see exactly how it will unfold at the time to you are moving pieces toward the middle. The second complication I want to propose is that my PaybackTime is only a relative measure. There also needs to be some sliding scale whereby we don't take even the neutral planet with the best PaybackTime, because our ships are better spent fighting the enemy than fighting neutrals. There needs to be a factor that indicates the urgency of fighting the enemy in the center. The hotter the central battle, the more we just send all troops there and ignore colonization entirely. I suspect most games will see a steady increase in this "hotness" factor, starting very cool when home worlds are far away, when colonization is everything, and gradually heating up to the point that fighting the enemy is everything. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 15th, 2010, 3:04pm on 09/15/10 at 13:43:56, Hippo wrote:
Your strategy (9 to A, 32 to D, 59 to enemy home) is exceedingly reckless. Suppose the opponent thinks, "I will wait one turn to see if my opponent is a complete maniac. Sure, I will lose a turn, but if he makes a bad move, I can crush him." Then on turn two your opponent has 105 ships to deploy. He sees what you have done. He knows that if he attacks your home planet, the maximum defense you can muster will be 45 from home planet growth, plus 6 returning from planet D. An attack of 52 beats you. For his home defense he will have 35 in growth, thus needing only 24 to stave off your attack. 105-52-24 = 28 ships left to deploy, with two great options: A) He can just rely on his home world and yours, send the extra ships to your home world. By turn nine he will have equal to your growth rate and more ships than you do, because he invested nothing attacking neutrals. B) He can take his own planet A and C with the ships left over from taking your home planet and securing his own. That will leave him with approximately the same ships you have and a much higher growth rate. So, to summarize, the opponent can beat your "better" move by the cunning strategy of doing nothing whatsoever on turn one. But he doesn't have to be that cunning. If he only makes the opening move suggested by Sconibulus, he will not only be equal with you on colonization speed, he can calculate on turn two that he has 40 free ships not needed for home defense. That's not enough to counter-attack your home world, but it is enough to launch a fleet to colonize his planet E. Your ships are all in the air, so you can't colonize anything else. The eventual fight on his home planet costs you each equal ships, but in the mean time, he is winning the colonization race. Thus an immediate attack on the opposing home world, if it doesn't win, is a terrible move. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 15th, 2010, 3:31pm on 09/15/10 at 14:13:27, Fritzlein wrote:
To expound on this point, I notice that you didn't list Planet F as another colonization option: Planet,Troops,Growth,Distance,PaybackTime A,8,5,6,7.6 D,31,5,4,10.2 E,30,5,7,13 C,4,4,14,15 F,29,4,9,16.25 B,67,5,8,21.4 You didn't list it because it is only distance 10 from the opponent, so even if we took it, the depletion in forces from fighting the neutrals would leave us vulnerable to being retaken by the opponent, and not ever getting the payback from our initial investment of ships. Now, let's look what happens if our first turn is less aggressive than the opponent's first turn, thus leaving more of our ships centralized. If we end up with 25 more ships on our home planet than the opponent has on his, Planet F is suddenly no longer too risky to take. We can take it and hold it. Since we are one turn closer, we can wait to see any counter-attack the opponent launches, and neutralize it by launching reinforcements one turn after. Unfortunately, for this particular map, having a cautious opening with centralized troops won't pay off unless the opponent makes a big error. If, for example, we use turn one to take planets AD, while he uses turn one to take planets ADE, on turn two we will note that we can take either planet E or F, and decide that E is better, merely ending up one turn behind. You only have to jigger the numbers slightly, however, (e.g. swap their growth rates of 4 and 5) to make planet F the better choice. In that case waiting one turn to watch the opponent incorrectly take planet E will pay off substantially when we take planet F on turn two. My hunch is that the small losses of being a turn behind are less important than the big gains of often getting a better planet. Also waiting one turn will leave the troop strength to punish any opponent (and there will be many) who incorrectly attacks planets ACDEF on the first turn. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Sconibulus on Sep 15th, 2010, 3:34pm I don't think Payback time is quite as important as growth rate, although it is an important metric, and definitely should be used as, at minimum, a tiebreaker. Perhaps a better fitness function for purely safe planets would be 5*GrowthRate-3*PaybackTime, although that would almost certainly need to be empirically optimized. I think looking solely at payback time would lead to a shortsighted program that potentially grabs a lot of cheap small planets passing over those that require a more substantial investment, but pay off more ships over time. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 15th, 2010, 4:02pm on 09/15/10 at 15:04:23, Fritzlein wrote:
OK this has something to do with the flexibility cost :). The variants I have written are all meant as possible candidates each achieving some goal. None of them is best, each has countarplays. Without risk of charging to your opponent attacking as much planets as possible/safe is the best option. Sending most of the troops to opponent is risky move leading to either fast loss or fast win. I agree with the stone-paper-scissors and this is how I tought about mentioned variants A).... One must probably run several scenarios to find whose variants are fully dominated by others and in the remaining "strongly connected component" chose ratios to chose particular of them. The variants which allow good play against most of them had to gain higher probability. I agree more flexibility allows better play in the midgame and centralised trops are more valuable. But the grow ratio remains the main principle ... sending grow ratio ships to your nearest opponent planet (or neutral planets the total number of send ships exceeds their defense and your ships would fight opponent's) seems increases your lead (as it reduces opponent chances to concentrate on attacking your planets) Of you can be faster than opponent growing in some region and slower in another. In that case you have to send troops to rebalance these regions. One more though probably hardly to made usable ... having almost symmetrical position with say one small planet more so you have slightly higher grow ratio ... in that case you could try to rearange your troops almost symmetrically to your opponent to mimic his moves ... but being one turn late could be easily fooled. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by jdb on Sep 15th, 2010, 4:08pm OMG, all this analysis for just the opening move! I'll never get the program finished. Quote:
This was one of the early formulas I tried. In isolation, it is likely a better choice than the total troops produced formula. This is because it tries to factor in the temporary loss of troop count, which leaves us vulnerable to a patient enemy, as discussed above. However it is possible to calculate how many troops the enemy (and the player) can send to a particular planet. So (I think) it is possible to calculate how much troop deficit is permitted, without resorting to a heuristic. I am not sure of this, we'll have to wait and see some games. Quote:
It is possible, but I'll wait until later. Quote:
Its easy to change fitness functions, so any number of them can be tried out. Some kind of selection/optimization routines will be needed. There must be a bunch of research already done on things like this. Currently, I was thinking to have a vector of the number of ships needed from each planet, required to achieve a goal (ie troop vector). Each goal would have a value from the fitness function. So in the above example, there would be 5 goals, capturing planets A,B,C,D,E. There would be a total available troop vector, containing the number of troops available from each planet. The optimizer would have to select goals to maximize the fitness function subject to the constraint that the sum of the troop vectors does not exceed the troops available vector at any point. Is there some algorithm that will look after this? |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 15th, 2010, 4:52pm on 09/15/10 at 15:34:42, Sconibulus wrote:
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? But I think you are right and my formula is wrong for a slight variation of the reason you give. I was equating two costs: the cost of having a ship in the air, and the cost of not having a ship at all. Consider the following: Planet,Troops,Growth,Distance,PaybackTime A,9,1,1,10 B,1,1,9,10 Both planets will repay the initial investment in ten turns, but I would much rather attack Planet B because having 2 ships in the air for 9 turns plus one turn for combat is less cost than having 10 ships unavailable, then 10, then 9, then 8, etc. 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 The promotion of Planet C as a desirable target is actually intuitively correct to me now that I have worked out some of the combat scenarios with these two close home worlds. The missing four ships won't tip the balance of many fights, especially since most of the planets that would be fighting are growing that much every turn. Committing 30+ ships against D or E, on the other hand, can indeed tip the balance of a fight, so the opportunity cost is real. This raises the possibility in my mind that a correct turn 1 might be attacking planets A and C only, and keeping all other ships at home to see what the opponent does. Perhaps we will attack D or E or both on turn two, putting us slightly behind in colonization, but very likely we will be glad to have kept the flexibility to take advantage of an opponent who makes the mistake of playing too aggressively. If he takes ADE, he will lose his homeworld, whereas if he takes just AD we are not really behind him at all. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 15th, 2010, 5:41pm on 09/15/10 at 16:52:19, Fritzlein wrote:
So we are slightly behind against AD, more behind against ACD an winning both against no charge and ADE charge. If it takes just DE ... this kind of simulations seems have to be done on the first move. ... sort the safe planets, try several subsets and tactical variants among them. Some of them would be clearly dominated, remaining should be chosen with nonzero probability. I am not sure following turns the situation is easier. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Oystein on Sep 15th, 2010, 6:02pm on 09/15/10 at 16:52:19, Fritzlein wrote:
Currently I believe attacking A, C and D is the best opening move. It should beat only attacking A and C. The distance between the player seems to be great enough to compensate the lack of 32 ships. It is of course possible for the opponent to attack D the next turn, but then he will be 5 ships behind without any compensation. The opponent may gamble and launch an unstoppable attack against my home planet, but that leaves his own home vulnerable. I can counter the next turn and one turn after he takes my home, I take his and become the only one on his side of the map. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 15th, 2010, 6:05pm on 09/15/10 at 16:08:30, jdb wrote:
As long at the complicated analysis produces simple heuristics, we're in good shape. :) Quote:
I wholeheartedly agree with this approach. A first pass at calculating a "safe" troop level for a planet should be very straightforward, considering only ships in the air, current troop levels, and growth rates. Instead of thinking of ships moving, it is easier to think of a circle expanding outward from the planet in question, iterating by turns. On each iteration, for every friendly planet in the circle (including the planet itself), add the growth rate to your strength, while for every enemy planet in the circle, subtract its growth rate. Then expand the radius of your circle by one. Things that came into your radius are now taken into account. Subtract from your strength enemy ships already in the air toward you. Add to your strength friendly reinforcements already in the air toward you. If a friendly planet came within range, add both its troops to your strength and its growth rate to the friendly growth rate. If an enemy planet came within range, subtract its troops from your strength and subtract its growth rate from the enemy growth rate. Expand this circle a reasonable distance, say radius fifteen, and take the minimum of your strength at each of the fifteen radii as your free troops. This doesn't get you Sconibulus's efficiency of being able to re-direct troops that are in flight, will land, and can be redirected. It doesn't account for changes in growth rate. It is therefore inaccurate, and important to cut it off from looking too far ahead, as it will get more inaccurate the further forward it looks. But the algorithm is easy and cheap and can get you a good bot up and running. Quote:
Yeah, it's complicated. I'm trying to think of something simple that is also somewhat smart. A first pass just to get a bot up and running might prioritize goals planet-by-planet rather than globally, and in strict hierarchy rather than weighted. For example, iterate through planets in order of furthest from enemy contact to closest to enemy contact, and for each 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) Note that this precludes joint attacks against neutrals or enemy planets. The only cooperation is defensive reinforcements or generally centralizing ships. I think it is good enough for a first pass, though. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Oystein on Sep 15th, 2010, 6:12pm Or maybe we have rock-paper-scissors: AC < ACD < ACDE < AC |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 15th, 2010, 6:40pm on 09/15/10 at 18:12:49, Oystein 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. However, it seems ACD < H, i.e. taking three planets leaves the home world vulnerable. Adding that fourth strategy will force us into playing mostly AC. I have no idea what other strategies are out there and how they affect the payout matrix. Does Hippo's ADH have a role to play, or is it dominated? I suspect that settling on AC 100% of the time is pretty darn good, while keeping us free from coding a bimatrix solver. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by jdb on Sep 15th, 2010, 7:33pm Quote:
This seems like a reasonable approach. I'll try and get this done sometime soon. Its easier to iterate through destination planets. Then its easier to launch joint attacks on a planet. So for step 1 it will look at all planets and move troops around to handle that. If there are any troops left over, it will move on to step 2 and look at all planets again. And so on until step 6. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by jdb on Sep 15th, 2010, 7:44pm Quote:
Quote:
I don't know what will happen here. The fight could get very complicated. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 15th, 2010, 11:32pm on 09/15/10 at 18:02:33, Oystein wrote:
I didn't consider the counter-counter attack. I think you are right that you can take his home world, but it is slightly complicated because then he might have enough to take D from you, and he will evacuate his doomed homeworld to take A and C when your counter-counter-strike launches. He would have 65 ships left over from his attack on your homeworld after defeating your growth. You would have 8 turns of growing on D before he got there, but that's only 41 ships. The way I count, before the growth rate evens out, you will have 5 turns of outgrowing him by 5 and 6 turns of outgrowing him by 10, for +85 ships to compensate the -39 you lost fighting neutrals. So you win that opening. Or am I missing something there? This close-range fighting is tricky. I have come around to your idea that sending fleets against ACD is probably the best opening move. Nevertheless, proving it to be safe is awfully tricky, and I wouldn't fuss if my bot just took AC on the first move instead. Only ACD beats it, with many possible opposing mistakes, and even if he outguesses us, taking DE the second move while the opponent takes E leaves us only 5 ships behind in the colonization race. So AC is a pretty small mistake. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 15th, 2010, 11:48pm on 09/15/10 at 19:33:28, jdb wrote:
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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Rednaxela on Sep 16th, 2010, 12:14am on 09/15/10 at 23:48:18, Fritzlein wrote:
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 (http://en.wikipedia.org/wiki/Simulated_annealing) or other global optimization (http://en.wikipedia.org/wiki/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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Sconibulus on Sep 16th, 2010, 12:39am "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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 16th, 2010, 12:50am on 09/15/10 at 18:05:55, Fritzlein wrote:
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 So I guess ACD<<H. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 16th, 2010, 1:31am on 09/16/10 at 00:39:56, Sconibulus wrote:
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. ::) |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 16th, 2010, 1:36am 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! |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Janzert on Sep 16th, 2010, 1:40am 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 |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 16th, 2010, 2:23am on 09/15/10 at 16:52:19, Fritzlein wrote:
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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 16th, 2010, 3:18am on 09/16/10 at 01:40:50, Janzert wrote:
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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Manuel on Sep 16th, 2010, 8:49am on 09/15/10 at 18:40:15, Fritzlein wrote:
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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by jdb on Sep 16th, 2010, 12:20pm 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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Oystein on Sep 16th, 2010, 1:45pm on 09/16/10 at 00:50:30, Hippo wrote:
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 09/15/10 at 19:44:36, jdb wrote:
|
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 16th, 2010, 2:11pm 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. 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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by omar on Sep 16th, 2010, 5:13pm 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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by jdb on Sep 16th, 2010, 8:04pm 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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 17th, 2010, 12:17am on 09/16/10 at 20:04:53, jdb wrote:
I'm not sure about that. If I am calculating correctly, map 30 (http://www.benzedrine.cx/planetwars/maps/map30.txt) 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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 17th, 2010, 12:31am 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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 17th, 2010, 1:21am on 09/16/10 at 12:20:12, jdb wrote:
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. :P |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 17th, 2010, 1:36am I just replayed this game (http://www.benzedrine.cx/planetwars/canvas?game_id=13314) 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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 17th, 2010, 1:56am on 09/17/10 at 00:17:51, Fritzlein 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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 17th, 2010, 2:10am on 09/17/10 at 01:56:51, Hippo 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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 17th, 2010, 2:29am on 09/17/10 at 02:10:02, Fritzlein wrote:
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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 17th, 2010, 2:33am on 09/17/10 at 02:29:10, Hippo wrote:
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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 17th, 2010, 3:05am 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). |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by jdb on Sep 17th, 2010, 9:13am on 09/17/10 at 01:36:14, Fritzlein wrote:
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/ |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 17th, 2010, 10:22am 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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 17th, 2010, 11:48am on 09/17/10 at 00:31:19, Fritzlein 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. 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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 17th, 2010, 12:36pm on 09/17/10 at 11:48:20, Hippo wrote:
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). |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 17th, 2010, 1:10pm 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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 17th, 2010, 2:17pm Mc Leopold centralizes his forces much betterthan his opponents ... but has more ships in air than required ... sending in almost opposite directions. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Rednaxela on Sep 17th, 2010, 6:07pm on 09/17/10 at 11:48:20, Hippo wrote:
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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 17th, 2010, 6:29pm on 09/17/10 at 09:13:15, jdb wrote:
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! :D |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Janzert on Sep 17th, 2010, 8:20pm on 09/17/10 at 18:07:12, Rednaxela wrote:
Unfortunately a bot is not allowed to save any information between games and does not know what opponent it is playing. Janzert |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Eltripas on Sep 17th, 2010, 8:40pm 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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Rednaxela on Sep 17th, 2010, 8:53pm on 09/17/10 at 20:20:13, Janzert 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. ::) |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 18th, 2010, 1:59am on 09/17/10 at 20:53:21, Rednaxela wrote:
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 .... |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by rbarreira on Sep 18th, 2010, 11:13am 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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by jdb on Sep 18th, 2010, 12:52pm I put the real bot up on the server as "jdb" |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 18th, 2010, 3:53pm on 09/18/10 at 12:52:56, jdb 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. 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 ... |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 18th, 2010, 3:54pm Very cool. I'll start re-playing games and giving commentary if I see anything interesting that looks fixable. This loss (http://www.benzedrine.cx/planetwars/canvas?game_id=32786) 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! |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 18th, 2010, 4:37pm on 09/18/10 at 15:53:05, Hippo wrote:
I agree with the strategic idea of centralizing ships, and this game (http://www.benzedrine.cx/planetwars/canvas?game_id=33895) 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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by jdb on Sep 18th, 2010, 6:09pm 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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 18th, 2010, 6:25pm on 09/18/10 at 18:09:48, jdb wrote:
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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 18th, 2010, 6:59pm Vortex is the current leader on dhartmei's server. In this game (http://www.benzedrine.cx/planetwars/canvas?game_id=35309), 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... |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 18th, 2010, 7:19pm 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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 18th, 2010, 8:56pm on 09/18/10 at 15:54:34, Fritzlein wrote:
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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 19th, 2010, 2:38am on 09/18/10 at 19:19:43, Hippo wrote:
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 :). |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 19th, 2010, 2:43am http://www.benzedrine.cx/planetwars/canvas?game_id=39928, http://www.benzedrine.cx/planetwars/canvas?game_id=39823 demonstrate wrongly calculated defense as the nearby neutral planet changed owner so the ships available here should be added as well. http://www.benzedrine.cx/planetwars/canvas?game_id=39270 centralizing ships would prevent recapture as well as improve your attacking power in all of these games. ... But in the first two your bot thought it's colonization time, no time for centralization so better defense calculation is much important ... later ... even while amount of ships is not enough to conquer a neutral, your bot sends the ships there ... |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 19th, 2010, 8:05am Oooo Adumlah in the contest, it would be difficult to win ... |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by jdb on Sep 19th, 2010, 10:25am 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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Rednaxela on Sep 19th, 2010, 10:48am on 09/19/10 at 10:25:21, jdb wrote:
|
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by jdb on Sep 19th, 2010, 12:33pm on 09/19/10 at 10:48:04, Rednaxela wrote:
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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 19th, 2010, 1:44pm 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'... |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by jdb on Sep 19th, 2010, 2:20pm on 09/19/10 at 13:44:58, Fritzlein wrote:
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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 19th, 2010, 2:59pm on 09/19/10 at 14:20:42, 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:
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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 19th, 2010, 3:35pm 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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by jdb on Sep 19th, 2010, 3:37pm Quote:
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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 19th, 2010, 3:54pm on 09/19/10 at 14:20:42, 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 09/19/10 at 15:37:38, jdb wrote:
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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by rbarreira on Sep 19th, 2010, 4:03pm Wow, jdb is now in fourth place, well done! |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 19th, 2010, 4:44pm on 09/19/10 at 15:37:38, jdb wrote:
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. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 19th, 2010, 4:49pm on 09/19/10 at 16:03:57, rbarreira wrote:
Wow, only 80 Elo from the top of the latest standings. Extremely impressive! I just noticed that this contest is substantially longer than the previous one. There are more than months two months remaining, not just one as I previously thought. I wonder how many hundreds of Elo points the ratings will advance between now and then. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 19th, 2010, 5:03pm on 09/19/10 at 16:44:49, Fritzlein wrote:
Oh, wait, I think I short-changed us on map 77. If we send 100 to the nearer central 14 on turn one, and the opponent counter-strikes with 105 on turn two, we can reinforce with 10 on turn three, holding the planet. 100-14+10+2*5 > 105. [EDIT] Oh, but that fails to an opponent who launches a psychic conter-strike of 100 on turn one. This is going to get game-theoretical; I had better leave it to Hippo. :) |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 19th, 2010, 5:20pm This game (http://72.44.46.68/canvas?game_id=49413) is a humorous victory for jdb based on accurate calculation of free ships. :) |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 19th, 2010, 5:23pm on 09/19/10 at 17:03:43, Fritzlein wrote:
I would lose to doing nothing :) not with 100 charge but with 48+15 charge ... . (r-s-p again :)) |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by jdb on Sep 19th, 2010, 5:47pm Quote:
I am not sure what happened here. Thanks for pointing this out. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by jdb on Sep 19th, 2010, 6:02pm on 09/19/10 at 17:23:36, Hippo wrote:
It is 16 steps from the home planet to the 14 planet. It is 13 steps from the home planet to the 48 planet. It is 3 steps from the 48 planet to the 14 planet. The 48 planet can be captured and held from any attack by sending 78 ships. Could the correct move be to send everything to the 48 planet on move 1? |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 19th, 2010, 6:23pm on 09/19/10 at 18:02:24, jdb wrote:
Oh yes in that case it's even better ... you lose nothing by going through 48. And you gain flexibility. Even more, I would continue with flow through 48 to 14 (amount to win the fight) ... and according to the game state to the opposite 14 (may be through the planet mentioned earlier). |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 19th, 2010, 6:35pm on 09/19/10 at 18:23:13, Hippo wrote:
Well, you lose 48 ships so you don't have enough left to win the fight for the better planet. Can't the other guy wait a turn to see your opening move and then safely take the higher-growth central planet on your side? |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 19th, 2010, 6:59pm on 09/19/10 at 16:49:52, Fritzlein wrote:
OK, I peeked in on the standings again, and jdb now leads outright. Woohoo! The result isn't just from picking on weaklings; it includes three straight wins over dhartmei. This one (http://72.44.46.68/canvas?game_id=50494) particularly bowls me over because it was not a win by speedier colonization plus good defense. On the contrary it was a second-strike win after dhartmei, on turn 25, decided to invest 76 troops for an extra growth rate of one. Is that just the rage-bot code doing the fighting, jdb, or did you come up with the attack strategy yourself? It is a type of win I haven't even contemplated. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 19th, 2010, 7:15pm One of jdb's few recent losses was this game (http://72.44.46.68/canvas?game_id=50615). The key point of the opening was Blue taking both central 20's. Red correctly took back the near one, but failed to hold it even though the troops were available. Fine strategy but poor tactics. Winning this battle would have won the war. This looks like a relatively easy tactical bug to quash. Something about the current reinforcement strategy must not allow a troop request from a planet currently controlled by the enemy, although it should allow a reinforcement request if the friendly ships in the air are sufficient to conquer it. A perhaps slightly harder bug to quash, but definitely superior move, would have been for Red to hold back troops from colonizing in order to counterstrike the nearer central 20 on the soonest turn possible. But allocating troops for future purposes is probably a bigger code add. Good thing there are 70 contest days left! ;) |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 19th, 2010, 8:02pm It seems that Red in this game (http://72.44.46.68/canvas?game_id=50744) (tilaiti.2) is hard-coded to pass the first turn, regardless of the map, to see what the opponent does. I looked at its ten most recent games, and it passed the first turn every time. Furthermore, it may be that the bots locutus0 and locutus0w are identical bots except that locutus0w passes the first turn. It must be worth something, because locutus0w is rated 40 points higher. At the very least, passing the first turn is an interesting insight into how some people are viewing opportunity cost; they would rather be a full turn behind in the colonization race than commit too soon. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 19th, 2010, 8:07pm Losing the big central planet in this game (http://72.44.46.68/canvas?game_id=50709) loses the war. It could only be saved by some sort of preemptive defense or by troop centralization. The latter is less desirable way to achieve the same end, because it is less precise than a tactical calculation of what troops are required for defense. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Nombril on Sep 19th, 2010, 9:01pm on 09/19/10 at 20:02:23, Fritzlein wrote:
A related thought - if bots are reacting to opponents actions, is there any value in launching 100% ships on turn 1 somewhere crazy, with the intent to turn back or to a different direction? Or would this "fake out" not work on better bots? |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Sconibulus on Sep 19th, 2010, 9:25pm As far as I can tell, a ship once launched cannot change its course until it reaches a planet. Maybe it's too expensive to outfit them with a FTL radio. : () ) |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Sep 19th, 2010, 9:49pm on 09/19/10 at 21:25:07, Sconibulus wrote:
That's right. Once your fleets are launched they are in hyperspace, where they have neither position nor direction. They wink out of existence when they set out, and wink back into existence some time later at their destination. :) |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Nombril on Sep 19th, 2010, 9:57pm OK! I thought I had read discussions about "redirecting" ships. But maybe this was referring to an intended destination for a build up of ships that hadn't been actually sent yet. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 20th, 2010, 1:13am on 09/19/10 at 18:23:13, Hippo wrote:
I have changed my mind. Send 49+15 to 48 on first turn and wait for opponent's move. Centralize ships later ... |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 20th, 2010, 2:48am on 09/18/10 at 19:19:43, Hippo wrote:
Actually for deterministic case DG+S-W is good for flight 0, and if the number of ships in air does not exceed the limit, next flight could have 2G more ships, as in exchange home scenario attacker gains defender's planet one day earlier. K-th flight could have 2kG more ships ... |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 20th, 2010, 1:23pm I have looked at the starter pack. All example bots are started at each turn again. The bots cannot remember game state from one turn to another? So even when bot makes long term plan, it has to reinvent it next turn again? |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Janzert on Sep 20th, 2010, 1:42pm Bots run for the full length of the game, although it's a little easy to get confused on this by looking at the starter bots. All bots are started once at the beginning of the game. Every turn they are resent the entire game state. The starter bots throw away all their state and regenerate it every turn. There isn't any reason you can't incrementally update your state each turn if you want. Janzert |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by jdb on Sep 20th, 2010, 8:17pm Several people have mentioned the importance of centralizing troops. Define the "radius" of a planet to be the number of turns to reach the farthest planet. So the formuia for neutral planets can now be a function of distance, growth rate, troops required and radius. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 21st, 2010, 1:35am on 09/20/10 at 20:17:56, jdb wrote:
I am not sure with that, but "border" planets are good only for production, but not for fight ... their ships should be sent back immediately ... Other situation is when there is another neutral nearby which could be occupied in near future ... in that case ships could be valuable here ... |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by jdb on Sep 28th, 2010, 10:22pm I have fixed, or at least have an idea on how to fix the obvious tactical mistakes. It requires some lookahead, but still fits under a tenth of a second. What are some viable strategies assuming short term tactics are handled? I tried always centralizing extra ships. Unfortunately this runs into trouble if there is a largish neutral planet towards the edge of the board. Not centralizing extra ships runs into trouble when the opponent gets too many ships in the centre. So it seems something more dynamic is needed to handle troop relocation. Another attempt was to only attack the enemy when you have a decisive advantage, equal or greater growth and 50 extra ships. It also seems wise to attack if behind on growth. This idea tested pretty well. All of the maps are symmetrical. I wonder if simply colonizing the planets on the home half of the board and defending them is enough. It is relatively easy to defend against an equal strength attacker. There are cases where it is necessary to keep enough troops close to a planet on the enemy half of the board, so he can't take it. This method runs into trouble if the enemy takes a central planet and starts loading it up with troops. Anyone have any other ideas to try out? |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 29th, 2010, 4:19pm I have start implementing my own bot ... It appeared much more complicated than I expected :(. I am not sure if the bot would even became competitive. There are some points in the current rules what should one have in mind. I am not sure someone have demonstarted it already: Any player could start playing "fog" game. Sending enough 0 size fleets one can limit players not to have time to read entire input. Unprepared player loses on time. Better player is paralyzed. Correctly implemented player shoud switch to the fog mode, when only planets are read from input and fleets are just extrapolated. Playing against paralyzed player have an advantage that reading planets is enough to know he is paralyzed. I am far away from implementing competitive bot and from implementing competitive fog mode even further. jdb@ yes, centralizing/attacking further neutral is difficult decision. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by jdb on Sep 29th, 2010, 6:44pm on 09/29/10 at 16:19:31, Hippo wrote:
It is my understanding that fleets of zero size are no longer allowed. Fleets of size 1 are allowed. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Sep 30th, 2010, 1:31am on 09/29/10 at 18:44:28, jdb wrote:
That is improvement. Making fog from 1 size fleets is much more compllicated may be impossible at all. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Oct 2nd, 2010, 9:07am Hmm, my current version of bot does not play well, but I suppose it could be in first fifth of the participants. (Attacking exposed enemy planets implemented, trying not to expose itself and centralizing implemented. It is not good code and there is a lot of things on to do list, but it would be better to concentrate on other things.) It may be fun to let it fight with others ... so I will probably post it as it is. ... sending not last, but almost stable version. (http://ai-contest.com/profile.php?user_id=10369) |
||||||||||
|
Title: http://ai-contest.com/visualizer.php?game_id=53200 Post by Hippo on Oct 3rd, 2010, 4:11am Testing against other bots shows that even heuristics without guessing opponent's turns and randomization could make good job. The decision between colonizacion and centralizacion failed in http://ai-contest.com/visualizer.php?game_id=5320055 game. Against better bot's it would be much more important to hold exposed planets. http://ai-contest.com/visualizer.php?game_id=5342208 Twice the same problem in calculating sufficient number of ships ... I know that I wrote about it to jdb, but it is not implemented yet. Planning on this map could be helpful :) map88 in praxis :) http://ai-contest.com/visualizer.php?game_id=5398413 Game full of blunders of the same kind http://ai-contest.com/visualizer.php?game_id=5422605 |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Oct 6th, 2010, 6:11pm What a blunder at 151th turn and the leading bot reblundered back at 152 ... http://ai-contest.com/visualizer.php?game_id=5519712. There is still room for good bots ... |
||||||||||
|
Title: Re: http://ai-contest.com/visualizer.php?game_id=5 Post by jdb on Oct 6th, 2010, 8:54pm on 10/03/10 at 04:11:54, Hippo wrote:
I've seen this happen with my bot too. For example, in the game in question, red sends troops to colonize the 24 planet in the lower left. Blue sends a snipe attempt, which red correctly defends. The problem occurs because blue colonized the 23 planet. It is far closer to the 24 planet than red's available defence. The future simulation needs to take this into account. Red needs to send defence in response to a future enemy planet. The calculation is still doable in a fraction of a second. Interestingly, when I added this to my bot, it made it play worse. It became too timid, worrying about potential attacks that never happened. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by jdb on Oct 6th, 2010, 8:59pm on 10/06/10 at 18:11:57, Hippo wrote:
Wow, blue could have taken everything. I guess the blue bot was programmed to defend first, and think about capturing planets later. Looks like this is a mistake. I'll have to rethink the strategy my bot is using. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by omar on Oct 7th, 2010, 8:25am I'm just wondering how the teams from the Arimaa community are doing in this contest. What are you positions on the ranking list? It must be really tough with almost 3,000 teams participating. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Oct 7th, 2010, 10:50am on 10/07/10 at 08:25:34, omar wrote:
I have started to write more competetive bot, but the first version is ranked somewhere in range 55 to 88 :). I have predicted to be in the first 600 :).... |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by jdb on Oct 7th, 2010, 6:25pm I find it interesting, every time I try and take a shortcut, it turns out to be a mistake. For example, initially it didn't worry about planets that would be captured later. Ooops, very important. Then I assumed it was always the best play to defend your planets first. Also a big mistake. So I need to change some stuff around to make things more general. It looks like any simplifying assumption is likely to be a mistake. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by omar on Oct 8th, 2010, 8:03pm on 10/07/10 at 10:50:30, Hippo wrote:
Wow, that's a very good start!!! You might even finish in the top 10 :-) |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Oct 9th, 2010, 12:00pm on 10/08/10 at 20:03:00, omar wrote:
... first code in java ... I have big problems with syntax and precodded data structures ... I wonder how would Fritzlein's bot ended :). ... I must got a lot of luck with bot almost without planning :). |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Oct 10th, 2010, 2:48pm I have improved attacking exposed enemy and centralisation principle in the simple version of bot ... not the revolutionary one I have planned, just the evolution ... it performs rather well. What a stupid 2nd move :( http://72.44.46.68/canvas?game_id=413280 And the bug on 9th move I know about ... http://ai-contest.com/visualizer.php?game_id=5722947 Uf http://72.44.46.68/canvas?game_id=415053 What a stupid 63rd move ... http://72.44.46.68/canvas?game_id=415053 |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by jdb on Oct 10th, 2010, 8:14pm Very nice. Its a good sign if you know where your bot makes the mistake. Its alot more depressing when you look over a game and have no idea what went wrong. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Oct 14th, 2010, 5:30pm on 09/17/10 at 03:05:23, Hippo wrote:
Oh after some more thinking waiting several more turns to start attacking by player A the neutral planet does not help. For growth 2: Opponent (B) could respond by sending all ships to home planet of A. Exchange of homes means losing the neutral, the other option is to wait till the fleets land. Exactly same situation as when started on first turn appears. B could sent 20 ships turn before the fleet lands to the neutral. This leads to neutral changing owner after 4 turns. Next 5 turns reinforcements of size 5 are required for B to hold the planet while letting sufficient defense. A has not enough ships to retake the control and don't lose home planet for exchange. For growth 1 the situation is simillar, but the planet could be captured by B 2 turns earlier by 10 ships, reinforcements by 5 ships for next 7 turns while the home planet of B remains safe. A again could not recapture the planet and loses. Growth rate 3 is OK for A ... never losing the planet. ---------------------------- http://72.44.46.68/canvas?game_id=489597 Interesting game ... initial lead against supperior fighter. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Oct 26th, 2010, 2:00am http://72.44.46.68/canvas?game_id=700243 Victory thanks to capturing zero-growth planet. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Janzert on Oct 26th, 2010, 12:19pm Very nice and quite impressive as your opponent Accoun was recently in 1st place on the official server. Janzert |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by omar on Oct 28th, 2010, 1:01am on 10/26/10 at 02:00:06, Hippo wrote:
Congratulations. I see you're managing to stay on the first page of the rankings even though the number of teams has gone up to about 3800 from 3000 when I last checked. Quite impressive. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Oct 29th, 2010, 11:47am on 10/28/10 at 01:01:40, omar wrote:
:) I have spent a lot of time thinking and implementing, but I am not sure I would finish "the good bot". I have made some local improvements to the "silly bot", but interesting thing is when you improve heuristic in one way, you start gaining somewhere and losing somwhere else. So good way for improvement is just to correct evident bugs. (Not capturing nearby opponent's planet seems to be the biggest issue, but attacking neutrals in opponent influence is another one. Correct estimate when the neutrals should be captured instead of centralisation and correct filtering of uninteresting neutrals, better time management (pondering) .... I am not sure incremental Delanay triangulation could help. Proper influence calculation, leaving planets for gaining other ones seems to remain forever on the to_do list. I am not sure my bot will ever be able to play well the MAP30 with small growth....) I felt to around 130, but now I am going back ... without an upgrade. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Nov 1st, 2010, 6:30am I like the game style of this one guy ... http://ai-contest.com/profile.php?user_id=10464. I wish I would do so small amount of blunders :) ... |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Nov 20th, 2010, 7:43am Grr, why I have started to play the planetwars :( ... I have chosen to "improve" the algorithm, by making computation more complex. The bot improved and I have discovered there were bug in the code making it play worse ... (at least according my expectations). It is not programming, it's alchemy :( ... I am going to add some more heuristics and not to try to compute it better :). After correcting the "bug" the bot plays much worse so ... I would probably continue to use the bug as "planned" good guess. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Nov 21st, 2010, 4:25pm rock - scissors - paper played by the top programs ... http://ai-contest.com/visualizer.php?game_id=8234903 Starting with 0/40 options on normal bidding or something more as superbid. On 1st turn both player passed. On 2nd turn bix0r4ever went for 40. On 3rd turn bocsimacko had to bid at least 41 and at most 80 more than bix0r4ever or bidding less than bix0r4ever. Bosimacko went to middle position and bid 41, and bix0r4ever went to low position and passed. So this rsp was locally won by bosimacko (anything in range 1-41 bid by bix0r4ever would result in bosimacko's loss). On 4th turn bix0r4ever had to bid at least 6 more and at most 41 more than bosimacko or 40 less than bosimacko. bix0r4ever bid highest possible bid ... 75, but bosimacko passed gaining globalwin. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Nov 27th, 2010, 11:07pm So finally after a week of thorough testing I have returned back to the bot already participating in the contest ... but than I have changed mind and returned to sume version in between. It would be success to finish in the first hundred, I hope I would not end at 200 or more (with almost all the time being in the first hundred expect today ...). I have not implemented "planet clouds" my heuristic to chose planets to colonize remain very easy. There were a lot of ways I went which didn't went to improvements ... I have tried to not be so eager, so now my bot is able to wait. Unfortunately, I am not sure I wait in proper time so it may play worse than original eager one. I hope it fights better in close fights now, but in global fights it plays really badly. ... |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Nov 28th, 2010, 2:05pm Seems letting the bot without changes would be much better. The current version not only does not intended bug correction, but it introduced several more :( ... So I would definitlety finish around 250 :( |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Fritzlein on Nov 29th, 2010, 1:25pm on 10/06/10 at 18:11:57, Hippo wrote:
on 10/07/10 at 18:25:42, jdb wrote:
Yes, the game turned out to be very complex, and simplifying assumptions seemed to only carry a bot a limited distance before they proved flawed. That's the sign of a good AI contest. I regret being distracted from this contest (and from Arimaa) if my absence sapped the motivation of you two. You each made enough progress that being competitive at the top seemed within reach given more support, but alas, other things have drawn away my time of late. Hippo, I see you are ranked #260 at present in the ongoing finals. Well done! |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Nov 29th, 2010, 3:21pm :) I suppose I would end around 150th without the last minute changes. I am rather disapointed, but there are games whose made me happy ... http://ai-contest.com/visualizer.php?game_id=9191158 :) |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by omar on Dec 3rd, 2010, 11:38am Looks like the contest is over now. Good finish Hippo. Placing 297 out of over 4600 is quite an achievement. I didn't see jdb or Janzert; just wondering how they did. Amazingly the 1st place finisher is 200 points above 2nd place. Wow. Now that the contest is over, I think it should be OK to post about the Arimaa AI Challenge in the Misc section of their forum; in case some of the contests there want another challenge. |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Janzert on Dec 3rd, 2010, 2:41pm I gave up the option to participate in the contest when I volunteered to take over system administration and coding for the contest. That in itself was certainly a great experience. I have mentioned Arimaa a few times in the IRC channel and I know at least a few people seemed to find it interesting. Overall I'm not sure how many people will cross over to Arimaa though. For one, while the top players certainly tend to be experienced programmers the contest itself is targeted more at the beginning programmer. Also since both google sponsored contests have featured fairly visual, quick games I'm not sure how many will find an abstract strategy game interesting. It'll be great if we can pick up even a few more bot developers though. Janzert |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by RonWeasley on Dec 6th, 2010, 7:30am I finally got the ability to view these games a few days ago. This was a great AI contest. Congratulations Hippo for performing so well! |
||||||||||
|
Title: Re: Google AI Contest Galactic Conquest Post by Hippo on Dec 8th, 2010, 5:00am Thanks to all who congratulated me :) I would be happy with my appearance in the contest if I would stop with experimental entry with few improvements. ... which would end much better than the bot I have finally chosen. My disapointment is not to the contest but to the fact the first attempts were so successful that all the codding done later went to worse results ... and there were a lot of ways to try. I had big problems with time management ... never know how many time I could spent on it so some plans were not codded ... I never went for backtracking ... to chose among several plans. Actually I have expected the best bots play a bit better ... it seems to me few of them (if some) colonised strategical planets not to gain actual growth but to secure future growth ... |
||||||||||
|
Arimaa Forum » Powered by YaBB 1 Gold - SP 1.3.1! YaBB © 2000-2003. All Rights Reserved. |