Probability Problem: Brown Caskets

[Byrthnoth]

I'm making this here instead of the Mathy subforum because I don't think most people have figured out that it was unlocked. Also, this is a pretty interesting problem that a wider audience may enjoy. If it's deemed appropriate, feel free to move it to the lands of math!

The basic question I'm asking is, "At which point should we choose to examine the chest for a random hint, and at which point should begin to just guess numbers?"

Spoiler: show

Sub-request. Because the answer to this question doubtlessly depends on the hints you've already been given, can someone make a program or algorithm that will do the thinking for me? Thanks!

For those who don't know, the casket system works like this:

• A brown casket drops, you examine it and it tells you how many attempts you have to figure out its key value between 10 and 99. (3~6, typically 5 or 6 for high level brown caskets from Grounds of Valor)
• You can either guess a number and be told if the key value is Higher or Lower than your guess (~50% reduction in possibilities per guess).
• -or- you can "Examine" the chest and obtain one of the hints below.

After doing Brown casket hunting and Grounds of Valor for a few nights, I think there are the following options for Casket hints, and I've combined options that I think are exclusive to each other, meaning that "Examining" the chest multiple times will only get you one of each category:
1) Range of ~14-30 numbers. "The number is between 25 and 40." I think this becomes "Above XX" or "Below XX" if one of the limits exceeds 90 or 10 respectively.
2) First digit is Odd/Even.
3) Last digit is Odd/Even.
4) First digit is {set of 3 consecutive numbers}.
5) Last digit is {set of 3 consecutive numbers}.
6) One of the digits is X.

Minor stats to get you started:
1) If have 90 possible options and 6 guesses, then 2^5/90 = 1:2.8 chance of guessing the chest if we do nothing but optimally guess numbers splitting the distance between our limits.
Example: 54 -> Above -> 77 -> Below -> 65 -> Above -> 71 -> Below -> 68 -> Above -> Guessing from {69,70} on our 6th guess. You end up guessing between 3 more of the time, unless I did my math wrong.

2) At first glance, it seems that "Examining" the chest on your first (and possibly second) attempt is always the best option. The worst cases (2 and 3) still reduce your set of possible values by 50%, which is the best you can hope for from a guess/hint.

3) The last guess, similarly, always has to be a number (in order to potentially open the chest) and the hint that you receive on it doesn't matter because the box disappears if you get it wrong. So the real focus should be on guesses 2~5.


This problem amounts to a trade-off. The "Hints" become increasingly less valuable the more of them you have. For instance, if you've already gotten "The first digit is odd" then getting a "The first digit is 5, 6, and 7" hint only decreases your set of numbers by 1/3.

[bungiefan]

A program was already done a few years ago, when Fields of Valor came out.

http://www.ffxionline.com/forums/gen...et-solver.html

There's an HTML file and a Mac OS desktop widget.

http://fanboy.net/elwynn/casket.html

[Byrthnoth]

Those show the correct number to guess, the middle number of the range. They do nothing to address whether you should start guessing or keep asking for hints, which is a much more interesting problem. Thanks, though.

[arus2001]

Well, here's what I do depending on the first hint.

The first number is x: Input x5 then +/- 3.
The second number is x: Input 5x then chose 3x or 7x.
The first digit is x, y, z: Input y5 and proceed to play halvesies. This one gets hairy if it's 4 guesses, so may wanna use another hint.
The second digit is x, y, z: Need another hint as this leaves 27 possible numbers.
One of the numbers is x: Need another hint since this leaves 18 possibilities.
The number is between x and y: If the range is around or less than 30, basically play this like the first is x, y, z. Otherwise, use another hint at discretion.
The x digit is odd/even: Need another hint since this only halves possibilities.

My usual goal is to get the last guess to a 1/3 chance, but that's not always an option if hints are dumb or redundant.

[Francisco]

I just try to get it down to a point where I can cover all possible numbers using guesses.

Given 13, 14, 15, 33, 34, 35 as possibilities with three guesses/hints left - someone would probably be tempted to pick 14 and 34... however the correct patterns to follow would be like...

15 (higher), 34 (higher), 35 (opened)
15 (lower), 13 (higher), 14 (opened)

Probably obvious to 99% of you - but I've seen people in Zeruhn who don't know what the fuck...

[Slycer]

Sort of a necro-bump, but I found this interesting and I've been thinking about it.

Minor stats to get you started:
1) If have 90 possible options and 6 guesses, then 2^5/90 = 1:2.8 chance of guessing the chest if we do nothing but optimally guess numbers splitting the distance between our limits.
Example: 54 -> Above -> 77 -> Below -> 65 -> Above -> 71 -> Below -> 68 -> Above -> Guessing from {69,70} on our 6th guess. You end up guessing between 3 more of the time, unless I did my math wrong.

