cmpsc441 - exam 2 notes

GAME: Well DEFINED game... nigga the fuck is chang talking about
	Like chess
	- 2 person game, well defined rules
	- Chess players
		- 1950's: Shanon -> Father of Information Theory *very important nigga.. probably not a nigga tho*
			- Came up with Game Theory: Principles w/ Modern game playing
		- 1953: Turing:
			- 1996 IBM DEEP BLUE: Deep Blue vs. Kastrov .. Deep Blue lost (Philly)
			- 1997 2nd Match (NY) ... Deep Blue won
			- 1998 3rd Match (Kastrov was pissed) .. IBM didn't wanna have a rematch
				Kastrov was pissed still
			- IBM WATSON - Literally won jeapordy
	- Game playing
		- application of search
			- state - board configuration
			- action - legal moves
			- goal - winning configuration
			- heuristic - scoring function (produces % chance of winning)
				- c*#Queens + c*#Kings .. etc.
		- Path is not important
	- Search Tree: Tic Tac Toe
		[ ][ ][ ]
		[ ][ ][ ]  Init-state
		[ ][ ][ ]
			|
			| Next level is all possible "my" moves
			[]
		 /     \
	        This level is possible opponent moves
		The Goal is to: Search this path to pick the best move that will make it most likely to win

	MIN MAX ALGORITHM (Shanon 1949):
		- Look ahead in the game tree to depth of N (N-Ply)
		- Evaluate score (heuristic) of each leaf node
	ex. 2 ply
				[] <-- current state (my turn)
			/    |   \
		 []-5    []1   []7 <-- Possible my Turns (pick one to maximize your score)
		/  \    /  \  /  \
   	  []   []  []  [] []  []  <-- Adversary's move (minmizing your score)
Heur: -3   -5  2   1   7   8
	Oppenent will try to minimize your score so you have to choose a path that
	will minimize the damage he can do .. by minimizing

	The silly thing is ... it gets inefficient the more legal moves you can make
	If the branching factor is like.. 20.. at depth of 10 .. you have 20^10 leaves
		and then you just kill yourself
			... soo you speed that shit up by making the tree smaller.. but ya can't do that now can ya
	so need.. Algorithm Alpha Beta Prunning

ALPHA BETA PRUNNING -> Optimization of min-max by reducing # of leaves to evaluate
	ex ..
			[]2
		  /    \
		[]2    1[]
	  /   \    /  \
	[]    []  []  []
	2      7  1    7
	So you're guarenteed at least 2 after evaluating the first branch there..
		so you evaluate that the next leaf would be 1 .. you just don't evalute the sibling node to it
		so you just don't go there since you can get at least 2
	Actual Algorithm
		[] alpha = -infinity---> update to 2, beta= infinity ---> 2, infinity
	  /
	[] -infinity, infinity<-- update to 2---> -infinity, 2
  /
[]2

	 basically, if you find a beta value smaller than your alpha value, you stop that branch
		- you have to evalute at LEAST the first branch

	Minmax normal = O(b^d) #leaves ... minmax prunning = O(b^(d/2))

_____________________________LOGIC_______________________________________________

LOGIC IN AI
	Neural Network is taking of again now because we now have the computational power for it
		- it originally was shit because of the lack of computational power
	Logic is a FORMAL LANGUAGE FOR KNOWLEDGE REPRESENTATION
		- Because it is a language it has a syntax and semantics
		- Syntax = Grammar - what are Legal expressions
		- Sematnics = Meanings - what syntatically legal statement is trying to convey
		- Proof System = Way to manipulate synatically correct expression to extract another
	ex. Robot w/ Sensors (Roomba)
			- Sensed umbrella and dirt dropping ---> conclusion: raining

TYPES OF LOGIC
	Propositional Logic:
	First-Order Logic:

	Prolog: Logic Language
		remember append from scheme? (look up sorce code for it... 2 lazy 2 type)
		Prolog for append:
			append([],Y,Y). <-- ((null? ls1) ls2)
			append([A|X],Y,[A|Z]) :-append(X,Y,Z)
            *                **************
			*(cons (car ls1)* (append cdr ls1) ls2)


