# What are the state space and the state transition function in AI?

I'm studying for my AI final exam, and I'm stuck in the state space representation. I understand initial and goal states, but what I don't understand is the state space and state transition function. Can someone explain what are they with examples?

For example, one of the questions was this on my previous exam:

Given $$k$$ knights on an infinite (in all directions) chessboard and k selected squares of the board. Our task to move the knights to these selected squares obeying the following simple rules:

• All knights move parallel, following their movement rule (L-shape jump)
• No knights can move to a square on which a knight stood anytime before

Give the state space of the problem, the starting and goal states, and the state transition function!

## 1 Answer

### Initial state

How things are at first.

In your particular example, it would be where your k knights are placed on the board initially. Your problem doesn't precisely state this, so you could either place them at the bottom or at random.

### Goal state

The board with the k knights placed on the target squares.

### State transition function

A function that takes actions (bound presumably by rules) and returns a new state.

In the k knight problem, the legal actions are moving parallel and in L shape movements, after which the knight will be in a new position and the board in a new state.

### State space

The set of all states reachable from the initial state by any sequence of actions.

So, in the case of the k knight problem, your state space would start at the top with your initial state followed down by each individual movement of the k knights and the resulting new state. A graph where lines are actions and nodes are new states or a table are common representations of state space.

### Reference

Artificial Intelligence: A Modern Approach, by S. Russell and P. Norvig.