Requests for stronger crash reporting

Post by **Paul Stevens** » Tue Apr 25, 2006 7:58 pm

Bug! The spell doesn't work anymore.

Zyx:
If you think there is any chance that CSBwin could
do something more graceful than 'Crash', then let
me know. In general I would like to have things
simply not work rather than crash the program.

Post by **Zyx** » Tue Apr 25, 2006 8:26 pm

Can you detect infinte loops?
The crash was due to "an infinite loop in a DSA". Displaying such a message would help both the player and designer. Also, stopping the log once the loop is detected would be useful, since the log keeps growing (160Mb before I stop CSBwin!)

Btw, I sent the fixed game, Kid_A.

Post by **Paul Stevens** » Tue Apr 25, 2006 8:31 pm

Can you detect infinte loops

No. No way to detect infinite loops. That was proven
by a famous mathemetician long ago.

But we could stop at 4294967295
(or any smaller integer number) of loops.

beowuuf · Post by **beowuuf** » Tue Apr 25, 2006 8:35 pm

Well, there might be, it will just take a little more time to prove it is working... any moment now....

I must admit the worst crashes I used to get were when a command would be pointed to a non-existent or negative level... is there still the potential for a nasty crash with these types of mistakes?

George Gilbert · Post by **George Gilbert** » Tue Apr 25, 2006 9:18 pm

Paul Stevens wrote:
Can you detect infinte loops
No. No way to detect infinite loops. That was proven
by a famous mathemetician long ago.

Turing I believe.

As a corollory to that there's also another theorem that states that it's not possible to determine the output of some code other than by running it. I'm sure there's a parallel with playing with dungeon mechanics in there somewhere

Post by **Sophia** » Tue Apr 25, 2006 9:42 pm

Paul Stevens wrote:But we could stop at 4294967295
(or any smaller integer number) of loops.

Why stop there?

64-bit integers have been supported forever by most compilers.

Post by **Zyx** » Tue Apr 25, 2006 9:50 pm

Really? I understand you can't detect infinite loops before running CSBwin, according to Turing.

However, while running a DSA, take a snap shot of the logical state after each instruction. By logical state I mean variables + stack + current place in the code.
Compare with all the previous logical states. If the current state is identical to a previous one, you're in an infinite loop.

(I know it wouldn't be very practical, but I'm just thinking about detecting infinite loops.)

beowuuf · Post by **beowuuf** » Tue Apr 25, 2006 10:04 pm

