Solutions to hitting

[Circon]

Multiply by people who play Wesnoth, and you might get 6 million. This is like over at the Civ forums, where people complain

"My tank lost to a spearman! <newbie crap censored> therefore this game sucks!"

(Tanks have ATK 16, spearmen DEF 2)

It is now so much of an inside joke that the veterans are complaining "My spearman lost to a tank!" and we have a tank-lost-to-spearman smilie.

[mikekchar]

So, either you're really unlucky, or YOU have a problem. I have never had anything like this happen to me, so it's probably not a bug in Wesnoth.

Are you implying I have a problem with reality

I'm not saying that it's impossible, merely improbable. Clearly some people don't notice a problem. Just as clearly, some people suspect a problem. If I could pin it down to a bug, I'd simply submit a bug report. As it is, I'm communicating my experiences in case someone sees something and thinks, "Aha! Yes, I noticed that too".

I'll do my best to take a look at the code today. Not having looked at it before, I'm not sure what to look for, but I'll start with the obvious (like someone resetting the seed by accident, etc).

It's interesting to me, though, that I always do more damage than the expected value. I also take less damage than the expected value. And at the extreme ends of the probabilities (with magic for instance), I encounter improbable runs. This indicates a possible problem with the distribution of the RNG. If that were the case, it wouldn't surprise me if others find no problem at all. Especially if different RNGs were used on different platforms.

[mikekchar]

Well... that didn't take long...

All of the calls to rand() are of the form:

my Result = rand()%100;

This is *not* portable across platforms and will not work properly on most systems. rand() uses an algorithm that is known to create poor distributions in the lower oder bits. As per the man page (quoting Numerical Recipes):

"If you want to generate a random integer between 1 and 10, you should always do it by using high-order bits, as in

j=1+(int) (10.0*rand()/(RAND_MAX+1.0));

and never by anything resembling

j=1+(rand() % 10);

(which uses lower-order bits)."

Now, having said that, the Linux implementation of rand() is *supposed* to use the random() implementation which has less problems on low order bits. However, I'm willing to bet that my problems will go away if this is fixed.

In fact, I'd be even happier if it were to use /dev/random which uses "entropy" based on system events to generate the seed. Currently Wesnoth is using the time as the seed. I'm not familiar enough with the RNG in rand() to know if this is a problem (some RNGs produce poor distributions with some seeds).

Random number generation is *tough* stuff.

Anyway, I should send in a bug report... I will do so once I get time. If a developer sees this, please feel free to pre-empt me...

[quartex]

Search the forums, we've had lots of arguments before about the randomness of the game, and if itleans one way or another. Dave has defended his random number generator before. Maybe there is a problem with the random function he's using, but many other people have asked the same question, so I'm doubtful. Ask him about it and I'm sure he'll address your concerns.

[silene]

No, mikekchar's point is relevant, and Wesnoth would benefit from such code changes (I'm not speaking about /dev/random here). It would be even more relevant if Wesnoth was using Java (well-known for the really short lower-bits cycles of its random generator, unfortunately). But I'm not sure it's responsible for the bad luck people see (funny how nobody ever complained about good luck). People will continue mistaking "not probable" with "not possible".

[Elvish_Pillager]

(funny how nobody ever complained about good luck).

I have, but it as about a multiplayer game, and since the majority of the luck was during my opponent's turns, it was actually bad luck (the calculations were preformed by the loser).

A contributor to the lack of good luck complaints is that most of the time, units are more likely to hit than to miss, so a long string of hits is easier to slip beneath your notice. (that wasn't too unlikely to happen... no point remembering it)

[Dobob]

It would be even more relevant if Wesnoth was using Java (well-known for the really short lower-bits cycles of its random generator, unfortunately).

Hum, last time I checked, Java was using the exact same generator as rand48.

Also, bad random lower-bits aren't that bad in Wesnoth, since the modulus used is 100, which is not a power of two (100 = 2*2*5*5). So the most signifiant bits are used in the calculation too. You should try the following : compute the odds of some attack to succed if the last 2 bits are always 00 (or any value). Since hit ratio are multiples of 10%, you won't see many differences.

Anyways, that point and the fact that Wesnoth is quite chaotic in it's use of random numbers and that it doesn't use a lot of them (I don't think it can use 2^16 ~ 64000 random numbers in a game) make it that BfW doesn't need a better RNG than it has now. Sure the present one is a bad generator, but getting a better one is not worth the effort, as small as it may be.

[Dave]

All of the calls to rand() are of the form:

my Result = rand()%100;

This is *not* portable across platforms and will not work properly on most systems. rand() uses an algorithm that is known to create poor distributions in the lower oder bits.

We have had this discussion before: the result was that I said that I thought that this 'problem' is relevant if you were programming, for instance, a cryptographic application, but for a game it doesn't make an observable difference.

I further offered to change the algorithm if someone can produce a test case that shows that rand()%100 doesn't produce good results on any of our major target platforms. No-one has made such a demonstration.

Also one of our developers who is a statistician ran a test on the GNU standard library implementation of rand() and found that it produces very good results for what we want.

The offer is still open though: show us big problems on any major platform using a verifiable test program (as opposed to anecdotes from gameplay) and we'll look into it.

Changing the way it works isn't trivial, btw, since the random numbers are shunted across the network, and taking the top order bits would be difficult since different systems have different int sizes.

In fact, I'd be even happier if it were to use /dev/random which uses "entropy" based on system events to generate the seed.

That's not a portable solution, since some of our supported platforms don't have /dev/random.

David

[ott]

Dave is right, rand() complaints are an unproductive flamewar sewer and should really be substantiated with facts.

However, I do believe the distribution of attack outcomes on my platform is problematic. I am also seeing unexpectedly long runs of hits and misses, and I am complaining just as much about excessive good luck as excessive bad luck -- please note my comments about damage dealt being 35% over EV over hundreds of hits. It's no fun playing a game where regularly a 40% chance to hit results in 9 consecutive hits, any more than when 13 consecutive 70% attacks result in no hits.

Wesnoth is supposed to be fun, and about strategy. If the game outcome is too dependent on quirks in the random number generation scheme (either because of platform bugs or code that does not work well across platforms), then it stops being fun, and becomes simply a "replay the scenario until the random numbers come out right" game.

I'll continue investigating.

[mikekchar]

I apologize if I'm bringing up an old topic. I think I may have been a little put off by the suggestion that I'm imagining the problem. Now, I'm the first to admit that these streaks may just be the luck of the draw. However, I think they warrant some investigation, if only by me.

The problem is that it is pretty hard to come up with an objective test for this. Testing that the output of a RNG is uniformly distributed is not a trivial task and is beyond my extremely rusty math skills. However, I will do my best to do so.

One thing to keep in mind is that the GNU rand() funtion is actually implemented with random(). Is Wesnoth using GNU libc on all platforms? If not, then there is already a potential that different platforms are generating different results.

BTW, just in case you are worried that I'm just complaining around here, having perused the code I'm quite impressed. This is definitely one of the better written large projects I've come across. The developers should definitely pat themselves on the back.

[Dave]

I apologize if I'm bringing up an old topic. I think I may have been a little put off by the suggestion that I'm imagining the problem. Now, I'm the first to admit that these streaks may just be the luck of the draw. However, I think they warrant some investigation, if only by me.

Don't get me wrong: I welcome investigation into this. However, I'm sure you can appreciate that when I've been told (and have seen developers of other games told) that the RNG seems to produce extraordinary/bad/unfair (as in yes, some players think the RNG is on the side of the AI, and favors it) results, then it's difficult for the developers to approach the issue.

In fact, it really puts our back against the wall. I mean, we don't want to call our users liars, or anything nasty like that, however at the same time it's just really difficult to do much about the problem when it is never substantiated with something that looks objective.

I did actually start an effort to obtain some kind of objective evidence on this: if you look in a save file, and go down to the [statistics] area, you will see tags called [attacks] and [defends]. An [attacks] tag contains tags that look like this:

Code: Select all

[sequence]
  00="1"
  01="2"
  10="1"
  11="3"
  111="1"
  101="2"
  _num="70"
[/sequence]

What this means is that for attacks that have a 70% chance to hit, once you have gotten two misses and no hits, twice you've gotten a miss followed by a hit, once you've got a hit followed by a miss, and so forth.

These statistics can be accumulated over, say, a campaign, so you can see exactly how many times you got the dreaded "four attacks with 70% each, and missed them all."

The problem is that it is pretty hard to come up with an objective test for this. Testing that the output of a RNG is uniformly distributed is not a trivial task and is beyond my extremely rusty math skills. However, I will do my best to do so.

Nothing so statistically rigorous is required: remember, you are trying to prove the algorithm used is bad, not good. Proving it is good needs something statistically rigorous. Proving it is bad only needs one example that shows the algorithm behaves poorly and you're done.

For instance, you could set out to prove that "using rand()%100 will produce an in-ordinate number of results where a mage with four attacks will miss all four attacks" (something that should normally happen only 0.8% of the time):

Code: Select all

int count = 0;
for(int i = 0; i != 1000000; ++i) {
  int hits = 0;
  for(int j = 0; j != 4; ++j) {
    if((rand()%100) > 70) {
      ++hits;
    }
  }

  if(hits == 4) {
    ++count;
  }
}

std::cout << count << "\n";

Of course, you probably don't want to try this actual test, since I've already tried it But if you can think up any test that is likely to happen in-game and the results differ substantially from expected results then you'll have made a good case for us investigating the random number generation.

Btw on my GNU stdlib, the above test results in four misses about 0.7% of the time -- so differing very slightly from the expected results, but I think close enough for it to not be a problem. (And in the opposite direction to what players who complain about this kind of thing seem to complain about!)

One thing to keep in mind is that the GNU rand() funtion is actually implemented with random(). Is Wesnoth using GNU libc on all platforms? If not, then there is already a potential that different platforms are generating different results.

There are different results on different platforms, since Wesnoth uses the local rand() function on each platform. However as long as rand() is implemented reasonably on all platforms, there's no real problem. I have considered importing our own random number algorithm to make results consistent, but I'm really not sure it's necessary.

BTW, just in case you are worried that I'm just complaining around here, having perused the code I'm quite impressed. This is definitely one of the better written large projects I've come across. The developers should definitely pat themselves on the back.

Thanks!

David

[mikekchar]

Don't get me wrong: I welcome investigation into this. However, I'm sure you can appreciate that when I've been told (and have seen developers of other games told) that the RNG seems to produce extraordinary/bad/unfair (as in yes, some players think the RNG is on the side of the AI, and favors it) results, then it's difficult for the developers to approach the issue.

I sure can! Clearly it would be difficult for the RNG to favour the AI (i.e., it would take *effort* to have such a bug ). I wasn't expecting this to be such a hot topic (serves me right for not reading the archives).

it's just really difficult to do much about the problem when it is never substantiated with something that looks objective.

I totally understand. Which is why I'd like to get something objective. For my part, I was noticing some strange results and decided to check the forum to see if anyone else had seen the same thing. When I discovered that others *had* indeed noticed something odd, I decided to look further. Clearly 13 or so misses in a row is compelling evidence that *something* strange is going on (if only seriously bad luck)

I did actually start an effort to obtain some kind of objective evidence on this: if you look in a save file, and go down to the [statistics] area, you will see tags called [attacks] and [defends]. An [attacks] tag contains tags that look like this:

<snipped for space>

That's awesome!!! That way I can play Wesnoth while I'm testing! Just need to extract the data. Much better to use the actual code than my interpretation of what's happening. For all I know there might be a problem somewhere else that makes it *look* like the distribution is off. Or, it might show that the data is perfectly distributed.

Nothing so statistically rigorous is required: remember, you are trying to prove the algorithm used is bad, not good. Proving it is good needs something statistically rigorous. Proving it is bad only needs one example that shows the algorithm behaves poorly and you're done.

Unfortunately it's more complicated than that. True, if I can show a particular defect in the distribution, it shows the distribution is off. However, there are an infinite number of ways the distribution can be off. For instance, perhaps every second generation is low. Depending on the code path, any number of observed effects could happen.

Remember that several of us are reporting consitently *high* damage values over the expected value. I'm not looking for a specific defect. It's just that *something* seems screwy and I can't quite figure out what it is.

There are different results on different platforms, since Wesnoth uses the local rand() function on each platform. However as long as rand() is implemented reasonably on all platforms, there's no real problem. I have considered importing our own random number algorithm to make results consistent, but I'm really not sure it's necessary.

I agree with you here. However, if there are differences, it might explain why some people experience one thing and others experience something else. My only point was that the behaviour of the RNG in Wesnoth is already unportable, although the code itself will compile on multiple platforms. If there turns out to be a problem on a specific platform, there's no real reason it couldn't be changed for that particular platform (although having read a bit more about /dev/random on Linux, I now agree this is probably not the best solution).

Anyway, thanks for putting up so graciously with the return of this dreaded issue. I shall do my best to gather some *real* data and give you the ammunition you need one way or the other.

[mikekchar]

OK. Now I'm confused!!!!

I took a look at my save file from the aformentioned 13 miss game. The data does not corroborate my observation. So either I missed some hits or some things aren't being saved. My guess is the former...

Damn! Perhaps a tempest in a teapot. I swear I must be losing it... But just to be sure, I'll keep looking...

[Darth Fool]

OK. Now I'm confused!!!!

I took a look at my save file from the aformentioned 13 miss game. The data does not corroborate my observation. So either I missed some hits or some things aren't being saved. My guess is the former...

Damn! Perhaps a tempest in a teapot. I swear I must be losing it... But just to be sure, I'll keep looking...

perhaps you can upload the save file. Doing this is one of the best ways to get other people to hunt down and squash bugs since they can see exactly what is happening. Remember, if a picture is worth a thousand words, how much is a save file worth?

[mikekchar]

I could definitely do that. But I'm not sure it would help matters. I don't have a replay file (curse my stupidity). What I've decided to do is to work on a set of tools for validating the RNG from the data in the save files. Then I can just play a lot and look for problems.

One question... I'm looking in the replay file and I notice that the [random] tags are nested. Is there some documentation that explains what this means?

BTW, I wish I had looked into the save files before I started complaining. Man, whoever decided what to write out here (Dave?) was brilliant! I can get everything I need out of this!

Probably this thread is in the wrong place