Wesnoth RNG for Board Game Adaptation (dice, coins)

[chameleon_effect]

Wesnoth needs an RNG that gives returns 0-100. That's 101 possible returns. So with coins or dice, we need to emulate a d101.

Coins: "1111111"
Flip 6 coins. There are -1 + 2^7, or 127, possible outcomes. Each coin is good for 0 or 2^k points (0<=k<=6), where k=0 for the first coin, k=1 for the second coin and so on. If the sum of the coins is greater than 101, chuck the result, otherwise we get the rng d101 result we need-the sum of the dice, less 1, to align the dice sum with the index of results from 0 to 100.

dice:
three dice rolls, "x", "y" and "z". x and y get multiplied together, and that sum is multiple by 1 if z={1,2}, multiplied by 2 if z={3,4} and multiplied by 3 if z={5,6}. There are 108 possible returns. Throw the three dice again if 102 through 108 are rolled.


proof:

One can generate an integer between 1 and n so long as one can run another function (such as coin flips or dice throws) which generates random integers between 1 and m for all values of m and n.
 
if A is a subset of B, and the chance to take an element from B is equally random for all elements in B, the chance for taking an element from B that is also in A will be 1/|A| (one over the cardinality/magnitude of A) so long as elements returned that are in B-A are not considered proper returns for the function.  The chance for getting any return from B for any two elements is equal, and only |A| elements are considered eligible returns, therefore the odds of getting any return from B that is in A is 1 / |A|. 
 
For purposes of the Random Number Generator, consider only sets of integers (to take random elements from non integer sets, just have another set of the non-integers which is ordered, indexed, such as {(apple,1), (foobar,2), (mel gibson movies,3)}). 
 
