1 00:00:00,000 --> 00:00:01,924 >> [MUSIC SPILLE] 2 00:00:01,924 --> 00:00:10,600 3 00:00:10,600 --> 00:00:13,280 >> SPEAKER: Velkommen tilbake, alle sammen. 4 00:00:13,280 --> 00:00:15,440 Dette er CS50. 5 00:00:15,440 --> 00:00:21,040 Og i dag har vi en rekke interessante ting å snakke om. 6 00:00:21,040 --> 00:00:25,500 Men først må jeg minne du av noen administrative ting. 7 00:00:25,500 --> 00:00:30,160 Denne uken er quiz en, onsdag eller for Yale seksjonen 8 00:00:30,160 --> 00:00:32,940 på tirsdager og torsdager, på torsdag. 9 00:00:32,940 --> 00:00:38,170 Det er quiz anmeldelser i kveld på Yale, 5:30 til 7:00. 10 00:00:38,170 --> 00:00:40,030 Ved Harvard, spilte de en i går. 11 00:00:40,030 --> 00:00:43,000 Og alle kan se at online. 12 00:00:43,000 --> 00:00:49,406 >> Også denne uken eller tidlig neste uke, vi ha vår siste CS50 forelesning. 13 00:00:49,406 --> 00:00:51,450 [Stønner] jeg vet. 14 00:00:51,450 --> 00:00:54,140 Det kom så fort. 15 00:00:54,140 --> 00:00:57,820 Yale studenter vil ha en live foredrag her i juss 16 00:00:57,820 --> 00:00:59,920 auditorium på fredag. 17 00:00:59,920 --> 00:01:01,140 Det vil være kake. 18 00:01:01,140 --> 00:01:05,570 Harvard studenter vil ha siste forelesning i Sanders på mandag. 19 00:01:05,570 --> 00:01:08,050 Det vil også være kake. 20 00:01:08,050 --> 00:01:14,000 >> Også denne uken på fredag, for de av dere som kommer til New Haven, 21 00:01:14,000 --> 00:01:15,740 vi har CS50 Expo. 22 00:01:15,740 --> 00:01:18,850 Vi har mer enn 30 ulike grupper registrert 23 00:01:18,850 --> 00:01:22,530 å vise deg alt fra selvstyrte seilbåter, 24 00:01:22,530 --> 00:01:27,170 til systemer som gjenkjenner digitale portretter, til datamaskinen 25 00:01:27,170 --> 00:01:32,100 musikk og dataprodusert musikk. 26 00:01:32,100 --> 00:01:33,610 Så vennligst bli med oss. 27 00:01:33,610 --> 00:01:36,460 Jeg tror det kommer til å bli en flott tid. 28 00:01:36,460 --> 00:01:40,320 >> I dag, men vi kommer til å fortsette å snakke om AI, 29 00:01:40,320 --> 00:01:43,150 om kunstig intelligens. 30 00:01:43,150 --> 00:01:46,070 Og en av de tingene som vi kommer til å få til i dag 31 00:01:46,070 --> 00:01:51,750 er ideen om hvordan du bruke AI til å løse problemer. 32 00:01:51,750 --> 00:01:54,690 Nå, som alltid, la oss starte med noe enkelt. 33 00:01:54,690 --> 00:01:57,120 Og vi kommer til å starte med en enkel idé. 34 00:01:57,120 --> 00:01:59,920 Og det er ved hjelp av søk. 35 00:01:59,920 --> 00:02:06,990 >> Så tenk et øyeblikk at jeg har en oppgave som jeg trenger for å utføre. 36 00:02:06,990 --> 00:02:11,970 Og jeg vil gjerne ha den oppgaven automatiseres ved noen programvare agent. 37 00:02:11,970 --> 00:02:17,100 Tenk deg at jeg prøver å bestille et sett på flyreiser fra, la oss si, Boston 38 00:02:17,100 --> 00:02:20,040 til San Francisco. 39 00:02:20,040 --> 00:02:24,230 Jeg kunne gå gjennom og jeg kunne bruke en av de fantastiske online søk 40 00:02:24,230 --> 00:02:28,790 verktøy, som kommer til å gjøre utgangspunktet den samme prosessen som vi er 41 00:02:28,790 --> 00:02:30,030 kommer til å gå gjennom i dag. 42 00:02:30,030 --> 00:02:34,100 Men hvis du ikke har som verktøyet, hva ville du gjort? 43 00:02:34,100 --> 00:02:37,570 >> Vel, du kan se og se og si, jeg er i Boston. 44 00:02:37,570 --> 00:02:41,520 Hva flyreiser er tilgjengelige for meg? 45 00:02:41,520 --> 00:02:44,390 Nå, kanskje jeg har tre mulige fly av Boston 46 00:02:44,390 --> 00:02:47,180 som passer tiden når jeg trenger å forlate. 47 00:02:47,180 --> 00:02:48,830 Jeg kunne fly til Chicago. 48 00:02:48,830 --> 00:02:50,130 Eller jeg kunne fly til Miami. 49 00:02:50,130 --> 00:02:53,340 Eller jeg kunne fly til New York. 50 00:02:53,340 --> 00:02:56,980 Jeg kunne da se fra hver en av disse reisemål byer 51 00:02:56,980 --> 00:03:00,650 og tenke på hva steder Jeg kunne muligens nå 52 00:03:00,650 --> 00:03:03,020 fra hver av de individuelle byene. 53 00:03:03,020 --> 00:03:07,390 >> Så kanskje fra Chicago, kan jeg få et direktefly til San Francisco. 54 00:03:07,390 --> 00:03:09,550 Det er utmerket. 55 00:03:09,550 --> 00:03:12,360 Eller jeg kunne få et fly til Denver. 56 00:03:12,360 --> 00:03:16,970 Nå, kanskje det fly til San Francisco er den perfekte løsningen for meg, 57 00:03:16,970 --> 00:03:19,530 men kanskje ikke. 58 00:03:19,530 --> 00:03:22,180 Kanskje jeg leter etter noe det er litt billigere 59 00:03:22,180 --> 00:03:24,920 eller litt bedre for min timeplan. 60 00:03:24,920 --> 00:03:29,197 Og så kunne jeg se etter hva andre Mulighetene kan være der ute. 61 00:03:29,197 --> 00:03:30,280 Så jeg kunne se på Denver. 62 00:03:30,280 --> 00:03:33,870 Og fra Denver, vel, kanskje Jeg kan få et fly til Austin. 63 00:03:33,870 --> 00:03:37,080 Og fra Austin, kanskje jeg kan få en fly til Phoenix, og fra Phoenix 64 00:03:37,080 --> 00:03:40,190 til San Francisco. 65 00:03:40,190 --> 00:03:42,730 Nå er jeg ikke ferdig ennå. 66 00:03:42,730 --> 00:03:45,640 Fordi kanskje det er en direkte fra New York 67 00:03:45,640 --> 00:03:47,850 til San Francisco som er perfekt for meg. 68 00:03:47,850 --> 00:03:53,354 Eller kanskje det er et fly fra Miami gjennom Denver som er mye billigere. 69 00:03:53,354 --> 00:03:54,270 Så jeg har fortsatt å gå. 70 00:03:54,270 --> 00:03:58,200 Og jeg har fortsatt å se på alle de byer som jeg ikke har undersøkt ennå. 71 00:03:58,200 --> 00:04:04,220 Jeg må uttømmende sjekke alle mulighetene for at jeg skulle ha. 72 00:04:04,220 --> 00:04:09,610 >> Så fra New York, kanskje jeg kan få en fly til Nashville, og fra Nashville 73 00:04:09,610 --> 00:04:10,336 til Austin. 74 00:04:10,336 --> 00:04:11,460 Og så vet jeg hvor jeg er. 75 00:04:11,460 --> 00:04:14,252 Og så vet jeg fra Austin, kan jeg fly til Phoenix, og fra Phoenix 76 00:04:14,252 --> 00:04:14,960 til San Francisco. 77 00:04:14,960 --> 00:04:18,240 78 00:04:18,240 --> 00:04:22,830 Hvis jeg flyr først til Miami, skjønt, kanskje jeg kan få et fly fra Miami 79 00:04:22,830 --> 00:04:25,080 til Nashville, eller fra Miami til Austin. 80 00:04:25,080 --> 00:04:27,950 81 00:04:27,950 --> 00:04:30,860 >> Og nå har jeg prøvd alt av mulighetene. 82 00:04:30,860 --> 00:04:36,310 Jeg har bygget opp denne grafen at viser meg alle mulige ruter 83 00:04:36,310 --> 00:04:37,790 at jeg kan være i stand til å ta. 84 00:04:37,790 --> 00:04:40,510 85 00:04:40,510 --> 00:04:43,640 Når vi representerer disse typer problemer, 86 00:04:43,640 --> 00:04:47,870 Vi kommer ikke til å representere dem eksplisitt som denne grafen, 87 00:04:47,870 --> 00:04:51,590 fordi at grafen ikke representerer historie hvor vi har gått. 88 00:04:51,590 --> 00:04:55,260 Å vite at jeg fløy fra Phoenix til San Francisco 89 00:04:55,260 --> 00:05:01,690 forteller meg ikke om jeg kom via Nashville, eller via Denver, eller via Miami. 90 00:05:01,690 --> 00:05:06,430 >> Så hva jeg skal gjøre i stedet er Jeg vil ta dette samme problemet, 91 00:05:06,430 --> 00:05:09,140 og jeg skal representere det som et tre. 92 00:05:09,140 --> 00:05:14,300 Og ved roten av treet, på toppen, vil jeg sette det sted som jeg startet, 93 00:05:14,300 --> 00:05:16,590 Boston. 94 00:05:16,590 --> 00:05:19,310 Og fra Boston, vil jeg se på alle de mulige plasseringer 95 00:05:19,310 --> 00:05:20,380 at jeg kan reise til. 96 00:05:20,380 --> 00:05:25,480 Vel, i dette tilfellet, hadde jeg tre, Chicago, New York og Miami. 97 00:05:25,480 --> 00:05:29,850 Og så vil jeg utforske hver av disse barna i treet. 98 00:05:29,850 --> 00:05:32,690 >> Fra Chicago, så jeg at jeg hadde to fly. 99 00:05:32,690 --> 00:05:35,940 Jeg kunne fly direkte til San Francisco eller til Denver. 100 00:05:35,940 --> 00:05:37,740 Nå San Francisco, det er mitt mål. 101 00:05:37,740 --> 00:05:39,790 Det er mitt mål. 102 00:05:39,790 --> 00:05:42,220 Det kommer til å være et blad av dette treet. 103 00:05:42,220 --> 00:05:45,340 Det vil si, jeg kommer aldri til å gå sted etter San Francisco. 104 00:05:45,340 --> 00:05:47,850 105 00:05:47,850 --> 00:05:50,340 Fra Denver, skjønt, Jeg kan fly fra Denver 106 00:05:50,340 --> 00:05:54,220 til Austin, fra Austin til Phoenix, og fra Phoenix til San Francisco. 107 00:05:54,220 --> 00:05:56,050 Og nå igjen, jeg har nådd et blad. 108 00:05:56,050 --> 00:05:59,470 109 00:05:59,470 --> 00:06:03,980 >> Jeg kunne da gå tilbake til neste byen som jeg ikke har fullt utforsket. 110 00:06:03,980 --> 00:06:07,440 Det ville være New York, går tilbake til toppen av treet mitt, 111 00:06:07,440 --> 00:06:09,160 komme ned til New York. 112 00:06:09,160 --> 00:06:12,700 Fra New York, kan jeg fly til Nashville, fra Nashville til Austin, 113 00:06:12,700 --> 00:06:17,290 fra Austin til Phoenix, og fra Phoenix til San Francisco. 114 00:06:17,290 --> 00:06:20,170 Og til slutt, en by jeg har ikke sett på ennå, Miami. 115 00:06:20,170 --> 00:06:24,600 >> Vel, fra Miami jeg sa jeg hadde to muligheter, Nashville eller Austin. 116 00:06:24,600 --> 00:06:28,810 Hvis jeg fly til Nashville, vel da jeg fly fra Nashville, til Austin, til Phoenix, 117 00:06:28,810 --> 00:06:29,640 til San Francisco. 118 00:06:29,640 --> 00:06:33,600 Hvis jeg fly til Austin, jeg flyr Austin, til Phoenix, San Francisco. 119 00:06:33,600 --> 00:06:36,340 Og nå har jeg et tre. 120 00:06:36,340 --> 00:06:37,230 Det er en komplett tre. 121 00:06:37,230 --> 00:06:41,890 Det er alle de muligheter og alle stiene som jeg kunne ta. 122 00:06:41,890 --> 00:06:44,310 Det vil si, hvis jeg begynner på roten av treet på toppen 123 00:06:44,310 --> 00:06:47,860 og jeg går ned til en av blader, det forteller meg ikke bare 124 00:06:47,860 --> 00:06:50,480 hvor jeg kommer til å ender opp med, San Francisco, 125 00:06:50,480 --> 00:06:53,670 men det forteller meg den ruten som Jeg må ta for å komme dit. 126 00:06:53,670 --> 00:06:56,400 127 00:06:56,400 --> 00:06:59,690 >> Nå er der en av disse er best? 128 00:06:59,690 --> 00:07:02,430 Vel, ingenting om dette problemet ennå forteller meg 129 00:07:02,430 --> 00:07:04,710 hvilke av disse som er den beste løsningen. 130 00:07:04,710 --> 00:07:09,270 Kanskje jeg bryr meg mest om hvor mye tid jeg er i luften, 131 00:07:09,270 --> 00:07:12,350 eller avstanden at jeg flyr. 132 00:07:12,350 --> 00:07:16,410 I dette tilfellet, Chicago til San Francisco kan være den korteste antall 133 00:07:16,410 --> 00:07:18,910 av miles i luften. 134 00:07:18,910 --> 00:07:20,860 >> Kanskje jeg bryr meg om kostnadene. 135 00:07:20,860 --> 00:07:23,680 Og vi vet alle direktefly er vanligvis dyrere. 136 00:07:23,680 --> 00:07:26,610 Så kanskje hvis jeg tar dette slags baklengs rute 137 00:07:26,610 --> 00:07:30,650 gjennom Miami, Nashville, Austin, Phoenix, kanskje da 138 00:07:30,650 --> 00:07:34,070 Jeg får en lavere pris. 139 00:07:34,070 --> 00:07:36,440 Men jeg kunne optimalisere på noen kriterier som jeg bryr meg om. 140 00:07:36,440 --> 00:07:39,790 Hvem har den beste i flight Wi-Fi, eller som 141 00:07:39,790 --> 00:07:43,110 flyplasser har den beste maten tilgjengelig. 142 00:07:43,110 --> 00:07:47,280 Og hver av dem kan gi meg en annen løsning 143 00:07:47,280 --> 00:07:49,215 som jeg ser som den beste. 144 00:07:49,215 --> 00:07:51,990 145 00:07:51,990 --> 00:07:54,400 >> Disse typer problemer, hvor vi går 146 00:07:54,400 --> 00:07:58,480 å bygge ut dette treet av muligheter, og deretter 147 00:07:58,480 --> 00:08:02,100 se på hver av dem enkelte baner, og undersøke 148 00:08:02,100 --> 00:08:05,270 hvilke av disse Oppfyller et kriterium for oss, 149 00:08:05,270 --> 00:08:08,790 vi kommer til å kalle disse søkeproblemer. 150 00:08:08,790 --> 00:08:11,280 Og vi har massevis av algoritmer, hvorav noen 151 00:08:11,280 --> 00:08:15,270 vi har sett allerede, å gå og utforske disse trærne. 152 00:08:15,270 --> 00:08:19,270 Vi kunne gjøre det på den måten at jeg bare gjorde, en dybde-først søk, 153 00:08:19,270 --> 00:08:22,900 går ned så langt vi kan før vi treffer et blad, og deretter kommer tilbake opp, 154 00:08:22,900 --> 00:08:24,787 og går rett ned igjen. 155 00:08:24,787 --> 00:08:26,870 Eller vi kunne gjøre det som er kalt bredde-først-søk. 156 00:08:26,870 --> 00:08:29,675 Vi kunne utvide alt på toppen, og deretter 157 00:08:29,675 --> 00:08:31,550 alt en linje under det, og deretter 158 00:08:31,550 --> 00:08:35,240 alt en linje under det. 159 00:08:35,240 --> 00:08:41,250 Disse søke trær er grunnleggende for AI. 160 00:08:41,250 --> 00:08:46,570 Men de har ikke helt får det rett hele tiden. 161 00:08:46,570 --> 00:08:51,600 Faktisk, i mange av tilfellene at vi virkelig bryr oss om, 162 00:08:51,600 --> 00:08:54,430 vi ønsker å bygge et tre, men vi gjør faktisk ikke 163 00:08:54,430 --> 00:08:57,140 kommer til å gjøre alle beslutninger. 164 00:08:57,140 --> 00:09:00,940 >> Dette er situasjoner som kalles motstandere søk, også kjent 165 00:09:00,940 --> 00:09:05,390 som hvordan å skrive spillet spilles systemer og få betalt for det. 166 00:09:05,390 --> 00:09:07,940 Men disse er de typer av systemer der jeg 167 00:09:07,940 --> 00:09:12,920 kan komme til å velge når jeg går fra Boston, hvilken by jeg går til neste. 168 00:09:12,920 --> 00:09:19,990 Men etter det, kanskje noen andre få å ta beslutningen om hvor jeg flyr. 169 00:09:19,990 --> 00:09:24,040 Så for å bygge disse typer strukturer, er vi 170 00:09:24,040 --> 00:09:28,510 nødt til å ta en litt annen tilnærming til det. 171 00:09:28,510 --> 00:09:31,060 Vi kommer ikke til å være i stand til å bare søke gjennom treet 172 00:09:31,060 --> 00:09:35,000 lenger, fordi vi ikke er den som er i kontroll 173 00:09:35,000 --> 00:09:38,180 av hver av disse beslutningspunkter. 174 00:09:38,180 --> 00:09:42,590 >> Så la oss forestille en enkel spill som tic-tac-toe. 175 00:09:42,590 --> 00:09:46,730 Jeg kan begynne med en helt tomt bord. 176 00:09:46,730 --> 00:09:49,580 Og i tic-tac-toe, X får spille først. 177 00:09:49,580 --> 00:09:53,890 Og så jeg kunne tenke på alt mulige trekk at X kan gjøre. 178 00:09:53,890 --> 00:09:57,420 Og hvis jeg er den som spiller X, det er flott. 179 00:09:57,420 --> 00:10:01,020 Jeg har ni mulige foreslår at jeg kan gjøre. 180 00:10:01,020 --> 00:10:05,000 Jeg kunne sette en X i ett av de ni stillingene. 181 00:10:05,000 --> 00:10:10,710 >> Og deretter fra hver av disse, I kunne forestille seg hva som skjer videre. 182 00:10:10,710 --> 00:10:14,130 Også, i dette tilfelle den annen spiller ville komme til å ta en tur. 183 00:10:14,130 --> 00:10:15,660 O ville komme til å ta en tur. 184 00:10:15,660 --> 00:10:19,510 Og fra hver av disse, der ville være åtte forskjellige steder 185 00:10:19,510 --> 00:10:22,980 at O kunne plassere markøren sin. 186 00:10:22,980 --> 00:10:25,790 >> La oss si at jeg bestemte meg for at jeg var kommer til å sette et kryss i sentrum. 187 00:10:25,790 --> 00:10:28,810 Det virker alltid som en god åpning trekk. 188 00:10:28,810 --> 00:10:34,870 Jeg kunne se på under det, åtte mulige trekk at O ​​gjør. 189 00:10:34,870 --> 00:10:37,320 Nå, hvis jeg spiller X, det er fantastisk. 190 00:10:37,320 --> 00:10:41,740 Jeg kommer til å velge hvilken jeg gå til, den i midten. 191 00:10:41,740 --> 00:10:45,000 Men nå O får velge. 192 00:10:45,000 --> 00:10:48,750 Og jeg har ikke kontroll i løpet av den beslutningen. 193 00:10:48,750 --> 00:10:51,670 >> Men fra hver av disse mulige styreverv, 194 00:10:51,670 --> 00:10:54,020 det er da en annen satt av muligheter. 195 00:10:54,020 --> 00:10:56,700 Når det gjelder å bli min tur igjen, ville jeg 196 00:10:56,700 --> 00:11:01,500 får velge, og si, vel, hvis O beveger seg inn i, vel, 197 00:11:01,500 --> 00:11:06,110 midten flekk på venstre, deretter Jeg har et sett av muligheter 198 00:11:06,110 --> 00:11:09,740 hvor jeg kan ta mitt neste trekk. 199 00:11:09,740 --> 00:11:14,140 Fra disse, kunne jeg vurdere alle muligheter under dem. 200 00:11:14,140 --> 00:11:18,030 Og så O ville få til å velge blant de. 201 00:11:18,030 --> 00:11:22,290 >> Og jeg kunne fortsette å bygge denne treet ut før jeg kom til et punkt 202 00:11:22,290 --> 00:11:26,960 der enten noen vinner game-- det er 203 00:11:26,960 --> 00:11:31,070 fikk å bli betraktet som et blad node-- eller styret er helt full 204 00:11:31,070 --> 00:11:32,704 og ingen har vunnet. 205 00:11:32,704 --> 00:11:34,370 Og som også kommer til å være en bladnode. 206 00:11:34,370 --> 00:11:35,411 Det kommer til å være en uavgjort. 207 00:11:35,411 --> 00:11:37,820 208 00:11:37,820 --> 00:11:41,680 >> Men den vanskelige ting med dette er hvis dette var bare en vanlig søk 209 00:11:41,680 --> 00:11:44,269 problem, jeg ville være i stand til å si, vel, X bør gå her. 210 00:11:44,269 --> 00:11:45,560 Og O bør gå veien dit. 211 00:11:45,560 --> 00:11:46,770 Og så X bør gå over her. 212 00:11:46,770 --> 00:11:48,269 Og deretter O bør gå veien dit. 213 00:11:48,269 --> 00:11:51,860 Og så X kan få tre på rad, og jeg vinner. 214 00:11:51,860 --> 00:11:54,870 Og spillet ville være over i fem trekk, tre for meg, 215 00:11:54,870 --> 00:11:57,710 to for min motstander. 216 00:11:57,710 --> 00:12:01,300 Men jeg vet ikke alltid kommer til å velge det. 217 00:12:01,300 --> 00:12:03,720 >> Så i stedet, hva vi er nødt til å gjøre 218 00:12:03,720 --> 00:12:06,270 er vi kommer til å ha å ha en ny strategi. 219 00:12:06,270 --> 00:12:09,350 Og den strategien som spill-spiller algoritmer bruker ofte 220 00:12:09,350 --> 00:12:12,000 er det som kalles minimax. 221 00:12:12,000 --> 00:12:15,500 Den sentrale ide minimax er at vi er 222 00:12:15,500 --> 00:12:21,365 kommer til å plukke farten som gir vår motstander den verst tenkesett 223 00:12:21,365 --> 00:12:22,790 trekk at de kan gjøre. 224 00:12:22,790 --> 00:12:25,570 225 00:12:25,570 --> 00:12:28,870 Det gjør ikke meg noe godt å velge en overgang der 226 00:12:28,870 --> 00:12:31,952 Jeg kan være i stand til å vinne etter det, fordi min motstander er ikke 227 00:12:31,952 --> 00:12:33,160 kommer til å gi meg den sjansen. 228 00:12:33,160 --> 00:12:37,770 De kommer til å velge noen forferdelig utfall for meg. 229 00:12:37,770 --> 00:12:42,010 Så jeg kommer til å gjøre flytte som tvinger min motstander 230 00:12:42,010 --> 00:12:45,760 å gjøre noe bedre for meg. 231 00:12:45,760 --> 00:12:46,260 Greit. 232 00:12:46,260 --> 00:12:48,410 La oss se hvordan det utspiller seg. 233 00:12:48,410 --> 00:12:51,640 Så her er vår algoritme i pseudokode. 234 00:12:51,640 --> 00:12:54,450 Vi kommer til å generere hele spillet treet. 235 00:12:54,450 --> 00:12:56,757 Vi kommer til å bygge hele strukturen. 236 00:12:56,757 --> 00:12:57,840 Og så får vi gå gjennom. 237 00:12:57,840 --> 00:13:02,100 Og helt nederst på hver av de terminal noder, på hvert av bladene, 238 00:13:02,100 --> 00:13:07,850 Da vil vi evaluere hvordan verdifullt er det for meg? 239 00:13:07,850 --> 00:13:11,690 Og vi kommer til å verdsette ting som er bra for meg som å være positiv. 240 00:13:11,690 --> 00:13:14,460 Ting som ikke er bra for meg vil være mindre positiv eller null, 241 00:13:14,460 --> 00:13:16,480 eller til og med negativ. 242 00:13:16,480 --> 00:13:19,240 >> Så i tic-tac-toe, kanskje en seier for meg er bra. 243 00:13:19,240 --> 00:13:20,290 Det er en en. 244 00:13:20,290 --> 00:13:22,400 Og en uavgjort er null. 245 00:13:22,400 --> 00:13:26,230 Og noe som er et tap for meg, kanskje det er en negativ en. 246 00:13:26,230 --> 00:13:29,620 Alt som teller er at jo bedre det er for meg, jo høyere score 247 00:13:29,620 --> 00:13:32,160 den mottar. 248 00:13:32,160 --> 00:13:36,690 Fra disse mulighetene på bunn, så får vi filtrere oppover. 249 00:13:36,690 --> 00:13:40,650 Og når det er min sjanse til å velge blant et sett av alternativer, 250 00:13:40,650 --> 00:13:44,460 Jeg vil velge den som er fikk høyest poengsum. 251 00:13:44,460 --> 00:13:47,200 >> Og når det er min motstandere slå til å velge, 252 00:13:47,200 --> 00:13:52,350 Jeg vil anta at de kommer til å velge den med lavest poengsum. 253 00:13:52,350 --> 00:13:56,090 Og hvis jeg gjør dette hele veien opp til toppen av treet, 254 00:13:56,090 --> 00:14:03,150 Jeg har valgt en vei som gir meg det beste resultatet som jeg kan få, 255 00:14:03,150 --> 00:14:09,110 forutsatt at min motstander gjør alle de riktige trekkene. 256 00:14:09,110 --> 00:14:11,940 >> Greit, så la oss se dette i aksjon først. 257 00:14:11,940 --> 00:14:14,980 Og så får vi faktisk se på koden for det. 258 00:14:14,980 --> 00:14:16,780 Så tenk jeg har dette store treet. 259 00:14:16,780 --> 00:14:18,280 Og nå er jeg ikke spille tic-tac-toe. 260 00:14:18,280 --> 00:14:20,405 Jeg ønsket å gi deg noe litt rikere. 261 00:14:20,405 --> 00:14:23,560 Så jeg har fått noen spill der det er mange forskjellige poengsummer 262 00:14:23,560 --> 00:14:26,390 at jeg kunne ha på slutten. 263 00:14:26,390 --> 00:14:27,980 Og så jeg bygge denne komplette treet. 264 00:14:27,980 --> 00:14:29,070 Og jeg kommer til å flytte først. 265 00:14:29,070 --> 00:14:31,290 Jeg er ved roten av treet. 266 00:14:31,290 --> 00:14:36,150 >> Og jeg kommer til å velge at-- så jeg får å maksimere over at første noden. 267 00:14:36,150 --> 00:14:38,410 Og da min motstander kommer til å gå. 268 00:14:38,410 --> 00:14:41,910 Og så kommer jeg til å gå igjen. 269 00:14:41,910 --> 00:14:46,830 Så ned på bunnen, jeg har et sett av muligheter for at jeg kan velge mellom, 270 00:14:46,830 --> 00:14:50,570 forskjellige terminal statene i spillet. 271 00:14:50,570 --> 00:14:54,980 Hvis jeg er nede i det Helt til venstre hjørne, 272 00:14:54,980 --> 00:14:58,867 og jeg ser at jeg har et valg mellom en åtte, syv, og en to, 273 00:14:58,867 --> 00:15:00,450 vel, jeg er den som får velge. 274 00:15:00,450 --> 00:15:02,910 Så jeg kommer til å velge den beste av dem. 275 00:15:02,910 --> 00:15:05,650 Jeg kommer til å velge åtte. 276 00:15:05,650 --> 00:15:10,090 >> Så jeg vet at hvis jeg noen gang komme ned til det punktet, 277 00:15:10,090 --> 00:15:13,890 Jeg vil være i stand til å få det åtte poeng. 278 00:15:13,890 --> 00:15:17,410 Hvis jeg ender opp på neste punkt over, de neste node over, 279 00:15:17,410 --> 00:15:20,760 en ni, ett, eller en seks, vel, jeg er kommer til å velge den beste av dem. 280 00:15:20,760 --> 00:15:21,950 Jeg vil velge den ni. 281 00:15:21,950 --> 00:15:24,880 Hvis jeg har et valg mellom to og fire, og en, 282 00:15:24,880 --> 00:15:28,240 Jeg vil velge de fire, det høyeste. 283 00:15:28,240 --> 00:15:31,990 >> Nå, hvis jeg ser på det nivået over det, min motstander 284 00:15:31,990 --> 00:15:34,440 er det man får til å gjøre det valget. 285 00:15:34,440 --> 00:15:37,040 Så min motstander blir til velge, ønsker jeg å gi ham 286 00:15:37,040 --> 00:15:39,250 ting som skjer å få ham åtte poeng, 287 00:15:39,250 --> 00:15:41,916 eller gi jeg ham det som er kommer til å gi ham ni poeng, 288 00:15:41,916 --> 00:15:45,240 eller det som kommer å gi ham fire poeng? 289 00:15:45,240 --> 00:15:49,130 Og min motstander, blir rasjonell, kommer 290 00:15:49,130 --> 00:15:53,470 for å velge den minste av dem, kommer til å velge de fire. 291 00:15:53,470 --> 00:15:56,020 >> Og jeg kan gjøre dette gjennom hele treet. 292 00:15:56,020 --> 00:15:59,110 Jeg kan gå ned til at midterste sett av tre. 293 00:15:59,110 --> 00:16:01,517 Og jeg kan velge mellom en, tre og fem. 294 00:16:01,517 --> 00:16:02,350 Og jeg kommer til å velge. 295 00:16:02,350 --> 00:16:03,810 Så jeg velger et fem. 296 00:16:03,810 --> 00:16:05,340 Jeg kan velge tre, ni, eller to. 297 00:16:05,340 --> 00:16:07,570 Jeg kommer til å velge, så velger jeg de ni. 298 00:16:07,570 --> 00:16:09,290 Seks, fem, eller to, jeg velger. 299 00:16:09,290 --> 00:16:11,539 Jeg kommer til å velge de seks. 300 00:16:11,539 --> 00:16:13,080 Nivå over det, som får velge? 301 00:16:13,080 --> 00:16:16,280 302 00:16:16,280 --> 00:16:18,140 Hvem får velge? 303 00:16:18,140 --> 00:16:20,000 Den andre fyren, min motstander. 304 00:16:20,000 --> 00:16:22,583 Slik at de velger fem, ni, eller seks, hvilken? 305 00:16:22,583 --> 00:16:23,410 >> PUBLIKUM: De fem. 306 00:16:23,410 --> 00:16:25,250 >> SPEAKER: De velger de fem. 307 00:16:25,250 --> 00:16:27,400 De får velge minimum. 308 00:16:27,400 --> 00:16:29,690 Og så den siste, velge en, to, eller tre. 309 00:16:29,690 --> 00:16:31,720 Jeg kommer til å velge, så velger jeg tre. 310 00:16:31,720 --> 00:16:34,370 Ni, sju, eller to, velger jeg ni. 311 00:16:34,370 --> 00:16:37,070 Og 11, seks eller fire, velger jeg 11. 312 00:16:37,070 --> 00:16:41,190 Min motstander deretter velger tre, ni eller 11, velger minimum. 313 00:16:41,190 --> 00:16:43,290 Han gir meg et tre. 314 00:16:43,290 --> 00:16:47,780 Og deretter til slutt ved toppen av treet, får jeg til å velge på nytt. 315 00:16:47,780 --> 00:16:51,190 Og jeg kommer til å velge mellom en fire, fem, eller et tre. 316 00:16:51,190 --> 00:16:52,270 Så jeg tar det fem. 317 00:16:52,270 --> 00:16:55,070 318 00:16:55,070 --> 00:17:00,891 >> Hvis jeg fikk til å kontrollere alt, hadde jeg ta banen som førte til 11. 319 00:17:00,891 --> 00:17:02,390 Men jeg får ikke til å gjøre det valget. 320 00:17:02,390 --> 00:17:04,220 Hvis jeg går ned den veien. 321 00:17:04,220 --> 00:17:10,710 Min motstander vil tvinge meg inn Valget som fører til et tre. 322 00:17:10,710 --> 00:17:14,530 Så det beste jeg kan gjøre er å å ta det midterste gren, 323 00:17:14,530 --> 00:17:19,859 ta det valget som er slutt kommer til å føre meg til fem poeng. 324 00:17:19,859 --> 00:17:23,230 Det er det minimax gjør. 325 00:17:23,230 --> 00:17:23,807 >> Greit. 326 00:17:23,807 --> 00:17:24,890 La oss ta en titt på det. 327 00:17:24,890 --> 00:17:27,480 328 00:17:27,480 --> 00:17:32,330 Så her i CS50 IDE er et program som 329 00:17:32,330 --> 00:17:36,540 implementerer minimax å spille tic-tac-toe. 330 00:17:36,540 --> 00:17:40,100 Vi kommer til å bygge opp en representasjon. 331 00:17:40,100 --> 00:17:44,390 Vi kommer til å ha to opponent-- eller to spillere, vår datamaskin 332 00:17:44,390 --> 00:17:46,090 spiller og en menneskelig spiller. 333 00:17:46,090 --> 00:17:48,980 334 00:17:48,980 --> 00:17:53,090 Spiller nummer én skal spille den O. Det blir maskinen spiller. 335 00:17:53,090 --> 00:17:55,747 De kommer til å flytte andre. 336 00:17:55,747 --> 00:17:57,830 Og den andre spilleren, vår menneskelig spiller, vil være X. 337 00:17:57,830 --> 00:17:59,880 >> Og for å gjøre livet mitt litt enkelt, jeg kommer 338 00:17:59,880 --> 00:18:03,060 å merke at spilleren negativ en. 339 00:18:03,060 --> 00:18:05,026 Så jeg kan bare formere med negativt å bytte 340 00:18:05,026 --> 00:18:06,400 mellom en spiller og det andre. 341 00:18:06,400 --> 00:18:09,030 342 00:18:09,030 --> 00:18:12,250 Greit, så la oss ta en titt på hva vi faktisk kommer til å gjøre. 343 00:18:12,250 --> 00:18:15,840 Vi kommer til å definere vårt styre. 344 00:18:15,840 --> 00:18:19,060 Det kommer til å være, vel, vi skal for å tillate det å være tre av tre, 345 00:18:19,060 --> 00:18:21,580 eller vi kan også spille five med fem eller syv 346 00:18:21,580 --> 00:18:28,870 med sju tic-tac-toe hvis du hadde som, basert på noen dimensjon D. 347 00:18:28,870 --> 00:18:31,260 >> Og vi vil ha et par av hjelpefunksjoner 348 00:18:31,260 --> 00:18:34,360 som vil gjøre ting som initialisere screen-- eller sorry, 349 00:18:34,360 --> 00:18:38,900 initial våre variabler, tømme skjermen, tegne brettet på skjermen, 350 00:18:38,900 --> 00:18:41,060 en som sjekker et styre for å se hvorvidt 351 00:18:41,060 --> 00:18:44,520 det er en vinner, en som analyserer via kommandolinjen, 352 00:18:44,520 --> 00:18:50,670 bare for å hjelpe til, en som leser i innspill, og en funksjon som heter minimax. 353 00:18:50,670 --> 00:18:52,746 Og det er den ene vi vil bry seg mest om. 354 00:18:52,746 --> 00:18:54,120 Men la oss først se på de viktigste. 355 00:18:54,120 --> 00:18:57,490 356 00:18:57,490 --> 00:18:58,510 >> Hva skal vi gjøre? 357 00:18:58,510 --> 00:19:00,570 Vel, vi skal til analysere vår kommandolinje, 358 00:19:00,570 --> 00:19:04,300 bare lese inn og se hva dimensjon bord vi ønsker å ha. 359 00:19:04,300 --> 00:19:07,330 Vi vil initial vårt styre. 360 00:19:07,330 --> 00:19:10,360 Og så får vi inn én store vill loop, gjentatte ganger 361 00:19:10,360 --> 00:19:16,630 godta trekk til spillet er vant, eller det er ingen trekk igjen. 362 00:19:16,630 --> 00:19:20,560 Hver gang vi går gjennom det loop, vil vi tømme skjermen. 363 00:19:20,560 --> 00:19:23,290 Vi vil trekke brettet på skjermen. 364 00:19:23,290 --> 00:19:28,750 Og vi er bevisst slags abstrahere disse bort som subrutiner, 365 00:19:28,750 --> 00:19:32,030 slik at vi ikke trenger å bekymre deg for mye om detaljene i hvordan de skjer. 366 00:19:32,030 --> 00:19:33,480 >> Du vil ha koden senere i dag. 367 00:19:33,480 --> 00:19:37,970 Og hvis du ønsker å se gjennom og finne ut, du kan se dem alle. 368 00:19:37,970 --> 00:19:39,890 Men vi skal tegne et bord på skjermen. 369 00:19:39,890 --> 00:19:43,620 Og så skal vi sjekke og ser, har vi en vinner? 370 00:19:43,620 --> 00:19:46,290 Har noen vunnet denne kampen? 371 00:19:46,290 --> 00:19:49,260 Hvis de har, vil vi skrive ut ut en seier melding. 372 00:19:49,260 --> 00:19:51,680 Og vi vil avslutte spillet. 373 00:19:51,680 --> 00:19:54,510 >> Vi vil også sjekke og se om det er uavgjort. 374 00:19:54,510 --> 00:19:56,620 Det vil være lett å se om det er uavgjort. 375 00:19:56,620 --> 00:20:00,700 Det betyr at alle mellomrommene er full, men det har ikke vært en vinner. 376 00:20:00,700 --> 00:20:03,580 Vi kan erklære en uavgjort og bli ferdig. 377 00:20:03,580 --> 00:20:10,530 Så den virkelige meat-- hvis det er en maskin-spiller, 378 00:20:10,530 --> 00:20:14,120 vi vil tillate at Maskinen spiller å søke 379 00:20:14,120 --> 00:20:19,500 gjennom å bruke denne minimax algoritmen, å finne den beste farten at det kan. 380 00:20:19,500 --> 00:20:22,310 Og så får vi sette det farten opp. 381 00:20:22,310 --> 00:20:27,640 >> Ellers, hvis det er en menneskelig spiller, vi vil lese noen innspill fra det menneskelige. 382 00:20:27,640 --> 00:20:30,800 Og så om det er den menneskelige spiller eller maskinen spiller, 383 00:20:30,800 --> 00:20:32,800 vi vil gjøre et par lite biter av feilsjekking, 384 00:20:32,800 --> 00:20:36,910 sørg for at den holder seg innenfor grensene av de faktiske dimensjoner av styret 385 00:20:36,910 --> 00:20:40,040 som vi har, sørge at denne plassen er tom, 386 00:20:40,040 --> 00:20:43,570 at ingen har satt en brikke i det allerede. 387 00:20:43,570 --> 00:20:45,810 Og så får vi bare sette en brikke på brettet, 388 00:20:45,810 --> 00:20:51,550 endre spilleren til neste lag, og øke hvor mange trekk har skjedd. 389 00:20:51,550 --> 00:20:54,090 >> Det er den viktigste løkke for vår tic-tac-toe spillet. 390 00:20:54,090 --> 00:20:57,000 391 00:20:57,000 --> 00:21:02,340 Minimax, da, er nøyaktig algoritmen som vi tidligere. 392 00:21:02,340 --> 00:21:04,710 Den eneste justeringen som vi har gjort, slik at vi 393 00:21:04,710 --> 00:21:07,290 kan spille høyere dimensjonale styrene er vi har 394 00:21:07,290 --> 00:21:11,070 holdt denne ekstra parameter kalt dybde. 395 00:21:11,070 --> 00:21:14,870 Og dybde bare sier, hvis jeg er søke nedover gjennom det treet 396 00:21:14,870 --> 00:21:19,022 og jeg blir så langt ned utover et visst nivå dybde 397 00:21:19,022 --> 00:21:20,730 at jeg vil bare ikke å gå videre, 398 00:21:20,730 --> 00:21:25,630 Jeg kommer til å stoppe opp og bare evaluere styret på det tidspunktet. 399 00:21:25,630 --> 00:21:27,310 Jeg skal sjekke og se om det er en vinner. 400 00:21:27,310 --> 00:21:29,240 Hvis det er en vinner, jeg kommer tilbake dem. 401 00:21:29,240 --> 00:21:31,720 Ellers vil jeg gå gjennom en loop. 402 00:21:31,720 --> 00:21:34,380 Og jeg skal si, for alle mulige plasseringer 403 00:21:34,380 --> 00:21:38,080 at jeg kunne muligens ta så mitt trekk, vil jeg 404 00:21:38,080 --> 00:21:43,760 bygge en hypotetisk bord som omfatter mitt trekk på at styret, 405 00:21:43,760 --> 00:21:45,960 og deretter rekursivt kaller minimax. 406 00:21:45,960 --> 00:21:49,360 407 00:21:49,360 --> 00:21:53,900 >> Hvis det er mitt trekk, får jeg til å finne den en som har fått den største poengsummen. 408 00:21:53,900 --> 00:21:58,710 Hvis det er min motstanderens trekk, finner vi den som har fått minimum score. 409 00:21:58,710 --> 00:22:02,240 Og alt annet er bare journalføring. 410 00:22:02,240 --> 00:22:04,789 Greit, så la oss se denne kjøringen. 411 00:22:04,789 --> 00:22:06,830 Egentlig, kanskje vi kan få et par frivillige 412 00:22:06,830 --> 00:22:09,930 å komme opp og spille tic-tac-toe. 413 00:22:09,930 --> 00:22:12,780 [Uhørbart] én og én mer, to, rett der. 414 00:22:12,780 --> 00:22:13,550 Kom opp. 415 00:22:13,550 --> 00:22:19,290 416 00:22:19,290 --> 00:22:23,650 >> Så la oss gå videre og starte dette helt. 417 00:22:23,650 --> 00:22:24,150 Så, hi. 418 00:22:24,150 --> 00:22:24,920 >> PUBLIKUM: Hei. 419 00:22:24,920 --> 00:22:25,420 >> SPEAKER: Hva heter du? 420 00:22:25,420 --> 00:22:26,086 >> PUBLIKUM: Gorav. 421 00:22:26,086 --> 00:22:26,840 SPEAKER: Gorav. 422 00:22:26,840 --> 00:22:27,800 >> PUBLIKUM: Jeg er Layla. 423 00:22:27,800 --> 00:22:29,490 >> SPEAKER: Og Layla, og Layla, beklager. 424 00:22:29,490 --> 00:22:30,384 Kom opp. 425 00:22:30,384 --> 00:22:32,050 Gorav, kommer vi til å ha deg gå først. 426 00:22:32,050 --> 00:22:37,710 Og jeg kommer til å be deg om å være en ikke veldig god tic-tac-toe-spiller. 427 00:22:37,710 --> 00:22:40,130 OK, så alt presset er på deg. 428 00:22:40,130 --> 00:22:44,660 La oss se, men at vår maskin Spilleren kan faktisk gjøre noe smart. 429 00:22:44,660 --> 00:22:45,310 Så sett i gang. 430 00:22:45,310 --> 00:22:49,830 Du kommer til å skrive hvor koordinere du ønsker å sette X i. 431 00:22:49,830 --> 00:22:55,170 A0, OK, og maskinen har gått med en gang og sette sitt preg på A1. 432 00:22:55,170 --> 00:22:56,640 >> Sett O på brettet. 433 00:22:56,640 --> 00:22:58,970 Greit, nå gå videre. 434 00:22:58,970 --> 00:23:00,193 Hvor vil du reise? 435 00:23:00,193 --> 00:23:03,510 436 00:23:03,510 --> 00:23:05,090 C2. 437 00:23:05,090 --> 00:23:08,430 Vår maskin spiller har tatt midten kvadrat, har blokkert deg. 438 00:23:08,430 --> 00:23:10,320 Så det var en god, smart ting for den å gjøre. 439 00:23:10,320 --> 00:23:13,430 440 00:23:13,430 --> 00:23:14,250 Du har blokkert den. 441 00:23:14,250 --> 00:23:15,210 Det er utmerket. 442 00:23:15,210 --> 00:23:16,390 Det tar hjørnet der. 443 00:23:16,390 --> 00:23:23,890 444 00:23:23,890 --> 00:23:30,430 >> Og det kommer til å tvinge deg til å ta en siste plass, B0. 445 00:23:30,430 --> 00:23:32,220 Og den kampen ender uavgjort. 446 00:23:32,220 --> 00:23:35,030 Men det spilte en rimelig Kamp mot deg, ikke sant? 447 00:23:35,030 --> 00:23:36,956 Ok, takk veldig mye, Gorav. 448 00:23:36,956 --> 00:23:40,860 >> [BIFALL] 449 00:23:40,860 --> 00:23:44,723 >> Greit, Layla, vi kommer opp spillet på deg her. 450 00:23:44,723 --> 00:23:46,940 >> PUBLIKUM: Oh, great. 451 00:23:46,940 --> 00:23:49,950 >> SPEAKER: Vi kommer til å gi du fire av fire tic-tac-toe. 452 00:23:49,950 --> 00:23:54,760 Nå, i fire av fire, har du til å vinne med fire på rad, ikke tre på rad. 453 00:23:54,760 --> 00:23:56,135 Og det er bare din. 454 00:23:56,135 --> 00:24:02,180 455 00:24:02,180 --> 00:24:04,420 Så Layla tok D1. 456 00:24:04,420 --> 00:24:11,730 Vi nå kommer til å følge datamaskinen vår spiller her. 457 00:24:11,730 --> 00:24:16,910 Tre og tre tic-tac-toe er den type ting som er lett for oss alle. 458 00:24:16,910 --> 00:24:21,960 Men det er fortsatt hyggelig å se datamaskin spiller å gjøre smarte trekk. 459 00:24:21,960 --> 00:24:23,725 Fire av fire får være litt vanskeligere. 460 00:24:23,725 --> 00:24:42,960 461 00:24:42,960 --> 00:24:44,230 >> Bra gjort. 462 00:24:44,230 --> 00:24:46,210 All right, så Layla er avsluttet. 463 00:24:46,210 --> 00:24:48,270 Oh, og vi burde ha havnet der. 464 00:24:48,270 --> 00:24:51,870 Men la oss gjøre et mer opp her. 465 00:24:51,870 --> 00:24:53,480 Så Layla, takk. 466 00:24:53,480 --> 00:24:55,112 Bra gjort. 467 00:24:55,112 --> 00:24:57,517 >> [BIFALL] 468 00:24:57,517 --> 00:25:00,410 469 00:25:00,410 --> 00:25:04,750 >> Så vår tic-tac-toe spiller går gjennom og finner steder, 470 00:25:04,750 --> 00:25:07,040 løser dem ved hjelp av denne minimax. 471 00:25:07,040 --> 00:25:08,990 Og jeg hadde en dybdeinnstilling på den, slik at den 472 00:25:08,990 --> 00:25:11,010 ville ikke kjøre for fort, som er nok derfor 473 00:25:11,010 --> 00:25:16,790 Layla var i stand til å gå pent på forhånd som hun gjorde, og gjorde det veldig bra. 474 00:25:16,790 --> 00:25:20,450 Men disse systemene som bare gå gjennom og brute force 475 00:25:20,450 --> 00:25:23,870 gå dypere, og dypere, og dypere, og holde finne løsningen 476 00:25:23,870 --> 00:25:29,890 at de trenger, slike systemer er ganske vellykket på disse, vel, 477 00:25:29,890 --> 00:25:32,700 standard brettspill. 478 00:25:32,700 --> 00:25:37,060 >> Og faktisk, hvis vi ser på en tre og tre tic-tac-toe spill, 479 00:25:37,060 --> 00:25:40,040 Dette er i utgangspunktet et løst problem. 480 00:25:40,040 --> 00:25:45,430 Og dette er en fantastisk diagram fra Randall Munroe på XKCD, 481 00:25:45,430 --> 00:25:52,130 som viser hvilke flytter du bør ta, gitt motstanderens trekk. 482 00:25:52,130 --> 00:25:56,420 Dette er noe som vi kunne enkelt angi forhånd. 483 00:25:56,420 --> 00:26:00,180 Men hva skjer når vi får mer komplekse spill, mer intrikate spill, 484 00:26:00,180 --> 00:26:05,690 hvor det er større brett, mer muligheter, dypere strategi? 485 00:26:05,690 --> 00:26:09,660 >> Det viser seg at denne brute force søker fortsatt 486 00:26:09,660 --> 00:26:14,150 gjør rimelig bra, bortsett når du kommer til det punktet 487 00:26:14,150 --> 00:26:19,230 hvor det treet er så stort at du ikke kan representere det hele tatt. 488 00:26:19,230 --> 00:26:22,370 489 00:26:22,370 --> 00:26:28,280 Når du ikke kan beregne hele treet, når du ikke kan gå fremover og presse 490 00:26:28,280 --> 00:26:32,204 selv til et punkt der du har fått hele treet i minnet, 491 00:26:32,204 --> 00:26:34,370 eller om du kan få det i minnet, og det vil bare 492 00:26:34,370 --> 00:26:39,200 ta deg altfor lang tid å søke gjennom det, må du gjøre noe smartere. 493 00:26:39,200 --> 00:26:42,620 494 00:26:42,620 --> 00:26:46,450 >> For å gjøre det, må gjøre to ting. 495 00:26:46,450 --> 00:26:49,030 Først må du finne noen måte å begrense din dybde. 496 00:26:49,030 --> 00:26:50,370 Vel, det er OK. 497 00:26:50,370 --> 00:26:55,740 Vi kan finne noen fine, minimum og si, du kan bare gå så dypt. 498 00:26:55,740 --> 00:27:00,890 Men når du gjør det, betyr det at du har disse delvis ufullstendige boards. 499 00:27:00,890 --> 00:27:04,770 Og du må velge, jeg liker dette delvis ufullstendig bord, 500 00:27:04,770 --> 00:27:08,600 eller dette delvis ufullstendig bord? 501 00:27:08,600 --> 00:27:11,910 >> Og på våre fire av fire tic-tac-toe spill, 502 00:27:11,910 --> 00:27:15,240 datamaskinen vår spiller fikk ned til bunnen, og det er sagt, 503 00:27:15,240 --> 00:27:16,800 Jeg har to forskjellige brett. 504 00:27:16,800 --> 00:27:17,940 Verken en er en seier. 505 00:27:17,940 --> 00:27:19,120 Verken en er et tap. 506 00:27:19,120 --> 00:27:22,070 Verken en er uavgjort. 507 00:27:22,070 --> 00:27:24,100 Hvordan kan jeg velge mellom dem? 508 00:27:24,100 --> 00:27:26,200 Og det hadde ikke en smart måte å gjøre det. 509 00:27:26,200 --> 00:27:28,910 510 00:27:28,910 --> 00:27:32,850 >> Vi ser denne typen Evalueringen skjer hele tiden 511 00:27:32,850 --> 00:27:35,290 som vi får inn mer komplekse spill. 512 00:27:35,290 --> 00:27:37,600 Chess er et godt eksempel. 513 00:27:37,600 --> 00:27:41,550 I sjakk, har vi først av alt, en større bord. 514 00:27:41,550 --> 00:27:43,370 Vi har langt flere stykker. 515 00:27:43,370 --> 00:27:47,930 Og plasseringen av disse brikkene og den måte at disse stykker beveger 516 00:27:47,930 --> 00:27:50,370 er kritisk viktig. 517 00:27:50,370 --> 00:27:53,700 Så hvis jeg ønsker å bruke minimax, Jeg må være i stand til å spesifisere 518 00:27:53,700 --> 00:27:58,240 og si, dette forumet, hvor ingen har vunnet eller tapt ennå, 519 00:27:58,240 --> 00:28:04,310 er liksom bedre enn dette andre bord, der ingen har vunnet eller tapt. 520 00:28:04,310 --> 00:28:06,740 >> For å gjøre det, kan jeg gjøre ting som jeg kanskje bare 521 00:28:06,740 --> 00:28:10,787 telle hvor mange brikker må jeg og hvor mange brikker har du? 522 00:28:10,787 --> 00:28:12,870 Eller jeg kan gi forskjellig stk ulike punkter. 523 00:28:12,870 --> 00:28:14,420 Min dronning er verdt 20 poeng. 524 00:28:14,420 --> 00:28:16,500 Din bonde er verdt ett poeng. 525 00:28:16,500 --> 00:28:18,920 Hvem har flere poeng totalt? 526 00:28:18,920 --> 00:28:22,300 Eller jeg kan vurdere ting liker, hvem som fikk bedre styreverv? 527 00:28:22,300 --> 00:28:26,820 Hvem sin tur er det neste, noe som jeg kan 528 00:28:26,820 --> 00:28:31,220 trenger for å vurdere mer nøyaktig hvilke av disse mulighetene 529 00:28:31,220 --> 00:28:34,660 er bedre uten uttømmende vurderer 530 00:28:34,660 --> 00:28:36,565 hver bevegelse som kan komme etter det. 531 00:28:36,565 --> 00:28:39,740 532 00:28:39,740 --> 00:28:45,130 >> Nå for å gjøre dette arbeidet, en av de tingene som er 533 00:28:45,130 --> 00:28:48,680 kommer til å bli veldig viktig for oss er ikke bare å flytte rett 534 00:28:48,680 --> 00:28:53,720 ned til en bestemt dybde grense, men å være i stand til å si, 535 00:28:53,720 --> 00:28:59,380 en av disse ideene som jeg har er så ille at det er 536 00:28:59,380 --> 00:29:02,280 ikke verdt å vurdere alle de mulige måter 537 00:29:02,280 --> 00:29:06,680 at ting kan gå fra vondt til verre. 538 00:29:06,680 --> 00:29:12,760 For å gjøre det, vil vi legge inn minimax et prinsipp som kalles alph-beta. 539 00:29:12,760 --> 00:29:16,340 Og alfa-beta sier hvis du har en dårlig idé, 540 00:29:16,340 --> 00:29:22,840 ikke kast bort tid på å prøve å finne ut nøyaktig hvor ille det er. 541 00:29:22,840 --> 00:29:24,990 >> Så her er hva vi skal gjøre. 542 00:29:24,990 --> 00:29:28,620 Vi kommer til å ta den samme prinsipper som vi hadde før, 543 00:29:28,620 --> 00:29:32,200 samme minimax typen søk, bare vi er 544 00:29:32,200 --> 00:29:37,570 kommer til å holde orden, ikke bare av faktiske verdiene som vi har, men vi vil 545 00:29:37,570 --> 00:29:41,440 holde styr på den best mulige verdi at jeg kunne få, 546 00:29:41,440 --> 00:29:45,700 og den verst tenkelige Utfallet jeg kunne ha. 547 00:29:45,700 --> 00:29:50,470 Og hver gang den verst tenkelige ting ser sannsynlig, 548 00:29:50,470 --> 00:29:52,694 Jeg vil forlate den delen av treet. 549 00:29:52,694 --> 00:29:54,610 Og jeg vil ikke engang bry å se på det lenger. 550 00:29:54,610 --> 00:29:57,680 551 00:29:57,680 --> 00:30:02,600 >> All right, så tenk at vi begynner med dette nøyaktig samme spillet treet. 552 00:30:02,600 --> 00:30:05,200 Og nå skal vi gå ned igjen, helt ned 553 00:30:05,200 --> 00:30:07,200 til at venstre hjørne. 554 00:30:07,200 --> 00:30:11,180 Og i det nederste venstre hjørne, vi ser og vi evaluerer dette forumet. 555 00:30:11,180 --> 00:30:15,700 Kanskje det er en fire av fire tic-tac-toe bord, eller kanskje det er et sjakkbrett. 556 00:30:15,700 --> 00:30:18,620 Men vi ser på det, og vi evaluerer det, og vi får en verdi på åtte. 557 00:30:18,620 --> 00:30:22,290 558 00:30:22,290 --> 00:30:28,030 >> På dette tidspunktet vet vi at vi kommer til å få minst 559 00:30:28,030 --> 00:30:32,380 åtte poeng fra denne bunnen avgjørelse. 560 00:30:32,380 --> 00:30:36,620 Det spiller ingen rolle hva den andre to er, at syv og at to. 561 00:30:36,620 --> 00:30:38,580 De kunne være noen verdier de ønsket å være. 562 00:30:38,580 --> 00:30:41,279 Vi kommer til å få på minst åtte poeng. 563 00:30:41,279 --> 00:30:43,070 Greit, men vi kunne gå videre og sjekke. 564 00:30:43,070 --> 00:30:45,080 Kanskje en av dem er bedre enn åtte. 565 00:30:45,080 --> 00:30:46,000 >> Vi ser på de syv. 566 00:30:46,000 --> 00:30:46,910 Er det bedre enn åtte? 567 00:30:46,910 --> 00:30:48,680 Nei, det betyr ikke endre vår mening i det hele tatt. 568 00:30:48,680 --> 00:30:49,460 Vi ser på de to. 569 00:30:49,460 --> 00:30:50,543 Er det bedre enn åtte? 570 00:30:50,543 --> 00:30:52,580 Nei, det betyr ikke endre vår mening i det hele tatt. 571 00:30:52,580 --> 00:30:55,480 Så nå vet vi at vi har brukt opp alle mulighetene der. 572 00:30:55,480 --> 00:30:58,330 Vi kommer ikke til å få noe bedre enn åtte. 573 00:30:58,330 --> 00:31:01,310 Vi kommer til å få nøyaktig åtte. 574 00:31:01,310 --> 00:31:03,825 >> Og så vi endre det node og si, er at nå en visshet. 575 00:31:03,825 --> 00:31:07,010 576 00:31:07,010 --> 00:31:10,270 Vi går opp ett nivå over det. 577 00:31:10,270 --> 00:31:13,820 Og nå vet vi noe om at minimalisering nivå. 578 00:31:13,820 --> 00:31:18,560 Vi vet at vi aldri kommer til å få mer enn åtte poeng hvis vi går ned 579 00:31:18,560 --> 00:31:20,910 den retningen. 580 00:31:20,910 --> 00:31:22,980 For selv om de to andre grener slå ut 581 00:31:22,980 --> 00:31:26,170 å være fantastisk og verdt tusenvis av poeng hver, 582 00:31:26,170 --> 00:31:31,666 vår motstander vil gi oss minimum, og gi oss åtte. 583 00:31:31,666 --> 00:31:32,790 Greit, vel, la oss se. 584 00:31:32,790 --> 00:31:35,190 Vi vil fortsette å gå ned den veien. 585 00:31:35,190 --> 00:31:38,490 Vi går ned til at midten på venstre side. 586 00:31:38,490 --> 00:31:40,560 Vi ser ned, og vi ser det er en ni. 587 00:31:40,560 --> 00:31:45,590 Vi vet at vi kommer til å få minst ni poeng ved å gå ned 588 00:31:45,590 --> 00:31:47,720 at middelvei. 589 00:31:47,720 --> 00:31:52,110 Og på dette punktet, kan vi bare ta en pause. 590 00:31:52,110 --> 00:31:56,910 Og vi kan si, se, jeg vet i nivået ovenfor, 591 00:31:56,910 --> 00:32:01,160 Jeg kommer til å få noe mer enn åtte poeng ved å gå ned denne retningen. 592 00:32:01,160 --> 00:32:05,670 Men hvis jeg gikk ned på midten bane i stedet for den venstre bane, 593 00:32:05,670 --> 00:32:08,980 Jeg ville få minst ni poeng. 594 00:32:08,980 --> 00:32:13,590 >> Min motstander er aldri kommer til la meg gå ned den middelveien. 595 00:32:13,590 --> 00:32:14,650 De kommer til å velge. 596 00:32:14,650 --> 00:32:18,140 Og de kommer til å velge stien til venstre mot åtte, 597 00:32:18,140 --> 00:32:23,650 heller enn på midten langs hva er minst ni poeng. 598 00:32:23,650 --> 00:32:25,334 Så på det punktet, vil jeg stoppe. 599 00:32:25,334 --> 00:32:26,500 Og jeg skal si, vet du hva? 600 00:32:26,500 --> 00:32:29,990 Jeg trenger ikke å se noen mer ned i den retningen. 601 00:32:29,990 --> 00:32:32,270 Fordi jeg aldri kommer til å komme dit. 602 00:32:32,270 --> 00:32:36,660 >> Jeg kan hoppe over det ene, og jeg kan hoppe over at seks, 603 00:32:36,660 --> 00:32:39,720 fordi det aldri kommer til å skje. 604 00:32:39,720 --> 00:32:42,470 Så jeg skal gå ned og jeg skal vurdere neste mulighet. 605 00:32:42,470 --> 00:32:44,830 Jeg går der nede og jeg sier, jeg ser en to. 606 00:32:44,830 --> 00:32:47,125 Jeg vet at hvis jeg får til her, er jeg kommer til å få minst to. 607 00:32:47,125 --> 00:32:49,810 608 00:32:49,810 --> 00:32:50,470 OK. 609 00:32:50,470 --> 00:32:51,520 Jeg holde det gående. 610 00:32:51,520 --> 00:32:52,440 Jeg ser en fire. 611 00:32:52,440 --> 00:32:54,920 Jeg vet at jeg kommer til å få minst fire. 612 00:32:54,920 --> 00:32:57,200 Det er fortsatt mye mellom fire og åtte, skjønt. 613 00:32:57,200 --> 00:32:58,454 Så jeg holde det gående. 614 00:32:58,454 --> 00:32:59,870 Jeg ser ned og jeg ser det er ett. 615 00:32:59,870 --> 00:33:01,614 Greit, jeg vet om Jeg går ned denne veien, 616 00:33:01,614 --> 00:33:03,280 Jeg kommer til å være i stand til å velge de fire. 617 00:33:03,280 --> 00:33:06,540 618 00:33:06,540 --> 00:33:08,980 Hva er min motstander kommer til å gjøre? 619 00:33:08,980 --> 00:33:12,310 Mellom noe som gir meg åtte, noe som gir meg fire, 620 00:33:12,310 --> 00:33:14,730 og noe som gir meg minst ni, 621 00:33:14,730 --> 00:33:17,550 vel, han kommer til å gi meg de fire. 622 00:33:17,550 --> 00:33:20,110 Og jeg vet nå på Helt øverst, jeg kommer 623 00:33:20,110 --> 00:33:23,145 å være i stand til å få minst fire poeng ut av dette spillet. 624 00:33:23,145 --> 00:33:27,030 625 00:33:27,030 --> 00:33:30,900 >> Hele ideen om alfa-beta er å kutte av deler treet slik 626 00:33:30,900 --> 00:33:32,530 at jeg ikke ser på dem lenger. 627 00:33:32,530 --> 00:33:35,964 Men det fortsatt ser ut som jeg har vært ser på mye av treet. 628 00:33:35,964 --> 00:33:36,880 La oss holde det gående ned. 629 00:33:36,880 --> 00:33:38,305 Vi vil gå ned neste nå. 630 00:33:38,305 --> 00:33:39,680 Nede på bunnen, finner jeg en en. 631 00:33:39,680 --> 00:33:41,030 Jeg vet at jeg kommer til å få minst én. 632 00:33:41,030 --> 00:33:41,690 Jeg holde utkikk. 633 00:33:41,690 --> 00:33:42,625 >> Jeg finner en tre. 634 00:33:42,625 --> 00:33:44,250 Jeg vet at jeg kommer til å få minst tre. 635 00:33:44,250 --> 00:33:44,840 Jeg holde det gående. 636 00:33:44,840 --> 00:33:45,660 Jeg finner en fem. 637 00:33:45,660 --> 00:33:49,760 Jeg vet at jeg kommer til å få fem- hvis jeg får ned i den banen. 638 00:33:49,760 --> 00:33:52,580 Og jeg vet også da at min motstander, hvis jeg 639 00:33:52,580 --> 00:33:55,510 velge midt de tre store valg, 640 00:33:55,510 --> 00:34:01,440 han kommer til å gi meg noe som er fem eller mindre. 641 00:34:01,440 --> 00:34:02,150 >> OK. 642 00:34:02,150 --> 00:34:03,400 Jeg kan holde det gående der. 643 00:34:03,400 --> 00:34:06,470 Jeg kan se ned og jeg kan si, hva skal jeg 644 00:34:06,470 --> 00:34:08,239 å få hvis jeg går ned midt banen? 645 00:34:08,239 --> 00:34:09,909 Jeg kommer til å få, vel tre der. 646 00:34:09,909 --> 00:34:12,080 Jeg kommer til å få noe det er minst tre. 647 00:34:12,080 --> 00:34:16,030 Det er fortsatt ting mellom tre og fem, så jeg holde utkikk. 648 00:34:16,030 --> 00:34:20,203 Oh, en ni, vil jeg definitivt ta det over en tre. 649 00:34:20,203 --> 00:34:22,744 Jeg kommer til å få minst ni hvis jeg går ned at middelveien. 650 00:34:22,744 --> 00:34:25,530 651 00:34:25,530 --> 00:34:31,010 >> Nå er min motstander stopper og sier: ser, er det ingen vits lenger. 652 00:34:31,010 --> 00:34:33,669 Jeg vet at min minimering motstander, han 653 00:34:33,669 --> 00:34:36,210 kommer til å gi meg det som er mindre enn eller lik fem, 654 00:34:36,210 --> 00:34:39,030 snarere enn det som er større enn eller lik ni. 655 00:34:39,030 --> 00:34:39,530 Jeg stopper. 656 00:34:39,530 --> 00:34:40,779 Jeg ser ikke noe mer på det. 657 00:34:40,779 --> 00:34:43,280 Jeg holde det gående. 658 00:34:43,280 --> 00:34:44,850 >> Jeg ser ned på denne. 659 00:34:44,850 --> 00:34:46,370 Ned til bunnen, finner jeg en sekser. 660 00:34:46,370 --> 00:34:50,040 Jeg vet at jeg kommer til å få minst seks. 661 00:34:50,040 --> 00:34:53,130 Og hva kan jeg gjøre? 662 00:34:53,130 --> 00:34:54,877 Jeg kan stoppe. 663 00:34:54,877 --> 00:34:57,460 Fordi det er et valg mellom noe som er minst seks 664 00:34:57,460 --> 00:34:59,250 og noe som er mindre enn fem, er han 665 00:34:59,250 --> 00:35:02,570 kommer til å gi meg den tingen det er mindre enn fem. 666 00:35:02,570 --> 00:35:04,779 Og nå jeg vet at jeg kommer til å få akkurat det valget. 667 00:35:04,779 --> 00:35:06,195 Jeg kommer til å få at fem valg. 668 00:35:06,195 --> 00:35:08,980 669 00:35:08,980 --> 00:35:10,010 >> Jeg går opp til toppen. 670 00:35:10,010 --> 00:35:11,450 Som jeg kommer til å velge mellom noe 671 00:35:11,450 --> 00:35:14,449 som er større enn eller lik fire, eller noe som er lik fem? 672 00:35:14,449 --> 00:35:17,140 Jeg kommer til å ta noe som er minst fem. 673 00:35:17,140 --> 00:35:20,490 Jeg går ned den siste banen, alle helt ned til bunnen. 674 00:35:20,490 --> 00:35:21,260 Det er en en. 675 00:35:21,260 --> 00:35:23,410 OK, minst jeg kommer til å få ett poeng. 676 00:35:23,410 --> 00:35:24,427 Jeg holde det gående. 677 00:35:24,427 --> 00:35:25,760 To, oh, det er bedre enn ett. 678 00:35:25,760 --> 00:35:27,100 Jeg kommer til å få minst to. 679 00:35:27,100 --> 00:35:28,610 Jeg finner en tre. 680 00:35:28,610 --> 00:35:31,450 Jeg vet at jeg kommer til å få tre. 681 00:35:31,450 --> 00:35:34,690 >> Og punktet som ovenfor, min motstander kommer 682 00:35:34,690 --> 00:35:38,540 å gi meg noe som er mindre enn eller lik tre. 683 00:35:38,540 --> 00:35:40,940 Og nå kan jeg stoppe. 684 00:35:40,940 --> 00:35:46,290 Fordi i valget mellom meg å være stand til å få en fem og min motstander 685 00:35:46,290 --> 00:35:52,290 gi meg noe mindre enn tre, Jeg er alltid kommer til å ta det fem. 686 00:35:52,290 --> 00:35:56,810 Så jeg ikke vurdere det nederste del av treet i det hele tatt. 687 00:35:56,810 --> 00:35:59,470 >> Nå kan dette virke mindre. 688 00:35:59,470 --> 00:36:03,630 Men når små biter av aritmetikk, større enn og mindre enn, 689 00:36:03,630 --> 00:36:10,640 kan skjære bort hele deler av denne eksponentielt voksende treet, 690 00:36:10,640 --> 00:36:14,280 som fører til et stort Mengden av sparing, sparing 691 00:36:14,280 --> 00:36:17,630 som er store nok til at jeg kan begynne å spille kompetitivt 692 00:36:17,630 --> 00:36:21,330 på flere komplekse spill. 693 00:36:21,330 --> 00:36:27,030 >> Greit, hvis vi ser på størrelsen og kompleksiteten av forskjellige spill, 694 00:36:27,030 --> 00:36:29,470 tic-tac-toe var vårt enkle eksempel. 695 00:36:29,470 --> 00:36:32,150 Vi har fått et lite bord, tre og tre. 696 00:36:32,150 --> 00:36:36,030 Vi får i beste fall et gjennomsnitt på om fire ulike valg 697 00:36:36,030 --> 00:36:38,440 som vi går gjennom spillet. 698 00:36:38,440 --> 00:36:42,720 Vi har et sted rundt 10 til femte mulige forskjellige blader. 699 00:36:42,720 --> 00:36:45,200 Og bygge en tic-tac-toe spiller, vel, vi bare gjorde det. 700 00:36:45,200 --> 00:36:47,460 Det er lett. 701 00:36:47,460 --> 00:36:49,890 >> Hvis vi går opp til noe mer Komplekset, som Connect Four. 702 00:36:49,890 --> 00:36:53,170 Husker du dette spillet hvor du slippe den lille tokens i? 703 00:36:53,170 --> 00:36:58,490 Det er en seks av sju bord, ikke så mye større, fortsatt 704 00:36:58,490 --> 00:37:00,770 har omtrent samme forgrening faktor som tic-tac-toe. 705 00:37:00,770 --> 00:37:05,410 Jeg har ca fire valg hvor jeg kan sette ting i. 706 00:37:05,410 --> 00:37:10,760 Men nå har jeg fått mye mer fører, 10 til 21. makt. 707 00:37:10,760 --> 00:37:14,440 Det er noe som er lett nok at vi løser det med en gang. 708 00:37:14,440 --> 00:37:17,560 >> Checkers, mer complex-- deg fikk en åtte av åtte bord. 709 00:37:17,560 --> 00:37:20,570 Du er bare på halvparten av dem når som helst, skjønt. 710 00:37:20,570 --> 00:37:24,930 Du har en forgrening faktor som er omtrent 2,8. 711 00:37:24,930 --> 00:37:28,160 Vel, vi har fått et par beveger du kan ta. 712 00:37:28,160 --> 00:37:33,870 Du har ca 10 til 31. blader, større og større, og større områder. 713 00:37:33,870 --> 00:37:37,340 Som jeg har til å søke gjennom de større og større områder, 714 00:37:37,340 --> 00:37:42,220 det er da ting som alpha-beta og å være i stand til å kutte vekk hele grener 715 00:37:42,220 --> 00:37:44,420 blir avgjørende. 716 00:37:44,420 --> 00:37:47,440 >> Nå brikker var lett nok i 1992. 717 00:37:47,440 --> 00:37:51,400 Et dataprogram som kalles Chinook slå verdens brikker 718 00:37:51,400 --> 00:37:53,590 champion, Marion Tinsley. 719 00:37:53,590 --> 00:37:57,260 Og siden da, nei menneskelige mester spiller har 720 00:37:57,260 --> 00:38:02,290 vært i stand til å slå de beste beregningssystemer. 721 00:38:02,290 --> 00:38:06,570 Hvis vi ser på noe som sjakk, nå igjen, har vi en åtte av åtte bord. 722 00:38:06,570 --> 00:38:09,870 Men vi har mye mer kompleks stykker, mye mer komplekse bevegelser. 723 00:38:09,870 --> 00:38:14,610 Vi har et forgrenings faktor på ca. 35, 35 mulige trekk i gjennomsnitt 724 00:38:14,610 --> 00:38:20,030 at jeg kan ta, og en stat plass, et antall blader 725 00:38:20,030 --> 00:38:28,950 som er vokst til 10 til 123. makt, enorme mengder av muligheter. 726 00:38:28,950 --> 00:38:35,570 >> Enda moderne prosessorer er i stand til å gjøre dette vellykket. 727 00:38:35,570 --> 00:38:43,900 I 1995 og deretter i 1997, en datamaskin program kalt Deep Blue bygget av IBM 728 00:38:43,900 --> 00:38:49,601 som kjørte på en gigantisk superdatamaskin slå den gjeldende verdensmesteren, 729 00:38:49,601 --> 00:38:50,225 Garry Kasparov. 730 00:38:50,225 --> 00:38:54,000 731 00:38:54,000 --> 00:38:56,650 Dette var et vendepunkt. 732 00:38:56,650 --> 00:39:00,620 I dag, men at samme behandling makten sitter på min MacBook. 733 00:39:00,620 --> 00:39:04,180 734 00:39:04,180 --> 00:39:06,440 >> Prosessorhastigheten holder stadig raskere og raskere. 735 00:39:06,440 --> 00:39:09,500 Vi kan vurdere mer og mer styrene raskere og raskere. 736 00:39:09,500 --> 00:39:14,550 Men enda viktigere, har vi bedre evaluerings funksjoner og bedre beskjæring 737 00:39:14,550 --> 00:39:15,460 metoder. 738 00:39:15,460 --> 00:39:19,560 Så vi kan søke på plass mer complexly. 739 00:39:19,560 --> 00:39:22,350 Den største av styret spill som vi kan tenke på, 740 00:39:22,350 --> 00:39:26,310 noe sånt Go som er fikk en 19 med 19 bord, 741 00:39:26,310 --> 00:39:32,490 nå plutselig er vi forbi det punktet hvor beregningssystemer kan vinne. 742 00:39:32,490 --> 00:39:34,530 Det er ingen beregnings system der ute 743 00:39:34,530 --> 00:39:38,880 som kan slå en profesjonell Go-spiller. 744 00:39:38,880 --> 00:39:45,000 Den beste systemer i dag rang det om den slags god amatørnivå. 745 00:39:45,000 --> 00:39:49,285 Så det er fortsatt ganske mye ut det at du ikke kan få til enda. 746 00:39:49,285 --> 00:39:51,840 747 00:39:51,840 --> 00:39:55,360 >> Greit, disse tradisjonelle brettspill, 748 00:39:55,360 --> 00:39:58,560 slike systemer der vi bygge dette minimax, enten det har 749 00:39:58,560 --> 00:40:06,300 alfa-beta eller ikke, disse algoritmene arbeide fordi det er visse begrensninger. 750 00:40:06,300 --> 00:40:08,520 Vi har perfekt informasjon om i verden. 751 00:40:08,520 --> 00:40:11,690 Vi vet hvor alle bitene er. 752 00:40:11,690 --> 00:40:13,570 Verden er statisk. 753 00:40:13,570 --> 00:40:16,220 Ingen får flytte brikkene rundt mens jeg er 754 00:40:16,220 --> 00:40:20,640 sitter der og tenker, tar min tur. 755 00:40:20,640 --> 00:40:23,140 Det er en handling plass som er diskret. 756 00:40:23,140 --> 00:40:26,900 Jeg kan sette min bonde her, eller jeg kan sette min bonde her. 757 00:40:26,900 --> 00:40:30,520 Jeg har ikke lov til å sette min bonde på linjen mellom de to rutene. 758 00:40:30,520 --> 00:40:34,430 759 00:40:34,430 --> 00:40:36,520 >> Og til slutt, handlingene er deterministisk. 760 00:40:36,520 --> 00:40:39,790 Jeg vet at hvis jeg sier, tårn til ridder tre, 761 00:40:39,790 --> 00:40:44,660 min tårn kommer til å ende opp på ridder tre, så lenge det er en gyldig flytte. 762 00:40:44,660 --> 00:40:47,830 Det er ingen usikkerhet om det. 763 00:40:47,830 --> 00:40:52,490 Nå som jeg går til mer forskjellige typer spill, 764 00:40:52,490 --> 00:40:55,960 vi nødt til å bryte disse forutsetningene. 765 00:40:55,960 --> 00:41:00,020 >> Hva hvis jeg går til noe liker klassiske videospill? 766 00:41:00,020 --> 00:41:04,180 Her er et utvalg av video spill fra Atari 2600. 767 00:41:04,180 --> 00:41:05,180 Hva har jeg der oppe? 768 00:41:05,180 --> 00:41:08,440 Jeg har Frogger, Space Invaders, fallgruve, og Pac-Man. 769 00:41:08,440 --> 00:41:11,290 770 00:41:11,290 --> 00:41:14,840 Hva slags miljøer har jeg her nå? 771 00:41:14,840 --> 00:41:16,900 Hvilke av disse forutsetningene må jeg bryte? 772 00:41:16,900 --> 00:41:19,410 773 00:41:19,410 --> 00:41:21,570 >> Vel, det kommer an på spillet. 774 00:41:21,570 --> 00:41:28,170 Jeg kunne spille sjakk på 2600, og det ville være akkurat som det var før. 775 00:41:28,170 --> 00:41:33,020 For de fleste av disse systemene, er det fullstendig kunnskap om verden. 776 00:41:33,020 --> 00:41:36,300 Det er helt deterministiske handlinger. 777 00:41:36,300 --> 00:41:38,330 Men vanligvis er verden ikke lenger statisk. 778 00:41:38,330 --> 00:41:41,970 Det vil si, mens jeg sitter der venter, er noe bevegelse. 779 00:41:41,970 --> 00:41:44,320 Spøkelsene kommer til å få meg. 780 00:41:44,320 --> 00:41:46,570 Skorpionen følger meg under. 781 00:41:46,570 --> 00:41:48,880 Space Invaders er kommer nærmere og nærmere. 782 00:41:48,880 --> 00:41:54,020 783 00:41:54,020 --> 00:41:55,510 Hvor godt kan vi gjøre mot disse? 784 00:41:55,510 --> 00:41:58,640 785 00:41:58,640 --> 00:42:02,790 >> For noen år siden, Google hadde et prosjekt kalt 786 00:42:02,790 --> 00:42:12,030 DeepMind, der de trente en datamaskin program for å spille Atari 2600 spill. 787 00:42:12,030 --> 00:42:16,120 Og hvis du tror dette er ikke alvorlig virksomheten, resultatene av sine studier 788 00:42:16,120 --> 00:42:19,920 ble publisert i Nature, så omtrent så god en publikasjon 789 00:42:19,920 --> 00:42:22,500 som du kan muligens få. 790 00:42:22,500 --> 00:42:24,340 Og her er hvor godt de har utført. 791 00:42:24,340 --> 00:42:29,220 >> De har en algoritme som satt og så bare skjerm innganger. 792 00:42:29,220 --> 00:42:34,080 Det fikk ingen instruksjoner hodet om reglene i spillet. 793 00:42:34,080 --> 00:42:42,610 Og det var ment å finne ut, baserte sin poengsum, hvor godt det gjorde. 794 00:42:42,610 --> 00:42:46,560 Dette var et system som brukes til noe kalt forsterkning læring. 795 00:42:46,560 --> 00:42:48,380 Det vil si, det så ut på sitt poengsum. 796 00:42:48,380 --> 00:42:51,620 Og hvis det fikk en god score, det er sagt, Jeg bør huske disse tingene. 797 00:42:51,620 --> 00:42:53,310 Og jeg skal gjøre dem igjen. 798 00:42:53,310 --> 00:42:56,450 Og hvis det fikk en dårlig score, det er sagt, Jeg skal ikke gjøre disse tingene på nytt. 799 00:42:56,450 --> 00:42:59,750 800 00:42:59,750 --> 00:43:03,430 >> Dette er ytelsen av disse trente systemer 801 00:43:03,430 --> 00:43:07,490 lov til å spille for en noen timer på hvert spill, 802 00:43:07,490 --> 00:43:12,490 sammenlignet mot profesjonelle spillere. 803 00:43:12,490 --> 00:43:19,670 Så for alle spillene som er til venstre side av denne linje, 804 00:43:19,670 --> 00:43:25,920 Denne selv trent dataprogram bedre enn de profesjonelle spillere. 805 00:43:25,920 --> 00:43:29,690 Og for alt til rett, profesjonelle spillere 806 00:43:29,690 --> 00:43:30,920 fortsatt var best. 807 00:43:30,920 --> 00:43:34,040 808 00:43:34,040 --> 00:43:36,850 For noe som visste ingenting om reglene, som 809 00:43:36,850 --> 00:43:43,020 visste ingenting om strukturen av spill, er dette imponerende ytelse. 810 00:43:43,020 --> 00:43:45,660 Og dette er hva vi er i stand til å gjøre i dag. 811 00:43:45,660 --> 00:43:50,239 >> OK, sier du, men hvis vi tenke på AI i spill, 812 00:43:50,239 --> 00:43:52,530 normalt tror vi om ting som vi faktisk kan 813 00:43:52,530 --> 00:43:54,180 sitte ned og spille mot. 814 00:43:54,180 --> 00:43:58,760 Hvis jeg setter meg ned og jeg spiller Starcraft, eller jeg spiller Gratis Sieve, 815 00:43:58,760 --> 00:44:01,870 datamaskinen motstanderen er person styre Zerg, 816 00:44:01,870 --> 00:44:06,770 eller kontrollere andre kultur. 817 00:44:06,770 --> 00:44:11,920 Hvordan gjør de spillerne faktisk finne sine trekk? 818 00:44:11,920 --> 00:44:18,810 >> Vel, disse spillene strukturert mye på samme måte som våre brettspill, 819 00:44:18,810 --> 00:44:22,250 disse spillene at vi vil kollektivt kaller fire X Games, 820 00:44:22,250 --> 00:44:26,040 utforske, expand-- glemme de. 821 00:44:26,040 --> 00:44:26,980 Hva er de? 822 00:44:26,980 --> 00:44:32,150 Utforske, utvide og slukke, Jeg tror jeg er den siste. 823 00:44:32,150 --> 00:44:36,060 Men de er i utgangspunktet lete- og erobre spill. 824 00:44:36,060 --> 00:44:41,020 Vanligvis datamaskinen motstanderen det har begrenset informasjon. 825 00:44:41,020 --> 00:44:45,486 De vet ikke nøyaktig hva som er skjer bak at krigens tåke. 826 00:44:45,486 --> 00:44:47,735 De får ikke til å se hva du har i din beholdning. 827 00:44:47,735 --> 00:44:50,240 828 00:44:50,240 --> 00:44:52,800 >> Det er et miljø som er dynamisk. 829 00:44:52,800 --> 00:44:56,180 Alt er i endring hele tiden. 830 00:44:56,180 --> 00:45:00,290 Du får ikke til å sitte og vente med å ta ditt trekk. 831 00:45:00,290 --> 00:45:02,810 Men det meste er fortsatt diskret. 832 00:45:02,810 --> 00:45:04,200 Jeg må sette min by her. 833 00:45:04,200 --> 00:45:06,750 Eller jeg må sette min by her. 834 00:45:06,750 --> 00:45:08,950 Og alt er deterministisk. 835 00:45:08,950 --> 00:45:14,660 Når jeg sier, flytte min enhet her, min enhet beveger seg her, med mindre en hindring plutselig 836 00:45:14,660 --> 00:45:17,700 kommer inn i bildet. 837 00:45:17,700 --> 00:45:21,610 Nå, det er ikke alle PC spill som er der ute i dag. 838 00:45:21,610 --> 00:45:27,320 >> Hvis jeg går og jeg spiller et første person typen spill, noe som Thief eller Fallout 839 00:45:27,320 --> 00:45:33,350 eller Skyrim, eller Halo, nå Jeg har datamotstandere 840 00:45:33,350 --> 00:45:37,860 som er der ute som har en helt annen situasjon. 841 00:45:37,860 --> 00:45:40,020 De har, igjen, begrenset informasjon. 842 00:45:40,020 --> 00:45:43,420 De bare kan se en viss synsfelt. 843 00:45:43,420 --> 00:45:45,180 Miljøet er fortsatt dynamisk. 844 00:45:45,180 --> 00:45:48,280 Ting er i endring hele tiden. 845 00:45:48,280 --> 00:45:52,300 >> Men nå har jeg en mye mer kontinuerlig virkning plass. 846 00:45:52,300 --> 00:45:57,170 Jeg kan bare titte en litt ut av døråpningen. 847 00:45:57,170 --> 00:46:00,650 Og noen spill, min handlinger er stokastisk. 848 00:46:00,650 --> 00:46:04,590 Jeg får prøve å hoppe over den veggen, men jeg har en sjanse for å mislykkes. 849 00:46:04,590 --> 00:46:08,280 850 00:46:08,280 --> 00:46:14,550 Disse typer spill nærmer og nærmere typer kontrollerne 851 00:46:14,550 --> 00:46:17,330 at vi bygger i robotikk. 852 00:46:17,330 --> 00:46:21,050 >> I robotikk, må vi anta at vi har begrenset informasjon. 853 00:46:21,050 --> 00:46:23,070 Vi har sensorer som fortelle oss om verden. 854 00:46:23,070 --> 00:46:25,860 Vi har en alltid skiftende, dynamisk miljø. 855 00:46:25,860 --> 00:46:30,440 Vi har en verden der plassen er kontinuerlig, i stedet for diskret. 856 00:46:30,440 --> 00:46:36,260 Og våre handlinger, når vi prøver dem, har en sjanse for å mislykkes. 857 00:46:36,260 --> 00:46:40,960 Og faktisk, moderne spill kontrollere for din Halo motstander, 858 00:46:40,960 --> 00:46:48,690 eller for de NPCer i Skyrim, i utgangspunktet kjøre små robotikk arkitekturer. 859 00:46:48,690 --> 00:46:50,380 >> De fornemme verden. 860 00:46:50,380 --> 00:46:52,910 De bygger en modell av verden. 861 00:46:52,910 --> 00:46:57,950 De Beregn basert på et sett av mål som de ønsker å oppnå. 862 00:46:57,950 --> 00:47:03,110 De planlegger tiltak basert på hva de vet. 863 00:47:03,110 --> 00:47:07,940 Og de er nøyaktig de samme typer systemer som vi bygger i robotikk. 864 00:47:07,940 --> 00:47:11,420 Så disse arkitekturer, til bringe dette tilbake sammen, 865 00:47:11,420 --> 00:47:14,500 er ofte ganske like. 866 00:47:14,500 --> 00:47:16,340 >> Så la oss se om vi kan se det. 867 00:47:16,340 --> 00:47:19,210 La oss gå tilbake til vår tic-tac-toe eksempel. 868 00:47:19,210 --> 00:47:22,690 Og jeg kommer til å be om et par min postdoktorer til å komme opp og hjelpe meg. 869 00:47:22,690 --> 00:47:26,970 Så Chen Ming, og Alessandro, og Olivier, hvis dere skulle komme opp. 870 00:47:26,970 --> 00:47:32,080 871 00:47:32,080 --> 00:47:35,440 Og jeg kommer til å trenge et par frivillige 872 00:47:35,440 --> 00:47:37,590 >> OK, så jeg en hånd opp rett der i midten. 873 00:47:37,590 --> 00:47:39,965 La meg ta ett, noen videre i ryggen kanskje. 874 00:47:39,965 --> 00:47:40,881 Greit, over der. 875 00:47:40,881 --> 00:47:41,490 Kom opp. 876 00:47:41,490 --> 00:47:44,190 877 00:47:44,190 --> 00:47:45,335 Greit. 878 00:47:45,335 --> 00:47:49,490 Så la oss ta det dekselet ned. 879 00:47:49,490 --> 00:48:03,700 Og hvis dere skulle komme rett tilbake rundt her for meg, fantastisk. 880 00:48:03,700 --> 00:48:06,580 >> Så dette er en robot som heter Baxter. 881 00:48:06,580 --> 00:48:10,880 Og Baxter er en robot som er en kommersiell plattform, utformet 882 00:48:10,880 --> 00:48:13,030 av et selskap kalt Rethink. 883 00:48:13,030 --> 00:48:16,580 Og denne roboten er utformet for småskala produksjon. 884 00:48:16,580 --> 00:48:19,265 Men i dag skal vi bruke den til å spille tic-tac-toe. 885 00:48:19,265 --> 00:48:21,930 886 00:48:21,930 --> 00:48:27,150 Nå er denne roboten også noe det er relativt unik. 887 00:48:27,150 --> 00:48:32,950 Fordi hvis jeg ble stående overalt nær en standard fabrikk automasjon 888 00:48:32,950 --> 00:48:39,580 system, vil jeg være i svært alvorlig fare for å bli skadet. 889 00:48:39,580 --> 00:48:45,600 >> Baxter, men er utformet for å være relativt trygt å samhandle med. 890 00:48:45,600 --> 00:48:48,680 Og så jeg kan presse på denne roboten. 891 00:48:48,680 --> 00:48:52,350 Og du kan se det er en liten bit fleksibel når den beveger seg rundt. 892 00:48:52,350 --> 00:48:57,250 Og jeg kan flytte den hvor jeg ønsker at det skal gå. 893 00:48:57,250 --> 00:49:03,410 Nå i en normal robotsystem, vi ville ha et sett av ledd her 894 00:49:03,410 --> 00:49:07,970 som ville være direkte svarer på posisjonskommandoer. 895 00:49:07,970 --> 00:49:13,180 Og de ville ikke nødvendigvis bryr seg hvis de var i bevegelse gjennom friluft, 896 00:49:13,180 --> 00:49:15,555 eller om de var i bevegelse gjennom min brystkasse. 897 00:49:15,555 --> 00:49:18,410 898 00:49:18,410 --> 00:49:19,120 >> OK. 899 00:49:19,120 --> 00:49:22,090 Og vanligvis, hvis du var her med en industriell system, 900 00:49:22,090 --> 00:49:23,400 du vil gå langt nær den. 901 00:49:23,400 --> 00:49:26,280 Det ville være gul sikkerhet tape hele veien rundt. 902 00:49:26,280 --> 00:49:28,310 Dette systemet har en litt annen utforming 903 00:49:28,310 --> 00:49:32,130 å være vennligere og lettere for folk å samhandle med, 904 00:49:32,130 --> 00:49:36,380 ved at det i hver skjøt, er det en fjær. 905 00:49:36,380 --> 00:49:39,110 Og i stedet for å kontrollere nøyaktig posisjon, 906 00:49:39,110 --> 00:49:43,110 Vi kontrollerer en viss mengde dreiemoment, en viss mengde kraft, 907 00:49:43,110 --> 00:49:45,874 at vi ønsker å være på den våren. 908 00:49:45,874 --> 00:49:47,790 Greit, så la meg ta våre frivillige her. 909 00:49:47,790 --> 00:49:48,540 Hei, hva heter du? 910 00:49:48,540 --> 00:49:49,010 >> PUBLIKUM: Louis. 911 00:49:49,010 --> 00:49:49,635 >> SPEAKER: Louis. 912 00:49:49,635 --> 00:49:50,490 Hyggelig å se deg. 913 00:49:50,490 --> 00:49:50,990 Og? 914 00:49:50,990 --> 00:49:51,610 >> PUBLIKUM: David. 915 00:49:51,610 --> 00:49:51,960 >> SPEAKER: David. 916 00:49:51,960 --> 00:49:52,550 Hyggelig å møte deg. 917 00:49:52,550 --> 00:49:54,508 Hvis dere vil vente her for en andre, 918 00:49:54,508 --> 00:49:56,420 Jeg kommer til å gi deg en sjanse til å gjøre dette. 919 00:49:56,420 --> 00:50:00,610 Så dette robot, hvis du kommer opp og hvis du trykker forsiktig på det, 920 00:50:00,610 --> 00:50:03,780 du kommer til å se at den beveger seg litt. 921 00:50:03,780 --> 00:50:06,349 Og hvis du ta det riktig her på håndleddet bare 922 00:50:06,349 --> 00:50:09,390 over hvor disse knappene er, det ser ut som du bør ta tak i knapper, 923 00:50:09,390 --> 00:50:13,100 men grip rett ovenfor den i stedet, vil du kunne veldig forsiktig manipulere det 924 00:50:13,100 --> 00:50:14,545 gjennom rommet. 925 00:50:14,545 --> 00:50:15,920 Louis, ønsker du å gi det et forsøk? 926 00:50:15,920 --> 00:50:19,465 Så gi det litt presse til å begynne med. 927 00:50:19,465 --> 00:50:23,190 Og så hvis du putter fingrene akkurat der og holde på til det, 928 00:50:23,190 --> 00:50:24,807 fordi det vil flytte for deg da. 929 00:50:24,807 --> 00:50:27,824 930 00:50:27,824 --> 00:50:29,365 Greit, du ønsker å gi det et forsøk? 931 00:50:29,365 --> 00:50:29,980 Kom opp. 932 00:50:29,980 --> 00:50:32,300 Så gi det bare en svak skyve det å starte. 933 00:50:32,300 --> 00:50:33,820 Du kan føle hvordan det er. 934 00:50:33,820 --> 00:50:40,060 Og så hvis du ta det der, vil du være i stand til å manøvrere rundt. 935 00:50:40,060 --> 00:50:41,280 >> OK. 936 00:50:41,280 --> 00:50:47,360 Så typisk, denne typen en robot ville brukes for småskala produksjon. 937 00:50:47,360 --> 00:50:50,980 Og jeg kommer til å flytte denne armen like ned ut av veien litt her. 938 00:50:50,980 --> 00:50:55,750 Men i dag, kommer vi til å bruke samme tic-tac-toe spille system 939 00:50:55,750 --> 00:50:59,520 basert på minimax at vi bygget tidligere. 940 00:50:59,520 --> 00:51:00,549 OK? 941 00:51:00,549 --> 00:51:02,340 Så, dere er hver kommer til å spille et spill. 942 00:51:02,340 --> 00:51:04,210 Louis, du kommer til å være først. 943 00:51:04,210 --> 00:51:05,920 La meg bare holde opp her for et sekund. 944 00:51:05,920 --> 00:51:10,949 Jeg kommer til å ha deg stå rett her, så alle kan se deg. 945 00:51:10,949 --> 00:51:11,990 Skal dere sette opp her? 946 00:51:11,990 --> 00:51:13,120 >> ROBOT: Velkommen. 947 00:51:13,120 --> 00:51:15,910 La oss spille tic-tac-toe. 948 00:51:15,910 --> 00:51:20,860 Ikke ta tak token før Jeg sier at det er din tur. 949 00:51:20,860 --> 00:51:22,050 Jeg starter spillet. 950 00:51:22,050 --> 00:51:27,900 951 00:51:27,900 --> 00:51:28,750 Det er min tur. 952 00:51:28,750 --> 00:51:47,002 953 00:51:47,002 --> 00:51:50,210 SPEAKER: Nå, hvis du kunne ta en av brikkene dine og gå videre og plassere den. 954 00:51:50,210 --> 00:51:51,446 ROBOT: Det er din tur. 955 00:51:51,446 --> 00:51:53,430 [LATTER] 956 00:51:53,430 --> 00:51:54,836 Det er min tur. 957 00:51:54,836 --> 00:51:56,820 [LATTER] 958 00:51:56,820 --> 00:52:12,196 959 00:52:12,196 --> 00:52:15,680 [LATTER] 960 00:52:15,680 --> 00:52:16,570 Det er din tur. 961 00:52:16,570 --> 00:52:21,397 962 00:52:21,397 --> 00:52:23,688 SPEAKER: Den menneskelige rase er regner med deg her, Louis. 963 00:52:23,688 --> 00:52:27,440 964 00:52:27,440 --> 00:52:28,350 >> ROBOT: Det er min tur. 965 00:52:28,350 --> 00:52:44,810 966 00:52:44,810 --> 00:52:47,015 >> SPEAKER: Så Baxter vellykket blokkert her. 967 00:52:47,015 --> 00:52:49,670 968 00:52:49,670 --> 00:52:52,480 >> ROBOT: Det er din tur. 969 00:52:52,480 --> 00:52:53,360 Det er min tur. 970 00:52:53,360 --> 00:53:14,730 971 00:53:14,730 --> 00:53:16,810 Det er din tur. 972 00:53:16,810 --> 00:53:17,760 Det er min tur. 973 00:53:17,760 --> 00:53:21,330 974 00:53:21,330 --> 00:53:23,830 SPEAKER: Og vi skal la Baxter slutt ut sin siste trekk her. 975 00:53:23,830 --> 00:53:36,622 976 00:53:36,622 --> 00:53:39,090 >> [LATTER] 977 00:53:39,090 --> 00:53:40,480 >> ROBOT: Det er uavgjort. 978 00:53:40,480 --> 00:53:42,030 Jeg vil vinne neste gang. 979 00:53:42,030 --> 00:53:43,365 >> [LATTER] 980 00:53:43,365 --> 00:53:45,210 >> SPEAKER: Greit, Tusen takk, Louis. 981 00:53:45,210 --> 00:53:46,094 Takk. 982 00:53:46,094 --> 00:53:46,980 Du kan gå på denne måten. 983 00:53:46,980 --> 00:53:49,759 >> ROBOT: Jeg starter spillet. 984 00:53:49,759 --> 00:53:51,800 SPEAKER: Så la meg forklare til deg en mer lite 985 00:53:51,800 --> 00:53:55,410 litt før vi får vår omkamp her. 986 00:53:55,410 --> 00:53:57,200 Hva skjer? 987 00:53:57,200 --> 00:53:59,430 Så roboten har et kamera opp toppen her. 988 00:53:59,430 --> 00:54:01,330 Og det ser ned på brettet. 989 00:54:01,330 --> 00:54:04,470 Og det er å se hvorvidt det har en rød O eller en blå 990 00:54:04,470 --> 00:54:10,450 og hvit X. Som de blir plassert på bord, det er i utgangspunktet den samme inngang 991 00:54:10,450 --> 00:54:13,890 at vi ville være å lese i fra vår datastruktur fra vår skjerm. 992 00:54:13,890 --> 00:54:17,290 Det kjører det samme minimax algoritme for å være 993 00:54:17,290 --> 00:54:21,010 i stand til å finne hvor du skal plassere et godt tegn. 994 00:54:21,010 --> 00:54:24,820 >> Og så gir vi en kommando om hvor vi ønsker en token skal plasseres. 995 00:54:24,820 --> 00:54:26,120 Armen går ut. 996 00:54:26,120 --> 00:54:31,750 Det er ved hjelp av en vakuumgriper til å søke noen sug til at tre stykke, 997 00:54:31,750 --> 00:54:35,240 plukke den opp, flytte den til høyre spot, og deretter slippe suge 998 00:54:35,240 --> 00:54:36,950 og slipper det. 999 00:54:36,950 --> 00:54:38,990 Greit, vi skal for å gi den en mer shot 1000 00:54:38,990 --> 00:54:40,930 med en litt smartere spiller her. 1001 00:54:40,930 --> 00:54:42,290 Er du klar? 1002 00:54:42,290 --> 00:54:46,150 Greit, hvis du vil stå rett opp her og gi a-- slå ut på denne måten 1003 00:54:46,150 --> 00:54:47,955 så du kan se alle. 1004 00:54:47,955 --> 00:54:48,830 Og så [uhørbart]. 1005 00:54:48,830 --> 00:54:49,330 >> ROBOT: Det er min tur. 1006 00:54:49,330 --> 00:54:50,455 >> SPEAKER: Baxter starter. 1007 00:54:50,455 --> 00:55:10,750 1008 00:55:10,750 --> 00:55:11,730 Det er din tur. 1009 00:55:11,730 --> 00:55:16,490 1010 00:55:16,490 --> 00:55:17,520 Det er min tur. 1011 00:55:17,520 --> 00:55:38,740 1012 00:55:38,740 --> 00:55:39,690 Det er din tur. 1013 00:55:39,690 --> 00:55:46,330 1014 00:55:46,330 --> 00:55:47,165 Det er min tur. 1015 00:55:47,165 --> 00:56:01,252 1016 00:56:01,252 --> 00:56:06,192 >> [LATTER] 1017 00:56:06,192 --> 00:56:08,542 >> SPEAKER: [hvisken] Just la ham gå videre og vinne. 1018 00:56:08,542 --> 00:56:09,500 ROBOT: Det er din tur. 1019 00:56:09,500 --> 00:56:15,099 1020 00:56:15,099 --> 00:56:15,890 SPEAKER: Det er OK. 1021 00:56:15,890 --> 00:56:20,390 1022 00:56:20,390 --> 00:56:21,360 >> ROBOT: Det er min tur. 1023 00:56:21,360 --> 00:56:24,825 1024 00:56:24,825 --> 00:56:26,805 >> [LATTER] 1025 00:56:26,805 --> 00:56:42,650 1026 00:56:42,650 --> 00:56:43,510 >> Jeg vinner. 1027 00:56:43,510 --> 00:56:45,620 >> [LATTER] 1028 00:56:45,620 --> 00:56:46,595 >> Jeg starter spillet. 1029 00:56:46,595 --> 00:56:48,261 >> SPEAKER: Ok, takk. 1030 00:56:48,261 --> 00:56:50,180 1031 00:56:50,180 --> 00:56:55,590 Greit, jeg tror vi har fått tid til enda en utmerket tic-tac-toe-spiller, 1032 00:56:55,590 --> 00:57:00,490 noen som kan sette denne tingen å matche, som vet hva de gjør. 1033 00:57:00,490 --> 00:57:03,010 >> [LATTER] 1034 00:57:03,010 --> 00:57:05,560 >> Hvem kommer til å bli vår mester her? 1035 00:57:05,560 --> 00:57:08,110 Greit, venner frivillig deg. 1036 00:57:08,110 --> 00:57:11,190 Det er bra nok for meg. 1037 00:57:11,190 --> 00:57:12,194 Si meg navnet ditt igjen. 1038 00:57:12,194 --> 00:57:12,860 PUBLIKUM: Tamir. 1039 00:57:12,860 --> 00:57:14,193 SPEAKER: Tamir, hyggelig å se deg. 1040 00:57:14,193 --> 00:57:19,270 Greit, igjen, vi kommer til å sette deg rett opp her slik at alle kan se deg. 1041 00:57:19,270 --> 00:57:22,070 Du er vår representant i denne kampen nå. 1042 00:57:22,070 --> 00:57:24,540 Baxter er en og oh og oh. 1043 00:57:24,540 --> 00:57:26,300 Eller sorry, én oh og en. 1044 00:57:26,300 --> 00:57:27,490 Og det er opp til deg her. 1045 00:57:27,490 --> 00:57:29,340 Baxter vil komme til å flytte først, though. 1046 00:57:29,340 --> 00:57:30,435 Så. 1047 00:57:30,435 --> 00:57:31,310 ROBOT: Det er min tur. 1048 00:57:31,310 --> 00:57:45,226 1049 00:57:45,226 --> 00:57:48,208 >> [LATTER] 1050 00:57:48,208 --> 00:57:52,720 1051 00:57:52,720 --> 00:57:55,780 >> Det er din tur. 1052 00:57:55,780 --> 00:57:56,845 Det er min tur. 1053 00:57:56,845 --> 00:58:18,130 1054 00:58:18,130 --> 00:58:18,965 Det er din tur. 1055 00:58:18,965 --> 00:58:28,751 1056 00:58:28,751 --> 00:58:30,248 Det er min tur. 1057 00:58:30,248 --> 00:58:51,210 1058 00:58:51,210 --> 00:58:52,160 Det er din tur. 1059 00:58:52,160 --> 00:59:00,854 1060 00:59:00,854 --> 00:59:03,365 >> [LATTER] 1061 00:59:03,365 --> 00:59:04,240 ROBOT: Det er min tur. 1062 00:59:04,240 --> 00:59:06,930 SPEAKER: Det er mye vanskeligere når du står opp her, folkens. 1063 00:59:06,930 --> 00:59:19,400 1064 00:59:19,400 --> 00:59:21,840 [LATTER] 1065 00:59:21,840 --> 00:59:26,730 1066 00:59:26,730 --> 00:59:29,054 ROBOT: Du mennesker er så lett å slå. 1067 00:59:29,054 --> 00:59:30,803 [Latter og applaus] 1068 00:59:30,803 --> 00:59:31,886 SPEAKER: Takk veldig mye. 1069 00:59:31,886 --> 00:59:34,692 ROBOT: Jeg vinner. 1070 00:59:34,692 --> 00:59:35,400 Jeg starter spillet. 1071 00:59:35,400 --> 00:59:39,500 >> SPEAKER: Greit, så takk veldig mye til Olivier, og Alessandro, 1072 00:59:39,500 --> 00:59:41,616 og til Chen Ming. 1073 00:59:41,616 --> 00:59:45,600 >> [BIFALL] 1074 00:59:45,600 --> 00:59:47,040 >> Jeg ønsker å gjøre en siste punkt. 1075 00:59:47,040 --> 00:59:51,630 Så Baxter helt slutt der, jukset. 1076 00:59:51,630 --> 00:59:54,160 1077 00:59:54,160 --> 00:59:56,310 Og det var uventet. 1078 00:59:56,310 --> 01:00:00,440 En av de fantastiske ting om AI er at vi 1079 01:00:00,440 --> 01:00:05,070 utføre arbeid i AI slik at vi kan bygge veldig interessant og intelligent 1080 01:00:05,070 --> 01:00:06,930 enheter. 1081 01:00:06,930 --> 01:00:10,130 Men vi gjør også arbeid i AI fordi det forteller oss noe 1082 01:00:10,130 --> 01:00:13,940 om hvordan mennesker er intelligente. 1083 01:00:13,940 --> 01:00:17,280 >> En av favoritt studier fra min lab er 1084 01:00:17,280 --> 01:00:23,660 å se på hva som skjer når maskiner uventet jukse. 1085 01:00:23,660 --> 01:00:27,070 Vi gjorde dette opprinnelig ikke med Baxter spille tic-tac-toe, 1086 01:00:27,070 --> 01:00:30,340 men med en mindre robot som heter Nao, som spilte Stein, Saks, Papir. 1087 01:00:30,340 --> 01:00:33,010 1088 01:00:33,010 --> 01:00:35,800 Og noen ganger etter spille masse, masse 1089 01:00:35,800 --> 01:00:41,580 kjedelig Stein, Saks, Papir spill, roboten ville kaste en gest, 1090 01:00:41,580 --> 01:00:48,616 taper, og så plutselig endre sin gest og si, jeg vinner. 1091 01:00:48,616 --> 01:00:50,480 >> [LATTER] 1092 01:00:50,480 --> 01:00:56,090 >> Nå, noen ganger vil vi også ha robot, akkurat som en kontroll, kaste en gest, 1093 01:00:56,090 --> 01:01:01,270 vinne, og endre sin gest å tape, kaste kampen, 1094 01:01:01,270 --> 01:01:04,070 jukse for å miste. 1095 01:01:04,070 --> 01:01:07,540 Og det er ikke på langt nær så overbevisende. 1096 01:01:07,540 --> 01:01:09,890 Roboten som jukser for å vinne mennesker 1097 01:01:09,890 --> 01:01:14,660 svare på som om den er ut for å få dem, som det 1098 01:01:14,660 --> 01:01:17,690 er aktivt søker deres ødeleggelse. 1099 01:01:17,690 --> 01:01:19,210 >> [LATTER] 1100 01:01:19,210 --> 01:01:20,990 >> Det blir en agent. 1101 01:01:20,990 --> 01:01:21,840 Det er som en person. 1102 01:01:21,840 --> 01:01:23,970 Det har tro og intensjon. 1103 01:01:23,970 --> 01:01:27,470 Og det er ikke god intensjon. 1104 01:01:27,470 --> 01:01:33,790 Og roboten som kaster Spillet er bare feil. 1105 01:01:33,790 --> 01:01:36,990 Det er bare en ødelagt enhet. 1106 01:01:36,990 --> 01:01:41,405 La meg vise deg et par eksempler av at fra noen av våre deltakere. 1107 01:01:41,405 --> 01:01:43,990 1108 01:01:43,990 --> 01:01:45,600 Så her er juks for å miste. 1109 01:01:45,600 --> 01:01:46,266 >> [VIDEO PLAYBACK] 1110 01:01:46,266 --> 01:01:47,010 - [Uhørbart] vinne. 1111 01:01:47,010 --> 01:01:49,550 La oss leke. 1112 01:01:49,550 --> 01:01:50,538 >> -Wait, Hva? 1113 01:01:50,538 --> 01:01:54,490 1114 01:01:54,490 --> 01:01:55,352 >> - [Uhørbart] vinne. 1115 01:01:55,352 --> 01:01:58,280 La oss leke. 1116 01:01:58,280 --> 01:01:59,400 >> [Uhørbart] vinne. 1117 01:01:59,400 --> 01:02:02,290 La oss leke. 1118 01:02:02,290 --> 01:02:05,490 >> SPEAKER: Og her er juks å vinne. 1119 01:02:05,490 --> 01:02:06,438 >> -Ja, Vinner jeg. 1120 01:02:06,438 --> 01:02:07,394 La oss leke. 1121 01:02:07,394 --> 01:02:08,828 >> -Du Kan ikke gjøre det. 1122 01:02:08,828 --> 01:02:10,740 >> [LATTER] 1123 01:02:10,740 --> 01:02:12,174 1124 01:02:12,174 --> 01:02:13,979 >> -Ja, Vinner jeg. 1125 01:02:13,979 --> 01:02:14,520 -Du Jukset. 1126 01:02:14,520 --> 01:02:17,990 1127 01:02:17,990 --> 01:02:20,010 Du snytt nå. 1128 01:02:20,010 --> 01:02:21,140 >> -Ja, Vinner jeg. 1129 01:02:21,140 --> 01:02:22,940 >> -Hei, Du juksemaker. 1130 01:02:22,940 --> 01:02:26,670 Du jukser, super cheat. 1131 01:02:26,670 --> 01:02:27,650 >> [END PLAYBACK] 1132 01:02:27,650 --> 01:02:31,130 >> SPEAKER: Disse annerledes reaksjoner raskt 1133 01:02:31,130 --> 01:02:34,890 endre vår oppfatning av enheten. 1134 01:02:34,890 --> 01:02:36,780 Betyr det at vi bevisst bygge 1135 01:02:36,780 --> 01:02:40,370 maskiner som jukser fordi det er den beste ingeniør at vi kan gjøre? 1136 01:02:40,370 --> 01:02:44,680 Nei, men det forteller oss noe veldig interessant om mennesker. 1137 01:02:44,680 --> 01:02:49,710 At ting som jukser du og stjeler din seier, det er 1138 01:02:49,710 --> 01:02:53,660 noe som er i live, det er animere, som er ute etter deg. 1139 01:02:53,660 --> 01:02:54,680 Den har mentale tilstand. 1140 01:02:54,680 --> 01:02:55,400 Den har troen. 1141 01:02:55,400 --> 01:02:57,170 Den har intensjon. 1142 01:02:57,170 --> 01:03:01,540 >> At ting som hender i spillet for deg, er det ikke. 1143 01:03:01,540 --> 01:03:04,670 Det er bare feil. 1144 01:03:04,670 --> 01:03:08,900 Dette er på mange måter hvorfor det er lett å kaste spill med barna. 1145 01:03:08,900 --> 01:03:12,050 Men hvis du prøver å lure dem og liksom kreve seier 1146 01:03:12,050 --> 01:03:15,200 når, du vet, bare for å forkorte spillet, vil de ta deg med en gang. 1147 01:03:15,200 --> 01:03:19,040 1148 01:03:19,040 --> 01:03:23,140 Slike effekter som vi ser kommer ut av AI, 1149 01:03:23,140 --> 01:03:26,490 de lærer oss mye om oss selv. 1150 01:03:26,490 --> 01:03:28,076 >> Greit, det er det for i dag. 1151 01:03:28,076 --> 01:03:30,450 Tusen takk til David og Harvard produksjonsteamet 1152 01:03:30,450 --> 01:03:32,350 for å komme ned. 1153 01:03:32,350 --> 01:03:33,820 >> [BIFALL] 1154 01:03:33,820 --> 01:03:36,760 1155 01:03:36,760 --> 01:03:41,840 >> Vi ser deg for quiz en, og deretter for en siste forelesning. 1156 01:03:41,840 --> 01:03:43,025 Ha en fin dag. 1157 01:03:43,025 --> 01:03:44,965 >> [BIFALL] 1158 01:03:44,965 --> 01:03:48,360 1159 01:03:48,360 --> 01:03:51,825 >> [MUSIC SPILLE] 1160 01:03:51,825 --> 01:03:54,950 DAVID J MALAN: Vel, vi trolig trenger å innføre noen form for kryptering, 1161 01:03:54,950 --> 01:03:55,450 høyre? 1162 01:03:55,450 --> 01:03:58,650 Fordi da hodene av disse HTTP-forespørsler blir 1163 01:03:58,650 --> 01:04:01,530 egge slik at alle prøver å snuse trafikken 1164 01:04:01,530 --> 01:04:03,400 vil faktisk ikke være i stand til å se dem. 1165 01:04:03,400 --> 01:04:05,254 Så hva er løsningen på dette problemet? 1166 01:04:05,254 --> 01:04:07,920 Vel, må vi faktisk introdusere kryptering inn i formelen, 1167 01:04:07,920 --> 01:04:11,010 slik at når den personen er overføring av data fra A til B, 1168 01:04:11,010 --> 01:04:12,390 vi kan sikkert send-- 1169 01:04:12,390 --> 01:04:14,590 >> [LATTER] 1170 01:04:14,590 --> 01:04:19,530 >> Informasjonen på en måte som Motstanderen kan ikke, faktisk ser det.