Game Trees
- For this bit we're going to talk about deterministic adversarial games
with full information.
- Chess and Tic Tac Toe (noughts and crosses) are two examples.
- There are two players.
- They take turns moving.
- There is no chance involved, so backgammon doesn't work.
- There is one winner (or a draw).
- Can you think of some other games that this works for?
- Can you think of some games that don't count?
- This is good old fashioned AI, and we've been doing it for 50 years.
- A good way to represent the game is a game tree.
- Each node represents a state.
- The next level of the tree represents all the possible next moves, with
one node for each state.
- It doesn't strictly have to be a tree as in some games (e.g. chess) you
can revisit states.
