Hello, There are two groups of numbers which try to destroy each other: Group X = 1,2,3,4 Group Y = 1,2,3,4 There is a 4 by 4 victory table which describes the chance of a number destroying another number: Victory table = 50, 3, 80, 70 90, 60, 20, 40 30, 90, 55, 65 75, 90, 98, 60 (Currently implemented as a chance by diving it by 100 and storing as floating point, but since these are subtracted only from 1.0 I guess they can be stored as integers instead, even bytes) This leads to the following computational problem as far as I am concerned: Each number has an attack order permutation as follows (factorial 4 = 1x2x3x4 = 24) 1,2,3,4 // 1 1,2,4,3 // 2 1,3,2,4 // 3 1,3,4,2 // 4 1,4,2,3 // 5 1,4,3,2 // 6 2,1,3,4 // 7 2,1,4,3 // 8 2,3,1,4 // 9 2,3,4,1 // 10 2,4,1,3 // 11 2,4,3,1 // 12 3,1,2,4 // 13 3,1,4,2 // 14 3,2,1,4 // 15 3,2,4,1 // 16 3,4,1,2 // 17 3,4,2,1 // 18 4,1,2,3 // 19 4,1,3,2 // 20 4,2,1,3 // 21 4,2,3,1 // 22 4,3,1,2 // 23 4,3,2,1 // 24 (These attack orders can be numbered from 1 to 24 or 0 to 23 and then it's attack order/permutation can be looked up to safe memory.) Each number has it's own attack order and thus this leads to the following combinational computational problem: All combinations of permutations in which order group X can attack Group Y and vice versa: Group X = 24 x 24 x 24 x 24 Group Y = 24 x 24 x 24 x 24 So this is 24 possibility to the power of 8. Final computation complexity at the very minimum is (24 to the power of 8) multiplied by roughly 4 attacks perhaps even 5 or 6 to finally destroy a group of numbers. 24 to the power of 8 = 110.075.314.176 I have already written a computer program which can solve this, however the computer program estimates it takes 19 hours on a 2.0 gigahertz AMD Athlon X2 core. Using dual core could solve the problem over night, though I do not feel comfortable running my PC at night unattended. So now I have the idea to make this program run when my computer is idling during the day, it should also be able to store it's progress so that it can continue after it was shutdown. (Idea for now is to make it multi threaded and assign a low thread priority so it can run during the day when I use my computer and it's not doing much so it can use the reserve computational horse power). (I still have to try these "idle/reverse" ideas to see which one works best without interrupting my web browsing or music listening too much ;)) My system has 4 GB of ram, so other ideas could be to store a data structure partially which could keep some computations so that it doesn't have to be done again... Though memory lookups might be a bit slow so not sure if that makes any sense. I might also try GPU/Cuda since there seems to be lots of loops/reoccurences of the same computations that will happen over and over again... So maybe cuda can detect "same branch execution" and some "computations" and might speed it up, not sure about that. Just the 8 index loops already cost a lot of instructions. Since there are only 24 permutation it would be enough to store it in 5 bits. Perhaps a rounded floating point which increases by 1/24 might be enough to trigger the 4th bit from incrementing when it actually needs to. 2x2x2x2x2 = 32 (it should increment bit 6 when the 5 bits reach 24). So the idea here was to create 8 indexes from just 1 index being incremented to create the 8 combinations of indexes "instruction cheaply". Not sure if this will work, just an idea I might try :) Then those bits would still need to be extract and makes. So perhaps on older systems this is not efficient. The 8 indexes need at least 3 instructions, 1 index increment, 1 comparision, 1 jump. The inner loop contains some while loops to increment attack index per number. Each number has a "alive" variable which starts at 1.0 and is decreased everytime it's attacked. Once a number is dead below 0.0000001 it's considered dead and can no longer attack. (Since victory table was described as integers above this can also be read as: Alive starts at 100 and once it goes zero or negative it's dead). Anyway the main reason why I wrote to this/these groups is that the numbers themselfes are not that larger and can fit in a byte, even a few bits. Thus they will fit into SSE registers and such and I also know SSE has some permutations instructions. I am not expert at SSE but I am wondering if there are perhaps some SSE1/2/3/4/5 instructions which can help at solving/computing this problem ? Now the question you might be wondering about is ? What am I actually trying to compute ? Well the final output could simply be the number of victories that each attack order has had per number. I am particullary interested in victories of number 4. So that would be sufficient for now. Number 4 has 24 permutations. So I want to know how each permutation of number 4 performs under all other circumstances/permutations of all other numbers/combinations and so forth. This basically requires the entire set to be computed and then record number of victories for for example Group X number 4. Only the results of one group needs to be outputted since the two groups are a mirror of each other. Also during the development of the computer program I finally had a successfull implementation by keeping it as simple as possible and working with direct variables, instead of much more complex arrays. Later on I made a more code efficient version which uses arrays/lookups and such. It was much harder to try the array approach at first since it becomes mindly complex and can obscure "vision to a solution". So I suggest anybody trying to implement a solver for this to keep the code as simple as possible at first, since this is already an 8 dimensional problem with a 9th dimension. Also it was interesting to see the Delphi for loops not allowing array fields as loop variables, so those loops will need to be fleshed out anyway, or one big linear loop could be used and then 8 indexes calculated from that. That approach will probably be necessary for a cuda solution anyway... 32 bit might be sufficient if remainders are reincluded in the conversion from thread/block dimensions to linear dimension back to 8 dimensional indexes. Perhaps such computation might even be a bit quicker than the 3 instructions per loop. For example 8 divisions and 8 remainders will be necessary to compute 8 indexes from one big linear indexes. Since div/mod can be the same instruction this might only require 8 instructions to compute these loop indexes from a big linear index. However computing the big linear index already requires between 6 or 10 instructions. So just to compute those 100+ billion data entries requires something like 20 instructions just to be able to compute those loop indexes. This is my finding with bigger data sets which consists out of small little data units... The closer the number of entries/data items get to the actually processing computing power the more time/processing/instructions are wasted on just computing these loop indexes. It makes sense from this perspective: A problem of 100 items only needs 100 loops. Thus lots of processing power remains for the data. But for 2 billion data items, the number of items already matches the gigaherts of the core... so the core is already swamped... with just loop index calculations. I hope this reasoning/explanation convinces some CPU/GPU designers to include more instructions to compute loop indexes in all kinds of ways that could speed that up somewhat and safe some processing time. Anyway... let me know if you think SSE could be of some help in solving this permutation/combination problem ?! Bye, Skybuck.

