DOC PREVIEW
Stanford CS 157 - Lecture Notes

This preview shows page 1-2-3-22-23-24-44-45-46 out of 46 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

PowerPoint PresentationGame PlayingGeneral Game PlayingTechnologyKnight-Zone ChessBughouse ChessCompetitive GamesSingle Player “Games”VersatilityAnnual AAAI GGP CompetitionOther Games, Other WinnersCarbon versus SiliconSlide 13Single Player Game as a State MachineComposite Actions for Multiple PlayersDirect DescriptionTic-Tac-ToeNo Built-in AssumptionsGame ManagerGame Playing ProtocolSlide 21LogicState RepresentationLegality ComputationUpdate ComputationGame Tree ExpansionGame Tree SearchResource LimitationsIncremental SearchNon-Guaranteed Evaluation FunctionsAAAI-06 Final - Cylinder CheckersSlide 32Automatic ProgrammingGuaranteed Evaluation FunctionsHodgepodgeDouble Tic-Tac-ToeGame ReformulationDelayed GratificationSlide 39General Game Playing is not a gameTabula RasaUsing What We LearnJohn McCarthyEd FeigenbaumRobert HeinleinSlide 461/542/54Game PlayingHuman Game Playing•Intellectual Activity•Skill ComparisonComputer Game Playing•Testbed for AI•Limitations3/54General Game PlayingGeneral Game Players are systems able to play arbitrary games effectively based solely on formal descriptions supplied at “runtime”.Translation: They don’t know the rules until the game starts.Additional Complexities: uncertainty (moves of other players) resource bounds (game clock)4/54TechnologyUnlike specialized game players (e.g. Deep Blue), they do not use algorithms designed in advance for specific games.Artificial Intelligence Technologies knowledge representation reasoning, reformulation, learning rational behavior w/ uncertainty, resource bounds5/54Knight-Zone Chess6/54Bughouse Chess7/54Competitive Games8/54Single Player “Games”acbQuickTime™ and aTIFF (Uncompressed) decompressorare needed to see this picture.9/54VersatilityQuickTime™ and aTIFF (Uncompressed) decompressorare needed to see this picture.10/54Annual AAAI Competition Held at AAAI conference Administered by Stanford (Stanford folks not eligible to participate)Reward 2005 - winner Jim Clune of UCLA 2006 - Stephan Schiffel and Michael Thielscher 2007 - Yngve Bjornsson and Hilmar Finsson 2008 - Yngve Bjornsson and Hilmar FinssonAnnual AAAI GGP Competition11/54Other Games, Other Winners12/54Carbon versus Silicon13/54General Game Description14/54Single Player Game as a State Machines3s2s5s6s8s9s4s7s10s1s11baa d b ca b aba a b b aa a c d b15/54Composite Actions for Multiple Playerss3s2s5s6s8s9s4s7s10s1s11bbbaaabb abbaaaab aaababaa aaabaabb aa bbba ab16/54Direct DescriptionSince all of the games that we are considering are finite, it is possible in principle to communicate game information in the form of transition graphs.Problem:Size of description. Even though everything is finite, the graphs can be large.Ideas: 1. Different Conceptualization 2. Compact Encoding17/54Tic-Tac-Toeinit(cell(1,1,b))init(cell(1,2,b))init(cell(1,3,b))init(cell(2,1,b))init(cell(2,2,b))init(cell(2,3,b))init(cell(3,1,b))init(cell(3,2,b))init(cell(3,3,b))init(control(x))legal(P,mark(X,Y)) :- true(cell(X,Y,b)) & true(control(P))legal(x,noop) :- true(control(o))legal(o,noop) :- true(control(x))next(cell(M,N,P)) :- does(P,mark(M,N))next(cell(M,N,Z)) :- does(P,mark(M,N)) & true(cell(M,N,Z)) & Z#bnext(cell(M,N,b)) :- does(P,mark(J,K)) & true(cell(M,N,b)) & (M#J | N#K)next(control(x)) :- true(control(o))next(control(o)) :- true(control(x))terminal :- line(P)terminal :- ~opengoal(x,100) :- line(x)goal(x,50) :- drawgoal(x,0) :- line(o)goal(o,100) :- line(o)goal(o,50) :- drawgoal(o,0) :- line(x)row(M,P) :- true(cell(M,1,P)) & true(cell(M,2,P)) & true(cell(M,3,P))column(N,P) :- true(cell(1,N,P)) & true(cell(2,N,P)) & true(cell(3,N,P))diagonal(P) :- true(cell(1,1,P)) & true(cell(2,2,P)) & true(cell(3,3,P))diagonal(P) :- true(cell(1,3,P)) & true(cell(2,2,P)) & true(cell(3,1,P))line(P) :- row(M,P)line(P) :- column(N,P)line(P) :- diagonal(P)open :- true(cell(M,N,b))draw :- ~line(x) & ~line(o)18/54No Built-in AssumptionsWhat we see:next(cell(M,N,x)) :- does(white,mark(M,N)) & true(cell(M,N,b))What the player sees:next(welcoul(M,N,himenoing)) :- does(himenoing,dukepse(M,N)) & true(welcoul(M,N,lorenchise))19/54Game ManagerGame ManagerGameDescriptionsMatchRecordsTemporaryState DataPlayerGraphics forSpectators. . .. . .Tcp/ip20/54Start Manager sends Start message to players Start(id,role,description,startclock,playclock)Play Manager sends Play messages to players Play(id, actions) Receives plays in responseStop Manager sends Stop message to players Stop(id, actions) Game Playing Protocol21/54General Game Playing22/54LogicPossible to use logical reasoning for everything Computing legality of moves Computing consequences of actions Computing goal achievement Computing terminationEasy to convert from logic to other representations Simplicity of logical formulation Simple, widely published algorithms 3-4 orders or magnitude speedup no asymptotic change23/54State Representationcell(1,1,x)cell(1,2,b)cell(1,3,b)cell(2,1,b)cell(2,2,o)cell(2,3,b)cell(3,1,b)cell(3,2,b)cell(3,3,x)control(black)XOX24/54Legality Computationlegal(W,mark(X,Y)) :- cell(1,1,x) true(cell(X,Y,b))  cell(1,2,b) true(control(W)) cell(1,3,b)cell(2,1,b)legal(white,noop) :- cell(2,2,o) true(cell(X,Y,b))  cell(2,3,b) true(control(black))cell(3,1,b)cell(3,2,b)legal(black,noop) :- cell(3,3,x) true(cell(X,Y,b))  control(black) true(control(white))Conclusions: legal(white,noop) legal(black,mark(1,2)) … legal(black,mark(3,2))25/54Update Computationcell(1,1,x) cell(1,1,x)cell(1,2,b) cell(1,2,b)cell(1,3,b) cell(1,3,o)cell(2,1,b) black cell(2,1,b)cell(2,2,o) cell(2,2,o)cell(2,3,b) mark(1,3) cell(2,3,b)cell(3,1,b) cell(3,1,b)cell(3,2,b) cell(3,2,b)cell(3,3,x) cell(3,3,x)control(black) control(white)next(cell(M,N,o)) :- does(black,mark(M,N)) & true(cell(M,N,b))26/54Game Tree ExpansionXO XO XOXO XO XOXXO XO XOXXO XO XOX27/54Game Tree SearchXO XOXO XO XOXXO XO XOXXO XO XOXXO XO XOXO XO XXO XOXXO XOXXO XOXXO XOX28/54Resource LimitationsLarge state spaces ~5000 states in Tic-Tac-Toe ~1044 states in ChessLimited Resources Memory Time (start clock, move clock)29/54Incremental SearchIncremental Search Expand Game Graph incrementally As much as time allows Minimax/etc. evaluation on non-terminal states using an evaluation function of some sortBut how do we evaluate non-terminal states?In traditional game playing, the rules are known in advance, and the programmer can


View Full Document

Stanford CS 157 - Lecture Notes

Documents in this Course
Lecture 1

Lecture 1

15 pages

Equality

Equality

32 pages

Lecture 19

Lecture 19

100 pages

Epilog

Epilog

29 pages

Equality

Equality

34 pages

Load more
Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?