### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Intro Artificial Intelligence CS 580

Mason

GPA 3.66

### View Full Document

## 295

## 0

## Popular in Course

## Popular in ComputerScienence

This 7 page Study Guide was uploaded by Leland Swift on Monday September 28, 2015. The Study Guide belongs to CS 580 at George Mason University taught by Zoran Duric in Fall. Since its upload, it has received 295 views. For similar materials see /class/215120/cs-580-george-mason-university in ComputerScienence at George Mason University.

## Popular in ComputerScienence

## Reviews for Intro Artificial Intelligence

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/28/15

CS 580 Spring 2006 Dr Duric Midterm Review 1 Answer brie y a What is the major difference between blind and heuristic search methods b Enumerate and de ne three major blind search methods c How is the hill climbing method different from the best rst search method For what classes of problems are the hill climbing and the best rst search methods equivalent 2 List the order in which nodes are visited in the tree below for each of the following search strategies choosing leftmost branch in all cases a Depth rst search b Depth rst iterative deepening search increasing the depth by 1 each iteration c Breadth rst search A 3 A boy brings a basket of cabbage7 a wolf7 and a goat to a river There is a small boat on their river bank that they can use to cross to the other side However7 the boat is so small that it can hold only the boy and the cabbage or the boy and one of the animals The boy cannot leave the goat alone with either the cabbage or the wolf How should the boy use the boat to take the cabbage and the animals to the other side of the river in such a way that the number of river crossings is minimal and that the goat is never left alone with either the wolf or the cabbage on any side of the river Use iterative deepening search to solve this problem q In the water jug puzzle we are given a 4 liter jug7 and a 7 liter jug lnitially7 both jugs are empty Either jug can be lled with water from a tap7 and we can discard water from either jug down a drain Water may be poured from one jug into the other There is no additional measuring device We want to nd a set of operations that will leave precisely z liters of water in either one of the jugs i Set up a statespace search formulation of the water jug puzzle U a 7 a Given the initial iconic state description as a data structure b Give a goal condition on states as some test on data structures c Name the operators on states and give precise descriptions of what each operator does to a state description ii Find whether the goals z 1 2 3 4 5 6 7 can be accomplished in 8 or fewer steps Hint Use breadth rst search A simple sliding tile puzzle consists of 3 numbered tiles and an empty space The puzzle has two legal moves with associate costs A tile may move into an adjacent empty location This has a cost of 1 ii A tile can move over one other tile into the empty position This has a cost of 2 The start and goal positions are given below Set up a state space search formulation for this puzzle 93 V Specify the form of state descriptions the starting state and the goal state for this problem 7 V Name the operators on states and describe what each operator does to a state description Write a lisp function that takes a state as input and outputs a list of states that can be reached from that state Include the parent and the cost elds Propose a heuristic function Ii for solving this problem CLO V Use the A algorithm to nd a solution path using your heuristic function D ls your solution path optimal Give a formal argument The game mm is played as follows Two players alternate in removing one two or three pennies from a stack initially containing ve pennies The player who picks up the last penny loses Show by drawing the game tree that the player who has the second move can always win Can you think of a simple characterization of the winning strategy ls it necessary to generate the whole tree to nd a winning strategy A partial search tree for a two player game is given below MAX 23590742156 a Find the best move for the MAX player using the minimax procedure b Using alpha beta pruning show which parts of the tree do not need to be searched lndicate where the cutoffs occur 8 A simple version of the MM game is played as follows Two players alternate in removing H H H H to stones from three piles initially containing one one and ve stones respectively The player who picks up the last stone wins Each player can pick one or more stones from a single pile at least one stone has to be picked every time At every turn the players can pick from different piles a Show by drawing a game tree which player can always win You may use either DFS or BFS method to generate nodes b ls it necessary to generate the whole tree to nd a winning strategy Explain why or why not ls it possible to use the alpha beta pruning on this game tree Write a recursive lisp function that takes a list as an argument and returns the number of atoms on any level of the list For instance list A B C D E contains six atoms ABC DE and NIL Write a lisp function shuffle that takes a list of 52 different symbols and returns a list in which the original 52 elements are mixed in random order Hint Use functions random and remove Write a lisp function last5 that takes a list A as its argument and returns a list B consisting of the last ve elements of A You are not allowed to use the built in function last last5 A B 0 should return A B C last5 A B C D EF G should return D E F G H A simple version of a Grundy s game77 is played as follows Two players have in front of them a single pile of objects say a stack of 7 pennies The rst player divides the original stack into two stacks that must be unequal Each player alternatively thereafter does the same to some single stack when it is his turn to play The game proceeds until each stack has either just one penny or twoiat which point continuation becomes impossible The player who rst cannot play is the loser Show by drawing a game tree whether any of the players can always win The 8 puzzle consists of eight numbered movable tiles set in a 3x3 frame One cell of the frame is always empty thus making it possible to move and adjacent numbered tile into the empty cellior we could say to move the empty cell Two con gurations of tiles are given Consider the problem of changing the initial con guration into the goal con guration 2 4 3 l 2 3 l 6 8 4 8 5 7 5 6 7 start goal Set up a state space search formulation for this puzzle a Specify the form of state descriptions the starting state and the goal state for this problem 14 H a b c d e Name the operators on states and describe what each operator does to a state description Propose a heuristic function I for solving this problem Use the 14 algorithm to nd a solution path ls your solution path optimal Give a formal argument Write a recursive function ip that takes a binary tree as input and returns a binary tree that it is its mirror image You can represent binary trees as nested structures Nested recursive representation ltr00tgt ltleft subtreegt ltright subtreegt Examples ip 71 2 3 should return 1 3 2 Hip 71 2 3 4 should return 1 2 4 3 Hip 71 2 3 4 5 10 11 12 6 7 should eturn 1 6 7 8 0 0 2 10 12 11 3 5 4 a Write a lisp function funny rst that takes a list of at lists and returns a new list composed of the rst elements of the original at lists b Write a lisp function funnyJust that takes a list of at lists as its argument and returns a new list composed of the last elements of the original at lists c Write a lisp function funnylen that takes a list of at lists as its argument and returns the sum of the lengths of the nested lists d Write a lisp function funnyjum that takes a list of at lists of numbers and returns the sum of the elements of the nested lists Examples funny rst 7A B C D E F G funnyJast 7A B C D E F G funnyJen 7A B C D E F G funnysum 71 2 3 4 5 10 20 30 should return A C D F should return B C E H should return 8 should return 75 A simple sliding tile puzzle consists of 4 numbered tiles and an empty space The puzzle has two legal moves with associate costs A tile may move into an adjacent empty location This has a cost of 1 ii A tile can move over one other tile into the empty position This has a cost of 2 The start and goal positions are given below Set up a state space search formulation for this puzzle a Specify the form of state descriptions7 the starting state7 and the goal state for this problem b Name the operators on states and describe what each operator does to a state description c Propose a heuristic function Ii for solving this problem d Use the A algorithm to nd a solution path e ls your solution path optimal Give a formal argument 17 The sliding tile puzzle consists of three black tiles7 three white tiles and an empty space in the con guration shown below HEE The puzzle has two legal moves with associate costs A tile may move into an adjacent empty location This has a cost of 1 A tile can move over one or two other tiles into the empty position This has a cost equal to the number of tiles jumped over The goal is to have all the white tiles to the left of all the black tiles with the blank in the middle a Choose a representation for this problem so that A algorithm can be applied to nd a solution b Propose two heuristics for solving this problem c Show all states that can be reached from the start and compute their 9 and h values for one of your heuristics state clearly which one you are using Mark the state that would be expanded next by A algorithm 7 you do not need to expand that state The 8 puzzle consists of eight numbered7 movable tiles set in a 3x3 frame One cell of the frame is always empty thus making it possible to move an adjacent numbered tile into the empty cellior7 we could say7 to move the empty cell Two con gurations of tiles are given Consider the problem of changing the start con guration into the goal con guration 5 6 7 5 7 start goal Set up a state space search formulation for this puzzle a Specify the form of state descriptions7 the starting state7 and the goal state for this problem b Name the operators on states and describe what each operator does to a state description Propose a heuristic function Ii for solving this problem d Use the A algorithm to nd a solution path e O ls your solution path optimal Give a formal argument 19 A simple version of a Kayles game77 is played as follows Two players have in front of them a single contiguous sequence of objects say 5 pennies which are placed next to each other so that the rst penny touches the second the second touches the third the third touches the fourth and the fourth touches the fth penny The rst player removes 1 or 2 pennies whose sides that are touching for example the rst player can remove any single penny or pennies 1 and 2 or pennies 2 and 3 or pennies 3 and 4 or pennies 4 and 5 Each player alternatively thereafter removes 1 penny or 2 pennies whose sides are touching Note If the rst player removes penny 2 the pennies 1 and 3 will have a gap between them and cannot be removed at the same time The last player to pick a penny or two loses Show by drawing a game tree whether any of the players can always win You can ignore symmetries and obvious losing plays if there is a winning play available such as picking both pennies when there are 2 pennies left 20 a Write a non recursive function that takes a list as its argument and reverses it Hint use the dolist statement b Write a recursive function that takes a list as its argument and reverses it Examples reverse 7A B C D E should return F D E C B A reverse 71 2 3 4 5 should return 4 5 6 3 2 1 21 What do these functions do defun xx lst if atom lst 0 if null lst 0 if member first lst rest lst 1 XX rest lSt xx rest lst defun yy lst if atom lst yy list lst mapcar lambda x if atom x list t x nil lst defun dd lst cond atom lst lst atom first lst cons first lst dd rest lst t append dd first lst dd rest lst defun zz lst cond null lst nil numberp first lst zz rest lst t append list first lst zz rest lst list first lst 22 Consider the following game tree a Find the best move for the MAX player using the minimax procedure b Perform a left to right alpha beta pruning on the tree lndicate where the cutoffs occur 23 c Perform a right to left alpha beta pruning on the tree Discuss why different pruning occurs In the water jug puzzle we are given a 2 liter jug and a 5 liter jug lnitially both jugs are empty Either jug can be lled with water from a tap and we can discard water from either jug down a drain Water may be poured from one jug into the other There is no additional measuring device We want to nd a set of operations that will leave precisely z liters of water in either one of the jugs A Set up a statespace search formulation of the water jug puzzle Give the initial state description as a data structure De ne the goal predicate as a function of a state Name the operators on states and give precise descriptions of what each operator does to a state E Find whether the goals z E 1 2 3 4 5 can be accomplished in 4 or fewer steps A simple version of the MM game is played as follows Two players alternate in removing stones from three piles initially containing two stones each The player who picks up the last stone wins Each player can pick one or more stones from a single pile at least one stone has to be picked every time At any turn the player can pick from any one pile Show by drawing the game tree whether a player can always win and if so which one ls it necessary to generate the whole tree to nd a winning strategy Write a lisp function that takes a at list as an argument and returns a list whose elements are those elements of the original list that are not numbers Write a lisp function that takes a at list as an argument and returns a sum of the numbers in the original list Your function should not add the non number elements of the original list Write a lisp function shu le that takes a list of 32 different symbols and returns a list in which the original 32 elements are mixed in random order Hint Use functions random and remove

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I made $350 in just two days after posting my first study guide."

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.