bugBattle for Wesnoth - Bugs: bug #21706, helper.shuffle uses incorrect...

Show feedback again

bug #21706: helper.shuffle uses incorrect shuffling algorithm

Submitted by:  Eli Dupree <elvish_pillager>
Submitted on:  Fri Feb 21 22:08:35 2014  
Category: BugSeverity: 2 - Minor
Priority: 5 - NormalItem Group:  None of the others
Status: FixedPrivacy: Public
Assigned to: Alexander van Gessel <ai0867>Open/Closed: Closed
Release: 1.11.9+devOperating System: Debian Linux

Add a New Comment (Rich MarkupRich Markup):

You are not logged in

Please log in, so followups can be emailed to you.


Tue Mar 4 18:33:27 2014, comment #4:

Ah, right. It was taking quite a lot of effort to adapt my thinking to lua's 1-based indexing, so I may have overlooked that.

Alexander van Gessel <ai0867>
Project MemberIn charge of this item.
Tue Mar 4 17:45:09 2014, comment #3:

I don't see how mine is wrong, other than how it frivolously exchanges the first element with itself. Yours looks correct too, though. (Per the terminology on Wikipedia, yours is "the modern algorithm" and mine is "the inside-out algorithm".)

Eli Dupree <elvish_pillager>
Tue Mar 4 11:39:09 2014, comment #2:

Fixed Fisher-Yates in 62b287354f32. (in a different way, your suggested code was wrong too)

I'm not going to touch the synchronization stuff this late in the dev-cycle, though maybe you can convince someone who knows the area better than I do.

Alexander van Gessel <ai0867>
Project MemberIn charge of this item.
Fri Feb 21 22:12:18 2014, comment #1:

As a side note, why is it MP-unsafe? It could easily use helper.rand("1.."..index) instead of math.random. It's true that currently, that would be MP-unsafe if it was used in a non-synchronized way, such as in AI - so the function could take a boolean argument indicating which random source to use. Or, with my proposals in https://gna.org/bugs/?21697, it wouldn't need to.

Eli Dupree <elvish_pillager>
Fri Feb 21 22:08:35 2014, original submission:

helper.shuffle uses an incorrect implementation of the Fischer-Yates in-place shuffle, which produces slightly biased results. It swaps each element with a random other element from the whole list, when the algorithm calls for swapping the element with a random earlier (or same) element. In the shuffling of {1,2,3}, for instance, helper.shuffle produces half the possible results at a 4:5 ratio to the other half.

To fix, replace the line
local random = math.random( 1, length )
local random = math.random( 1, index )

(and delete the line "local length = #t", as it's now unused.)


Eli Dupree <elvish_pillager>


(Note: upload size limit is set to 1024 kB, after insertion of the required escape characters.)

Attach File(s):

No files currently attached


Depends on the following items: None found

Items that depend on this one: None found


Carbon-Copy List
  • -unavailable- added by shadowmaster (Updated the item)
  • -unavailable- added by ai0867 (Posted a comment)
  • -unavailable- added by elvish_pillager (Submitted the item)

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.


    Error: not logged in



    Follow 3 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Tue Mar 25 13:27:10 2014shadowmasterOpen/ClosedOpen=>Closed
    Tue Mar 4 11:39:09 2014ai0867StatusNone=>Fixed
      Assigned toNone=>ai0867
    Show feedback again

    Back to the top

    Powered by Savane 3.1-cleanup