Game Trees ? Search Trees

• Strong similarities with 8s puzzle search trees

  • there may be loops/infinite branches
  • typically no equivalent of variable ordering heuristic
    • “variable” is always what move to make next

• One major difference with 8s puzzle

  • The key difference is that you have an opponent!

• Call the two players Max and Min

  • Max wants leaf node with max possible score
    • e.g. Win = +?
  • Min wants leaf node with min score,
    • e.g. Lose = -?

Previous slide

Next slide

Back to first slide

View graphic version