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 21 Feb 2014 10:08:35 PM UTC  
 
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 04 Mar 2014 06:33:27 PM UTC, 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 04 Mar 2014 05:45:09 PM UTC, 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 04 Mar 2014 11:39:09 AM UTC, 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 21 Feb 2014 10:12:18 PM UTC, 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 21 Feb 2014 10:08:35 PM UTC, 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 )
with
local random = math.random( 1, index )

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

https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_.22inside-out.22_algorithm

Eli Dupree <elvish_pillager>

 

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

Attach File(s):
   
   
Comment:
   

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.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 3 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Tue 25 Mar 2014 01:27:10 PM UTCshadowmasterOpen/ClosedOpen=>Closed
    Tue 04 Mar 2014 11:39:09 AM UTCai0867StatusNone=>Fixed
      Assigned toNone=>ai0867
    Show feedback again

    Back to the top


    Powered by Savane 3.1-cleanup