KP#3: Poor Optimisation Result

Reported
17 Jan 2018, v0.0.2 (Beta) (SH)
Description
The following command line leads to a poor optimisation result: “-Camp=JuHolz#4 -Attack=*BSK;*BSS;Ans“. It leads to

150BSK;Ans ==> 10.2XP/PLVMix, 381.75PLVMix, [40]s duration, [368.5-381.75-408.7]PLV, PlrDd [55-56.98-61]BSK, [3892]XP

But actually the following simulation shows there is a much better configuration: “-Mode=Simulate -Camp=JuHolz#4 -Iterations=10000 -Attack=25BSK;125BSS;Ans” with

25BSK;125BSS;Ans ==> 14.6XP/PLVMix, 266.89PLVMix, [20-28.13-30]s duration, [181.7-266.89-366.3]PLV, PlrDd [25]BSK;[1-7.00-14]BSS, [3892]XP
Analysis
The optimal solution lies in a very narrow ditch of the objective fuction, so that it is missed even on a x16x grid. This causes the optimiser to discard the area in the search space where there solution lies as “not very promising” and then converge elsewhere. Graphical illustration to follow. Grid condensation and search space contraction must be refined to be able to find this solution.
Solution
Optimisation algorithm has been enhanced. It now uses a first-principle approach when it is detected that there is only one wave and both player and enemy have first strike units. Runs a little longer though in that cases. Fixed in v1.5.2.
Fixed
v1.5.2

