Final Fantasy VIII

2011-05-03 10:56:27 pm

Moo! Flap! Hug!

Quote from Rakuen:

Posit the game starts with some default value in a variable X. X is combined with the frame where you press Play and the result is stored back in X.

Yeah, I like that theory a lot. But determining how X is initialized, and if anything other than pressing "Play" affects X (e.g., something completely unrelated to TT), could be quite an undertaking. And I think that's more in the realm of the TASers at this point Wink

DarkKobold

2011-05-04 12:33:52 am

RPG TASer

[quote="Poxnor"]
Good thinking. Here's some post-processing results on the Trepie #1 dump:

Code:

Total hands processed: 131072
Unique ordered hands processed: 124853
Unique unordered hands processed: 26100
Hands with level ten card: 39339 (30.01%)
Average card strength: 4.48
Average card strength when level ten played: 4.81
Average card strength when level ten not played: 4.33

All this aside, I think you have your (first) answer. Even if the RNG goes out to 32 bit, it is unlikely that the statistics will vary that much - and, given that it is already tested out to 17 bits, I doubt we are going to find a good way to predict it in a SS run. I'd be interested to see now, what you figure out for zell's mom, the other trepies, possibly Dr. Odine.

Poxnor

Edit history:

Poxnor: 2011-05-04 01:12:47 am

2011-05-04 01:06:26 am

Moo! Flap! Hug!

Quote from DarkKobold:

All this aside, I think you have your (first) answer. Even if the RNG goes out to 32 bit, it is unlikely that the statistics will vary that much

Indeed. The 99% CI on the sample mean I posted is +/- 0.33% (i.e., 29.68% to 30.34%). In other words, the odds of Trepie #1 playing the card are 30%.

Quote from "DarkKobold:

given that it is already tested out to 17 bits, I doubt we are going to find a good way to predict it in a SS run.

