Mersenne Twister (Codea specific)

I am porting a game I originally started in Java into Codea. It’s a solitaire engine that is kind of a geek version of solitaire. I know a geek who kept track of the seed values in free cell because he wanted to make sure he won each game – it’s that built to appeal to that type of crowd.

Anyway I wanted a nice random algorithm. I don’t know what Codea uses, so maybe it’s a good one, but my Googling has indicated that few programming languages default to a “good” random generator. Also, the Mersenne Twister provides a well-documented, decent performance, and commonly used PRNG. Python uses it by default. Lua 5.2 includes a C implementation of it (alas, Codea is 5.1). I used the MT algorithm in my Java code originally. Plus Wikipedia has pseudocode for it, which I can read more easily than C.

I quickly ran into issues when trying to port it into Codea.

  1. Codea doesn’t do 32-bit unsigned integers
  2. It’s not obvious how (if even possible) to get a 32-bit number for milliseconds that is usually used as a seed
  3. Codea doesn’t natively include the bit math (until 5.2, again)

So what I have now appears to be working. It’s entirely possible I messed up part of the algorithm so I need to do some kind of distribution tests to see. But it definitely produces a deck of cards that don’t have an obvious order, so if something is wrong it is one of the bit things were implemented wrong.

I want to share it because it seems like some or all of the code could be useful to lots of people.

If you see stuff to fix, I would welcome it. I wasn’t a CS major so your brains will probably find obvious stuff. I pulled 10,000 numbers from it, put them in a table, added concat and printed and it took under a minute to show.

Parts:
1st is the MT algorithm itself. It is pretty much directly translated from the pseudocode on Wikipedia. To run it, initialize with a seed (format is vec2(16-bit unsigned int, 16-bit unsigned int) … Keep reading for how to get one of those). Next, use mt_inRange(r) to get an int in the range [0,R). I don’t know how to convert 2 16-bit int values into 32-it floating point and since I really just want a value in a range anyway, I didn’t write it. If you prefer to get back 32 bits, just mt_extract instead.

2nd part gets entropy.
HandleGravity, handleAccel, and handleTaps take sensor info from the iPad and get squeeze out the least significant bits from them (my belief is they would be closest to random).

I left handleTaps in there, but I’m only using Gravity and UserAcceleration right now. Another note is I found neither was initialized to anything until at least sometime after setup, after the first draw. The soonest I got any number was after a screen tap, I added a “Tap to continue!” to my UI and collect my entropy after the tap. Not sure if this is on purpose, but not really a problem to my game, so…I left it.

Eventually I want to consider the holy grail of card games, a 52! shuffle (or 104! for double deck games). Right now 32-bits is ok.

3rd part does bit math with a focus on the unique challenges of doing so with vec2(16-bit int, 16-bit int).

Anyway, I submit the code so if any whole or part of it is useful, people can use it.

I’m still kind of new to Lua, so I wasn’t sure if this would be better in a class or 3 classes. So far they seem mostly just for organizational purposes and my code is pretty much 3 distinct things that all need each other … So … It’s just functions for now.

https://docs.google.com/document/d/1_WPn5yOAZWjvtKxbcQI5LAdCcTq6DPwgJgZ-pmVkat8/edit

I’ve been wanting to include MT in Codea for some time. I didn’t realise Lua 5.2 included a C implementation of it, I am interested in back-porting this to Lua 5.1. Would you please be able to add a feature request for this to the issue tracker?

Thank you for sharing your Lua Twister code. I’ve always found PRNGs a bit fascinating.

I found this page containing C libraries for use with Lua below 5.2:
http://www.tecgraf.puc-rio.br/~lhf/ftp/lua/#lrandom

He writes:
These tools are being adapted to Lua 5.2. For the time being, the 5.1 versions should work fine if you build Lua 5.2 with LUA_COMPAT_ALL or just LUA_COMPAT_MODULE. (These are the default settings.) You may need to compile my libraries with -DLUA_COMPAT_MODULE as well.

There is still the issue of bits. If the underlying MT code expects a double and all it gets is a float then the result will be garbage.

Writing it up on issue tracker.

Ok I know this isn’t overly scientific or anything, but I plotted 20,000 values pulled from my port of MT in Excel (10,000 values each from 2 different runs). It looks like tv static, spread really nicely across the graph.

I was worried because I had to rewrite some parts of the bit-shifting pseudocode so it would work with 2 ints and it seemed likely that I’d make a math error. I would have thought that would create an obvious bias. So either it doesn’t or I didn’t make any bit errors.

In the original post I mentioned the getSeed but then never explained. So I take Gravity(x,y,z) and UserAcceleration(x,y,z) and take 5 or 6 of the least significant bits from each and paste them together into the 2 16-bit values that are then returned as vec2.

Simpler explanation how to use the MT algorithm:

mt_initialize(getSeed())
-- sets it up, I recommend not doing this until after the user taps the screen at least once, the sensor might not have any state at startup

local n = mt_inRange(r)
-- get an integer in the range [0,r)

local v = mt_extract()
-- get a vec2 with a total of 32 bits to convert to whatever value you want

There’s proper tests for whether data is random - I’ll look them up.

I do like the idea of initialising the random number generator by shaking the iPad.

Etch a sketch solitaire!