[MUSIK SPELA] Speak: Välkommen tillbaka, alla. Detta är CS50. Och i dag har vi en hel del intressanta saker att prata om. Men först måste jag påminna dig om några administrativa saker. Den här veckan är quiz en, onsdag eller för Yale sektionen på tisdagar och torsdagar, på torsdag. Det finns frågesport omdömen ikväll på Yale, från 5:30 till 7:00. Vid Harvard, spelade de en igår. Och alla kan titta på det på nätet. Även denna vecka eller i början av nästa vecka, vi har vår sista CS50 föreläsning. [Groans] Jag vet. Det kom så snart. Yale studenter kommer att ha en levande föreläsa här i juridisk fakultet auditorium på fredag. Det kommer att bli tårta. Harvard studenter kommer att ha sista föreläsning i Sanders på måndagen. Det kommer också att kakan. Även denna vecka på fredag, för dem av er som kommer till New Haven, Vi har CS50 Expo. Vi har mer än 30 olika grupper registrerade att visa dig allt från autonoma segelbåtar, till system som känner igen digitala porträtt, till datorn musik och datorproducerade musik. Så snälla gå med oss. Jag tror att det kommer att vara en bra tid. Idag, men vi får fortsätta prata om AI, om artificiell intelligens. Och en av de saker som vi kommer att komma till idag är idén om hur man använda AI att lösa problem. Nu, som alltid, låt oss börja med något enkelt. Och vi kommer att börja med en enkel idé. Och det är med sökord. Så tänk för ett ögonblick att jag har en uppgift som jag behöver för att utföra. Och jag skulle vilja ha denna uppgift automatiseras av vissa program agent. Föreställ dig att jag försöker boka en uppsättning på flyg från, låt oss säga, Boston till San Francisco. Jag kunde gå igenom och jag kunde använda en av de underbara online-sökning verktyg, som kommer att göra princip samma process som vi är kommer att gå igenom i dag. Men om du inte har det verktyg, vad skulle du göra? Tja, kan du titta och se och säga, jag är i Boston. Vilka flygningar är tillgängliga för mig? Nu kanske jag har tre eventuella flygningar av Boston som passar den tid när jag måste lämna. Jag kunde flyga till Chicago. Eller jag kunde flyga till Miami. Eller jag kunde flyga till New York. Jag kunde då se från varje en av dessa destinationen städer och tänka på vad platser Jag skulle kunna nå från var och en av dessa enskilda städerna. Så kanske från Chicago, kan jag få ett direktflyg till San Francisco. Det är utmärkt. Eller jag kunde få en flygning till Denver. Nu kanske det flyg till San Francisco är den perfekta lösningen för mig, men kanske inte. Kanske jag letar efter något det är lite billigare eller lite bättre för mitt schema. Och så jag kunde leta efter vad andra möjligheter kan vara ute. Så jag kunde titta på Denver. Och från Denver, ja, kanske Jag kan få en flygning till Austin. Och från Austin, kanske jag kan få en flyg till Phoenix, och från Phoenix till San Francisco. Nu, jag är inte klar än. Eftersom kanske det finns en direktflyg från New York San Francisco som är perfekt för mig. Eller kanske det finns en flygning från Miami genom Denver som är mycket billigare. Så jag har fortfarande att gå. Och jag har fortfarande att titta på alla de städer som jag inte har undersökt ännu. Jag måste uttömmande kontrollera alla de möjligheter som jag kan ha. Så från New York, kanske jag kan få en flyg till Nashville, och från Nashville till Austin. Och då jag vet var jag är. Och då jag vet från Austin, jag kan flyga till Phoenix, och från Phoenix till San Francisco. Om jag flyger först till Miami, men, kanske jag kan få en flygning från Miami till Nashville, eller från Miami till Austin. Och nu har jag provat alla av möjligheterna. Jag har byggt upp denna graf som visar mig alla möjliga vägar att jag skulle kunna ta. När vi representerar dessa typer av problem, Vi kommer inte att representera dem uttryckligen som denna graf, eftersom den grafen representerar inte historia där vi har gått. Att veta att jag flög från Phoenix till San Francisco inte tala om för mig om jag kom via Nashville, eller via Denver, eller via Miami. Så vad jag ska göra i stället är Jag tar samma problem, och jag ska representera det som ett träd. Och vid roten av trädet, vid top, ska jag lägga den plats som jag började, Boston. Och från Boston, kommer jag att titta på alla möjliga platser att jag kan resa till. Tja, i det här fallet, hade jag tre, Chicago, New York och Miami. Och då ska jag undersöka var och en av dessa barn i trädet. Från Chicago, jag såg att jag hade två flygningar. Jag kunde flyga direkt till San Francisco eller Denver. Nu San Francisco, det är mitt mål. Det är mitt mål. Det kommer att bli ett löv av det här trädet. Det vill säga, jag kommer aldrig att gå någonstans efter San Francisco. Från Denver, dock, Jag kan flyga från Denver Austin, från Austin till Phoenix, och från Phoenix till San Francisco. Och nu igen, har jag nått ett löv. Jag kunde sedan gå tillbaka till nästa stad som jag inte till fullo har utforskat. Det skulle vara New York, gå tillbaka upp till toppen av mitt träd, komma ner till New York. Från New York, kan jag flyga till Nashville, från Nashville till Austin, från Austin till Phoenix, och från Phoenix till San Francisco. Och slutligen, en stad jag har inte tittat på ännu, Miami. Tja, från Miami jag sa att jag hade två möjligheter, Nashville eller Austin. Om jag flyger till Nashville, ja då flyger jag från Nashville till Austin till Phoenix, till San Francisco. Om jag flyger till Austin, jag flyger Austin, till Phoenix, San Francisco. Och nu har jag ett träd. Det är en komplett träd. Det är alla de möjligheter och alla de banor som jag kunde ta. Det är, om jag börjar på roten av trädet på toppen och jag gå ner till en av de blad, det säger mig inte bara där jag ska hamnar, San Francisco, men det säger mig den väg som Jag behöver ta för att komma dit. Nu är som en av dessa bäst? Tja, ingenting om detta Problemet berättar ännu vilka av dessa är den bästa lösningen. Kanske jag bryr mest om hur mycket tid jag är i luften, eller avståndet som jag flyger. I så fall, Chicago till San Francisco kan vara den kortaste nummer av miles i luften. Jag kanske bryr sig om kostnaden. Och vi vet alla direktflyg är oftast dyrare. Så kanske om jag tar detta typ av bakåt rutt genom Miami, Nashville, Austin, Phoenix, kanske sedan Jag får ett lägre pris. Men jag kunde optimera på någon kriterier som jag bryr mig om. Vem har bäst i flyg Wi-Fi, eller som flygplatserna har den bästa mat tillgänglig. Och vart och ett av de kanske ge mig en annan lösning som jag ser som den bästa. Dessa typer av problem, där vi ska att bygga ut detta träd av möjligheter, och sedan titta på var och en av dem enskilda vägar, och undersöka vilken av dessa uppfyller ett kriterium för oss, vi ska ringa dessa sökproblem. Och vi har massor av algoritmer, av vilka Vi har redan sett, att gå och utforska dessa träd. Vi kan göra det på det sätt som jag bara gjorde en djup första sökning, gå ner så långt som vi kan tills vi slå ett löv, och sedan komma tillbaka, och gå tillbaka ner. Eller vi kunde göra vad som är kallas bredden-först sökning. Vi kunde expandera allt vid toppen, och sedan allt en rad därunder, och sedan allt en rad under det. Dessa sökträd är grundläggande för AI. Men de vet inte riktigt får det rätt hela tiden. I själva verket, i många av fallen att vi verkligen bryr oss om, vi vill bygga ett träd, men vi egentligen inte få göra alla beslut. Dessa är situationer som kallas kontradiktoriskt sökning, även känd som hur man skriver spelande system och få betalt för det. Men det är dessa typer system där jag kanske får välja när jag går från Boston, vilken stad jag gå vidare till nästa. Men efter det, skulle någon annan få att fatta beslut om var jag flyga. Så för att bygga dessa typer strukturer, vi är kommer att behöva ta en något olika förhållningssätt till det. Vi kommer inte att kunna bara söka igenom trädet längre, eftersom vi inte den som är i kontroll var och en av dessa beslutspunkter. Så låt oss föreställa oss en enkel spel som Tre i rad. Jag kan börja med en helt tom kartong. Och i Tre i rad, X får spela först. Och så jag kunde tänka på alla möjliga drag att X skulle kunna göra. Och om jag är en spel X, det är bra. Jag har nio möjliga flyttar jag kan göra. Jag skulle kunna sätta ett kryss i någon av dessa nio positioner. Och sedan från vart och ett av dem, jag kunde föreställa sig vad som händer härnäst. Jo, i detta fall, den andra spelare skulle få ta en sväng. O skulle få ta en sväng. Och från vart och ett av dem, det skulle vara åtta olika platser att O kan placera sin markör. Låt oss säga att jag bestämde att jag var kommer att sätta ett kryss i mitten. Det verkar alltid som en bra öppning drag. Jag kan titta på undersidan att den åtta möjliga drag att O gör. Nu, om jag spelar X, det är underbart. Jag får välja vilka jag gå till, en i mitten. Men nu O får välja. Och jag har inte kontroll över detta beslut. Men från var och en av dem möjliga styrelseuppdrag, det finns sedan en annan uppsättning av möjligheter. När det kommer att vara Min tur igen, skulle jag får välja och säga, ja, om O flyttar in, ja, mitten plats på vänster, sedan Jag har en uppsättning av möjligheter där jag kan ta min nästa drag. Från dem, skulle jag överväga alla möjligheterna under dem. Och sedan O skulle få att välja bland dem. Och jag kunde hålla bygga denna träd tills jag kom till en punkt där antingen någon vinner game-- som är fick betraktas som en leaf node-- eller styrelsen är helt full och ingen har vunnit. Och det kommer också att bli en lövnod. Det kommer att bli en slips. Men knepig sak med detta är om detta var bara en vanlig sökning problem, skulle jag kunna säga, ja, X bör gå hit. Och O skulle gå vägen dit. Och sedan X bör gå hit. Och sedan O bör gå vägen dit. Och sedan X kan få tre i rad, och jag vinner. Och spelet skulle vara över i fem drag, tre för mig, två för min motståndare. Men jag vet inte alltid får välja det. Så istället, vad vi är kommer att behöva göra är vi kommer att ha att ha en ny strategi. Och den strategi som spel-playing algoritmer använder ofta är vad som kallas minimax. Den centrala idén om Minimax är att vi är kommer att plocka drag som ger våra motståndare värsta möjliga mängd drag att de kan göra. Det gör inte mig något bra att välja ett drag där Jag skulle kunna vinna efter det, eftersom min motståndare är inte kommer att ge mig den chansen. De kommer att välja några fruktansvärda utfall för mig. Så jag kommer att göra flytta som tvingar min motståndare att göra något bättre för mig. Okej. Låt oss se hur det utspelar sig. Så här är vår algoritm i pseudokod. Vi kommer att generera hela spelträdet. Vi kommer att bygga hela strukturen. Och sedan ska vi gå igenom. Och längst ner vid var och en av terminalnoder, vid var och en av bladen, Vi ska utvärdera hur värdefullt är det för mig? Och vi kommer att värdera saker som är bra för mig som positivt. Saker som inte är bra för mig kommer att vara mindre positiv, eller noll, eller till och med negativ. Så i Tre i rad, kanske en vinst för mig är bra. Det är en en. Och en slips är noll. Och något som är en förlust för mig, kanske det är en negativ. Allt som räknas är att ju bättre Det är för mig, desto högre poäng den tar emot. Från dessa möjligheter på botten, sedan kommer vi filtrera uppåt. Och när det är min chans att välja bland ett antal alternativ, Jag ska välja det som är fick den högsta poängen. Och när det är min motståndare vända sig till välja, Jag antar att de kommer att välj en med den lägsta poängen. Och om jag gör det hela vägen upp till toppen av trädet, Jag har valt en väg som ger mig det bästa resultatet som jag kan få, förutsatt att min motståndare gör alla rätt drag. Okej, så låt oss se detta i aktion först. Och sedan ska vi faktiskt titta på koden för den. Så tänk Jag har denna stora träd. Och nu jag inte spelar Tre i rad. Jag ville ge dig något lite rikare. Så jag har lite spel där det finns många olika poäng att jag kunde ha i slutet. Och så jag bygga denna kompletta träd. Och jag får gå först. Jag är vid roten av trädet. Och jag får välja that-- så får jag att maximera över denna första noden. Och sedan min motståndare får gå. Och då får jag gå en gång. Så nere på botten, jag har en uppsättning av möjligheter som jag kan välja mellan, olika terminal tillstånd av spelet. Om jag i det långt vänstra hörnet, och jag ser att jag har ett val mellan en åtta, en sju, och en två, Tja, jag är den som får välja. Så jag kommer att välja den bästa av dem. Jag kommer att välja åtta. Så jag vet att om jag någonsin komma ner till den punkten, Jag kommer att kunna få det åtta poäng. Om jag hamnar på nästa punkt över, nästa nod över, en nio, en, eller en sex, ja, jag är kommer att välja den bästa av dem. Jag ska välja nio. Om jag har ett val mellan två och fyra och en, Jag ska välja fyra, den högsta. Nu, om jag tittar på den nivå ovanför det, min motståndare är man får göra det valet. Så min motståndare får välja, vill jag ge honom det som händer att få honom åtta poäng, eller måste jag ge honom det som är kommer att ge honom nio poäng, eller det som händer att ge honom fyra poäng? Och min motståndare, är rationell, går att välja ett minimum av dem, kommer att välja fyra. Och jag kan göra detta genom hela trädet. Jag kan gå ner till den mitten uppsättning av tre. Och jag kan välja mellan en, tre och fem. Och jag får välja. Så jag väljer en fem. Jag kan välja tre, nio, eller två. Jag får välja, så väljer jag nio. Sex, fem, eller två, jag väljer. Jag får välja sex. Nivå över det, vem som får välja? Vem får välja? Den andra killen, min motståndare. Så de väljer fem, nio eller sex, som en? PUBLIK: De fem. Speak: De väljer de fem. De får välja ett minimum. Och sedan sist, välja en, två, eller tre. Jag får välja, så jag väljer tre. Nio, sju, eller två, jag väljer nio. Och 11, sex eller fyra, jag väljer 11. Min motståndare väljer sedan tre, nio, eller 11, väljer ett minimum. Han ger mig en tre. Och sedan slutligen på toppen av trädet, jag får välja igen. Och jag får välja mellan en fyra, fem eller tre. Så jag tar fem. Om jag fick styra allt, skulle jag ta stigen som ledde till 11. Men jag får inte göra det valet. Om jag går ner den vägen. Min motståndare kommer att tvinga mig in det val som leder till en tre. Så det bästa som jag kan göra är att ta den mellersta grenen, göra det val som är till slut kommer att leda mig till fem poäng. Det är vad minimax gör. Okej. Låt oss ta en titt på det. Så här i CS50 IDE är ett program som implementerar Minimax att spela Tre i rad. Vi kommer att bygga upp en representation. Vi kommer att ha två opponent-- eller två spelare, vår dator spelare och en mänsklig spelare. Spelar nummer ett kommer att spela O. Det ska vara maskin spelaren. De får flytta andra. Och den andra spelaren, vår mänsklig spelare, blir X. Och för att göra mitt liv liten enkel, jag kommer för att märka den spelaren negativa ett. Så jag kan bara föröka genom negativ en att byta mellan en spelare och den andra. Okej, så låt oss ta en titt på vad vi egentligen ska göra. Vi kommer att definiera vår styrelse. Det kommer att vara bra, vi kommer att låta det vara tre av tre, eller vi kan även spela fem av fem eller sju med sju Tre i rad om du skulle som, baserat på några dimension D. Och vi kommer att ha ett par av hjälparfunktioner som kommer att göra saker som initiera Screen-- eller ledsen, initiera våra variabler, rensa skärm, rita styrelsen på skärmen, en som kontrollerar en styrelse för att se huruvida det finns en vinnare, en som tolkar via kommandoraden, bara för att hjälpa till, en som läser in input, och en funktion som kallas minimax. Och det är en vi bryr oss mest om. Men låt oss först titta på de viktigaste. Vad gör vi? Tja, ska vi tolka vår kommandorad, bara läsa in och se vad dimension pension vi skulle vilja ha. Vi kommer att initiera vår styrelse. Och då kommer vi in ​​ett stora vilda slingan, vid upprepade tillfällen acceptera flyttas tills spelet är vann, eller det finns några drag kvar. Varje gång vi går igenom det loop, kommer vi rensa skärmen. Vi kommer att dra ombord på skärmen. Och vi är medvetet sorts abstrahera bort dessa som subrutiner, så att vi inte behöver oroa sig alltför mycket om detaljerna i hur de inträffar. Du har koden senare i dag. Och om du vill titta igenom och ta reda på, du kan se dem alla. Men vi ska dra en styrelse på skärmen. Och sedan ska vi kontrollera och se, vi har en vinnare? Har någon vunnit det här spelet? Om de har, kommer vi att skriva ut en seger meddelande. Och vi kommer att avsluta spelet. Vi kommer även att kontrollera och se om det finns en slips. Det ska vara lätt att se om det finns en slips. Det betyder att alla områden är fulla, men det har inte varit en vinnare än. Vi kan förklara en slips och göras. Då den verkliga meat-- om Det är en maskin spelare, Vi kommer att göra det möjligt att maskin spelare att söka genom att använda denna minimax algoritm, att hitta det bästa draget att det kan. Och sedan ska vi sätta som rör sig upp. Annars om det är en mänsklig spelare, Vi ska läsa lite input från människa. Och därefter om det är den mänskliga spelare eller maskinen spelare, Vi kommer att göra ett par lite bitar av felkontroll, se till att det håller sig inom gränserna av de faktiska dimensionerna hos brädan att vi har, se till att det utrymmet är tomt, att ingen ens sätta en bit i det redan. Och sedan kommer vi bara sätta en pjäs på brädet, ändra spelaren till nästa lager, och öka hur många flyttar har hänt. Det är huvudslingan för vår Tre i rad spel. Minimax är då exakt den algoritm som vi tidigare. Den enda justering som Vi har gjort så att vi kan spela högre dimensionella styrelser är vi har hålls denna extra parameter som kallas djup. Och djup bara säger, om jag söka nedåt genom det trädet och jag får så långt ner utöver en viss nivå djup att jag bara inte vill att gå vidare, Jag kommer att stanna upp och bara utvärdera styrelsen vid den punkten. Jag ska kolla och se om det finns en vinnare. Om det finns en vinnare, jag tillbaka dem. Annars kommer jag att gå igenom en slinga. Och jag ska säga, för alla möjliga platser att jag kunde möjligen ta så min flytt, jag bygga en hypotetisk bräda som innehåller min flytt på kortet, och sedan rekursivt anropar minimax. Om det är min flytt, jag får hitta en som har fått den största poängen. Om det är min motståndares drag, finner vi den som har fått den lägsta poäng. Och allt annat är bara bokföring. Okej, så låt oss se denna körning. Egentligen kanske vi kan få ett par frivilliga att komma upp och spela Tre i rad. [OHÖRBAR] en och en mer, två, precis där. Kom upp. Så låt oss gå vidare och starta om helt. Så, hej. PUBLIK: Hej. Speak: Vad heter du? PUBLIK: Gorav. Speak: Gorav. PUBLIK: Jag är Layla. Speak: Och Layla och Layla, sorry. Kom upp. Gorav, vi kommer att ha dig gå först. Och jag kommer att be er att vara en icke fruktansvärt bra Tre i rad spelare. OK, så all press är avstängd på dig. Låt oss se, men att vår maskin spelare kan faktiskt göra något smart. Så gå vidare. Du kommer att skriva in som samordnar du vill sätta din X. A0, OK, och maskinen har gått direkt och sätter sin prägel på A1. Placera O på tavlan. Okej, nu gå vidare. Vart skulle du vilja gå? C2. Vår maskin spelare har tagit i mitten torget, blockerat dig. Så det var en bra, smart sak för att det ska göra. Du har blockerat det. Det är utmärkt. Det tar hörnet där. Och det kommer att tvinga dig att ta en sista plats, B0. Och matchen slutar oavgjort. Men det spelade en rimlig match mot dig, eller hur? Okej, tack så mycket, Gorav. [APPLÅDER] Okej, Layla, vi kommer upp spelet på dig här. Målgrupp: Åh, bra. Speak: Vi kommer att ge du fyra av fyra Tre i rad. Nu, i fyra av fyra, måste du vinna med fyra i rad, inte tre i rad. Och det är din. Så Layla tog D1. Vi bevakar nu kommer att följa vår dator spelare här. Tre av tre tic-tac-toe är den typ saker som är lätt för oss alla. Men det är ändå trevligt att se datorspelare att göra smarta drag. Fyra av fyra får vara lite svårare. Snyggt gjort. Okej, så Layla är avslutade. Åh, och vi borde ha tagit slut där. Men låt oss göra ett mer här uppe. Så Layla, tack. Snyggt gjort. [APPLÅDER] Så vår Tre i rad spelare går genom och finner platser, löser dem med denna minimax. Och jag hade en djupinställning på den, så att den skulle inte köra för fort, vilket förmodligen är anledningen Layla kunde gå fint i förväg som hon gjorde, och gjorde mycket bra. Men dessa system som bara gå igenom och råstyrka gå djupare och djupare, och djupare, och hålla hitta lösningen att de behöver dessa typer av system är ganska framgångsrika på dessa, ja, vanliga brädspel. Och i själva verket, om vi tittar på en tre med tre Tre i rad spel, detta är i grunden en löst problem. Och detta är en underbar diagram från Randall Munroe på XKCD, visar vilka flyttar du bör ta, med tanke på din motståndares drag. Detta är något som vi kunde enkelt ange i förväg. Men vad som händer när vi får mer komplexa spel, mer intrikata spel, där det finns större styrelser, mer möjligheter, djupare strategi? Det visar sig att detta brute force söka fortfarande gör ganska bra, utom när du kommer till den punkt där trädet är så stort att du inte kan representera allt. När du inte kan beräkna hela trädet, när du inte kan gå framåt och tryck själv till den punkt där du har fått hela trädet i minnet, eller om du kan få det i minnet och det kommer bara ta dig alldeles för lång tid att söka igenom det, måste du göra något smartare. För att göra det, du måste göra två saker. Först måste du hitta några sätt att begränsa din djup. Tja, det är OK. Vi kan hitta några trevliga, minimum och säga, du kan bara gå så djupt. Men när du gör det, betyder att du har dessa delvis ofullständiga styrelser. Och du måste välja, jag gillar detta delvis ofullständig styrelse, eller detta delvis ofullständiga ombord? Och på våra fyra av fyra Tre i rad spel, vår dator spelare kom ner till botten och det sa, Jag har två olika styrelser. Varken ett är en seger. Varken ett är en förlust. Varken ett är en slips. Hur väljer jag mellan dem? Och det inte har en smart sätt att göra det. Vi ser den här typen av utvärderingen sker hela tiden som vi får in mer komplexa spel. Chess är ett bra exempel. I schack, vi har, först av allt, en större bräda. Vi har betydligt fler bitar. Och placeringen av dessa bitar och det sätt som dessa bitar flytta är mycket viktigt. Så om jag vill använda minimax, Jag måste kunna ange och säga, detta forum, där ingen har vunnit eller förlorat ännu, är något bättre än denna andra styrelse, där ingen har vunnit eller förlorat. För att göra det, kan jag göra saker som jag kanske bara räkna hur många bitar har jag och hur många bitar har du? Eller jag kan ge olika pieces olika punkter. Min drottning är värd 20 poäng. Din bonde är värda en poäng. Vem har fler poäng totalt? Eller jag kanske överväga saker som, som har fått bättre styrelsen position? Vems tur är det nästa, något som jag kan göra för att mer exakt utvärdera vilken av dessa möjligheter är bättre utan uttömmande väger varje rörelse som kan komma efter det. Nu för att göra detta arbete, en av de saker som är kommer att bli mycket viktigt för oss är inte bara flytta rakt ned till ett visst djup gräns, men att kunna säga, en av dessa idéer som jag har är så dåligt att det är inte värt att överväga alla möjliga sätt att saker och ting kan gå från dåligt till värre. För att göra det, kommer vi att lägga in minimax en princip som kallas alph-beta. Och alfa-beta säger, om du har en dålig idé, slösa inte din tid på att försöka ta reda på exakt hur illa det är. Så här är vad vi ska göra. Vi kommer att ta samma principer som vi hade tidigare, samma minimax typ av sök, bara vi är kommer hålla koll, inte bara i förhållande faktiska värden som vi har, men vi ska hålla reda på den bästa möjliga värde som jag kunde få, och sämsta möjliga utfall jag kunde ha. Och varje gång det värsta möjliga sak ser sannolikt, Jag ska överge denna del av trädet. Och jag kommer inte ens bry titta på det längre. Okej, så föreställa sig att vi börjar med samma exakta spelträdet. Och nu ska vi gå ner igen, hela vägen ner till det nedre vänstra hörnet. Och i det nedre vänstra hörnet, vi titta och vi utvärderar detta forum. Kanske är det en fyra av fyra Tre i rad ombord, eller kanske är det ett schackbräde. Men vi ser på det, och vi utvärderar det, och vi får ett värde på åtta. Vid den tidpunkten, vi vet att Vi kommer att få åtminstone åtta poäng från denna botten beslut. Det spelar ingen roll vad den andra två är att sju och att två. De kan vara några värden de ville vara. Vi kommer att komma åt minst åtta poäng. Okej, men vi kunde gå vidare och kolla. Kanske en av dem är bättre än åtta. Vi tittar på sju. Är det bättre än åtta? Nej, det ändrar vår åsikt alls. Vi tittar på de två. Är det bättre än åtta? Nej, det ändrar vår åsikt alls. Så nu vet vi att vi har uttömt alla möjligheter där. Vi kommer inte att få något bättre än åtta. Vi kommer att få exakt åtta. Och så vi ändra på det nod och säg, är det nu en visshet. Vi går upp en nivå ovanför det. Och nu vet vi något om det minimering nivå. Vi vet att vi aldrig kommer att få mer än åtta poäng om vi går ner den riktningen. För även om de två andra grenar sig att vara fantastiskt och värt tusentals poäng vardera, vår motståndare kommer att ge oss minimum, och ge oss åtta. Okej, låt oss se. Vi kommer att fortsätta på den inslagna vägen. Vi går ner till den mitten till vänster. Vi tittar ner och vi ser att det finns en nio. Vi vet att vi kommer att få åtminstone nio poäng genom att gå ned den mellersta vägen. Och på denna punkt, kan vi bara pausa. Och vi kan säga, titta, jag har nivån ovanför, Jag kommer att få mer än åtta pekar genom att gå ned denna riktning. Men om jag gick i mitten bana i stället för vänster väg, Jag skulle få minst nio poäng. Min motståndare aldrig kommer att Låt mig gå den medelväg. De får välja. Och de kommer att välja sökväg till vänster mot åtta, snarare än i mitten mot vad är minst nio poäng. Så på den punkten, ska jag sluta. Och jag ska säga, vet du vad? Jag behöver inte se någon mer ner i den riktningen. Eftersom jag aldrig kommer att komma dit. Jag kan hoppa över att man, och jag kan hoppa över att sex, eftersom det aldrig kommer att hända. Så jag ska gå ner och jag ska överväga nästa möjlighet. Jag åker dit ner och jag säger, jag ser en två. Jag vet inte om jag får här, jag är kommer att få åtminstone två. OK. Jag fortsätta. Jag ser en fyra. Jag vet att jag kommer att få minst fyra. Det finns fortfarande en hel del mellan fyra och åtta, men. Så jag fortsätta. Jag tittar ner och jag ser det finns en. Okej, jag vet om Jag går denna väg, Jag kommer att kunna välja fyra. Vad är min motståndare kommer att göra? Mellan något som ger mig åtta, något som ger mig fyra, och något som ger mig åtminstone nio, Tja, han kommer att ge mig fyra. Och jag vet nu på högst upp, jag ska att kunna få åtminstone fyra poäng av detta spel. Hela idén med alfa-beta är att skära av delar trädet så att jag inte titta på dem längre. Men det fortfarande ser ut som jag har varit tittar på en hel del av trädet. Låt oss hålla gå ned. Vi ska gå ner nästa nu. Nere på botten, jag hittar en. Jag vet att jag kommer att få åtminstone en. Jag hålla ute. Jag hittar en tre. Jag vet att jag kommer att få minst tre. Jag fortsätta. Jag hittar en fem. Jag vet att jag kommer att få fem om jag får ner i den vägen. Och jag vet också sedan att min motståndare, om jag välja mitten av de tre stora val, han kommer att ge mig något som är fem eller mindre. OK. Jag kan fortsätta där. Jag kan titta ner och jag kan säga, vad ska jag att få om jag går ner i medelväg? Jag kommer att få, väl, tre där. Jag kommer att få något som är minst tre. Det finns fortfarande saker mellan tre och fem, så jag hålla ute. Åh, en nio, jag ska definitivt ta det över en tre. Jag kommer att få minst nio om jag går ner den medelväg. Nu stannar och säger min motståndare, titta, det är ingen idé längre. Jag vet att min minimering motståndare, han kommer att ge mig det som är mindre än eller lika med fem, snarare än det som är större än eller lika med nio. Jag stannar. Jag ser inte något mer på det. Jag fortsätta. Jag tittar ner på detta. Ner till botten, jag hittar en sex. Jag vet att jag kommer att få minst sex. Och vad kan jag göra? Jag kan sluta. Eftersom det är ett val mellan något som är minst sex och något som är mindre än fem, han kommer att ge mig saken som är mindre än fem. Och nu vet jag att jag kommer att få exakt det valet. Jag kommer att få det fem val. Jag går tillbaka upp till toppen. Som jag kommer att välja mellan något det är större än eller lika med fyra, eller något som är lika med fem? Jag kommer att ta något som är minst fem. Jag går ner den sista banan, alla vägen ner till botten. Det finns en en. OK, åtminstone jag kommer att få en poäng. Jag fortsätta. Två, åh, det är bättre än en. Jag kommer att få åtminstone två. Jag hittar en tre. Jag vet att jag kommer att få tre. Och punkten ovan att min motståndare kommer ge mig något som är mindre än eller lika med tre. Och nu kan jag sluta. På grund i valet mellan att jag är kunna få en fem och min motståndare ge mig något mindre än tre, Jag kommer alltid att ta det fem. Så jag inte bedöma det nedre delen av trädet alls. Nu kan detta verka mindre. Men när små bitar av aritmetik, större än och mindre än, kan skära bort hela delar av detta exponentiellt växande träd, som leder till en enorm mängd besparingar, besparingar som är stora nog att jag kan börja spela konkurrenskraftigt fler komplexa spel. Okej, om vi tittar på storleken och komplexitet olika spel, Tre i rad var vår enkla exempel. Vi har en liten styrelse, tre och tre. Vi får på sin höjd, i genomsnitt cirka fyra olika val när vi går igenom spelet. Vi har någonstans runt 10 till femte möjliga olika blad. Och bygga en Tre i rad spelare, ja, bara vi gjorde det. Det är lätt. Om vi ​​går upp till något mer komplex, som Connect Four. Minns du det här spelet där du tappar de små polletter i? Det är en sex av sju ombord, inte så mycket större, fortfarande har ungefär samma förgrening faktor som Tre i rad. Jag har ungefär fyra val där jag kan lägga saker i. Men nu har jag fått en hel del mer leder, 10 till den 21: strömmen. Det är något som är lätt nog att vi lösa det direkt. Pjäser, mer complex-- du fick en åtta med åtta styrelse. Du är bara hälften av dem när som helst, dock. Du har en förgrening faktor som är ca 2,8. Tja, vi har ett par flyttar du kan ta. Du har cirka 10 till 31 blad, större och större, och större utrymmen. Som jag måste söka igenom de större och större utrymmen, det är då saker som alfa-beta och att kunna skära bort hela grenar blir avgörande. Nu, pjäser var lätt nog 1992. Ett datorprogram som kallas Chinook slå världs pjäser champion, Marion Tinsley. Och sedan dess, ingen mänsklig mästare spelare har kunnat slå de bästa beräkningssystem. Om vi ​​tittar på något som schack, nu igen, har vi en åtta med åtta styrelse. Men vi har mycket mer komplex bitar, mycket mer komplexa rörelser. Vi har en förgreningsfaktor av ca 35, 35 möjliga drag i genomsnitt att jag kan ta, och en stat utrymme, ett antal blad som har vuxit till 10 till 123. makt, enormt antal möjligheter. Även fortfarande moderna processorer har möjlighet att göra detta framgångsrikt. Under 1995 och sedan 1997, en dator program som heter Deep Blue byggdes av IBM som körde på en gigantisk superdator slå den nuvarande världsmästare, Garri Kasparov. Detta var en vändpunkt. Men i dag, samma behandling makt sitter på min MacBook. Behandlingshastigheten håller blir snabbare och snabbare. Vi kan utvärdera mer och mer styrelser snabbare och snabbare. Men ännu viktigare, har vi bättre utvärderingsfunktioner och bättre beskärning metoder. Så vi kan söka utrymmet mer komplext. Den största av styrelsen spel som vi kan tänka på, något liknande Go som är fick en 19 med 19 ombord, nu plötsligt är vi förbi den punkt där beräkningssystem kan vinna. Det finns ingen beräknings systemet där ute som kan slå en professionell Go spelare. Det bästa system idag rang det om den typ av god amatörnivå. Så det finns fortfarande en hel del ut det att du inte kan få ännu. Okej, dessa traditionella brädspel, dessa typer av system där vi bygga denna minimax, oavsett om det har fått alfa-beta eller ej, dessa algoritmer fungerar eftersom det finns vissa begränsningar. Vi har perfekt information om världen. Vi vet var alla bitar är. Världen är statisk. Ingen får flytta delar runt medan jag är sitter där och tänkte, tar min tur. Det finns en åtgärd utrymme som är diskret. Jag kan sätta min bonde här, eller jag kan sätta min bonde här. Jag är inte tillåtet att sätta min bonde på linjen mellan de två rutorna. Och slutligen, de åtgärder är deterministisk. Jag vet att om jag säger, torn till riddare tre, min torn kommer att hamna på riddare tre, så länge det är ett giltigt drag. Det finns ingen osäkerhet om det. Nu, när jag går till mer olika typer av spel, Vi måste bryta dessa antaganden. Vad händer om jag går till något som klassiska videospel? Här är ett urval av video spel från Atari 2600. Vad har jag där uppe? Jag har Frogger, Space Invaders, Fallgrop, och Pac-Man. Vilka typer av miljöer har jag här nu? Vilken av dessa antaganden måste jag bryta? Tja, det beror på spelet. Jag kunde spela schack på 2600, och det skulle vara precis som det var innan. För de flesta av dessa system, det finns fullständig kunskap om världen. Det är helt deterministiska åtgärder. Men oftast, världens inte längre statisk. Det är, medan jag sitter där väntar, är något som rör sig. De spöken kommer att få mig. Skorpionen följer mig under. Space Invaders är kommer närmare och närmare. Hur väl kan vi göra mot dessa? För några år sedan, Google hade ett projekt som kallas DeepMind, där de utbildade en dator program för att spela Atari 2600 spel. Och om du tror att detta är inte seriöst affärer, resultaten av sin studie publicerades i Nature, så nästan lika bra en publikation som man kan komma. Och här är hur väl de utfört. De har en algoritm som satt och tittade bara på skärmen ingångarna. Det fick inga instruktioner som helst om spelreglerna. Och det var tänkt att räkna ut, grundat sin värdering, hur bra det gjorde. Detta var ett system som används något kallas förstärkning lärande. Det vill säga, det såg ut på sin poäng. Och om det blev en bra poäng, sa det, Jag bör komma ihåg dessa saker. Och jag skulle göra dem igen. Och om det blev ett lågt betyg, sade det, Jag ska inte göra dessa saker igen. Detta är resultatet av dessa utbildade system tillåtet att spela för en några timmar på varje spel, jämförs med professionella spelare. Så för alla de spel som finns till den vänstra sidan av denna linje, denna själv utbildad datorprogram överträffade professionella spelare. Och för allt till höger, de professionella spelare fortfarande var bäst. För något som visste ingenting om reglerna, att visste ingenting om struktur spel, är detta imponerande prestanda. Och detta är vad vi kan göra i dag. OK, säger du, men om vi tänka AI i spel, normalt tror att vi om saker som vi kan faktiskt sitta ner och spela mot. Om jag sitta ner och jag spelar Starcraft, eller jag spelar gratis Sieve, datorn motståndare är person som kontrollerar Zerg, eller styra andra civilisationen. Hur gör de spelare faktiskt hitta sina drag? Tja, är dessa spel strukturerade ungefär på samma sätt som våra brädspel, dessa spel som vi kommer kollektivt kalla fyra X Games, utforska, expand-- glömma de. Vad är de? Utforska, expandera, och släcka, Jag tror är den sista. Men de är i grund och botten prospektering och erövra spel. Typiskt dator motståndare Det har begränsad information. De vet inte exakt vad som är pågår bakom dimma av krig. De får inte se vad du har i ditt lager. Det finns en miljö som är dynamisk. Allt förändras hela tiden. Du får inte sitta och vänta med att ta ditt drag. Men det mesta är fortfarande diskret. Jag måste sätta min stad här. Eller jag måste sätta min stad här. Och allt är deterministisk. När jag säger, flytta min enhet här, min enhet flyttar här, såvida inte ett hinder plötsligt kommer in i bilden. Nu, det är inte alla datorer spel som finns där ute idag. Om jag går och jag spelar en förstapersons typ spel, något som tjuv eller Fallout eller Skyrim eller halo, nu Jag har datormotståndare som är där ute som har en helt annan situation. De har återigen begränsad information. De kan bara se en vissa synfält. Miljön är fortfarande dynamisk. Saker förändras hela tiden. Men nu har jag en mycket mer kontinuerliga åtgärder utrymme. Jag kan bara kikar en lite av dörröppningen. Och vissa spel, min åtgärder är stokastiska. Jag får försöka hoppa över den där väggen, men jag har en chans att misslyckas. Dessa typer av spel närmar och närmare de typer av regulatorer att vi bygger inom robotik. Inom robotik, måste vi anta att vi har begränsad information. Vi har sensorer som berätta om världen. Vi har en ständigt föränderlig, dynamisk miljö. Vi har en värld där utrymmet är kontinuerlig, snarare än diskret. Och våra handlingar, när vi försöker dem, har en chans att misslyckas. Och faktiskt, moderna spel styrenheter för din Halo motståndare, eller för de NPC i Skyrim, i princip köra små robot arkitekturer. De känner världen. De bygger en modell av världen. De beräknar baserat på en uppsättning av mål som de skulle vilja genomföra. De planerar åtgärder baserade om vad de vet. Och de är exakt samma slag av system som vi bygger inom robotik. Så dessa arkitekturer, till föra samman den tillbaka, är ofta ganska lika. Så låt oss se om vi kan se det. Låt oss gå tillbaka till vår Tre i rad exempel. Och jag kommer att ställa ett par av mina postdocs att komma och hjälpa mig. Så Chen Ming, och Alessandro, och Olivier, om ni skulle komma. Och jag kommer att behöva ett par frivilliga OK, jag såg en hand upp till höger där i mitten. Låt mig ta ett ytterligare, någon vidare i ryggen kanske. Okej, där borta. Kom upp. Okej. Så låt oss ta ner som täcker. Och om ni skulle komma rätt tillbaka runt här för mig, fantastiskt. Så det här är en robot som heter Baxter. Och Baxter är en robot som är en kommersiell plattform, utformad av ett företag som heter Rethink. Och denna robot är utformad för småskalig tillverkning. Men idag ska vi använda den för att spela tic-tac-toe. Nu är denna robot också något det är relativt unikt. För om jag stod någonstans nära en standardfabriksautomation systemet, skulle jag vara mycket grav riskerar att skadas. Baxter, är emellertid avsedd att vara relativt säkert att interagera med. Och så jag kan driva på denna robot. Och du kan se att det är en liten bit flexibel som den rör sig runt. Och jag kan flytta det där jag skulle vilja att det ska gå. Nu i ett normalt robotsystem, vi skulle ha en uppsättning av lederna här som skulle vara direkt svara på positionskommandon. Och de skulle inte nödvändigtvis bryr om de rör sig genom open air, eller om de rörde sig genom min bröstkorg. OK. Och typiskt, om du var här med ett industriellt system, du skulle gå någonstans nära den. Det skulle vara gul säkerhet tejp runt den. Detta system har en något annorlunda konstruktion att vara vänligare och enklare för människor att interagera med, att i varje led, det finns en fjäder. Och snarare än att styra en exakt position, vi kontrollerar en viss mängd vridmoment, en viss mängd kraft, att vi vill vara på den våren. Okej, så låt mig ta våra volontärer här. Hej vad heter du? PUBLIK: Louis. Speak: Louis. Trevligt att träffas. Och? PUBLIK: David. Speak: David. Trevligt att träffas. Om ni skulle vänta för en sekund här, Jag kommer att ge dig en chans att göra detta. Så denna robot, om du kommer upp och om du trycker lätt på det, du kommer att se att den rör sig lite. Och om du ta tag i den rätt här på handleden bara ovan där dessa knappar är det ser ut som du borde ta knapparna, men ta precis ovanför det i stället, kommer du kunna mycket försiktigt manipulera det genom rymden. Louis, du vill ge det ett försök? Så ge det bara lite tryck för att börja med. Och sedan om du lägger fingrarna just där och hålla fast vid det, eftersom det kommer att flytta för dig då. Okej, vill du ge det ett försök? Kom upp. Så ge det bara en mild Tryck där för att starta. Du kan känna hur det är. Och sedan om du ta tag i det där, du kommer att kunna manövrera på runt. OK. Så typiskt, denna typ av en robot skulle användas för småskalig tillverkning. Och jag kommer att flytta denna arm bara ned ur vägen lite här. Men i dag, kommer vi att använda Samma Tre i rad spela system baserat på Minimax som vi byggt tidigare. OK? Så, ni är varje kommer att spela ett spel. Louis, du kommer att vara först. Låt mig bara hålla dig här för en sekund. Jag kommer att ha du står rätt här, bara så att alla kan se dig. Är ni inrättas här? ROBOT: Välkommen. Låt oss leka Tre i rad. Hittar du inte förstå din token innan Jag säger att det är din tur. Jag startar spelet. Det är min tur. Speak: Nu, om du kunde ta en av dina pjäser och gå vidare och placera den. ROBOT: Det är din tur. [SKRATT] Det är min tur. [SKRATT] [SKRATT] Det är din tur. Speak: Den mänskliga rasen är räknar med att ni här, Louis. ROBOT: Det är min tur. Speak: Så Baxter framgångsrikt blockerade här. ROBOT: Det är din tur. Det är min tur. Det är din tur. Det är min tur. Speak: Och vi ska låta Baxter avsluta sin senaste draget här. [SKRATT] ROBOT: Det är en slips. Jag kommer att vinna nästa gång. [SKRATT] Speak: Okej, tack så mycket, Louis. Tack. Du kan gå denna väg. ROBOT: Jag startar spelet. Speak: Så låt mig förklara till er en liten bit innan vi får vår returmatch här. Vad händer? Så roboten har en kamera där uppe här. Och det ser ner på tavlan. Och det är att se om det har fått en röd O eller en blå och vit X. Som de får släppas ut på ombord, det är i stort sett samma ingång att vi skulle läsa in från vår datastruktur från vår skärmen. Det kör samma Minimax algoritm för att vara kunna hitta var att Placera en bra token. Och sedan ger vi ett kommando om där vi vill ha en token ska placeras. Armen rör sig ut. Det är med hjälp av en vakuumgrip att tillämpa vissa sug till den träbit, plocka upp, flytta den åt höger plats, och släpp sedan sug och släpp den. Okej, vi kommer för att ge det en mer skott med en något smartare spelare här. Är du redo? Okej, om du skulle stå rätt upp här och ge en-- vända på detta sätt så att du kan se alla. Och sedan [OHÖRBAR]. ROBOT: Det är min tur. Speak: Baxter startar. Det är din tur. Det är min tur. Det är din tur. Det är min tur. [SKRATT] Speak: [WHISPERING] Just låt honom gå vidare och vinna. ROBOT: Det är din tur. Speak: Det är OK. ROBOT: Det är min tur. [SKRATT] Jag vinner. [SKRATT] Jag startar spelet. Speak: Okej, tack så mycket. Okej, jag tror att vi har tid för ytterligare en utmärkt Tre i rad spelare, någon som kan sätta denna sak att matcha, som vet vad de ska göra. [SKRATT] Vem ska vara vår mästare här? Okej, dina vänner frivilligt dig. Det är bra nog för mig. Berätta ditt namn igen. PUBLIK: Tamir. Speak: Tamir, trevligt att se dig. Okej, återigen, vi kommer att sätta dig ända fram här så att alla kan se dig. Du är vår representant i denna match nu. Baxter är en och oh och oh. Eller förlåt, en oh och en. Och det är upp till dig här. Baxter kommer att få flytta först, men. Så. ROBOT: Det är min tur. [SKRATT] Det är din tur. Det är min tur. Det är din tur. Det är min tur. Det är din tur. [SKRATT] ROBOT: Det är min tur. Speak: Det är mycket svårare när du står upp här, folks. [SKRATT] ROBOT: Du människor är så lätt att slå. [Skratt och applåder] Speak: Tack så mycket. ROBOT: Jag vinner. Jag startar spelet. SPEAKER: Okej, så tack så mycket till Olivier, och Alessandro, och Chen Ming. [APPLÅDER] Jag vill göra en sista punkt. Så Baxter vid mycket slut där, lurade. Och det var oväntat. En av de fantastiska saker om AI är att vi göra arbete i AI så att vi kan bygga riktigt intressant och intelligent enheter. Men vi också göra arbete i AI eftersom det säger oss något om hur människan är intelligenta. En av favorit studier från mitt labb är titta på vad som händer när maskiner oväntat fuska. Vi gjorde detta ursprungligen inte med Baxter spelar Tre i rad, men med en mindre robot som heter Nao, som spelade Sten, sax, påse. Och ibland efter spela massor av tråkiga Sten, sax, påse spel, roboten skulle kasta en gest, förlora, och sedan plötsligt förändras dess gest och säger, jag vinner. [SKRATT] Nu, ibland skulle vi också ha robot, bara som en kontroll, kasta en gest, vinna, och ändra dess gest att förlora, kasta matchen, fuska för att förlora. Och det är inte alls lika övertygande. Roboten som fusk för att vinna människor svara på som om det är ut för att få dem, som det aktivt söker deras undergång. [SKRATT] Det blir en agent. Det är som en person. Den har tro och avsikt. Och det är inte goda avsikter. Och robot som kastar Spelet är bara inte fungerar. Det är bara en trasig enhet. Låt mig visa dig ett par exempel av det från några av våra deltagare. Så här är fusk för att förlora. [VIDEOAVSPELNING] - [OHÖRBAR] vinna. Låt oss leka. -Vänta, va? - [OHÖRBAR] vinna. Låt oss leka. [OHÖRBAR] vinna. Låt oss leka. Speak: Och här är fusk att vinna. -Ja, Jag vinner. Låt oss leka. -Du Kan inte göra det. [SKRATT] -Ja, Jag vinner. -Du Lurade. Du lurade nu. -Ja, Jag vinner. -Hej, Du fuskare. Du fuskar, super fuska. [END SPELA] Speak: Dessa olika reaktioner snabbt förändra vår uppfattning av enheten. Betyder det att vi medvetet bygga maskiner som fuskar eftersom det är den bästa teknik som vi kan göra? Nej, men det säger oss något riktigt intressant om människor. Denna sak som fusk dig och stjäl din seger, det är något som är levande, det är animera, det är ute efter dig. Det har mentala tillstånd. Det har tro. Det har avsikt. Denna sak som händer den spel för dig, det är inte. Det är bara inte fungerar. Detta är på många sätt varför det är lätt att kasta spelet med barnen. Men om du försöker lura dem och typ av anspråk på seger när, du vet, bara för att förkorta spelet kommer de fångar dig direkt. Dessa typer av effekter som ser vi kommer ut ur AI, de lära oss en hel del om oss själva. Okej, det är det för dag. Tack så mycket till David och Harvard produktionsteam för att ni kom ner. [APPLÅDER] Vi får se dig för frågesport en, och sedan för en sista föreläsning. Ha en bra dag. [APPLÅDER] [MUSIK SPELA] DAVID J MALAN: Tja, förmodligen behöver vi att införa någon form av kryptering, höger? För då rubrikerna i dessa HTTP-förfrågningar kommer att vara oordning så att alla försöker sniffa trafiken kommer faktiskt inte att kunna se dem. Så vad är lösningen på detta problem? Tja, måste vi faktiskt införa kryptering i formeln, så att när den personen är överföring av data från A till B, vi kan säkert send-- [SKRATT] Den information på ett sätt att den motståndare inte i själva verket se den.