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

Programming Paradigms

A programming paradigm is a fundamental style of computer programming. (Compare with a methodology, which is a style of solving specific software engineering problems).

A programming language can support multiple paradigms. For example programs written in C++ or Object Pascal can be purely procedural, or purely object-oriented, or contain elements of both paradigms. Software designers and programmers decide how to use those paradigm elements.

Lecture 1

In object-oriented programming, programmers can think of a program as a collection of interacting objects, while in functional programming a program can be thought of as a sequence of stateless function evaluations. When programming computers or systems with many processors, process-oriented programming allows programmers to think about applications as sets of concurrent processes acting upon logically shared data structures.

Just as different groups in software engineering advocate different methodologies, different programming languages advocate different programming paradigms. Some languages are designed to support one particular paradigm (Smalltalk supports object-oriented programming, Haskell supports functional programming), while other programming languages support multiple paradigms (such as Object Pascal, C++, C#, Visual Basic, Common Lisp, Scheme, Python, Ruby and Oz).

Many programming paradigms are as well known for what techniques they forbid as for what they enable. For instance, pure functional programming disallows the use of side-effects; structured programming disallows the use of the goto statement. Partly for this reason, new paradigms are often regarded as doctrinaire or overly rigid by those accustomed to earlier styles. Avoiding certain techniques can make it easier to prove theorems about a program's correctness—or simply to understand its behavior.

Lecture 2


Lecture 3


Lecture 4



Lecture 5

Watch Video