There are a whole lot of 'phatom' like maps where they randomly choose a player to be the phantom. When there are 1, 2, 4 or 8 players in the game the task is quite simple: we have to randomize 0, 1, 2 or 3 switches and map each posible outcome to a player. When there are 3, 5, 6 or 7 players the task is not that simple. I've been thinking about it and found some algorithms which may work. That problem (when there are n players) is identical to the problem of choosing a random number between 0 and n-1, so I'll address the second problem instead. [u]Method I - Mapping every possible output[/u] This means that if we have to randomize a number between 0 and 5 we can randomize 3 switches and map every possible outcomes to one of the 6 numbers. For example: [code]000 -> 0 001 -> 1 010 -> 2 011 -> 3 100 -> 4 101 -> 5 110 -> 0 111 -> 1[/code] The biggest problem of this method is that if n is not a power of 2 we cannot have equiprobability. [u]Method II - Throwing away wrong results[/u] When we get a not valid outcome we rerandomize the switches and check them again. This way we ensure equiprobability. E.g: [code]000 -> 0 001 -> 1 010 -> 2 011 -> 3 100 -> 4 101 -> 5 110 -> Randomize again 111 -> Randomize again[/code] The biggest problem is that this algorithm might never end. Nothing ensures us that we'll not keep getting 111 forever. This is not likely to happen anyway and even in the worst case (randomizing a number between 0 and 2^m so we have to randomize m switches thus the probability of failing an attempt is ~0.5) the mean of attempts needed to get a right outcome is 1/0.5 = 2. Actually, if we're randomizing m switches and we have n possible succesful outcomes, we'll expect this method to randomly choose a right outcome in ~(2^n)/m attempts. [u]Method III - Modulo algorithm[/u] The idea behind this method is randomizing a number between 0 and an high 2 power, then using the division modulo operation to transform it into a number between 0 and n. This method ensures almost equiprobability and constant time. A good SC map implementation would be randomizing a great number of switches, then composing the binary number using on a death counter and finally substracting (n+1) until the death counter value is lower than (n+1). This example will randomize a number between 0 and 7: [code]Cond: Always Actions: - Randomize Switch 1 - Randomize Switch 2 - Randomize Switch 3 - Randomize Switch 4 - Randomize Switch 5 - Randomize Switch 6 - Randomize Switch 7 - Randomize Switch 8 Cond: Switch 1 is set Actions: - Clear switch 1 - Add 1 to death counter Cond: Switch 2 is set Actions: - Clear switch 2 - Add 2 to death counter Cond: Switch 3 is set Actions: - Clear switch 3 - Add 4 to death counter Cond: Switch 4 is set Actions: - Clear switch 4 - Add 8 to death counter Cond: Switch 5 is set Actions: - Clear switch 5 - Add 16 to death counter Cond: Switch 6 is set Actions: - Clear switch 6 - Add 32 to death counter Cond: Switch 7 is set Actions: - Clear switch 7 - Add 64 to death counter Cond: Switch 8 is set Actions: - Clear switch 8 - Add 128 to death counter Cond: Death count is atleast 8 Actions: - Substract 8 from death counter - Preserve trigger Cond: Death counter is almost 7 Actions: - (We have a random number in our death counter that ranges from 0 to 7)[/code] The best method is probably method II because it is not bad, flexible and simple to implement. If anyone knows any other method of choosing random numbers using switches please post it.

There are a whole lot of 'phatom' like maps where they randomly choose a player to be the phantom. When there are 1, 2, 4 or 8 players in the game the task is quite simple: we have to randomize 0, 1, 2 or 3 switches and map each posible outcome to a player.
When there are 3, 5, 6 or 7 players the task is not that simple. I've been thinking about it and found some algorithms which may work.

That problem (when there are n players) is identical to the problem of choosing a random number between 0 and n-1, so I'll address the second problem instead.

Method I - Mapping every possible output
This means that if we have to randomize a number between 0 and 5 we can randomize 3 switches and map every possible outcomes to one of the 6 numbers. For example:

Code

The biggest problem of this method is that if n is not a power of 2 we cannot have equiprobability.

