Krogothe provided a decent, clean class for metal extractor placement, but I got to thinking it wasn't the optimal solution. I'm not sure where I'm going to go with this, but I'll begin by explaining why I think Krogothe's solution (while a decent approximation) is non-optimal.
Krogothe uses a greedy algorithm finding the spot on the map with the highest metal area concentration (add each metal-pixel in extractor radius to find metal area concentration). It marks the point as the first 'best metal spot' then reduces all nearby metal concentrations as if a metal extractor was placed there before repeating the process until no spots remain or N such spots have been found. In summar, the algorithm picks out the largest spot, then the next largest, then the next, and so on.
This works - to a degree. For one, it fails to handle metal maps very well. Dealing with them isn't too hard however - the mathematical solution to 'circle packing' (2 dimensional spheres, actually) provides the optimal solution for stuffing the maximum number of constant-sized circles in a given size square (ie, our map).
What the greedy algorithm fails to account for are situations where it is NOT best to gobble up the best concentration, but rather split that concentration up over 2 or more metal extractors. For example, suppose we're playing a map with an oval section of metal that grows denser towards the center (ie, sparse outside, dense inside). Krogothe's algorithm will take the middle of this concentration (which is the most short-term efficient). This deplets the metal from the edges and now they may not be half as good as they would have been had one placed two metal extractors at the 1/3 and 2/3 points in circle width (long-term efficient).
What we're looking for here seems to fall under the mathematical 'covering problems'. I found some PhD-level resources on covering all the dots with a minimal circle and a rad looking Optimal location of a mining facility, but I'm not $40 worth of interested in this problem (also, I'm aware it is taking about factors other than what we're discussing). Wikipedia has some interesting information as well, but nothing concretely describing how to solve this type of problem. Fundamentally, we can think of the problem as, 'what is the maximum economic value for covering a set of weighted points using n-radius circles (circle has a cost, each point has a value).' This allows us to view the income rates as either short-term (30 seconds), medium-length (10 minutes), or long-term (3 days). In the first case, a greedy algorithm will probably be quite effective (though, perhaps, non-optimal). In the second, we're looking at maximizing economic value for the cost of each metal extractor. In the last case, we're looking to cover every single point of metal.
Given that Krogothe's algorithm should be good for the short-term case and sphere-packing covers the long term (expanded to an arbitrary bounding volume), I'm not quite sure how to solve the middle case. Any guesses?
Metal Extractor Placement
Moderators: hoijui, Moderators
Re: Metal Extractor Placement
Kelson wrote: This works - to a degree. For one, it fails to handle metal maps very well. Dealing with them isn't too hard however - the mathematical solution to 'circle packing' (2 dimensional spheres, actually) provides the optimal solution for stuffing the maximum number of constant-sized circles in a given size square (ie, our map).
Heres a little pic of 4 skulls, produced by my metal class.
notice that the metal on that map is not 100% constant so a few points are invariably warped its a good enough example of what this ideal map you imagine could be:
It does use circle packing naturally.
What the greedy algorithm fails to account for are situations where it is NOT best to gobble up the best concentration, but rather split that concentration up over 2 or more metal extractors. For example, suppose we're playing a map with an oval section of metal that grows denser towards the center (ie, sparse outside, dense inside). Krogothe's algorithm will take the middle of this concentration (which is the most short-term efficient). This deplets the metal from the edges and now they may not be half as good as they would have been had one placed two metal extractors at the 1/3 and 2/3 points in circle width (long-term efficient).
Now, Say you have a round metal patch of radius 1.1r (r= extractor radius). You could put one in the middle, and take over 80% of the metal in that spot. OR you could put 3+ extractors and get that extra metal.
We both agree its better in the short term to do it my way right?
now about the long term, lets think it through!
say the patch will generate 2 metal total, so my one extractor will make 1.6 metal and your 3 ones will generate 0.66 each.
Since we are looking at the long term, we will consider mohos have been placed.
So, since mohos make 6 times more metal than a mex in XTA, my moho will be making 9.6 metal, draining 300 energy, and your 3 mohos will be making 12 metal, draining 900 energy.
My moho needs 300/9.6 = 31.25 energy per metal produced, which is twice as good as metal makers.
Your, long term mohos need 900/12 = 75 energy per metal produced. Youre a couple K metal down and constantly wasting energy.
Of course you could say that my example was very specific too, but the bottom line is:
My class will handle as best as it is possible:
Early and late game (thats about 80% of all games)
Metal maps, OTA maps (brings it up to 93% considering even spread of maps)
Any spot on spring metal maps that isnt elliptical, uniform, contiguous metal patch of dimensions very close to the ones you described, (hmm im guessing that brings it up to 99%?)
It would be nice to see a class that does it 100%, but i doubt it will be able to do so fast enough to be playable, or if it will be worth spending the time sqeezing so little when it could be used improving other parts of the AIs
(post edited to remove sarcasm)
Last edited by krogothe on 10 Jan 2006, 15:29, edited 1 time in total.
Generalising the greedy metal extractor placement algorithm
Firstly there really is only a need to go to this level of detail for Moho placement. There 's no point being ultra efficient with mex placement, minimising the number you put down because they're 1 cheap, 2 build fast, 3 use very little energy. It's actually handy to have redundancy in your mex placements so that raids are less effective. Mohos on the other hand need to be placed with utmost care due to their cost, build time and large energy usage. Of course for expensive resources like Mohos you also want to make sure they're reasonably well defended too - you don't care if you build a mex in the middle of nowhere and it gets popped because it's so cheap, but if you build an undefended Moho you have to be careful that you get your investment back, not to mention putting your adv con-units at risk whilst building it.
A simple generalisation to the greedy algorithm is to consider multiple mexes simultaneously. I.e. instead of finding the single best spot for the next mex, find the best placements for the next n mexes (e.g. the next 3 mexes).
Having found the best positions for the next 3 mexes, you then build just the first of these, and then rerun the algorithm next time you need another one (i.e. don't depend on your original calculation). This effectively gives you a bit of "look ahead" on what effect your use of mexes is going to have on the efficiency of metal usage, and makes sure you don't plant a Moho in the middle of an oval, requiring three Mohos to cover the oval instead of two.
This approach gives you a headache because as you increase the number of mexes which you look ahead by (n), the possible number of combinations goes throught the roof (k^n, where k is the size of the search space for 1 mex). Therefore you need to use either a GA (genetic algorithm) or simulated annealing type algorithm to cut down the search space fast.
Here's a cheap and cheerful bit of psuedo-code if GAs/simulated annealing scare you =) Here, we have a vector (mexPosns) of length 2n, which contains the x and y position for each mex. Note that this algorithm really doesn't work to well on maps which have defined metal spots instead of a continuous metal map (e.g. Greenhaven), but those need to be treated differently anyway.
The score function indicates how good the n metal extractor positions are. If you're just looking at metal income then that will mean the total amount of metal they'll bring in. However distance from construction units, how well defended the area is etc. also need to be taken into consideration when placing mohos.
The acceleration parameter should be any value greater than 1. It controls how fast the algorithm works and also how accurate the answers are. The more acceleration, the faster it works, but the less accurate your mex placement will be.
Once you've found your three positions, you'll probably want to "polish" your final solution to make sure your extractors are bang on target. An easy way to do this is to re-run the algorithm with a much lower acceleration, but start it off running with the mex positions output by the previous, high acceleration run.
Disclaimer : 1. I haven't seen the code for the current algorithm, 2. the above psuedo-code likely has mistakes in as I typed it on the fly, but hopefully it gives you the idea!
Hope this helps
Munch
A simple generalisation to the greedy algorithm is to consider multiple mexes simultaneously. I.e. instead of finding the single best spot for the next mex, find the best placements for the next n mexes (e.g. the next 3 mexes).
Having found the best positions for the next 3 mexes, you then build just the first of these, and then rerun the algorithm next time you need another one (i.e. don't depend on your original calculation). This effectively gives you a bit of "look ahead" on what effect your use of mexes is going to have on the efficiency of metal usage, and makes sure you don't plant a Moho in the middle of an oval, requiring three Mohos to cover the oval instead of two.
This approach gives you a headache because as you increase the number of mexes which you look ahead by (n), the possible number of combinations goes throught the roof (k^n, where k is the size of the search space for 1 mex). Therefore you need to use either a GA (genetic algorithm) or simulated annealing type algorithm to cut down the search space fast.
Here's a cheap and cheerful bit of psuedo-code if GAs/simulated annealing scare you =) Here, we have a vector (mexPosns) of length 2n, which contains the x and y position for each mex. Note that this algorithm really doesn't work to well on maps which have defined metal spots instead of a continuous metal map (e.g. Greenhaven), but those need to be treated differently anyway.
Code: Select all
acceleration = 1.2
stepSize = extractor radius
bestScore = 0
while stepSize > 1:
delta = random vector, length 2n
if score(mexPosns + (delta * stepSize)) < (bestScore * 0.9):
stepSize /= acceleration
else:
while score(mexPosns + (delta * stepSize)) > bestScore:
bestPosns = mexPosns + delta * stepSize
bestScore = score(bestPosns)
stepSize *= acceleration
mexPosns += delta * stepSize #NB DON'T set this to bestPosns or we get stuck in local minima
The acceleration parameter should be any value greater than 1. It controls how fast the algorithm works and also how accurate the answers are. The more acceleration, the faster it works, but the less accurate your mex placement will be.
Once you've found your three positions, you'll probably want to "polish" your final solution to make sure your extractors are bang on target. An easy way to do this is to re-run the algorithm with a much lower acceleration, but start it off running with the mex positions output by the previous, high acceleration run.
Disclaimer : 1. I haven't seen the code for the current algorithm, 2. the above psuedo-code likely has mistakes in as I typed it on the fly, but hopefully it gives you the idea!
Hope this helps
Munch
yeah kelson you big cunt, how could you politely put forward a suggestion that just happened to be wrong like that? absolutely no need. some people... way to go for cutting him down krog, dick must've grown with that one, i bet you hold a knife in your sleep you're so cool, you and AF are like the gangsta rappers of AI making, fo shiz my nizzles... fo shiz...
Re: Metal Extractor Placement
No, if it were using circle packing it would place the minimum number of metal extractors that completely cover the map. Not, as your's does, include a non-optimal level of overlap (notice your skew). Just because something may cover all the metal and/or cover the 'best' spots, doesn't mean it is optimal - as per my original statement.krogothe wrote:It does use circle packing naturally.
To explain a bit, your's covers all metal spots, progressively culling the max-valued ones. This means that, run to it's logical conclusion, all spots will be covered. This does not mean it will be the optimally minimized number of metal extractors. It also does not mean it will be the most economically valuable solution after 100/1000/100000 seconds of extraction.
Not only do we agree, but I stated that. Your arbitrary case falls into the third algorithmic choice - complete coverage. What _I_ asked was the most economic medium-term solution.krogothe wrote:Now, Say you have a round metal patch of radius 1.1r (r= extractor radius). You could put one in the middle, and take over 80% of the metal in that spot. OR you could put 3+ extractors and get that extra metal.
We both agree its better in the short term to do it my way right?
Your class will handle both cases, by definition, the best it is possible. Wording aside, it will not handle either case the best that is possible. What it will do is provide the short term economic gain from covering the metal spots with the highest initial value - pretty much the definition of a greedy algorithm.krogothe wrote:My class will handle as best as it is possible:
Early and late game (thats about 80% of all games)
Metal maps, OTA maps (brings it up to 93% considering even spread of maps). Any spot on spring metal maps that isnt elliptical, uniform, contiguous metal patch of dimensions very close to the ones you described, (hmm im guessing that brings it up to 99%?)
Now, you're throwing out numbers here which mean absolutely nothing. Furthermore, you're talking like an dick and bringing up irrelevant points to somehow claim/prove that your metal class is the best one that could be written. Once again, you are wrong and the class is non-optimal in every sense of the word.
Covering all the metal falls under the third point I made and said I wasn't interested in. There are well-studied mathematical abstractions of these specific problems - I'm looking for information about the economic trade-off problem. I don't care about the first or last approaches I posted (ie, highest concentration and/or complete coverage).krogothe wrote:It would be nice to see a class that does it 100%, but i doubt it will be able to do so fast enough to be playable, or if it will be worth spending the time sqeezing so little when it could be used improving other parts of the AIs
Since my point was clearly missed (by krog), I'll state it again.
Your case of putting three mexes to completely cover a point shows the economic faults of such an idea - it will cost you a ridiculous amount of energy units / metal unit extracted. In a high-energy game, this may be a good choice, but the class should have some way of determining these factors. Additionally, I'd like it to cut-off metal spots once their income falls below a certain economic (not hard coded metal-spot value) threshold - perhaps based on the player's current energy/metal. Recalling that the class is claiming to provide the 'best spots', these seem required.Kelson wrote:Fundamentally, we can think of the problem as, 'what is the maximum economic value for covering a set of weighted points using n-radius circles (circle has a cost, each point has a value).' This allows us to view the income rates as either short-term (30 seconds), medium-length (10 minutes), or long-term (3 days).
One other note, I'm trying to keep this mod-abstract. The class will be given a set of parameters (metal extraction, energy use, metal cost, energy cost, time estimate) and set to find the best locations given those. These parameters will help in determining how much influence the building cost of a metal extractor has. At 0 seconds, the only cost is the build cost. At 10 magic units, the cost is build cost + 10*energy use + 10*metal use. At 100 magic units, the cost is build cost + 100*energy use + 100*metal use (current mexes use 0 metal, this may not always be the case). Compare with the metal production of to find best locations.
Some interesting code you've got there. Looks like delta somehow picks a selection of mex placements. These are checked against the best found so far and updating if it is best. How are we determining the points to check for though? Are you trying to 'jiggle' it during the hill climb, essentially?munch wrote:The score function indicates how good the n metal extractor positions are. If you're just looking at metal income then that will mean the total amount of metal they'll bring in. However distance from construction units, how well defended the area is etc. also need to be taken into consideration when placing mohos.
The worst part was it wasn't wrong!Liam wrote:How could you politely put forward a suggestion that just happened to be wrong like that?
Nice flame. Doesn't make you sound like an ass at all. And, what the hell is a scousers?krogothe wrote:wow liam, its your first post thats over 3 lines long! I bet youre growing up into a fine boy! maybe youll even learn to make useful ones in a few years huh? No matter how hard i try i cant take scousers seriously Rolling Eyes
Krogothe, I started this thread to include everyone in a discussion on optimal metal extractor placement to maximize variably-timed economic factors. I don't need, or want, you trolling it in some vain attempt to defend your precious class. You can accept its faults or claim it is the best possible mex placement EVAR!!11one!1 All I'm going to ask is, if you feel it is necessary for you to keep being an asshole and/or claiming the above, leave the thread. There is no need for dick-waving here.
I wont interrupt your topic further, in order to prevent a flame war you are dying to start, but please stop sending childish pms full of swearing on spring okay?
Enjoy your discussion and hopefully make a better metal class for the benefit of the community!
Enjoy your discussion and hopefully make a better metal class for the benefit of the community!
Last edited by krogothe on 10 Jan 2006, 21:39, edited 2 times in total.
wtf, em a gansta rapper? Where did all that come from, that and zaphod comment seems totalyl out fo place.
I agree that there is more room for optimisation in krogothes mex class, but ti is currently the best implementation avilable (at least the version he has), next in line would be the copy he sent me which i itnegrated into cains class, whcih has advantages thus over krogothes version, but krogothe then cotninued to optimise and work on his algorithm after I did that. Then we have the public version of his class which is is currently outdated comapred to the versions me and krog have. Then there's cains old class coming in close.
When cosnidering the economic potential of a spot one needs to think in terms more fo what the potential fo the actual region si, rather than simply what reosurces there are to be exploited. For example you want a large patch fo land to build a hypermart that's cheap, and easy tog et plannign permission. But there are plenty fo palces that fit that bill much better than the preferable locations, yet no planner would ever cosnider building them there for other reasons, such as transport, demographic, accessibility.
As such when evaluating a map co-ordinate, all the algorithms thus far are totally ignoring the enemy threat. What fire coverage is provided in that area, is the output of the item worth it? Or is it not going to last long enough to be profitable.
In the mean time, liam whoever you are, and kelson, quit it with the penis envy. And dont swear on thsi baord, there are people who get domain names blocked/filtered out from school networks when theys ee words like that. Zaphod? Try fitlering them out? If I remember correctly ti is possible under PhpBB
I agree that there is more room for optimisation in krogothes mex class, but ti is currently the best implementation avilable (at least the version he has), next in line would be the copy he sent me which i itnegrated into cains class, whcih has advantages thus over krogothes version, but krogothe then cotninued to optimise and work on his algorithm after I did that. Then we have the public version of his class which is is currently outdated comapred to the versions me and krog have. Then there's cains old class coming in close.
When cosnidering the economic potential of a spot one needs to think in terms more fo what the potential fo the actual region si, rather than simply what reosurces there are to be exploited. For example you want a large patch fo land to build a hypermart that's cheap, and easy tog et plannign permission. But there are plenty fo palces that fit that bill much better than the preferable locations, yet no planner would ever cosnider building them there for other reasons, such as transport, demographic, accessibility.
As such when evaluating a map co-ordinate, all the algorithms thus far are totally ignoring the enemy threat. What fire coverage is provided in that area, is the output of the item worth it? Or is it not going to last long enough to be profitable.
In the mean time, liam whoever you are, and kelson, quit it with the penis envy. And dont swear on thsi baord, there are people who get domain names blocked/filtered out from school networks when theys ee words like that. Zaphod? Try fitlering them out? If I remember correctly ti is possible under PhpBB
Psuedo simulated annealing
Bingo =) There are two basic principles behind simulated annealing:Kelson wrote:Are you trying to 'jiggle' it during the hill climb, essentially?
1. Instead of just climbing the hill, also randomly allow downhill steps
2. Reduce the chance of going downhill gradually over time (cooling)
The point of priniciple 1 is that it allows you to avoid just climing the nearest hill, which may in fact not be very "high". The point of prinicple 2 is that it gets to the highest part of the map overall at the start (i.e. best concentration of metal), then gradually refines that result. The code I presented above only uses the first of these, but that's OK for TA since metal is generally scattered all over the map.
Hope this helps
Munch
oh i know what you mean, went to the doctors the other day and he told me i had cancer, my mother cried for hours, turned out he was just kidding. i tell you those scousers are tricky b*stards (just for you AF). seriously though, my point is: it's not like he was foaming at the mouth in that post or anything, honestly i don't know/care if he was wrong or not, and you lept on him like a big leaping leaperer (if you will) because he was talking about something you did, much like if you give a hint that NTAI might not be the best AI, then quite clearly you're testing it unfairly and/or goblins are affecting the results. god i can't wait for KAI to be released, not because i think it might be the best AI, because i can't WAIT to see how fast you and AF turn on each other. seriously i've already started buying the popcorn in.krogothe wrote:No matter how hard i try i cant take scousers seriously
also, for Kelson, scousers are people from Liverpool :)
lmao, now I understand the gangsta comment.
Though a lot fo those NTAI si not the best comments where fair because I specifically stated XTA Core as the condition, and touted NTAI as beign the best udner those conditions. Yet all attempts to prove em wrong for soemr eason happened to occur under AA, or on XTA Arm. And there are instances where I did say another AI was at the tiem better than NTAI, for example I touted OTAI v1 as better for a while, and currently KAI is better than NTAI 0.28.10, he's posted the screenshots to prove ti and he's shown examples of it doing things NTAI was either rarely doing, or was incapable of doing.
However NTAI's superiority is soemthign that is not lost, and I will return with 0.3 as I ahve said for a while, and I'll make all that came before ti hopelessly obsolete.
And as long as Krog doesnt attempt to attack NTAI's standing directly through means other than replays and screenshots proving KAI's dominance (for example a game with no neutral spectators or replays), which doesnt seem like krogothe at all since he seems more fo a show and tell person, then I'll be ok, because I know I'll beat him with the next version of NTAI ^_^
Though a lot fo those NTAI si not the best comments where fair because I specifically stated XTA Core as the condition, and touted NTAI as beign the best udner those conditions. Yet all attempts to prove em wrong for soemr eason happened to occur under AA, or on XTA Arm. And there are instances where I did say another AI was at the tiem better than NTAI, for example I touted OTAI v1 as better for a while, and currently KAI is better than NTAI 0.28.10, he's posted the screenshots to prove ti and he's shown examples of it doing things NTAI was either rarely doing, or was incapable of doing.
However NTAI's superiority is soemthign that is not lost, and I will return with 0.3 as I ahve said for a while, and I'll make all that came before ti hopelessly obsolete.
And as long as Krog doesnt attempt to attack NTAI's standing directly through means other than replays and screenshots proving KAI's dominance (for example a game with no neutral spectators or replays), which doesnt seem like krogothe at all since he seems more fo a show and tell person, then I'll be ok, because I know I'll beat him with the next version of NTAI ^_^
well AF where does all that ai rudeness come from ?
its ok we are all developing ai's and everyone wants to have the best ai, but u seem kinda fixated or even obcessed with the best ai thing.
just drop it and develop urs naturally, cause after all were here to give spring a skirmish stable skirmish option, wich it doesnt have know.
its ok we are all developing ai's and everyone wants to have the best ai, but u seem kinda fixated or even obcessed with the best ai thing.
just drop it and develop urs naturally, cause after all were here to give spring a skirmish stable skirmish option, wich it doesnt have know.
you want a stable skirmish AI option, I'll give you one.
My goal with NTAI is to progress it as rapidly as possible. If someone ha bettered NTAI it means they're moving faster and I'm failing. That and I like to compete. I just dont like it when people stand by and diss my work rather than give constructive critiscism. Say NTAI cant do a or b or c, and I wont make so much as a reaction, as if you said, NTAI is crap and is a laoda rubbish or NTAI crashed so go use this instead (with no crash information whatsoever), or when people generally bear grudges, or allow others to act like trolls (see JCAIvsTAI fiasco), or are generally not trying to understand things and take everything from an overprotective self centred view (see cains mex class fiasco), or even NTAI cant do this simple thing (following a screenshot of it actually being done by NTAI), or people dissing the latest version because a version that's outdated crashed on them a month ago.
My goal with NTAI is to progress it as rapidly as possible. If someone ha bettered NTAI it means they're moving faster and I'm failing. That and I like to compete. I just dont like it when people stand by and diss my work rather than give constructive critiscism. Say NTAI cant do a or b or c, and I wont make so much as a reaction, as if you said, NTAI is crap and is a laoda rubbish or NTAI crashed so go use this instead (with no crash information whatsoever), or when people generally bear grudges, or allow others to act like trolls (see JCAIvsTAI fiasco), or are generally not trying to understand things and take everything from an overprotective self centred view (see cains mex class fiasco), or even NTAI cant do this simple thing (following a screenshot of it actually being done by NTAI), or people dissing the latest version because a version that's outdated crashed on them a month ago.