Help: Brute Logic...

[Steve0]

So I have this idea for a script to help work out the best party combination for a mobile game. I've been trying to come up with a method that will logically determine the best combination, but there are too many variables to take into consideration... so what I've ended up with is a very "brute" method of cycling through every possible combination of character looking for the highest scoring combination and reporting it at the end. The only trouble is, with only 20 characters, the script is running through around 20 billion combinations which takes a couple of hours. I'm wondering if anyone has any ideas to reduce the amount of time taken to come up with the best combination.

The characters have 3 key stats - Attack, Health and Cost.

The party has a maximum of 8 members and a maximum variable "cost", so you can't just choose the best cards.

The loop I came up with looks awful and is exceptionally slow (that said, it can get through a few million combinations in a few minutes):

$CharArray - Array storing the character list.

[0][0] is the total number

[x][0] is character name

[x][1] is their cost value

[x][13] is their combined Attack and Health used to determine the highest card.

expandcollapse popup

$BestTeam[0] = 0 ; reset the best score before running the loop
For $a = 1 to $CharArray[0][0]
    For $b = 2 to $CharArray[0][0]
        For $c = 3 to $CharArray[0][0]
            For $d = 4 to $CharArray[0][0]
                For $e = 5 to $CharArray[0][0]
                    For $f = 6 to $CharArray[0][0]
                        For $g = 7 to $CharArray[0][0]
                            For $h = 8 to $CharArray[0][0]
                                If $a <> $b And $a <> $c And $a <> $d And $a <> $e And $a <> $f And $a <> $g And $a <> $h _
                                    And $b <> $c And $b <> $d And $b <> $e And $b <> $f And $b <> $g And $b <> $h _
                                    And $c <> $d And $c <> $e And $c <> $f And $c <> $g And $c <> $h _
                                    And $d <> $e And $d <> $f And $d <> $g And $d <> $h _
                                    And $e <> $f And $e <> $g And $e <> $h _
                                    And $f <> $g And $f <> $h _
                                    And $g <> $h Then ; very poor way to check for no duplicates

                                    $FinalCost = $CharArray[$a][1] + $CharArray[$b][1] + $CharArray[$c][1] + $CharArray[$d][1] + $CharArray[$e][1] + $CharArray[$f][1] + $CharArray[$g][1] + $CharArray[$h][1]
                                    If $FinalCost <= $MaxCostValue Then ; Cost value hasn't exceeded the maximum value, proceed with check
                                        $TempTeam = $CharArray[$a][13] + $CharArray[$b][13] + $CharArray[$c][13] + $CharArray[$d][13] + $CharArray[$e][13] + $CharArray[$f][13] + $CharArray[$g][13] + $CharArray[$h][13]
                                        If $TempTeam > $BestTeam[0] Then ; current variation is the new best, store the party in the BestTeam array.
                                            $BestTeam[0] = $TempTeam
                                            $BestTeam[1] = $CharArray[$a][0]
                                            $BestTeam[2] = $CharArray[$b][0]
                                            $BestTeam[3] = $CharArray[$c][0]
                                            $BestTeam[4] = $CharArray[$d][0]
                                            $BestTeam[5] = $CharArray[$e][0]
                                            $BestTeam[6] = $CharArray[$f][0]
                                            $BestTeam[7] = $CharArray[$g][0]
                                            $BestTeam[8] = $CharArray[$h][0]

                                        EndIf
                                    EndIf
                                EndIf
                            Next
                        Next
                    Next
                Next
            Next
        Next
    Next
Next
_ArrayDisplay($BestTeam)

.............. if that massive combination of loops is too confusing, the goal is:

Find the best combination of characters by their combined $CharArray[x][13] value.

Cannot exceed 8 characters.

Cannot exceed a variable cost limit stored in $MaxCostValue.

Cannot have duplicate cards.

The loop I have works, just takes a long time for just 20 characters, I was hoping to have the array include 50 or more... any assistance improving this would be greatly appreciated.

Many thanks,

Steve

[Kidney]

lol dear lord...... i would be interested to see what changes between each time you want this to calculate. is it what you start out with that changes??

[Steve0]

@Kidney - characters can be upgraded, new characters added to the pool, and as you continue to play your "cost limit" increases allowing more higher level characters. Ideally, you'd want to rerun after your cost limit increases or if you pick up any extra characters.

The game has an "auto set", but just picks the top scoring cards until the cost is reached, rather than allocating lower scoring cards that add up to better stats.

There is a mode in the game that has a 4-character limit, at 20 cards thats only 160,000 possibilities which the script returns the best combination in a few seconds... increasing to 8 is where the fun starts...

[Kidney]

i would say that adding an if statement in between each for loop would lower the amount of test it would do. instead of testing everything at the end. this should cut down on time.

you can keep the final if  just to make sure nothing gets by.

 

EDIT: the reason why you want to run the test directly after the for loop starts is cuz you wont want it to run the script if the cards r the same. here is an example using just 3 slots with 3 different chars:

Names:

Char1

Char2

Char2

Slots:

1

2

3

1    2    3

Char1    Char1    Char1
Char1    Char1    Char2
Char1    Char1    Char3

Char1    Char2    Char1
Char1    Char2    Char2
Char1    Char2    Char3

Char1    Char3    Char1
Char1    Char3    Char2
Char1    Char3    Char2

Char2    Char1    Char1
Char2    Char1    Char2
Char2    Char1    Char3

Char2    Char2    Char1
Char2    Char2    Char2
Char2    Char2    Char3

Char2    Char3    Char1
Char2    Char3    Char2
Char2    Char3    Char3


etc...

 

in the first loop, the way you have it currently, it will actually run all of those tests.

however, if you did a simple test that sees if $a = $b, it will skip hundreds of tests.

 

Run the script before you make any changes, then make the right changes and then rerun the script to make sure you get the same result as before.

Edited November 14, 2013 by Kidney

[Steve0]

The way I originally tried to go about it was determining which characters had the greatest ratio of statistics per cost point, but this ended up using only half the available cost as the top 8 characters were low cost ones.

Thought about picking the top 8 highest ratio characters, if there is cost leftover, then see if the highest character can replace #8... if there is still unspent cost, try replacing #7 with the next highest... and so on.

Seemed like a more logical way about it, all the checks were doing my head in...........

[Melba23]

Steve0,

 

So I have this idea for a script to help [...] for a mobile game

Despite being a member here longer than myself you appear not to have read the Forum rules. In my opinion this thread falls under the game interaction prohibition - and will now be locked.

Kidney,

Whe the first line of the thread makes it quite clear that the subject is gaming, I would not expect help to be offered so readily.

M23