Apr 1999 CO230: Cognitive Science (Question 3)

	Problems can be represented as sets of facts and rules, or graphs. To solve the problems, reasoning can be applied on the facts and rules, or the graphs can be searched.
(a)	There are four reasoning methods that can be applied on propositional and predicate logic. Name and use symbols and connectives to show the four reasoning methods.	[4]
	Modus Ponen [ p _^ ( p ® q) ] ® ( p ®q) Modus Tollen [ p _^ ( ~q ® ~p) ] ® ( p ®q) Contrapositive ( p ® q) ] º ( ~q ® ~p) Hypothetical Syllogism (Transitivity) [( p ® q )_^ ( q ® r)] ® (p ®r)
(b)	There are basically two types of search techniques: exhaustive search and heuristic search.
	(i) Compare exhaustive and heuristic searches.	[4]
	Scope of Searching : Exhaustive search searches the entire problem space in order to find a solution ; However, heuristic search does not search the entire problem space. It searches the paths that lead to higher probability of finding a solution. Effectiveness : If there is a solution, exhaustive search guarantees to find it as it does not miss any area of the problem space; However heuristic search does not guarantee and even if it finds a solution, the solution might be suboptimal because it may miss some areas of the problem space. Situations : Even thought heuristic search does not guarantee a solution, it has advantages over exhaustive search when The cost of performing exhaustive search is very high. Hence, exhaustive search is prohibited and heuristic search is used instead. There may not be an exact solution due to ambiguities in problem statement. Hence why bother to use exhaustive search? Heuristic search will be a better choice.
	(ii) state and define the two types of search classified under exhaustive search.	[4]
	Depth First Search It searches along a branch of the problem state to its full vertical length, and then continues to search another branch. The order of branches to be searched is predetermined. For example : from left to right. Breadth First Search It searches all nodes at the same horizontal level before it continues to search nodes at the next level.
(c)	Describe and give an example of state space.	[4]
	It is the area that is searched to find a solution for a problem. It consists of nodes each represents a problem status and branches each represent a path.
(d)	In the few decades of computing history, it is only in the last few years where scientists have implemented a computer system that managed to defeat a world class chess master. If the game is staged again today, can we guarantee that the computer system will once again defeat the chess master? Explain your answer.	[4]
	No, we cannot. This is based on an assumption that Heuristic Search is used in this system. This is because the cost of implementing exhaustive search is prohibitive, as there may be vast number of paths at each stage of the chess game and each move triggers even more complicated calculations. Heuristic search does not guarantee a solution. This means when the system plays chess against a chess master, it may lose to the master if it fails to find a solution.