Resolution - Refutation Proofs

Watch Video

Knowledge Based Systems: Logic and Deduction

Watch Video

Searching Game Trees

In combinatorial game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position.


The diagram shows the first two levels, or ply, in the game tree for tic-tac-toe. We consider all the rotations and reflections of positions as being equivalent, so the first player has three choices of move: in the centre, at the edge, or in the corner. The second player has two choices for the reply if the first player played in the centre, otherwise five choices. And so on.

The number of leaf nodes in the complete game tree is called the game tree complexity. It is the number of possible different ways the game can be played. The game tree complexity for tic-tac-toe is 26,830.

Game trees are important in artificial intelligence because one way to pick the best move in a game is to search the game tree using the minimax algorithm or its variants. The game tree for tic-tac-toe is easily searchable, but the complete game trees for larger games like chess are much too large to search. Instead, a chess-playing program searches a partial game tree: typically as many ply from the current position as it can search in the time available.

Two-person games can also be represented as and-or trees. For the first player to win a game, there must exist a winning move for all moves of the second player. This is represented in the and-or tree by using disjunction to represent the first player's alternative moves and using conjunction to represent all of the second player's moves.

Watch Video

Problem Reduction Search: AND/OR Graphs

Sometimes problems only seem hard to solve. A hard problem may be one that can be reduced to a number of simple problems...and, when each of the simple problems is solved, then the hard problem has been solved. This is the basic intuition behind the method of problem reduction. We will have much more to say about this method of search when we cover problem solving and planning in the second half of the course. At this point, our goal is simply to introduce you to this type of search and illustrate the way in which it differs from state space search.

The typical problem that is used to illustrate problem reduction search is the Tower of Hanoi problem because this problem has a very elegant solution using this method. The story that is typically quoted to describe the Tower of Hanoi problem describes the specific problem faced by the priests of Brahmah. Just in case you didn't decide to read this story, the gist of it is that 64 size ordered disks occupy one of 3 pegs and must be transferred to one of the other pegs. But, only one disk can be moved at a time; and a larger disk may never be placed on a smaller disk.

Rather than deal with the 64 disk problem faced by the priests, we will consider only three disks...the minimum required to make the problem mildly interesting and useful for our purpose here...namely to illustrate problem reduction search. The figure below shows the state space associated with a 3-disk Tower of Hanoi Problem. The problem involves moving from a state where the disks are stacked on one of the pegs and moving them so that they end up stacked on a different peg. In this case, we will consider the state at the top of the figure the starting state. In this case all three disks are on the left-most peg. And we will consider the state at the bottom right to be the goal state. In this state the three disks are now all stacked on the right-most peg.

Watch Video

Heuristic Search A* and Beyond

Heuristic algorithm or simply a heuristic is an algorithm that gives up finding the optimal solution for an improvement in run time.

Two fundamental goals in computer science are finding algorithms with provably good run times and with provably good or optimal solution quality. A heuristic is an algorithm that abandons one or both of these goals; for example, it usually finds pretty good solutions, but there is no proof the solutions could not get arbitrarily bad; or it usually runs reasonably quickly, but there is no argument that this will always be the case.

For instance, say you are packing odd-shaped items into a box. Finding a perfect solution is a hard problem: there is essentially no way to do it without trying every possible way of packing them. What most people do, then, is "put the largest items in first, then fit the smaller items into the spaces left around them." This will not necessarily be perfect packing, but it will usually give a packing that is pretty good. It is an example of a heuristic solution.

Many commercial anti-virus scanners use heuristic signatures to look for specific attributes and characteristics for detecting viruses and other forms of malware.

Judea Pearl states that heuristic methods are based upon intelligent search strategies for computer problem solving, using several alternative approaches.

Often, one can find specially crafted problem instances where the heuristic will in fact produce very bad results or run very slowly; however, such pathological instances might never occur in practice because of their special structure. Therefore, the use of heuristics is very common in real world implementations. For many practical problems, a heuristic algorithm may be the only way to get good solutions in a reasonable amount of time. There is a class of general heuristic strategies called metaheuristics, which often use randomized search for example. They can be applied to a wide range of problems, but good performance is never guaranteed.

Watch Video

Artificial Intelligence:Informed State Space Search

Watch Video

Artificial Intelligence-Searching with Costs

Watch Video

Artificial Intelligence-Problem Solving by Search

Watch Video

Artificial Intelligence

Watch Video