[Week 9]: Projects

Summary

We will start class by reviewing what we’ve covered these last 9 weeks. Then, you will work on your projects! If you didn’t get a working prototype over the week, the goal is to get one by the end of the class time. See below for the project prototype requirements.

Project Prototype

The project is to implement a search for a problem of your choosing. Last week we did Missionaries and Cannibals in class and I provided links to some other options. These included tic-tac-toe, nim, and some others.

The important parts of the search are:

  1. The search state representation
    • this should be some set of variables which represent the state of the game
    • You should define both your start and your goal states.
    • In the missionaries and cannibals, it was a tuple with three things:
      1. “how many missionaries on the right side”
      2. “how many cannibals on the right side”
      3. “how many boats on the right side”
    • The start state was (3, 3, 1)
    • The goal state was (0,0,0)
    • In general, representing with tuples is a good easy first solution.
  2. The set of possible actions
    • Given the way you represented the state, what are all the ways the state can change?
    • This is usually determined by the rules of the game
    • For example, in Missionaries and Cannibals, the rules were the you can only

    have two people in a boat at one time. - So, we could do the following actions in one boat trip:

    1. 2 Missionaries, 0 Cannibals
    2. 1 Missiionary, 0 Cannibals
    3. 1 Missionary, 1 Cannibal
    4. 0 Missionaries, 1 Cannibal
    5. 0 Missionaries, 2 Cannibals
    • We don’t mention the boat because it just changes sides to whichever side it wasn’t on
    • To represent this as changes to our state, we can say each of these three moves is a tuple:
      1. (2,0)
      2. (1,0)
      3. (1,1)
      4. (0,1)
      5. (0,2)
  3. A rule for applying the actions to the state that results in a new state
    • Given that you have your state and set of actions, there should be a rule

    that you can turn into a function that determines the new state. - For example, in missionaries and cannibals:

    • If the boat is on the left side, then the action is to bring the specified people to the right
    • If the boat is on the right side, then the action is to bring the specified people to the left
    • So if the state is (3,3,1), the boat is on the right, and any actions will bring people to the left
    • To bring people to the left, we subtract our move numbers
    • So, the move (1,1), which is 1 missionary and 1 cannibal, will result in the state (2,2,0)
    • If the boat were on the left side, we add our move numbers to the state because we are bringing people to the right

    and the state represents the number of people on the right

  4. A test for illegal actions
    • When are actions illegal?
    • You might have to apply the actions to your state a couple of time to notice the possible illegal states
    • It usually comes from possibilities that are outside of realistic situations
    • For example, in Missionaries and Cannibals:
      • if we were in the state (2,2,0), we still have the full set of actions available
      • So we could pick the action (2,0) which means “2 missionaries use the boat”
      • Since the boat is on the left side, we would add the number to our state
      • This results in state (4,2,1).
      • This state is clearly impossible!
    • Given this example, you should just have a rule that tells you when things are impossible
  5. A test for losing states
    • when is the state a losing state?
    • In Missionaries and Cannibals, the state is a losing state when:
      • there are more cannibals than missionaries on either side.
  6. A test for the winning state
    • when is the state a winning state?
    • In missionaries and cannibals, the winning state is (0,0,0)

So, to sum that up, you need:

  1. State Representation
  2. Action Representation
  3. Rule for applying actions to states
  4. Test for illegal actions
  5. Test for losing states
  6. Test for winning states

Given these things, the search is fairly simple. Below is the example code from Missionaries and Cannibals. When you implement your state code, this search code should also work for you. It is the following steps:

  1. Create the initial root state

  2. Create the python data structures that are useful (to_search, seen-states, solutions)

  3. Loop until the to_search stack/queue is empty

  4. Get the next state

  5. Check to see if it’s a solution

  6. If it’s not a solution, look at the states that can follow it

  7. Add in any states we haven’t seen yet
    • an example of a state that could repeat is just bringing 1 person back

    and forth forever.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
### this is the stack/queue that we used before
from collections import deque

### create the root state
root = MCState.root()


### we use the stack/queue for keeping track of where to search next
to_search = deque()

### use a set to keep track fo where we've been
seen_states = set()

### use a list to keep track of the solutions that have been seen
solutions = list()

### start the search with the root
to_search.append(root)


### while the stack/queue still has items
while len(to_search) > 0:

    ### get the next item
    current_state = to_search.pop()

    ### Test for Winning State
    if current_state.is_solution():
        ## this is a successful state!
        ## the state vars should be (0,0,0)

        ## Save it into our solutions list
        solutions.append(current_state)

        ## we don't really want to go through the rest of this loop
        ## continue will skip the rest of the loop and start at the top again
        continue

    ## look at the current state's children
    ## this uses the rule for actions and moves to create next states
    ## it is also removing all illegal states
    next_states = current_state.get_next_states()

    ## next_states is a list, so iterate through it
    for possible_next_state in next_states:

        ## to see if we've been here before, we look at the state variables
        possible_state_vars = possible_next_state.state_vars

        ## we use the set and the "not in" boolean comparison
        if possible_state_vars not in seen_states:

            # the state variables haven't been seen yet
            # so we add the state itself into the searching stack/queue

            #### IMPORTANT
            ## which side we append on changes how the search works
            ## why is this?
            to_search.append(possible_next_state)

            # now that we have "seen" the state, we add the state vars to the set.
            # this means next time when we do the "not in", that will return False
            # because it IS in
            seen_states.add(possible_state_vars)

## finally, we reach this line when the stack/queue is empty (len(to_searching==))
print("Found {} solutions".format(len(solutions)))

Examples of Missionaries and Cannibals in iPython Notebooks

Presentation Template

You will give a presentation to your parents when we meet next week. You will have time at the beginning of class to finish things up, but your presentation is due to me that Friday.

Here is the presentation template: