Strange behavior in Character Generation - Abilities in both BG:ee and BG2:ee

[InKal]

what the fuck are you talking about all of you? is there a doctor in the room???

 

Quote

I asked my friend to buy BG:EE, install it, install autoroller

[Bartimaeus]

10 hours ago, subtledoctor said:

Yeah it reminds me a bit of a Rubik's Cube. A kid I know has gotten into Rubik's Cube a bit, and apparently there are a couple algorithms that can reliably solve it...

At the beginner's level, it's more like...maybe ten different algorithms that you apply (usually multiple times) depending on the particular formations that you see within each stage of solving the cube. They're not terribly complex (I think the most complicated is only 8 steps long), but you do have to recognize when and where to use them and do it consistently.

Source: Me being capable of solving a Rubik's Cube at a beginner level (i.e. within 3-4 minutes) while not having had the skills, dedication, and/or patience to move on to the next level, . Relevancy to the rolling stuff? About none, but I figure this is at least slightly more interesting conversation than some of the stupidity I've seen around here lately.

Edited June 25, 2022 by Bartimaeus

[lalakobe]

18 hours ago, suy said:

But if you want to give it a shot (you seem quite motivated and that's cool!), get the debug symbols, then search for CScreenCreateChar::OnAbilityReRollButtonClick.

Thanks for the tip, here is what I found using Ghydra (although my knowledge of C++ is very low, last time I used it to make a program  was like 15 years ago, so my assumptions may be wrong, happy if someone corrects me)

Reroll button (OnAbilityReRollButtonClick) calls ResetAbilities function. ResetAbilities does some checks (for example for Halfling race) and calls rand() function to reroll exceptional STR

 

(rand() seems to be Microsoft rand implementation:

my_rand_gen->seed = (my_rand_gen->seed * 214013 + 2531011);

return (my_rand_gen->seed >> 16) & 0x7fff;)

 

After that, it calls ResetAbility function for each stat (until it returns 1) and checks if total sum is above 75. Then, UpdateAbilitiesPanel is called to redraw new numbers on screen.

 

ResetAbility also uses rand(), converts its output to 1-6 range, and repeats 2 more times, basically doing 3D6 roll. After that, it checks for racial and class restrictions, if that check fails, function returns 0, so it is fired again, until correct number is rolled. Inside ResetAbility there are however some strange varibles, I cant understand how it got its value.

[subtledoctor]

7 hours ago, Bartimaeus said:

Relevancy to the rolling stuff? About none

Why not? I figure the random number generation is basically a seed value plus the application of an algorithm. Obviously that’s a simplified description but the point is merely, it is not actually random and is likely to result in the repetition of certain particular outcomes. 

I only said it is analogous to what is happening here.

Edited June 25, 2022 by subtledoctor

[Bartimaeus]

28 minutes ago, subtledoctor said:

Why not? I figure the random number generation is basically a seed value plus the application of an algorithm. Obviously that’s a simplified description but the point is merely, it is not actually random and is likely to result in the repetition of certain particular outcomes. 

I only said it is analogous to what is happening here.

I really need to stop saying stuff like that when I haven't made it perfectly clear what it is I'm speaking about: sorry, I meant my more detailed explanation of the Rubik's Cube stuff was irrelevant to the discussion at hand, not what you said.

Edited June 25, 2022 by Bartimaeus

[subtledoctor]

Ah got it, no worries

[lalakobe]

Continuing my research 

Algorythm for exceptional STR is:

1. Check if race <> HALFLING (as halfling max STR is only 17)

2. Call rand() function, get number from 1 up to 32767, for example 20461

3. Get last two digits of this random number, 61 in this example

4. Add 1, result is 62. Thats it, exceptional STR is 62 in this roll

 

Another interesting thing, as an experiment, I changed racial condition from halfling to elf in executable (by changing byte from 05 to 02), launched autoroller, and 104 rolls became "unstuck":

[jmerry]

And the algorithm for generating the base ability numbers is really simple. Generate random numbers 18 times, mod by 6 for the d6 rolls, and line up the abilities as 3d6 x6, in order. Apply race/class modifiers and silently discard any rolls that don't meet the race/class minima.

There are about 10^14 results for 18 six-sided dice. About six thousand of them give you a total of 104 or more if the race has neutral modifiers (such as an elf). Less for net negative modifiers, like dwarves and halflings have. Just how many possible random seeds are there? If that's a 32-bit integer, we're looking at about 4*10^9 possibilities ... which leaves about a 1 in 4 chance that a 104+ roll exists at all.

If the random number generation is 64-bit, that's more than enough to cover every possible roll and ensure that all ability totals are possible.

Thinking about it more, I think that's exactly what you've found. You can expect there to be about one 103+ roll for non-halflings (before race/class modifiers) on a 32-bit system. And you found it. You can expect there to be about one 103+ roll for halflings (before race/class modifiers, which are net negative for them). And you've found that as well.

Over on the Beamdog forums, one of the regulars posted a shot of a perfect 108. Which I suspect means that at least some versions of the EE are using 64-bit random numbers under the hood.

Edited June 28, 2022 by jmerry

[lalakobe]

On 6/28/2022 at 5:54 AM, jmerry said:

Thinking about it more, I think that's exactly what you've found. You can expect there to be about one 103+ roll for non-halflings (before race/class modifiers) on a 32-bit system. And you found it. You can expect there to be about one 103+ roll for halflings (before race/class modifiers, which are net negative for them). And you've found that as well.

By using x64dbg debugger I looked at the whole "press reroll button" process. It saves roll result ("good" ones, fitting into race and class restrictions) into memory after each stat generation (first, STR, then DEX etc.), six times. This memory segment looks like this:

STR EXCEP_STR INT WIS DEX CON CHR

17 36 11 12 11 12 11 (for example)

I thought that maybe some function altered these number afterwards, so I set up breakpoint on write to these addresses, but no luck.

After that, I tried altering rolls in the memory in debugger on the fly (I thought maybe some kind of overflow happens, that silently discards high rolls). So, I changed each stat to 18 during generation, and program wrote these numbers into memory as intended without any errors, and I got 108 roll on screen in game. So, this process works fine.

Last thing that I can think of is some kind of overflow in rand() function, maybe tied with seed as you proposed.

By changing racial condition, as I described before, I disabled additional EXC_STR roll, that happens before stat rolls, for ELF, and 104 rolls became a)unstuck and b)much more frequent. I think Ihave to look at rand() implementation in EE more closely.

[Jarno Mikkola]

1 hour ago, lalakobe said:

By changing racial condition, as I described before, I disabled additional EXC_STR roll, that happens before stat rolls, for ELF, and 104 rolls became a)unstuck and b)much more frequent. I think Ihave to look at rand() implementation in EE more closely.

This doesn't only do that unfortunately, as the race has minimum stat line you can see in https://gibberlings3.github.io/iesdp/files/2da/2da_bgee/abracerq.htm

Like the name inclines, requirements which are for an elf, far higher than for a human. Requirements that if not met, "allow a reroll" until they are met.

And then there's the ab_class/kit_addons and the ab_race_additives ... all this make the human have smaller actual chance to give them the total amount of max stat.

Edited June 30, 2022 by Jarno Mikkola

[lalakobe]

14 minutes ago, Jarno Mikkola said:

This doesn't only do that unfortunately, as the race has minimum stat line you can see in https://gibberlings3.github.io/iesdp/files/2da/2da_bgee/abracerq.htm Which are for an elf, far higher than for a human.

And then there's the ab_class/kit_addons and the ab_race_additives ...

If 05 is changed to 02, race is not changed, it stays ELF, just this code (rolling for EXC_STR) is skipped:

 

[jmerry]

Not overflow. It's just that 32-bit pseudo-random numbers don't have enough variation to model this system completely, and will omit many rolls that would be possible with true randomness. If you know the initial value of the random seed and the auxiliary dice, you can determine all of the stats. And those 2^32 possibilities don't cover all of the 6^18 possible ways to roll the 18 needed dice.

Though ... looking at what you posted, I think I was a little off. There's probably significant class/race dependence, because of this:

On 6/25/2022 at 3:58 AM, lalakobe said:

After that, it checks for racial and class restrictions, if that check fails, function returns 0, so it is fired again, until correct number is rolled.

Rerolling stats individually if they don't match race/class minima changes the flow, and makes things different between classes. Now every initial seed will lead to a roll that meets the race/class minima, though it still might be discarded for not reaching the 75 total. Which makes the high rolls more common, particularly for classes with high minima. At one extreme, there are only about 10^11 rolls that meet the elf ranger minima, which is only 24 times the number of 32-bit integers. The maximum roll for that race/class combo (with 32-bit math) is probably a 106 or a 107.

Then there's another way seeds can double up. If you roll a number that's too low for the first stat (strength), you move on to the next seed and roll strength again ... which is equivalent to just starting with that next seed. So, when there's a strength minimum, that effectively reduces the number of possible seeds.

Oh, and your "unstuck" list for when you didn't roll exceptional strength? I see six different 104 rolls there. Maybe there's one or two more, but I'll guess it's just those six. Just a matter of luck on the near-Poisson distribution for how many such rolls there are. Assuming 32-bit math and modeling the RNG with a a random hash, here's the expected number of different 104+ rolls for some elf classes, to two significant digits:

Fighter: 0.51

Thief: 0.58

Fighter/Mage/Thief: 0.66

Ranger: 78

Dragon Disciple: 17

Enchanter: 10

Diviner: 12

Shadowdancer: 6.7

Hmm. If we're looking at an expected value of 78, a result of 1 is not plausible. There's something more going on that I haven't caught yet. We would expect the maximum roll for an elf ranger to be 106 or 107.

[polytope]

Although the pseudo random algorithm isn't entirely accurate representation of 18d6 I don't think this is much of a bug that needs solving.

As jmerry said, fewer than 1 in every billion 18d6 rolls are >/= 104. A billion seconds is... 31 years, 36 weeks, 6 days, and nearly 9 hours. Oops, my math is bad, I forgot leap years, so it would vary.

It takes a least one second for a human (not a computer) to glance at the summed rolls and tell if those are good or should be re-rolled, realistically, several seconds for most people.

This bug would never be discovered or cared about in the absence of an autoroller program, and I don't see the point of an autoroller, like, you could use the ctrl+8 cheat and save electricity.

This is the highest roll I believe I've ever gotten naturally with a human (base class is thief so only minimum is dex at 9):

Edited July 12, 2022 by polytope
Polytope's wonky math

[lalakobe]

I patched executable once again to use inside rand() function RDRAND CPU instruction (https://en.wikipedia.org/wiki/RDRAND). This instruction is available up from Ivy Bridge Intel architecture (my cpu is old, but luckily has support).

The only drawback is that RDRAND is 2x-3x slower (at least on my CPU) that classic C++ rand() implementation, thus autorolling takes more time.

And here is the result:

 

 

Edited July 12, 2022 by lalakobe

[lalakobe]

4 hours ago, polytope said:

This bug would never be discovered or cared about in the absence of an autoroller program

Well, it's still a bug, that prevented player from getting some of the roll results.