Suggestion. Update the random generator to Mersenne twister.

[Mind]

I have tried Battle for Wesnoth for some time now and I have gotten the feeling that the results in battle tend to clump together a little bit more than they should. For instance missing all spell attacks 8 times in a row, and then miss them all again the next turn. I know, getting a "feel" for a random number generator is not an easy thing, our psyche is not perfect in the sense that we have a tendency to remember only the particulary high/low or good/bad results. (And I have of course taken all the statistics into consideration... that I know of anyway)

Still, I could not shake that feeling. So I downloaded the source and checked it out. Now, I must stress, I do not particulary like to complain at stuff, especially since I love the game. I really really appreciate all the hard work the developers are putting in. But it is my opinion that the algorithm could be switched to a better one. (at least better than rand 3)

My suggestion is the Mersenne twister (or similar). A wonderful algorithm. Simple, small, and fast. And it is also well known and well tested. There is also lots of working examples, c++ snippets and classes etc. So it's easy to get working.

Now, I have not followed the code enough to draw any conclusions wether there is a problem with seeding or initializing, but it could be worth considering a change. I could of course modify the source myself but then only me and my friends would benefit. It would be better if it was official.

Here is a place where it can be downloaded: http://www.agner.org/random/
But a google search for it should yield tons of info.

Regards / Mind

[henka]

I 2nd this. Personaly i got not much experience with randomizers but mind made a demo application demonstrating the.. uselessness of rand(3). This demonstration proved (even for someone as sceptical as me) his point.

So if you dont want 4 mages to miss 8 hits in a row (wich should NEVER happen with 70%) you should listen to this guy.

[zookeeper]

Still, I could not shake that feeling. So I downloaded the source and checked it out. Now, I must stress, I do not particulary like to complain at stuff, especially since I love the game. I really really appreciate all the hard work the developers are putting in. But it is my opinion that the algorithm could be switched to a better one. (at least better than rand 3)

My suggestion is the Mersenne twister (or similar). A wonderful algorithm. Simple, small, and fast. And it is also well known and well tested. There is also lots of working examples, c++ snippets and classes etc. So it's easy to get working.

Now, I have not followed the code enough to draw any conclusions wether there is a problem with seeding or initializing, but it could be worth considering a change. I could of course modify the source myself but then only me and my friends would benefit. It would be better if it was official.

Well, if you're going to argue that the current RNG has a flaw of some kind, meaning that it's not random enough, then you'd have to point that out somehow. Like make a prediction of how exactly the current RNG is skewed, and then make it generate enough numbers to prove that.

4 mages to miss 8 hits in a row (wich should NEVER happen with 70%)

Good try! But seriously, we get quite enough people here who really believe nonsense like that, so sarcastic remarks like that are better left to some other topics. Besides, being a forum newbie, someone might easily think you're one of those people, so better be careful.

[Gambit]

I don't get it. You want to replace the current RNG with a supposedly better RNG?

[ozean]

maybe a look at a thread from 2009 on this topic is helpful:

http://forums.wesnoth.org/viewtopic.php?f=10&t=23905

[thespaceinvader]

Prove it. Provide replays in large enough numbers that statistically you can demonstrate that your proposed RNG is better than the current RNG, and enough to make it worthwhile to change over. A hint: replays.wesnoth.org is available, and has records of EVERY game played on the official server. If you can;t prove your case with that, you probably can't prove your case.

[Dave]

I have tried Battle for Wesnoth for some time now and I have gotten the feeling that the results in battle tend to clump together a little bit more than they should.

It is normal for random numbers to clump together more than people think they should.

But it is my opinion that the algorithm could be switched to a better one. (at least better than rand 3)

rand() is not an algorithm. rand() is a standard C function that is implemented using an algorithm. There was a time when some C implementors used fairly poor algorithms to implement rand(), but these days all the C implementations that I'm aware of use sophisticated implementations that work very well.

I'm not sure why anyone would think that C platform vendors would intentionally choose a very poor algorithm to implement rand(), but it appears to be a common misconception. By contrast, most vendors try to make the quality of their C implementation as good as possible, and so implement a RNG that works as well as possible on their target hardware.

My suggestion is the Mersenne twister (or similar). A wonderful algorithm. Simple, small, and fast. And it is also well known and well tested.

