$1254 calcBinominal Question

Talk about everything related to general reverse engineering of computer games!

Moderator: Kroah

$1254 calcBinominal Question

Postby searle » 14 May 2007, 21:00

I've been staring at the code for over an hour now and I just don't get it :-(

I just don't see the "binominal" in the function. What the function does for me is:
- find a random r number between -1530; 1530
- if Y==0, r /= 2
- if Y==2, r *= 2
- cut off the lower byte (r >>= 8 )

Conclusions:
- As Y is either 0, 1 or 2, loc_1295 is even never reached.
- r is [-5 .. 5] ( ... * Y )
- not binominal, same chance for every possible result

What am I missing?

Cheers,
searle
searle
 
Posts: 12
Joined: 30 Apr 2007, 11:35
Location: Berlin

Re: $1254 calcBinominal Question

Postby Kroah » 15 May 2007, 11:05

Hi Searle,

searle wrote:- find a random r number between -1530; 1530


Here, you can't say this straight because [-1530; 1530] are the bounds of the sum of random numbers, not the random number itself.

The distribution is not linear:
When you take 12 random numbers between [0;255] ([0; 1.0] because fixed) and you sum them up, you obtain a gaussian distribution. In fact, the result follows a "normal law" when the number of dices (here 12) tends to infinite.

So, you can't say that taking a number between [0;8] is the same as the sum of 4 random numbers between [0;2] because the distribution (the probability to have a 4 for example) is not the same.

After the sum, the result is centered at 0 by substracting 1530. And finally, it's divided according to Y like you said.

The result is a fixed number on two bytes (a word) where the fixed part is in the low byte. So the result is between [-5.98...; 5.98...].

Does this help you ?

Cheers,
Kroah
Kroah
Site Admin
 
Posts: 412
Joined: 07 Feb 2006, 01:01
Location: France

Postby searle » 20 May 2007, 14:01

Great, thanx! I knew I was missing something...

Searle
searle
 
Posts: 12
Joined: 30 Apr 2007, 11:35
Location: Berlin

Nearly....

Postby searle » 21 May 2007, 21:46

Hmm I wish my maths were better...

This Java implementation:
Code: Select all
package mule;

import java.util.*;

public class Test {

   static Random random= new Random();

   static int calcBinominal(int value, int fluctuation) {

      if (fluctuation == 0) return value;

      int r= -255 * 6;
      for(int i= 0; i < 12; i++) {
         r += random.nextInt(256);
      }
      
      if (fluctuation == 1) return value + r / 512;
      return value + r * (fluctuation - 1) / 256;
   }

   public static void main(String[] args) {
      int[] res= new int[12];
      
      for (int i= 0; i < 10000000; i++) {
            res[calcBinominal(0, 2) + 5]++;
      }
      
      for (int i= 0; i < 11; i++) {
         System.out.print(res[i]);
         System.out.print(" ");
      }
      System.out.println();
   }
}

outputs
Code: Select all
0 84 10170 213806 1388504 6775051 1388989 213374 9946 76 0


which differs from your numbers:

Code: Select all
1254 ; Répartition:
1254 ; -4:  0.013%
1254 ; -3:  0.562%
1254 ; -2:  6.248%
1254 ; -1: 24.303%
1254 ;  0: 37.748%
1254 ;  1: 24.303%
1254 ;  2:  6.248%
1254 ;  3:  0.562%
1254 ;  4:  0.013%


Do you see the cause of the difference?

Cheers,
Searle
searle
 
Posts: 12
Joined: 30 Apr 2007, 11:35
Location: Berlin

p.s.

Postby searle » 21 May 2007, 23:47

For fluctuation == 1 I get
Code: Select all
0 0 0 82 224460 9550955 224438 65 0 0 0


Searle
searle
 
Posts: 12
Joined: 30 Apr 2007, 11:35
Location: Berlin

Postby Kroah » 22 May 2007, 17:35

You seem to have an error in your program. I've translated it to Javascript (I haven't another language at work) and it gives me the same result as the presumed probabilities:

Computed probabilities (Amplitude 1):
Code: Select all
0: 0
1: 0
2: 0
3: 0
4: 0.1
5: 15.925
6: 67.855
7: 16.019
8: 0.101
9: 0
10: 0
11: 0
12: 0
Somme: 100%
Amplitude: 1
Factor: 0.5


Javascript program (from yours) (Amplitude 1):
Code: Select all
0 0 0 0.089 15.855 68.076 15.876 0.104 0 0 0


Computed probabilities (Amplitude 2):
Code: Select all
0: 0
1: 0
2: 0.012
3: 0.543
4: 6.164
5: 24.271
6: 37.885
7: 24.356
8: 6.209
9: 0.549
10: 0.012
11: 0
12: 0
Somme: 100.001%
Amplitude: 2
Factor: 1


Javascript program (from yours) (Amplitude 2):
Code: Select all
0.001 0.013 0.499 5.931 24.446 38.048 24.396 6.098 0.553 0.015 0


