Summary: Start position allocation not deterministic
Submitted by: jtn
Submitted on: Thu Jul 14 00:41:04 2011
Severity: 3 - Normal
Priority: 5 - Normal
Assigned to: None
Release: S2_3 r19940
Discussion Lock: Any
Operating System: None
Discovered during autogame testing of bug #17962:
For autogames that should have been identical, I was seeing the assignment of
nations to start positions differ. The set of nations and leaders was the
same, as was the set of start positions on the map, it was just the assignment
of one to the other that was perturbed (which went on to change the whole
course of the game).
I think the problem lies in init_new_game(). This pulls start positions out
of a hash (map.startpos_table) into several lists
(flexible_list/targeted_list), which are then shuffled to get the mappings.
The shuffling is deterministic, as you'd expect from fc_rand(). However, I
don't think the order in which map positions are pulled out of the hash is.
The hash is a genhash which I think uses genhash_ptr_val_func() as its
comparison function, which uses pointer comparisons. This relies on things
like heap allocation being deterministic, which I don't think we can rely on.
However, in practice, on my system, the ordering seems _quite_ deterministic,
not completely random.
Iterating the hash in some deterministic order, or sorting the lists before
shuffling, would solve this, I think.
(Wonder how many other dependencies on pointer order we have...)
Reply to this item at:
Message sent via/by Gna!
Freeciv-dev mailing list