quote:

---

Original post by Diodor

Hm, bishop_pass, why do you call Apex an ass ? I''d think that a .. person that has 6 whole posts on gamedev deserves at least some respect...

---

First of all, if Apex has only six whole posts here on GameDev, why are two of them (and the only two I have seen, and both directed at me) insulting and accusing? 33% of Apex''s comments are asslike, and 100% of the posts I have seen by him are asslike.

Apex accused me of pretending to know about logic, implying that I don''t actually know anything. And Apex accused me of talking directly out of my ass. Go back and read his posts.

I''ll get to your other points as soon as I can.

quote:

---

Original post by Diodor

So, do I need to know theorem proving theory, write a Prolog interpreter, and work my way from there to solve this ?

Or is there a graph theory analogous problem (or some other more conventional analogy) ?

Maybe using a library with functions like Unify (int predicate), IsLinked (int pred1, int pred2), Expand (int predicate) that would take care of the predicate solving part. (These examples arent making much sence I know)


How much do I need to know to
- understand the problem
- solve it ?

---

Diodor,

I am trying to do this in C. And yes, this is straight graph theory.

Imagine a graph of nodes and links between the nodes. The nodes don't have any spatial dimension, merely information regarding their connections to other nodes. Each link is categorized as a type of link, in this case, the predicate the link represents.

Let's say we are at node "Mary" and we need to find a path to node "Animal" via the path using the links: InstanceOf - SubsetOf - SubsetOf. Look at the statement below.

InstanceOf(Mary,x) & SubsetOf(x,y) & SubsetOf(y,Animal)

The variable x represents a node, but we don't know what one, other than it is connected to Mary by the InstanceOf link. The variable y is connected to x by the SubsetOf link and the variable y is also connected to the "Animal" node.

To show this as a real world example, let's say the knowledgebase has explicitly encoded that Mary is an InstanceOf a human, a teacher, a golfer and any number of other things. And let's also say the knowledgebase has explicitly encoded such things as a human is a SubsetOf a mammal, a biped, a rationalBeing, and the knowledgebase also has encoded such facts that a golfer is a SubsetOf a sportsPlayer, and on and on.

Here are the standard graph search methods: depth first, breadth first, iterative deepening, and bidirectional breadth first. I am leaning towards bidirectional breadth first with the intention of the variable bindings meeting in the middle and taking the intersection to determine if there is a connection. And I believe I have come up with a very fast way to do it with bit arrays.



Edited by - bishop_pass on June 9, 2001 12:04:13 AM

I think I see where you''re coming from, but I still think there''s an improvement in the basic model that could be made.

Zelda is a zebra, and we don''t know if it is male or female. So the database says ''I don''t know''. Got no problem with that.


But what about a can opener? Assume that there exists sufficient nodes to describe it as a machine, metal, not an animal, etc.

Is the can opener male? No (in the absolute sense).

Is the can opener female? No. (in the absolute sense)

What gender is the can opener? I don''t know (implying undetermined).

There''s not a reply that says not only is the can opener not male or female, but that the question is nonsense. You''ve got a good system for storing facts, but it doesn''t benefit from any understanding of those facts (as near as I can tell).

I think it would have to be built into the disjunctions somehow. Hmmm. I''ll give it some more thought.


Second question:
Are you working only on a search algorithm, or something to optimise the nodeset as well?

By that I mean if Zelda was the only zebra in the knowledge base, do you intend to collapse the Zelda and zebra nodes into a single node, or just use the uniqueness to transverse the nodes quickly?


JSwing

JSwing, let me try to answer and clarify everything you mentioned.

quote:

---

Original post by JSwing

Zelda is a zebra, and we don't know if it is male or female. So the database says 'I don't know'. Got no problem with that.

---

Okay, we're clear on that point.

quote:

---

But what about a can opener? Assume that there exists sufficient nodes to describe it as a machine, metal, not an animal, etc.

---

Okay, let's make sure that we are clear that there are axioms that determine Zelda is NOT a can opener, a bottle, etc. without actually having to state all the things Zelda is NOT. I think you're clear on that point also.

quote:

---

Is the can opener male? No (in the absolute sense).

Is the can opener female? No. (in the absolute sense)

What gender is the can opener? I don't know (implying undetermined).

There's not a reply that says not only is the can opener not male or female, but that the question is nonsense. You've got a good system for storing facts, but it doesn't benefit from any understanding of those facts (as near as I can tell).

---

This is a valid point. But it is not really a shortcoming of first order logic (which the above system is) as much as a shortcoming of the chosen semantics.

