Is it possibly to live infinitely?
Dan
with non-zero probability?
1. On the current Nethack
2. On a computer where all integers could be infinitely long.
(So you can have a HP
1751941846920456965203/948727592745329475439759375937573957, say)
Gary D. Young
You could win the game and "ascend to demigod(dess)hood". From
what I recall, demigods are immortal... ;p
There's also the issue that Nethack probably depends on integers
being a fixed size (no matter how big). So you would probably
have trouble getting it to compile on that machine.
Practice makes perfect in Nethack. But remember that you have
to break a few eggs to make an omlette.
--
#include <disclaimer.h>
/-------------------------------------------------\
| Gary D. Young gdy...@us.oracle.flames.com |
| Chance Dragon Source Diver |
| --=<UDIC>=-- Ascensions: VA |
| to respond: delete all flames |
\-------------------------------------------------/
David Damerell
>Does exist a strategy which allows you to live infinitely long,
>with non-zero probability?
No.
Assertion; if such a strategy exists, it can survive any set of random
numbers. Hence, I can wonder about just how pathological the RNG can be.
You can't pray for food indefinitely. There is a nonzero chance that no
food or edible corpses will be generated for a very long time. You can't
reliably polymorph into a non-eating monster. Hence, you starve.
--
dame...@chiark.greenend.org.uk T000B320O500T000N230O500T000L000D510G653I500
T000V430H600T000T000V453S530A530T000D625T000B453T000E200T300S500A530T000V220
A530T000S525A530T000L500O500L500T200I200T000F462T000C415H532A554F400F650T000
A554G453I500T000V430H600T000T000V453S530G520R530A530A653A530A653A530A653A530
Gary D. Young
> with non-zero probability?
>
> 2. On a computer where all integers could be infinitely long.
> (So you can have a HP
> 1751941846920456965203/948727592745329475439759375937573957, say)
>
1) Find one of those little one-square places off of some rooms
that are empty and have no exits/entrances. Not a vault.
2) Teleport there (preferably without intrinsic teleportation),
or polymorph into a Xorn and walk there.
3) Polymorph into a creature that doesn't eat. IIRC, none of
the undead monsters eat, so I'd suggest a dwarf zombie. Aren't
zombies supposed to eat brains? Perhaps that can be a future
modification...
4) Put on an amulet of unchanging.
5) Genocide Xorns, Mind flayers, dwarves (all of them), rock
moles, umber hulks, and anything else that can dig. They're
the only ones I think have a chance of damaging you through
a wall.
6) n60000.
7) goto step 6.
You ought to be able to survive this, but if you can pull it
off, you're probably well-equipped enough to attempt an actual
ascension.
Anyone have any modifications to this setup to make it more
fool-proof? Perhaps getting rid of the warning intrinsic or
ESP, or something would be useful so the game doesn't
interrupt you with messages. That's why I suggested the lack
of intrinsic teleportation. Getting rid of automatic searching
would be nice in case you jumped into a one-width room that
actually had a secret door attached....
Dylan O'Donnell
> "Dan" <rb...@hotmail.com> wrote in message news:38A9717C...@hotmail.com...
> > Does exist a strategy which allows you to live infinitely long,
> > with non-zero probability?
> Actually, I just thought of a way to live indefinitely.
>
> 1) Find one of those little one-square places off of some rooms
> that are empty and have no exits/entrances. Not a vault.
Note that these will never be _empty_, as such; there'll always be at
least a scroll of teleportation, just in case some accident got you
stuck there.
> 2) Teleport there (preferably without intrinsic teleportation),
> or polymorph into a Xorn and walk there.
> 3) Polymorph into a creature that doesn't eat. IIRC, none of
> the undead monsters eat, so I'd suggest a dwarf zombie. Aren't
> zombies supposed to eat brains? Perhaps that can be a future
> modification...
> 4) Put on an amulet of unchanging.
> 5) Genocide Xorns, Mind flayers, dwarves (all of them), rock
> moles, umber hulks, and anything else that can dig. They're
> the only ones I think have a chance of damaging you through
> a wall.
> 6) n60000.
> 7) goto step 6.
>
> You ought to be able to survive this, but if you can pull it
> off, you're probably well-equipped enough to attempt an actual
> ascension.
A refinement - you don't want to wear the amulet, that'll make you
hungry. You want to be polyed into a xorn and eat it (or enough so
that one takes). (Don't worry about then genociding them; if you've
got unchanging, you can survive it provided you use a blessed scroll
rather than an uncursed one. This is very likely a bug. I'll see what
nethack-bugs have to say). Xorns don't _need_ to eat, so you're safe
enough right there.
You'll need to be on a level with no ghosts or shades, of course.
Genocide woodchucks and doppelgangers as well (as archeologists, dopps
can tunnel if they lay their hands on a pick axe). Avoid levels with
message-producing features like fountains or shops.
A quick test in wizard mode shows this works up to 100000 turns
(that's xorn turns - the speed system means that the turn counter
doesn't quite track the number of . commands issued. Also, you can't
wait 60000 at once, the max is LARGEST_INT which is 32767) without
apparent problem. All those monsters being generated throughout the
level and then tracked don't half chew up CPU after a while,
though. Wonder if there's any problems when the level becomes
_entirely_ full of monsters... the RNG should, as far as I can see,
just give up trying to place new ones at that point, but I doubt it's
undergone much stress-testing. Quaffing a blessed potion of monster
detection at this point is _fun_, though :-)
Having said all this, there's rather a drawback. Earth elementals
aren't genocidable. You'll have to have the whole thing arranged on a
level where they can't be generated, which means the average of your DL
and XL need to be less than 10.
--
: Dylan O'Donnell : Stay alert! :
: Demon Internet : Trust no-one! :
: Resident, Forgotten Office : Keep your laser handy! :
: http://www.fysh.org/~psmith/ : -- Greg Costikyan, "Paranoia" :
Peter Snelling
> Having said all this, there's rather a drawback. Earth elementals
> aren't genocidable. You'll have to have the whole thing arranged on a
> level where they can't be generated, which means the average of your DL
> and XL need to be less than 10.
How about instead of doing it in a 1x1 unattached
room, you dig it out to be a 3x3 unattached room,
you stand in the middle, and then reverse genocide
brown molds (or some other sessile monster) so that
they occupy the 8 spaces around you.
You still need to genocide any digging monsters,
but I think you should now be safe from Xorns and
Earth Elementals, since they wouldn't attach the
molds so they'd never get next to you.
FFF
E FXF
FFF
+------+
|DcjnLR|
--
Peter Snelling, P.Eng. (snel...@nortelnetworks.com)
Nortel Networks, Ottawa, Canada
Standard Disclaimer: My views only, not my employer's
Tommi Syrjanen
> Having said all this, there's rather a drawback. Earth elementals
> aren't genocidable. You'll have to have the whole thing arranged on a
Stand on a scroll of scare monster.
- Tommi
Bagpuss
>Dan <rb...@hotmail.com> wrote:
>>Does exist a strategy which allows you to live infinitely long,
>>with non-zero probability?
>
>
>Assertion; if such a strategy exists, it can survive any set of random
>numbers. Hence, I can wonder about just how pathological the RNG can be.
Not true. To have a non-zero probablity of success, it must work for at least
*one* set of random numbers, the answer's still no, though, I think.
>You can't pray for food indefinitely. There is a nonzero chance that no
>food or edible corpses will be generated for a very long time. You can't
>reliably polymorph into a non-eating monster. Hence, you starve.
Given that there is only a fixed number of each type of monster, after a
(long) while, you'd end up relying on food being generated and after you've
cleared out the stuff from every level, there wil be no more food generated,
so you end up starving to death in a very empty dungeon.
OTOH it is possible to wish for smoky potions, which have a possibilty of
giving you more wishes, so using some wishes on food and some on more smoky
potions, you might live for ever. In fact, if smoky is fruit juice, you won't
even have to wish for food. I don't think this is very likely to work,
though.
--
Richard Smeltzer
But it can still be a brighter day, all I need are some cooking
utensils and my special party hat...
Eva R. Myers
> Dan <rb...@hotmail.com> wrote:
> >Does exist a strategy which allows you to live infinitely long,
> >with non-zero probability?
>
> No.
>
> Assertion; if such a strategy exists, it can survive any set of random
> numbers. Hence, I can wonder about just how pathological the RNG can be.
>
> You can't pray for food indefinitely. There is a nonzero chance that no
> food or edible corpses will be generated for a very long time. You can't
> reliably polymorph into a non-eating monster. Hence, you starve.
I wonder whether you could manage it with a horn of plenty and the
Platinum Yendorian Express Card. If you could have a horn of plenty
with infinite charges, then I'm pretty sure your probability of
surviving indefinitely would be high. If you apply it and produce a
food ration, that's 800 units, and extends your time to live by 794
turns after you've deducted the 1 turn taken to produce it and the 5
turns taken to eat it. If you produce a potion of acid, then that has
no nutrition, and you've wasted 1 turn. (You may also have to waste
the occasional turn putting things down or picking them up, but I
don't think that makes much difference.) So with the hypothetical
infinite horn, your time to live oscillates up and down in a random
walk. Since you gain much more when you get food than you lose when
you get a potion of acid, and I think the probability of getting food
on a random application of a horn of plenty is quite high, you are
likely to survive indefinitely.
What happens when the infinite horn is replaced by a horn of plenty
and the PYEC? First of all, can a horn of plenty be recharged
infinitely many times? If not, then this strategy is completely
useless. Next, how long do you have to wait between invocations of
the PYEC - is it a random number between X and Y, or a random number
from a Poisson distribution with mean X, and what are the values of X
and Y? It might make a difference whether or not you are a Tourist
and able to perform blessed charging. Even so, since even one food
ration will keep you going more than long enough to invoke the PYEC
again, this strategy seems quite promising to me.
Eva.
--
Eva Myers, Computer Officer, Statistical | Ignorance and deception can't
Laboratory, University of Cambridge | save anybody. *Knowing* saves
Email: erm...@cam.ac.uk | them.
Aaron
says...
>
>David Damerell <dame...@chiark.greenend.org.uk> writes:
>
>> Assertion; if such a strategy exists, it can survive any set of random
>> numbers. Hence, I can wonder about just how pathological the RNG can be.
>>
>> You can't pray for food indefinitely. There is a nonzero chance that no
>> food or edible corpses will be generated for a very long time. You can't
>> reliably polymorph into a non-eating monster. Hence, you starve.
>
>and the PYEC? First of all, can a horn of plenty be recharged
>infinitely many times? If not, then this strategy is completely
>useless. Next, how long do you have to wait between invocations of
>the PYEC - is it a random number between X and Y, or a random number
>from a Poisson distribution with mean X, and what are the values of X
>and Y? It might make a difference whether or not you are a Tourist
>and able to perform blessed charging. Even so, since even one food
>ration will keep you going more than long enough to invoke the PYEC
>again, this strategy seems quite promising to me.
>Eva.
Not to mention that with a amulet of unchanging, and an appropriate
polymorph form, you can greatly increase the periods between needing
to eat.
A
David Damerell
>dame...@chiark.greenend.org.uk wrote:
>>Dan <rb...@hotmail.com> wrote:
>>>Does exist a strategy which allows you to live infinitely long,
>>>with non-zero probability?
>>numbers. Hence, I can wonder about just how pathological the RNG can be.
>*one* set of random numbers, the answer's still no, though, I think.
Oh, FFS. Doesn't anyone think before posting? He's talking about surviving
_infinitely_ long; any _finite_ series of numbers will be generated by the
RNG in that period. A strategy that works for only some sets of random
numbers has a non-zero probability of success for any finite (even
extremely long) period, but not for an infinite one.
[More precisely, the probability of such a strategy succeeding tends to
zero as the number of turns tends to infinity.]
>>You can't pray for food indefinitely. There is a nonzero chance that no
>>food or edible corpses will be generated for a very long time. You can't
>>reliably polymorph into a non-eating monster. Hence, you starve.
Of course, I had forgotten the amulet of unchanging when I wrote this...
--
David/Kirsty Damerell. dame...@chiark.greenend.org.uk
CUWoCS President. http://www.chiark.greenend.org.uk/~damerell/ Hail Eris!
|___| "Life is short and love is always over in the morning." |___|
| | | Temple of Love - The Sisters of Mercy. | | |
David Grenier
<dame...@chiark.greenend.org.uk> wrote:
>Bagpuss <MAT...@leeds.ac.spamuk.leeds.ac.uk> wrote:
>>dame...@chiark.greenend.org.uk wrote:
>>>Dan <rb...@hotmail.com> wrote:
>>>>Does exist a strategy which allows you to live infinitely long,
>>>>with non-zero probability?
>>>Assertion; if such a strategy exists, it can survive any set of random
>>>numbers. Hence, I can wonder about just how pathological the RNG can be.
>>Not true. To have a non-zero probablity of success, it must work for at least
>>*one* set of random numbers, the answer's still no, though, I think.
>
>Oh, FFS. Doesn't anyone think before posting? He's talking about surviving
>_infinitely_ long; any _finite_ series of numbers will be generated by the
>RNG in that period. A strategy that works for only some sets of random
>numbers has a non-zero probability of success for any finite (even
>extremely long) period, but not for an infinite one.
>
>[More precisely, the probability of such a strategy succeeding tends to
>zero as the number of turns tends to infinity.]
Not a horribly brilliant proof, and it doesn't even have the virtue of
being correct. Oh well...
The probability of a specific strategy will only approach zero as the
number of turns in the game tends to infinity if the strategy is
unsound. Even given that stipulation, such a strategy still has a
positive, albeit negligible, chance of surviving infinitely. Suppose
for a moment that every number the RNG generates can be likened to a
single digit, so those digits, if laid out one after the other, would
reveal an irrational real number. Let's also assume that for two
specific values of that number, pi and e, the attempt will succeed.
The probability of succeeding after the first turn is .2, after the
second turn it is .02, after the third .002, ad infinitum. The limit
as the function approaches infinity is zero, but the actual value of
the function as it approaches infinity is (.2)*(.1)^(infinity), while
infintesimally small, is a positive number.
Perhaps you should think a little harder before posting responses out
of your apparent field?
Dave
Christopher Jeris
David Damerell <dame...@chiark.greenend.org.uk> wrote:
>Oh, FFS. Doesn't anyone think before posting? He's talking about surviving
>_infinitely_ long; any _finite_ series of numbers will be generated by the
>RNG in that period.
Hey, chill. This is false, even though the following assertion is true:
>[More precisely, the probability of such a strategy succeeding tends to
>zero as the number of turns tends to infinity.]
You have to state the first one in the same sense: the probability of any
a-priori-fixed sequence appearing in a string approaches 1 as the string
gets long. I'm sure you know this, but nonmathematical readers might be
confused by the first formulation.
If an event that will kill you may occur every turn, with probability p,
then the expected number of turns for which you survive is (1 - p)/p.
For more details look in a text on probability or statistics, under
"binomial distribution".
peace,
Chris Jeris
Eva R. Myers
> Bagpuss <MAT...@leeds.ac.spamuk.leeds.ac.uk> wrote:
> >dame...@chiark.greenend.org.uk wrote:
> >>Dan <rb...@hotmail.com> wrote:
> >>>Does exist a strategy which allows you to live infinitely long,
> >>>with non-zero probability?
> >>Assertion; if such a strategy exists, it can survive any set of random
> >>numbers. Hence, I can wonder about just how pathological the RNG can be.
> >Not true. To have a non-zero probablity of success, it must work for at least
> >*one* set of random numbers, the answer's still no, though, I think.
>
> Oh, FFS. Doesn't anyone think before posting? He's talking about surviving
> _infinitely_ long; any _finite_ series of numbers will be generated by the
> RNG in that period. A strategy that works for only some sets of random
> numbers has a non-zero probability of success for any finite (even
> extremely long) period, but not for an infinite one.
>
> [More precisely, the probability of such a strategy succeeding tends to
> zero as the number of turns tends to infinity.]
If there were one particular finite series of random numbers that would
kill you no matter _what_ your situation was when it came up, then
your probability of surviving infinitely long would be zero. E.g., if
your only source of nutrition was monsters that you had just killed,
then a period of more than 5000 turns with no monsters being generated
would kill you. (I suspect that number is way too high - I'm just
using it for an illustration.) Because the 5000 zeroes _will_ turn up
eventually, the probability of success tends to zero.
But if the series of random numbers it would take to kill you is not
fixed but tending to increase in length over time, then your
probability of surviving infinitely long need no longer be zero. This
is what I think happens with my strategy of the horn of plenty - by
the time the 5000 zeroes hit, you have almost certainly got a
sufficient stockpile of food to survive them. By the time enough
zeroes to kill you with that stockpile turn up, the stockpile has
grown big enough to survive them, ad infinitum with non-zero
probability.
A strategy which could survive _any_ set of random numbers would have
probability 1 of success (once it reached the point of being able to
survive anything). David's right that there's no strategy which does
reach the point of being able to survive anything (except for eating
an amulet of unchanging?), but the probability can tend to a finite
number somewhere between one and zero as the number of turns tends to
infinity.
This is similar to the "unbounded random walk" problem which you may
know about - if you start on the edge of a cliff, and on each turn
walk one step towards it or one step away from it with equal
probability, then you will fall over with probability 1. But if
instead you walk away with probability 2/3 and towards with
probability 1/3, then you have probability 1/2 of surviving for ever.
I hope a mathematician will now jump in, explain why this is, and
correct any mistakes I've made in this post.
Aaron
says...
[Many things... basic summary: statistics sucks!]
>A strategy which could survive _any_ set of random numbers would have
>probability 1 of success (once it reached the point of being able to
>survive anything). David's right that there's no strategy which does
>reach the point of being able to survive anything (except for eating
>an amulet of unchanging?)
Well... I think, in nethack's current incarnation, that the
probability can indeed be 1.
As a test, I'm currently sitting at turn 336,894 with no apparent
reason to think the safe status of the character will change.
Not unless there's a programming limitation I can hit (ie: if
the turn counter reaches the maximum size for the variable it
is stored in? What if the 14 spaces still unoccupied on my
map have a monster generated in them, and then the program
tries to generate another... will it crash?)
But, assuming the program doesn't blow up from stress-testing
code limitations... I think it does indeed hit probability
1. =)
(note, for the record, I'm the X, there is a boulder, as well
as a blue jelly on each of the squares surrounding me, and
I have genocided master mind flayers and mind flayers.)
(for a nice image of the current state of the game, after
336k turns on the same level, see:
http://www.iphc.washington.edu/staff/aaron/NHStressTest.jpg
It is interesting to note that, after about turn 100k, all
the monsters on the level really started to thrash my cpu
over long waits. =)
A
Nephi Allred
> Oh, FFS. Doesn't anyone think before posting? He's talking about surviving
> _infinitely_ long; any _finite_ series of numbers will be generated by the
> RNG in that period. A strategy that works for only some sets of random
> numbers has a non-zero probability of success for any finite (even
> extremely long) period, but not for an infinite one.
Others have already pointed out problems with this argument but here's one
that I haven't heard from anyone yet (on this topic):
Some may call it a god, but the RNG is a Turing machine. It CANNOT generate
even one random number. What it does is generate psuedo random numbers.
Different seeds increase the number of psuedo random numbers which can be
generated, but there are a finite number of possible seeds. So for some
integer n,
after generating n pseudo random numbers the n+1 th will be the same the
first, the
n+2th the same as the second etc. The number n may be fantastically large
but it is
not infinite.
If the DevTeam have found a way around this, there are some cryptographers
that
would like to speak with them.
(All of this is assuming that the RNG is not hooked up to some external
physical event
to get its random numbers rather than using a psuedo random number
generator)
Nephi
--
Homer: Aah! OK, don't panic -- remember the advice your father gave you
on your wedding day.
[remembers Abe with hair and a tuxedo]
Abe: If you ever travel back in time, don't step on anything because
even the tiniest change can alter the future in ways you can't
imagine.
Sascha Wostmann
> Ok... here it is...
Well, I followed your HOWTO in wizmode and used it on the bigroom. On
my first attempt I was only surrounded by seven jellies and at the
remaining corner there came a giant eventually which I killed with the
wand of death I wished for. Then I teleported away into a new location
where I made a full shield of jellies and boulders around me.
Now I discovered something funny: most of the monsters on the level
(and there are many at turn #10,000) followed me to the new location,
but some of them remain lurking around my former position. How is the
monster movement AI implemented? Do they reckognize me at my old
position and just missed my teleport or what?
Oh, and a bug maybe:
You hear a mumbled curse. HM7 You hear a mumbled curse.--More--
HM7? I only know Scroll Nr. 9...
Sascha
--
net...@gmx.de http://www.nethack.de/
You break up the fortune cookie and throw away the pieces.--More--
This cookie has a scrap of paper inside. It reads:--More--
Shopkeepers can't tell identical twins apart.
Rob Ellwood
>
> Given that there is only a fixed number of each type of monster,
> after a (long) while, you'd end up relying on food being
> generated and after you've cleared out the stuff from every
> level, there wil be no more food generated,
> so you end up starving to death in a very empty dungeon.
The quest levels for Barbarians specialize in Ogres. The
"extinct after 120" rule doesn't apply there. I've killed over
1000 of the beggars. I suspect that the same applies to [quest
levels + quest special enemies] for all types of characters.
(I tinned over 500 of them. And they're yours for just
20 zorkmids a tin! Home-made ogre: yum yum.)
--
Rob Ellwood
To reply, delete the anti-spam stuff in the address.
Scott Schulz
states of the system being driven by the pseudo-random number generator
is finite as well. Otherwise, even though the string of numbers
regenerates, the system it is driving may go through ever new
combinations. Of course, in the absence of infinite storage capacity
the system will have to have a finite number of states (otherwise, you'd
have to be able to represent an infinite number of states in a finite
machine).
All of this begs the question: does there exist a recurrent sequence of
pseudo-random numbers and states within the the Nethack universe such
that a character remains alive indefinitely. I believe, that as close
as we can get to a proof lays in Dylan's strategy after a level has
completely filled up with monsters. The state of the system at that
point pretty much reduces to the turn counter which is the only thing
which will change from one turn to the next. That is, no hunger or new
monsters can be generated, and nothing else except for the turn counter
and any message text for stuff on the level (pets, thrones, fountains,
vaults, etc.) will be triggered. Thus, I would be inclined to believe
that there is such a state and sequence. That sequence is, however, at
a minimum 2^(n-1) turns long (where n is the byte size of the processor
in bits) assuming a that nethack uses the usual poor rgn in most
interpreted languages like C+. Thus, providing the instance (one
sequence of numbers and the corresponding states) to prove that a
character could survive indefinitely is theoretically possible but
practically prohibitive.
Scott Schulz, Ph.D., killed by a dissertation committee
--
http://www.slip.net/~sschulz/WWWW/sschulzh.htm
Sent via Deja.com http://www.deja.com/
Before you buy.
Dan
> David Damerell <dame...@chiark.greenend.org.uk> writes:
>
> > Dan <rb...@hotmail.com> wrote:
> > >Does exist a strategy which allows you to live infinitely long,
> > >with non-zero probability?
> >
> > No.
> >
> > Assertion; if such a strategy exists, it can survive any set of random
> > numbers. Hence, I can wonder about just how pathological the RNG can be.
> > You can't pray for food indefinitely. There is a nonzero chance that no
> > food or edible corpses will be generated for a very long time. You can't
> > reliably polymorph into a non-eating monster. Hence, you starve.
>
On the current Nethack, the RNG is periodic. So you should not
survive *any* set of random numbers, only those sets which
RNG can generate.
As for the abstract "ideal nethack", if you make food faster than eat it,
there is a non-zero probability that you never be out of food.
Here is the related question: suppose you genocided all genocidable
monsters and killed all unique monsters. Which other monsters
can appear on level 1?
Bagpuss
>On 16 Feb 2000 17:39:25 +0000 (GMT), David Damerell
><dame...@chiark.greenend.org.uk> wrote:
>
>>>>>Does exist a strategy which allows you to live infinitely long,
>>>>>with non-zero probability?
>>>>numbers. Hence, I can wonder about just how pathological the RNG can be.
> least
>>>*one* set of random numbers, the answer's still no, though, I think.
>>
>>_infinitely_ long; any _finite_ series of numbers will be generated by the
>>RNG in that period. A strategy that works for only some sets of random
>>numbers has a non-zero probability of success for any finite (even
>>extremely long) period, but not for an infinite one.
Sorry.
>>[More precisely, the probability of such a strategy succeeding tends to
>>zero as the number of turns tends to infinity.]
>
>Not a horribly brilliant proof, and it doesn't even have the virtue of
>being correct. Oh well...
>
>The probability of a specific strategy will only approach zero as the
>number of turns in the game tends to infinity if the strategy is
>unsound. Even given that stipulation, such a strategy still has a
>positive, albeit negligible, chance of surviving infinitely. Suppose
>for a moment that every number the RNG generates can be likened to a
>single digit, so those digits, if laid out one after the other, would
>reveal an irrational real number. Let's also assume that for two
>specific values of that number, pi and e, the attempt will succeed.
>The probability of succeeding after the first turn is .2, after the
>second turn it is .02, after the third .002, ad infinitum. The limit
>as the function approaches infinity is zero, but the actual value of
>the function as it approaches infinity is (.2)*(.1)^(infinity), while
>infintesimally small, is a positive number.
>
>Perhaps you should think a little harder before posting responses out
>of your apparent field?
No, he was right. I didn't think properly before posting and I rushed out
the reply because I had to dash off to a maths lecture (oh, the irony).
1^infinity is not a positive number, unless you're working with some odd
definition, of which the rest of us are unaware. To try to prove this:
between any two real numbers, there is an infinite number of real numbers
(the axiom of completeness IIRC), but between 0 and .1^infinity, there is
not a gap, so there are no numbers between them, therefore if .1^infinty is
a real number, then it is 0.
David Damerell
>If there were one particular finite series of random numbers that would
>kill you no matter _what_ your situation was when it came up, then
>your probability of surviving infinitely long would be zero. E.g., if
>fixed but tending to increase in length over time, then your
>probability of surviving infinitely long need no longer be zero. This
What Eva says is correct; I should have been more clear.
--
David/Kirsty Damerell. dame...@chiark.greenend.org.uk
CUWoCS President. http://www.chiark.greenend.org.uk/~damerell/ Hail Eris!
|___| You bought a mask: I put it on: you never thought to ask me if I wear
| | | it when you're gone. The Sisters of Mercy: When You Don't See Me.
David Damerell
><dame...@chiark.greenend.org.uk> wrote:
>>[More precisely, the probability of such a strategy succeeding tends to
>>zero as the number of turns tends to infinity.]
>for a moment that every number the RNG generates can be likened to a
>single digit, so those digits, if laid out one after the other, would
>reveal an irrational real number. Let's also assume that for two
>specific values of that number, pi and e, the attempt will succeed.
>The probability of succeeding after the first turn is .2, after the
>second turn it is .02, after the third .002, ad infinitum. The limit
>as the function approaches infinity is zero, but the actual value of
>the function as it approaches infinity is (.2)*(.1)^(infinity), while
>infintesimally small, is a positive number.
... tending to zero as the number of turns tends to infinity - so inasmuch
as 'surviving an infinite number of turns' is a meaningful concept, the
probability of it is zero. Nice try.
>Perhaps you should think a little harder before posting responses out
>of your apparent field?
You're awfully stroppy for someone who's talking crap.
David Damerell
>Well, I'm not a mathematician but I've noticed one error that just
>about everyone has made. That is, you have been making calculations
>based on true random sequences while Nethack uses only pseudo-random
>numbers. To quote (not necessary the exact words) von Neumann:
NetHack _might_ use the system random number source, which might use
something like Linux's /dev/random which is based on real-world events.
I think we should assume a truly random random number generator for this
exercise, personally.
David Grenier
<dame...@chiark.greenend.org.uk> wrote:
>David Grenier <gre...@uiuc.edu> wrote:
>><dame...@chiark.greenend.org.uk> wrote:
>>>[More precisely, the probability of such a strategy succeeding tends to
>>>zero as the number of turns tends to infinity.]
>>positive, albeit negligible, chance of surviving infinitely. Suppose
>>for a moment that every number the RNG generates can be likened to a
>>single digit, so those digits, if laid out one after the other, would
>>reveal an irrational real number. Let's also assume that for two
>>specific values of that number, pi and e, the attempt will succeed.
>>The probability of succeeding after the first turn is .2, after the
>>second turn it is .02, after the third .002, ad infinitum. The limit
>>as the function approaches infinity is zero, but the actual value of
>>the function as it approaches infinity is (.2)*(.1)^(infinity), while
>>infintesimally small, is a positive number.
>
>... tending to zero as the number of turns tends to infinity - so inasmuch
>as 'surviving an infinite number of turns' is a meaningful concept, the
>probability of it is zero. Nice try.
Thank you. You know, I wouldn't have complained if you had added "for
all practical purposes" to your definition. Infintesimals are *not*
zero, but they are considered to be zero for all practical purposes.
Mind you, I haven't happened upon a branch of mathematics where it
matters yet, but I know one exists...
>>Perhaps you should think a little harder before posting responses out
>>of your apparent field?
>
>You're awfully stroppy for someone who's talking crap.
Oh, and you aren't? :-) No, I don't mean that as an insult. I just
find it humerous...
Dave
Nathan Alexander Simington
David Grenier wrote:
> I just find it humerous...
This thread tickles my funny bone too.
Nathan
David Damerell
Both Eva Myers and the person I was replying to seem to feel that I'm not;
I know for a fact Eva is a competent mathematician. So no, I don't suppose
that I am.
Peter Snelling
> This is similar to the "unbounded random walk" problem which you may
> know about - if you start on the edge of a cliff, and on each turn
> walk one step towards it or one step away from it with equal
> probability, then you will fall over with probability 1.
It reminded me more of a (complex) state machine with one
terminal state. I'm trying to think of the name for this,
but it's been way too long since I did any stats. I think
there's some standard stats term for a Markov (?) process
with a state that you can never transfer out of. If there's
any possibility to arrive in that state, then you will with
probability 1 over an infinite time.
Nethack isn't really unbounded. I start thinking about
it as a simple two dimensional walk, with the one dimension
consisting of your hitpoints, and another dimension being
your nutrition. Both of those have a maximum, and if either
go to 0 you lose. This isn't perfect model, as there are
some things which can kill you without losing hitpoints
or nutrition. But assume your stategy guarantees that you
avoid all of those.
So the simple solution to this problem we're trying to find
is one that clearly avoids any possibility by ensure you
never lose any hitpoints or nutrition (and avoids all the
other ways to die). There are possibly more complex solutions,
such as ensuring that your nutrition drops slowly enough that
your prayer timeout would always allow you to get food.
You could probably think up solutions that would be pretty
complex to analyze. For example: imagine you could show
that only the 8 monsters adjacent to you could do damage.
They did between 0 and 80 damage per turn (say 16d5). But
if your AC made the average only 10 per turn, and you
regenerated at 11 per turn, and you have 300 max HP, you'll
eventually die (I think). But how long do you last on
average?
Bruce Cox
[1 changed to .1 in the following line -- ed]
> .1^infinity is not a positive number, unless you're working with some odd
> definition, of which the rest of us are unaware. To try to prove this:
> between any two real numbers, there is an infinite number of real numbers
> (the axiom of completeness IIRC), but between 0 and .1^infinity, there is
> not a gap, so there are no numbers between them, therefore if .1^infinty is
> a real number, then it is 0.
I think you are working with an odd definition here. .1^infinity is
not a positive number because it is just a string of characters:
infinity is not something you can use meaningfully like this (without
defining your own convention). In this case, however, it seems clear
that it is meant to denote lim_{h->\infty}(0.1)^h.
Now for the proof. Yours is hand-waving: Why is there not a gap?
Because you already know it is zero. So it is hardly a good proof
that it _is_ zero.
A correct proof that the limiting value is zero requires you to be
able to supply, given any positive real e, a positive integer N(e)
such that |(0.1)^h| < e for all values of h >= N. In fact, this is
very easy: simply let N be ceiling(-log_10(e)) if e < 1 or 1
otherwise. (Well, I think that's a suitable N: I haven't checked it
rigorously).
Cheers,
bruce
Scott Schulz
> It reminded me more of a (complex) state machine with one
> terminal state. I'm trying to think of the name for this,
> but it's been way too long since I did any stats. I think
> there's some standard stats term for a Markov (?) process
> with a state that you can never transfer out of. If there's
> any possibility to arrive in that state, then you will with
> probability 1 over an infinite time.
True if the terminal (or absorbing) state is unique. Any transient
Markov Chain will exit all transient classes woth probability 1 as t
goes to infinity. If there are multiple absorbing states accessible
from a transient state, then there will be a strictly positive
probability associated with each absorbing state of eventually
hitting that absorbing state from that transient state. The question is
whether death is the only absorbing state in Nethack or is there an
absorbing state where the character stays alive. Sufficient proof of
that would be to prove that it is possible for a character to reach a
point where he or she never takes damage or uses nutrition. Again, I
think Dylan has pretty much delineated such a state.
Scott the Ph.D., killed by an Occam's Razor
Mike
>"extinct after 120" rule doesn't apply there. I've killed over
>1000 of the beggars. I suspect that the same applies to [quest
>levels + quest special enemies] for all types of characters.
the rule doesn't seem to apply to killer bees, either. on my most
recent damn-close-to-ascension (iced in the plane of air), I'd killed
150-some.
Tommi Syrjanen
> Mike <stev...@buckNOSPAMnell.edu> writes:
> >the rule doesn't seem to apply to killer bees, either. on my most
> >recent damn-close-to-ascension (iced in the plane of air), I'd killed
> >150-some.
>
I noticed the same thing in 3.3.0 when I tried the
live-forever-as-an-unchanging-xorn trick. In the end the kill-list
showed 220 dead killer bees. (My dog drove a couple of species into
extinction before succumbing to large monsters).
- Tommi
Kieron Dunbar
> second turn it is .02, after the third .002, ad infinitum. The limit
> as the function approaches infinity is zero, but the actual value of
> the function as it approaches infinity is (.2)*(.1)^(infinity), while
> infintesimally small, is a positive number.
For the purposes of this discussion, .2*.1^infinity can be taken as 0. My
reason is that, for any finite series of random real numbers (there not
being enough time to perform an infinite series), the number of times for
which either pi or e would be expected to appear is exactly 0.
kwaheri, Kieron