Solving a factorial time problem (alliance techies ahoy)

[Jester]

I've been playing around with my PA dumpfiles occasionally over the last few weeks.

The information is available for us to derive alliance memberlists from the dumpfiles.

The easiest way, in algorithmic terms, is to simply generate all, unorder, non-replacement, permutations of planet combinations and test sum of score and size vs alliance score and size*. However, this is impossible to do practice. The problem, in its dumbest form, takes total_planets C alliance_members time, which is about 10^200 for 4500C100**. One would have to make incredibly powerful optimizations to make this problem solvable for any alliance_members > single digits. My experimental script managed to do 6 member alliances in reasonable time, however these were most likely all wrong, as I did not do exhaustive search and I did not check against later ticks. For those of you not familiar with the pigeon hole principle, look it up.

This means the problem is even worse than just plain factorial time, you have to do full, exhaustive searches, over multiple ticks to confirm a match.

Alliance intel, lists of smaller alliances' members, pruning, optimizations, distributed computing***. These things can all help, but are not likely to actual put a worthwhile memberlist (that is, a top alliance) in the realms of the practical****.

A better way

There must be a better way of doing this. And I think there may be.

We have statistical information on every planet, it's easy to compile. We have similar information for each alliance. We need to combine everything we know to get a good list of possible candidates, rather than assume everyone is a member.

Every tick an alliance gains a certain amount of score and (possibly) roids. Within the alliance, this difference should follow a normal distribution. Over a series of ticks, it should be possible to use these statistics to weed out a series of planets.

There are probably more maths we can do on the lists to make them more reasonable, and even better: these things are all O(N^P) time or less (where N is the number of planets, and P is an integer).

If we can't reduce the number of planets quite enough, we can hopefully do our old factorial time algorithm on a reduced set of possible planets in reasonable time.

Disclaimer: I haven't checked to see how many planets it's possible to discount over how many ticks. Obviously, with similarly sized alliances there's going to be overlap. At this point one can see two solutions: the Right one, and the Good Enough one. The R solution would mathematically guarantee that any produced result is correct. The GE one would make it likely enough to trust any result, but wouldn't guarantee it.

Disclaimenr number two: I'm not doing this for any alliance. To be honest, I originally wanted some way to figure out how much XP each alliance has. Then I figured it'd be fun to follow other trends. Once one has alliance memberlists for every alliance in the game, it's possible to do some pretty interesting things with the available numbers.

