Hello, (This problem is probably too computationally intensive to solve with Python, though Python + Cuda could be interesting, and also Python has some interesting expressive powers, so it could be interesting to see how Python programmers might be able to express this problem with Python code, so I am going to give this Python group a try... maybe it will surprise me ! :) At least now you have a nice computational problem for those boring rainy days (when the net is down?and the offline games bore you ;) LOL :))
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 ?! Also for the python newsgroup: Maybe python is more powerfull than I thought and it has some weird/kinda crazy/cool new permutation/combination algorithmic classes that can solve these kinds of problems faster than just the average run of the mill general code ! ;) (Or perhaps build in solver support, that will be my next try/posting :P :)) Bye, Skybuck. -- https://mail.python.org/mailman/listinfo/python-list
