User Tools

Site Tools


Lab 2 - Formulating Search Problems

Problem Description

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 (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.

/var/www/ailab/WWW/wiki/data/pages/public/t-622-arti-13-1/lab_2_-_formulating_search_problems.txt · Last modified: 2013/02/05 12:42 by stephan