Consider an agent for playing Connect-4 on a c x r board (c columns and r rows).

1. Formulate the search problem, that is,

• find a representation (data structure) for states
• find a representation (data structure) for actions
• write down the initial state in your representation
• develop a function computing a list of legal moves of each agent
• develop a function computing the successor state resulting from executing a move in a state
• develop a function deciding when a terminal state is reached
• develop a function for deciding whether an agent has won the game

All of this can be done on paper. Just write down pseudo-code. You don't actually have to program it!

2. Estimate the memory requirement for you state data structure (in bytes relative to c and r). What does that mean for breadth-first search, depth-first search and iterative deepening search? What is the largest board (c x r) that you could solve using each of the two algorithms assuming you have 2GB of memory available.

3. For each of functions above, determine its (worst-case) time complexity in terms of c, r.