Here's the Javascript program (from yours) (launch it from IE):
Code: Select all
<script>
function calcBinominal (value, fluctuation) {
  if (fluctuation == 0) {
    return value;
  }

  var r= -255 * 6;
  for (var i= 0; i<12; i++) {
    r += Math.round (255*Math.random ());
  }

  if (fluctuation == 1) {
    return (value + Math.round (r / 512));
  }
  return (value + Math.round (r * (fluctuation - 1) / 256));
}


var res = new Array ();
for (var i=0; i<12; i++) {
 res [i] = 0;
}

for (var i=0; i<100000; i++) {
  res [calcBinominal(0, 2) + 5] += 1;
}

for (var i= 0; i<11; i++) {
  document.write (res[i]/1000);
  document.write (" ");
}
</script>


Here's my Javascript program to compute probabilities:
Code: Select all
<script>

var nbDices = 12;
var maxOnDice = 255;
var amplitude = 2;



var factor = null;
if (amplitude == 0) {
  factor = 0;
}
else if (amplitude == 1) {
  factor = 0.5;
}
else {
  factor = amplitude-1;
}

var tab = InitDice (maxOnDice);
var result = AddDices (tab, nbDices);


for (var i=0; i<result.length; i++) {
  document.write (i + ": " + result [i] + "<br />");
}

var result2 = new Array ();
for (var i=0; i<=nbDices; i++) {
  result2 [i] = 0;
}

var somme = 0;
for (var i=0; i<result.length; i++) {
  var i2 = (i - 1530) * factor + 1530;
  result2 [Math.round((i2+6)/256)] += result [i];
  somme += result [i];
}

var somme2 = 0;
for (var i=0; i<result2.length; i++) {
  var nb = Math.round ((result2 [i] / somme)*100000)/1000;
  document.write (i + ": " + nb + "<br />");
  somme2 += nb;
}
document.write ("Somme: " + somme2 + "%<br />");
document.write ("Amplitude: " + amplitude + "<br />");
document.write ("Factor: " + factor + "<br />");


function InitDice (max) {
  var tab = new Array ();
  for (var i=0; i<=max; i++) {
    tab [i] = 1;
  }
  return (tab);
}

function AddDices (tabDice, nb) {
  var result = null;
  for (var i=0; i<nb; i++) {
    document.write ('Dice ' + (i+1) + '...');
    result = AddDice (tabDice, result);
    document.write (' Done<br />');
  }
  return (result);
}

function AddDice (tabDice, tabPrev) {
  var tabNext = new Array ();
  if (tabPrev == null) {
    for (var i=0; i<tabDice.length; i++) {
      tabNext [i] = tabDice [i];
    }
  }
  else {
    for (var i=0; i<=(tabDice.length-1+tabPrev.length-1); i++) {
      tabNext [i] = 0;
    }
    for (var i=0; i<tabDice.length; i++) {
      for (var j=0; j<tabPrev.length; j++) {
        tabNext [i+j] += tabDice [i] * tabPrev [j];
      }
    }
  }
  return (tabNext);
}
</script>


If you have any idea why we don't have the same result... good luck ;)
Cheers
Kroah
Site Admin
 
Posts: 412
Joined: 07 Feb 2006, 01:01
Location: France

Math.round problem

Postby searle » 22 May 2007, 18:45

Maybe the problem is that there is no proper cast to int in JavaScript?
I think that using Math.round and Math.floor is not correct, mainly because Math.floor(-0.2) == -1 (and not 0). I changed your script to what I think is a closer adaption of the 6502 code. (And, closer to the Java version which doesn't use floats aniway.)

Code: Select all
<script>
function int(a) {
    if (a < 0) return -Math.floor(-a);
    return Math.floor(a);
}
function calcBinominal (value, fluctuation) {
  if (fluctuation == 0) {
    return value;
  }
  var r= -255 * 6;
  for (var i= 0; i<12; i++) {
    r += int(256*Math.random ());
  }
  if (fluctuation == 1) {
    return (value + int(r / 512));
  }
  return (value + int(r * (fluctuation - 1) / 256));
}


var res = new Array ();
for (var i=0; i<12; i++) {
 res [i] = 0;
}

for (var i=0; i<100000; i++) {
  res [calcBinominal(0, 2) + 5] += 1;
}

for (var i= 0; i<11; i++) {
  document.write (res[i]/1000);
  document.write (" ");
}
</script>


This results in
Code: Select all
0 0.001 0.111 2.032 13.955 67.745 13.887 2.171 0.098 0 0


So maybe there's a problem in your calculations?

What do you think?

Cheers,
Dietrich
searle
 
Posts: 12
Joined: 30 Apr 2007, 11:35
Location: Berlin

Postby Kroah » 23 May 2007, 01:12

Some points:

- I don't understand why you say to not use Math.floor, since i've never used it. Even if you talked about the 'bug' in Math.floor, i've checked Math.round and it works correctly with negative numbers (Math.round (-0.4) gives 0 and Math.round (-0.6) gives -1).

- In your script, you floor the number instead of rounding it, i don't understand why, can you give me more informations? The 6502 code rounds the divisions when casting from fixed to int, it never truncates it (or i've missed it).

