[Freeciv-Dev] Re: (PR#7311) rewrite create_start_positions

["ue80@xxxxxxxxxxxxxxxxxxxxx" <ue80@xxxxxxxxxxxxxxxxxxxxx>]

<URL: http://rt.freeciv.org/Ticket/Display.html?id=7311 >

On Sat, Jan 24, 2004 at 06:31:51PM -0800, Jason Short wrote:
> 
> <URL: http://rt.freeciv.org/Ticket/Display.html?id=7311 >
> 
> This patch rewrites create_start_positions to use rand_map_pos_filtered.
> 
> The main advantage is that it fails more consistently: we don't have to
> loop 10 million times to be sure that there's no remaining valid map
> position; rand_map_pos_filtered just returns FALSE and we know.  Thus it
> is many, many times faster when there is no available starting position.
> 
> There are still a couple of biases, however.
> 
> (1) The minimum distance is decreased over the course of the loop (if
> there are too many start positions).  This means some players may be
> given more advantageous positions than other players.  Of course we knew
> that already.
> 
> (2) We only try to place players once.  Once a player is in position,
> they won't be moved.  This means sometimes even if there is a valid set
> of start positions, it won't be found.  We'll try repeatedly to place
> the next player (until we find a good start position) but we never
> consider moving a player once he's already in place.
> 
> These are related in that it would be "cleanest" to restart placing
> players when the distance is decreased.
> 
> [Digression]
> To be sure of finding a start position, if one exists, will take C(M, N)
> = M! / (N!(M-N)!) checks, where M is the number of valid
> (grassland/plains) starter positions and N is the number of players. 
> This value can be very large: on a 200x100 map with 10,000 valid start
> positions and 30 players, the value C(10,000, 30) is impossibly large. 
> Although when the island's "starter" value is taken into account, it may
> get a bit better: with 2 players per island and equal-sized islands it
> would take
>   C(10,000 / 15, 30 / 15) ^ 15 = C(666, 2) ^ 15
>                                > (2 * 10^5) ^ 15
>                                > 10^105
> which is still impossibly large.

And you don't get fair positions with that too.

I think a solution where you evalutate the value of every possible
starting position and try to give every player one of them would be
fairer.

We need such a mechanism especially for tournament games.

Thomas
-- 
Thomas Strub  ***  eMail ue80@xxxxxxxxxxxxxxxxxxxxx
jb: people are stupid, they don't want to learn.