This is incorrect as it ignores the fact that you have a 1/X chance of opening the chest on each individual guess, which is not statistically insignificant as the range is reduced on the later few guesses. You would never be guessing among three options if you just went straight through with mid-range numerical guesses on a six guess crate. The chance of opening the crate guessing optimally on each guess is the inverse of the chance of not opening the crate at all on any guess:

Five guesses:
1 - (89/90 * 44/45 * 21/22 * 10/11 * 4/5) = 32.9%

Six guesses:
1 - (89/90 * 44/45 * 21/22 * 10/11 * 4/5 * 1/2) = 66.4%

These probabilities are actually slightly lower than actual as well because they assume the worse case for each guess on which the quantity of numbers in the range is even (for example, you can reduce the total number of remaining values to 44 or 45 after the first guess, depending on the result). I don't feel like going through all the possibilities, but I wouldn't be surprised if the chances were closer to 35% and 70%.

If you have a 50/50 chance each of the chest being five or six guesses, then you have a ~50% or better chance of opening any given chest if you just guess numbers straight through. I have some follow-up ideas which I might throw out in another reply here.

[Ticktick]

http://depositfiles.com/files/anvr1od7r source code included. it assumes each type hint is equally likely, and each possible hint within types is equally likely. it also assumes you won't be wanting more hints after you start guessing and that you can figure out what numbers to guess after the first. have fun.

the answer is almost always to take a hint.

[Byrthnoth]

How did you deal with the possibility of a "hint" returning a range of possible values? In my experience, this range doesn't have a fixed width. That's pretty much what stopped my attempts to make one of those.

[Ticktick]

enumerated every possible range hint with width from 14 to 30 (from your spec in the OP), minus those resulting in no possible numbers, and gave them all equal probabilities. I used expected value, so that part is basically probability of hint * size of resulting possible number set.

assuming this is what you are talking about: "1) Range of ~14-30 numbers. 'The number is between 25 and 40.' I think this becomes 'Above XX' or 'Below XX' if one of the limits exceeds 90 or 10 respectively."

i didn't allow the limits to pass 99 or 10, but that would be easy to change.

[Byrthnoth]

So you just brute force the options? Like, you've been told "First number is 1, 2, or 3" At this point you could get:
"Less than 15"
"Less than 16"
"Less than 17"
"Less than 18"
"Less than 19"
"Less than 20"
"Less than 21"
"Less than 22"
"Less than 23"
"Less than 24"
"Less than 25"
"11 to 25"
"Less than 26"
"11 to 26"
"12 to 26"
"Less than 27"
"11 to 27"
"12 to 27"
"13 to 27"
etc.

You assume the probability of all of these cases are equal and calculate the average number of options eliminated off that?

[Ticktick]

yup, not much else you can do since there are so many variations of the set of possible numbers you can have at any one point. i'm using number of options remaining, but maybe i'll change it to number eliminated since that seems like a more accurate measure.

[Slycer]

Without getting too deep into the programming yet, one thing which I immediately noticed was missing was somehow feeding the information on which numbers have been guessed. Guessing a number and not opening the chest clearly eliminates the number from the list of possibilities, which I don't think you have accounted for in your program. This does have a definite impact on what you choose to do as you narrow down your choices.

Still, this is a great start, I really like what you put together.

[Byrthnoth]

Ah, okay. I was unwilling to do it like that because I'm trying to do it in excel and I couldn't think of a clever way to code it other than writing the hundreds of possibilities out.

I think you can use the "range" option to flub in your own guesses.

[Ticktick]

i made the assumption that after making a guess, you wouldn't be wanting any more hints, to simplify the design. though there are certainly cases where this is not the case, i thought they were few enough to ignore. I also assumed that you can determine what sequence of guesses to make given the list of available numbers. I did account for the case where you are guaranteed to find the value given how many tries you have remaining, like francisco's example above.

edit:
you could use the range option to put in your own guesses, but that would remove the chance of getting a range hint from the calculation, so unless you've already gotten that hint, it would introduce some error.

[Byrthnoth]

PS. VLOOKUP and MATCH have an extreme penchant for weirdness. I started looking over my old code just now, and that was the other thing that stumped me.

VLOOKUP(1,A2:B91,2)
A2:91 is a list of 1s or 0s that says whether that cell is the optimal guess number. There's only ever a single 1 and a bunch of 0s. This is the result of an IF statement I made.
B2:91 are the numbers (10 to 99)

I can break VLOOKUP so it only returns 99 by doing things that don't change the values in any of the referenced cells at all (though it does change some of the terms in the IF statement). Still, I'm multiplying together a bunch of IF(Something,1,0) terms. So what the hell?

Edit: Nevermind, fixed it. I needed to force an exact match, which is goofy as crap. There are two values, and the thing I'm searching for matches one of them. Why the hell doesn't it just return it? Whatever, now it works.

