====== Lab 2 - Formulating Search Problems ======

===== Problem Description =====
Consider an agent for playing [[http://en.wikipedia.org/wiki/Connect-4|Connect-4]] on a //c// x //r// board (//c// columns and //r// rows).

===== Tasks =====
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 (or in a text file). You don't actually have to program it! Just write down pseudo-code.**

2. Estimate the memory requirement for you state data structure (in bytes relative to //c// and //r//). Suppose you want to solve the game by searching the state space. How does the size of your data structure influence the applicability of 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 three algorithms assuming you have 2GB of memory available? For the sake of simplicity, you can assume a square board, i.e. //c//=//r//.

3. For each of functions above (legal moves, successor state, ...), determine its (worst-case) time complexity in terms of //c// and //r//.