New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

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

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Artificial Intelligence

by: Mrs. Carolyne Abbott

Artificial Intelligence CS 4710

Mrs. Carolyne Abbott
GPA 3.71


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 5 page Class Notes was uploaded by Mrs. Carolyne Abbott on Monday September 21, 2015. The Class Notes belongs to CS 4710 at University of Virginia taught by Staff in Fall. Since its upload, it has received 10 views. For similar materials see /class/209697/cs-4710-university-of-virginia in ComputerScienence at University of Virginia.

Similar to CS 4710 at UVA

Popular in ComputerScienence


Reviews for Artificial Intelligence


Report this Material


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/21/15
Lecture 26 Review Movies CS 416 Artificial Intelligence H M M Exam ple Point to stress about H s rThere l leed not be a correlatlol l between real States and the HMM States Example mudellng a EDlrltEISS onMYYurnurui S39lel2ll ATE r w IP quota Iconsnap iimziimxmomi n urrnlnnrrnm mm 2 saiiznizzia rimr I39mr mi ni Threestate HMM Final Exam Modeling a coin toss it a momma Women May 6 at 700 pm in this classroom THN E316 CLOSED BOOK CLOSED NOTE Final Exam will cover Review Chapters 3 and 7 These are l lOt go you should be ra ihg to be emphaSlZed oh the test but miliarWilh the baSlC Search r slmulated ahhealihg GA Search in Cuntlnuuus spaces Final Exam will Cover Chapters 8 9 15 17 n 20 e 8 Flrstrol del loglc excluoihg 8 4 r 9 ll39lferel39lce lrl F 715 3 HMM 7 l5 6 Speech Recoghitioh 7 l7 Makll lg complex deClSlOl l r 20 Statlstlcal Leamll lg NN Sectlol ls l 2 and 5 Page 1 CS 416 Artificial Intelligence Lecture 22 Making Complex Decisions Mapping MDPs to POMDPs The belief state alter executing action a and observing observation 0 is Your belief yeetur U at state 5 evaluates tn li is39i ttUlJ UlZTLLll Jilii call this o39 FORWARD o a o i J But this requires knowing the observation 0 Predicting future observation Prob of perceiving 0 given d r s39 is the set of potentially reached states I39iilii in eriuln39tiir rlt l lii Xrtis mli is lmlil Zoomich Predicting new belief state Previously we predicted observation Now predict new belief state 7 a 1739 prob of reaching o39 from o gllerl action a rilmi l Iliumii Zrlil39lnni ilr394ililiil X I iii39inn liZti quot e firo39 FORWARDm a o e 0 ornemise l n riiii Another way to write For all observations 0 that when combined with the knowledge of action a and previous state b lead to a new belief state sum inimiZIi n Jiriin Game Theory Multiagent games with simultaneous moves 7 First study games With one rnoye bankruptcy proceedings aumluns Ecunumlcs War gaming Page 1 Definition of a game eThe players matrix sthe utilityte eaeh playerrer each combination or o e The payorr preyide HS aetiu Game theory strategies Strategy policy 7 What do you do pure strategy 7 Vuuduthesamethlnuallthetlme mixed strategy 7 you rely on some randomlzed puilcylu select an action 7 StrategyProf e The assignment or strategiestu players Game theoretic solutions What s a solution to a game eAll players select a rational strategy 7 Note that We re not arialyzmg orie partlcuiargarne but the outcomes that accumulate oyera series of played games Prisoner s Dilemma Alice and Bob are caught red handed at the scene ofa crime 7 both are iriterrogated separately by the police 7 the penalty forboth irthey both confess is 5 years 7 the penalty for both irrieithercoriresses is l year 7 it one teStlfleS against the o er the implicated gets in years the sriiteh gets El years What do you do to act sel shly Prisoner s dilemma payoff matrix Prisoner s dilemma strategy Alice s Strategy 7 if Bob leSM leS bEs tuptlunlstulestlf36 t y e5i ingisa eeroo ses dominant re u best options is to lestlfy0 strategy Prisoner s dilemma strategy Rationality Both players seem to have clear strategies 7 Both testify game outeome would be 75 75 39 Bob s Strategy e if Alice testries b s erlice refuses 39 95 me 395 a best options isto testirym d mmanl strategy Dominance of strategies Pareto Optimal Pareto optimality comes from economics 39 eAn outcome can be Pareto optima 39 textbook no altematiye outeome that all players would er Comparing strategies 7 strategy s can strongly dominate s the outeome or sis always bettertnari the outeome or e no mattervmattne other player does prer s testlymg strongly dominates remamgtur Bop andAllce i Warm the hamper mid be ammpitshed WM 39 dlsadvantaglng at least one group 7 strategy s can Weakly dominate s the outcome Elf Sis better than the outcome Elf 5 on at least on action uftne opponent and no worse on others Is the testify outcome 5 5 Pareto Optimal Is 5 5 Pareto Optimal Dominant strategy equilibrium s5 5 represents a dominant strategyequilionum Is there an outcome that improves outcome 7 neither player has an ineentiye to diyerttrom dominant strategy without disadvantaging any group l1Allcea umesEubexec ssamestratEgyasnelsnuw snewlllurlly U l I U ss iose more by snttehino llkewse tuv ah e imagine this as a loeal optimum in outeome spaee eachdlmenslunoluutcumESpacelsdlmenslunuia niayensenoiee any moyementnom dumlnam strme eouiionum in this Space results in WuVsE outcomes UniIrtfltnt How about 1 1 from refuse re Jse Page 3 Thus the dilemma Now we see the problem 7 Outcome 5 75 is Pareto dominated by outcome 7 t Tu achieye Pareto optimai outcome reguires diyergence rrom iocai optimum at strategy eguiiipnum rTough situation Pareto optimai wouid be nice but it is unlikely since each playerrisks iosing more Nash Equilibrium John Nash studied game theory in 1950s 7 Proyed that eyery game has an equii briurn it here is a set or strategies With the propertythat no piayer can penerit p changing her strategy whiie the other players keep their strategies unchanged thent at set or strategies and the corresponding payoffs constitute the Nash Eguiiipnum eAll dominant strategies are Nash equilibria Another game 7 Hardware manuracturer chooses between co and DVD rormat fornext game piatrorm e Soltware manuracturerchooses between co and DVD rormat fornexttitle r 1 ti 3 No dominant strategy 7 yenry that there is no dominant strategy Yet two Nash equilibria exist Outcome 1 DVD DVD 9 9 Outcome 2 CD CD 5 5 B B A If either player unilaterally changes strategy that player will be worse 0 We still have a problem Two Nash equlibria but which is selected 7 irpiayers rail to select same strategy both will lose they couid agree to seiect the Pareto optimai soiution e that seems reasonable they couid coordinate Page 4


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

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

Jim McGreen Ohio University

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

Anthony Lee UC Santa Barbara

"I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."


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

Become an Elite Notetaker and start selling your notes online!

Refund 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


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:

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

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.