Best attack order for groups of numbers trying to destroy each other, given a victory chance for number to number attack.

[skybuck2000 at hotmail.com]

Skybuck wrote:

"
Also keep in mind that an attack is only valid if the target is still alive, otherwise the attacker would move to the next one.
 
So pre-computing an attack plan/outcome or storing it might not be so usefull for on color, since the other color might already be dead and thus attack plan was calculated incorrectly potentially.
"

^- Apperently this text/posting was essential/the key for Skybuck's Magical Brain to come up with a solution !

I love how Skybuck's Magical Brain comes up with solutions after some sleep ! =D

Just need to input the problem before sleeping, then in the morning ! TA-TA: Solution ! =D

I just woke up, thought a little bit and then came up with the following solution !

The problem with the lookup/intermediate table is ALIVE/DEATH of own object (also teammate objects), furthermore another problem is ALIVE/DEATH of enemy object(s).

So now the solution is obvious ! A special lookup table as follows:

(Furthermore I just had another idea to compute an enemy health reduction or perhaps enemy health outcome, both are possible ! ;) Yeah... enemy health calculation probably possible and accurate, since alive/death of enemy also known on input and thus result can be calculated/stored in table ! ;)

EnemyHealth (could also be EnemyHealthReduction if that were necessary for some reason ! ;) total damages would be summed, but probably not necessary to do it that way).


Enemy1Health,Enemy2Health,Enemy3Health,Enemy4Health =
Friendly1AliveStatus, Friendly2AliveStatus, Friendly3AliveStatus, Friendly4AliveStatus, Object1AttackPermutations, Object2AttackPermutations, Object3AttackPermutations,Object4AttackPermutations,Enemy1AliveStatus,Enemy2AliveStatus,Enemy3AliveStatus,Enemy4AliveStatus

^ So what I just tried to describe above is an 16 dimensional array as follows:

2x2x2x2x24x24x24x24x2x2x2x2

So computational complexity added by alive/death status is only x8 which is totally great... total complexity is therefore:

24x24x24x24x8

(For each attack the lookup table can be reused so that perfect too)

So the initial complexity of 24x24x24x24x24x24x24x24x4(?) has now been reduced too:

1x24x24x24x24x8 (computations)

It will probably still be necessary to "compute/lookup" all possibilities just to be sure, however doing an 16 way array lookup should be way faster than computing while loops and if statements and what not... though the table is quite large so some random access may occur.

16 random access is roughly 16x100 nanoseconds. Plus some 5 minute looping overhead or so so let's calculate rough indication of new processing time.

24x24x24x24x24x24x24x24x4(?) (look ups)


But first I try and calculate some kind of indicator of current per loop processing time.

24^8 = 110075314176 battles / 80.000 seconds = 1375941.4272 battles per second.

The 5 minute overhead is about 300 seconds so seems minimal not going to adjust for that for now.

Now let's compute new expected running time.

Perhaps crazyly inaccurate calculation since it does not account for data cache hits... but just worst case scenerio or something:

It will be at least 16x100 nanoseconds, then 8 branches or so to determine winner is about 8 x branch time which is roughly 15 cycle clocks of 2 gigahertz or so. Then also 8 data field fetches another 8x1 cycle, and perhaps 8 assignments or so to store healths so roughly 15+8+8 = 13 plus probably some while loop to repeat attacks until there is a winner though this was already accounted for in the branches above... so for now I'll stick with 31 cycles or so

So 31 cycles of 2.000.000.000 hz machine I would guess is roughly: 

0.0000000155 seconds, roughly 15.5 nanoseconds so worst case scenerio:

16x100 = 1600 + 15 = 1615.5 nanoseconds to compute/lookup a battle.

Number of battles: 110075314176 x 1615.5 = 177826670051328 nanoseconds

= 177826.670051328 seconds.

According to my initial calculations it will be far worse off lol !

However the 8x dimensions could be put close together so that at least those are cached, then perhaps a lookup will only take 10 nanoseconds or something or maybe even less.

So then it becomes 8x10 nanoseconds + 8*100 nanoseconds = 880 nanoseconds

Seems like roughly a reduction... then I am back to square one roughly running time of 90.000 seconds. Plus ofcourse some pre-compute overhead...

Though I am kinda bad at estimating running time like this... 

I am hopefully that the look ups will proceed much faster...

Sometimes of those 8x100 nanosecond seeks there will be some L1/L2 data cache hits hopefully so that should accelerate it somewhat.

What actually needs to be stored is enemy health... this can be done with one byte... 100 is near 128 bits... so at least 7 bits needed for 100, so only 1 bit could be saved so doesn't really seem worth it to save 4 bits in total ! ;)

The pre-compute time for the table lookups should be quite fast...

The main processing for generating the lookup is:

24^4 = 331776 x 8 = 2.654.208

That's nothing compared to the 110.000.000.000 that it used to be ! ;) :)

So I am very hopefull that I have found a nice data acceleration structure ! ;) :)

Having this conversation with you was usefull, thanks !

Bye,
  Skybuck =D