RE: [Flashcoders] semi-OT: Pseudo-random number sequence
At 10:50 AM +0100 7/19/06, Danny Kodicek wrote: > I get the impression it is a set number of turns. In that case, you'll need to be a bit canny, doing something like biasing the roll according to the distance to the goal. I enjoyed this problem way too much, so I've written an implementation (in Lingo, I'm afraid - it's my first language. But it should be easy enough to follow) Danny, Wow! Thanks. I ended up doing something much simpler, basically because I don't really care too much about the apparent distribution. Yours is way more elegant. Here's what I did. In pseudo-code (mostly because I'm embarrassed this is still AS1): To move S squares in N turns - Fill an array of length N with random numbers - While the sum of array members' values does not equal S: * Sort the array * Calculate the difference between S and the sum * If the difference is positive, increase the value of the first array member by the difference or by 5, whichver is smaller * If the difference is negative, decrease the value of the last array member by the difference or by 5, whichever is smaller - Sort the array - If the last array member is smaller than the number of spaces to move plus one minus the number of remaining turns, start over - Remove the last array member and store in a variable - Randomize the array order, then push the last member to the array I'm not 100% sure this will work, especially the test near the end to determine if the final roll is big enough to allow extra turns to be added. Thanks again. -Jim ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
Re: [Flashcoders] semi-OT: Pseudo-random number sequence
At 1:58 AM -0500 7/19/06, ryanm wrote: - there are n integers in the sequence - the sum of the integers in the sequence is x - the value of each integer in the sequence is between 1 and 6, inclusive There are a couple of things that I'm not following. 1. Does the board have a static number of spaces? Yes (25 in this case). 2. Are there a set number of turns, or can it take as long as it takes? There are a minimum of 7 turns, and a maximum of 9. Each turn consists of a roll, a move on the board, and a question for the player to answer. If a player answers all questions correctly, the game must consist of exactly 7 turns. If they get one or two wrong, one or two turns need to be added so they can still achieve a perfect winning score. If they get more than two wrong, they can't get the perfect score (we have only 9 questions to work with, so the game can't be extended beyond that). 3. Why do you need to know all of the rolls in advance, can't you just make your "roll" function ensure that the last roll is always exactly the right number of spaces? I don't need to know the rolls in advance, but the player has to be able to reach the end on the last roll. Given 7 turns, 25 spaces and a six-sided die, if a random-only solution produced [1,3,4,2,1,2] for the first six rolls, it would be impossible to reach the end space on the seventh roll. I figure the best way to do this is generate the roll sequence based on where they are, examine it to make sure they can reach, adjust it if necessary, and redo the whole thing if the number of turns changes. -Jim ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
RE: [Flashcoders] semi-OT: Pseudo-random number sequence
> I get the impression it is a set number of turns. In that case, > you'll need > to be a bit canny, doing something like biasing the roll according to the > distance to the goal. I enjoyed this problem way too much, so I've written an implementation (in Lingo, I'm afraid - it's my first language. But it should be easy enough to follow) on getRolls tSquares, tTurns, tList if voidP(tList) then tList = [] if tTurns = 1 then tList.add(tSquares) return tList end if tMean = 1.*tSquares / tTurns -- Find the minimum value needed: min q>=1 such that (S-q)/(n-1)<=6 tMin = tSquares - 6*(tTurns - 1) if tMin<1 then tMin = 1 if tMin>6 then return #no -- Find the maximum value needed: max r<=6 such that (S-r)/(n-1)>=1 tMax = tSquares - (tTurns - 1) if tMax>6 then tMax = 6 if tMax<1 then return #no if tMax = tMin then -- Only one possible answer here tRoll = tMin else tOptions = tMax - tMin -- Set probability distribution tWeight = 1 - 1.0/tTurns tProbabilities = [] tProbMean = tMean - tMin -- ensure p lies between 0 and 1 tSkew = min(tProbMean, tOptions - tProbMean) if tWeight> 2*tSkew / tOptions then tWeight = 2*tSkew / tOptions end if tBinomialProb = (tProbMean - tWeight*tOptions/2) / ((1 - tWeight)*tOptions) repeat with i = 0 to tOptions tProbabilities.add(tWeight/(tOptions+1) + (1 - tWeight)*choose(tOptions,i)*power(tBinomialProb,i)*power(1-tBinomialProb, tOptions-i)) end repeat -- choose a random number according to this distribution r = random(1000) repeat with i = 1 to tProbabilities.count tProb = tProbabilities[i]*1000 if rn/2 then return choose(n,(n-k)) tRes = 1 repeat with i=0 to k-1 tRes = tRes * (n-i) end repeat repeat with i=1 to k tRes = tRes / i end repeat return tRes end on getLotsOfRolls s, n, m repeat with i=1 to m put getRolls(s,n) end repeat end I asked for getLotsOfRolls(50,15,20) and got this: -- [6, 4, 3, 6, 6, 4, 1, 5, 1, 1, 5, 1, 1, 1, 5] -- [5, 6, 1, 5, 5, 2, 2, 1, 1, 2, 2, 6, 4, 4, 4] -- [3, 6, 5, 2, 4, 2, 1, 1, 6, 5, 6, 1, 1, 3, 4] -- [5, 4, 1, 3, 5, 6, 1, 1, 3, 2, 3, 1, 4, 6, 5] -- [1, 3, 2, 1, 1, 1, 5, 3, 2, 6, 6, 6, 2, 5, 6] -- [1, 5, 2, 2, 2, 4, 1, 6, 4, 1, 6, 6, 1, 4, 5] -- [4, 1, 6, 6, 2, 1, 1, 3, 2, 4, 3, 6, 3, 5, 3] -- [3, 6, 1, 3, 4, 2, 1, 1, 6, 2, 3, 1, 6, 6, 5] -- [5, 3, 1, 4, 6, 1, 2, 3, 2, 3, 3, 6, 1, 4, 6] -- [1, 5, 4, 1, 4, 3, 1, 5, 5, 5, 3, 4, 5, 1, 3] -- [2, 2, 5, 4, 3, 2, 3, 4, 1, 5, 6, 3, 1, 3, 6] -- [1, 1, 2, 5, 6, 2, 5, 1, 5, 2, 6, 3, 5, 4, 2] -- [1, 4, 5, 3, 3, 6, 4, 1, 4, 3, 1, 5, 6, 1, 3] -- [3, 5, 1, 3, 4, 3, 3, 3, 1, 6, 6, 4, 3, 3, 2] -- [3, 4, 4, 1, 6, 5, 6, 1, 1, 1, 4, 6, 1, 1, 6] -- [1, 6, 5, 3, 2, 1, 5, 2, 5, 6, 1, 6, 1, 3, 3] -- [1, 5, 3, 2, 5, 2, 2, 2, 3, 5, 5, 4, 3, 6, 2] -- [1, 2, 5, 1, 2, 6, 5, 5, 2, 2, 3, 6, 4, 2, 4] -- [2, 5, 1, 6, 4, 3, 1, 3, 3, 5, 2, 3, 1, 6, 5] -- [3, 1, 2, 3, 3, 4, 2, 5, 6, 5, 1, 3, 3, 4, 5] Looks pretty decent to me. Danny ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
RE: [Flashcoders] semi-OT: Pseudo-random number sequence
> > - there are n integers in the sequence
> > - the sum of the integers in the sequence is x
> > - the value of each integer in the sequence is between 1 and
> 6, inclusive
> >
>
> There are a couple of things that I'm not following.
>
> 1. Does the board have a static number of spaces?
> 2. Are there a set number of turns, or can it take as long as it takes?
I get the impression it is a set number of turns. In that case, you'll need
to be a bit canny, doing something like biasing the roll according to the
distance to the goal. In pseudocode:
To move S squares in N turns
Divide S by N to get the average number needed: call it m
Find the minimum value needed: min q>=1 such that (S-q)/(n-1)<=6
Fing the maximum value needed: max r<=6 such that (S-r)/(n-1)>=1
(If you can't find any such q or r then the problem can't be solved)
Now you need to find a number between q and r with expected value m. If r-q
= Z then we're looking for a set of probabilities p[i] such that:
Sum(i=0 to Z) {q+i)*p[i]} = m, with 0<=p[i]<=1 and sum(p[i]) = 1
This evaluates to q + mean(p[i]) = m, so any distribution of Z+1
probabilities with a mean of m-q will work. For example you could use a
binomial distribution p[i] = C(Z,i)p^i*(1-p)^i, where p = (m-q)/Z - however
this would probably be a bit too noticeable as you'd get very few 1's or
6's. To reduce this skew, you could make a weighted average of a uniform
distribution and a binomial distribution. Back-of-the-envelope calculations
suggest:
p[i] = t/(Z+1) + (1-t) C(Z,i)p^i*(1-p)^i
Here, t is a parameter that describes the weighting, set by you (you could
start with t = 1, a completely uniform distribution, then gradually reduce
it to make the rolls more deterministic towards the end; or you could change
t depending on how far m is from the unbiased value of 3.5). For a given t,
you can determine p so as to get the correct mean m - I think this amounts
to:
p = (m - tZ/2) / ((1-t)*Z)
There are plenty of other distributions you could use instead.
Nice problem!
Danny
___
Flashcoders@chattyfig.figleaf.com
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com
Re: [Flashcoders] semi-OT: Pseudo-random number sequence
- there are n integers in the sequence
- the sum of the integers in the sequence is x
- the value of each integer in the sequence is between 1 and 6, inclusive
There are a couple of things that I'm not following.
1. Does the board have a static number of spaces?
2. Are there a set number of turns, or can it take as long as it takes?
3. Why do you need to know all of the rolls in advance, can't you just make
your "roll" function ensure that the last roll is always exactly the right
number of spaces?
The following function will generate a (semi-) random number from 1 to
6, and always cause the last roll to land exactly on the last game board
space:
function roll(current:Number):Number{
var iBoardSize:Number = 50; // 50 spaces on the board
current = (current==undefined)?0:current; // make sure current is set
var maxroll:Number = iBoardSize - current; // largest number you can
roll
var r:Number = Math.floor(Math.random()*5)+1; // generate random number
r = (r>maxroll)?maxroll:r; // if roll is larger than maxroll, substitute
maxroll
return(r);
}
Prior to the last 6 spaces, the roll can never be larger than maxroll,
because maxroll will be like 35 and the roll is only 1-6. But on the last 6
spaces, it is possible for the roll to be higher than the last space, so you
substitute maxroll. It gets more complicated if you need to know all the
roll sin advance, or if there are always a set number of turns, etc, but not
too much more complicated.
ryanm
___
Flashcoders@chattyfig.figleaf.com
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com
[Flashcoders] semi-OT: Pseudo-random number sequence
Hi, I'm trying to come up with a way to generate a pseudo-random sequence of integers that meet the following conditions: - there are n integers in the sequence - the sum of the integers in the sequence is x - the value of each integer in the sequence is between 1 and 6, inclusive Basically, I'm trying to create a game in which users roll a die and move their piece along a game board, but arranging things so that on the last turn they reach the "finish" space exactly. (It's all for fun, so there are no ethical concerns about "rigging.") There are a few times during the game where the number of turns remaining might increase by one, so I have to be able to recalculate the sequence on the fly based on the player's current board position. I suppose I'll also have to make sure the player doesnt' get too close to the finish space on the penultimate turn, in case an extra turn needs to be added. If anyone has any ideas, I'd be most appreciative! Thanks in advance, Jim ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