Instead of querying:

InstanceOf (CanOpener, Male)

and getting an answer of "No", which is correct, because a can opener cannot be a member of the set containing all males or females, you could first query:

MakesSenseFor (p, Male) & MakesSenseFor (p, CanOpener)

and, in this case, receive an answer binding the variable to the intersection of all the predicates which make sense for CanOpener and Male. Distinctly absent from that set would be Gender, thus making it clear that doing a query such as:

Gender (CanOpener, x)

is a nonsense query.

Naturally this means that there need to be added axioms which categorize and describe the nature of predicates. But then again, that is knowledge, and in the case you pointed out, sometimes desirable.

quote:

---

Second question:
Are you working only on a search algorithm, or something to optimise the nodeset as well?

By that I mean if Zelda was the only zebra in the knowledge base, do you intend to collapse the Zelda and zebra nodes into a single node, or just use the uniqueness to transverse the nodes quickly?

---

Zelda and zebra are distinct nodes and always will be. Zelda is an atom (node) which represents some particular zebra. The atom called 'zebra' is another atom (node) which represents a concept that is entirely different from Zelda. Whereas Zelda refers to one unique specimen, zebra refers to the set of all zebras. We can say things about the set which don't make sense for a unique individual. Individuals are individuals that occupy a niche in the universe, and sets are collections which have altogether different qualities and behavior. A set contains individuals, an individual is itself. The can opener in your kitchen drawer is just that. The set of all can openers is different concept.

What you are seeing here is one aspect of the unification and search process. As I alluded above, the system also binds variables to answer 'what' or 'who', in addition to yes or no. Additionally, with functional unification, which I haven't really described very much, you can also extract plans from the args in the functions, and do existential reasoning using skolem functions.





Edited by - bishop_pass on June 10, 2001 2:07:46 AM

Hi bishop_pass,

i feel you are really willing to go through that theoretical stuff so lets have a try, and stop that useless bashing on each other; it is anyway not my style. But I think there is a lot of work to do before we are clear on a formal base what your problem is, and how to solve it. I may use a lot of strange words since i do not know the exact english terminology but since they all come from latin or greek it should not matter that much. May i will learn from you step by step what their real english aequivalents are. I think it will take a long time to get things done, but i am really willing to work on this provided that we first make clear what we are talking about and what we want to achieve and how we can achieve it. What i mean is to get really common sense about what we want to do.

SO LETS GO ....

quote:

---

Original post by bishop_pass

"Given a disjunction of conjunctions of the form:

A or B or ... or J or K

where each capital letter is a conjunction of the form

m & n & ... & p & q

and each conjunct of the conjunction is of the form

m(x, y, ... z, w)

where m is a predicate and each term is either a constant or an unbound variable and (elsewhere in the database) there may be several grounded instances of m of the form

m(S, T ... V, W)

which may unify with the predicates in the disjunction.

The objective is to determine if the disjunction is true by determining if one of the disjuncts is true by determining if there exists a case of all of the conjuncts of one of the disjuncts being true through a consistent unification (binding) of the unbound variables in the conjunction with the grounded instances."

Ok, from top to here i would say your are talking about "Praedicate logic Level One". I say this because all you say is included in the PL1 "Kalkuel". The practical thing about fixing the Kalkuel to be used is that we know what we are talking about and we also fix the inference rules, aequivalence rules and what kind of normalisation can be applied to your later rule set to make them shorter and sort redundant rules out. What I mean here
with is for example:
A->B AND B->C
Using TRANSITION RULE in "->"
A->C

Normally a Kalkuel is defined on different levels:
Syntax, Meta and Semantic.

The underlying inference rules for semantic level:

(1)
Modus ponens: that is F; F -> G
---------
G

That everybody else may understand what i am talking about the
above rule says: If F is TRUE, and F implies G then G is TRUE.

(2)
Modus tollens: that is F->G; not G
-----------
not F

(3) Introduction of AND: that is F;G
-------
F and G

(4) Elemination of AND: that is F and G
-------
F

(5) For all instantion rule
(6) For each instantion rule

Like I said there are different levels and there are inference rules to the different levels. But the more important point is to distinct between syntax and semantic level. Syntax level is fairly easy here, it is very similiar to what people know from Boolean Algebra. Semantics is a little bit harder:

For all those who want to read something about it on the net the most common example to introduce it is "blocks world". There you describe a world which consist of a table and some blocks lying on the table and on each other. With PL1 you can then describe the "blocks world" and can make decisions about what the world looks like by now using inference rules.


The formal way to describe such a system is:

A PL1 Signature:
Sigma :=(Func, Praed)
Where Func is the set of functions and Praed is the set of Preadicates in the world we are talking about.

A Sigma Interpretation is:

I := (U, Func, Pread)

Where U is the universe we are talking about. That is a set which contains all individuals we have in this world. For Func and Praed look above.

What I said above is only a little bit of what must be said but i think it gives us enough input to make some decisions about the formal base.

*****************************************************************
IF WE COULD AGREE ON THAT OR SOMETHING SIMILIAR WE WOULD HAVE MADE A BIG STEP IN THE RIGHT DIRECTION.
*****************************************************************


"Also, note that any predicate may be expandable (unfolded) by replacing the predicate with its definition which is of the form:

m(x, y, ... z, w) <-> D

where D is once again a disjunction as defined above."

OK.


"The following properties would be desirable:
1) Do not waste time recursively following a blind path which possibly has no solution.
2) Do not recompute values.
3) Efficiently determine if their are grounded cases."
To do that we must make clear how we can make rules shorter, detect doubles, do normalsiation and what kind of Algebra we will use for our data structures or classe etc.


"I am leaning towards the following solution, as of yet unproven, and unimplemented: Within each conjunct, store the links to its neighboring conjuncts which can be linked by common variables. Attempt to find grounded instances of these predicates which can link these conjuncts together. If a pair of conjuncts can be linked, then there is no need to unfold the predicate. If all links within a conjunction can be linked, then the conjunction is proven true. For all links in a conjunct which cannot be linked, unfold one of the predicates and once again attempt to join all the links."

How to make an algorithm on that is secondary but i think you are on the right track.


"Anyone care to explore this problem?"
WE WILL, BUT IT WILL SURELY TAKE A LONG TIME.

The major point is now how we will use the rules, statically or dynamically and how we can simplify them and how we will make decision with what we currently know in our rule set and variables. I suggest that we will have a Universe with flexible number of Objects during runtime and a flexible rule set, may a basic one which will be extended by learning during runtime.

Can you give us some more input about how dynamic that stuff should be and if we may introduce a virtual engine to get it done . How will we describe the rules, as 4-G Tupel context free grammar ???? What should be hardcoded what should be flexible ?
The best would be a specification where you describe what you want to achieve in detail. This may sounds a little ridiciolous
but the benefit you gain from producing that paperwork at the start cannot be overestimated.


By the way:
The scientific way to explore things like what we do now is:
(1) Make sure that the problem can be fully described in a formal way so that we can evaluate the following in form of mathematical proves.

(2) Is the problem completely solveable ? If so continue with point (3). Is it solveable if we reduce it and does that help us in any way ? if so do it. If not, forget it.

(3) Classify the complexity grade of your problem. That is pure Hardcore Math. The result of that is the problem has the complexity class like:
NP - HARD
NP - COMPLETE
.. - ...

Depending on the evaluated complexity class, do it or forget it.

I think we should not do that since i am sure we will end up in getting some very practical and useful, but that is the normal way people in science work. The point is before you cannot show that there is a chance to get a result you will hardly get any money for your project. Luckily we are independent, enthusiastic and believe that we will reach our goal.



Edited by - bishop_pass on June 3, 2001 3:58:21 AM

---

cu

Peter


PS:
By the way, the photos on your web site are very impressive.


My motto since i am a late hippie area survivor:
Life is very short and there is no time for forcing and fighting my friend.
John Lennon.

phemmer,

Modes Ponens, Modes Tollens, introduction...

There are others too...

Addition:
A -> (A or B)

Double Negation:
~~A -> A

Biconditional to Conditional:
(A <-> B) -> (A -> B) & (B -> A)

All that aside, given any statement, it can be converted to a conjunction of disjunctions. Given that, any conjunction of disjunction may be converted to a set of definitions for each predicate in each disjunction. Like this:

Given the two disjunctions:

A | B | C
A | D

becomes:

A <- ~B & ~C
A <- ~D
B <- ~A & ~C
C <- ~A & ~B
D <- ~A

which becomes:

A <- (~B & ~C) | ~D
B <- ~A & ~C
C <- ~A & ~B
D <- ~A

We now have a 'definition' for each predicate.

Now, let's say we were to do a query asking if A is true. First we see if A is just plain asserted in the knowledge base. In this case, it is not. So, we must go to the definition of A, which is:

(~B & ~C) | ~D.

If both ~B and ~C are asserted, then we can say that A is true. In this case, neither is asserted. So, we see if ~D is asserted, because that would also mean A is true. In this case, ~D is not asserted either, so we need to expand the definition. In this case, there is no definition for ~B, ~C, and ~D, so we are done. The answer is "I don't know".