0 |

12/9/2016 12:14:08 PM

Hello, I received a reply from somebody on my ISP newsserver. Apperently his reply= is not visible on google groups. I wonder why, maybe it's a banned troll o= r something, but perhaps not. Anyway... my ISP has problems accessing their newsserver. They won't offer = the service to new customers or changing subscriptions and they lack softwa= re to access the server. The server currently has a technical problem. Uplo= ading messages is not possible. Some kind of bug... this has been going on = for months. Seems like the bug will be ever lasting. Just called ISP helpdesk... I forgot to ask them if they could simply reset= the server... but with the little information I was giving it seems to be = a "remote control problem". The server is probably remotely controlled and somehow that remote control = has been lost... Either password lost, or software is not working anymore..= .. kinda strange story... especially for such a large ISP which should have = sufficient technical people to solve this... weird story isn't it... perhap= s they just don't want to fix it to drop people of of it.... This kinda sucks for me because using usenet via google newsgroups complete= ly sucks... and is like 1.000.000 times more difficult with this very lacki= ng interface. But for messages that I consider worth it... like this one, I might keep on= going(/presserve? gotta look that up in dictionary) for now... :) Anyway here is my reply, it might enlighting others as well to this exact p= roblem: >So now I have the idea to make this program run when my computer is idling >during the day, it should also be able to store it's progress so that it >can >continue after it was shutdown. > " Periodic snap-shots of the running environment will likely take up a majority of the run-time. " (Since you the only one who has replied so far I will take some time to try and answer some of your questions to help you along and perhaps it will be usefull to others as well). Haven't implemented this yet, but I don't see why that would be the case. It would probably need to store very little. Only 8 indexes, and perhaps 4x24 entries so that's nothing. This could be then everything index4 increments for example, or index 3. Somewhere below in this posting I will give some pseudo code for the indexe= s since it seems you might be struggling with that a little bit or you are trying to solve it a different way which is interesting to see but in this case I don't think it's better so I will adjust you there, but first I reply to the rest of your posting so the pseudo code will be somewhere below... " Especially if your idea is to first generate two lists of the permutations of the inputs " The permutations were already given by me in my original post. No further permutation lists are needed. The permutation table was simple generated with some 1234 string with some Delphi code found from the internet. Generating permutations is not the real issue here, since there is code on the internet which already solves that. " then generate a list of the "combat" permutations, and you want to be able to store-off/reload all those lists. " I don't see why it would be necessary to store any lists at all, except fro= m the permutation table as to avoid having to implement a complex permutation algorithm. Generating permutations is a topic in itself so I tried to avoid that by simply hard coding the small permutation list into the code to side step that sub problem. Generating/storing/loading any kind combination list would either not be possible because of lack of memory or would require way too much time. What should however be stored is the number of victories for each permutation. >(Idea for now is to make it multi threaded and assign a low thread priorit= y "It's CPU-bound, so using multiple threads for the computation won't be that effective..." I disagree, the problem is pretty straight forward and can be split just fine by duplicating some simple indexes/data structures. And should be able to run on each core at nearly 100% efficiency. The results could be merged together at the very end. At least in Delphi/native code this will work nicely... "You add the system overhead of context switches between the threads, and for common Python, you run into the GIL (so even if you get subsets of processing assigned to each of multiple processor cores, the GIL will block all but one from doing any work at any moment -- say you partitioned it so core0 handles only the set where X begins [1, ...], core 1 handles [2, ...], etc.). " Your last sentence made the most sense to me... I don't know what GIL is or if Python has any multi threading issues or overhead. I would assume it would not be to bad concerning overhead and that python threads can run pretty efficient as well, if not that would surprise me a little bit. Ofcourse there would only be 2 threads since it's a dual core system. If yo= u ment running more than 2 threads then yes there would be context overswitch overhead. But why would anybody want to run more threads than the number of cores ?! ;) Since it's not necessary to run more threads to divide up the problem. >so it can run during the day when I use my computer and it's not doing muc= h >so it can use the reserve computational horse power). >(I still have to try these "idle/reverse" ideas to see which one works bes= t >without interrupting my web browsing or music listening too much ;)) > <snip> " Not seeing any code makes it hard to estimate where your slow-downs would be, however all your mentions of keeping "index" values implies (as I mention above) that you are trying to build huge tables of permutations first, then beating each entry against those of the other. " I quickly realised that this approach (generating huge lists) won't work because out of memory. So instead each possibility is simply calculated and only results are stored. "In truth, I can't figure out what you consider a combat" I did not use the term "combat". I do think of them as "attacks". We could define "combat" as simple "one of the possibilities". So let's look at a single possibility to explain it to you. I will simply produce a random index example: Index1: 7 Index2: 22 Index3: 12 Index4: 10 Index5: 4 Index6: 9 Index7: 11 Index8: 5 Now the task for program is to calculate the outcome of battle. The program will eventually lookup the permutations from the permutation table so let's get those first: First let's copy & paste the permutation table from original posting: 1,2,3,4 // 1 1,2,4,3 // 2 1,3,2,4 // 3 1,3,4,2 // 4 1,4,2,3 // 5 1,4,3,2 // 6 2,1,3,4 // 7 2,1,4,3 // 8 2,3,1,4 // 9 2,3,4,1 // 10 2,4,1,3 // 11 2,4,3,1 // 12 3,1,2,4 // 13 3,1,4,2 // 14 3,2,1,4 // 15 3,2,4,1 // 16 3,4,1,2 // 17 3,4,2,1 // 18 4,1,2,3 // 19 4,1,3,2 // 20 4,2,1,3 // 21 4,2,3,1 // 22 4,3,1,2 // 23 4,3,2,1 // 24 Now let's retrieve the permutations for the indexes: (instead of calling it a permutation I will now call it an "attack order"): Index1: 7 Attack order: 2,1,3,4 Index2: 22 Attack order: 4,2,3,1 Index3: 12 Attack order: 1,3,2,4 Index4: 10 Attack order: 2,3,4,1 Index5: 4 Attack order: 1,3,4,2 Index6: 9 Attack order: 2,3,1,4 Index7: 11 Attack order: 2,4,1,3 Index8: 5 Attack order: 2,1,4,3 Now the computer program can perform the combat. However perform I explain further how a combat would be performed I will tr= y to answer the rest of your questions: ", what you consider a number," A number is a tag uppon an object. The object could be a ship, a tank, an airplane, or whatever the real world scenerio is behind the problem. I was considering mentioning this, but I thought it let it out just for the fun of it. Consider "number" the number of the object performing the attack= .. Perhaps giving some context to these numbers might have helped to imagine the problem better. If this is indeed the case then perhaps a little "sorry= " might be in place. Numbers usually don't fight each other... so that concept/idea is kinda weird/vague... I was kinda hoping that people would find it a bit funny... but could see through that and understand by themselfes that these numbers probably could represent a solder,tank,plane,ship and so forth. I also want to conceal what this program will be used for just to thart any possible/potential enemy that might read these postings ! :) But if you must know it's written to help me understand which attack strategies work better and which work less well in a specific online game..= .. but that's all I will say about it... perhaps you can now already interfere which game it might be ;) "nor how your result table works" Hmmm fair enough point I guess perhaps that wasn't so clearly described. If you want me to give you an exact definition then fair enough. The results table is simply the number of numbers on each team dimensionall= y multiplied by the number of permutations (=3Dattack orders). So since momentarily the team consists out of 4 contenders/numbers and sinc= e attack orders are 24 the entire result table would be a 2D table: 4 by 24. "you don't identify x vs y" X is a group Y is a group I think this was pretty clearly defined ? However I can see how your question might be related to the victory table since you seem to be unsure what the rows and columns represent. I was kinda hoping that you would automatically understand what it ment based on the description of "numbers fighting each others". But perhaps tha= t description was too vague and too multi-interpretable. Or simply too confusing/unclear to what it relates. To put it simply: The victory table describes the "number to number" attack chance. Which means the individual chance of an individual number attacking another individual number. In other words the victory table has nothing to do with the groups themselfes. Since there are only two groups I don't see how a victory table could be related to the groups themselfes. However the groups were tag as X/Y also t= o prevent confusing with the speaking term "a table", "a bank", "a bike". However now that I see me writing this table if you plot the table versus the x-axis and the y-axis... and put some numbers on it... it might have been more clear. I am afraid that apperently it's still not clear ?! So I will have to explain harder... at least for you... maybe for others two... perhaps an example will help to clearify how the Victory Table is to be used. Also perhaps I should have mentioned that each number is also a type. That might have made it more clear how the envision the victory table. So to help you understand I will now describe that number 1 could represent a horse, number 2 could represent a tank, number 3 could represent a plane, number 4 could represent a ship. What the numbers/types truely represent will remain concealed for now to thart any enemies reading this text :) However I hope by "applieing" types/classes to the numbers that maybe now i= t is starting to make some sense to you. The victory table basically describes what the chance is that for example a horse will win from a tank. Or what the chance will be of a tank winning against a ship. Or what the chance will be of a plane winning against a ship. So basically the Y-Axis describes the source=3Dattacker So basically the X-Axis describes the destination=3Dtarget Finally the chance in the table itself thus describes the chance of the attacker killing the target. (The chance could also be interpreted as "damage done" which is actually what my code uses for now). ", and since it is not diagonally symmetric that makes a difference... " I don't quite understand this sentence of yours... a bit weird... but I guess this was because of your confusion and because you trying to sum the entries in the victory table for some reason, which is because of misunderstand... it's not necessary, I hope to have cleared that up above and will continue with an example below. "nor do the rows/columns sum to 100%)" Not required. Finally an example. Let's say a horse attacks a tank. What would it's chance of winning be ? Let's first define the numbering as describes above: Horse=3D1 Tank=3D2 Plane=3D3 Ship=3D4 Let's re-examine our victory table: Let's apply some row/column numbering perhaps that will clearify it a bit for you. 1 2 3 4 1: 50, 3, 80, 70 2: 90, 60, 20, 40 3: 30, 90, 55, 65 4: 75, 90, 98, 60 Now the program wants to know what is the chance of a horse defeating a tan= k ? So horse =3D 1 So proceed to row. So tank =3D 3 So proceed to column 3. This gives the horse a winning chance of 80%. Ofcourse this makes completely nosense with these horse, tank, plane,ship descriptions. But I hope you get the idea. So finally what could a possible solution program do to calculate outcome o= f battle ?!? Let's proceed with the example: Index1: 7 Attack order: 2,1,3,4 Index2: 22 Attack order: 4,2,3,1 Index3: 12 Attack order: 1,3,2,4 Index4: 10 Attack order: 2,3,4,1 Index5: 4 Attack order: 1,3,4,2 Index6: 9 Attack order: 2,3,1,4 Index7: 11 Attack order: 2,4,1,3 Index8: 5 Attack order: 2,1,4,3 Index 1,2,3,4 belongs to group X index 5,6,7,8 belongs to group Y (5,6,7,8 renumbered as 1,2,3,4) From the information above it's now clear how group X will attack group Y and how group Y will attack group X. X1 will first attack Y2 X2 will first attack Y4 X3 will first attack Y1 X4 will first attack Y2 Y1 will first attack X1 Y2 will first attack X2 Y3 will first attack X2 Y4 will first attack X2 From looking at this first round of attacks from above it's already pretty clear that Group Y has "chosen" to attack X2 with 3 objects. Thus it's very likely that X2 will be destroyed. Funny enough groupX is also attacking Y2 but only with 2 objects. So Y2 is also likely to be destroyed but a bit less likely. How the program now proceeds with calculations is open to debate. There are two possibilities: Either the program considers X2 destroyed if the chances are subtracted fro= m 100 and it goes below 0. (The chances are lookup in the victory table as describes in the example above for horse vs tank). This I would call the "dynamic" approach... it complexifies the problem somewhat... a number which is destroyed cannot further attack so it will no= t take part in the next round of attacks. However another approach could be taken which stays more true to the concep= t of a "decision tree". Instead of subtracting the chances, the chances could also be multiplied... this will reduce the chance of X2 being alive, but it is still allowed to participate in the fight assuming it had a very low chance of surviving but might have miracously survived. T= o compensate for this perhaps further attacks from X2 should have it's chance of success reduced... to make the computation a bit more realistic but stil= l computationally easy to do: just a multiplication, no branches. So for now I will explain how my program proceeds. Without actually looking up the chances... which would be a bit much work to do... I will simply assume that X2 died and perhaps Y2 too. So the next round commences as follows: (attack targets/indexes acquired from attack order from above): X1 will first attack Y1 X2 (destroyed) X3 will first attack Y3 X4 will first attack Y3 Y1 will first attack X1 Y2 (destroyed) Y3 will first attack X4 Y4 will first attack X1 Perhaps after this second round Y3 is destroyed, perhaps X1 is destroyed So round 3 commences: X1 (destroyed) X2 (destroyed) X3 will first attack Y2 X4 will first attack Y4 Y1 will first attack X4 Y2 (destroyed) Y3 (destroyed) Y4 will first attack X4 Apperently group Y had the more lucky permutation of attack orders, here they jointly attack 4 so it's likely 4 was described which gives them a better chance of winning since now they are +1 vs the enemy, while Y2/Y4 ar= e only damaged but not yet destroyed. Let's see what happens in potentially the final round: X1 (destroyed) X2 (destroyed) X3 will first attack Y4 X4 (destroyed) Y1 will first attack X2, cycles to X1, cycles to X3 Y2 (destroyed) Y3 (destroyed) Y4 will first attack X3 Here my program if I remember correctly will detect that enemy X2 is alread= y destroyed so it's starts cycling/wrapping it's attack order index to find which one it should attack next until it finds X3 still alive and attacks it. (First Y1 tried X1 according to it's attack order "table" but X1 is also already destroyed so it proceeds to X3). From this "permutation" example it seems likely that X3 was destroyed and group Y might be the winner. However if group Y is truely the winner will depend on the actually victory chances... perhaps something weird occured and one of the objects was easil= y destroyed by a high victory chance... even though it was 1 vs 1... thus thi= s might have completely altered the outcome of battle. So that's what the computer program will have to do/compute. Also finally let's look at the results table. For this outcome the results table would be adjusted as follows: Group Y won, so no adjustment. Only Group X is examined, since it's a mirro= r of each other. However let's assume that the exact same battle happens but vice versa. Group X/Y swapped. In that case the results table would be adjusted as follows: Index1: 7 Victories +1 Index2: 22 Victories +1 Index3: 12 Victories +1 Index4: 10 Victories +1 This basically means that the permutation 7 for object 1 has +1 victories independently record of what the rest did. This basically means that the permutation 22 for object 2 has +1 victories independently record of what the rest did. This basically means that the permutation 12 for object 3 has +1 victories independently record of what the rest did. This basically means that the permutation 10 for object 4 has +1 victories independently record of what the rest did. So basically in C/Delphi like terminology: ObjectPermutationVictories[1,7]++ ObjectPermutationVictories[2,22]++ ObjectPermutationVictories[3,12]++ ObjectPermutationVictories[4,10]++ *** Continueing with the rest, unrelated to above *** (By the way I made a little typo in this weird text below 3th should have been 5th, I thought 3 bits would be enough but it actually needed 5 bits): " Just the 8 index loops already cost a lot of instructions. Since there are only 24 permutation it would be enough to store it in 5 bits. Perhaps a rounded floating point which increases by 1/24 might be enough to trigger the 5th bit from incrementing when it actually needs to. 2x2x2x2x2 =3D 32 (it should increment bit 6 when the 5 bits reach 24). So the idea here was to create 8 indexes from just 1 index being incremente= d to create the 8 combinations of indexes "instruction cheaply". Not sure if this will work, just an idea I might try :) " If you don't understand this crazy idea above in quotations then you can safely ignore it. It is not used it was an experimental thought how things might be done differently in regards to advancing the indexes. *** Now continueing with the rest of your questions " >>> import itertools >>> for x in itertools.permutations("1234"): .... xout =3D "".join(x) .... for y in itertools.permutations("1234"): .... print xout, "".join(y) .... 1234 1234 1234 1243 1234 1324 1234 1342 1234 1423 1234 1432 1234 2134 1234 2143 1234 2314 1234 2341 " I don't quite understand that python code, but I can imagine what it might be doing... but it's probably not correct, it's too simplistic. Or perhaps this was just to generate the permutations. As I wrote above... generating the permutations is not really the problem, they can be looked up from the permutation table. " Replace the print with something to compute just the win/loss stuff for the single x vs y, and save the result off -- since I couldn't work out your scoring I can't say if a dictionary keyed by the permutation makes sense... " For now I will not reply to this... there seems to be some understanding i= n what you wrote... but for now I will wait to see if this new reply of mine will have clearified a lot for you and thus perhaps I do not need to respon= d to the text above. " And are you generating random numbers to determine the winner/loser? " No, brute force is applied to calculate which group wins, in case you ment which group wins/losses. If you ment which number wins, then that is giving by a chance lookup and perhaps a health variable per object which is decremented. However you are free to decide what to do... kill of numbers ? keep them alive ? Use a different way of reasoning what should happen to them. The victory chance should be applied somehow though. It definetly should influence the outcome of battle somehow= .. " How many cycles -- loop on random values until one or the other is "dead"= .. " A "while loop" which examines the "alive status" of each number/object is used to examine if the battle came to an end. As long as each team has an alive member the fight/combat continues. Once the numbers of one group are completely destroyed, the other group wins. In case both groups destroy each other at the same time, it's a draw. "What is the statistics? How many combats the digits took (ie, number of cycles of random)... How many it took for all four digits to die?" Nice question. This depends on the approach taken. I decided to take a "natural" feeling approach, which I call the "dynamic approach". The combat for each possibility is continued until one group dies. Therefore it's hard to say what the exact number of "rounds" or "cycles" as you call them it will take= .. However it will probably be something like 4 or 5 cycles. This is kind of a= n interesting question. Some additional statistical analysis variables could be added to the code to track what the average number of rounds is, what th= e minimum was and what the maximum was ! Thanks for this feedback it's kinda interesting ! ;) Bye, Skybuck.

0 |

12/15/2016 11:30:01 AM

<skybuck2000@hotmail.com> wrote: > This kinda sucks for me because using usenet via google newsgroups > completely sucks... and is like 1.000.000 times more difficult with this > very lacking interface. You could try nntp.aioe.org. No password or registration required. -- Mvh./Regards, Niels J�rgen Kruse, Vanl�se, Denmark

0 |

12/17/2016 11:28:34 AM