As far as my understanding goes, the main advantages of the mersenne twister are that it's fast and has a very long period.

I think the efficiency and period of any modern C implementation's version of rand() is fine for a strategy game.

If you can demonstrate that the mersenne twister actually provides better results, we might consider it. Otherwise I don't think it's worth putting any effort into. I doubt anyone could perceive a difference between any modern implementation of rand() and the mersenne twister.

David

[Max]

here's a really awesome list worth reading:
Biases in probability and belief

i guess the only thing that could be done to get an rng that would feel "more randomly" would be to implement a less random one:
New RNG to preventing exceptional luck

and things like that have been turned down in the past (for a good reason^^)...

[Mind]

I checked it up some more and the documentation for the currently implemented rand actually states that it is poor. I made a program to demonstrate it a couple of years ago, although I don't still have it I guess I can make a program again that demonstrates it. I'm not saying it has to be Mersenne, there has been some improvement to that as well called Mother of all generators or something similar. Is the randomness is bad enough to be worth changing it? I'm not sure. Maybe. It would not be too much work changing it though but I can examine the randomness some more if you want. I did not want to come here and flail around with a stick in a hornets nest, just making some suggestions =)

Sorry about starting a new thread about it, actually searched the forum but I could not check the next page because it said I was not allowed to search any more.

Cheers!

[Mind]

here's a really awesome list worth reading:
Biases in probability and belief

i guess the only thing that could be done to get an rng that would feel "more randomly" would be to implement a less random one:
New RNG to preventing exceptional luck

and things like that have been turned down in the past (for a good reason^^)...

Well, hence why I said "our psyche is not perfect in the sense that we have a tendency to remember only the particulary high/low or good/bad results" in the beginning of my first post, I was waiting for exactly this link to show up

[Dave]

I checked it up some more and the documentation for the currently implemented rand actually states that it is poor.

What platform are you talking about, and what documentation?

If you are talking about Linux then note that the standard Linux implementation of rand() used to be of poor quality for many purposes (though probably still fine for a game), but all Linux distributions I'm aware of now implement rand() the same way as random(), and have done so for some time. random() is implemented with a linear feedback algorithm with a long period and good results on statistical tests.

Unfortunately many Linux distributions failed to update their man pages for rand() for some time, continuing to lead people to believe that the implementation was (relatively) poor.

David

[Mind]

Yes, it was in fact the linux version I read it about. Then you might be correct in that an upgrade is unnecessary. I'll do some tests and comparisons when I have some time over and get back to you guys with what I find out.

[Dave]

Honestly, it's 2010. The C standard with rand() in it dates to 1989. If your platform doesn't have a decent enough implementation of rand() yet for something casual like a -strategy game- then you need to move to a better OS where they can actually make a reasonable implementation of the C standard library.

David

[zaimoni]

My suggestion is the Mersenne twister (or similar). A wonderful algorithm. Simple, small, and fast. And it is also well known and well tested.

As far as my understanding goes, the main advantages of the mersenne twister are that it's fast and has a very long period.

I think the efficiency and period of any modern C implementation's version of rand() is fine for a strategy game.

If you can demonstrate that the mersenne twister actually provides better results, we might consider it. Otherwise I don't think it's worth putting any effort into.

I don't think an empirical demonstration that either Mersenne Twister or Mother of All is better is possible. (If nothing else, any given target C library may actually use one of these as its implementation.) If the change is to be done, it should be to shut up complaints about insufficiently random RNGs by actually being able to use argument from authority.

In any case, such a change doesn't belong in the current feature-freeze; it should have to wait for the Wesnoth 1.8.0 release.

An option with this change, is that it makes the design choice of whether the RNG state is part of the savegame possible. This doesn't affect multiplayer, but has a considerable effect on single-player (hotseat and campaign modes) by changing what kinds of savescumming are possible.

[Ken_Oh]

I think it would be pretty freaking simple to make a test of the current RNG system. I'm not even talking about using the rand operator either, but rather making units with 1000 strike berserk attacks at 1 damage a piece, each unit with different chance to hit values, on a unit with 1000 hitpoints, and then have WML keep track of the number of hits and misses in a row.

Is there anything else needed for this test? I'd be happy to throw something together tomorrow if it can put this dispute to rest, one way or another.