Now, actually there is another process occuring at the same time. And that is an attempt to see if ~A is true, because if we can show that, then we can say that A is not true and stop the attempt to show that A is true. However, in this case, there is no definition for the predicate ~A, nor an assertion saying ~A is true, so that process stops.

Our answer is: "I don't know".

During the expansion of the predicate to it's definition, we make sure that we have not expanded that same predicate with the same potential variable bindings because it is pointless to prove something by attempting to prove the same thing as a subgoal. Likely the most efficient way to test this is with hash tables.

Lastly, in regards to the scientific process, I am well aware of that. However, to pursue it in such a rigorous way would take as long as applying what is known and seeing how efficient an algorithm one can come up with. It will become clear soon enough whether the problem is tractable given the intended application of it.



Edited by - bishop_pass on June 10, 2001 5:17:10 AM

Hi bishop_pass,

first of all i think we are on the right track now. I hope the others do not mind if we discuss that kind off hardcore stuff here, but i would say we should try to make the discussion understandable for all which are really interested.

quote:

---

Original post by bishop_pass

phemmer,

"Modes Ponens, Modes Tollens, introduction...

There are others too..."
Yes, too many to list them all here in detail.

"Addition:
A -> (A or B)

Double Negation:
~~A -> A

Biconditional to Conditional:
(A <-> B) -> (A -> B) & (B -> A)"

All that aside, given any statement, it can be converted to a conjunction of disjunctions.
OK, i think we talk about the normal forms:
VNF - Negative Normal form
CNF - Conjunctive Normal Form
DNF - Disjunctive Normal Form
Am i am right ?



Given that, any conjunction of disjunction may be converted to a set of definitions for each predicate in each disjunction. Like this:

Given the two disjunctions:

A | B | C
A | D

becomes:

A <- ~B & ~C
A <- ~D
B <- ~A & ~C
C <- ~A & ~B
D <- ~A

which becomes:

A <- (~B & ~C) | ~D // OK, using OR extension rule.
B <- ~A & ~C
C <- ~A & ~B
D <- ~A

We now have a ''definition'' for each predicate."

OK, i think you are talking about the semantic level that means we have a defined universe and these variables A,B ... are expressions in that universe.


Now, let''s say we were to do a query asking if A is true. First we see if A is just plain asserted in the knowledge base. In this case, it is not. So, we must go to the definition of A, which is:

(~B & ~C) | ~D.

OK.

"If both ~B and ~C are asserted, then we can say that A is true.
Agreed.

In this case, neither is asserted.
That is something i cannot see from the abobe definitions, but i think you want to do an example and wish them to be asserted.

So, we see if ~D is asserted, because that would also mean A is true. In this case, ~D is not asserted either, so we need to expand the definition. In this case, there is no definition for ~B, ~C, and ~D, so we are done.
You mean since we are at the end of the definitions recursions level there is nothing to do.

The answer is "I don''t know".
That means you need an explicit definition of A and not A. If you do not have that you do not use the fact that you know A and make your conclusions from that.

"Now, actually there is another process occuring at the same time. And that is an attempt to see if ~A is true, because if we can show that, then we can say that A is not true and stop the attempt to show that A is true. However, in this case, there is no definition for the predicate ~A, nor an assertion saying ~A is true, so that process stops.
Our answer is: "I don''t know". "
OK, that gives me some information i was missing above.

"During the expansion of the predicate to it''s definition, we make sure that we have not expanded that same predicate with the same potential variable bindings because it is pointless to prove something by attempting to prove the same thing as a subgoal."
Thats true, we end up in infite recursion or and endless loop.


"Likely the most efficient way to test this is with hash tables."
Yes, it should be a something whith a logaritmic access time for efficency reasons.

"Lastly, in regards to the scientific process, I am well aware of that. However, to pursue it in such a rigorous way would take as long as applying what is known and seeing how efficient an algorithm one can come up with. It will become clear soon enough whether the problem is tractable given the intended application of it."
Totally agreed, since what we want to achieve is something practical. We can try to prove things afterwards as a nice excersise, but it is not neccessary since there is enough literature that tells us what we can achieve and what the pitfalls are.




Edited by - bishop_pass on June 10, 2001 5:17:10 AM

---

The only thing i am missing at the moment is the use of:
For all "\-/" and Existence Quantors in your formulas, but i think we will also find a common level here. I say this because there is another normalized form of such formulas that cleans up
those stuff; i mean Praenex formulas.