Method II - Throwing away wrong results
When we get a not valid outcome we rerandomize the switches and check them again. This way we ensure equiprobability. E.g:

Code

The biggest problem is that this algorithm might never end. Nothing ensures us that we'll not keep getting 111 forever. This is not likely to happen anyway and even in the worst case (randomizing a number between 0 and 2^m so we have to randomize m switches thus the probability of failing an attempt is ~0.5) the mean of attempts needed to get a right outcome is 1/0.5 = 2.
Actually, if we're randomizing m switches and we have n possible succesful outcomes, we'll expect this method to randomly choose a right outcome in ~(2^n)/m attempts.

Method III - Modulo algorithm
The idea behind this method is randomizing a number between 0 and an high 2 power, then using the division modulo operation to transform it into a number between 0 and n. This method ensures almost equiprobability and constant time.
A good SC map implementation would be randomizing a great number of switches, then composing the binary number using on a death counter and finally substracting (n+1) until the death counter value is lower than (n+1).
This example will randomize a number between 0 and 7:

Code

The best method is probably method II because it is not bad, flexible and simple to implement. If anyone knows any other method of choosing random numbers using switches please post it.

PRetty sure this 'theory' is a fact, why didnt ye post in teh tutorials? ;o

PRetty sure this 'theory' is a fact, why didnt ye post in teh tutorials? ;o

[quote=name:Dark_Marine]PRetty sure this 'theory' is a fact, why didnt ye post in teh tutorials? ;o[/quote] Because it's not a tutorial yet. I had these ideas and I'm asking people for their opinion. I can also add it to the tutorials later, but I want to get some feedback first.

Quote from [Dark_Marine]

PRetty sure this 'theory' is a fact, why didnt ye post in teh tutorials? ;o

Because it's not a tutorial yet. I had these ideas and I'm asking people for their opinion.
I can also add it to the tutorials later, but I want to get some feedback first.

