Numerical Systems

Introduction Positional Notation Converting Between Bases Binary Addition Binary Multiplication Challenges (Python) Challenges (Java)

Modular Arithmatic

Introduction The Modulus Operator Cyphers Modular Arithmetic Modular Inverse Challenges (Java)

Algorithms

Introduction Algorithms Time Functions Asymptotic Complexity Summation Challenges

Propositional Logic

Introduction Propositional Logic Conjunction and Disjunction Implication and Equivalence Bitwise Operators Challenges

Set Theory

Introduction Sets Subsets and Supersets Set Operations Challenges

Graph Theory

Introduction Graphs Directed Graphs Structure of Language Search Trees Neural networks Game Object Trees Challenges Graph Question Generator

Proof

Introduction Proof Proof by Cases Proof by Contradiction Proof by Induction Challenges

Maths to Code

Maths to Code Challenges Question Generator

Descriptive Statistics

Introduction Statistics Measures of Central Tendency Measures of Spread Data Visualisation Correlation Challenges

Probability

Introduction Probability Basics Combinatorics Probability Trees Law of Total Probability Bayes Rule Challenges

Inferential Statistics

Introduction Probability Distributions Samples and Populations Hypothesis Testing Z Scores Student's T-Test Challenges

Search Trees

In this video I’m going to be talking - at a very high level - about how graphs can be used for working in different problem domains. Rather than focusing on formalism or definitions, I want to show you how graphs can be used. Hopefully this will help you use graphs to solve problems that you encounter.

In this video we’ll be seeing how trees are used for reasoning about game states in game AI.

Important: You will not be tested on the problem domain! I do not expect you to learn about game trees or AI! If this video is helpful to you, great! If not, don’t worry about it!

Eight-minute video

You can also view this video on YouTube

Key Points

A game state (the state of everything in the game) can be represented as a node in a tree. The edges represent the actions that can be taken in that state.
This representation allows us to search for paths through the game tree from our starting state to a goal state.
The complexity of a game (how hard it is to solve with tree search) is related to the branching factor - how many possible successor states (children) there are for each state (node).
In a tree, a node has a parent (i.e. the node it branched out from) and children (the nodes the branch out from it)
The terminal nodes of the tree are the ones at the end. They also called the leaves.
The non-termainal nodes are the nodes in the middle.

Summary

In this section we saw how trees can be used for game AI by repesenting game states as vertices and actions as edges.

In the next section we are going to see another application of graphs to AI, this time to we’ll look at neural networks.

Improve this page

Getting Started

Introducing Mathematics