Does exist a strategy which allows you to live infinitely long,
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)

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      gdyo...@us.oracle.flames.com |
| Chance Dragon      Source Diver                 |
|  --=<UDIC>=--      Ascensions: VA               |
| to respond: delete all flames                   |
\-------------------------------------------------/

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.
--
damer...@chiark.greenend.org.uk T000B320O500T000N230O500T000L000D510G653I500
T000V430H600T000T000V453S530A530T000D625T000B453T000E200T300S500A530T000V22 0
A530T000S525A530T000L500O500L500T200I200T000F462T000C415H532A554F400F650T00 0
A554G453I500T000V430H600T000T000V453S530G520R530A530A653A530A653A530A653A53 0

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.
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....

--
#include <disclaimer.h>
/-------------------------------------------------\
| Gary D. Young      gdyo...@us.oracle.flames.com |
| Chance Dragon      Source Diver                 |
|  --=<UDIC>=--      Ascensions: VA               |
| to respond: delete all flames                   |
\-------------------------------------------------/

"Gary D. Young" <gdyo...@us.oracle.flames.com> writes:

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.

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"   :

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. (snell...@nortelnetworks.com)
Nortel Networks, Ottawa, Canada
Standard Disclaimer: My views only, not my employer's

Stand on a scroll of scare monster.

   - Tommi

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.

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...

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: erm1...@cam.ac.uk                 | them.

In article <xo2hff96vtr....@tcm16.phy.cam.ac.uk>, erm1...@tcm16.phy.cam.ac.uk
says...

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

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.]

Of course, I had forgotten the amulet of unchanging when I wrote this...
--
David/Kirsty Damerell.                       damer...@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.              | | |

On 16 Feb 2000 17:39:25 +0000 (GMT), David Damerell

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

In article <LDt*ZG...@news.chiark.greenend.org.uk>,
David Damerell  <damer...@chiark.greenend.org.uk> wrote:

Hey, chill.  This is false, even though the following assertion is true:

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

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.
Eva.

--
Eva Myers, Computer Officer, Statistical | Ignorance and deception can't
Laboratory, University of Cambridge      | save anybody.  *Knowing* saves
Email: erm1...@cam.ac.uk                 | them.

In article <xo2itzoq005....@tcm16.phy.cam.ac.uk>, erm1...@tcm16.phy.cam.ac.uk
says...

[Many things... basic summary: statistics sucks!]

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

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.

Aaron :

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

--
neth...@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.

        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.

Well, you've almost got it.  You also have to show that the number of
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.

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?

Sorry.

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.

--
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 <erm1...@tcm16.phy.cam.ac.uk> wrote:

What Eva says is correct; I should have been more clear.
--
David/Kirsty Damerell.                       damer...@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.

... 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.

You're awfully stroppy for someone who's talking crap.
--
David/Kirsty Damerell.                       damer...@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.

Tommi Syrjanen  <tssyr...@alpha.hut.fi> wrote:

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/Kirsty Damerell.                       damer...@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.

On 17 Feb 2000 14:56:06 +0000 (GMT), David Damerell

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...

Oh, and you aren't?  :-)  No, I don't mean that as an insult.  I just
find it humerous...

Dave