On detecting (and aborting) infinite loops in scripts

See this as well as one other recent post where a script in an infinite loop came to Jick's notice and resulted in a player ban.

Is there something KoLmafia might do to address this?

The techniques I have used elsewhere in general won't apply because they amount to writing a monitor process. Other techniques work best if there is a fairly compact representation of the "state" of the system and/or a quick way to determine whether the state has changed.

Since the thing that bothers Jick is server hits and reducing hits has always been a KoLmafia design goal, perhaps the focus should be on visited URLs?

My first thoughts are usually never the best ideas but I am wondering if the following would be both feasible and address the issue. First these checks only happen when running a script. I suspect I can detect that easily enough at least for scripts that get run in such a way that they appear on the script MRU list If I am running a script I then record any URL submitted and the adventure count. I then check my "table" and if if the adventure count remains constant for X called URLs or the URL remains unchanged for Y I raise an error condition and let the existing mechanics abort the script.

Is this likely to make Jick happier than he is now?

I would try X and Y about 1000 each and then tune.

There is also an operator error in automated adventuring that can cause an infinite loop. I adventure, run the Summon daily deed, forget that the adventure location has changed and then blindly start auto-adventuring again. This results in effectively an infinite loop. I can imagine a similar check in automated adventuring that counts how many times the adventure loop has executed without the adventure counter changing and if that number is greater than Z, auto-adventuring aborts. I'm thinking Z as low as 10 might be reasonable.

Thoughts? Bad ideas? Won't solve the problem or solution won't scale generalize? Not as easy as I think?

I can see this being the most interesting thing for me to do between Christmas and New Years' so it might actually happen ;-)

Thanks.

let the existing mechanics abort the script

Click to expand...

It is common for scripts to capture those aborts (boolean tempValue = ash_function() leads to a script not aborting, generally), so something new would be needed, or that functionality needs to be altered somehow.

One example was a script changing the MCD between two values repeatedly (lots of server hits that Jick noticed), and I think it tried to restore HP or MP repeatedly but failed (an ignored mafia abort, but no server hit).

lostcalpolydude said:

One example was a script changing the MCD between two values repeatedly (lots of server hits that Jick noticed), and I think it tried to restore HP or MP repeatedly but failed (an ignored mafia abort, but no server hit).

Click to expand...

I've had that happen when BBB and BCA decided to both compete on what MCD-value should be set.

That said, would it be possible to check for a repetition of the exact same full URL being submitted more than, say 100 times in a row without any kind of change? Or is there a real KoL-reason for submitting the same URL so many times in a row for anything?

A few thoughts...

Locations: Mafia does not provide availability information about them. You can attempt to adventure in any WhiteWed zone from the Adventure Tab. Having a way to check for availability, such as a boolean proxy, can aid in proper loops. There is some support that would need to be built-in. For example, the Post-War Farm only has X ducks each day. After that, mafia doesn't know that you can't adventure there and will loop endlessly on it. A simple check would allow any loops to break out. It could also cull the list of locations shown on the Adventure Tab.

try..finally v abort: Any breakouts need to circumvent try..finally or you'll still just loop forever. Might be an edge case, but then again, it was an edge case that got that poor guy banned.

"I would try X and Y about 1000 each": I'd start lower around 100.

Jick: Given Skullhead's departure, I'm sure he'd love to cut down on hits to save money.

If you were crafting something in bulk, that didn't have any way to create more than one at a time, you might reasonably submit the exact same URL many times in a row, with the adventure count not changing. Perhaps the adventure count, along with the hash code of the session tally, would detect useless server hits.

Fluxxdog said:

Jick: Given Skullhead's departure, I'm sure he'd love to cut down on hits to save money.

Click to expand...

I see what you did there.

Bale said:

I see what you did there.

Click to expand...

I did something?

You're saying that you weren't referencing Skully's known propensity for spanking? That's too bad. I thought it was very amusing.

I wasn't. Now that you point it out... *o.o*

The low hanging fruit seemed to be looking at the number of iterations in auto-adventuring and aborting if iterations changed but adventures used did not. I'm cleaning that up and will probably commit in the next few days. Still deciding how to implement the script looping but have several ideas.

That doesn't seem appropriate, given that you can have skippable noncombats in the course of adventuring (even multiple times in a row).

edit: Also, free runaways and free combats exist.

Leaving combat or a choice adventure could reset whatever counter there is. That would miss the case where the same choice is encountered and walked away from, though.

