patchFreeciv - Patches: patch #3620, Governor (cma) branch pruning...

 
 
Show feedback again

patch #3620: Governor (cma) branch pruning heuristic fix

Submitted by:  Bastian Schmidt <stlth>
Submitted on:  Fri 25 Jan 2013 02:16:10 PM UTC  
 
Category: agentsPriority: 5 - Normal
Status: DonePrivacy: Public
Assigned to: Marko Lindqvist <cazfi>Open/Closed: Closed
Planned Release: 2.4.0-beta2, 2.5.0

Add a New Comment (Rich MarkupRich Markup):
   

You are not logged in

Please log in, so followups can be emailed to you.

 

(Jump to the original submission Jump to the original submission)

Fri 08 Mar 2013 08:11:51 AM UTC, comment #11:

Could something in this patch explain bug #20541?

Marko Lindqvist <cazfi>
Project AdministratorIn charge of this item.
Tue 19 Feb 2013 12:15:38 AM UTC, comment #10:

In my testing, this patch does look to fix bug #18040, and also gets rid of the gold_upkeep_style-dependent tax collectors of bug #18767 / #17542.

Jacob Nevins <jtn>
Project Administrator
Sat 16 Feb 2013 10:36:03 PM UTC, SVN revision 22356:

Improved cma branch pruning heuristic.

Patch by Bastian Schmidt

See gna patch #3620

(Browse SVN revision 22356)

Marko Lindqvist <cazfi>
Project AdministratorIn charge of this item.
Sat 16 Feb 2013 10:35:57 PM UTC, SVN revision 22355:

Improved cma branch pruning heuristic.

Patch by Bastian Schmidt

See gna patch #3620

(Browse SVN revision 22355)

Marko Lindqvist <cazfi>
Project AdministratorIn charge of this item.
Sat 09 Feb 2013 10:11:06 PM UTC, comment #7:

Will be running more autogames with this before committing (even if patch itself is correct, old AI balancing may have resulted in fudge factors that mean correct low-level results cause poor overall performance). But also want this in to beta-release testing.

Marko Lindqvist <cazfi>
Project AdministratorIn charge of this item.
Tue 05 Feb 2013 07:49:27 PM UTC, comment #6:

> I do not know about the developing process here. Am I supposed
> to change the style issues?


I was hoping so. More the original authors do to get their patches to acceptable state, less work for us maintainers.

> Anyway, I attached a new patch file with the backup changed and
> hopefully all style issues considered.


I fixed a couple more of "if(" -> "if (" style issues.

Probably stuff for future ticket (if nobody objects during inspection period, and this passes my testing, I'm ready to commit this one in its current form), but it might make sense to create temporary virtual city instead of messing with real city's data. I'm not 100% sure it's doable, but should be investigated at least.

(file #17134)

Marko Lindqvist <cazfi>
Project AdministratorIn charge of this item.
Tue 05 Feb 2013 05:20:40 PM UTC, comment #5:

- I believe it is not necessary to initialize production[] (bug #20482). It is either copied from soln->production or solnplus.production (in compute_max_stats_heuristic)

- You are right, city production should be restored.
There are some other functions changing the state of the city and performing backups, I would suggest performing one backup at the beginning of cm_find_best_solution and restoring at the end. This would give better performance.

- I do not know about the developing process here. Am I supposed to change the style issues?

Anyway, I attached a new patch file with the backup changed and hopefully all style issues considered.

Doing this I found another dependence on rulesets. Non-changeable tax rates and anarchy are now considered, too.

(file #17133)

Bastian Schmidt <stlth>
Tue 05 Feb 2013 02:35:26 PM UTC, comment #4:

> - Not new with the patch, but it seems that production[] is
> never initialized, but assumed to be zero-filled in the
> beginning


This raised separately as bug #20482 as it can have quite a nasty effects with high compiler optimization level, and it should be fixed in all branches.

Marko Lindqvist <cazfi>
Project AdministratorIn charge of this item.
Tue 05 Feb 2013 02:12:27 PM UTC, comment #3:

- So it mpodifies actual city state, for example by calling set_city_production(), instead of just calculating the best solution. I don't see it restoring city to the original state, so city can end in a weird state if caller decides not to apply the result.

- Not new with the patch, but it seems that production[] is never initialized, but assumed to be zero-filled in the beginning

- Minor Style issues: "}else{" -> "} else {", "return(value);" -> "return value;", empty line between variable declarations and code.

Marko Lindqvist <cazfi>
Project AdministratorIn charge of this item.
Thu 31 Jan 2013 04:39:10 PM UTC, comment #2:

Good point, I just had the civ2 ruleset in mind.

I have revised the patch and added a new version. The hardcoded twos had to be replaced. Everything is now as in city.c.

(file #17079)

Bastian Schmidt <stlth>
Thu 31 Jan 2013 12:03:57 PM UTC, comment #1:

Quick question before I read this more carefully: have you considered different rulesets, i.e., do the hardcoded twos in the code really means always to double value, or should current rules be consulted?

Marko Lindqvist <cazfi>
Project AdministratorIn charge of this item.
Fri 25 Jan 2013 02:16:10 PM UTC, original submission:

This fixed various issues with the cma branch & bound algorithm.

The heuristics used for pruning branches was severely flawed. This caused solutions not to be found, as the heuristic about how good a partial solution can still get was computed wrongly.

It mainly showed by having additional tax specialists, which were actually not really needed. But also other situations were not handled correctly (which just occur not as often).
See bugs #18767, #180403, #17542

As too much solutions were pruned, the algorithm would now be less performant.
That is why I also added pruning based on luxuries needed to make the city content.

Bastian Schmidt <stlth>

 

(Note: upload size limit is set to 1024 kB, after insertion of the required escape characters.)

Attach File(s):
   
   
Comment:
   

Attached Files
file #17134:  CmHeuristic-4.patch added by cazfi (17kB - text/x-diff)
file #17133:  cm_heuristic_v3.patch added by stlth (16kB - text/x-patch)
file #17079:  cm_heuristic_ruleset.patch added by stlth (13kB - text/x-patch - changed to work with different rulesets)
file #17024:  cm_heuristic.patch added by stlth (13kB - text/x-patch)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by jtn (Posted a comment)
  • -unavailable- added by cazfi (Posted a comment)
  • -unavailable- added by stlth (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 10 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Sat 16 Feb 2013 10:36:25 PM UTCcazfiStatusReady For Test=>Done
      Open/ClosedOpen=>Closed
    Sat 09 Feb 2013 10:11:06 PM UTCcazfiPlanned Release2.4.0, 2.5.0=>2.4.0-beta2, 2.5.0
    Tue 05 Feb 2013 07:49:26 PM UTCcazfiAttached File-=>Added CmHeuristic-4.patch, #17134
    Tue 05 Feb 2013 05:20:40 PM UTCstlthAttached File-=>Added cm_heuristic_v3.patch, #17133
    Fri 01 Feb 2013 09:32:51 PM UTCcazfiAssigned toNone=>cazfi
      Planned Release=>2.4.0, 2.5.0
    Fri 01 Feb 2013 09:32:50 PM UTCcazfiStatusNone=>Ready For Test
    Thu 31 Jan 2013 04:39:10 PM UTCstlthAttached File-=>Added cm_heuristic_ruleset.patch, #17079
    Fri 25 Jan 2013 02:16:11 PM UTCstlthAttached File-=>Added cm_heuristic.patch, #17024
    Show feedback again

    Back to the top


    Powered by Savane 3.1-cleanup