You might have a self targetting DSA that is sitting in a waiting period until something external breaks it (like a monster freeze until you are bitten, or I assume a DSA swapping overlays until you come out of the environment. I think the number is better than checking state

rain` · Post by **rain`** » Wed Apr 26, 2006 4:25 am

Isn't there an infinite loop in conflux III? Infinite tower of loops?

I think Zyx has become hypocritical here, sure he wants to stop DSA's from being infinit, but forces us to climb an infinite tower. Maybe its time to take a toe, wheres my knife?

Post by **Paul Stevens** » Wed Apr 26, 2006 4:10 pm

take a snap shot of the logical state after each instruction

In principle you are perfectly right. Mr Turing's machine
had an infinitely long tape. But the DSA has a very large
dungeon. And the dungeon is part of the DSA's state.

Would you like me to do this for you? Save your multi-megabyte
dungeon after each instruction? And save all those snapshots
so that the current state can be compared to each of the previous
10,000 or so snapshots? (It really is not that bad.....There is a
nice algorithm that does not require us to keep all 10,000. Only
one, actually. But then we have to run all the instructions
twice. So it is a tradeoff between CPU time and disk space.)

Post by **Zyx** » Wed Apr 26, 2006 5:05 pm

I was just demostrating that it is possible to detect an infinite loop during runtime for CSBwin. I am well aware of the cost.
Obviously limiting the DSA operations to a certain number is much more practical. Which should be this number I don't know.
As a rough guess I could propose the number of DSA operations a 100Mz can do in 1s.

The idea is that if an old machine takes more than 1s to execute a DSA, then it's too much to be playable.

Post by **Paul Stevens** » Thu Apr 27, 2006 4:48 pm

demostrating that it is possible to detect an infinite loop

Oh, you may convince me but you will never
'demonstrate' such a thing. Not in your lifetime.
I was the first to verify the 6-state (that's only
six states, mind you) 'Busy Beaver' problem.
The answer was an integer with about 1700 digits.
A DM game has a few more than six states.

Post by **Zyx** » Thu Apr 27, 2006 8:07 pm

Something like 3*10^1730? ^ ^

I'm not sure I'm understanding you. By "demostrate" I assume you mean listing all the possible DSAs, trying all the the possible input for each one, and then veryfying if I can detect an infinite loop if there is any.
Otherwise, if by demostrate you mean "logical proof", I don't see why my algorithm doesn't demostrate that it is possible to detect an infinite loop in CSBwin at runtime.
I'm not trying to predict an infinite loop before execution of the code and I'm not trying to enumerate all the possible DSAs that would enter in an infinite loop.
Anyway this was just a formal question. However it does interest me, and I'm curious about your vision about it. In fact any epistemological problem always raises an interest in me.

Note to the admins: could you split this infinite loop topic from this thread please?

Post by **Paul Stevens** » Fri Apr 28, 2006 5:58 am

demostrate you mean "logical proof

No. I meant a demonstration. Don't tell how you
are going to do it. Actually do it. Your algorithm
requires running the program (machine) until its
state becomes identical to a previous state. That is
easy to say. But if this does not occur for 30 quintillion
years then it is hard to actually do it. The problem
is that you want to detect 'infinite' loops and so there
is no way to ever stop and say that you have reached
the point where you can say that the machine is NOT
going to loop.

Now it is quite sure that the machine will HAVE to loop
when it has exhausted all possible states. Say that
we have a mega-byte of data. That is 2^8000000
states. So we know that CSBwin will have to stop
before 2^8000000 steps or else it will loop forever.
So you can check your DSA by testing for only that
number of instructions.

A simple example of a machine that will NOT loop
forever.......Count a 64-bit number until you get an
overflow - then stop.

Your algorithm requires me to run the machine
until the state repeats itself so that I can say it will
loop forever. You will run it for 2^64 instructions.
At 4 Gig instructions per second it will take you
4 Gig seconds. You will not demonstrate this very
easily. But it is easy to see that it would work if
you live a very long time - 127 years or so.

Post by **Zyx** » Fri Apr 28, 2006 6:38 am

Ok, now I understand what you mean, and it seems we're not having the same goals.
I was not trying to demostrate that a DSA is in an infinite loop or not.
I was limiting myself to demostrate that it is possible to detect an infinite loop. I just need an example to prove that something exists or is possible. I don't need to implement my algorithm. I don't want to know if a given DSA actually has an infinite loop, I want to know if there is a way to eventually detect infinite loops.
Remember that you asserted there is

No way to detect infinite loops.

Haiving said that, let's suppose a moment that I really wanted to detect an infinite loop through the method I explained, thus entering your scope, since you could object that thinking about a theoretical solution is not enough: one has to check that it is implementable in terms of ressources or time consumption.
It's true that I would need to wait for the completion of the DSA before deciding if there was no infinite loop. It's true that it would be a problem to detect an infinite loop if the DSA is going to take 127 years to execute.
But this is irrelevant. We can exclude all the DSA executions that go beyond a given duration/length, (for example 100M instructions) because, infinite loop or not, they would last already for too long, and CSBwin should be interrupted anyway.
So if we keep to the ensemble of DSAs below 100M instructions (executed), this method is much more implementable. Yet useless for playing purposes since it would consume a lot of memory/data storage and/or CPU usage. I already knew that ^ ^'

Checking for a given maximum number of instructions or a maximum number of instructions would be much simplier and efficient, although you wouldn't differentiate between infinite loops or incredibly long but finite serie of instructions. This would adress the crash capturing issue, imho.

beowuuf · Post by **beowuuf** » Fri Apr 28, 2006 8:39 am

Can't you limit this to the DSA trace? Larger loops would maybe be indetectable, but surely smaller loops could be found if the engine can 'store' the last line dump to the text file and compare it to the next one - maybe break to give a warning if 10 line dumps are exactly the same? A yes/no dialogue to continue or break running the DSA?