OK. My initial idea that X iterations without consuming an adventure was an "error" won't work because people can do free runaways in their CCS during autoadventuring. Glad I can scrap that now rather than revert

I'm leaning towards some kind of Monitor that watches Requests. It records the URL of the request, the adventure count and some kind of hash on Inventory (and possibly even Buffs). If none of those things change for X consecutive requests then declare an Error state. For the moment this will only look at successive URLs which means an infinite loop that visits thre URLS in sequence would not be detected. My initial expectation that this would only trigger for scripts and automated adventuring is going to have to be relaxed and since the goal was to reduce hits on KoL it is TBD whether the URLs tracked are just KoL URLs or whether it is all URLs. The hard part will be reliable monitoring so I will poke at that first. Thanks.

Wouldn't low-hanging fruit be just "start throttling (by delaying them) any new requests if we made more than N requests in the past M minutes (and stop throttling once no new requests were requested for X minutes)"?

xKiv said:

Wouldn't low-hanging fruit be just "start throttling (by delaying them) any new requests if we made more than N requests in the past M minutes (and stop throttling once no new requests were requested for X minutes)"?

Click to expand...

N would have to be pretty large (and so would M, probably) to not catch "automate 400 turns, with a mood that extends 15 buffs at 10 turns per time". Unless it's okay to catch some of those cases.

How do we try to detect actual infinite loops, where we change gear twice and fail to adventure, hitting the server with at least 3 different urls (if we have outfits, but possibly with significantly more hits for the gear) on each of the loops? That's where I expect to see most loops...

How do we try to detect actual infinite loops, where we change gear twice and fail to adventure, hitting the server with at least 3 different urls

Click to expand...

You don't, at least not generally. You might find something for 3, but then there's a situation with 4 URLs, et cetera...

Detecting infinite loops is the Holy Grail of computer science - very tempting but nonexistent: You might implement some safeguards for a limited set of conditions, but there is no general solution. It's theoretically and practically impossible - you learn that in Theoretical Computer Science 101.

That should not keep you from implementing a "don't hammer the servers" safeguard - but be prepared for false positives and/or fools ingenious enough to create infinite loops nonetheless.

xKiv said:

Wouldn't low-hanging fruit be just "start throttling (by delaying them) any new requests if we made more than N requests in the past M minutes (and stop throttling once no new requests were requested for X minutes)"?

Click to expand...

Could be, but the problem I am interested in solving has morphed into "reduce or eliminate server hits on KoL that are caused by user or script error that result in infinite loops". While it might help Jick if such loops were slowed down the same could be said if Jick asked every KoLmafia user to run from a 386 class PC over dial up My success metric is "hits" not "hits per unit time".

Theraze said:

How do we try to detect actual infinite loops, where we change gear twice and fail to adventure, hitting the server with at least 3 different urls (if we have outfits, but possibly with significantly more hits for the gear) on each of the loops? That's where I expect to see most loops...

Click to expand...

My anecdotal evidence suggests otherwise. What we really want is to detect that an identical sequence of length X has occurred Y times and if Y is big enough declare the sequence an infinite loop. It is much easier to conceptualize and debug for X = 1. If it turns out that there are enough cases where X needs to be greater than 1 that can be phase two.

P.S. - As noted detecting infinite loops always and in general is never going to happen so the more modest goal is to detect and eliminate some of the more common ones.

Working on my own experiences, my infinite loops have basically been one of two types...
One, single event that didn't actually work, and usually mafia filtered it out. Trying to adventure in a locked zone that mafia blocks (or doesn't), trying to use an item that I don't have, trying to adventure when I'm out of adventures so mafia already stops it, etc. The more common one here is when BatBrain decides to use the short calculator. It plans out its strategy, tries to execute it... and fails, because the short calculator always seems to fail on bosses. Doesn't matter to BatBrain, it will keep trying. Ten thousand times, if I start automation before going to sleep. This is easy to fix by disabling using the short calculator, but inevitably it slips back into the list of potential items and gets stuck again.
Two, multiple events with multiple server hits, sometimes with a cost to me - the player - and sometimes not. This is the sort of thing where BCA accidentally burned through 18 million meat once, 50 meat at a time, by changing gear and healing me over and over and over until all my meat was gone. Fixed the bug after that, but still... that was a lot of server hits. Probably over a million, with the gear and restoration figured in. That's very bad, both for meat storage and server hits.