If you don''t mind i would like to agree about some more things:
First of all we should agree on how to write the different mathematical signs. Since we cannot use MathML we should use normal ASCII character set. Or do you have any better idea ?
Then we verbally should describe some test cases and try to formulate them in a syntax to be defined. That means let us create a world scenario (simple J&R, RTS, RPG) and try to describe it using our future rule set definitions. Let us instantiate some objects and look how far we come with our first model. I want to get a feeling for:
How to write rules, how to process state changes, how to use them in a game engine etc.


I am really looking forward to the further discussion ....

cu

Peter

..excuse my poor english.
... also excuse the way i write, i can''t avoid it, my ideas jump like a particle inside a particle accelerator (maybe dislexia).

...Logic! what the heck is that!, we have no such concept in our little human brain, we may define it as the expected way (by us) of doing something or something to be done; but just because we expect a defined event to be or behave in our standarized, stereotyped, and restricted by our poor understanding of what we persive, doesn''t mean that its right. We conseptualize recations to event in the way we persive those reaction, but in no means it implies that our concept of reaction must be the real reaction to that event. Human logic and therefore everything we create (such as computers) are restricted by the same factor "Event perseption".

If you want to undertand logic you must think of events not how you understand them, but rather think of being the event it self.

ordinary stuff like a > b or if a | b then such... it all depends on how you look at the problem. you can compare two factors for things the way you are used to persive "the whole" like shape color texture an so on, but I am sure there are billions of other "comparation units" out there (something still unknown like resistance to acceleration on a negative magnetic field )... and thus one cannot compare things for particularities.

If all you wan to do is a human-like ligic imitations then procede with your restricted (a > b) things.

..or change that for ( (human physical consept of a) > (human physical consept of b) ).... to get a human physical consept of the comparation. and do the same for every consept you might thing of (a) and do the same for the whole alphabet.

... heh now I lost the thread, I''m thinking of something else now, maybe when I get back i''ll post again....

masterware,

I'm not sure where you are going with that, but it is generally accepted that a rational being is able to assimilate disparate pieces of information into a quantity greater than the sum of its parts, and reject new incoming information if that information contradicts the being's current set of beliefs.

Here's an example. Bob has thus far learned (or always known) these facts about the world:

Kelly is the parent of Bill.
Kelly just got prostate cancer.

Prostate cancer is a disease of males.
Males and females are a disjoint set.
Being the mother of someone means you're the parent of someone.
Being the mother of someone means you're a female.
Being the father of someone means you're the parent of someone.
Being the father of someone means you're a male.
Being the parent of someone means you're older than that someone.
If you're older than someone, that someone is not older than you.

Given that knowledge, you should be able to reason the following:

Kelly is the father of Bill.
Kelly is male.
Kelly is not the mother of Bill.
Kelly is not the mother of anyone.
Kelly is not female.
Kelly is older than Bill.
Bill is not older than Kelly.

Having prostate cancer means you're not female.
Being the mother of someone means you're older than that someone.
Being the father of someone means you're older than that someone.
Being the mother of someone means that someone is not older than you.
Being the father of someone means that someone is not older than you.

If someone attempted to tell the agent that Kelly was the mother of Sam, the agent should reject this, or possible reevaluate what it knows. By no means should it blindly incorporate such contradictory information into it's knowledge base. Doing so would result in a knowledge base which becomes increasingly useless and irrational. So, rationality and logic are necessary to maintain knowledge about the world.





Edited by - bishop_pass on June 10, 2001 12:23:58 PM

Hey Bishop

I just wanted to say that I think what you are working on is very interesting and would definitely have an impact on the gaming world as computer power gets healthier.

I was working on some similar projects for AI in VR for the DoD a few years back and I still explore the problems with my old colleagues occasionaly. It has been a while though. Although I cannot disclose any of the specific AI logic that was used I am under no restrictions for discussing the theory behind it.

I don''t have much time right now but I will try and come back later or tommorow and post some more on the subject. But basically we had 6-way logic which I will call: Yes, No, Dont Know, Dont Care, Might Be(%) and Irrelevant.

These would be further refined depending on the importance of the agent in question. An infantryman would not need as much complexity as the commander of an aircraft carrier.

As the importance grows you need to not only understand what the agent knows but what the agent thinks he might know and what he really wants to know.

I am not much into spewing mathematical equations but I can discuss it in english Or code. I am working on a game right now and I am just learning how to use OpenGL and D3D pretty good. Then I will start working on some cool AI and could always use a healthy discussion.

Seeya
Krippy