[Slycer]

One other thing. I'm not sure if the way we're looking at this is the best way to look at it. The program you put together is basically choosing the option that has a combination of eliminating a large group of numbers AND doing so with high probability, and assumes that the alternative to using a hint is guessing the median number (+/- for an even amount of numbrs) of the range. But, is guessing the median number always the best option when you do choose to guess?

For example, if you have a six guess crate, if you can narrow the range down to 31 numbers (or fewer) on the first guess, you are guaranteed to open the crate by the sixth guess with just median numerical guesses following the first non-median guess and no hints whatsoever, removing the randomness of hints from the equation. In other words, if I choose 68 and the result is higher, or if I choose 41 and the result is lower, I am guaranteed to open the crate (eliminations would yield sets of 31 -> 15 -> 7 -> 3 -> 1). If I fail to open the crate, I am left with a 5 guess crate with a range of 10-67 or 42-99. I'm not suggesting that this way is better than starting off with a hint, I'm just proposing alternative schools of thought for what might truly be the solution that yields the highest probability of opening the crate.

[Byrthnoth]

You gain less information from a non-optimal guess than from an optimal guess, so it will never be efficient to choose non-optimally.

* Guessing 54 eliminates 45 options 46/90 times
** More than 54, you've eliminated 10 to 54 and the odds were equal to the odds of getting a number greater than or equal to 54 (99-53)/90
* ...and 46 options 45/90 times
** Less than 54, you've eliminated 54 to 99 and the odds were equal to the odds of getting a number less than or equal to 54 (55-10)/90
Average of 46 guesses eliminated, which makes sense (you eliminate half of the range, and then one extra from the guess itself).

Similarly, guessing 41 eliminates 32 options 59/90 times and 59 options 32/90 times (41.96 options eliminated on average). You eliminate more options on average by guessing 54 than 41, which is why an optimal guessing strategy improves your odds in the long run.

The correct way to compare guessing options in this case is probably to convert it into information (p*log(p)) and average them.

Spoiler: show

If you're interested in this kind of stuff, I'd recommend looking up Shannon Entropy or reading this page on efficient encoding. imop, the original paper is too mathy and dense to be casually accessible. I'd stick with secondary sources.

[Slycer]

* Guessing 54 eliminates 45 options 46/90 times
** More than 54, you've eliminated 10 to 54 and the odds were equal to the odds of getting a number greater than or equal to 54 (99-53)/90
* ...and 46 options 45/90 times
** Less than 54, you've eliminated 54 to 99 and the odds were equal to the odds of getting a number less than or equal to 54 (55-10)/90
Average of 46 guesses eliminated, which makes sense (you eliminate half of the range, and then one extra from the guess itself).

Similarly, guessing 41 eliminates 32 options 59/90 times and 59 options 32/90 times (41.96 options eliminated on average). You eliminate more options on average by guessing 54 than 41, which is why an optimal guessing strategy improves your odds in the long run.

Your logic is correct though your numbers are a little off as you double counted the guessed number. For example, you said if you guess 54 you eliminate 46 options 45/90 times and 45 options 46/90 times. That's 91/90 times. Correct way would be eliminating 89 options 1/90 times if you guess correctly, and then eliminating 44 options 45/90 times and eliminating 45 options 44/90 times on incorrect guesses, net average 45 options eliminated. Similarly with the second case, actual average is 40.96 options eliminated.

I have not taken a detailed look at how the hints compare to each other, but I know the overall value of hints is reduced as you eliminate numbers and choose other hints. Question regarding the hints -- if you choose "examine" rather than guessing six times in a row (granted this would make you fail since you obviously need to guess to get the number correct), would you always receive one hint from each of the categories you listed in the first post? My ideas were more related to how guesses and hints impact one another as you exhaust all of your chances. It's possible and likely that I'm just overthinking this and eliminating as many numbers as possible with the highest probability is always the best solution, I just didn't want to completely disregard the value of choosing an off-center guess, especially when the result of said guess can completely steer you away from needing to use any hints at all.

[Byrthnoth]

You never receive the same hint twice, but it is possible to "glean no information" very infrequently (I think it has happened to me twice). I'm not sure what would happen if you just did Examine 6 times in a row.

I don't think off-center guessing is ever a good idea, because my impression is that the hints you receive do not depend in any way upon the hints you've already been given, except that you can't get the same hint twice.

[Xantavia]

You may not get the same hint twice, but I've had occasions that are basically the same thing. Hint 1: The first digit is 3,4,5. Hint 2: The number is between 31 and 58.

And I doubt anybody has tracked it, but I seem to get a lot of double digit answers (11, 22, 33...). If it is not just my selective memory, there may less randomness than initially appears.