Go to index

Game tree evaluation and the minimax principle (1 of 7)

The game tree

• A rooted tree in which internal nodes at even distance from the root are labelled MIN and internal nodes at odd distance are labelled MAX
  
  

• Every leaf has a real number associated to it, called its value

• Rules for evaluation:

  • Each leaf returns its associated value

  • Each MAX/MIN node returns the largest/smallest value returned by its children

• The evaluation problem consists of finding the value returned by the root

• We will study the number of steps taken by an algorithm for evaluating the game tree
  

Next page

Go to index