PROPOSITONAL LOGIC
	* Syntax and Semantics
		ex. a = (3 + 4) * 5;
		    _   ____________
		left val 	right val

		ex2. Chomsky "Colorless green ideas sleep furiously"
				Synatically correct (grammar)... symanticly.. it just doesn't work
	Term:
		sentence: Syntactically correct expressions
			(Well formed Formula) - WFF
		Syntax:
			Sentence -->  Atomic | Complex
			Atomic --> "true" | "false" | symbol
				This is called "Backus Naur Form"
			Symbol --> P | Q | R | ...
			Complex --> ~Sentence | (Sentence) |  (Sentence /\ sentense) |
						 (Sentence \/ Sentence)| (Sentense -> sentence) |
						 (Sentence <-> Sentence)
			What does this actually mean tho?
				1. true / false are sentences
				2. Prop. variable is sentence
				3. If phi && Sci are sentenses, then so are (~phi), (phi /\ sci), (phi \/ sci)... and so on
				if we want to get rid of () we have to get fancy and define precidence
		Precidence:
			~ /\ \/ -> <->
			High <----- Low
			ex. (A \/ (B /\ C))  == A \/ B /\ C
				((A/\B) -> (C\/D)) : A/\B --> C\/D
			ex. A /\ B /\ C <-- Doesn't matter where () go (works with \/ too)
		Semantics:
			What the Given sentence means in the real world

			Meaning of a sentence is either True or False
				read as t / f .... "TRUE" is literal, t just represents it

		Interpretation:
			ex. A /\ B /\ C : t or f?
				- depends on what A B C means *INTERPREATION*
					assigning t / f to each variable
				  Interpretation is how to figure out the assignment of each variables
				ex. cont.
				 A = T
				 B = T    this is one possible assignment
				 C = F     where A /\ B /\ C = F
			Semenatics of a sentence depend on the interpretation
	The question comes...
			Is the sentence true (hold) given the interpretation?
			T = "HOLD" F = "FAILS"
	LOGICIAN NOTATION
		holds(phi,i): phi is true if the interpretation i
		fails(phi,i): phi is false in interpretation i
	- Semenatic rules
		1.  holds(true, i) for all i
		    fails(false, i) for all i
		2.  holds(~phi, i) iff fails(phi, i)  : NEGATION
	    3.  holds(phi\/sci, i) iff holds(phi, i) or holds(sci, i) : DISJUNCTION
		4.  holds(phi/\sci, i) iff holds(phi, i) and holds(sci, i): CONJECTION
		5.  holds(phi->sci, i) iff fails(phi, i) or holds(sci, i): IMPL.
		6. phi <-> sci =- (phi -> sci) /\ (sci -> phi)
                          (~phi \/ sci) /\ (~sci \/ phi)
		7. holds(P, i) iff i(p) = t
		   fails(P, i) iff i(p) = f
		AND THUS BIRTHS TRUTHTABLES
	TERMS:
		1. VALID: phi is valid iff for all interpretations holds(phi, i)
			ex. ~p \/ p,
		2. SATISFIABLE: Phi is satisfiable iff there Exsists an interpretation where holds(phi, i)
		3. UNSATISFIABLE: Phi is unsatisfiable iff for all interpretations fails(phi, i)
			ex. ~p /\ p
		GIVEN PHI, to find iout if PHI is VALID, SATISFIABLE or UNSATISFIABLE use a Truth Table

    Boolean satisfiability prob.
		ex. if it rains, tom because sad
			if tom is sad, mary will buy me dinner
			john is sad
			today is rainy
		Will I get free dinner?
			yes
		p->q
		q->r
		s
		p
	  .....   p = T, P->Q = T, Q = T, Q->R = T, R=T
		R = Goal
	Instead of truth tables we use inference (above)