So before I actually get started on coding (and partly because I don't actually have time to prototype atm), I'd like to get some thoughts. I'm sure we can all agree that the simple, dumb factorial time version is useless on the raw data. However, can it be useful on a reduced set? I'm sure that if one could reduce the number of possible planets to around 500, it'd be possible to figure out the larger alliances reasonably quickly (by applying strategic optimizations and prunes). The key is not to be able to find out the largest alliances directly, the key is to figure out who is definitely not in it, and part of that is figuring out the smaller alliances first. Remember that every planet removed from the larger cases is a great improvement do to the exponentiality of the problem.

Thoughts?

* If you don't quite follow this, don't worry. The important stuff is later.

** Quantum physicist flatmate in useful for something shocker!

*** Finally a techie can be glad for having more members.

**** I'd say a practical solution would give an opposing memberlist within 200-300 ticks. Anyone disagree?

[Kloopy]

Firstly, the algorithm I was talking to you about on IRC, it removed the smaller alliances and worked it's way up the scale. But there are some interesting maths possible, as you say.

I don't think we'd ever get a suitably fast solution to the problem, but it would be interesting to see how well we could do.

For example, you could do some clever maths on averages, you know the average score of an alliance's members. So assuming an alliance of three members whose average score is 5mil, you choose the first one as 1:1:1 which has 20mil score, you know this planet cannot be part of the alliance, because it brings the average up too far. I'm not sure whether this principle works at a large scale, in fact I'm fairly confident that it would only ever have an effect in a small number of cases. But it's another thought at least.

There are lots of little tricks you can do to make this thing faster, but as I say, I don't think it's very possible.

One thing to make sure is that you can cache the entire dump and working memory of the program into the physical RAM of the machine you're running it on. You really don't want to be flowing over into virtual memory for something as intensive as this.

As it's something I've already attempted before, it'd be interesting to see other peoples view on the idea and whether anyone can come up with better ideas for optimisation.

But, of course, this whole thing would be in vain, because if we were to succeed, PATeam would simply give rough values in the dumps, for example telling us the total score is 100mil instead of 100,241,295. *sigh*

Kloopy

[Bashar]

I think it would be quicker and easier to hack into the games database and get the lists that way. I dunno why you were looking for me about this problem, I barely understand half of what you said. I am no techie, I just do a bit of coding from time to time, I gave up with all that algorithm theory crap years ago.

You would need to remember as well that alliances lose/gain members, and that could throw a cog in the works.

Also, I don't think that it would be worth doing anyway from an alliances point of view, as it wouldn't work til a decent time into the round (when most alliances already have enemy memberlists from intel) as there are too many possible combinations early on as scores are much closer together, and in many cases, exactly the same (although the fact there is score and value makes this less problematic sooner). As you progress through the round, there are less and less viable combinations, but I suspect that when you get to the point that you have a combination that is probably right, most alliances would have a full memberlist for enemies anyway, and if you were that bothered, you could just ask them.

[jerome]

so, i`m just going to ignore 99% of what was said in the thread and make a point about the remaining 1% -> yes i too am interested in an alliance xp and average xp etc, it`d be interesting viewing - to see which alliance were purely-roiding allround and who were 'killing' the bigger targets as well etc.

[Bashar]

Originally Posted by Jester

**** I'd say a practical solution would give an opposing memberlist within 200-300 ticks. Anyone disagree?

I think it would have to be less than that, I have known alliances having full memberlists of others before protection ends, I reckon 100-150 ticks. Although, I suppose if it was later, and it could be made to work, it would serve to confirm intel.

[mist]

rather than trying to match all the alliances at the same time, it would seem quicker to start matching to one alliance at a time.

in order to do this you'd only need to consider up to 100 planets at once, less if you get to know an alliances size. then you can start with the largest planets and work down to including the smallest, so that you need to consider less combinations (or is it permutations? i think permutations, anyway, whichever is least).

once one alliance is done, you can remove them from the pool and repeat, so that you have to crunch less numbers with each alliance. if you start with the top alliance, then odds are you'll reach a solution quickly as you'll be looking at the top planets.

in order to speed things up, i'd suggest looking for possible matches after a few ticks (doubt the first 24-48 ticks would be useful, as too many planets will be the same) and then once you find a solution that works for score only, checking its roids, and if that works then moving on to latter ticks. as there'll be few solutions that work for more than a couple of ticks this part should be fairly quick.

also, as there are always leaks, the 100 member limit may well reduce. also, with buddy packs in this could provide a helping hand, if you consider people in the same pack to be likely in the same alliance, as it'll third the variations

i have a gut feeling that looking at progression, rather than direct results might be quicker, but i don't see how at the moment. if it dawns on me i'll get back to you

disclaimer: i made this all up in 5 minutes. there's no guarentee any of it's right

-mist

[mist]

oh, forgot to mention. i figure it'd work on less than 100 ticks of data easilly, could probably do it with a day's data. it's the processing time that's a problem

-mist

[xtothez]

We looked at this during the last round, but couldn't find a suitable way to optimize it enough to be practical. Even when cross-referencing with known intel and removing tiny inactive planets, there was still a huge margin to cover.
I do however have two points for you. First, you don't really need to check over a period of several ticks, as allliance size can be used as a 'checksum' for your final total (alternatively you can do the search on size and use score to verify). Secondly, and most importantly, do not let kloopy near this project:

<Kloopy> You could just create one **** of an index of the universe.
<Kloopy> Store in a database every combination of planets.
<Kloopy> And total up the score and roids for that combination.
<Kloopy> I mean one HELL OF A BIG file with every combination of planets that's possible.
<@Synthetic_Sid> lol
<@[MO]TheRat> 500kb*3300^99
<Sin|coding> Kloopy
<@Synthetic_Sid> you seriously have no clue kloopy :)
<Sin|coding> taht's like...a few million terrabytes

[Kloopy]

On the subject of accuracy, I think it might be rather surprising how quickly a correct match is calculated. We have a target for total score, total roids and total value. That's three items that all need to add up to the absolute single digit to make the alliance list correct. I would have said by the end of the first round of attacks after protection is lifted, there would be sufficient variation for a good result.

[Kloopy]

There Is Nothing Wrong With Large Amounts Of Data!

[Bashar]

lol xtothez, that is a Kloopy solution if ever there was. He is nearly as lacking in subtlety as I am.

Mind you, knowing him, if he set his mind on it, he'd probably go out an buy all the necessary hard drives/processors/RAM/power stations necessary, and come back witha big grin and say "Done it!", to which we would all of course reply "That's nice, but wasn't that overkill?".

[mist]

checking over several ticks is a good idea to make sure you've got the only match possible, and once you've got a match requires very little extra processing.

i had forgotten about removing the uselessly small planets tho, although starting with the biggest and then working down would probably have that effect anyway

-mist

[Kloopy]

Rofl. I love reputations. Actually, it's pay day in two weeks followed very shortly by a nice chunky student loan cheque. I realise it'd take a long time, but surely it must be possible. Even if we have to proove that P (the set of algorithms solvable in polynomial time) is the same as NP (the set of algorithms solvable in non-polynomial time) by showing that we can reduce any NP problem to P using a third (reducing) algorithm (which itself can be run in polynomial time), then not only can we solve the alliance member list problem in a suitable time period, we also become the most famous mathematicians of our time.

Doing the above would rule all public key encryption useless, thus ruining security in the computing industry entirely. So, we'd better watch our backs.

[mist]

itt, kloopy tries to confuse everyone else in to agreeing with him

-mist

[Bashar]

Originally Posted by mist

itt, kloopy tries to confuse everyone else in to agreeing with him

-mist

Tries? I find myself agreeing, but I don't even know what with.

[Kloopy]

Whether the groups P and NP are equal is one of the biggest questions in Maths. Noone has managed to proove that they are equal and noone has managed to proove they're not equal. It's amazing. There are huge concequences if either way is prooved.

