Instructions
User Manual:
Open the PDF directly: View PDF 
.
Page Count: 6
CS 4260/5260: Introduction to AI
Homework 1 [ points]: (Search).
Due: 2018, Central Time on BrightSpace
General Instructions:
If anything is ambiguous or unclear.
1. Discuss possible interpretations with other students, your TA, and instructor
2. Send e-mail to your TA first, and to your instructor if an issue is not resolved to your
satisfaction.
3. Make use of web sources.
Remember that after general discussions with others, you are required
to work out the problems by yourself. All submitted work must be your
own. Please refer back to the Honor code for clarifications.
Write legibly, be sure to staple all your answer sheets together, and write your
name, and the honor pledge on the top of the first answer sheet.
Start early, and avoid last minute stress!
!
Introduction*
!
"#!$%&'!()*+,-$.!/*0!1&22!-*3,!4!54-64#!47,#$!$%4$!8'!(4$%'!$%)*07%!4!649,!1*)23.!:*$%!$*!
),4-%!4!(4)$&-024)!2*-4$&*#!4#3!$*!-*22,-$!8**3!,88&-&,#$2/;!<*0!1&22!:0&23!7,#,)42!',4)-%!
427*)&$%6'!4#3!4((2/!$%,6!$*!54-64#!'-,#4)&*';!
!
=%,!-*3,!8*)!$%&'!()*+,-$!&'!'$*),3!&#!4!8,1!>4-?,$!8&2,'!&#'&3,!$%,!)4-?,$@'*2A,)!8*23,);!=%,!8&2,!
/*0!1&22!:,!,3&$!&'!-422,3!student.rkt!BC46(2,!649,'!4),!'$*),3!&#!$,C$!8&2,'!1&$%!;24/!
,C$,#'&*#'!&#'&3,!$%,!24/*0$'!8*23,);!
!
=%,!(/$%*#!-*3,!&#!$%,!64&#!8*23,)!()*A&3,'!A&'042&94$&*#'!*8!/*0)!8*!',4)-%!(4$%!2&?,!$%,!*#,!
'%*1#!:,2*1;!"8!/*0!3*#D$!%4A,!(/$%*#!*#!/*0)!64-%&#,.!4#3!3*#D$!14#$!$*!',,!$%,',!
A&'042&94$&*#'.!/*0!-4#!&7#*),!$%,',!8&2,'!E$%,/!4),!#*$!#,,3,3!$*!)0#!/*0)!-*3,!4#3!1&22!#*$!:,!
0',3!&#!7)43F;!
!
!
!
How*to*Run*Your*Code*
!
=%,!-*3,!8*)!$%&'!()*+,-$!-*#'&'$'!*8!',A,)42!5/$%*#!8&2,'.!'*6,!*8!1%&-%!/*0!1&22!#,,3!$*!),43!
4#3!0#3,)'$4#3!&#!*)3,)!$*!-*6(2,$,!$%,!4''&7#6,#$.!4#3!'*6,!*8!1%&-%!/*0!-4#!&7#*),;!<*0!
-4#!3*1#2*43!422!$%,!-*3,!4#3!'0((*)$!8&2,'!4'!4!9&(!4)-%&A,;!
!
<*0)!-*3,!'%*023!),$0)#!4!2&'$!*8!-%4)4-$,)'!1%&-%!4),!&#'$)0-$&*#'!8*)!(4-64#!E&;,;!‘(#\S #\S
#\W) 8*)!'*0$%!E3*1#F.!'*0$%.!1,'$!E2,8$FF;!
!
=*!)0#!/*0)!-*3,!&#!)4-?,$!)0#G!
racket racket-solver/main.rkt -l <path to layout in layouts dir>
-s <search strategy> -r <heuristic>
!
"8!/*0!4),!0'!H*1'!-%4#7,!$%&'!$*G!
racket racket-solver\main.rkt -l <path to layout in layouts dir>
-s <search strategy> -r <heuristic>
!
I*)!,C46(2,G!
racket racket-solver/main.rkt -l layouts/tinyMaze.lay -s
tinyMazeSearch
!
*)!8*)!H*1'G!
racket racket-solver\main.rkt -l layouts\tinyMaze.lay -s
tinyMazeSearch
!
J,,!6*),!,C46(2,'!&#!)4-?,$@-*664#3';$C$!
!
=*!A&'042&9,!/*0)!-*3,!1&$%!(/$%*#!E&8!/*0!%4A,!(/$%*#!&#'$422,3F.!)0#G!
!
python pacman.py -l <name of layout file> -p RacketAgent -a
fn=<search strategy>,heuristic=<heuristic>
!
Note:*"$!&'!&6(*)$4#$!$%4$!$%,),!:,!#*!'(4-,!:,$1,,#!$%,!-*664!4#3!%,0)&'$&-;!
!
J,,!,C46(2,'!&#!-*664#3';$C$!
*
Problems*
=%,),!4),!$%),,!',4)-%!'$)4$,7&,'!$%4$!/*0!#,,3!$*!&6(2,6,#$!8*)!$%&'!4''&7#6,#$G!KIJ.!LIJ!4#3!
MN;!
!
Depth*First*Search*
*
For*python*visualization:*
"#!',4)-%M7,#$';(/.!/*0O22!8!4!8022/!&6(2,6,#$,3!>4-?,$M7,#$.!1%&-%!A&'042&9,'!4!(4$%!
$%)*07%!54-64#O'!1*)23!4#3!$%,#!,C,-0$,'!$%4$!(4$%!'$,(@:/@'$,(;!=%,!',4)-%!427*)&$%6'!8*)!
8*)6024$!4!(24#!4),!#*$!&6(2,6,#$,3!@@!$%4$O'!/*0)!+*:;!
!
I&)'$.!$,'$!$%4$!$%,!>4-?,$M7,#$!&'!1*)?!-*)),-$2/!:/!)0##G!
!
python pacman.py -l tinyMaze -p RacketAgent -a fn=tinyMazeSearch
!
=%,!-*664#3!4:*A,!$,22'!$%,!>4-?,$M7,#$!$*!0',!$&#/P49,J,4)-%!4'!&$'!',4)-%!427*)&$%6.!
1%&-%!&'!&6(2,6,#$,3!&#!'$03,#$;)?$!4$!$%,!$*(!*8!$%,!8&2,;!54-64#!'%*023!#4A&74$,!$%,!649,!
'0--,''8022/;!
!
Racket*Part:*
Q*1!&$O'!$&6,!$*!1)&$,!8022@82,37,3!7,#,)&-!',4)-%!80#-$&*#'!$*!%,2(!54-64#!(24#!)*0$,'R!
5',03*-*3,!4#3!,C46(2,'!8*)!$%,!',4)-%!427*)&$%6'!/*0O22!1)&$,!-4#!:,!8*0#3!&#!$%,!2,-$0),!
'2&3,'!8)*6!1,,?!S!4#3!&#!',-$&*#!T;U;S!*8!$%,!$,C$:**?;!>,6,6:,)!$%4$!4!',4)-%!#*3,!60'$!
-*#$4&#!#*$!*#2/!4!'$4$,!:0$!42'*!$%,!*)64$&*#!#,-,''4)/!$*!),-*#'$)0-$!$%,!(4$%!E(24#F!1%&-%!
7,$'!$*!$%4$!'$4$,;!
!
Important*note:*=%,!80#-$&*#'!()*A&3,3!&#!0$&2';)?$!4''06,!$%4$!#*3,'!*#!$%,!8)*#$&,)!4),!
'$*),3!4'!$0(2,'!*8!$/(,!EV(4$%!$*!'$4$,W.!'$4$,F;!"8!/*0!-%**',!$*!'$*),!/*0)!(4$%!3&88,),#$2/.!
(2,4',!&#-203,!$%,!80#-$&*#'!#,,3,3!$*!&#$,)(),$!/*0)!'*20$&*#!&#!'$03,#$;)?$;!
!
Important*note:!M22!*8!/*0)!',4)-%!80#-$&*#'!#,,3!$*!),$0)#!4!2&'$!*8!2,$$,)'!),(),',#$!4-$&*#'!
$%4$!1&22!2,43!$%,!47,#$!8)*6!$%,!'$4)$!$*!$%,!7*42!E8*)!,C46(2,!‘(#\S #\S #\W)8*)!'*0$%@
'*0$%@1,'$F;!=%,',!4-$&*#'!422!%4A,!$*!:,!2,742!6*A,'!EA42&3!3&),-$&*#'.!#*!6*A!$%)*07%!
1422'F;!"8!/*0!0',!$%,!7,$@'0--!80#-$&*#!()*A&3,3!&#!0$&2';(/.!,4-%!'0--,''*)!-*6,'!(4&),3!1&$%!
$%,!2,$$,)!$%4$!3,'-)&:,'!&$'!4-$&*#;!
!
<*0)!80#-$&*#!60'$!),$0)#!$%&'!2&'$.!#*$!()&#$!&$;!"8!/*0!4),!()&#$!$%,!2&'$!&#'$,43!*8!),$0)#!&$.!
/*0)!-*3,!1&22!$%)*1!4#!,))*)!1%,#!/*0!)0#!$%,!)4-?,$!-*664#3!$*!$,'$!/*0)!()*7)46;!
!
Hint:!B4-%!427*)&$%6!&'!A,)/!'&6&24);!M27*)&$%6'!8*)!KIJ.!LIJ.!4#3!MN!3&88,)!*#2/!&#!$%,!3,$4&2'!*8!
%*1!$%,!8),!&'!64#47,3;!J*.!-*#-,#$)4$,!*#!7,$$!KIJ!)&7%$!4#3!$%,!),'$!'%*023!:,!
),24$&A,2/!'$)4&7%$8*)14)3;!
!
"6(2,6,#$!$%,!3,($%@8&)'$!',4)-%!EKIJF!427*)&$%6!&#!$%,!KIJ!80#-$&*#!&#!'$03,#$;)?$;!=*!64?,!
/*0)!427*)&$%6!-*6(2,$,.!1)&$,!$%,!7)4(%!',4)-%!A,)'&*#!*8!KIJ.!1%&-%!4A*&3'!,C(4#3!4#/!
42),43/!A&'&$,3!'$4$,'!E&8!/*0!3*!#*$!?,,(!$)4-?!*8!42),43/!A&'&$,3!'$4$,'.!/*0)!-*3,!1&22!:,!A,)/!
'2*1!4#3!64/!,C-,,3!$%,!'$4-?!'&9,!422*1,3!8*)!)4-?,$F;!
!
=*!$,'$!/*0)!-*3,.!$)/!$%,!8*22*1!-*664#3'!&#!/*0)!-*664#3!2&#,!E'0:'$&$0$,!X!8*)!Y!&8!0'!
H*1'FG!
!
racket racket-solver/main.rkt -l layouts/tinyMaze.lay -s dfs
racket racket-solver/main.rkt -l layouts/tinySearch.lay -s dfs
racket racket-solver/main.rkt -l layouts/smallMaze.lay -s dfs
racket racket-solver/main.rkt -l layouts/greedySearch.lay -s dfs
racket racket-solver/main.rkt -l layouts/mediumMaze.lay -s dfs
racket racket-solver/main.rkt -l layouts/bigMaze.lay -s dfs
!
B4-%!$,'$!'%*023!()&#$!4!2&'$!*8!&#'$)0-$&*#'!&#!;U!Z!T!',-*#3';!
!
"8!/*0!1*023!2&?,!$*!',,!/*0)!*0$(0$!A&'042&9,3!0'!$%,!(/$%*#!2&:)4)&,'.!$)/!$%,!8*22*1!
-*664#3'G!
!
python pacman.py -l tinyMaze -p RacketAgent
python pacman.py -l tinySearch -p RacketAgent
python pacman.py -l smallMaze -p RacketAgent
python pacman.py -l greedySearch -p RacketAgent
python pacman.py -l mediumMaze -p RacketAgent
python pacman.py -l bigMaze -z .5 -p RacketAgent
!
Hint:!"8!/*0!0',!4!J$4-?!4'!/*0)!34$4!'$)0-$0),!4#3!433!#*3,'!$*!$%,!8)*#$&,)!&#!$%,!'46,!*)3,)!
$%,/!4),!()*A&3,3!:/!7,$@'0--.!$%,!'*20$&*#!8*0#3!:/!/*0)!KIJ!427*)&$%6!8*)!6,3&06P49,!
'%*023!%4A,!4!2,#7$%!*8!ST[!E&8!/*0!(0'%!$%,6!&#!$%,!),A,)',!*)3,)!/*0!6&7%$!7,$!\T]F;!"'!$%&'!4!
2,4'$!-*'$!'*20$&*#^!"8!#*$.!$%&#?!4:*0$!1%4$!3,($%@8&)'$!',4)-%!&'!3*!$*!7,$!4!'0:@*($&642!
(4$%;!
!
Hint:!"8!54-64#!6*A,'!$**!'2*12/!8*)!/*0!&#!$%,!(/$%*#!A&'042&94$&*#'.!$)/!$%,!*($&*#!@@
8)46,=&6,!];!
*
Breadth*First*Search*
!
"6(2,6,#$!$%,!:),43$%@8&)'$!',4)-%!ELIJF!427*)&$%6!&#!$%,!LIJ!80#-$&*#!&#!'$03,#$;)?$;!M74&#.!
1)&$,!4!7)4(%!',4)-%!427*)&$%6!$%4$!4A*&3'!,C(4#3!4#/!42),43/!A&'&$,3!'$4$,';!=,'$!/*0)!-*3,!
$%,!'46,!14/!/*0!3&3!8*)!3,($%@8&)'$!',4)-%;!
!
E474&#!'0:'$&$0$,!X!8*)!Y!&8!0'!H*1'FG!
!
racket racket-solver/main.rkt -l layouts/tinyMaze.lay -s bfs
racket racket-solver/main.rkt -l layouts/smallMaze.lay -s bfs
racket racket-solver/main.rkt -l layouts/greedySearch.lay -s bfs
racket racket-solver/main.rkt -l layouts/mediumMaze.lay -s bfs
racket racket-solver/main.rkt -l layouts/bigMaze.lay -s bfs
!
=%,',!-*664#3'!'%*023!,4-%!$4?,!;U!@!S!',-*#3'!$*!)0#;!
!
"8!/*0!14#$!$*.!/*0!-4#!42'*!$)/!$&#/J,4)-%.!:0$!/*0)!-*3,!1&22!()*:4:2/!$4?,!\]!',-*#3'!*)!6*),!
$*!8!$%,!'*20$&*#!0'!LIJG!
!
racket racket-solver/main.rkt -l layouts/tinySearch.lay -s bfs
!
"8!/*0!1*023!2&?,!$*!',,!A&'042'!*8!/*0)!-*3,!&#!4-$&*#.!$)/!$%,!8*22*1!(/$%*#!-*664#3'G!
!
python pacman.py -l smallMaze -p RacketAgent -a fn=bfs
python pacman.py -l mediumMaze -p RacketAgent -a fn=bfs
python pacman.py -l greedySearch -p RacketAgent -a fn=bfs
python pacman.py -l bigMaze -p RacketAgent -a fn=bfs -z .5
!
Hint:!"8!54-64#!6*A,'!$**!'2*12/!8*)!/*0.!$)/!$%,!*($&*#!@@8)46,=&6,!];!
!
A-Star*Search*
!
"6(2,6,#$!MN!7)4(%!',4)-%!&#!$%,!,6($/!80#-$&*#!M@'$4)!&#!'$03,#$;)?$;!MN!$4?,'!4!%,0)&'$&-!
80#-$&*#!4'!4#!4)706,#$;!=%,!#022@%,0)&'$&-!80#-$&*#!&#!0$&2';)?$!&'!4!$)&A&42!,C46(2,;!
!
<*0!-4#!$,'$!$%4$!/*0)!MN!&6(2,6,#$4$&*#!&'!1*)?!-*)),-$2/!:/!)0##!$%,!8*22*1!)4-?,$!
-*664#3'!E474&#!'0:'$&$0$,!X!8*)!Y!&8!0'!H*1'FG!
!
racket racket-solver/main.rkt -l layouts/bigMaze.lay -s astar -r distance-to-food
racket racket-solver/main.rkt -l layouts/openMaze.lay -s astar -r distance-to-food
racket racket-solver/main.rkt -l layouts/greedySearch.lay -s astar -r count-food
racket racket-solver/main.rkt -l layouts/tinySearch.lay -s astar -r count-food
!
=%,',!-*664#3'!'%*023!,4-%!$4?,!;U!@!S!',-*#3'!$*!)0#;!
!
<*0!'%*023!7,$!$%,!'46,!),'02$'!4'!8)*6!/*0)!LIJ!&6(2,6,#$4$&*#.!:0$!&#!2,''!$&6,!E#*$,!$%4$!
$&#/J,4)-%!'%*023!#*1!*#2/!$4?,!4!8,1!',-*#3';!
!
"8!/*0!1*023!2&?,!$*!',,!A&'042'!*8!/*0)!-*3,!&#!4-$&*#.!$)/!$%,!8*22*1!(/$%*#!-*664#3'G!
!
python pacman.py -l bigMaze -z .5 -p RacketAgent -a fn=astar,heuristic=distance-to-food
python pacman.py -l openMaze -z .5 -p RacketAgent -a fn=astar,heuristic=distance-to-food
python pacman.py -l greedySearch -p RacketAgent -a fn=astar,heuristic=count-food
python pacman.py -l tinySearch -p RacketAgent -a fn=astar,heuristic=count-food
!
Some*Tips*for*Racket*
!
=%,),!4),!',A,)42!14/'!&#!1%&-%!>4-?,$!1*)?'!3&88,),#$2/!8)*6!*:+,-$!*)&,#$,3!
24#7047,'.!4'!/*0!#*!3*0:$!3&'-*A,),3!&#!5)*7)466!M''&7#6,#$!];!=%&'!',-$&*#!-*#$4&#'!4!
8,1!(*&#$,)'!*#!%*1!$*!3*!'*6,!$%'!&#!>4-?,$!$%4$!6&7%$!8,,2!4!2&$$2,!#*#@&#$0&$&A,;
!
<*0!-4#!8!6*),!#*$,'!*#!%*1!$*!0',!80#-$&*#'!&#!$%,!0$&2';)?$!8&2,!4#3!,C46(2,'!&#!$%,!'2&3,'!
8)*6!=%0)'34/.!J,($,6:,)!\T;!
!
Assigning*and*Scoping*Variables*
!
_',!define!$*!64?,!72*:42!A4)&4:2,'.!let!$*!64?,!2*-422/!'-*(,3!A4)&4:2,'!4#3!set!!$*!
-%4#7,!$%,!A420,!*8!4!A4)&4:2,;!=*!4''&7#!602$&(2,!A4)&4:2,'!0',!define-values.!let-
values!4#3!set!-values;!
!
While*loops*
=*!64?,!4!1%&2,!2**(!&#!)4-?,$.!433!4!`G:),4?!-*#3&$&*#!$*!4#!&#&$,!8*)!2**(;!I*)!,C46(2,G!
!
(let ([x 0])
(for ([i (in-naturals 1)]
#:break (>= x 5))
(print (list i x))
(set! x (add1 x))))
!
<*0!-4#!42'*!433!a-*#$�,b!$/(,!'$4$,6,#$'!:/!8&2$,)!2**('!1&$%!$%,!`G0#2,''!*(,)4$*)G!
!
(let ([x 0])
(for ([i (in-naturals 1)]
#:unless (even? i)
#:break (>= x 5))
(print (list i x))
(set! x (add1 x))))!
!
Using*Lists,*Stacks,*Queues*and*Priority*Queues*
!
P,$%*3'!*8!'$4-?'.!c0,0,'!4#3!()&*)&$/!c0,0,'!%4A,!:,,#!()*A&3,3!4$!$%,!$*(!*8!utils.rkt;!
!
<*0!1&22!#*$&-,!$%4$!(0'%!80#-$&*#'!),$0)#!$%,!34$4$/(,!4#3!(*(!80#-$&*#'!),$0)#!$%,!(*((,3!
&$,6!4#3!$%,!34$4!$/(,;!=%&'!&'!:,-40',!&#!80#-$&*#42!24#7047,'!2&?,!>4-?,$!&$!&'!-*#'&3,),3!7**3!
()4-$&-,!#*$!$*!60$4$,!*:+,-$'!4#3!&#'$,43!),@4''&7#!$%,6!$*!$%,!60$4$,3!A,)'&*#!0'!
80#-$&*#'!2&?,!set!!4#3!set!-values;!
!
<*0!-4#!-%,-?!&8!4#!,2,6,#$!&'!&#!4!2&'$!0'!$%,!ismember?!80#-$&*#!E$%&'!1&22!-*6,!&#!%4#3/!
1%,#!/*0!14#$!$*!-%,-?!&8!4!'$4$,!14'!(),A&*0'2/!A&'&$,3F;!
!
Acknowledgements*
*
=%,!(/$%*#!-*3,!4#3!&3,4!8*)!$%&'!()*+,-$!-*6,'!8)*6!_d!L,)?2,/;!<*0!-4#!),43!4:*0$!$%,&)!
(/$%*#!A,)'&*#!*8!$%&'!()*+,-$!4$!%$$(GYY4&;:,)?,2,/;,30!!