TERM: Entailment
	- Given a knowledge base (everything in the KB is true) and a sentence S
		- if every interpretation that satisfy KB also satisfies S
		- then KB entails S
			or S is entailed from KB
			or S follow KB

	UNDER WORLD LOGIC:
		We have to convert every sentence in the World to an interpretation (KB)
			- The knowledge base will entail a new fact
				- The new fact goes back to real world sentences
				- The undworld is where we work doing logic
	Instead of using a truth table to do gay shit we use proof
	PROOF
		ex. ax^2 + bx + c = 0 is x = (-b +/- sqrt(b^2 - 4ac))/2
		.. you can use algebra to show that
	PROOF SYSTEM:
		- Sound: Inference algorith is sound if it derives only entailed sentence
		- Complete - inference algorithm is complete if it can derive any entailed sentence
	INFERENCE RULE:
		-  Natural Deduction
			1) a -> b
			   a
			:. b (MODUS PONENS)
			2) a -> b
			  !b
			:. !a (MODUS TOLENS)
			3) a /\ b
			 :. a  (AND ELIMINATION)
			4) a
			   b
			 :. a /\ b (AND INTRODUCTION)
	- You can prove if individual things are true (so it's sound

		- RESOLUTION
		 a \/ b
		!a \/ c
	  .: b \/ c

		- CONTRAINT of RESOLUTION -> All sentences in (CNF)
			cnf = conjunctive normal form (conjunctions of disjunctions)
		- CNF EX.
			(!A \/ B \/ C) /\ (A \/ !B) /\ (A \/ D)       ----> T
				clause         clause         clause
			 since it returns true, we know each clause is true
						~~~~CONVERT TO CNF~~~
						 1. Eliminate <->  :: a <-> b ~~ (a->b)/\(b->a)
						 2. Eliminate ->   :: a->b ~~ !a\/b
						 3. Move NOTs inward :: !(!a) ~ a  || demorgans
                   ~~~~~~AT THIS POINT WE ONLY HAVE \/ /\ !(to symbols)~~~~~~~
						 4. Distribute /\ over \/ :: a\/(b/\c) ~~ (a\/b)/\(a\/c)
					~~~~~ DONE ~~~~~~~~ DONE ~~~~~~~~~~ DONE ~~~~~~~~~~ DONE ~~~~~~~~
		ex.
			(A \/ B) -> (C -> D)

			!(A \/ B) \/ (!C \/ D)

			(!A /\ !B) \/ (!C \/ D)

			(!A \/ (!C \/ D)) /\ (!B \/ (!C \/ D))

			(!A \/ !C \/ D) /\ (!B \/ !C \/ D)
	 PROVING KB Entails a (RESOLUTION)
		KB /\ !a

		ex.
			KB
			  A -> B :: ~A\/B \---> B
			  A      ::  A    /     |
			PROVE       ~B --------CONTRADICTION
			  B						Therefore B is true

		ex. GIVEN-> P\/Q , P->R. Q->R     PROVE-> R
			1. P\/Q
			2. !P \/ Q
			3. !Q \/ R
			4. !R  ~~~ !Q
			5. Q\/R ~~~~ 1 and 2
			6. P\/R ~~~~1 and 3
            7. R  ~~~~ 3 and 5
			8. FALSE 4 7
			THEREFORE: R is true

		ex. 1. I like one or more of 3: Paul, George, John
			2. If I like Paul and not George then I also like John
			3. I either like George and John or I like Neither
			4. If I like George, I also like Paul
			Q. Do I like all 3?
				CONVERT IT ALL!!!!
			1. (P \/ G \/ J)
			2. (P/\!G) -> J
			3. (G /\ J) \/ (!G /\ !J)
			4. G -> P
			Q. (P /\ G /\ J)?
				CONVERT TO CNF
			1. P \/ G \/ J
			2. ~P \/ G \/ J
			3. (J\/!G) /\ (G\/!J) *note, both must be true
			4. ~G \/ P
			!Q. ~P\/~G\/~J
					~~AND IT BEGINS~~~
			5. J \/ !G    3
			6. !J \/ G    3
			7. G \/ J    5 6
			8. !J \/ P   4 5
			9. G         4 7
		   10. J         5 9
		   11. P         8 9
		   12. !J \/ !P  !Q 9
		   13. ~P   CONTRADICTION
			Q is TRUE!

		RESOLUTION!!!!! when you're doing it.. try to use terms for what you're trying to contradict
		(ie.. Look at ex #2 above.. just start doing shit with R)
FIRST ORDER LOGIC
	- Proposition logic limited expressiveness ..
		ex. I <3 John
			I <3 Ringo
			I <3 Paul
			I <3 George
		.. you have to literally list everything
			very unfortunate when you're using a lot of variables

	ex. If an animal has feathers, then it is a bird...
				F -> B
		is a hummingbird a bird?
			feathers(animals) -> birds(animals)
						or
			feathers(x) -> birds(x), [For-All]x[in]ANIMALS

	[There-Exists]x[in]PEOPLE [ Sibling(John,x) -> Mother(mother-of(John), x) ]
		analizing each thing
			[There-Exists] <- Quantifiers
			x <- var
			[in]PEOPLE <- universe
			Sibling <- Predicate (relation)
			John <- Literal
			Mother <- Predicate
			mother-of <- Function

	- First oder logic basically just adds a predicate
	- Syntax:
		Terms and Constants (Literals): Name of a particular Object
			ex. John, Paul, Chair, Chair.2 etc...
				(usually upercalse)
		Variable: A placeholder that can be bound to a literal
			ex. a, x , y , z, etc.
		Function: Another way to name an object
			ex. left-Leg(John) ... John's left leg
				left-leg(mother-of(x)) .. someone's mother's left hand
		Sentence:
			Atomic Sentence: Predicates and Equality
				ex. Bird(x)
					NatNum(10)
					Above(x,b)
				  (Predicates)
				ex. mother-of(John) = mother-of(sister-of(John)
				  (EQuality)
			Complex Sentence: Quantifier and Operators
				Quantifiers: [For All], [There Exists] w/ Sentence
				Operators: phi \/ psy
						   ph /\ psy .. you see wher this is going... phi and psy are sentences

			EX:
				John is a smart student
				Student(John) /\ Smart(John)
			EX:
				Cats are animals
				[For-All)x[in]UNIVERSE, Cat(x) -> Animal(x)
			EX:
				One's mother is one's female parent
				[For-All]x,m[in]PEOPLE, mother-of(x)=m <-> parent(m,x) /\ female(m)
			EX:
				Sibling is another child of one's parent
				[For-All]x,y[in]PEOPLE, Sibling(x,y) <-> x !=y /\ [There exists]p(Parent(P,x) /\ Parent(P,y))
			EX:
				Everyone loves somebody
				[For-All]x[There-Exists]y Loves(x,y)
			Ex.
				Nobody Loves John
				[ForAll]x(!(Loves(x,John)))
						or
				![There-Exists]x(Loves(x,John))
			EX.
				Whoever has a father has a mother
				[For-All]z[There-Exists]x,y Father(x,z) /\ Mother(y,z)
	- Interpretation:
		ex. "All Cars are not created equal" <-- is this true?
			[For-All]c !(sameQual(c)) <-- no, some cars are exactly the same.. ergo, created equal
			 "Not all cars are created equal" <- this is true
			!([For-All]c sameQual(c))
		For good interpreations.. we need......
			1. UNIVERSE: Set of objects
			2. CONSTANT: Literal, represents an object in the Universe, (ie. giving a name to an object)
			3. VARIABLE: represents nothing on its own in universe.. but it can be bound to anything in universe
			4. PREDICATE: Relation, a truth value
			5. EQUALITY: self explanitory
			6. QUANTIFIERS: Binds a variable to object in Universe ([There-Exists],[For-All])
	PROOF BY RESOLUTION FEFUTATION
		* In 1st order logic: Clausal Form
									also called prenex normal for, conjuctions of dijunctions no quantifiers

	CONVERTING propositional into CNF
		1. Eliminate <->
		2. Eliminate ->
		3. Move ~ inwards
		note: Careful about quantifiers  with the ~
			~[For All] --> [ThereExisists] ~
		4. Rename variables to avoid using same variables for different qualifiers
			ex. [ForAll x] P(x) \/ [ThereExists x] Q(x)
				---> [ForAll x] P(x) \/ [ThereExists y] Q(y)
		5. Skolemization (remove [ThereExists])
			ex. [ThereExists y] Loves(John, y)
				---> Loves(John, Mary)
			ex. [ForAll x][ThereExists y] Loves(x, y)
				---> [ForAll x] Loves(x, Raymond) ... Wait this changes the meaning...
								SO INSTEAD
				---> [ForAll x] Loves(x, F(x)) where F=Loved
								janky.. but same meaning :)
			If [ThereExists] stands alone, you can just slap in a literal.. if not..
					(inside [forAll]) you need a function
		6. At this point, All variables are quantified by [forAll] and vars are all different
			ex. ([ForAll x] P(x)) \/ ([ForAll y] Q(y)) \/ ([ForAll z] R(z))
				---> [ForAll x][ForAll y][ForAll z](P(x) \/ Q(y) \/ R(z))
				---> [ForAll x,y,z](P(x) \/ Q(y) \/ R(z))
			DROP UNIVERSAL QUANTIFIERS!!! pretty much implied here
		7. Distribute \/ over /\
			ex. Everyone who loves all animals is loved by someone
	[step 0]	[ForAll x] (([ForAll y]  Animals(y) -> Loves(x,y)) -> ([ThereExists y] Loves(y,x)))
    [step 1/2] 	[ForAll x] (([ForAll y] ~Animals(y) \/ Loves(x,y)) -> ([ThereExists y] Loves(y,x)))
	[step 3]	[ForAll x] (~([ForAll y] ~Animals(y) \/ Loves(x,y)) \/ ([ThereExists y] Loves(y,x)))
	[step 3]	[ForAll x] (([ThereExists y] Animals(y) /\ ~Loves(x,y)) \/ ([ThereExists y] Loves(y,x)))
	[step 4]	[ForAll x] (([ThereExists y] Animals(y) /\ ~Loves(x,y)) \/ ([ThereExists z] Loves(z, x)))
	[step 5]    [ForAll x] ((Animals(F(x)) /\ ~Loves(x, F(x))) \/ Loves(G(x), x))
	[step 6]    (Animals(F(x)) /\ ~Loves(x,F(x))) \/ Loves(G(x), x)
	[step 7]    (Animals(F(x) \/ Loves(G(x), x) /\ (~Loves(x,F(x)) \/ Loves(G(x),x))
		Synatically corrected after dropped quantifiers.. since you're assuming it exists.. not needed to represent

	Then.. we can slap it in a proof
	PROOF BY RESOLUTION REFUTATION
		- KB => Everything to PNF
		- Q => ~Q
		- Apply Resolution until contradiction

	EXAMPLE:
		1. Everyone Who Loves All Animals is Loved by Someone
		2. Anyone who kills an animal is loved by no one
		3. Jack Loves all animals
		4. Either Jack or Vuriosity Killed the Cat, Whos name is tuna
		5. All Cats are Animals
		Q. Curiosity killed cat

		1. [ForAll x] (([ForAll y] Animal(y) -> Loves(x,y)) -> ([ThereExists y] Loves (y,x)))
		2. [ForAll x] (([ThereExists y]Animal(y) /\ kill(x,y)) -> ([ForAll y] ~Loves(y,x)))
		3. [ForAll x] (Animal(x) -> Loves(Jack, x))
		4. Kills(Jack,Tuna) \/ Kills(Curiosity, Tuna)    where Cat(tuna)
		5. [ForAll x] Cat(x) -> animal(x)
		Q. Kills(Curiosity, Tuna)

		[note: 1 and 2 are the same statement. it's just joined by an /\ so it can be separated]
		1. ((Animals(F(x)) \/ Loves(G(x), x))
		2. (~Loves(x, F(x)) \/ Loves(G(x),x)))
		3. ~Animal(y) \/ ~Kills(x,y)  \/ ~Loves(z,x)
		4. ~Animal(x) \/ Loves(Jack, x)
		5. Kills(Jack, Tuna) \/ Kills(Curiosity, Tuna)
		6. Cat(tuna)
		7. ~Cat(x) \/ Animal(x)
		Q. Kills(Curiosity, Tuna)
        8. ~Kills(Curiosity, Tuna)
	 	9. kills(Jack, Tuna) *5 and 8*
	   10. Animal(Tuna) *6 and 7*
	   11. Loves(Jack, Tuna) *4 and 10*
	   12. Loves(G(Jack), Jack) *2 and 11... 2: x = Jack, F(x) = Tuna)
	   13. ~Animal(y) \/ ~Kills(Tuna, y) *3 and 11 ... z = jack, x = tuna*
	   14. ~Animal(Tuna) \/ ~Loves(z, Jack) *3 and 9 .. x=Jack, y = Tuna*
	   15. ~Loves(z,Jack) *10 and 14*
	   16 FALSE *12 15* .. Therefore curosity killed the cat



SKOLEMIZATION
	- ues to remove [There Exists]
	- Substitute a new name of each existentially quantiied variable
	ex. [ThereExists] P(x) --> P(Fred)
		- Basically giving an X a name
	ex. [ThereExists x][ThereExists y] P(x,y)
		---> P(Fred, Mary) .. can't do P(Fred, Fred)
								*Because x and y are different
	ex.
		[ThereExists x] P(x) /\ Q(x) => P(Fred) /\ Q(Fred)
	ex.
		[ThereExists y][ForAll x]Loves(x,y) => [ForAll x]Loves(x, Raymond)
		this is ot the same if Forall and ThereExists are flipped...
				but
		[ForAll x][ThereExists y] Loves(x,y) --> [ForAll x]Loves(x. lovedby(x))

	EXAMPLE:

		[ForAll x] ( [thereExists] R(x,y) /\ [ForAll y] -> ([ThereExists y] R(x,y) /\ P))
		1. <-> *done*
		2. -> === [ForAll x] (~([ThereExists y]R(x,y) /\ [ForAll y] ~S(x,y)) \/ ~([ThereExistsx y] R(x,y) /\ p))
		3. ~ === [ForAll x](([ForAll y] ~R(x,y) \/ [ThereExists y] S(x,y)) \/ ([ForAll y] ~R(x,y) \/ ~P))
		4. rename vars - [ForAll x](([ForAll y] ~R(x,y) \/ [ThereExists w] S(x,w)) \/ ([ForAll z] ~R(x,z) \/ ~P)
		5. remove [ThereExists]
			  [ForAll x] ( [ForAll y] ~R(x,y) \/ S(x, Q(x)) \/ [ForAll z] ~R(x,y) \/ ~P)
		6. move for all to front and remove
				~R(x,y) \/ S(s,Q(x)) \/ ~R(x,z) \/ ~P
			DONE!

UNIFICATION
	: Process to compute the substitution that makes two sentense to resolve
	* UNIFIERS: list of substiutions
	ex. Knows(John, x)
		Knows(John, Mary)
			if x represents Mary.. these sentences are the same.. process of finding it is unification

	ex.
		Knows(John, x)
		Knows(y, Bill)
		UNIFIERS: x = bill , y = John
		therefore, same sentence

	ex.
		Knows(John, x)
		Knows(x, Bill) .... can this be unified?
			no.. you can't do that
	ex. ~Knows(John, x) \/ Hates(John, x)
		Knows(John, Jim)
			x = Jim  .. : Hates(John, Jim)

	ex.  Knows (John, x)
		 knows(y, z)
			y = john, x = z  <---------- while all are valid.. this is best choice "Most General Unifier"
				or
			y = john, x = john, z = john
				or
			y = john, x = mary, z = mary
			 *abunch are possible here*

EX. Resolution shit
1	~P(w) \/ Q(w)
2	~Q(y) \/ S(y)
3	P(x) \/ R(x)
4	~R(z) \/ S(z)
5 Q: ~S(A) <----------------------- Actually S(A) .. bu you know.. resolution
6 unify: z = A .. ~R(A) (4 and 5)
7.unify y = A  .. ~Q(A) (2 and 5)
8.unify w = A .. ~P(A) (1 and 7)
9.unify x = A .. R(A) (3 and 8)
10.  FAIL: 6 and 9 .. unified w = a
11. Therefore, S(A) = True