
Here's a game that we've seen before.

We call this a singleplayer deterministic game.

We know how to solve this.

We use the techniques of search through a state spacethe problems solving techniques.

We draw a search tree through the state space,

and I'm going to draw the nodes like this with triangles rather than with circles.

In any positionin this position herethere are three moves I can make.

I can slide this tile, this tile, or this tile.

So I have 3 moves, and that gives me 3 more states.

I keep on expanding out the states going farther and farther down until I reach one

that's a goal state, and then I have a path through there that gets me to a solution.

What does it take to describe a game?

Well, we have a set of states S, including a distinguished start state S0.

We have a set of players P that can be our one player, as in this game, or two or more.

We have a function that gives us the allowable actions in a state,

and sometimes we put in a second argument,

which is the player, in that statemaking action,

and sometimes it's explicit in the state itself whose turn it is to move.

We have a transition function that tells us the result of,

in some state, applying an action giving us a new state.

And we have a terminal test to say is it the end of the game.

That's going to be true or false.

Finally, we have terminal utilities saying that for a given state and a given player

there is some number which is the value of the game to that player.

In simple games that number is a win or a loss, a one or a zero.

Sometimes it's denoted as a +1 and a 1.

In other games there can be more complicated utilities

of you win twice as much or four times as much or whatever.