Simply put, does anyone have any experience with this? Especially in MUSHclient?
I've read up on the topic a bit and they seem like the solution I have - a lengthy process (goes beyond 5s+) that is capable of returning intermediate results. Since it is lengthy, I don't want it to block my triggers with a simple execution. Rather, I want it to process in the background while my triggers fire, and if a trigger needs one of those intermediate results, it can just request it.
The entire topic is new to me, so I'm kind of lost thus far.. any help people could offer is appreciated. I've been reading up on co-routines, but most uses of it are complicated in the sense that I'm not sure what it is achieving. :/
I think what you really want though for background processing are true threads. You can launch a new thread in Python fairly easily using the threading module which also has synchronization classes, so the intermediate (and final) results can be stored in Python variables available to the triggers.
The only important proviso is that the world object becomes invalid around the time the main thread returns from the script so you shouldn't try and use it in the second thread.
It's kind of late at night atm so if this doesn't make sense I will produce demonstration code after I've gotten some sleep :)
Actually, in theory their should be a way around the world object being lost. You simply create another instance of it in the other thread. Mind you, that may not be as simple as making a new object type variable = world, it might require setting up a wrapper from the linker table used by external applications (i.e. mushclient.tlb), then connecting to the client via that. It kind of depends on how Mushclient hands over the "world" functions. If they are part of a class/object, then making a copy of the object before the main script exits should means that you still have access to them, from that copy. I have no idea if that will work though, or for that matter, if there is a way in Windows to make it *not* work. At worst, trying to do something like:
new object myhdl
myhdl = world
Or what ever the commands are in Python to create an empty object container, then copy an existing one into it, will simply fail.
The problem is that you can copy the Python side of the world object, but because it's COM you don't have access to the C++ side of it and Something happens after execution passes back to MUSHClient that causes at least part of the world object to be invalidated... so some things work, some cause MUSHClient to segfault :P
Since I haven't made a list of what works and what doesn't (and under what circumstances that might change), I try and avoid doing anything with it. As it happens there is no great need to as there are work arounds.
That example is built around having a Tkinter event loop as the second thread but is easily generalized.
I've since discovered the memory leak mentioned in there is avoidable if you call the global poll() function as a timer function rather than using Send-To-Script.
ie:
def poll(name=None):
global apps
for app in apps:
app.poll()
## I use Python 2.5.1 which has the with statement in __future__
## Python < 2.5 needs to replace the:
## with <lock>:
## <code>
## blocks with:
## try:
## <lock>.acquire()
## <code>
## finally:
## <lock>.release()
## The following line must be before any other Python statements in the file:
from __future__ import with_statement
import threading
_qcode = []
_qlock = threading.RLock()
def TimerPoll(name):
global _qcode, _qlock
while len(_qcode):
with _qlock:
code, locals = _qcode.pop(0)
exec code in globals(), locals
def TimerQueue(code, locals = {}):
global _qcode, _qlock
with _qlock:
_qcode.append((code, locals))
Then we can convert from:
def some_function_with_lots_of_processing():
data = []
world.Note("Started!")
time.sleep(2.0) # busy, busy
update_interim_results(data)
time.sleep(3.0) # so much hard work
update_final_results(data)
def update_interim_results():
world.Note("Interim Results Available!")
def update_final_results():
world.Note("Job's Done!")
To:
def actual_sfwlop():
data = []
TimerQueue("world.Note(\"Started!\")")
time.sleep(2.0) # busy, busy
TimerQueue("update_interim_results(data)", { 'data': data[:] }) # making shallow copy to avoid sync and validity issues
time.sleep(3.0) # so much hard work
TimerQueue("update_final_results(data)", locals())
def update_interim_results(data):
world.Note("Interim Results Available! %s" % repr(data))
def update_final_results(data):
world.Note("Job's Done! %s" % repr(data))
def sfwlop():
threading.Thread(target=actual_sfwlop).start()
If a shallow copy is not enough to get the job done, you can use the synchronization decorator:
from __future__ import with_statement
import functools, threading, types
def synchronized(p = None):
def wrapping(f):
@functools.wraps(f)
def wrapper(*p, **kw):
with lock:
return f(*p, **kw)
return wrapper
if 'acquire' in dir(p) and 'release' in dir(p):
lock = p
return wrapping
else:
lock = threading.RLock()
if isinstance(p, types.FunctionType):
return wrapping(p)
if isinstance(p, types.ClassType) or isinstance(p, object):
for k in dir(p):
if k not in p.__dict__:
continue
f = p.__dict__[k]
if not isinstance(f, types.FunctionType):
continue
setattr(p, k, wrapping(f))
return p
return wrapping
You can use it as a function decorator:
@synchronized
def f():
thread_name = threading.currentThread().getName()
print "Only one thread can be in this function at any time! That thread is currently: %s" % thread_name
time.sleep(2.0)
print "%s leaving!" % thread_name
Or as a class decorator, the lock is shared by all of the methods:
class C:
def f():
thread_name = threading.currentThread().getName()
print "Only one thread can be in this function at any time! That thread is currently: %s" % thread_name
time.sleep(2.0)
print "%s leaving!" % thread_name
C = synchronized(C) # have to wait for Python 2.6 for the @syntax :(
This code is fairly robust, the only problem I've seen is sometimes Bad Things Happen if you recompile the script while a child thread is still executing.
I totally forgot about this thread, heh. I eventually found out I indeed needed threads and I got quite far, until I ran into a little issue with the background processing I wanted to do - the GIL made what I wanted to happen still freeze up my MUSHclient which kind of got me stuck. If anyone here is any good at rewriting that specific part for me in C (Isthiriel maybe? *flutter*) I'd be really grateful. I could paste all the code here, but frankly it is so damn huge and complex it would be easier explained in an IM conversation.
Also, pyrex is a (mostly)python-to-c translator that can give you c-speed with (slightly non-standard) python syntax.
EDIT[2]:
Also, also, the GIL is unique to the CPython implementation. Neither IronPython nor Jython have it.
The other workaround is to start another python process and talk to it with sockets or one of the rpc systems that are part of Python's standard library.
EDIT[3]:
... which, being recognized as a Standard Solution, has been encapsulated in a module (http://www.parallelpython.com/).
I've read up on the topic a bit and they seem like the solution I have - a lengthy process (goes beyond 5s+) that is capable of returning intermediate results. Since it is lengthy, I don't want it to block my triggers with a simple execution.
My examples there, in Lua, show how a lengthy sequence can pause for both time intervals (eg. 5 seconds) or input from the MUD (eg. waiting for some sort of result).
I'll email you the relevant code in a few minutes. Thanks for wanting to look at it, I really appreciate it.
However, while I know the GIL is only a part of the CPython implementation.. isn't COM and thus a MUSHclient implementation only possible with CPython?
I have given seperate applications and such a thought, but given the fact I work a lot with references to certain objects that I'd rather not copy back and forth (we're potentially talking thousands of objects during the lengthy calculation process) since the overhead would be extreme, and performance is already a problem in its current shape.
Nick Gammon:
Heh, that is not really the purpose. It is a rewrite of the core of my curing system in one of the IRE muds, but the 700+ triggers that move the system aren't stuff I look forward to porting much. Due to the fact I have used a silly hybrid of OOP and simple procedural programming, it will be difficult enough to make all the changes I have in mind in Python. Additionally, Lua doesn't have the built-in support for set objects (no order, no duplicates) that the entire idea is founded on.
Good point. It turns out neither of them can be used as WSH languages :(
Re: Lua Sets, you can roll your own with metatables.
I'm not sure what you're trying to acheive? (Possibly because I'm not familiar with the IRE affliction system.)
You're implementing a system that, when told a certain skill has been used on your character, it will learn what afflictions that skill caused by progressively attempting to cure the afflictions it knows about? (There's no way to find out what you're currently afflicted with?)
The problem with your set simplification algorithm isn't something that can be solved by reimplementing in C. The complexity is expanding combinatorially, which comes under the heading "O(NP)". C would, ideally, make it 3-4 times faster than it currently is, which means that you might be able to add an extra affliction before you reach the same slowdown.
Well, being able to squeeze that bit of time out of it, and more importantly managing to keep the trigger-processing of mushclient fast and speedy while my (currently 1 processor-core) system doesn't freeze in executing triggers like my prototype tends to freeze when trying to execute new input while my background thread is running.
And yes, there is a method to find out what I need, however, that takes an equilibrium balance of half a second.. and with certain afflictions on top of it, that time can increase quite a bit. Perfecting the tracking means that I have more time to build a proper offense, especially given the fact that I am in a class who can lose a lot of headway by wasting 1-2 seconds to diagnose every few rounds.
Of course, I will diagnose when stuff gets really problematic, but in the last year there have been a lot of skills added that end up in guessing or assuming a certain affliction has happened, but having five or six twenty-choice afflictions before a horrible slow-down is a must, especially when you take in the unfortunate event of people teaming or plain group-battles.
Hmm. I think I'm going to have to play one of the IRE muds before I understand the problem :(
My naive solution would be to just track one set with all of the affliction you could possibly be afflicted with and every time you attempt to cure something it is removed from the set (that is: succeed at curing or discover you don't have the affliction; attempt to cure and fail means it moves to the I-know-I-have-this-affliction set).
Or, an improvement over that would be to use a dictionary (whose keys form a set anyway) with the value for a particular affliction-key is how many skills have been used that might cause that affliction (either by incrementing for each skill that might cause it, or by adding a percentage that relates to how likely that skill is to give you that affliction -- for example injuring-a-limb-skill might have a 25% chance of afflicting each limb while blow-to-the-head skill might have a 5% chance of blindness and 95% chance of concussion; so in the first case you add 0.25 to each value for the limb keys and in the second you add 0.05 to blindness and 0.95 to concussion ... if that makes sense?), so you can then pull the keys/values as tuples and reorder them on severity and the likelihood of being afflicted and then attempt to cure them in order.
The problem that I see with the way you're trying is if skill A afflicts you with one of (l, j, k) and skill B afflicts you with one of (l, k, m) and you cure k did you remove the effects of A? or B? (or both?)
A commented game transcript would probably help me :(
> Or, an improvement over that would be to use a dictionary
> (whose keys form a set anyway) with the value for a
> particular affliction-key is how many skills have been
> used that might cause that affliction (either by
> incrementing for each skill that might cause it, or by
> adding a percentage that relates to how likely that skill > is to give you that affliction .......
Problem with that is that relationships are lost between the afflictions. Some methods of curing can only be performed when you do not have other afflictions, and a 10% chance for that affliction does not properly represent the choice to make. Rspecially once you start dealing with overlapping possible afflictions (which you'll need to remove at a later stage). For example, skill A gives either x, y, or z, so you increase the chances on those, but later on, you do have a hard time determining what x and y their probability should be if said afflictions turns out to be z. Your earlier example suffers from the same dilemma: the longer you go on without a 'fresh start', the more polluted and unreliable your information becomes. (I already tried percentages to death before I arrived at this solution, heh.)
> The problem that I see with the way you're trying is if
> skill A afflicts you with one of (l, j, k) and skill B
> afflicts you with one of (l, k, m) and you cure k did you
> remove the effects of A? or B? (or both?)
Nah, I don't have that problem. For simplicity, I'll show you the output of the prototype I sent you in my email, minus some of the debugging spam.
Welcome to the affliction tester!
Try 'help' for basic instructions.
=>> import (<l, k, m>, <l, k, j>)
Interpreted set succesfully.
=>> show
Current afflictions ( 2 ):
11623696:set(['k', 'm', 'l']) (unknown range)
11623632:set(['k', 'j', 'l']) (unknown range)
=>> help identify
Forcefully identify a range into an affliction. Syntax: identify ID AFFLICTION. Or substitute ID with 'some' for the best automatic choice.
=>> identify some k
Performing identification of None into 'k'.
=>> show
Current afflictions ( 2 ):
k
11623632:set(['j', 'm', 'l']) (unknown range)
=>> discard k
Affliction 'k' removed.
This affliction stuck for 80.506 seconds.
=>> show
Current afflictions ( 1 ):
11623632:set(['j', 'm', 'l']) (unknown range)
Succesfully curing something means that you are certain you have it, thus you can identify one of the afflictions as being k. The others are adjusted so any left-over possibilities are not lost. After identification, the k option can be removed.
> A commented game transcript would probably help me :(
Well, I included the log above. A game transcript isn't really useful since I'm primarily dabbling in the higher abstractions of writing a curing system - getting uncertain afflictions, tracking them properly, being able to remove the precise affliction or all mentionings of it - without losing information that can help to better prioritize curing.
Anyhow, I hope I am not confusing you too much and I am very grateful for any (coding) insights/assistance you can offer.
Quote: Additionally, Lua doesn't have the built-in support for set objects (no order, no duplicates) that the entire idea is founded on.
Actually, it most definitely does. :-) And no need to go into metatables, either...
myset = {}
myset[key] = true -- we just added key to the set
myset[key2] = nil -- we just removed key2 from the set
-- test for membership:
if myset[key] then
print("the key is in the set")
end
Additionally, Lua doesn't have the built-in support for set objects ...
I am not trying to hijack this thread into "why don't you use Lua", however given that you want to use Python because it supports sets, and you also want to use coroutines, and this doesn't work (it says earlier this "freezes MUSHclient"), then I am trying to propose an alternative that will work.
Lua tables do indeed, as David says, provide a simple way of testing for membership of an item, with no duplicates. Plus, the example from the Programming In Lua (pil) shows how you might do intersections and unions.
I seem to remember working on an affliction system earlier. I used a simple table to remember which afflictions you currently had (effectively a set of afflictions).
Then a second (ordered) table gave the desired cure order (and, for each affliction, what the cure was).
So, you go through the desired cure order in sequence, and for each one, you test for membership in the table of afflictions you actually have, and if you have that one, you cure it first.
This may not necessarily apply to your case, however the code looked neat enough.
Thank you for your efforts, Nick, and I certainly don't consider it as a 'just use Lua' statement. :) I use Lua for various simple scripts so I can basically muck my way around with it, but given the amount of code that is still okay (just the innards need a lot of mucking about) I am only considering a language switch as a very, very last choice.
Also, the system you are suggesting is a simplified version of what I already have in my current system. The new reworking of the innards is a radical change I am making exactly because the simpler approach isn't giving me all the flexibility and information I want to have.
Python coroutines don't freeze MUSHclient; Python threads can cause MUSHclient to lose some of its responsiveness. MUSHclient only freezes if the main script thread blocks while waiting for the worker thread to free a lock.
(The responsiveness is lost due in equal parts to the GIL, the kind-of-sort-of-semi-random-round-robin scheduling algorithm and the varying granularity of context switches... I found out recently that Python's BDFL prefers fork().)
The art of Worstje's system is that it is tracking afflictions you potentially have and inferring what you do have without stopping to 'diagnose' the exact afflictions.
That's what I feel too, or I'd not be working on it still. :D
Only problem is that my mathematical skills are not good enough to switch from the semi-bruteforcing algorythm I use right now to a logical deducting that would have an O(n)-like execution time. I've been trying to bang my head at it for various months, showed it to some really brainy people and they couldn't figure out either whether there'd be a simpler and less cpu- and memory-intensive way to calculate it.
Do you have a quick way of explaining what exactly you're trying to solve? Is there one of the posts here that explains it particularly well? I can take a crack at reorganizing the algorithm if you want...
Not really; the easiest way for me would be to send you my prototype and show you the code (well over 1400 lines of code, where around 900 lines are the actual code being tested). I think I have some emails written in english that also discuss it, but it is all pretty specific.
First, a short notation explanation. Suppose you have the following affliction-set: (a, b, <c, d>, <c, e, f>). That would mean you have four afflictions: a, b, either c or d, and either c, e or f.
Now, when someone uses a skill at me which I can not exactly pinpoint the affliction of, I add a new affliction range (denoted by <>) with the proper afflictions. Against some classes, this is more a rule than an exception, where a problem props up: the data becomes superfluous and unmanagable to make sensible decisions off. Take the following example, where you'll be asking yourself: 'do I have a broken leg?'
I'll be simplifying the terms left leg, right arm etc to two letter equivalents (LA, RA, LL, RL) since it types a bit easier. Suppose you end up with the following knowledge: you have three broken limbs.
Three limbs. Simple logic says that this must equate to:
(<LA, RA>, <LL, RL>, <LA, RA, LL, RL>)
...thus, one arm, one leg, and one something else. However, we can take it even further:
(<LA, RA>, <LL, RL>, <LA, RL>)
In other words, we have narrowed it down greatly - reducing 12 total choices to only 6 possible choices. This makes the data more uniform and makes it easier to make decisions based on the knowledge we have. The more choices we have and the harder it is to tell how much of the information is useful, and how much is excessive and just grew while the system was in operation.
A big problem lies in making this uniform - no special handling for special afflictions. The various affliction-ranges theoretically offer you all the information you need (the logic doesn't need special information to know left leg and right leg are both legs, since they're both in the sets). The only method at which I have managed this so far is an optimized version of a brute force approach. It essentially goes like this:
1. Take the current afflictionset and calculate all possible results.
2. Now evaluate one of the affliction ranges in this afflictionset to a certain choice (eg <a, b, c> is made to be <a>), and calculate all possible results again.
3. If the resultsets are identical (represented by a frozenset of a frozenset of strings for easy comparison), we have deduced that this particular choice is spurious and unneeded.
Of course, the possible simplifications using this algorythm can change, so I try to evaluate into the most often occurring choices first since those have a bigger chance of matching. Results can still differ through various runs though (sets lack an order to iterate through them).
Additionally, the code also has to take chain-reactions into account (partially because the code has different classes for an afflictionrange and an absolutely 'set in stone' affliction, which need to be converted once only one choice remains). Also, due to illusions and false information, it can happen that you do not actually have an affliction because all possible choices disappeared at once.
Anyhow, the brute forcing mentioned above is what I am doing now. Anything simpler and less cpu- and memory-intensive is what I'm looking for.
OK, to try to understand this better can we introduce a bit more terminology?
Am I correct in thinking we have three main things here ...
Some sort of attack, poison, disease that causes a problem to the target.
For example:
A swing of the mace might break one or more limbs.
A poison might make you blind and silence you
A disease might reduce your stamina and cause damage over time
Am I also correct in thinking you don't necessarily know what something does? So for example, if you previously had no broken limbs, and someone hits you with a mace, and now you have a broken limb, you conclude the mace caused it?
In a more complicated case if a poison blinds and silences you, but you are already silenced, then you can't be sure if the receipt of the poison would have silenced you, or not, had you not been silenced already.
I suspect this is unknowable, unless you happen to be perfectly healthy when you receive a certain sort of attack.
The effects of attacks.
These are the individual things that can be wrong with you. For example:
Broken left leg, broken right leg
Broken left arm, broken right arm
Silenced
Blind
Mad
Reduced stamina
Damage occuring over time
There could be a many-to-many relationship here, I suppose, so that multiple poisons might send you mad, and an individual poison might cause two effects.
The cures for effects.
I presume you can take various cures, for example:
A banana reduces hunger
A spell cures a broken limb
A herb cures madness
A potion cures blindness
I also presume you can have a many-to-many relationship again? Eg. a certain herb cures both madness and blindess.
I also presume there is an optimal cure sequence, for example if you cannot eat, then that has to be cured before you can eat herbs to cure other things. Alternatively, you want to cure first the things that are causing the most damage.
The idea of illusions makes it harder. Is there a way of knowing, at some time, whether or not you have been tricked by an illusion?
If you definitely find out at some point, you might have to move an attack->effect set into a holding area, to be accepted or rejected as real or an illusion at a later time.
If it turned out to be an illusion, you discard it, if it turned out to be real, you merge it into your "known" area.
I already have a rudimentary - actually, it's pretty good - system in place to deal with illusions. However, if one sneaks through the code needs to be able to handle situations which end up as being impossible (an affliction running out of choices rather than resolving). That's about as far as the illusionhandling in the affliction-tracker goes.
Three limbs. Simple logic says that this must equate to:
(<LA, RA>, <LL, RL>, <LA, RA, LL, RL>)
...thus, one arm, one leg, and one something else. However, we can take it even further:
(<LA, RA>, <LL, RL>, <LA, RL>)
I don't believe it is as simple as you make it out to be, or maybe I'm missing an assumption you make. The expressions you wrote are not in fact logically equivalent: if you treat the first as:
(LA|RA|LL|RL) & (LA|RA|LL|RL) & (LA|RA|LL|RL)
and the second as:
(LA|RA) & (LL|RL) & (LA|RA|LL|RL)
and the third as:
(LA|RA) & (LL|RL) & (LA|RL)
you will note that the first expression is true when just LA is true but neither the second nor the third expression are true. In your simplifications, you seem to want to be saying that something from each of the three afflictions has to be true in the end of the day.
If that's what you mean to say, what it comes down to is that you not only have those three disjunctive guesses, but one of each must be true. In making the "simple logical simplifications" you described, you are in fact assuming this fact about each affliction being distinct.
Except what you wrote does not correspond to this assumption, because the simplified version is satisfied by just LA and LL being true, and all others being false.
So I'd like to hear more about the simplifications you made and how you justify them, i.e. what assumptions you are holding as you make those simplifications.
The thing with the afflictionsets is that you are guaranteed to have one affliction from each subset.
In the case of the broken limbs:
(<ll rl la ra>, <ll rl la ra>, <ll rl la ra>,)
We're saying that we currently have three skills affecting us, each of which could be afflicting any limb, so the possible actual afflictions (which we won't know until we diagnose) are:
1. (ll, rl, la) # no duplicates
2. (ll, rl, ra)
3. (ll, la, rl) # except these are sets, so this is identical to 1
4. (ll, la, ra)
5. (ll, ra, rl) # identical to 2
6. (ll, ra, la) # identical to 4
7. (rl, ll, la) # identical to 1
8. (rl, ll, ra) # identical to 2
9. (rl, la, ll) # identical to 1
10. (rl, la, ra)
11. (rl, ra, ll) # identical to 2
12. (rl, ra, la) # identical to 10
Now, we just spun out 12 possible choices from the original afflictionset and 8 of them were meaningless (and hence unnecessary work).
So the idea is to simplify the original afflictionset, preserving the 4 unique cases and reducing the number of duplicate possibilities.
If we look at: (<ll rl>, <la ra>, <ll, ra>) you'll notice the possibilities are:
1. (ll, la, ra)
2. (ll, ra ... can't choose from the last subset
3. (rl, la, ll)
4. (rl, la, ra)
5. (rl, ra, ll)
6. (rl, ra, ... can't choose again
We get the same 4 unique cases and do a bit less than half the work.
Now, knowing these are limbs and that three of four of them are broken we can enumerate the four unique cases by knowing that 4C3 is 4 and produce them by subtracting a limb from the set of four (that is the four unique cases are given by taking the set of four limbs and subtracting one limb in each) BUT Worstje is trying to make this as general as possible, so it doesn't know you have four limbs.
The problem is that expanding all possible choices is an O(NP) operation (factorial in fact, so worse than exponential order :( ). On the other hand, you have something like three billion cycles to play with.
Most skills apparently only give you a few possible afflictions, so you may need 20+ of them before the algorithm soaks up all of those cycles and is no longer useful. On the other hand there are some skills that can give you up to twenty possible afflictions and four skills like that make the algorithm useless (because it takes >10 seconds to come back with an answer, by which time the fight is nearly over).
... or at least that's the way I understand it.
Because this is trying to be an inference engine that can determine what afflictions you are certain to have from what afflictions you might have, and I think you need to specify which limb you are going to fix when curing, counting potentially broken limbs won't work :(
Though, having said that, I think being afflicted with (<ll, rl>, <ll, blind>, blind) might be a problem since (due to the arrival order) the possibilities are (rl, ll, blind) and (ll, blind). (I suppose a simpler example would be (<ra la>, ra) since you can't have your right arm doubly broken a second ra is a noop so your la isn't necessarily broken.)
Crap, too many responses and too little time for me to reply. :D
Isthiriel pretty much hit the bullseye, except that it is a condition for my class that any choices that are already there for certain are removed, since they're not valid. E.g. (<LA, RA>, LA) is simplified into (<RA>, LA) and then (RA, LA).
Sadly I'm going to be out for the weekend, so the long and intensive replies to all I have just read may take a while.. thanks for all the input though, everyone. It is really appreciated.
Quote: The thing with the afflictionsets is that you are guaranteed to have one affliction from each subset.
I think you mean to say something stronger: what you described after that was actually that you are not only guaranteed to have one from each, but you must have a distinct affliction from each. In other words, it's not possible to pick the same affliction twice.
Now again, I don't know the relevant world that well, but it seems to me that assumption is too strong. I can picture several cases where two different attacks might give you the same affliction, like one could give you <LA, RA> and the other could give you <LA, LL>. And then, you could have gotten the left arm broken from both attacks. It would in this case be an error to "simplify" this to <LA,RA>, <LL>. But perhaps this is not true: perhaps it is in fact guaranteed that you will have a unique affliction given by each attack.
I believe you were pointing this out in this paragraph:
Quote: Though, having said that, I think being afflicted with (<ll, rl>, <ll, blind>, blind) might be a problem since (due to the arrival order) the possibilities are (rl, ll, blind) and (ll, blind). (I suppose a simpler example would be (<ra la>, ra) since you can't have your right arm doubly broken a second ra is a noop so your la isn't necessarily broken.)
Cases such as these need to be handled in some sane way before you can start simplifying the more complex expressions. If <ra la>, <ra> can be reduced to merely <ra>, then as I said it is incorrect to conclude that <ra la ll rl>x3 will be reduced to the sets given: it could just as easily be <ra>x3 (where the last two would be "noops").
Perhaps the easiest way to state my question is that I am looking for a precise definition of the semantics of the affliction set. What does it mean to have a list of possible afflictions; what does it mean when there is overlap in those sets; does order matter in the list of possible afflictions; etc.
I think skills are guaranteed to give you one new affliction if it is possible for them to do so (that is, you don't already have all of the afflictions that they can give you). Otherwise this whole exercise would be done better (and much, much easier) with probabilities. (Four limb-breaking attacks becomes a 1.5625% chance of only one limb broken, 9.375% chance of all four broken, 32.8125% chance of two broken and 56.25% chance of three broken with a 68.36% chance of any particular limb being broken. Which took only a couple of minutes to calculate by hand.)
So, for (<ra la>, <ra la>) it doesn't matter which affliction the first skill gives you, the second will give you the other affliction.
OTOH, for (<ra la>, ra) if the first skill gives you la, then both arms are broken. If it gives you ra then the second skill doesn't do anything.
Quote: So, for (<ra la>, <ra la>) it doesn't matter which affliction the first skill gives you, the second will give you the other affliction.
OTOH, for (<ra la>, ra) if the first skill gives you la, then both arms are broken. If it gives you ra then the second skill doesn't do anything.
If those are truly the operating assumptions then that changes things, thanks for clearing that up. Those assumptions do surprise me, though: it suggests that when I attack you with some skill, the code looks at the afflictions you have, and gives you whatever you don't already have. That seems odd: I would have thought that first an affliction would be chosen, and then it would be applied, potentially resulting in a noop.
Well, anyhow, I'll give it a think. There's probably a much better way of approaching the problem that doesn't involve testing every possible combination...
Like I said, "I think". I haven't played the mud(s) in question so I can't be sure. In the case of broken limbs it makes sense (because you aren't going to bother attempting to multiply disable a limb), poisons less so. Spells... well, that's magic.
Personally, I would have coded afflictions to be less random, so a certain poison might give you nausea, blurred vision, blindness, confusion, bleeding from the mouth and nose and finally death. Resisting part of the effects would mean not receiving the later afflictions, but if you get blurred vision you already have nausea. A specific expensive magical cure would remove the poison and its effects (or an even more expensive general magical cure), otherwise you're patching symptoms. (And the fun here would be guessing the poison from the symptoms :D particularly if you have a high resistance and a lot of poisons start with nausea.)
First of all, sorry for the belated reply. I've been rather busy the last few days and didn't see a chance to reply before this.
It seems your discussion has already properly determined the semantics of the afflictionsets. It is CORRECT that if skills can give an affliction, you are SURE to have a new added affliction. I imagine the code at the MUDs side indeed goes like 'check for non-present afflicton'-'give non-present affliction'.
The information inside an afflictionset should be 'sensible' at all times. This means that (<RL, LL>, LL) or even the more elaborate (<RL, LL, BLIND>, <RL, LL>, LL) are situations that will not exist - as soon as the final LL is added to the set the entire set is evaluated and the afflictionset is simplified into what would be (RL, LL) and (BLIND, RL, LL).
A simple count of limbs would indeed not be sufficient for all the various reasons given - the various problems and intricacies of this model were easiest to explain using limbs (due to simplicity and not being mud-specific) but in practice limbs are not what I'm concerned with - it is the larger afflictionsets where a single <> can contain 10 to 20 items.
I am very aware that there is no 'one' simplification of a set, since multiple afflictionsets can give the same resultset depending on the road wandered. (<a, b>, <b, c>) and (<a, c>, <b, c>) being the simplest example of that, but if one looks at the 3x<RL, LL, LA, RA>, you can also find several simplifications that are different, but essentially mean the same thing when you look at all the resultsets. This is NOT a problem for me - I merely want the afflictionsets to become as simple (=devoid of possible choices) as possible, and the precise simplification I end up with does not matter for me.
I think that addressed most stuff about the afflictionset idea I came up with. Now, balances. It's a word that we use to denote the time from curing in a certain way until we can cure again. For example:
> eat herbX
You eat some herbX.
Your clarity of mind returns. <-- yay, afflictionY cured.
..wait..wait..some seconds later..
The herb has cleared your system.
This is the point at which I can eat another herb and have the herb cure something. If I'd eat another herb BEFORE the previous herb cleared my system, it would be a dud and not work. 'Having herbbalance' would thus mean that I'd be able to eat a herb at a certain point. This concept prevents people from spamming cures and adds more of a tactical approach to curing, since you can't just spam all possible cures at all times. Hell, it is worse - for quite a few balances it is so that trying to use the balance (eat a herb while not ready to eat one again) would increase the time it'd take to regain the balance, slowing down ones curing considerably. Salve curing (used to cure limbs) in my mud is even a bit more complex - the time to regain the balance depends on the salve used and on top of that, some cures simply fail if another cure isn't done first: curing of the limbs.
Anyhow, I deviate again. The balances themselves do not matter for this problem (I merely mentioned them to clear something up I think) nor does the precise order in which stuff is cured. I've got plenty of experience and working code for that already. The afflictionsets are the ones I need to get simplified.
Premature thanks come in the paragraph, but hey, actually getting this discussion going means a lot to me already given the fact that what I'm doing is kind of over the top for 99% of the people I play my mud with.
Thanks for everything, Isthiriel, Nick Gammon and David Haley. It's very much appreciated. :)
Given the discussion I had with Isthiriel, I don't understand how this:
(<RL, LL>, LL)
is simplified to this:
(RL, LL)
when the choice comes before the non-choice. However, I would be perfectly happy to take this:
(LL, <RL,LL>)
and simplify to this:
(LL, RL)
The problem is that I thought that the attacks were ordered chronologically, and that new attacks were guaranteed to add a new affliction if possible. In that case, the first attack above could yield LL, and the second attack would also yield LL (but not actually do anything). But in the second option (the one I understand), the first attack has to yield LL, in which case the second one has to yield RL because LL wouldn't be a new affliction.
So given this, I'd need to know the following:
- when does ordering of attacks (affliction sets) matter?
- what exactly does the ordering mean?
- is there any kind of chronological ordering of afflictions/attacks?
Sets do not have an order. It is why I am calling them sets and not lists. :)
(<RL, LL>, LL) is inherently redundant - you can not have your left leg broken twice. Therefore, (<RL>, LL) remains. But a 'choice' of one affliction essentially means that must be the only choice you can take, thus you are certain to have RL. A <> notation of one element is logically equivalent to the element without the <> around it.
I'll work out both scenario's, and for the matter of these examples I'll pretend the order -does- matter.
(<LL, RL>, LL): First we find out that someone breaks a leg. For example, you try to do something and find out you are limping which means that one of the two legs is broken. Then someone attacks you, and you get a message that your left leg breaks. Your left leg doesn't break twice, so the previous broken leg had to be de right leg. Thus follows (RL, LL).
(LL, <LL, RL>): I have broken my left leg, and I am aware of it. But before I can heal it, someone attacks me again and I get a message like "Your leg shrivels and withers away beneath you." which doesn't allow me to pinpoint which leg it is. But because I knew the other was already broken and that the attack WILL BE effective, it must be the right leg. Thus follows (LL, RL).
While the notation itself tries to avoid any thoughts about ordering, of course afflictions will come in a certain order. However, the beauty is that as time passes by, you learn more and more of your situation.
You eat a herbZ, but nothing is cured. Stuff cured by herbZ can be removed as choices.
You eat a herbZ, and 'slickness' is cured. If 'slickness' was available as a choice, we can identify one of the choices and push left over other choices with this option to keep logical integrity. Additionally, the 'slickness' being cured may imply we do not have another ailment because the herb is garantueed to cure paralysis before slickness. Thus if paralysis is an option in any choice, we can remove it there. Similar for if we actually think we have paralysis.
The system is self-correcting and in the process, allows the code to approximate a humans way of thinking by going for the most obvious things and striping away the things that are irrelevant. Even -if- the affliction tracker gets faulty information through illusions and such, it should deal with it as gracefully as possible and hopefully end up figuring out things are not possible without ever having tried to cure them. (Of course, this is not the only way I guard against illusions, but in case all other stuff fails, this is very important. Sadly illusions are becoming more undetectable and foolproofy by the day.)
Summary:
- when does ordering of attacks (affliction sets) matter?
In a given set, it does not. In live action, it should be self-correcting.
- what exactly does the ordering mean?
Nothing besides the fact that it makes it more readable that using a typewriter and writing all the words through eachother. :)
- is there any kind of chronological ordering of afflictions/attacks?
In the tracker itself: no. It just represents the CURRENT situation, which can be adjusted as more information becomes available.
I think a lot of things make sense to me now... It seems that order is in fact crucial to improving the algorithm, because you never are presented with one giant set all at once that you have to simplify. You maintain a set of possibilities, that you refine over time as more information come in. (I don't like the term simplify because it suggests operating on a snapshot rather than an incremental change.) I think it's very confusing to talk about not having ordering because the algorithm really does operate chronologically: just look at how you explained it, for example.
Anyhow, I think the key in improving your algorithm will be in realizing that you only need to do work on the incrementals: there is no need to reprocess the entire set when new information comes in. You should only have to look at how that new information affects the existing uncertainties.
Have you given any thought to representing these as decision trees? It seems that could be promising. But again I need to think about this more, especially now that (I think) I have a better understanding of what exactly you mean with your notation and what exactly the problem is...
Crap, forgot to reply after I did some initial research on decision trees. I concluded that I have zero idea on how to implement those in this case.
I think I know how I can improve my current algorithm (Isthiriel has seen it) to exclude fruitless research that has been done in the past using lists of already-simplified-afflictionchoices, but it wouldn't be the prettiest thing on this side of the globe.
I appreciate any ideas you may have on this, David. :)
So I'm totally double-posting. Sue me, but my curiousity is getting the better of me. :) That and I hate it when I am stuck.
David, did you happen to come to any new realizations? And could you perhaps give me a good reference on decision trees (wikipedia isn't all that helpful to me) or perhaps an example of what you mean?
Sorry for the big delay here -- I was away in Mexico for the break and just got back fairly recently; I haven't really had much time to think about all this. :-)
What you're trying to do is, I believe, a non-trivial problem in AI research, but I also believe it has been solved before. Basically it is the field of information update on a partial world view: you only know a subset of what is true, and worse, your knowledge is disjunctive; but, as new information comes in you can adjust your world view.
I have to context-switch back into what I was thinking before leaving to give you a good answer on what I meant by decision trees used in this context. But basically a decision tree is the following:
- At every node, you have a list of possibilities, i.e., decisions to make.
- Following a possibility (i.e. making a decision) puts you in a new decision node.
- After having exhausted the possibilities (i.e. running out of decisions) you know for sure where you are.
I believe that the book "AI: A Modern Approach" by Russell & Norvig provides a pretty good coverage of decision trees, but perhaps not in the correct context.
Again sorry for the delay and lack of useful information, give me a couple of days to think about this. It's a fairly fun puzzle to work through. :-)
Just mumbling here: it occurs to me that this kind of problem is very similar to classic problems solved by knowledge representation using modal logic. If you look up "Muddy Children" (probably on Wikipedia) you might see what I'm talking about. The idea is quite similar; you have a disjunctive view of the world, but as information comes in you can eliminate possibilities. That is almost exactly what you are trying to do here. I'll pursue this track and see what happens...
It's quite allright, I've been stuck and to be honest, I'm a horrible magician.. uhm, mathematician. They're my biggest obstacle in my Computer Science course, so I really appreciate any help I can get.
I just took a look at the Muddy Children problem (link: http://tcw2.ppsw.rug.nl/mas/LOK/lwb/muddy.html) and I think I can reason that one out in a rather simple way, although I admit I didn't go beyond k=3 since I'm tired and haven't got paper in front of me. I'd assume the mathematical side would be solvable using mathematical induction.. but I'm getting sidetracked. :D
I can see the comparison between the muddy children problem and my problem. I see two issues from the top of my head though.. first being that in unfortunate cases where the data is not proper (illusion snuck through or I didn't track a cure), it shouldn't fail. Second being that there is no real 'base' to start with nor a final 'gotcha' moment, but a continuously changing situation, of which the fact that an affliction is not certain to be able to calculated. But I'm talking in circles now I think, so I'm going to bed...
I hope Mexico was fun, andI hope you'll have a happy new year and all that stuff, too!