Complete.Org: Mailing Lists: Archives: freeciv-ai: October 2004:
[freeciv-ai] (PR#10203) Greedy CM algorithm

[freeciv-ai] (PR#10203) Greedy CM algorithm

[Top] [All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
To: per@xxxxxxxxxxx
Subject: [freeciv-ai] (PR#10203) Greedy CM algorithm
From: "Benoit Hudson" <bh@xxxxxxxxxxxxxxxxxxx>
Date: Fri, 1 Oct 2004 13:30:17 -0700
Reply-to: rt@xxxxxxxxxxx

<URL: >

Here's the branch-and-bound cm, now with auto_arrange_workers rejiggered to use 
find_first_feasible, which is essentially the greedy search, except we 
guarantee finding 
a feasible solution if there is one.  Finding the first feasible takes about a 
quarter the 
time of finding the optimal.

It includes moving cm.c to cm-old.c ; if you set COMPARE_OLD to TRUE, then 
call to cm_query_result will use the branch-and-bound algorithm, but then also 
sure that the dynamic programming algorithm returns an equally good solution.  
normal usage, of course, this would slow you down a bunch, so you wouldn't do 
but it's very helpful for debugging.

The branch-and-bound is inconsistently faster than dynamic programming: 
it's slightly slower, sometimes it's much faster.  It seems to do especially 
well when 
there is no way to make enough food, and on large cities.  Dynamic programming 
does especially well when the constraints are easy to achieve.  In the savegame 
attached, I see a factor of almost two time difference in favour of 
So in the late game, branch-and-bound is a lot faster; in the early game, 
programming seems slightly faster.  But in the early game, we don't spend much 
in CM.

This code prunes based on insufficient food or shields to meet the requirement, 
not on insufficient luxury.  That would probably speed it up a bunch.  The 
reason I
don't do it is that I don't especially want to tie the CM code too tightly in 
with the 
default ruleset, and I'm not sure how to elegantly find the required lux 
without lots
of ruleset-specific hackery.

Attachment: cm_branch_bound.diff
Description: Binary data

Attachment: civgame+1995.sav.gz
Description: GNU Zip compressed data

[Prev in Thread] Current Thread [Next in Thread]