- If you change Math.floor with a Math.round (like in my first program), you get the 'good' result. I think it's the good one because it's the same as the result from the second program which computes all the possible distributions (and not a sample) and in this one.

- I think if you put a round up in your Java code, you should get the 'correct' result (Java seems to truncate when casting from float to int, doesn't it ?).

- I've corrected a minor bug i've done: Math.random chooses a number between [0; 1[ (0 inclusive, 1 exclusive). So to choose a number between [0; 255], the code must be: Math.floor (256*Math.random ())

If you can light me on those points, i could look deeper in my algorithms.
Thanks in advance,
Pascal

Edit: just to mention that my first program (translated from yours), computes a sample whereas my second program computes the exact probabilities by enumerating all possible combinations (beside an eventual bug).
Kroah
Site Admin
 
Posts: 412
Joined: 07 Feb 2006, 01:01
Location: France

Of course you're right

Postby searle » 23 May 2007, 10:41

Ok, I must have been too tired or something obviously. Sorry for asking you rubbish questions. Anyway, i finally understood the subject and have a running version which produces the correct results:

Code: Select all
package mule;

import java.util.*;

public class Test {

   static Random random= new Random();
   

   static int calcBinominal(int value, int fluctuation) {

      if (fluctuation == 0) return value;

      int r= -6 * 255;
      for(int i= 0; i < 12; i++) {
         r += random.nextInt(256);
      }
      if (fluctuation == 1) {
         r >>= 1;
      }
      else if (fluctuation > 2) {  // For completeness, it never happens...
         r *= fluctuation - 1;
      }

      // Round, see $12AA
      if ((r & 255) > 128) r += 256;
      
      return value + r >> 8;
   }

   /**
    * @param args
    */
   public static void main(String[] args) {

      int[] res= new int[11];
      
      for (int i= 0; i < 10000000; i++) {
            res[calcBinominal(0, 2) + 5]++;
      }
      
      for (int i= 0; i < 11; i++) {
         System.out.print(" - ");
         System.out.printf("%.1f", res[i] / 100000f);
      }
      System.out.println();
   }
}


results:
Code: Select all
 - 0,0 - 0,0 - 0,6 - 6,2 - 24,3 - 37,9 - 24,3 - 6,2 - 0,5 - 0,0 - 0,0
 - 0,0 - 0,0 - 0,0 - 0,1 - 16,1 - 67,9 - 15,8 - 0,1 - 0,0 - 0,0 - 0,0


Thanx for your help!!!

Cheers,
Searle

P.S.: Price calculation and Land grant AI seem to work...
Sneak preview: http://www.mediafire.com/?8bzjykj111s
searle
 
Posts: 12
Joined: 30 Apr 2007, 11:35
Location: Berlin

Postby Kroah » 23 May 2007, 21:46

Glad we've found the source of the problem.

Have a nice coding!
Pascal
Kroah
Site Admin
 
Posts: 412
Joined: 07 Feb 2006, 01:01
Location: France

Postby Kroah » 24 May 2007, 00:42

Could you attach the file to your post? I've put back file attachment.

Thanks!
Pascal
Kroah
Site Admin
 
Posts: 412
Joined: 07 Feb 2006, 01:01
Location: France

Dunno

Postby searle » 24 May 2007, 14:58

Sure? It's 12 MB...

Cheers,
Searle
searle
 
Posts: 12
Joined: 30 Apr 2007, 11:35
Location: Berlin

Postby Kroah » 24 May 2007, 16:55

Yeah, i've lot of disk space. But i hope uploading 11MB will not give a time out on the server. Let's see ;)

PS: I'm unable to download from mediafire, dunno why. After the page is loaded and i click on start, i receive a timeout... tried several times.
Kroah
Site Admin
 
Posts: 412
Joined: 07 Feb 2006, 01:01
Location: France

Didn't work

Postby searle » 24 May 2007, 17:57

Got a 500 error..

Try this:
http://rapidshare.com/files/33141399/muledist.zip.htm

or that:
http://www.sendspace.com/file/cbpfae

Did it work? (Which one?)

Cheers,
Searle
searle
 
Posts: 12
Joined: 30 Apr 2007, 11:35
Location: Berlin

Postby Kroah » 24 May 2007, 23:53

Rapidshare works great, thanks.

Nice work. I see you use JMonkeyEngine, good library.

Keep up coding and good luck!
Pascal
Kroah
Site Admin
 
Posts: 412
Joined: 07 Feb 2006, 01:01
Location: France

Next

Return to General Discussion

Who is online

Users browsing this forum: No registered users and 2 guests