If P = NP, then as I said, so much of todays technology, especially in security is rendered pointless. But if P != NP, then mathematicians can save a lot of effort trying to proove it and we have proof that PGP and other encryption methods are "perfectly" secure.

You can always find some stunning things in Maths. :-)

[mist]

being as pgp's security was recently called in to question, i find the prior more probable

but that's beside the point

your methods for finding alliances are still slow

-mist

[Jester]

Originally Posted by Kloopy

Firstly, the algorithm I was talking to you about on IRC, it removed the smaller alliances and worked it's way up the scale. But there are some interesting maths possible, as you say.

I don't think we'd ever get a suitably fast solution to the problem, but it would be interesting to see how well we could do.

I think you've misunderstood me. Primarily, I want to avoid the factorial version of the problem. Entirely if possible, but I'll accept running it on very well pruned sets.

I'm not sure whether this principle works at a large scale, in fact I'm fairly confident that it would only ever have an effect in a small number of cases. But it's another thought at least.

Pruning too large planets out of small alliances is easy, and can get rid of a lot of planets. However, doing stuff on cases where you're looking for small subsets is not very efficient. If one is looking at the factorial solution, one has to reduce the size of the possible set in the larger cases, as this will give exponential gains (well, inverse exponential.)

There are lots of little tricks you can do to make this thing faster, but as I say, I don't think it's very possible.

Thank you for repeating what I said!

One thing to make sure is that you can cache the entire dump and working memory of the program into the physical RAM of the machine you're running it on. You really don't want to be flowing over into virtual memory for something as intensive as this.

The python prototype I was using had a consistent footprint of about 8.5MB. Not exactly frightening memory consumption these days.

As it's something I've already attempted before, it'd be interesting to see other peoples view on the idea and whether anyone can come up with better ideas for optimisation.

First off, part of the reason this is interesting is that it's dead hard. Secondly, you've entirely missed the point of my suggestion. I want to avoid using permutation matching because it ****ing sucks. However, if one is in the position of having reduced the set of possible members to a practical size, then using permutation matching becomes a viable way of finding an exact (rather than an approximated) solution.

But, of course, this whole thing would be in vain, because if we were to succeed, PATeam would simply give rough values in the dumps, for example telling us the total score is 100mil instead of 100,241,295. *sigh*

This is a pretty good argument to never ever tell anyone when a good method is found. But really, if the method is public, PA team should have no incentive to protect the large alliances from discovery, which is essentially what they'd be doing.

Originally Posted by Bashar

I think it would be quicker and easier to hack into the games database and get the lists that way. I dunno why you were looking for me about this problem, I barely understand half of what you said. I am no techie, I just do a bit of coding from time to time, I gave up with all that algorithm theory crap years ago.

You were posting in the other thread, and I was going to ask you what I asked Kloopy instead.

You would need to remember as well that alliances lose/gain members, and that could throw a cog in the works.

Actually that would help, except in the case where they lose a member the same tick they gain a new one (or more, as long as the member difference is not the same as the difference between the two ticks.) One could reasonably well predict who joined or left an alliance by taking the difference, subtracting the average alliance gain and finding planets within z* of the assumed number.

Also, I don't think that it would be worth doing anyway from an alliances point of view, as it wouldn't work til a decent time into the round (when most alliances already have enemy memberlists from intel) as there are too many possible combinations early on as scores are much closer together, and in many cases, exactly the same (although the fact there is score and value makes this less problematic sooner).

This isn't really meant to be from an alliance point of view, though. I haven't been in a proper alliances since before round 9. It could potentially be an equalizer for smaller alliances.

As you progress through the round, there are less and less viable combinations, but I suspect that when you get to the point that you have a combination that is probably right, most alliances would have a full memberlist for enemies anyway, and if you were that bothered, you could just ask them.

Again, I'm sorry if I gave the impression that I think the matching of sequential combinations is the way to do it. I'm looking for other ways to deduce who is likely part of an alliance.

Originally Posted by Bashar

I think it would have to be less than that, I have known alliances having full memberlists of others before protection ends, I reckon 100-150 ticks. Although, I suppose if it was later, and it could be made to work, it would serve to confirm intel.

Depends on the alliance though. Obviously it'd be better to have it as early as possible, but 200-300 ticks is easily the first 5th of the round, which is good enough for someone like me who isn't going to use it to target people, but to see how people are faring etc.

Originally Posted by mist

rather than trying to match all the alliances at the same time, it would seem quicker to start matching to one alliance at a time.

It doesn't matter much, actually.

in order to do this you'd only need to consider up to 100 planets at once, less if you get to know an alliances size.

Which we obviously do.

then you can start with the largest planets and work down to including the smallest, so that you need to consider less combinations (or is it permutations? i think permutations, anyway, whichever is least).

Either works. Starting with biggest or smallest depends on the alliance, really.

once one alliance is done, you can remove them from the pool and repeat, so that you have to crunch less numbers with each alliance. if you start with the top alliance, then odds are you'll reach a solution quickly as you'll be looking at the top planets.

You're very clever. Unfortunately, top alliances have small planets too. Cog in the wheel.