if the sample space of an available RNG has |B| elements, and the desired target space has |A| elements and |A| < |B|, one can get a mapping by the above principle at least, and in some cases where |A| is a factor of |B| get a result with one 'roll'.  In cases where |A| > |B|, executions of the available RNG function can be made on subsets of Bs sample space (a roll on a subset is one which does not allow returns that are outside a desired range equal or lessar to |B| (awkward language sorry) of cardinality of factors of the desired sample space.  rolls are repeated until associated factor multiplication equals the cardinality of the desired target sample space or one which is greater though as close as possible to the cardinality of the desired sample space (as close as possible to reduce the number of rethrows necessary to get a valid result). 
 
Where rethrows are necessary, and factors, cardinalities, are specified, use of the formula to calculate the sum of an infinite geometric series will verify that probabilities of results of the bric-a-brac RNG align with that of the target one.

[Mabuse]

why "needs" wesnoth an rng that gives results from 0-100 ?



since wesnoth rng represents percentages, it is 1-100

to emulate 1-100 with dice:
use 2x 10 sided dice

(numbers on the side range from 0-9, 2x times 0 = 100, one dice is multiplied with 10)
e.g. the dice which gets multiplied by 10 shows 3, the other 7, result 37

[lipk]

There're no 10-sided dice only 4, 6, 8, 12 or 20
Btw, what's the chance that you'll ever have for example 37% chance to hit in Wesnoth? I think it's pretty low

[Kernigh]

There are only 100 possible returns. For example, suppose that I would attack an Elvish Shaman on forest, who has 70% defense. Then I roll 1 to 100. If I get 1 to 70, then I miss. If I roll 71 to 100, then I hit.

dice:
three dice rolls, "x", "y" and "z". x and y get multiplied together, and that sum is multiple by 1 if z={1,2}, multiplied by 2 if z={3,4} and multiplied by 3 if z={5,6}. There are 108 possible returns.

This method fails to give 108 different numbers. I showed this with a Python program that makes all 216 different rolls. (I prefer Ruby, but Wesnoth seems to like Python more.)

Code: Select all

# Combine the dice rolls x, y, z.
def combine(x, y, z):
    return x * y * {1: 1, 2: 1, 3: 2, 4: 2, 5: 3, 6: 3}[z]

# Do all possible rolls -- range(1, 7) gives 1 to 6, stops before 7.
rolls = [combine(x, y, z) for x in range(1, 7)
                          for y in range(1, 7)
                          for z in range(1, 7)]
text = ', '.join(map(lambda n: '%d' % n, rolls))
from textwrap import wrap
for line in wrap(text): print(line)

Code: Select all

1, 1, 2, 2, 3, 3, 2, 2, 4, 4, 6, 6, 3, 3, 6, 6, 9, 9, 4, 4, 8, 8, 12,
12, 5, 5, 10, 10, 15, 15, 6, 6, 12, 12, 18, 18, 2, 2, 4, 4, 6, 6, 4,
4, 8, 8, 12, 12, 6, 6, 12, 12, 18, 18, 8, 8, 16, 16, 24, 24, 10, 10,
20, 20, 30, 30, 12, 12, 24, 24, 36, 36, 3, 3, 6, 6, 9, 9, 6, 6, 12,
12, 18, 18, 9, 9, 18, 18, 27, 27, 12, 12, 24, 24, 36, 36, 15, 15, 30,
30, 45, 45, 18, 18, 36, 36, 54, 54, 4, 4, 8, 8, 12, 12, 8, 8, 16, 16,
24, 24, 12, 12, 24, 24, 36, 36, 16, 16, 32, 32, 48, 48, 20, 20, 40,
40, 60, 60, 24, 24, 48, 48, 72, 72, 5, 5, 10, 10, 15, 15, 10, 10, 20,
20, 30, 30, 15, 15, 30, 30, 45, 45, 20, 20, 40, 40, 60, 60, 25, 25,
50, 50, 75, 75, 30, 30, 60, 60, 90, 90, 6, 6, 12, 12, 18, 18, 12, 12,
24, 24, 36, 36, 18, 18, 36, 36, 54, 54, 24, 24, 48, 48, 72, 72, 30,
30, 60, 60, 90, 90, 36, 36, 72, 72, 108, 108

We should really multiply x, y and z. Then we get 1 to 216. (EDIT: This step is wrong. The correct formula is in the next post by chameleon_effect.) If we get 1 to 100, we keep that. If we get 101 to 200, we subtract 100. If we get 201 to 216, we drop that and reroll the dice. Now we have a random number from 1 to 100.

[chameleon_effect]

sorry. here's what I meant.
x is an integer between 1 and 6, inclusive.
y has the same story.
z is an integer between 1 and 6, incl., where returns of 1 or 2 get mapped to 1, 3 or 4 go to 2, 5 and 6 get 3.

The following combine to create a

a = 6x
b = 6x - 6 + y
c = z36 - 36 + b

am i rite?

[alexanderthegre]

There actually is a ten-sided die; they're just not made up of regular polygons. The wikipedia article: http://en.wikipedia.org/wiki/10-sided_die

[Mabuse]

There're no 10-sided dice only 4, 6, 8, 12 or 20
Btw, what's the chance that you'll ever have for example 37% chance to hit in Wesnoth? I think it's pretty low

well, maybe you are not as familar as me in the world of pen&paper rpgs, which i playED for years, when i was young. (For example "Call of Cthulhu", which uses percentages for the character skills)

but i can guarantee you that there are 10 sided dice. and they work pretty well. the whole world of pen&paper rpg use them. they are the best thing when it comes down to get percentage results.


again:
--------

to emulate 1-100 with dice:
use 2x 10 sided dice

(numbers on the sides range from 0-9, 2x 0 = 100, one dice is multiplied with 10)
e.g. the dice which gets multiplied by 10 shows 3, the other 7, result 37

of course for the best handling the dices have different colors, and the one which gets multiplied by 10 is always the same




And for that simple reason (CABD) the whole thread is completely obsolet.



ok, to give the thread a reason to exist:

if you have only 6 sides dice then do this

We should really multiply x, y and z. Then we get 1 to 216. If we get 1 to 100, we keep that. If we get 101 to 200, we subtract 100. If we get 201 to 216, we drop that and reroll the dice. Now we have a random number from 1 to 100.

[Gragorak]

There're no 10-sided dice only 4, 6, 8, 12 or 20

10-sided dice:

Spoiler:

Result of d20 = equivalent result on d10

1 = 1
2 = 1
3 = 2
4 = 2
5 = 3
6 = 3
7 = 4
8 = 4
9 = 5
10 = 5
11 = 6
12 = 6
13 = 7
14 = 7
15 = 8
16 = 8
17 = 9
18 = 9
19 = 10
20 = 10

And of course there are 20-sided dices which have numbers 1-10 (all twice) and real 10-sided dices.
Example of 10-sided dice:

Spoiler:

[lipk]

Oh, my mistake. I just had the prejudice that a dice must be a regular shape.
EDIT:

there are 20-sided dices which have numbers 1-10 (all twice)

That's still a 20-sided dice

The're no 10-sided dice

I meant it 'geometrically'

[Gragorak]

there are 20-sided dices which have numbers 1-10 (all twice)

That's still a 20-sided dice

Yes it is, but 20-sided dice (with numbers 1-10) does the same as 10-sided dice.

The're no 10-sided dice

I meant it 'geometrically'

10-sided dices are deltohedrons (pentagonal trapezohedrons).
See this.

//Edit: I found quite good picture of deltohedron.

Spoiler:

[chameleon_effect]

The RNG is my invention, btw.

[Kernigh]

sorry. here's what I meant.
x is an integer between 1 and 6, inclusive.
y has the same story.
z is an integer between 1 and 6, incl., where returns of 1 or 2 get mapped to 1, 3 or 4 go to 2, 5 and 6 get 3.

The following combine to create a

a = 6x
b = 6x - 6 + y
c = z36 - 36 + b

am i rite?

Yes, this works; c is a uniform random integer from 1 to 108.

The Python version of this is

Code: Select all

# Combine the dice rolls x, y, z.
def combine(x, y, z):
    z = {1: 1, 2: 1, 3: 2, 4: 2, 5: 3, 6: 3}[z]
    a = 6 * x
    b = 6 * x - 6 + y
    c = 36 * z - 36 + b
    return c

One can simplify it (swapping x and y) to

Code: Select all

# Combine the dice rolls x, y, z.
def combine(x, y, z):
    z = {1: 1, 2: 1, 3: 2, 4: 2, 5: 3, 6: 3}[z]
    return x + 6 * (y - 1 + 6 * (z - 1))

Here is a demonstration. Today, I will be a Dwarvish Fighter. Dwarves hate elves, so I want my axe to hack this Elvish Shaman on forest (70% defense).

A quick, healthy Dwarvish Fighter threatens a resilient, dextrous Elvish Shaman.

dwarf-assaults-elf.png (108.99 KiB) Viewed 5628 times

If I roll 1 to 70, I miss. If I roll 71 to 100, I hit. If I roll 101 to 108, I must reroll. I have no d10 or d20, so I must use my single d6.

1. First roll is 2, so x = 2.
2. Second roll is 3, so y = 3.
3. Third roll is 6, so z = 3 (because 5 or 6 gets 3).

I calculate x + 6 * (y - 1 + 6 * (z - 1)) = 2 + 6 * (2 + 6 * 2) = 2 + 6 * 14 = 86. Because 71 to 100 covers 86, I hit my enemy elf.

The most important roll is z, because this formula multiples z by 36. My 86 takes 72 from z, 12 from y and 2 from x. If I would roll 1,1,5, I would get 73, and still hit the elf. If I would roll 6,6,2, I would get 36, and miss the elf.

I might prefer a simpler system that removes x and y and keeps only z, the most important roll. Suppose that I change the elf's defense from 70% to 4/6 (around 67%). Then I only need to roll z: if I roll 1 to 4, I miss; if I roll 5 to 6, I hit. This tiny change away from Wesnoth's rules would help a board game.

[Xudo]

Why you are want to use such complicated system?
All chances in mainline wesnoth are sticked to multipliers of 10. That means you can simplify roll by using two 6-sided dice and substract 2 from roll result.

Code: Select all

			1	2	3	4	5	6
			-	-	-	-	-	-
1	-	0	1	2	3	4	5
2	-	1	2	3	4	5	6
3	-	2	3	4	5	6	7
4	-	3	4	5	6	7	8
5	-	4	5	6	7	8	9
6	-	5	6	7	8	9	10

In your demo it will look like:
First roll is 2
Second roll is 3
Their sum is 5.
After substraction it is 3.
3 < 7, so you miss.

To hit elf on 70% terrain, you need to roll 7 or more.

It's board game after all. Players would not like to do calculations most of time.

[csarmi]

ZOMG

Okay I said all this in IRC, but just to set things straight here too:

In my post I will assume that by d6, d10, d20, d100 we mean uniformly distributed values (same probability) between 0-5, 0-9, 0-19 and 0-99 respectively. You can add one to every value if you like, or you can map 0 to 6, 10, 20, 100. It doesn't matter. The only difference is in the range you have to roll for an event to have a specific chance.

For example, rolling at least 7 on a range of 0-9 is the same chance as rolling more than seven (or at least eight) on a range of 1-10. I will use the former for simplicity.

It is important to understand, however, that for a d100 or a d10 simulation you don't need 101 or 11 different outcomes. That only comes from the misunderstanding of how rolls (and ranges) work. If we roll a d10, we will get 11 different probabilities (0%, 10%, ... 100%), not 10.

• you only have to emulate 10 values, defenses are multiples of 10, if you really want to be picky, make it 20 (or 100)
• against 0% defense roll a d10 (mod 10) and if you roll at least 0, you hit (guaranteed, 100% chance)
• against 100% defense roll a d10 (mod 10) and if you roll at least than 10, you hit (impossible, 0% chance)

Now for simulation of dice rolls:

• for d10 roll a blue and a red dice, if red dice is 6 reroll, otherwise result is 5*(blue dice mod 2) + (red dice mod 5)
• my solution to emulate d10 with 2d6 is also optimal in the sense that you can't get away with less rerolls
• you can use a 6-base too: (blue mod 6)*6 + (red mod 6), discard 30-35 and watch the last digit but it is more complicated
• for a d100 use two d10 (or d20*d6 - reroll if 6 on d6), if you wanna do it with 3d6, the method described in an earlier post is good 36*(yellow mod 6) + 6*(blue mod 6) + (red mod 6) and watch last two digits

The last 'solution' presented fails completely, for two reasons: It simulates 0-10 (and we need only 10 outcomes, not 11) and what's even worse, the probabilities are not the same for all values (as the table shows very nicely).

Code: Select all

The mathematical operation x mod y means that you divide x by y and take what remains (not sure how it is called in english). For example, 17 mod 10 is 7 (17 = 1*10 +7, note that x mod 10 is always the last digit of x), 6 mod 6 is 0 (6 = 1*6 + 0)