6 thoughts on “KP#3: Poor Optimisation Result”

  1. I have been thinking about various ways to help focus the brute force approach to where it is really needed, Here’s a suggestion. Develop a routine that calculates a kind of “average battle” between two armies. Let the attack be the mean of lo and hi, weight appropriately by accuracy. Done right, you won’t even need any simulation of individual attackers, but get a gross result for representative kills and losses. Ideally, this would run faster even than a single battle simulation (since you don’t need to loop through individual fighters). You would need to loop through the phases, the rounds and the fighter types. This high speed routine could then span across the grid at high resolution, and identify the regions where it is worth doing the simulation.

    Like

    Reply

  2. Another possibly revealing instance of this problem. Seems to have failed to run with a sufficiently large number of bows.

    αO-C v0.1 04-Mar-2018 10:54:56 (UI-launched)
    8R;Nus2 ==> 0% wins, 85.7XP/PLVMix, 7PLVMix, [10]s duration, [7]PLV, PlrDd [7]R;[1]Nus2, [600]XP, EnmDd [50]Fu
    9R;Nus2 ==> 0% wins, 75XP/PLVMix, 8PLVMix, [10]s duration, [8]PLV, PlrDd [8]R;[1]Nus2, [600]XP, EnmDd [50]Fu
    10R;Nus2 ==> 0% wins, 66.7XP/PLVMix, 9PLVMix, [10]s duration, [9]PLV, PlrDd [9]R;[1]Nus2, [600]XP, EnmDd [50]Fu
    -Camp=Tapf#34 -Iterations=5000 -Attack=8-40R;*B;Nus2

    Interestingly, if the number of recruits is fixed at 40, the solution is still not found.
    αO-C v0.1 04-Mar-2018 11:13:33 (UI-launched)
    40R;Nus2 ==> 0% wins, 16.7XP/PLVMix, 36PLVMix, [10]s duration, [36]PLV, PlrDd [36]R;[1]Nus2, [600]XP, EnmDd [50]Fu
    40R;1B;Nus2 ==> 0% wins, 16.1XP/PLVMix, 37.3PLVMix, [10]s duration, [37.3]PLV, PlrDd [36]R;[1]B;[1]Nus2, [600]XP, EnmDd [50]Fu
    40R;2B;Nus2 ==> 0% wins, 15.5XP/PLVMix, 38.6PLVMix, [10]s duration, [38.6]PLV, PlrDd [36]R;[2]B;[1]Nus2, [600]XP, EnmDd [50]Fu
    -Camp=Tapf#34 -Iterations=5000 -Attack=40R;*B;Nus2

    By giving a minimum number of bows, the solution is found:
    αO-C v0.1 04-Mar-2018 10:56:29 (UI-launched)
    14R;165B;Nus2 ==> 9.57XP/PLVMix, 207PLVMix, [30]s duration, [207]PLV, PlrDd [12]R;[150]B, [1980]XP
    13R;166B;Nus2 ==> 9.55XP/PLVMix, 207.3PLVMix, [30]s duration, [207.3]PLV, PlrDd [11]R;[151]B, [1980]XP
    11R;168B;Nus2 ==> 9.54XP/PLVMix, 207.6PLVMix, [30]s duration, [207.6]PLV, PlrDd [10]R;[152]B, [1980]XP
    -Camp=Tapf#34 -Iterations=5000 -Attack=8-40R;100-180B;Nus2

    For replication, Nus2 is configured as

    I guess that what might be happening here is that the initial grid using 64 steps considers 0, 64 and 128 bows. 128 bows is not enough with 40R.

    If this is truly the problem, then an easy fix might be to have the grid search start with high troops numbers, not with 0. so the initial bows grid with 40R would not be 0, 64, 128; but 140, 76, 12. But I think this is only a patch which does not address the deeper issue.

    Fixing this should be a priority, but unfortunately I think to fix it well requires a fairly major change to the algorithm so that it looks at the interior of the search space and not only the boundaries. My previous comment is something I may try to prototype in C, and is intended to give a crude high speed map of the search space interiors.

    Liked by 1 person

    Reply

    1. Nus2 definition failed to show up because it was in XML. here it is wit angle brackets replaced by parentheses
      (CustomGeneral Id=”Nus2″ BasedOn=”Nus”)
      (Skill Name=”FirstAid”/)
      (Skill Name=”FirstAid”/)
      (Skill Name=”FirstAid”/)
      (Skill Name=”RapidFire”/)
      (Skill Name=”RapidFire”/)
      (Skill Name=”RapidFire”/)
      (Skill Name=”Overrun”/)
      (Skill Name=”Overrun”/)
      (Skill Name=”Overrun”/)
      (Skill Name=”SniperTraining”/)
      (Skill Name=”SniperTraining”/)
      (Skill Name=”SniperTraining”/)
      (Skill Name=”Cleave”/)
      (Skill Name=”Cleave”/)
      (Skill Name=”GarrisonAnnex”/)
      (Skill Name=”GarrisonAnnex”/)
      (Skill Name=”GarrisonAnnex”/)
      (Skill Name=”MasterPlanner”/)
      (/CustomGeneral)

      Like

      Reply

      1. Should also give troops values! they are:

        (PersonalValues)
        (PersonalValue Id=”R” Value=”1.0″/)
        (PersonalValue Id=”M” Value=”3.6″/)
        (PersonalValue Id=”S” Value=”4.9″/)
        (PersonalValue Id=”E” Value=”22.6″/)
        (PersonalValue Id=”C” Value=”3.6″/)
        (PersonalValue Id=”B” Value=”1.3″/)
        (PersonalValue Id=”LB” Value=”2.6″/)
        (PersonalValue Id=”AB” Value=”20.5″/)
        (PersonalValue Id=”K” Value=”39.6″/)
        (PersonalValue Id=”SK” Value=”5.7″/)
        (PersonalValue Id=”BSK” Value=”6.7″/)
        (PersonalValue Id=”RIT” Value=”4.5″/)
        (PersonalValue Id=”SS” Value=”13.2″/)
        (PersonalValue Id=”GSS” Value=”15.4″/)
        (PersonalValue Id=”BSS” Value=”14.2″/)
        (PersonalValue Id=”BEL” Value=”32.4″/)
        (/PersonalValues)

        Like

  3. OK. Been thinking about this some more, and went to look up the literature as well.

    There’s a fair bit of research on algorithms for finding the maximum point in a multidimensional space. Most of them are designed to work with a continuous domain; but could be adapted.

    There are a couple of pitfalls. We already know some of them! Here’s another one. The maximum may lie along a “ridge”, and the direction of the ridge may not align well with the dimensions.For example.

    Suppose we are searching for the best combination of three kinds of troops: R, S and B. Suppose that for a given S value, the best R/B combination moves by about 8. That is, (and I am picking numbers out of the air, but I bet we could find examples) good solutions are 100R,30B,10S and 92R,38B,9S.

    If we simply use a hyper-rectangle and shrink to find the solution, then it will quickly rule out certain R/B combinations as the grid step drops below 8, and thereafter only one S value can be considered. This is very likely to miss the optimum.

    I’m looking into using a method of “Divided Rectangles”; a standard algorithm also called “DIRECT”. Here’s a reference: http://adl.stanford.edu/aa222/lecture_notes_files/chapter6_gradfree.pdf; look for section 6.3, Or google “Divided rectangles search algorithm”.

    The adaption to discrete spaces such as we are using is comparatively straightforward. The algorithm maintains a set of hyperrectangles spanning the entire search space, with one representative (central) point evaluated in each hyperrectangle, and keeps finding rectangles likely to contain the global optimum, and subdividing them. In our case, the evaluation at a point corresponds to a simulation for a given army. The evaluation is approximate, which introduces an extra level of complexity, but a good solution (IMO) would be to incrementally increase the number of simulations as the algorithm progresses, guided by the need to find which hyperrectangles to subdivide.

    This kind of thing would be a major change, of course! The payoff, however, is likely to be considerable.

    If you are interested, then, read the papers, and see if there’s anything there that gives you ideas.

    Like

    Reply

  4. Still thinking about optimization…. Hope you don’t mind me using your comment stream as a kind of notebook to make a record of interesting cases.

    Here is a situation where the algorithm fails to converge to a best case; despite the best case being very close indeed to the slightly suboptimal solution found. That is, the algorithm does not at present work for hill climbing towards a local optimum.

    The relevant parts of the config file (replacing angle brackets with parentheses) is as follows:

    (CustomGenerals)
    (CustomGeneral Id=”Nus2″ BasedOn=”Nus”)
    (Skill Name=”FirstAid”/)
    (Skill Name=”FirstAid”/)
    (Skill Name=”FirstAid”/)
    (Skill Name=”RapidFire”/)
    (Skill Name=”RapidFire”/)
    (Skill Name=”RapidFire”/)
    (Skill Name=”Overrun”/)
    (Skill Name=”Overrun”/)
    (Skill Name=”Overrun”/)
    (Skill Name=”SniperTraining”/)
    (Skill Name=”SniperTraining”/)
    (Skill Name=”SniperTraining”/)
    (Skill Name=”Cleave”/)
    (Skill Name=”Cleave”/)
    (Skill Name=”GarrisonAnnex”/)
    (Skill Name=”GarrisonAnnex”/)
    (Skill Name=”GarrisonAnnex”/)
    (Skill Name=”MasterPlanner”/)
    (/CustomGeneral)
    (/CustomGenerals)
    (PersonalValues)
    (PersonalValue Id=”R” Value=”1.0″/)
    (PersonalValue Id=”M” Value=”3.6″/)(!–2.0, 3.5–)
    (PersonalValue Id=”S” Value=”4.9″/)(!–3.0, 8.5–)
    (PersonalValue Id=”E” Value=”22.6″/)(!–7.0, 999.0–)
    (PersonalValue Id=”C” Value=”3.6″/)(!–3.0, 3.6–)
    (PersonalValue Id=”B” Value=”1.3″/)(!–1.0, 0.95–)
    (PersonalValue Id=”LB” Value=”2.6″/)(!–1.0, 1.45–)
    (PersonalValue Id=”AB” Value=”20.5″/)(!–3.0, 999.0–)
    (PersonalValue Id=”K” Value=”39.6″/)(!–9.0, 999.0–)
    (PersonalValue Id=”SK” Value=”5.7″/)
    (PersonalValue Id=”BSK” Value=”6.7″/)
    (PersonalValue Id=”RIT” Value=”4.5″/)
    (PersonalValue Id=”SS” Value=”13.2″/)
    (PersonalValue Id=”GSS” Value=”15.4″/)
    (PersonalValue Id=”BSS” Value=”14.2″/)
    (PersonalValue Id=”BEL” Value=”32.4″/)
    (/PersonalValues)

    The result, using tight constraints on the number of cavalry
    αO-C v0.1.2 08-Apr-2018 01:52:45 (UI-launched)
    23R;4S;153C;Nus2 ==> 30.6XP/PLVMix, 21.57PLVMix, [30]s duration, [18-21.57-30.8]PLV, PlrDd [18-20.66-21]R;[0-0.18-2]S, [660]XP
    23R;4S;152C;Nus2 ==> 30.6XP/PLVMix, 21.6PLVMix, [30]s duration, [18-21.60-30.8]PLV, PlrDd [18-20.68-21]R;[0-0.19-2]S, [660]XP
    23R;5S;152C;Nus2 ==> 30.5XP/PLVMix, 21.64PLVMix, [30]s duration, [18-21.64-30.8]PLV, PlrDd [18-20.68-21]R;[0-0.20-2]S, [660]XP
    -Camp=Verr#4 -Iterations=10000 -Attack=14-30R;1-5S;0-2E;152-156C;Nus2

    Same search, with no constraint on the number of cavalry.
    αO-C v0.1.2 08-Apr-2018 02:09:32 (UI-launched)
    27R;3S;150C;Nus2 ==> 28.9XP/PLVMix, 22.87PLVMix, [30]s duration, [18-22.87-33.8]PLV, PlrDd [18-22.63-24]R;[0-0.05-2]S, [660]XP
    28R;2S;150C;Nus2 ==> 28.8XP/PLVMix, 22.89PLVMix, [30]s duration, [17-22.89-29.9]PLV, PlrDd [17-22.83-25]R;[0-0.01-1]S, [660]XP
    26R;3S;151C;Nus2 ==> 28.8XP/PLVMix, 22.89PLVMix, [30]s duration, [18-22.89-32.8]PLV, PlrDd [18-22.26-23]R;[0-0.13-2]S, [660]XP
    -Camp=Verr#4 -Iterations=10000 -Attack=14-30R;1-5S;0-2E;*C;Nus2

    When the number of cavalry are unconstrained, centurion consistently finds a sub-optimal solution, with slightly less cavalry.

    Like

    Reply

Leave a comment