in order to speed things up, i'd suggest looking for possible matches after a few ticks (doubt the first 24-48 ticks would be useful, as too many planets will be the same) and then once you find a solution that works for score only, checking its roids, and if that works then moving on to latter ticks. as there'll be few solutions that work for more than a couple of ticks this part should be fairly quick.

You're still pretty clever, you're pretty much restating the algorithm I used in my prototype.

also, as there are always leaks, the 100 member limit may well reduce. also, with buddy packs in this could provide a helping hand, if you consider people in the same pack to be likely in the same alliance, as it'll third the variations

Hm, hadn't considered buddy packs. Will have to have another look at how they work.

i have a gut feeling that looking at progression, rather than direct results might be quicker, but i don't see how at the moment. if it dawns on me i'll get back to you

Progression? Part of the problem is that there is no progression. You can never know if a planet fits into an alliance until you have a complete match. And again, there will be several erroneous matches for each alliance.

disclaimer: i made this all up in 5 minutes. there's no guarentee any of it's right

Most of what you said is pretty sensible, but it's still assuming matching of permutations, which we've already concluded requires too much CPU time to be feasible.


Also, generating all the possible matches, then checking them against alliance totals is not a good idea. It's just a variation on the other idea. Keep in mind that you'd be doing just as many checks as with computing the sums dynamically. This might sound like a good idea (hey, you don't have to compute the sums again!), but you'd never fit the list of indices into memory, and HDD seeks are a tad slower than summing.

Now, with all that said.

I don't want to use permutations to figure this out. I think that with clever use of statistics, a reasonably good 'possible' list can be found.

Also, Kloopy obviously has no idea what P =? NP is actually about. You look like you've read a slashdot article about it. The only security P = NP could have, and I must empasize that word, could, is that public/private key encryption flawed.

If you look at one tick worth of data, then yes, the problem is NP.

However, with the amount of data available, it's possible to approach the basic problem (find out what planets are in what alliances) in an entirely different manner.

What I want to do is look at who is most likely to be in an alliance. This is pretty easy, as alliances members follow a reasonably good distribution around the mean score/size. While the distribution isn't normal, it probably is a t-distribution (if I remember my stat101 correctly.) This means that we can infer a load of shit about who fits into an alliance profile for every tick. Then after collecting this data for say, 10-20 ticks, we can start using that data to decide who is more likely to be a member.

This method should provide more and more accurate descriptions of alliances as each tick passes. Not only that, but it should be possible to apply the same theory to changes in membership (ie when someone joins, there's a limited number of planets that fit the size/score differences.)

* Assuming normal distribution. If unfamiliar, choose z to be a reasonable number, say 10k score during the later parts of the round.

[velcrome]

its proven PGP is not even NP hard, since it just involves factorizing Blum-numbers.

But if I trust the voice of my stomach your alliance-problem is NP-hard, since all statistical approaches are rendered useless by the sheer mass of dynamics (read: chaos). We don't even have enough certainty (rather: mathematical models) of the PA universe to build a greedy algorithm.

[mist]

by progression, i meant the differences from tick to tick, rather than the hard numbers

that said, i can't think of a way of doing this without involving permutations at some stage.

the reason i started with larger planets and alliances is that traditionally there's less people with a load of score, although i guess that's truer later in the round.

using statistical modeling you could narrow down the amount of planets that you'd need to look at. however you'd still need to look at them all to ensure that you're not missing one out. also, finding the deviations etc for data that you don't yet know could be tricky.

didn't know you get to see the number of memebers an alliance has, i don't play pax - was just interested in your idea. if you do indeed get an alliance limit then i'd start work on the smallest (numbers wise) alliances first, however this would just reduce the pool...

-mist

[Tactitus]

Originally Posted by Jester

This is a pretty good argument to never ever tell anyone when a good method is found.

It's an even better argument why you should never discuss your plans on the public forums.

Were I PATeam, I'd already be changing the code so the dumps have nerfed numbers. I certainly wouldn't be sitting on my hands waiting to see if anyone could come up with a good matching algorithm.

But really, if the method is public, PA team should have no incentive to protect the large alliances from discovery, which is essentially what they'd be doing.

If you really thing that argument holds water, then just ask PATeam to release the member lists of all large alliances and save yourself a lot of coding. Good luck with that one.

[Jester]

Why should I keep it a big secret just because PAteam might have a kneejerk reaction?

[Gerbie]

As the search for a full list of large alliances is uncalcable (and probably has multiple possible outcomes) I would go for an optimization. A good start is eliminating the smaller alliances and work your way up there.

My point of focus would be the amount of roids within an alliance. This changes each tick and each tick there is only a very limited amount of planets taking/losing roids (problem: 2 planets from different alliances roiding the same planet at the same time). This should give you lists of a few possible members of each alliance. This will allow you to slowly eliminate your way through the universe (until you reach the point where the amount of permutations is small enough to try calculating the full list).
The outcome of this analysis is fuzzy (you cannot be sure whether what you found is correct as people might have landed multiple fleets at the same time etc.)
It is possible to increase the chance the list is correct. Since planets get XP, if you have a possible match (X roided Y), then you can check this by calculating the XP gain, to increase likelyness of the match significantly. By registering who can roid who you can significantly reduce the amount of permutations.

A major problem I see is that alliance member lists are dynamic. If you pinpoint a planet to be in an alliance and there is one planet leaving that alliance, then without a full list of members you cannot be sure whether the list you have is still correct.

If you added intel as a way to label planets, the search would again be a lot easier. It is already possible to label a significant portion of the most active planets a few weeks into the round by using intel only.

Once you have the most active planets, any less active planet that gains or loses roids is easily labelled.

Every time a planet is labeled it becomes benificial to reanalyse any earlier calculations this planet had a relevant effect on (reanalyse all ticks this planet gained/lost roids), but could not be solved.

[god113]

Okay, first the formula to how many possible sets of 100 you will have to check is: (amount unknown in alliance)^(Amount of possible planets). So presuming you know nothing with 4k planets, that's 100^4000 possible sets.

But most likely it isn't near that many. As you can use other information such as alliance average, and roids gained can also be used.

If you use 100^4000 as the primary way, then use the rest as filters.
So if you start at: 1:1:1 1:1:2 1:1:3 1:1:4 1:1:5 1:1:6 1:1:7 to calculate 1up co-ordes etc. Then it averages at maybe 1.5m for c1 (average planets), then knowing that the top 50 planets average = mabye 18m, means that you can be sure that the combination is wrong after 50 planets. But in reality it would be more like after 30 if the planets were small. So using this filter of 'average score' alone can make combinations of 100 void after 30-50 planets.

(Note, this can be used for the oppersite affect for working out small alliances)

Then the next filter, average roids. A simular principle, a rough guess from the top of my head is it could show a combination of 100 to be void after being half way through. Or maybe have more effect for biggest alliance. As this filter is more effective finding big alliances (as few small allie planets have lots of roids), maybe it could make the set of 100 void after 25-40 planets even.

Now we have roids gained and roids lost. It isn't as effective as a filter, but nevertheless it could still eliminate possibilities.

So presuming you don't know any information about any planet, then there are 100^4000 possible combinations, but using the combination of the different filters you could probably make each list void after 20-30 planets. And then you would maybe get 50 lists of 1up co-ordes being exact in score if you did it for one tick with the current stats. Then it would only take 2-3 ticks to find out which one of these is geniune, as the other combinations would become void in this time (as planets grow at different rates etc). So you don't have to redo the big search each tick, just check through the possible combinations you have already got the tick before (say if you even got 500, then it would only be maybe 5-6 ticks before you see which is real). Of course, you need to make sure that there is no change in teh memberlist over these ticks. Also, the data can be saved (eg, save dumps from PT 70-PT 80), so you can take as long as you like to process the information to find out a certain alliances memberlist over those ticks. Once you have a memberlist for a certain tick, then it's much easier to keep it updated using this system. As each tick at least 95% of the memberlist will be the same.

But you can narrow down even further by knowing certain planets status (as Gerbie said I think, find out the smaller allies first). I think that the largest and smallest allies will be the easiest to find the co-ordes of in such a system, and after that there are less free for the middle alliances.
And what could make the search even shorter is alliance intel from other sources. For example, if LCH are using this to find 1up co-ordes, they can cancel out their own planets. Also if you know 50 out of 100 of an alliances players at a certain tick, that's drastically reducing the amount of combinations (50^3950). And there's no reason why you couldn't have several machines running difference versions (if you arn't sure if information is solid, set a different machine to use that information and see if it works out). Or share the work load between difference machines.

One very important 'filter' I have forgotten to mention is the amount of roids. It can work in a simular principle to 'average roids' as a filter, as if you go over the amount the list is void. But it can also narrow down possible lists extremely quickly. As even if you have 500 possible lists one tick, then next tick very very very very few would have the exact roids/score again.

Anyway, that's the long way round. But even being the long way round, I believe it's very do-able. But unfortunately I know nothing about coding so I couldn't start on such a prodject myself.

I do believe there is a much easier way aswel, and that's by differentiating* from the alliances average. So having 100 planets closest to the alliances average, and then by making them differentiate from that average. This would lessen the amount of time needed as the chances are most planets are reasonably close to the average (opposed to having rank #1 planet and rank #4000 planet in same alliance). Obviously there are exceptions, but it's more logical doing this than going from 1:1

*I'm not sure if I used this in the right context, I mean starting from teh alliances average (eg if 1ups average is 10m, finding 50 planets either side of the 10m bit)

(Note, I didn't have time to check this. I was meaning to speak to Jester befroe posting (as he started the post) but he was NA. I spoke to ToF techie about this before who told me it was impossible unless they included alliance value aswel, but I remain unconvinced)

[Jester]

Originally Posted by Gerbie

My point of focus would be the amount of roids within an alliance.
---snip---
Once you have the most active planets, any less active planet that gains or loses roids is easily labelled.

Every time a planet is labeled it becomes benificial to reanalyse any earlier calculations this planet had a relevant effect on (reanalyse all ticks this planet gained/lost roids), but could not be solved.

This is very interesting, I hadn't thought of trying to match roidlosses and gains. This won't be easy during the 'active' ticks, but during the daytime ticks it should be possible to make a few good matches. Thanks.

I'm also convinced that fuzzy matching is the way to go.

Originally Posted by god113

Okay, first the formula to how many possible sets of 100 you will have to check is: (amount unknown in alliance)^(Amount of possible planets). So presuming you know nothing with 4k planets, that's 100^4000 possible sets.

Sorry, no. The amount of possible sets for an alliance with 100 members is approximately 10^200. Or number_of_planets binomial number_in_alliance. Also written 4000C100. This is stated clearly in my post, didn't you read it?

But most likely it isn't near that many. As you can use other information such as alliance average, and roids gained can also be used.

You obviously have no idea what you're talking about.

If you use 100^4000 as the primary way, then use the rest as filters.
So if you start at: 1:1:1 1:1:2 1:1:3 1:1:4 1:1:5 1:1:6 1:1:7 to calculate 1up co-ordes etc. Then it averages at maybe 1.5m for c1 (average planets), then knowing that the top 50 planets average = mabye 18m, means that you can be sure that the combination is wrong after 50 planets. But in reality it would be more like after 30 if the planets were small. So using this filter of 'average score' alone can make combinations of 100 void after 30-50 planets.

Sorry, this is wrong. 30-50 planets isn't a realistic cutoff. Did you try picking the 30-50 smallest planets and matching against the top50 planets? The difference is only 100 million (this was at tick 1650). There are ~1k planets with a score over 2 million. Now keep in mind that during the beginning phases of the round the difference is far less. It's an ok optimization, nothing great.

Then the next filter, average roids. A simular principle, a rough guess from the top of my head is it could show a combination of 100 to be void after being half way through. Or maybe have more effect for biggest alliance. As this filter is more effective finding big alliances (as few small allie planets have lots of roids), maybe it could make the set of 100 void after 25-40 planets even.

This is similar. It's of little consequence.

So presuming you don't know any information about any planet, then there are 100^4000 possible combinations, but using the combination of the different filters you could probably make each list void after 20-30 planets. And then you would maybe get 50 lists of 1up co-ordes being exact in score if you did it for one tick with the current stats.

At this point we've spent so many billion years that we'd better go looking for the fountain of youth right now if we want to know what's in any of those lists. I wonder if you have any concept of how large a number 10^4k is. And that's the wrong number! The correct number of possibilities is 10^200, and even that is so far outside the realm of possibility it smacks scifi in the face.

Then it would only take 2-3 ticks to find out which one of these is geniune, as the other combinations would become void in this time (as planets grow at different rates etc). So you don't have to redo the big search each tick, just check through the possible combinations you have already got the tick before (say if you even got 500, then it would only be maybe 5-6 ticks before you see which is real). Of course, you need to make sure that there is no change in teh memberlist over these ticks. Also, the data can be saved (eg, save dumps from PT 70-PT 80), so you can take as long as you like to process the information to find out a certain alliances memberlist over those ticks. Once you have a memberlist for a certain tick, then it's much easier to keep it updated using this system. As each tick at least 95% of the memberlist will be the same.

This is mostly correct, but still of little consequence as we can't actually find any of the permutations within our lifetime.

But you can narrow down even further by knowing certain planets status (as Gerbie said I think, find out the smaller allies first). I think that the largest and smallest allies will be the easiest to find the co-ordes of in such a system, and after that there are less free for the middle alliances.

Heh, which crack pipe did you smoke to find that out?

And what could make the search even shorter is alliance intel from other sources. For example, if LCH are using this to find 1up co-ordes, they can cancel out their own planets. Also if you know 50 out of 100 of an alliances players at a certain tick, that's drastically reducing the amount of combinations (50^3950).

It astounds me that you think 50^3950 is so much smaller than 10^4000 that it matters.

And there's no reason why you couldn't have several machines running difference versions (if you arn't sure if information is solid, set a different machine to use that information and see if it works out). Or share the work load between difference machines.

Running this program distributed would require a few million machines. Got a few crays handy?

One very important 'filter' I have forgotten to mention is the amount of roids. It can work in a simular principle to 'average roids' as a filter, as if you go over the amount the list is void.

This filter isn't nearly as good as you'd think.

But it can also narrow down possible lists extremely quickly. As even if you have 500 possible lists one tick, then next tick very very very very few would have the exact roids/score again.

Yes, once you have the full set of matching lists from a tick, it's trivial to check them.

Anyway, that's the long way round. But even being the long way round, I believe it's very do-able. But unfortunately I know nothing about coding so I couldn't start on such a prodject myself.

It's not.

I do believe there is a much easier way aswel, and that's by differentiating* from the alliances average. So having 100 planets closest to the alliances average, and then by making them differentiate from that average.

If you can find an algorithm to do this systematically (ie to include all permutations) then I'd like to see it. Even so, I don't think it would help. A top alliance will have players on both extremes of scale.

This would lessen the amount of time needed as the chances are most planets are reasonably close to the average (opposed to having rank #1 planet and rank #4000 planet in same alliance). Obviously there are exceptions, but it's more logical doing this than going from 1:1

The only thing that matters is that all possibilities are run through. Theoretically, the order should reflect the most powerful pruning that can be done, or rather the one that shows up the most often compared to value. But really, most of the difficult alliances have players on both sides of the spread, which basically makes this ordering difficult. It's also difficult for a machine to order this in a sensible fashion.

(Note, I didn't have time to check this. I was meaning to speak to Jester befroe posting (as he started the post) but he was NA. I spoke to ToF techie about this before who told me it was impossible unless they included alliance value aswel, but I remain unconvinced)

It's not impossible for that reason, and that wouldn't help. It's impossible because you have to check 10^200 combinations. Noting that one combination is stored in 32 bits, we'd need 32*10^200 bits memory to store them. That's more than all the memory in the world. Or even if we did 10^15 (more than your machine does) instructions per seconds, and 1 check was just 1 instruction. It'd still take us 10^185 seconds. That's more than the age of the universe, which is less than 10^20 seconds. So to make this problem even close to realistic, we'd need to reduce it by a factor of 10^150. Even at 10^50 this problem is unlikely to be solved within realistic time. So we can reject the long way around out of hand. I don't have a calculator that will do binomials this large for me, but 4500C6 was small enough to be done realisticly, 4500C7 (ie trying to find an alliance with 7 members) ran for 5000 minutes before I killed it.

[god113]

I see. Well, ty for the reply.

I guess the downfall of what I said was getting the original '100^4000' thing wrong, and also not knowing how long it would take a computer to process so many calculations.

As you may have seen, i'm not really knowledgable on the coding side of this, but the subject interested me a while back.

[Gerbie]

I'm not an expert on statistical methods (I passed the exam by a narrow margin). The best way to do it i.m.o. would be to calculate for each planet a likeliness that it is a member of the alliance. You could use intel, and like god113 proposed average score, average roids etc. Also you could use correlations with alliance roidchange (for ticks you could not solve) and scorechange (correct for the planets you know).

With a n member alliance, start a loop with x=0:

take a group of n+x most likely candidates.

Use some filters like:
-the score of the 49 smallest planets+largest planets (in score) in the selection should >= alliance score (or remove the largest planet from the selection)
-the score of the 49 largest planets+smallest planet <= alliance score (or remove the smalest
-(similar for value and roids)

asume the planet ranked n+x is correct

next step is to calculate all permutations

x=x+1 and do the same again.

This way you can check all combinations of the most likely candidates first.

Once you found a match: don't continue checking for all possible outcomes: if it fits, and it also fitted the tick before (no change in amount of members), then asume it is the correct list).

[Blazde]

I looked into this problem quite a bit when I played PA. Practically I decided there wasn't much point in the end. Our quality intel in Elysium always did a decent job of finding hostiles and at the point where the info is most useful (very early in the round) the problem also seems at it's most difficult. There was some other issues with getting accurate data (see below) that put me off as well.

From a mathematical viewpoint I'm still interested if it's possible. However, I don't think you'll find a decent solution just by thinking about it, or discussing it on these boards. It's a tricky problem, no doubt about it. The thing to do is to trawl the mathematical research and ask for help on some math mailing lists (preferably without mentioning Planetarion, mathematicians get turned off as soon as they know something has a direct application ).


This is somewhere around where I got to:

If you take a single tick of data the problem is a special case of the 0-1 Knapsack problem often called the Subset Sum Problem:

(ripped from a text book, cos it really is easiest written this way)

Given integers c_j, j = 1, ..., n and K, is there a subset S of {1, ..., n} such that
Sum(c_j) where j is a member of S = K

In english, you have some items of different weights and you want to put some of them in a knapsack with a certain capacity, so that you make full use of that capacity.

(In this case the weights c_j are the planet's scores and the capacity K is an alliance score. And you need to solve the problem for each alliance.)

In the more general 0-1 Knapsack optimisation problem there's a 'profit' associated with each weight:

q_j, j = 1, ..., n

and the aim is to maximize the total profit without exceeding the capacity (it's acceptable that the sum of weights is less than the capacity).

Maximise
(Sum(q_j) where j is a member of S)

Constrain
(Sum(c_j) where j is a member of S) <= K

Most of the literature will talk about it like this but it's the same as the more specific subset sum problem if you set the profits to be identical to the weights, so the 'profit-density' is the same for each item. (Although it might be useful to bias the profits very slightly to make use of known inteligence about a planet's alliance, or from information gained from previous inexact solutions). And since you know there's a solution which sums to the capacity, not less than it, optimal solutions for the inequality version will be the solutions of the equality version.

Much of the (succesful) research in this problem is to do with inexact (non-optimal) solutions. Which in this case means you'll get a set of planets who's score almost but not quite adds up to the alliance score. There's simple polynomial time algorithms which will give very good solutions, probably in a matter of seconds on problems of this size. Google on dynamic programming. But these don't seem to be of any use in this case. Random collections of planets with a total score fairly close to an alliance score will say nothing about which alliances those planets are, they are just that: random collections of planets. The known inexact algorithms probably won't pay attention to the alliance's member count, it's very likely they'll 'fill in the gaps' with huge amounts of small planets and you'll get a solution of ~2000 planets where the alliance only has 100. Of course the algorithms might just come across the correct solution, but I don't feel it's that likely.

The exact algorithms may not pay attention to membercount either, but if you assume there is only 1 exact solution they will come across it, and the member count will be correct (ignoring 0 score planets ofc). Subset Sum and 0-1 Knapsack are NP-Complete. That doesn't neccesarily mean it's hard to find the optimal solution but all the evidence does indicate (according to the mathematicians) that 'typical' instances are very hard. There are some algorithms which will solve specific classes of the problem efficiently, but I haven't found any yet that are relevant. But of course you have more data to use yet...

Planet/Alliance Size.

Using the planet size and the alliance (roid) size, you have a second knapsack. Technically I think the problem now becomes a "Two-Objective Two-Dimensional 0-1 Equality Knapsack" problem. Two dimensional because each item has two weights and the knapsack has two capacities (score and size). Two objectives, because the profits associated with each knapsack are different (again the profits are just the same as the weights in our case). At this point the literature gets confusing because Objectives are often confused with Dimensions (also known as multi-knapsacks). And the word Constraint is often used in place of either. Google various combinations of the following: "multi-knapsack" "multiple knapsack" multidimensional contraint objective two-constraint two-objective two-dimensional. Etc..

For exact solutions multiple objective/dimension knapsacks are generally classed as a more difficult problems, but that's only because it's worst-case complexity is greater. In the case of the planetarion data where we're after a single optimal solution it's probably quite a bit easier.

This paper might of some help:

"An Exact Algorithm for the Two-Constraint 0—1 Knapsack Problem"
http://www.extenza-eps.com/extenza/l...&type=abstract

If someone can access it (people with ATHENS access) I wouldn't take offence, ahem, if someone spammed it into my mailbox

(Of the papers I have read, nothing has jumped out yet as being directly applicable, so I'm not gonna post loads of links here)

The size might also be of some use is in getting decent solutions from single-dimensional inexact algorithms. For example, apply a fast inexact algorithm to the score data, then again to the size data. Planets which appear in both solutions may be more likely to be in the actual solution.

A problem however is that the size is unreliable. A player can initiate roids after the alliance totals are dumped, but before the planets sizes are dumped. This means the sizes of the planets in the dump don't always add up to the total alliance size. (If you're sceptical you can see the same effect more easily in galaxy totals). The window of time is significant, 2-10 seconds at a guess. Especially early on in the round you can guarantee quite a few people have hit the window (everyone rushes to initiate roids at the start of the tick).

I think the same problem might affect the score data, since it's possible for scores to change at times other than at the tick. For example if you make/recieve donations iirc. But it's much less likely to screw up the data, and you can be sure it won't in the first 72 (48?) ticks.

Multiple ticks.

If you can find (or guess at) a stretch of n ticks where the alliance that you're working on has a static membership (ie. their membercount doesn't change and you hope they didn't lose and gain an equal number of members in a single tick) then you have a "n-Objective n-Dimensionsal 0-1 Equality Knapsack" problem (or 2n if you use the less reliable size data too). There's algorithms to solve large objective/dimensional problems (of the order of 10-100 as you'd get here) but they're exclusively inexact, focusing on fuzzy/genetic techniques because the search domain is so huge. However I think they might be useful, especially early on in the round when the size/scores change rapdily from tick to tick. A solution which closely fits erratic size/score data over multiple ticks is very likely, imo, to include many of the correct planets. Then you try to combine results from multiple stretches of alliance history into meaningful info. Crucially, the correct biggest planets are more likely to be part of the solutions, and these are the ones of most interest. And it might even still get good results if the data is 'fuzzed' by the PA coding people trying to stop you analysing the dumps like this. So this is about the best lead I had, although I never tried coding anything.

Membercount.

It might help if you can track down what the mathematical lingo is for knapsack instances with a target number of items to put in the knapsack. However, I think you could also model it as yet another constraint and dimension. Simply set the weight and profit for each planet to 1 and the target value K to the membercount. Now you'll get solutions with the maximum number of planets possible <= the membercount, and you'd hope that even the inexact algorithms would do a good job of hitting the correct membercount on the head.


Finally you could try bringing all the alliances together into a single problem instead of searching them individually. (Note that the set of no alliance planets is just like another alliance, and you can calculate it's membersize, roid size and score easily). The advantage is that you enforce the constraint that a planet can't be in multiple alliances. The disadvantage is that it's more difficult to include multiple tick data (because at least one alliance is likely to change membership each tick), and there seems to be less research into this problem. For a single tick of score data it could be called "Multiple Subset Sum Problem with Different Capacities". I won't even try to name multi-constraint/dimension version that comes with multiple tick data because I'm sure I've already named stuff wrong but Google on: "multiple knapsack" and "bin packing" as well.

Good luck

[Jester]

THANK YOU BLAZDE.

Adding target number to Knapsack turns it into Subset Sum. According to Garey / Johnson (Computers and Intractability) there's pseudo-polynomial time solution to SS, and there's a good looking page about it on wikipedia, but I really cba to get down and dirty with it right now.

Again, thanks for the input. The more I look at the problem, the more I wonder what the hell I was thinking. The scary thing is that I still want to make the system. I just want to put it off longer so I can spend more time on it to make it better so I can have more info. Not that I have any idea how that works out. Guess I'll have another look it when I recover from my current case of brainmelt.