[url=http://Falkoner.CoW.GooglePages.com/Switches.html]Enjoy.[/url] It's a tutorial with all the general ways of using switch randomization that I know of, probably the most impressive is the Death-Switch Randomization, it only requires 1 death and one switch for any amount of outcomes, so it's like the basic switch method, but it requires much less variables, and it's similar to your third method. In my opinion, which method you use depends on what you are using it for, let's say I have an RPG where the player could hit a certain point in the map at any time, then maybe I'll use death counts instead, let's say I want 6 different outcomes in a single trigger loop, I'll use the basic switch method, it all depends on what I need in my map.

Enjoy. It's a tutorial with all the general ways of using switch randomization that I know of, probably the most impressive is the Death-Switch Randomization, it only requires 1 death and one switch for any amount of outcomes, so it's like the basic switch method, but it requires much less variables, and it's similar to your third method.

In my opinion, which method you use depends on what you are using it for, let's say I have an RPG where the player could hit a certain point in the map at any time, then maybe I'll use death counts instead, let's say I want 6 different outcomes in a single trigger loop, I'll use the basic switch method, it all depends on what I need in my map.

Your tutorial lacks one picture and its hard as hell to read with that bg... Plus most of the methods you exposed will only work if all the 8 players are playing.

Your tutorial lacks one picture and its hard as hell to read with that bg... Plus most of the methods you exposed will only work if all the 8 players are playing.

[quote]Plus most of the methods you exposed will only work if all the 8 players are playing.[/quote] How so? It doesn't require multiple players at all.... Oh, and I fixed the image, stupid imageshack randomly deletes my pictures...

Quote

Plus most of the methods you exposed will only work if all the 8 players are playing.

How so? It doesn't require multiple players at all....

Oh, and I fixed the image, stupid imageshack randomly deletes my pictures...

[quote=name:Clokr_] [u]Method II - Throwing away wrong results[/u] When we get a not valid outcome we rerandomize the switches and check them again. This way we ensure equiprobability. E.g: [code]000 -> 0 001 -> 1 010 -> 2 011 -> 3 100 -> 4 101 -> 5 110 -> Randomize again 111 -> Randomize again[/code] The biggest problem is that this algorithm might never end. Nothing ensures us that we'll not keep getting 111 forever. This is not likely to happen anyway and even in the worst case (randomizing a number between 0 and 2^m so we have to randomize m switches thus the probability of failing an attempt is ~0.5) the mean of attempts needed to get a right outcome is 1/0.5 = 2.[/quote] I'm using this methos for my map, and I am sattisfied with its functionality. It gives a result within 3 seconds at most (about 12*3 attempts). Running this algorithm while the intro is shown to the players is the best option or me.

Quote from Clokr_

Method II - Throwing away wrong results
When we get a not valid outcome we rerandomize the switches and check them again. This way we ensure equiprobability. E.g:

Code

000 -> 0
001 -> 1
010 -> 2
011 -> 3
100 -> 4
101 -> 5
110 -> Randomize again
111 -> Randomize again

The biggest problem is that this algorithm might never end. Nothing ensures us that we'll not keep getting 111 forever. This is not likely to happen anyway and even in the worst case (randomizing a number between 0 and 2^m so we have to randomize m switches thus the probability of failing an attempt is ~0.5) the mean of attempts needed to get a right outcome is 1/0.5 = 2.

I'm using this methos for my map, and I am sattisfied with its functionality. It gives a result within 3 seconds at most (about 12*3 attempts). Running this algorithm while the intro is shown to the players is the best option or me.

Yeah, it's probably the best one. Updated first post with the general mean formula for method II: [quote]Actually, if we're randomizing m switches and we have n possible succesful outcomes, we'll expect this method to randomly choose a right outcome in ~(2^n)/m attempts.[/quote]

Yeah, it's probably the best one. Updated first post with the general mean formula for method II:

Quote

Actually, if we're randomizing m switches and we have n possible succesful outcomes, we'll expect this method to randomly choose a right outcome in ~(2^n)/m attempts.

This makes me think of my code randomizer.

This makes me think of my code randomizer.

The third method is not equiprobable at all. It will make some numbers more probable than others like the first one. On the example for the first method this will look like this: you have two events to represent number 1 - 1 and 7, two events to represent number 2 - 2 and 8 and one event for the remaining numbers. This superfluous outcomes are hauniting you whenever you do. I know no method of equiprobable randomization of numers which are not powers of two and suspect there is no such a method in nature. But what you can do is to make these rerandomization events somewhat very unprobable (as unprobable as you like them to be, there is no limits) or make difference in probabilities as little as you like (no limits again). You could also randomize large numbers using one switch: COPY FOR EACH n FROM 0 TO N-1 Randomize sRandom. If sRandom is set then add 2^n deaths. ENDFOR I think it is what falkoner was talking about.

The third method is not equiprobable at all. It will make some numbers more probable than others like the first one. On the example for the first method this will look like this: you have two events to represent number 1 - 1 and 7, two events to represent number 2 - 2 and 8 and one event for the remaining numbers. This superfluous outcomes are hauniting you whenever you do. I know no method of equiprobable randomization of numers which are not powers of two and suspect there is no such a method in nature. But what you can do is to make these rerandomization events somewhat very unprobable (as unprobable as you like them to be, there is no limits) or make difference in probabilities as little as you like (no limits again).

You could also randomize large numbers using one switch:
COPY FOR EACH n FROM 0 TO N-1
Randomize sRandom.
If sRandom is set then add 2^n deaths.
ENDFOR
I think it is what falkoner was talking about.

[quote][u]Method III - Modulo algorithm[/u] The idea behind this method is randomizing a number between 0 and an high 2 power, then using the division modulo operation to transform it into a number between 0 and n. This method ensures [color=#CE091D]almost[/color] equiprobability and constant time.[/quote] Method II outcomes are 100% equiprobable. And yeah what you did is what falkoner was talking about. But it's equivalent to randomizing n different switches, so only works for powers of two. Then you would have to aply one of the methods that I explained on my first post if you had a different number of possibilities.

Quote

Method III - Modulo algorithm
The idea behind this method is randomizing a number between 0 and an high 2 power, then using the division modulo operation to transform it into a number between 0 and n. This method ensures almost equiprobability and constant time.

Method II outcomes are 100% equiprobable.

And yeah what you did is what falkoner was talking about. But it's equivalent to randomizing n different switches, so only works for powers of two. Then you would have to aply one of the methods that I explained on my first post if you had a different number of possibilities.

Yeah, Wormer, in that tutorial I posted it shows exactly how to make it :P

Yeah, Wormer, in that tutorial I posted it shows exactly how to make it

[quote]Quote [quote]Method III - Modulo algorithm The idea behind this method is randomizing a number between 0 and an high 2 power, then using the division modulo operation to transform it into a number between 0 and n. This method ensures almost equiprobability and constant time.[/quote] Method II outcomes are 100% equiprobable.[/quote] Oh, well, I'm sorry, haven't noticed [i]almost[/i]. But talking it is [i]almost[/i] equiprobable makes an illusion it is better than the first when it is not like that because they are identical. On a large scale there are only two methods of randomizing. There are only two things you can do, particularly you can attribute redundant outcomes to some of your events and get not equal probability or make rerandomization which needs more time (in mean) necessary to randomize. Everything else is just an implementation of these methods, which differs only the way attributing or rerandomization is done. [quote]I know no method of equiprobable randomization of numers which are not powers of two and suspect there is no such a method in nature.[/quote] To clearfy here I am talking about methods of certain randomization of numbers in one trigger circle. [quote]Yeah, Wormer, in that tutorial I posted it shows exactly how to make it :P[/quote] I've guessed :)

Quote

Quote

Quote

Method III - Modulo algorithm
The idea behind this method is randomizing a number between 0 and an high 2 power, then using the division modulo operation to transform it into a number between 0 and n. This method ensures almost equiprobability and constant time.

Method II outcomes are 100% equiprobable.

Oh, well, I'm sorry, haven't noticed almost. But talking it is almost equiprobable makes an illusion it is better than the first when it is not like that because they are identical. On a large scale there are only two methods of randomizing. There are only two things you can do, particularly you can attribute redundant outcomes to some of your events and get not equal probability or make rerandomization which needs more time (in mean) necessary to randomize. Everything else is just an implementation of these methods, which differs only the way attributing or rerandomization is done.

Quote

I know no method of equiprobable randomization of numers which are not powers of two and suspect there is no such a method in nature.

To clearfy here I am talking about methods of certain randomization of numbers in one trigger circle.

Quote

Yeah, Wormer, in that tutorial I posted it shows exactly how to make it

I've guessed

[quote=name:Wormer]Oh, well, I'm sorry, haven't noticed [i]almost[/i]. But talking it is [i]almost[/i] equiprobable makes an illusion it is better than the first when it is not like that because they are identical. On a large scale there are only two methods of randomizing. There are only two things you can do, particularly you can attribute redundant outcomes to some of your events and get not equal probability or make rerandomization which needs more time (in mean) necessary to randomize. Everything else is just an implementation of these methods, which differs only the way attributing or rerandomization is done.[/quote] Your right, you could use 'Method I' and randomize a lot of switches to make it almost equiprobable. But it takes a whole lot more triggers than 'Method III' does to archieve the same effect. In the examples, I needed 11 triggers to randomize 8 switches; using 'Method I' I'd need 257 triggers.

Quote from Wormer

Oh, well, I'm sorry, haven't noticed almost. But talking it is almost equiprobable makes an illusion it is better than the first when it is not like that because they are identical. On a large scale there are only two methods of randomizing. There are only two things you can do, particularly you can attribute redundant outcomes to some of your events and get not equal probability or make rerandomization which needs more time (in mean) necessary to randomize. Everything else is just an implementation of these methods, which differs only the way attributing or rerandomization is done.

Your right, you could use 'Method I' and randomize a lot of switches to make it almost equiprobable. But it takes a whole lot more triggers than 'Method III' does to archieve the same effect.
In the examples, I needed 11 triggers to randomize 8 switches; using 'Method I' I'd need 257 triggers.

[quote]Method II: The biggest problem is that this algorithm might never end. Nothing ensures us that we'll not keep getting 111 forever. [/quote] The chances are very low that it would take more than the 16 trigger cycles Method III will take on average.

Quote

Method II:
The biggest problem is that this algorithm might never end. Nothing ensures us that we'll not keep getting 111 forever.

The chances are very low that it would take more than the 16 trigger cycles Method III will take on average.