Complete.Org: Mailing Lists: Archives: freeciv-ai: September 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: Thu, 23 Sep 2004 22:33:31 -0700
Reply-to: rt@xxxxxxxxxxx

<URL: >

> [bhudson - Thu Sep 23 22:32:39 2004]:
> By the way, somewhat sparked by this, I implemented a branch & bound
> algorithm.  It's quite a bit faster on small cities, although I think
> I can make the current CM get those advantages too.  It's slower on
> large cities to get the optimal answer.  But, if we just choose the first
>  feasible answer, we get almost the algorithm you just outlined.

Here's the branch-and-bound algorithm all coded up.  This gives identically
good solutions to the dynamic programming CM code we had -- at least,
it does in an 8-AI game to 500 AD and another 8-AI game (different random 
seeds) to past 800 AD when it died of a punit->transported_by assertion.  By
identically good, I mean that it doesn't have the tie-breaker that the old CM 
code had, and it can't without limiting the pruning I can do, so the solutions
have the same fitness but may be different.

Only it does so with 1/3 fewer evaluations of solutions (generic_city_refresh,
or a cache hit).  This makes it about 10% faster than the current CM.  And,
it has support for Jason's pet project of specialists that produce food or
whatever: specialist positions are just "tiles" of which there happen to be an 
infinite number available.

The code has one function where it makes all sorts of assumptions to be able 
to prune effectively.  This is what got me thinking about #10290.  Apart from
that, there is little required of the ruleset except for 1 position takes 1 
and more is better.

Last pro to consider: it would be easy with this code to go down one branch
and take it as our solution.  For an example, look in init_bb_state where I do
just that (building up a food-optimal solution).

To build warning-free requires #10294.

Attachment: cm_branch_bound.diff
Description: Binary data

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