I was hopeful, with the large groupings of 103s in the output, that if we could predict the initial state of the PRNG ("X" in Rakuen's words), then we could time the pressing of the "Play" menu option to the music to manipulate Trepie #1 to always play Quistis in the first card match...

Quote from DarkKobold:

I'd be interested to see now, what you figure out for zell's mom, the other trepies, possibly Dr. Odine.

I have no save states anywhere near Odine, but I'll post all three Trepies and Zell's mom Wednesday evening Smiley

(Edit: If you have any save states near Odine, feel free to run the script I posted with the number of extractions set to 131072, and email me the output file. I'll run it through my post-processing script and upload the results Smiley

)

[quote="DarkKobold"]All this aside, I think you have your (first) answer. Even if the RNG goes out to 32 bit, it is unlikely that the statistics will vary that much[/quote]
Indeed.  The 99% CI on the sample mean I posted is +/- 0.33% (i.e., 29.68% to 30.34%).  In other words, the odds of Trepie #1 playing the card [b][i]are[/i][/b] 30%.

[quote="DarkKobold]given that it is already tested out to 17 bits, I doubt we are going to find a good way to predict it in a SS run.[/quote]
I was hopeful, with the large groupings of 103s in the output, that if we could predict the initial state of the PRNG ("X" in Rakuen's words), then we could time the pressing of the "Play" menu option to the music to manipulate Trepie #1 to always play Quistis in the first card match...

[quote="DarkKobold"]I'd be interested to see now, what you figure out for zell's mom, the other trepies, possibly Dr. Odine.[/quote]
I have no save states anywhere near Odine, but I'll post all three Trepies and Zell's mom Wednesday evening :)
(Edit: If you have any save states near Odine, feel free to run the script I posted with the number of extractions set to 131072, and email me the output file.  I'll run it through my post-processing script and upload the results :) )

gyth

2011-05-04 01:24:03 am

There are some patterns in the data, but it seems like its trying to count without repeating numbers.
Like each column has its own pattern, but if the card that should be in the third column was already used it does something else to pick the card; maybe next available.

Do you see these type patterns in your data?

53 16 15 49 12
46 44 49 18 48
50 16 17 20 46
53 44 50 12 13

12 17 51 14 18
16 45 19 17 14
19 17 53 15 49
12 45 20 21 15

I'm finding quite a few groups of four where:
1st column
-1st=4th
-3rd=2nd+3/4
2nd column
-numbers oscillate
3rd column
-3rd=1st+2
-4th=2nd+1

Poxnor

2011-05-04 01:29:15 am

Moo! Flap! Hug!

Quote from gyth:

Do you see these type patterns in your data?

Not really Smiley

But have a blast Wink

(131072 hands attached)

Attachment:

Trepie1.zip

gyth

2011-05-04 08:21:19 am

Your points at 30 follow the pattern
14 50 13 45 16
18 12 46 48 11
21 50 14 17 18
14 12 48 53 13

They occur too often to be "random"

Poxnor

2011-05-04 11:36:10 am

Moo! Flap! Hug!

Quote from gyth:

They occur too often to be "random"

That suggests that the card-selection algorithm is backed either by a table lookup or by a low-entropy shuffling algorithm. Cool Smiley

Poxnor

2011-05-04 11:38:26 am

Moo! Flap! Hug!

Card statistics Smiley

Trepie #1 (Cafeteria):

Code:

Total hands processed: 131072
Unique ordered hands played: 124853
Unique unordered hands played: 26100
Unique cards played: 22
Hands with level ten card: 39339 (30.01%)
Average card strength: 4.48
Average card strength when level ten played: 4.81
Average card strength when level ten not played: 4.33

Trepie #2 (Classroom):

Code:

Total hands processed: 131072
Unique ordered hands played: 130558
Unique unordered hands played: 100528
Unique cards played: 33
Hands with level ten card: 26227 (20.01%)
Average card strength: 4.16
Average card strength when level ten played: 4.59
Average card strength when level ten not played: 4.05

Trepie #3 (Classroom):

Code:

Total hands processed: 131072
Unique ordered hands played: 131020
Unique unordered hands played: 123543
Unique cards played: 44
Hands with level ten card: 13111 (10.00%)
Average card strength: 4.09
Average card strength when level ten played: 4.58
Average card strength when level ten not played: 4.03

Zell's Mom:

Code:

Total hands processed: 131072
Unique ordered hands played: 131039
Unique unordered hands played: 123393
Unique cards played: 44
Hands with level ten card: 13116 (10.01%)
Average card strength: 4.10
Average card strength when level ten played: 4.68
Average card strength when level ten not played: 4.04

Card statistics :)

Trepie #1 (Cafeteria):
[code]
Total hands processed: 131072
Unique ordered hands played: 124853
Unique unordered hands played: 26100
Unique cards played: 22
Hands with level ten card: 39339 (30.01%)
Average card strength: 4.48
Average card strength when level ten played: 4.81
Average card strength when level ten not played: 4.33
[/code]

Trepie #2 (Classroom):
[code]
Total hands processed: 131072
Unique ordered hands played: 130558
Unique unordered hands played: 100528
Unique cards played: 33
Hands with level ten card: 26227 (20.01%)
Average card strength: 4.16
Average card strength when level ten played: 4.59
Average card strength when level ten not played: 4.05
[/code]

Trepie #3 (Classroom):
[code]
Total hands processed: 131072
Unique ordered hands played: 131020
Unique unordered hands played: 123543
Unique cards played: 44
Hands with level ten card: 13111 (10.00%)
Average card strength: 4.09
Average card strength when level ten played: 4.58
Average card strength when level ten not played: 4.03
[/code]

Zell's Mom:
[code]
Total hands processed: 131072
Unique ordered hands played: 131039
Unique unordered hands played: 123393
Unique cards played: 44
Hands with level ten card: 13116 (10.01%)
Average card strength: 4.10
Average card strength when level ten played: 4.68
Average card strength when level ten not played: 4.04
[/code]

Rakuen

Edit history:

Rakuen: 2011-05-04 12:21:04 pm

2011-05-04 12:20:42 pm

Weegee Time

Quote from Trepie1:

Unique unordered hands played: 26100
Unique cards played: 22

I think this is the one to focus on if you want even more understanding as to how the game works. If the fan has 22 cards available, that means there's 3160080 ways the cards could be dealt. But when we're not interested in card order, you can divide by 120, because there's that many ways 5 cards could be ordered. That gives us 26334 unique hands. I think you could get every possible hand dealt out, and that might be enough to get whatever data was needed.

ButtersBB

2011-05-05 08:12:45 am

Very nicely done with the statistics Poxnor!

The stat that really illustrates to me how difficult it is to get the Zell card in comparison to the Quistis card is the "Unique cards played" stat. 22 vs. 44? Sheesh, no wonder Zell's Mom is so random.

The "unique cards played" stat does make me curious as to what that stat is for the other unique cards. Might make a card that originally would be seen as "not worthwhile enough" much more worthwhile in an SS if the odds of getting it are at least similar to the odds of getting the Quistis card from Trepie 1.

gyth

2011-05-05 02:05:20 pm

What is interesting to me is that with 22 cards the odds are 30% instead of 1/22 ~4.5%.
And that 44 cards lowers it to 10%, not 15%.

The 30, 20, 10%s look hard coded and on a separate entropy source than the rest of the card randomness.
For trepie1 the level 10 islands seem to be 57 every 189 or 190.

Rakuen

2011-05-05 04:33:13 pm

Weegee Time

Well, actually probability doesn't work that way gyth. There are five cards drawn in a hand, and each card has a chance of being the rare card. It appears to me that cards are never duplicated, so there are only 22 cards in the hand. To figure out the probability that the Quistis card should be drawn, we figure out the probability of NOT drawing it, which is as follows:

(21/22) * (20/21) * (19/20) * (18/19) * (17/18) = 77.3% to not draw.
Which means there should be a 22.7% chance it appears. Of course, that doesn't really help, considering the game seems to give it a 30% chance of appearing.

More pertinently, it wouldn't have to be a separate entropy source. You could force card injection by checking the random number that's generated. Say the number generator creates numbers from 0 to 255 inclusive. 30% of 256 is ~77. So you could say if the number generated is less than 77, execute an algorithm that makes the first card drawn Quistis, then draw the remaining 4 cards according to the regular algorithm.

Well, actually probability doesn't work that way gyth.  There are five cards drawn in a hand, and each card has a chance of being the rare card.  It appears to me that cards are never duplicated, so there are only 22 cards in the hand.  To figure out the probability that the Quistis card should be drawn, we figure out the probability of NOT drawing it, which is as follows:

(21/22) * (20/21) * (19/20) * (18/19) * (17/18) = 77.3% to not draw.
Which means there should be a 22.7% chance it appears.  Of course, that doesn't really help, considering the game seems to give it a 30% chance of appearing.

More pertinently, it wouldn't have to be a separate entropy source.  You could force card injection by checking the random number that's generated.  Say the number generator creates numbers from 0 to 255 inclusive.  30% of 256 is ~77.  So you could say if the number generated is less than 77, execute an algorithm that makes the first card drawn Quistis, then draw the remaining 4 cards according to the regular algorithm.

ButtersBB

Edit history:

ButtersBB: 2011-05-05 07:54:25 pm

2011-05-05 07:51:59 pm

That's kind of a round-about way to calculate the probability, though still correct.

Personally, I thought of it in the opposite way. I calculated the probability that one of the 5 cards drawn is the Quistis card.

So 1/22 (the probability of a Quistis card being drawn from the deck) * 5 (the amount of cards getting drawn). The answer is ultimately the same, 22.7% chance that the Quistis card is drawn.

Personally, I'd like to know what the number of unique cards is for Dr. Odine, as well as the guy that carries the Pandemona card. If they are low, then one might be useful for an SS run.

Poxnor

2011-05-05 09:05:00 pm

Moo! Flap! Hug!

The number of unique cards itself isn't important; I just added that in for interest's sake. What's important is the odds of him playing the card.

Rakuen

2011-05-05 10:14:25 pm

Weegee Time

Quote from ButtersBB:

So 1/22 (the probability of a Quistis card being drawn from the deck) * 5 (the amount of cards getting drawn). The answer is ultimately the same, 22.7% chance that the Quistis card is drawn.

Oh ffs... Didn't realize it would work out like that. *headdesk*

DarkKobold

2011-05-06 12:59:46 pm

RPG TASer

Quote from gyth:

What is interesting to me is that with 22 cards the odds are 30% instead of 1/22 ~4.5%.
And that 44 cards lowers it to 10%, not 15%.

The 30, 20, 10%s look hard coded and on a separate entropy source than the rest of the card randomness.
For trepie1 the level 10 islands seem to be 57 every 189 or 190.

My money is on this. Remember, once you have the player's rare card, they can't play this card again. Additionally, note that it is ALWAYS the first card. My guess is that the code looks pretty similar to this:

Randomize Hand
Check if Player can have tier 9/10 card (Thinking of Watts and Angelo, too).
Check if Player still has tier 9/10 card
Check if RNG value matches probability of tier 9/10 card
if so, replace card 1 with Rare.

Also, I checked, even with removing all hands that could have a rare card - Zell's mom still has over 256 possible hands (482), so the RNG is most likely > 8 bit. It MAY be only 16 bit, with a different RNG covering the rare card algorithm.

It would be interesting to see if it were 16 bit, by ignoring the first card, and seeing if the last 4 cards loop.

[quote="gyth"]What is interesting to me is that with 22 cards the odds are 30% instead of 1/22 ~4.5%.
And that 44 cards lowers it to 10%, not 15%.

The 30, 20, 10%s look hard coded and on a separate entropy source than the rest of the card randomness.
For trepie1 the level 10 islands seem to be 57 every 189 or 190.[/quote]

My money is on this. Remember, once you have the player's rare card, they can't play this card again. Additionally, note that it is ALWAYS the first card. My guess is that the code looks pretty similar to this:

Randomize Hand
Check if Player can have tier 9/10 card (Thinking of Watts and Angelo, too). 
Check if Player still has tier 9/10 card
Check if RNG value matches probability of tier 9/10 card 
if so, replace card 1 with Rare.

Also, I checked, even with removing all hands that could have a rare card - Zell's mom still has over 256 possible hands (482), so the RNG is most likely > 8 bit. It MAY be only 16 bit, with a different RNG covering the rare card algorithm.

It would be interesting to see if it were 16 bit, by ignoring the first card, and seeing if the last 4 cards loop.

Poxnor

2011-05-06 01:34:11 pm

Moo! Flap! Hug!

Quote from DarkKobold:

It would be interesting to see if it were 16 bit, by ignoring the first card, and seeing if the last 4 cards loop.

Code:

% head -5 Trepie1.txt 
44 17 11 20 18
48 45 46 11 13
51 17 46 13 19
11 45 14 16 21
15 18 20 53 45
% head -65541 Trepie1.txt | tail -5
103 52 51 16 54
103 11 13 49 45
103 15 51 17 20
103 18 13 51 50
103 21 52 11 14

Nope

Racht

2011-05-06 09:16:48 pm

(First post from a math/programming lurker)

The algorithm doesn't look like it runs a RNG for the special card every time. That would be a random distribution instead of the clumps we have. All that's relevant are the circumstances that produce the rare card, and Gyth hit upon the right idea: the hands are on a cycle of exactly 190, 133 consecutive without the card followed by 57 with the card, which is exactly 30%. For the other two cycles listed it looks like it's 152/38 and 171/19 - exactly 20% and 10%. I don't know the game's internal details but I suspect that means rare cards in general have their odds of appearing as a multiple of 10% (since 19 is prime) and that they use the same 190 cycle for all of them, though I have no idea why they would specifically choose 190. It looks like they did though. I don't know a whole lot about TASing but what that suggests to me is that the single frame advance in your code increments some master counter (number of frames in the game so far? A standard int field would easily hold that) that's calculated mod 190 for the number that determines if the hand contains the rare card or not, and then perhaps mod something else for the seed that determines the rest of the hand. If that's actually how it works, it seems like the best you could do outside of a TAS is to stagger starts of the card game to hit a different part of the 190-frame cycle every time, such that you're guaranteed to hit the 30% chance within 4 games, with a 60% chance to hit it within 2 games - only a bit better than just random luck. No idea if I'm on the right track, those were just my observations from looking at Poxnor's data dump.

(First post from a math/programming lurker)

The algorithm doesn't look like it runs a RNG for the special card every time.  That would be a random distribution instead of the clumps we have.  All that's relevant are the circumstances that produce the rare card, and Gyth hit upon the right idea: the hands are on a cycle of exactly 190, 133 consecutive without the card followed by 57 with the card, which is exactly 30%.  For the other two cycles listed it looks like it's 152/38 and 171/19 - exactly 20% and 10%.  I don't know the game's internal details but I suspect that means rare cards in general have their odds of appearing as a multiple of 10% (since 19 is prime) and that they use the same 190 cycle for all of them, though I have no idea why they would specifically choose 190.  It looks like they did though.  I don't know a whole lot about TASing but what that suggests to me is that the single frame advance in your code increments some master counter (number of frames in the game so far?  A standard int field would easily hold that) that's calculated mod 190 for the number that determines if the hand contains the rare card or not, and then perhaps mod something else for the seed that determines the rest of the hand.  If that's actually how it works, it seems like the best you could do outside of a TAS is to stagger starts of the card game to hit a different part of the 190-frame cycle every time, such that you're guaranteed to hit the 30% chance within 4 games, with a 60% chance to hit it within 2 games - only a bit better than just random luck.  No idea if I'm on the right track, those were just my observations from looking at Poxnor's data dump.

Poxnor

2011-05-06 11:30:00 pm

Moo! Flap! Hug!

Quote from Racht:

(number of frames in the game so far? A standard int field would easily hold that)

Good thinking. Unfortunately, it's neither the number of frames in the game so far (I tested that a bit earlier in the thread), nor is it only the number of frames from the start of the Triple Triad music (I have two save states at different points in the game; playing against Trepie 1 from those two save states yields different hands after x frames of TT music, for some fixed value x, e.g., x=50).

DarkKobold

Edit history:

DarkKobold: 2011-05-07 10:48:12 am

2011-05-07 10:17:41 am

RPG TASer

Code:

Z= 0x000786D4;
while true do
	memory.writeword(Z,100);
	emu.frameadvance();
end;

So, this code fixes the hand to one set. As far as I can tell, it is sufficient to manipulate what hand you will get. However, this is only a word, and not an int32, as far as I can tell.
Anyway, I'm pretty sure this isn't the end of the mystery... but it may help.

EDIT:
I also found these 4-byte addresses, which appear to be the clock (increments once per frame, even during lag). However, if you poke the high bits, PSXjin crashes, so I haven't been able to adjust the time clock yet.

d = 0x0005C460;
a = 0x00072F60;
b = 0x0005D58C;
c = 0x00072F64;

Sush

2011-05-12 11:46:53 am

Finally FINALLY fixed my graphics card problems! Started the final segment testing today and will hopefully be done in a few days, it will be under 8 hours for sure. Happy days

Essentia

2011-05-12 05:51:23 pm

Everything's better with Magitek

Awesome! I'm looking forward to it!

Poxnor

2011-05-12 08:26:50 pm

Moo! Flap! Hug!

Quote from DarkKobold:

0x000786D4

Awesome job DarkKobold -- this is it. However, it's a dword (32-bit), rather than a word (16-bit).

It increments by 1 every frame in TT (if you locked the low byte, DarkKobold, then value of the whole dword never changes). It also does crazy, crazy things during battle.

So, in other words, it would be trivial to manipulate a Trepie to play the Quistis card on a console before you get into any battles, and impossible after battle. Minor problem: good luck winning the Quistis card with the starting seven cards.

PS: Congratulations, Sush! Looking forward to it Smiley

ButtersBB

2011-05-13 06:18:21 am

Cool, can't wait to see the finished project Sush!

FF8Junkie

2011-05-20 02:22:12 am

.. finally found this thread in the huge internet ^^ when the run's gonna be finished?