Complete.Org: Mailing Lists: Archives: freeciv-ai: April 2005:
[freeciv-ai] Re: (PR#11509) a greedy CM

[freeciv-ai] Re: (PR#11509) a greedy CM

[Top] [All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
To: jdorje@xxxxxxxxxxxxxxxxxxxxx
Subject: [freeciv-ai] Re: (PR#11509) a greedy CM
From: "Benoit Hudson" <bh@xxxxxxxxxxxxxxxxxxx>
Date: Mon, 11 Apr 2005 20:11:14 -0700
Reply-to: bugs@xxxxxxxxxxx

<URL: >

On Mon, Apr 11, 2005 at 09:33:03AM -0700, Jason Short wrote:
> <URL: >
> 1.  It's not truly greedy.  It doesn't take the first solution but the
> first satisfactory one (that meets the minimums).  Usually this makes no
> difference.

The usual term is the first "feasible" solution.

> 2.  My original patch was quite buggy because it did "return FALSE"
> instead of "return TRUE" causing the CM to simply lock up - oops.  

> Also it didn't work with CMA because CMA didn't use cm_init_parameter
> correctly.  This patch fixes both.

Can you make this a seperate patch & apply it?  I got bitten by this in
trying to get the 12736 stuff to work.

> 3.  I think these numbers show the B&B algorithm to be flexible enough
> to meet all of our needs.  Of course you AI guys should test this on
> your own.

This was in the original design in #10203 but I cut it out since it
complicated the patch, so I'm not too surprised it works well :)

The way I'd implemented it was to have the API be:
        - build the cm_state
        - repeatedly call cm_find_first_feasible until you
          find a parameter that has a feasible solution
        - destroy the cm_state and apply the cm_result.

I pretty much don't care whether the first-feasible / full-search
determination is done via API or parameter, but building the cm_state
only once in auto_arrange_workers is quite advantageous if we get the
search time down to where pre-processing starts to matter.

        -- Benoît

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