1 00:00:00,000 --> 00:00:01,924 >> [Muziek] 2 00:00:01,924 --> 00:00:10,600 3 00:00:10,600 --> 00:00:13,280 >> SPEAKER: Welkom terug, iedereen. 4 00:00:13,280 --> 00:00:15,440 Dit is CS50. 5 00:00:15,440 --> 00:00:21,040 En vandaag hebben we een heleboel interessante dingen om over te praten. 6 00:00:21,040 --> 00:00:25,500 Maar eerst moet ik eraan herinneren je van een paar administratieve dingen. 7 00:00:25,500 --> 00:00:30,160 Deze week is een quiz, woensdag of voor het deel van Yale 8 00:00:30,160 --> 00:00:32,940 op dinsdag en donderdag, op donderdag. 9 00:00:32,940 --> 00:00:38,170 Er zijn quiz beoordelingen vanavond aan de Yale, 5:30-07:00. 10 00:00:38,170 --> 00:00:40,030 Op Harvard, namen ze een gisteren. 11 00:00:40,030 --> 00:00:43,000 En iedereen kan dat online te bekijken. 12 00:00:43,000 --> 00:00:49,406 >> Ook deze week of begin volgende week, hebben we onze laatste CS50 lezing. 13 00:00:49,406 --> 00:00:51,450 [Kreunt] Ik weet het. 14 00:00:51,450 --> 00:00:54,140 Het kwam zo snel. 15 00:00:54,140 --> 00:00:57,820 Yale studenten zal een live hebben lezing hier in de wet school 16 00:00:57,820 --> 00:00:59,920 auditorium op vrijdag. 17 00:00:59,920 --> 00:01:01,140 Er zal taart zijn. 18 00:01:01,140 --> 00:01:05,570 Harvard studenten moeten de laatste lezing in Sanders op maandag. 19 00:01:05,570 --> 00:01:08,050 Er zal ook taart. 20 00:01:08,050 --> 00:01:14,000 >> Bovendien is deze week op vrijdag, voor de van jullie die komen naar New Haven, 21 00:01:14,000 --> 00:01:15,740 wij hebben de CS50 Expo. 22 00:01:15,740 --> 00:01:18,850 We hebben meer dan 30 verschillende groepen geregistreerd 23 00:01:18,850 --> 00:01:22,530 om te laten zien alles uit autonome zeilboten, 24 00:01:22,530 --> 00:01:27,170 om systemen die te herkennen digitale portretten tot computer 25 00:01:27,170 --> 00:01:32,100 muziek en computer geproduceerde muziek. 26 00:01:32,100 --> 00:01:33,610 Dus bij ons. 27 00:01:33,610 --> 00:01:36,460 Ik denk dat het gaat om een ​​geweldige tijd te zijn. 28 00:01:36,460 --> 00:01:40,320 >> Vandaag de dag, hoewel, krijgen we blijven praten over AI, 29 00:01:40,320 --> 00:01:43,150 over kunstmatige intelligentie. 30 00:01:43,150 --> 00:01:46,070 En een van de dingen die we gaan vandaag te krijgen 31 00:01:46,070 --> 00:01:51,750 is het idee van hoe AI gebruiken om problemen op te lossen. 32 00:01:51,750 --> 00:01:54,690 Nu, zoals altijd, laten we beginnen met iets simpels. 33 00:01:54,690 --> 00:01:57,120 En we gaan beginnen met een simpel idee. 34 00:01:57,120 --> 00:01:59,920 En dat is met behulp van zoeken. 35 00:01:59,920 --> 00:02:06,990 >> Dus stel je voor een minuut dat ik een taak die ik nodig om te presteren. 36 00:02:06,990 --> 00:02:11,970 En ik zou graag willen dat de taak hebben geautomatiseerd door een aantal software-agent. 37 00:02:11,970 --> 00:02:17,100 Stel je voor dat ik probeer om een ​​reeks boeken van vluchten van, laten we zeggen, Boston 38 00:02:17,100 --> 00:02:20,040 naar San Francisco. 39 00:02:20,040 --> 00:02:24,230 Ik kon gaan door en ik kon gebruiken een van de prachtige online zoeken 40 00:02:24,230 --> 00:02:28,790 gereedschappen, dat gaat doen in principe hetzelfde proces dat we 41 00:02:28,790 --> 00:02:30,030 gaan lopen door vandaag. 42 00:02:30,030 --> 00:02:34,100 Maar als je niet hebben dat tool, wat zou u doen? 43 00:02:34,100 --> 00:02:37,570 >> Nou, je kon kijken en zien en te zeggen, ik ben in Boston. 44 00:02:37,570 --> 00:02:41,520 Welke vluchten zijn beschikbaar voor mij? 45 00:02:41,520 --> 00:02:44,390 Nu, misschien heb ik drie mogelijke vluchten vanuit Boston 46 00:02:44,390 --> 00:02:47,180 dat zal de tijd fit wanneer ik moet vertrekken. 47 00:02:47,180 --> 00:02:48,830 Ik kon vliegen naar Chicago. 48 00:02:48,830 --> 00:02:50,130 Of ik kon vliegen naar Miami. 49 00:02:50,130 --> 00:02:53,340 Of ik kon vliegen naar New York. 50 00:02:53,340 --> 00:02:56,980 Ik kon dan kijken van elkaar een van die bestemming steden 51 00:02:56,980 --> 00:03:00,650 en na te denken over welke locaties Ik zou kunnen bereiken 52 00:03:00,650 --> 00:03:03,020 uit elk van deze afzonderlijke steden. 53 00:03:03,020 --> 00:03:07,390 >> Dus misschien uit Chicago, kan ik een rechtstreekse vlucht naar San Francisco. 54 00:03:07,390 --> 00:03:09,550 Dat is uitstekend. 55 00:03:09,550 --> 00:03:12,360 Of ik kon een vlucht naar Denver te krijgen. 56 00:03:12,360 --> 00:03:16,970 Nu, misschien is dat de vlucht naar San Francisco is de perfecte oplossing voor mij, 57 00:03:16,970 --> 00:03:19,530 maar misschien ook niet. 58 00:03:19,530 --> 00:03:22,180 Misschien ben ik op zoek naar iets dat is een beetje goedkoper 59 00:03:22,180 --> 00:03:24,920 of een beetje beter voor mijn schema. 60 00:03:24,920 --> 00:03:29,197 En dus ik kon kijken naar wat andere mogelijkheden kan die er zijn. 61 00:03:29,197 --> 00:03:30,280 Dus ik kon kijken naar Denver. 62 00:03:30,280 --> 00:03:33,870 En uit Denver, nou ja, misschien Ik kan een vlucht naar Austin te krijgen. 63 00:03:33,870 --> 00:03:37,080 En uit Austin, misschien kan ik een krijgen vlucht naar Phoenix, en van Phoenix 64 00:03:37,080 --> 00:03:40,190 naar San Francisco. 65 00:03:40,190 --> 00:03:42,730 Nu, ik ben nog niet klaar. 66 00:03:42,730 --> 00:03:45,640 Want misschien is er een rechtstreekse vlucht vanuit New York 67 00:03:45,640 --> 00:03:47,850 San Francisco, dat is perfect voor mij. 68 00:03:47,850 --> 00:03:53,354 Of misschien is er een vlucht van Miami door middel van Denver, dat is een stuk goedkoper. 69 00:03:53,354 --> 00:03:54,270 Dus ik heb nog te gaan. 70 00:03:54,270 --> 00:03:58,200 En ik heb nog steeds te kijken naar al die steden die ik nog niet hebben onderzocht. 71 00:03:58,200 --> 00:04:04,220 Ik moet uitputtend te controleren alle de mogelijkheden die ik zou kunnen hebben. 72 00:04:04,220 --> 00:04:09,610 >> Dus van New York, misschien kan ik een krijgen vlucht naar Nashville, en vanuit Nashville 73 00:04:09,610 --> 00:04:10,336 naar Austin. 74 00:04:10,336 --> 00:04:11,460 En dan weet ik waar ik ben. 75 00:04:11,460 --> 00:04:14,252 En dan weet ik uit Austin, ik kan vliegen naar Phoenix, en van Phoenix 76 00:04:14,252 --> 00:04:14,960 naar San Francisco. 77 00:04:14,960 --> 00:04:18,240 78 00:04:18,240 --> 00:04:22,830 Als ik vliegen eerst naar Miami, hoewel, misschien kan ik een vlucht van Miami krijgen 79 00:04:22,830 --> 00:04:25,080 naar Nashville, of van Miami naar Austin. 80 00:04:25,080 --> 00:04:27,950 81 00:04:27,950 --> 00:04:30,860 >> En nu heb ik alles geprobeerd de mogelijkheden. 82 00:04:30,860 --> 00:04:36,310 Ik heb deze grafiek opgebouwd dat laat me alle mogelijke routes 83 00:04:36,310 --> 00:04:37,790 dat ik zou kunnen nemen. 84 00:04:37,790 --> 00:04:40,510 85 00:04:40,510 --> 00:04:43,640 Toen we deze vertegenwoordigen soorten problemen, 86 00:04:43,640 --> 00:04:47,870 we zijn niet van plan om te vertegenwoordigen ze expliciet als deze grafiek, 87 00:04:47,870 --> 00:04:51,590 want dat grafiek vertegenwoordigt niet de geschiedenis van waar we zijn gegaan. 88 00:04:51,590 --> 00:04:55,260 Wetende dat ik vloog uit Phoenix naar San Francisco 89 00:04:55,260 --> 00:05:01,690 mij niet vertellen of ik via kwam Nashville, of via Denver, of via Miami. 90 00:05:01,690 --> 00:05:06,430 >> Dus wat ik zal doen in plaats is Ik zal dit hetzelfde probleem te nemen, 91 00:05:06,430 --> 00:05:09,140 en ik zal het vertegenwoordigen als een boom. 92 00:05:09,140 --> 00:05:14,300 En aan de wortel van de boom, in het top, ik zal de plaats die ik begon te zetten, 93 00:05:14,300 --> 00:05:16,590 Boston. 94 00:05:16,590 --> 00:05:19,310 En uit Boston, ik kijk naar alle mogelijke locaties 95 00:05:19,310 --> 00:05:20,380 dat ik kan reizen. 96 00:05:20,380 --> 00:05:25,480 Nou, in dit geval, had ik drie, Chicago, New York en Miami. 97 00:05:25,480 --> 00:05:29,850 En dan zal ik elk van verkennen deze kinderen in de boom. 98 00:05:29,850 --> 00:05:32,690 >> Uit Chicago, zag ik dat ik had twee vluchten. 99 00:05:32,690 --> 00:05:35,940 Ik kon rechtstreeks vliegen naar San Francisco of Denver. 100 00:05:35,940 --> 00:05:37,740 Nu San Francisco, dat is mijn doel. 101 00:05:37,740 --> 00:05:39,790 Dat is mijn bestemming. 102 00:05:39,790 --> 00:05:42,220 Dat gaat om een ​​blad van deze boom zijn. 103 00:05:42,220 --> 00:05:45,340 Dat wil zeggen, ik ga nooit om te gaan ergens na San Francisco. 104 00:05:45,340 --> 00:05:47,850 105 00:05:47,850 --> 00:05:50,340 Van Denver, hoewel, Ik kan vliegen van Denver 106 00:05:50,340 --> 00:05:54,220 naar Austin, van Austin naar Phoenix, en van Phoenix naar San Francisco. 107 00:05:54,220 --> 00:05:56,050 En nu weer, ik heb een blad bereikt. 108 00:05:56,050 --> 00:05:59,470 109 00:05:59,470 --> 00:06:03,980 >> Ik kan dan terug naar de volgende stad die ik nog niet volledig onderzocht. 110 00:06:03,980 --> 00:06:07,440 Dat zou New York, gaan terug naar de top van mijn boom, 111 00:06:07,440 --> 00:06:09,160 kom af naar New York. 112 00:06:09,160 --> 00:06:12,700 Van New York, kan ik vliegen naar Nashville, van Nashville naar Austin, 113 00:06:12,700 --> 00:06:17,290 van Austin naar Phoenix, en van Phoenix naar San Francisco. 114 00:06:17,290 --> 00:06:20,170 En tenslotte, een stad waar ik heb nog niet gekeken, Miami. 115 00:06:20,170 --> 00:06:24,600 >> Nou, uit Miami ik zei dat ik had twee mogelijkheden, Nashville en Austin. 116 00:06:24,600 --> 00:06:28,810 Als ik vliegen naar Nashville, nou dan vlieg ik uit Nashville, naar Austin, naar Phoenix, 117 00:06:28,810 --> 00:06:29,640 naar San Francisco. 118 00:06:29,640 --> 00:06:33,600 Als ik vliegen naar Austin, vlieg ik Austin, Phoenix, San Francisco. 119 00:06:33,600 --> 00:06:36,340 En nu heb ik een boom. 120 00:06:36,340 --> 00:06:37,230 Het is een complete boom. 121 00:06:37,230 --> 00:06:41,890 Het is allemaal van de mogelijkheden en alle van de paden die ik kon nemen. 122 00:06:41,890 --> 00:06:44,310 Dat wil zeggen, als ik vanaf de wortel van de boom op de top 123 00:06:44,310 --> 00:06:47,860 en ik ga naar een van de laat, vertelt het me niet alleen 124 00:06:47,860 --> 00:06:50,480 waar ik ga belanden, San Francisco, 125 00:06:50,480 --> 00:06:53,670 maar het vertelt me ​​de route die Ik moet om er te komen. 126 00:06:53,670 --> 00:06:56,400 127 00:06:56,400 --> 00:06:59,690 >> Nu, welke van deze het beste? 128 00:06:59,690 --> 00:07:02,430 Nou, niets over deze nog probleem vertelt me 129 00:07:02,430 --> 00:07:04,710 die daarvan is de beste oplossing. 130 00:07:04,710 --> 00:07:09,270 Misschien heb ik de zorg het meest over hoeveel keer dat ik in de lucht, 131 00:07:09,270 --> 00:07:12,350 of de afstand die ik vlieg. 132 00:07:12,350 --> 00:07:16,410 In dat geval, Chicago San Francisco kan het kortste getal 133 00:07:16,410 --> 00:07:18,910 van mijlen in de lucht. 134 00:07:18,910 --> 00:07:20,860 >> Misschien heb ik de zorg over de kosten. 135 00:07:20,860 --> 00:07:23,680 En we weten allemaal directe vluchten zijn meestal duurder. 136 00:07:23,680 --> 00:07:26,610 Dus misschien als ik dit nemen soort achteruit route 137 00:07:26,610 --> 00:07:30,650 door middel van Miami, Nashville, Austin, Phoenix, misschien dan 138 00:07:30,650 --> 00:07:34,070 Ik krijg een lagere prijs. 139 00:07:34,070 --> 00:07:36,440 Maar ik kon optimaliseren op een criteria die ik zorg over. 140 00:07:36,440 --> 00:07:39,790 Wie is de beste in gekregen flight Wi-Fi, of die 141 00:07:39,790 --> 00:07:43,110 luchthavens hebben de beste voedsel beschikbaar. 142 00:07:43,110 --> 00:07:47,280 En elk van die macht geef me een andere oplossing 143 00:07:47,280 --> 00:07:49,215 dat zie ik als de beste. 144 00:07:49,215 --> 00:07:51,990 145 00:07:51,990 --> 00:07:54,400 >> Dit soort problemen, waar we heen gaan 146 00:07:54,400 --> 00:07:58,480 uit te bouwen deze boom van mogelijkheden, en dan 147 00:07:58,480 --> 00:08:02,100 kijken naar elk van die individuele paden, en te onderzoeken 148 00:08:02,100 --> 00:08:05,270 welke van die vervult een criterium voor ons, 149 00:08:05,270 --> 00:08:08,790 we gaan om te bellen die zoeken problemen. 150 00:08:08,790 --> 00:08:11,280 En we hebben veel algoritmen, waarvan sommige 151 00:08:11,280 --> 00:08:15,270 We hebben al gezien, om te gaan en verken die bomen. 152 00:08:15,270 --> 00:08:19,270 We kunnen het doen op de manier die ik net deed, een diepte-eerst zoeken, 153 00:08:19,270 --> 00:08:22,900 naar beneden zo ver als we kunnen totdat we raakte een blad, en dan terug te komen op, 154 00:08:22,900 --> 00:08:24,787 en gaan terug naar beneden. 155 00:08:24,787 --> 00:08:26,870 Of we kunnen doen wat genaamd breedte-eerst zoeken. 156 00:08:26,870 --> 00:08:29,675 We konden alles uit te breiden boven, en vervolgens 157 00:08:29,675 --> 00:08:31,550 alles één lijn onder die, en dan 158 00:08:31,550 --> 00:08:35,240 alles wat men onder die lijn. 159 00:08:35,240 --> 00:08:41,250 Die zoekbomen zijn fundamenteel voor AI. 160 00:08:41,250 --> 00:08:46,570 Maar ze hebben niet helemaal het juist de hele tijd. 161 00:08:46,570 --> 00:08:51,600 In feite, in veel gevallen dat we echt zorgen over, 162 00:08:51,600 --> 00:08:54,430 we willen een boom te bouwen, maar we doen niet echt 163 00:08:54,430 --> 00:08:57,140 krijgen om alle beslissingen te nemen. 164 00:08:57,140 --> 00:09:00,940 >> Deze situaties genoemd wederhoor zoeken, ook bekend 165 00:09:00,940 --> 00:09:05,390 hoe om het spel te spelen schrijven systemen en krijgt betaald voor het. 166 00:09:05,390 --> 00:09:07,940 Maar dit zijn de soorten van de systemen waar ik 167 00:09:07,940 --> 00:09:12,920 zou kunnen krijgen om te kiezen wanneer ik van Boston, welke stad ik ga naar de volgende. 168 00:09:12,920 --> 00:09:19,990 Maar na dat, iemand anders zou kunnen krijgen de beslissing over waar ik vliegen te maken. 169 00:09:19,990 --> 00:09:24,040 Dus om deze te bouwen soorten structuren, we zijn 170 00:09:24,040 --> 00:09:28,510 gaat te hebben om een ​​beetje te nemen andere benadering van het. 171 00:09:28,510 --> 00:09:31,060 We gaan niet in staat zijn om gewoon zoeken door middel van de boom 172 00:09:31,060 --> 00:09:35,000 meer, omdat we niet degene die in control 173 00:09:35,000 --> 00:09:38,180 van elk van deze beslissing punten. 174 00:09:38,180 --> 00:09:42,590 >> Dus laten we denken aan een eenvoudige spel als tic-tac-teen. 175 00:09:42,590 --> 00:09:46,730 Ik kon met een start- helemaal leeg bord. 176 00:09:46,730 --> 00:09:49,580 En in tic-tac-teen, X krijgt om eerst te spelen. 177 00:09:49,580 --> 00:09:53,890 En dus ik kon denken over alle mogelijke bewegingen die X kon maken. 178 00:09:53,890 --> 00:09:57,420 En als ik ben degene spelen de X, dat is geweldig. 179 00:09:57,420 --> 00:10:01,020 Ik heb negen mogelijke beweegt die ik kan maken. 180 00:10:01,020 --> 00:10:05,000 Ik kon een X in één zet van de negen posities. 181 00:10:05,000 --> 00:10:10,710 >> En dan van elk van deze, I kon voorstellen wat er daarna gebeurt. 182 00:10:10,710 --> 00:10:14,130 Welnu, in casu het andere speler zou krijgen om een ​​bocht te nemen. 183 00:10:14,130 --> 00:10:15,660 O zou krijgen om een ​​bocht te nemen. 184 00:10:15,660 --> 00:10:19,510 En uit elk van die, daar zou acht verschillende plaatsen 185 00:10:19,510 --> 00:10:22,980 O, dat konden hun markering. 186 00:10:22,980 --> 00:10:25,790 >> Laten we zeggen dat ik besloten dat ik was naar een X in het midden gezet. 187 00:10:25,790 --> 00:10:28,810 Dat lijkt altijd als een goede opening zet. 188 00:10:28,810 --> 00:10:34,870 Ik kon kijken onder dat, de acht mogelijke bewegingen die O maakt. 189 00:10:34,870 --> 00:10:37,320 Nu, als ik speel X, dat is geweldig. 190 00:10:37,320 --> 00:10:41,740 Ik krijg om welke ik kiezen naar de in het midden. 191 00:10:41,740 --> 00:10:45,000 Maar nu O krijgt om te kiezen. 192 00:10:45,000 --> 00:10:48,750 En ik heb geen controle over die beslissing. 193 00:10:48,750 --> 00:10:51,670 >> Maar uit elk van die mogelijk bestuursfuncties, 194 00:10:51,670 --> 00:10:54,020 Er is dan een ander reeks mogelijkheden. 195 00:10:54,020 --> 00:10:56,700 Als het gaat om zijn Mijn weer in te schakelen, zou ik 196 00:10:56,700 --> 00:11:01,500 op te halen en te zeggen, nou ja, Als O verhuist naar de, nou ja, 197 00:11:01,500 --> 00:11:06,110 de middelste vlek aan de linkerkant, dan Ik heb een set van mogelijkheden 198 00:11:06,110 --> 00:11:09,740 waar ik mijn volgende stap kan nemen. 199 00:11:09,740 --> 00:11:14,140 Van die kon ik al overwegen mogelijkheden eronder. 200 00:11:14,140 --> 00:11:18,030 En dan O zou krijgen te kiezen tussen deze. 201 00:11:18,030 --> 00:11:22,290 >> En ik kon houden het bouwen van deze boom uit totdat ik op het punt 202 00:11:22,290 --> 00:11:26,960 waarbij ofwel iemand wint de game-- dat is 203 00:11:26,960 --> 00:11:31,070 kreeg om te worden beschouwd als een blad node-- of de raad van bestuur is helemaal vol 204 00:11:31,070 --> 00:11:32,704 en niemand heeft gewonnen. 205 00:11:32,704 --> 00:11:34,370 En dat gaat ook een blad knooppunt zijn. 206 00:11:34,370 --> 00:11:35,411 Dat gaat naar een gelijkspel. 207 00:11:35,411 --> 00:11:37,820 208 00:11:37,820 --> 00:11:41,680 >> Maar het lastige ding met dit is als dit was gewoon een gewone zoekopdracht 209 00:11:41,680 --> 00:11:44,269 probleem, zou ik in staat zijn om zeg, nou, X moet gaan hier. 210 00:11:44,269 --> 00:11:45,560 En O moeten weg daar te gaan. 211 00:11:45,560 --> 00:11:46,770 En dan X moet hierheen gaan. 212 00:11:46,770 --> 00:11:48,269 En dan O moeten weg daar te gaan. 213 00:11:48,269 --> 00:11:51,860 En dan X kan drie krijgen in een rij, en ik win. 214 00:11:51,860 --> 00:11:54,870 En is het spel voorbij zou zijn in vijf bewegingen, drie voor mij, 215 00:11:54,870 --> 00:11:57,710 twee voor mijn tegenstander. 216 00:11:57,710 --> 00:12:01,300 Maar ik denk niet altijd te kiezen dat. 217 00:12:01,300 --> 00:12:03,720 >> Dus in plaats daarvan, wat we zal moeten doen 218 00:12:03,720 --> 00:12:06,270 is dat we gaan moeten een nieuwe strategie. 219 00:12:06,270 --> 00:12:09,350 En de strategie die spel-playing algoritmen vaak gebruik 220 00:12:09,350 --> 00:12:12,000 is wat minimax genoemd. 221 00:12:12,000 --> 00:12:15,500 Centraal in minimax is dat we 222 00:12:15,500 --> 00:12:21,365 gaan naar de beweging die geeft pick onze tegenstander het slechtst mogelijke set 223 00:12:21,365 --> 00:12:22,790 bewegingen die ze kunnen maken. 224 00:12:22,790 --> 00:12:25,570 225 00:12:25,570 --> 00:12:28,870 Het doet me geen goed doen om een ​​beweging waar de kiezen 226 00:12:28,870 --> 00:12:31,952 Ik zou in staat zijn om te winnen na dat, omdat mijn tegenstander niet 227 00:12:31,952 --> 00:12:33,160 gaat me die kans te geven. 228 00:12:33,160 --> 00:12:37,770 Ze gaan om wat te kiezen verschrikkelijke uitkomst voor mij. 229 00:12:37,770 --> 00:12:42,010 Dus ik ga het maken bewegen dat dwingt mijn tegenstander 230 00:12:42,010 --> 00:12:45,760 iets beter voor me doen. 231 00:12:45,760 --> 00:12:46,260 Prima. 232 00:12:46,260 --> 00:12:48,410 Laten we eens zien hoe dat uitpakt. 233 00:12:48,410 --> 00:12:51,640 Dus hier is ons algoritme in pseudocode. 234 00:12:51,640 --> 00:12:54,450 We gaan genereren het hele spel boom. 235 00:12:54,450 --> 00:12:56,757 We gaan bouwen de gehele structuur. 236 00:12:56,757 --> 00:12:57,840 En dan gaan we door te gaan. 237 00:12:57,840 --> 00:13:02,100 En op de bodem van elk van de eindknopen bij elk van de bladeren, 238 00:13:02,100 --> 00:13:07,850 zullen we evalueren hoe waardevol is dat voor mij? 239 00:13:07,850 --> 00:13:11,690 En we gaan de waarde dingen die zijn goed voor mij als positief. 240 00:13:11,690 --> 00:13:14,460 Dingen die niet goed voor mij minder positief zal zijn, of nul, 241 00:13:14,460 --> 00:13:16,480 of zelfs negatief. 242 00:13:16,480 --> 00:13:19,240 >> Dus in tic-tac-teen, misschien een overwinning voor mij is goed. 243 00:13:19,240 --> 00:13:20,290 Dat is een één. 244 00:13:20,290 --> 00:13:22,400 En een gelijkspel is nul. 245 00:13:22,400 --> 00:13:26,230 En iets dat is een verlies voor me, misschien is dat een negatieve. 246 00:13:26,230 --> 00:13:29,620 Het enige dat telt is dat het beter het is voor mij, hoe hoger de score 247 00:13:29,620 --> 00:13:32,160 het ontvangt. 248 00:13:32,160 --> 00:13:36,690 Van deze mogelijkheden op bodem, dan gaan we naar boven te filteren. 249 00:13:36,690 --> 00:13:40,650 En wanneer het is mijn kans om te kiezen onder een reeks van alternatieven, 250 00:13:40,650 --> 00:13:44,460 Ik zal degene die kiezen kreeg de hoogste score. 251 00:13:44,460 --> 00:13:47,200 >> En wanneer het is mijn tegenstanders wenden om uit te kiezen, 252 00:13:47,200 --> 00:13:52,350 Ik ga ervan uit dat ze gaan kiezen voor degene met de laagste score. 253 00:13:52,350 --> 00:13:56,090 En als ik dit helemaal naar de top van de boom, 254 00:13:56,090 --> 00:14:03,150 Ik zal een pad dat geeft hebben gekozen me het beste resultaat dat ik kan krijgen, 255 00:14:03,150 --> 00:14:09,110 veronderstelling dat mijn tegenstander maakt de juiste bewegingen. 256 00:14:09,110 --> 00:14:11,940 >> Oké, dus laten we zien dit in actie als eerste. 257 00:14:11,940 --> 00:14:14,980 En dan gaan we eigenlijk kijk naar de code voor het. 258 00:14:14,980 --> 00:14:16,780 Dus stel ik deze grote boom. 259 00:14:16,780 --> 00:14:18,280 En nu ben ik niet spelen tic-tac-teen. 260 00:14:18,280 --> 00:14:20,405 Ik wilde u iets een beetje rijker. 261 00:14:20,405 --> 00:14:23,560 Dus ik heb een aantal spel waar kreeg er zijn veel verschillende scores 262 00:14:23,560 --> 00:14:26,390 dat ik zou kunnen hebben aan het eind. 263 00:14:26,390 --> 00:14:27,980 En dus ik bouwen deze complete boom. 264 00:14:27,980 --> 00:14:29,070 En ik krijg om eerst te verplaatsen. 265 00:14:29,070 --> 00:14:31,290 Ik ben aan de wortel van de boom. 266 00:14:31,290 --> 00:14:36,150 >> En ik krijg om dat-- kiezen dus ik krijg maximaliseren over die eerste knooppunt. 267 00:14:36,150 --> 00:14:38,410 En dan mijn tegenstander krijgt om te gaan. 268 00:14:38,410 --> 00:14:41,910 En dan krijg ik nog een keer te gaan. 269 00:14:41,910 --> 00:14:46,830 Dus neer op de bodem, ik heb een set van mogelijkheden die ik kan kiezen, 270 00:14:46,830 --> 00:14:50,570 verschillende terminal staten van het spel. 271 00:14:50,570 --> 00:14:54,980 Als ik in die verre linkerhoek, 272 00:14:54,980 --> 00:14:58,867 en ik zie dat ik een keuze heb tussen een acht, een zeven en een twee 273 00:14:58,867 --> 00:15:00,450 goed, ik ben degene die krijgt om te kiezen. 274 00:15:00,450 --> 00:15:02,910 Dus ik ga om uit te kiezen het beste één van die. 275 00:15:02,910 --> 00:15:05,650 Ik ga naar de acht kiezen. 276 00:15:05,650 --> 00:15:10,090 >> Dus ik weet dat als ik ooit de slag om dat punt, 277 00:15:10,090 --> 00:15:13,890 Ik zal in staat zijn om dat acht punten te krijgen. 278 00:15:13,890 --> 00:15:17,410 Als ik uiteindelijk bij het volgende punt in de volgende knoop over, 279 00:15:17,410 --> 00:15:20,760 een negen, een één of een zes, goed, ik ben naar de beste van deze kiezen. 280 00:15:20,760 --> 00:15:21,950 Ik zal de negen kiezen. 281 00:15:21,950 --> 00:15:24,880 Als ik een keuze tussen twee en vier, en één, 282 00:15:24,880 --> 00:15:28,240 Ik zal de vier, de hoogste kiezen. 283 00:15:28,240 --> 00:15:31,990 >> Nu, als ik kijk naar het niveau boven dat, mijn tegenstander 284 00:15:31,990 --> 00:15:34,440 is de een krijgt om die keuze te maken. 285 00:15:34,440 --> 00:15:37,040 Dus mijn tegenstander krijgt om kiezen, wil ik hem te geven 286 00:15:37,040 --> 00:15:39,250 het ding dat gaat om hem acht punten te krijgen, 287 00:15:39,250 --> 00:15:41,916 of ik geef hem het ding dat is ga hem negen punten te geven, 288 00:15:41,916 --> 00:15:45,240 of het ding dat gaat hem vier punten op te geven? 289 00:15:45,240 --> 00:15:49,130 En mijn tegenstander, die rationele, gaat 290 00:15:49,130 --> 00:15:53,470 het minimum van deze kiezen, gaat de vier te kiezen. 291 00:15:53,470 --> 00:15:56,020 >> En ik kan doen door de gehele structuur. 292 00:15:56,020 --> 00:15:59,110 Ik kan gaan naar die middle set van drie. 293 00:15:59,110 --> 00:16:01,517 En ik kan kiezen tussen een, drie en vijf. 294 00:16:01,517 --> 00:16:02,350 En ik krijg om te kiezen. 295 00:16:02,350 --> 00:16:03,810 Dus kies ik een vijf. 296 00:16:03,810 --> 00:16:05,340 Ik kan drie, negen of twee te kiezen. 297 00:16:05,340 --> 00:16:07,570 Ik krijg om uit te kiezen, dus kies ik de negen. 298 00:16:07,570 --> 00:16:09,290 Zes, vijf, of twee, ik kies. 299 00:16:09,290 --> 00:16:11,539 Ik krijg om de zes te kiezen. 300 00:16:11,539 --> 00:16:13,080 Niveau boven dat, wie krijgt om te kiezen? 301 00:16:13,080 --> 00:16:16,280 302 00:16:16,280 --> 00:16:18,140 Wie krijgt om te kiezen? 303 00:16:18,140 --> 00:16:20,000 De andere man, mijn tegenstander. 304 00:16:20,000 --> 00:16:22,583 Dus kiezen ze vijf, negen, of zes, welke? 305 00:16:22,583 --> 00:16:23,410 >> Publiek: De vijf. 306 00:16:23,410 --> 00:16:25,250 >> SPEAKER: Ze kiezen de vijf. 307 00:16:25,250 --> 00:16:27,400 Ze krijgen tot het minimum te kiezen. 308 00:16:27,400 --> 00:16:29,690 En dan de laatste, kiezen voor een, twee, of drie. 309 00:16:29,690 --> 00:16:31,720 Ik krijg om uit te kiezen, dus ik drie te kiezen. 310 00:16:31,720 --> 00:16:34,370 Negen, zeven, of twee, kies ik negen. 311 00:16:34,370 --> 00:16:37,070 En 11, zes of vier, kies ik 11. 312 00:16:37,070 --> 00:16:41,190 Mijn tegenstander kiest dan drie, negen, of 11, kiest het minimum. 313 00:16:41,190 --> 00:16:43,290 Hij geeft me een drie. 314 00:16:43,290 --> 00:16:47,780 En uiteindelijk bovenaan de boom, krijg ik om opnieuw te kiezen. 315 00:16:47,780 --> 00:16:51,190 En ik krijg om te kiezen tussen vier, vijf, of drie. 316 00:16:51,190 --> 00:16:52,270 Dus ik neem de vijf. 317 00:16:52,270 --> 00:16:55,070 318 00:16:55,070 --> 00:17:00,891 >> Als ik om alles te controleren, zou ik het pad die tot de 11. 319 00:17:00,891 --> 00:17:02,390 Maar ik snap het niet om die keuze te maken. 320 00:17:02,390 --> 00:17:04,220 Als ik naar beneden dat pad. 321 00:17:04,220 --> 00:17:10,710 Mijn tegenstander zal me dwingen de keuze die leidt tot drie. 322 00:17:10,710 --> 00:17:14,530 Dus het beste dat ik kan doen is dat midden tak nemen, 323 00:17:14,530 --> 00:17:19,859 die keuze is dat uiteindelijk gaat me tot vijf punten. 324 00:17:19,859 --> 00:17:23,230 Dat is wat minimax doet. 325 00:17:23,230 --> 00:17:23,807 >> Prima. 326 00:17:23,807 --> 00:17:24,890 Laten we eens een kijkje nemen op die. 327 00:17:24,890 --> 00:17:27,480 328 00:17:27,480 --> 00:17:32,330 Dus hier in de CS50 IDE is een programma dat 329 00:17:32,330 --> 00:17:36,540 implementeert minimax om tic-tac-teen spelen. 330 00:17:36,540 --> 00:17:40,100 We gaan bouwen een representatie. 331 00:17:40,100 --> 00:17:44,390 We gaan twee opponent-- hebben of twee spelers, onze computer 332 00:17:44,390 --> 00:17:46,090 speler en een menselijke speler. 333 00:17:46,090 --> 00:17:48,980 334 00:17:48,980 --> 00:17:53,090 Speler nummer één zal spelen O. Dat zal de machine speler. 335 00:17:53,090 --> 00:17:55,747 Ze krijgen naar de tweede verplaatsen. 336 00:17:55,747 --> 00:17:57,830 En de andere spelers, onze menselijke speler, zal X. 337 00:17:57,830 --> 00:17:59,880 >> En tot mijn leven te maken beetje simpel, ik ga 338 00:17:59,880 --> 00:18:03,060 om die speler negatief bestempelen. 339 00:18:03,060 --> 00:18:05,026 Dus ik kan alleen maar vermenigvuldigen door negatieve om te wisselen 340 00:18:05,026 --> 00:18:06,400 tussen een speler en de ander. 341 00:18:06,400 --> 00:18:09,030 342 00:18:09,030 --> 00:18:12,250 Oké, dus laten we een kijkje nemen op wat we eigenlijk gaan doen. 343 00:18:12,250 --> 00:18:15,840 We gaan ons bestuur te bepalen. 344 00:18:15,840 --> 00:18:19,060 Het gaat worden, nou ja, we gaan om deze te drie bij drie, 345 00:18:19,060 --> 00:18:21,580 of we kunnen zelfs spelen vijf bij vijf of zeven 346 00:18:21,580 --> 00:18:28,870 door zeven tic-tac-teen als je wilt als, op basis van een extra dimensie D. 347 00:18:28,870 --> 00:18:31,260 >> En we zullen een paar heeft van helper functies 348 00:18:31,260 --> 00:18:34,360 dat zal dingen doen, zoals initialiseren de Screen-- of sorry, 349 00:18:34,360 --> 00:18:38,900 initialiseren onze variabelen, schakelt de scherm, trek de raad van bestuur op het scherm, 350 00:18:38,900 --> 00:18:41,060 een die een raad controleert te zien of 351 00:18:41,060 --> 00:18:44,520 er is een winnaar, die ontleedt via de command line, 352 00:18:44,520 --> 00:18:50,670 alleen maar om te helpen, iemand die leest in input, en een functie genaamd minimax. 353 00:18:50,670 --> 00:18:52,746 En dat is de ene zullen we het meest over de zorg. 354 00:18:52,746 --> 00:18:54,120 Maar laten we eerst kijken naar de belangrijkste. 355 00:18:54,120 --> 00:18:57,490 356 00:18:57,490 --> 00:18:58,510 >> Wat doen we? 357 00:18:58,510 --> 00:19:00,570 Nou, we gaan ontleden onze command line, 358 00:19:00,570 --> 00:19:04,300 lees net in en zien wat dimensie board we zouden willen hebben. 359 00:19:04,300 --> 00:19:07,330 We zullen ons bestuur initialiseren. 360 00:19:07,330 --> 00:19:10,360 En dan zullen we een in te voeren grote wilde lus, herhaaldelijk 361 00:19:10,360 --> 00:19:16,630 aanvaarden beweegt totdat het spel is gewonnen, of er is geen beweegt vertrokken. 362 00:19:16,630 --> 00:19:20,560 Elke keer dat we gaan door dat lus, we zullen het scherm te wissen. 363 00:19:20,560 --> 00:19:23,290 We zullen het bord te tekenen op het scherm. 364 00:19:23,290 --> 00:19:28,750 En we zijn bewust soort abstraheren deze weg als subroutines, 365 00:19:28,750 --> 00:19:32,030 zodat we niet al te veel zorgen te maken de details van hoe ze gebeuren. 366 00:19:32,030 --> 00:19:33,480 >> U vindt de code later vandaag. 367 00:19:33,480 --> 00:19:37,970 En als je wilt om door te kijken en uit te vinden, je kunt ze allemaal zien. 368 00:19:37,970 --> 00:19:39,890 Maar we zullen een bord te tekenen op het scherm. 369 00:19:39,890 --> 00:19:43,620 En dan zullen we controleren en zien, hebben we een winnaar? 370 00:19:43,620 --> 00:19:46,290 Heeft iemand won dit spel? 371 00:19:46,290 --> 00:19:49,260 Als ze hebben, zullen we afdrukken een overwinning bericht. 372 00:19:49,260 --> 00:19:51,680 En we zullen het spel te beëindigen. 373 00:19:51,680 --> 00:19:54,510 >> We zullen ook controleren en zien of er een gelijkspel. 374 00:19:54,510 --> 00:19:56,620 Het zal gemakkelijk zijn om te zien of er een gelijkspel. 375 00:19:56,620 --> 00:20:00,700 Dit betekent dat alle ruimten vol, maar er is nog geen winnaar geweest. 376 00:20:00,700 --> 00:20:03,580 We kunnen een band verklaren en worden gedaan. 377 00:20:03,580 --> 00:20:10,530 Dan is de echte meat-- als het is een machine-speler, 378 00:20:10,530 --> 00:20:14,120 we zullen toestaan ​​dat machine speler te zoeken 379 00:20:14,120 --> 00:20:19,500 door middel van het gebruik van deze minimax algoritme, om de beste beweging die het kan vinden. 380 00:20:19,500 --> 00:20:22,310 En dan zullen we die beweging zetten. 381 00:20:22,310 --> 00:20:27,640 >> Anders, als het een menselijke speler, zullen we een aantal input van de mens te lezen. 382 00:20:27,640 --> 00:20:30,800 En dan is de vraag of het de mens speler of de machine-speler, 383 00:20:30,800 --> 00:20:32,800 zullen we een paar weinig doen stukjes van foutcontrole, 384 00:20:32,800 --> 00:20:36,910 zorg ervoor dat het blijft binnen de grenzen van de werkelijke afmetingen van de raad van bestuur 385 00:20:36,910 --> 00:20:40,040 die we hebben, ervoor zorgen dat dat die ruimte leeg is, 386 00:20:40,040 --> 00:20:43,570 dat niemand zet een stuk in er al. 387 00:20:43,570 --> 00:20:45,810 En dan gaan we gewoon een stuk op het bord, 388 00:20:45,810 --> 00:20:51,550 verander de speler naar de volgende laag, en increment hoeveel zetten zijn gebeurd. 389 00:20:51,550 --> 00:20:54,090 >> Dat is de belangrijkste lus voor onze tic-tac-teen spel. 390 00:20:54,090 --> 00:20:57,000 391 00:20:57,000 --> 00:21:02,340 Minimax is dus precies het algoritme dat we eerder. 392 00:21:02,340 --> 00:21:04,710 De enige aanpassing die we hebben gemaakt, zodat we 393 00:21:04,710 --> 00:21:07,290 kan hoger spelen dimensionale boards is we hebben 394 00:21:07,290 --> 00:21:11,070 hield deze extra parameter genaamd diepte. 395 00:21:11,070 --> 00:21:14,870 En diepte gewoon zegt, als ik ben neerwaarts zoeken door middel van die boom 396 00:21:14,870 --> 00:21:19,022 en ik krijg zo ver naar beneden voorbij een bepaald niveau diepte 397 00:21:19,022 --> 00:21:20,730 dat ik gewoon niet willen om verder te gaan, 398 00:21:20,730 --> 00:21:25,630 Ik ga om te stoppen en gewoon de raad van bestuur te evalueren op dat punt. 399 00:21:25,630 --> 00:21:27,310 Ik zal controleren en zien of er een winnaar. 400 00:21:27,310 --> 00:21:29,240 Als er een winnaar, ik ze terug. 401 00:21:29,240 --> 00:21:31,720 Anders ga ik door middel van een lus. 402 00:21:31,720 --> 00:21:34,380 En ik zeg, voor al de mogelijke locaties 403 00:21:34,380 --> 00:21:38,080 dat ik zou kunnen nemen zoals mijn verhuizing, ik zal 404 00:21:38,080 --> 00:21:43,760 bouwen van een hypothetische bord dat inclusief mijn verhuizing op die raad, 405 00:21:43,760 --> 00:21:45,960 en vervolgens recursief oproepen minimax. 406 00:21:45,960 --> 00:21:49,360 407 00:21:49,360 --> 00:21:53,900 >> Als het mijn verhuizing, krijg ik tot het vinden een die heeft de grootste score. 408 00:21:53,900 --> 00:21:58,710 Als het verplaatsen van mijn tegenstander, vinden we degene die heeft de minimale score. 409 00:21:58,710 --> 00:22:02,240 En alles is gewoon bijhouden. 410 00:22:02,240 --> 00:22:04,789 Oké, dus laten we zien deze run. 411 00:22:04,789 --> 00:22:06,830 Eigenlijk, misschien kunnen we krijgen een paar vrijwilligers 412 00:22:06,830 --> 00:22:09,930 om te komen spelen tic-tac-teen. 413 00:22:09,930 --> 00:22:12,780 [Onhoorbaar] één, en één meer, twee, daar. 414 00:22:12,780 --> 00:22:13,550 Kom op maximaal. 415 00:22:13,550 --> 00:22:19,290 416 00:22:19,290 --> 00:22:23,650 >> Dus laten we verder gaan en hervatten dit volledig. 417 00:22:23,650 --> 00:22:24,150 Dus, hi. 418 00:22:24,150 --> 00:22:24,920 >> Publiek: Hi. 419 00:22:24,920 --> 00:22:25,420 >> SPEAKER: Wat is uw naam? 420 00:22:25,420 --> 00:22:26,086 >> Publiek: Gorav. 421 00:22:26,086 --> 00:22:26,840 SPEAKER: Gorav. 422 00:22:26,840 --> 00:22:27,800 >> Publiek: Ik ben Layla. 423 00:22:27,800 --> 00:22:29,490 >> SPEAKER: En Layla, en Layla, sorry. 424 00:22:29,490 --> 00:22:30,384 Kom op maximaal. 425 00:22:30,384 --> 00:22:32,050 Gorav, we gaan heb je eerst gaan. 426 00:22:32,050 --> 00:22:37,710 En ik ga u vragen om een ​​niet vreselijk goede tic-tac-teen speler. 427 00:22:37,710 --> 00:22:40,130 OK, dus alle druk uit is op je. 428 00:22:40,130 --> 00:22:44,660 Laten we eens kijken, hoewel, dat onze machine speler kan eigenlijk iets slim te doen. 429 00:22:44,660 --> 00:22:45,310 Dus ga je gang. 430 00:22:45,310 --> 00:22:49,830 Je gaat typen waarin coördineren u wilt uw X in te zetten. 431 00:22:49,830 --> 00:22:55,170 A0, OK, en de machine is gegaan meteen en zet haar merk in A1. 432 00:22:55,170 --> 00:22:56,640 >> Leg de O op het bord. 433 00:22:56,640 --> 00:22:58,970 Oké, nu ga je gang. 434 00:22:58,970 --> 00:23:00,193 Waar wilt u naar toe? 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 Onze machine speler heeft genomen het midden plein, geblokkeerd jou. 438 00:23:08,430 --> 00:23:10,320 Dus dat was een goed, slimme ding om te doen. 439 00:23:10,320 --> 00:23:13,430 440 00:23:13,430 --> 00:23:14,250 Je hebt geblokkeerd is. 441 00:23:14,250 --> 00:23:15,210 Dat is uitstekend. 442 00:23:15,210 --> 00:23:16,390 Het neemt de hoek. 443 00:23:16,390 --> 00:23:23,890 444 00:23:23,890 --> 00:23:30,430 >> En het zal je dwingen om neem het een laatste ruimte, B0. 445 00:23:30,430 --> 00:23:32,220 En het spel eindigt in een gelijkspel. 446 00:23:32,220 --> 00:23:35,030 Maar het speelde een redelijke spel tegen u, nietwaar? 447 00:23:35,030 --> 00:23:36,956 Oké, heel erg bedankt, Gorav. 448 00:23:36,956 --> 00:23:40,860 >> [APPLAUS] 449 00:23:40,860 --> 00:23:44,723 >> Oké, Layla, we gaan het spel op je hier. 450 00:23:44,723 --> 00:23:46,940 >> PUBLIEK: Oh, geweldig. 451 00:23:46,940 --> 00:23:49,950 >> SPEAKER: We gaan geven je vier bij vier tic-tac-teen. 452 00:23:49,950 --> 00:23:54,760 Nu, vier door vier, moet je om te winnen met vier op een rij, niet drie op een rij. 453 00:23:54,760 --> 00:23:56,135 En het is allemaal van jou. 454 00:23:56,135 --> 00:24:02,180 455 00:24:02,180 --> 00:24:04,420 Dus Layla nam D1. 456 00:24:04,420 --> 00:24:11,730 We gaan nu volgen onze computer speler hier. 457 00:24:11,730 --> 00:24:16,910 Drie bij drie tic-tac-teen is het soort ding dat is gemakkelijk voor ons allemaal. 458 00:24:16,910 --> 00:24:21,960 Maar het is nog steeds leuk om het te zien computer-speler maken van slimme moves. 459 00:24:21,960 --> 00:24:23,725 Vier bij vier krijgt een beetje lastiger. 460 00:24:23,725 --> 00:24:42,960 461 00:24:42,960 --> 00:24:44,230 >> Keurig gedaan. 462 00:24:44,230 --> 00:24:46,210 Oké, dus Layla's afgewerkt. 463 00:24:46,210 --> 00:24:48,270 Oh, en we moeten daar eindigde. 464 00:24:48,270 --> 00:24:51,870 Maar laten we nog één hier. 465 00:24:51,870 --> 00:24:53,480 Dus Layla, dank je. 466 00:24:53,480 --> 00:24:55,112 Keurig gedaan. 467 00:24:55,112 --> 00:24:57,517 >> [APPLAUS] 468 00:24:57,517 --> 00:25:00,410 469 00:25:00,410 --> 00:25:04,750 >> Dus onze tic-tac-teen speler gaat door en vindt locaties, 470 00:25:04,750 --> 00:25:07,040 lost ze met behulp van deze minimax. 471 00:25:07,040 --> 00:25:08,990 En ik had een diepte-instelling Op dat zodat 472 00:25:08,990 --> 00:25:11,010 zou niet te snel lopen, dat is waarschijnlijk de reden waarom 473 00:25:11,010 --> 00:25:16,790 Layla was te mooi vooruit kunnen gaan zoals ze deed, en deed het erg goed. 474 00:25:16,790 --> 00:25:20,450 Maar deze systemen die net ga door en brute kracht 475 00:25:20,450 --> 00:25:23,870 dieper en dieper en dieper, en houdt het vinden van de oplossing 476 00:25:23,870 --> 00:25:29,890 die ze nodig hebben, dat soort systemen zijn zeer succesvol in deze, nou, 477 00:25:29,890 --> 00:25:32,700 standaard bordspellen. 478 00:25:32,700 --> 00:25:37,060 >> En inderdaad, als we kijken naar een drie bij drie tic-tac-teen spel, 479 00:25:37,060 --> 00:25:40,040 Dit is in feite een opgelost probleem. 480 00:25:40,040 --> 00:25:45,430 En dit is een prachtige diagram van Randall Munroe bij XKCD, 481 00:25:45,430 --> 00:25:52,130 waaruit blijkt welke beweging die u moet nemen, gezien bewegingen van je tegenstander. 482 00:25:52,130 --> 00:25:56,420 Dit is iets dat we konden eenvoudig van tevoren opgeven. 483 00:25:56,420 --> 00:26:00,180 Maar wat gebeurt er als we meer complexe games, meer ingewikkelde games, 484 00:26:00,180 --> 00:26:05,690 waar er grotere borden meer, mogelijkheden, diepere strategie? 485 00:26:05,690 --> 00:26:09,660 >> Het blijkt dat dit brute kracht zoeken nog steeds 486 00:26:09,660 --> 00:26:14,150 doet redelijk goed, met uitzondering van als je naar het punt 487 00:26:14,150 --> 00:26:19,230 waarbij die boom is zo groot dat je niet kan vertegenwoordigen het allemaal. 488 00:26:19,230 --> 00:26:22,370 489 00:26:22,370 --> 00:26:28,280 Wanneer u de gehele boom niet kan berekenen, als je niet naar voren en duw kan gaan 490 00:26:28,280 --> 00:26:32,204 uzelf op het punt waar je hebt gekregen van de hele boom in het geheugen, 491 00:26:32,204 --> 00:26:34,370 of dat je kunt krijgen in het geheugen en het zal alleen maar 492 00:26:34,370 --> 00:26:39,200 neem je veel te lang te doorzoeken , je moet iets slimmer te doen. 493 00:26:39,200 --> 00:26:42,620 494 00:26:42,620 --> 00:26:46,450 >> Om dat te doen, je moeten twee dingen doen. 495 00:26:46,450 --> 00:26:49,030 Ten eerste, moet je een aantal te vinden manier van het beperken van uw diepte. 496 00:26:49,030 --> 00:26:50,370 Nou, dat is OK. 497 00:26:50,370 --> 00:26:55,740 We kunnen een aantal leuke, minimum vinden en zeggen: je kunt alleen gaan zo diep. 498 00:26:55,740 --> 00:27:00,890 Maar als je dat doet, dat betekent dat je hebben deze gedeeltelijk onvolledig planken. 499 00:27:00,890 --> 00:27:04,770 En je moet kiezen, doe ik graag dit gedeeltelijk onvolledige board, 500 00:27:04,770 --> 00:27:08,600 of dit gedeeltelijk onvolledige board? 501 00:27:08,600 --> 00:27:11,910 >> En op onze vier door vier tic-tac-teen spel, 502 00:27:11,910 --> 00:27:15,240 onze computer speler kreeg neer naar de bodem en het zei, 503 00:27:15,240 --> 00:27:16,800 Ik heb twee verschillende platen. 504 00:27:16,800 --> 00:27:17,940 Geen van beiden is een win. 505 00:27:17,940 --> 00:27:19,120 Geen van beiden is een verlies. 506 00:27:19,120 --> 00:27:22,070 Geen van beiden is een gelijkspel. 507 00:27:22,070 --> 00:27:24,100 Hoe kies ik tussen hen? 508 00:27:24,100 --> 00:27:26,200 En het niet hebben van een slimme manier om dat te doen. 509 00:27:26,200 --> 00:27:28,910 510 00:27:28,910 --> 00:27:32,850 >> We zien dit soort evaluatie gebeurt de hele tijd 511 00:27:32,850 --> 00:27:35,290 als we in meer complexe games. 512 00:27:35,290 --> 00:27:37,600 Schaken is een goed voorbeeld. 513 00:27:37,600 --> 00:27:41,550 In schaken, we hebben, eerst van alles, een grotere plank. 514 00:27:41,550 --> 00:27:43,370 We hebben veel meer stukken. 515 00:27:43,370 --> 00:27:47,930 En het positioneren van deze stukken en de manier waarop deze stukken te verplaatsen 516 00:27:47,930 --> 00:27:50,370 is van cruciaal belang. 517 00:27:50,370 --> 00:27:53,700 Dus als ik wil minimax gebruiken, Ik moet in staat zijn om aan te geven 518 00:27:53,700 --> 00:27:58,240 en zeggen: dit board waar niemand heeft gewonnen of verloren nog, 519 00:27:58,240 --> 00:28:04,310 is enigszins beter dan die andere board, waar niemand heeft gewonnen of verloren. 520 00:28:04,310 --> 00:28:06,740 >> Om dat te doen, kan ik doen dingen als ik zou gewoon 521 00:28:06,740 --> 00:28:10,787 optellen hoeveel stukken heb ik en hoeveel stukken heb je? 522 00:28:10,787 --> 00:28:12,870 Of ik misschien anders geven stukken verschillende punten. 523 00:28:12,870 --> 00:28:14,420 Mijn koningin is 20 punten waard. 524 00:28:14,420 --> 00:28:16,500 Uw pion is één punt waard. 525 00:28:16,500 --> 00:28:18,920 Wie heeft meer punten in totaal? 526 00:28:18,920 --> 00:28:22,300 Of ik zou kunnen overwegen dingen willen, wie kreeg de betere bestuurlijke functie? 527 00:28:22,300 --> 00:28:26,820 Wiens beurt is het de volgende, iets dat ik kan 528 00:28:26,820 --> 00:28:31,220 doen om beter te evalueren Welke van deze mogelijkheden 529 00:28:31,220 --> 00:28:34,660 is beter zonder uitputtend overweegt 530 00:28:34,660 --> 00:28:36,565 elke beweging die daarna kon komen. 531 00:28:36,565 --> 00:28:39,740 532 00:28:39,740 --> 00:28:45,130 >> Nu om dat werk te maken, een van de dingen die 533 00:28:45,130 --> 00:28:48,680 gaat echt belangrijk geworden voor ons is niet alleen bewegen rechtdoor 534 00:28:48,680 --> 00:28:53,720 tot een bepaalde diepte te beperken, maar de mogelijkheid om te zeggen, 535 00:28:53,720 --> 00:28:59,380 een van deze ideeën die ik hebben, is zo slecht dat het 536 00:28:59,380 --> 00:29:02,280 niet overwegen waard alle mogelijke manieren 537 00:29:02,280 --> 00:29:06,680 die dingen kunnen gaan van kwaad tot erger. 538 00:29:06,680 --> 00:29:12,760 Om dat te doen, zullen we toe te voegen in minimax een principe genaamd Alph-beta. 539 00:29:12,760 --> 00:29:16,340 En alfa-beta zegt als je een slecht idee, 540 00:29:16,340 --> 00:29:22,840 verspil je tijd proberen om precies te weten hoe erg het is. 541 00:29:22,840 --> 00:29:24,990 >> Dus hier is wat we gaan doen. 542 00:29:24,990 --> 00:29:28,620 We gaan naar dezelfde nemen principes die we eerder hadden, 543 00:29:28,620 --> 00:29:32,200 hetzelfde minimax soort van het zoeken, maar we zijn 544 00:29:32,200 --> 00:29:37,570 gaande houden, niet alleen van de actuele waarden die we hebben, maar we zullen 545 00:29:37,570 --> 00:29:41,440 bijhouden van de best mogelijke waarde die ik kon krijgen, 546 00:29:41,440 --> 00:29:45,700 en het slechtst mogelijke uitkomst Ik kon hebben. 547 00:29:45,700 --> 00:29:50,470 En elke keer dat de slechtst mogelijke ding zoekt waarschijnlijk, 548 00:29:50,470 --> 00:29:52,694 Ik zal dat een deel van de boom te verlaten. 549 00:29:52,694 --> 00:29:54,610 En ik zal niet eens de moeite te kijken naar het meer. 550 00:29:54,610 --> 00:29:57,680 551 00:29:57,680 --> 00:30:02,600 >> Oké, dus voorstellen dat we beginnen met dit spel precies dezelfde boom. 552 00:30:02,600 --> 00:30:05,200 En nu gaan we om te gaan weer naar beneden, helemaal naar beneden 553 00:30:05,200 --> 00:30:07,200 dat linkerbenedenhoek. 554 00:30:07,200 --> 00:30:11,180 En in die onderste linkerhoek, we kijken en we evalueren dit board. 555 00:30:11,180 --> 00:30:15,700 Misschien is het een vier bij vier tic-tac-teen board, of misschien is het een schaakbord. 556 00:30:15,700 --> 00:30:18,620 Maar we kijken naar het, en we evalueren het, en we krijgen een waarde van acht. 557 00:30:18,620 --> 00:30:22,290 558 00:30:22,290 --> 00:30:28,030 >> Op dat moment weten we dat we gaan in ieder geval 559 00:30:28,030 --> 00:30:32,380 acht punten van deze bodem beslissing. 560 00:30:32,380 --> 00:30:36,620 Het maakt niet uit wat de andere twee, die zeven en die twee. 561 00:30:36,620 --> 00:30:38,580 Ze kunnen elke waarde ze wilden zijn. 562 00:30:38,580 --> 00:30:41,279 We gaan op te krijgen minste acht punten. 563 00:30:41,279 --> 00:30:43,070 Oké, maar we konden ga je gang en te controleren. 564 00:30:43,070 --> 00:30:45,080 Misschien een van hen beter is dan acht. 565 00:30:45,080 --> 00:30:46,000 >> We kijken naar de zeven. 566 00:30:46,000 --> 00:30:46,910 Is dat beter dan acht? 567 00:30:46,910 --> 00:30:48,680 Nee, dat niet verandert onze mening helemaal. 568 00:30:48,680 --> 00:30:49,460 We kijken naar de twee. 569 00:30:49,460 --> 00:30:50,543 Is dat beter dan acht? 570 00:30:50,543 --> 00:30:52,580 Nee, dat niet verandert onze mening helemaal. 571 00:30:52,580 --> 00:30:55,480 Dus nu weten we dat we uitgeput alle mogelijkheden zijn. 572 00:30:55,480 --> 00:30:58,330 We gaan niet te krijgen iets beter dan acht. 573 00:30:58,330 --> 00:31:01,310 We gaan precies acht te krijgen. 574 00:31:01,310 --> 00:31:03,825 >> En dus hebben we dat veranderen knooppunt en laten we zeggen, dat is nu een zekerheid. 575 00:31:03,825 --> 00:31:07,010 576 00:31:07,010 --> 00:31:10,270 We gaan een niveau boven dat. 577 00:31:10,270 --> 00:31:13,820 En nu iets wat we weten daarover minimalisatie niveau. 578 00:31:13,820 --> 00:31:18,560 We weten dat we nooit gaat krijgen meer dan acht punten als we naar beneden gaan 579 00:31:18,560 --> 00:31:20,910 die richting. 580 00:31:20,910 --> 00:31:22,980 Want zelfs als die andere twee takken blijken 581 00:31:22,980 --> 00:31:26,170 te zijn fantastisch en de moeite waard duizenden punten per stuk, 582 00:31:26,170 --> 00:31:31,666 onze tegenstander zal ons de minimum, en geef ons de acht. 583 00:31:31,666 --> 00:31:32,790 Oké, goed, laten we eens kijken. 584 00:31:32,790 --> 00:31:35,190 We zullen blijven gaan onderaan die weg. 585 00:31:35,190 --> 00:31:38,490 We gaan naar die midden aan de linkerkant. 586 00:31:38,490 --> 00:31:40,560 We naar beneden kijken en zien we er is een negen. 587 00:31:40,560 --> 00:31:45,590 We weten dat we gaan krijgen ten minste negen punten door te gaan naar beneden 588 00:31:45,590 --> 00:31:47,720 dat midden weg. 589 00:31:47,720 --> 00:31:52,110 En op dit punt, kunnen we gewoon te pauzeren. 590 00:31:52,110 --> 00:31:56,910 En we kunnen zeggen, kijk, ik weten het niveau boven, 591 00:31:56,910 --> 00:32:01,160 Ik ga krijgen niet meer dan acht wijst door naar beneden gaat deze richting. 592 00:32:01,160 --> 00:32:05,670 Maar als ik in het midden pad in plaats van de linker pad, 593 00:32:05,670 --> 00:32:08,980 Ik zou krijgen ten minste negen punten. 594 00:32:08,980 --> 00:32:13,590 >> Mijn tegenstander gaat nooit laat me gaan dat middenweg. 595 00:32:13,590 --> 00:32:14,650 Ze krijgen om te kiezen. 596 00:32:14,650 --> 00:32:18,140 En ze gaan het kiezen pad naar links richting acht, 597 00:32:18,140 --> 00:32:23,650 in plaats van in het midden in de richting van wat is er ten minste negen punten. 598 00:32:23,650 --> 00:32:25,334 Dus op dat punt, ik zal stoppen. 599 00:32:25,334 --> 00:32:26,500 En ik zeg, weet je wat? 600 00:32:26,500 --> 00:32:29,990 Ik heb niet om elke look meer in die richting. 601 00:32:29,990 --> 00:32:32,270 Want ik ben nooit van plan om er te komen. 602 00:32:32,270 --> 00:32:36,660 >> Ik kan overslaan die ene, en ik kan overslaan dat zes, 603 00:32:36,660 --> 00:32:39,720 want dat gaat nooit gebeuren. 604 00:32:39,720 --> 00:32:42,470 Dus ik zal gaan en ik zal beschouwen de volgende mogelijkheid. 605 00:32:42,470 --> 00:32:44,830 Ik ga er af en ik zeg, ik zie een twee. 606 00:32:44,830 --> 00:32:47,125 Ik weet dat als ik naar hier, ik ben naar ten minste twee krijgen. 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 Ik ga door. 610 00:32:51,520 --> 00:32:52,440 Ik zie een vier. 611 00:32:52,440 --> 00:32:54,920 Ik weet dat ik ga tenminste vier te krijgen. 612 00:32:54,920 --> 00:32:57,200 Er is nog veel tussen vier en acht, dat wel. 613 00:32:57,200 --> 00:32:58,454 Dus ik ga door. 614 00:32:58,454 --> 00:32:59,870 Ik kijk naar beneden en zie ik er een. 615 00:32:59,870 --> 00:33:01,614 Oké, ik weet dat als Ik ga op deze weg, 616 00:33:01,614 --> 00:33:03,280 Ik zal in staat zijn om de vier te kiezen. 617 00:33:03,280 --> 00:33:06,540 618 00:33:06,540 --> 00:33:08,980 Wat is mijn tegenstander gaat doen? 619 00:33:08,980 --> 00:33:12,310 Tussen iets dat me geeft acht, iets dat me geeft vier, 620 00:33:12,310 --> 00:33:14,730 en iets dat geeft me tenminste negen, 621 00:33:14,730 --> 00:33:17,550 goed, hij gaat me de vier te geven. 622 00:33:17,550 --> 00:33:20,110 En ik weet nu aan de top, ik ga 623 00:33:20,110 --> 00:33:23,145 kunnen in ieder geval vier punten uit dit spel. 624 00:33:23,145 --> 00:33:27,030 625 00:33:27,030 --> 00:33:30,900 >> Het idee van alfa-beta is om onderdelen zo af te snijden van de boom 626 00:33:30,900 --> 00:33:32,530 dat ik niet meer naar ze kijken. 627 00:33:32,530 --> 00:33:35,964 Maar het ziet er nog steeds als ik ben geweest kijken naar een groot deel van de boom. 628 00:33:35,964 --> 00:33:36,880 Laten we naar beneden. 629 00:33:36,880 --> 00:33:38,305 We zullen nu gaan de volgende. 630 00:33:38,305 --> 00:33:39,680 Beneden onderaan ik één. 631 00:33:39,680 --> 00:33:41,030 Ik weet dat ik ga in ieder geval een te krijgen. 632 00:33:41,030 --> 00:33:41,690 Ik blijf zoeken. 633 00:33:41,690 --> 00:33:42,625 >> Ik vind een drie. 634 00:33:42,625 --> 00:33:44,250 Ik weet dat ik ga ten minste drie te krijgen. 635 00:33:44,250 --> 00:33:44,840 Ik ga door. 636 00:33:44,840 --> 00:33:45,660 Ik vind een vijf. 637 00:33:45,660 --> 00:33:49,760 Ik weet dat ik ga tot vijf krijgen als ik in dat pad. 638 00:33:49,760 --> 00:33:52,580 En ik weet ook dan dat mijn tegenstander, als ik 639 00:33:52,580 --> 00:33:55,510 Kies het midden van de drie grote keuzes, 640 00:33:55,510 --> 00:34:01,440 hij gaat me iets dat vijf of minder. 641 00:34:01,440 --> 00:34:02,150 >> OK. 642 00:34:02,150 --> 00:34:03,400 Ik kan houden er heen te gaan. 643 00:34:03,400 --> 00:34:06,470 Ik kijk naar beneden en ik kan zeggen, wat moet ik 644 00:34:06,470 --> 00:34:08,239 te komen als ik naar beneden de middenweg? 645 00:34:08,239 --> 00:34:09,909 Ik ga er te komen, goed, drie. 646 00:34:09,909 --> 00:34:12,080 Ik ga om iets te krijgen dat is ten minste drie. 647 00:34:12,080 --> 00:34:16,030 Er is nog steeds dingen tussen drie en vijf, dus ik blijf zoeken. 648 00:34:16,030 --> 00:34:20,203 Oh, een negen, zal ik zeker neem dat meer dan drie. 649 00:34:20,203 --> 00:34:22,744 Ik ga in ieder geval negen krijgen als ik naar beneden gaan dat middenweg. 650 00:34:22,744 --> 00:34:25,530 651 00:34:25,530 --> 00:34:31,010 >> Stopt nu mijn tegenstander en zegt: kijk, daar is geen punt meer. 652 00:34:31,010 --> 00:34:33,669 Ik weet dat mijn minimalisering tegenstander, hij is 653 00:34:33,669 --> 00:34:36,210 gaat me het ding dat is te geven minder dan of gelijk aan vijf, 654 00:34:36,210 --> 00:34:39,030 in plaats van het ding dat is groter dan of gelijk aan negen. 655 00:34:39,030 --> 00:34:39,530 Ik stop. 656 00:34:39,530 --> 00:34:40,779 Ik niet meer kijken. 657 00:34:40,779 --> 00:34:43,280 Ik ga door. 658 00:34:43,280 --> 00:34:44,850 >> Ik kijk neer op deze. 659 00:34:44,850 --> 00:34:46,370 Tot op de bodem, vind ik een zes. 660 00:34:46,370 --> 00:34:50,040 Ik weet dat ik ga in ieder geval zes krijgen. 661 00:34:50,040 --> 00:34:53,130 En wat kan ik doen? 662 00:34:53,130 --> 00:34:54,877 Ik kan stoppen. 663 00:34:54,877 --> 00:34:57,460 Want er is een keuze tussen iets dat ten minste zes 664 00:34:57,460 --> 00:34:59,250 en iets dat minder dan vijf, hij is 665 00:34:59,250 --> 00:35:02,570 gaat me het ding te geven dat is minder dan vijf. 666 00:35:02,570 --> 00:35:04,779 En nu ik weet dat ik ga om precies te krijgen die keuze. 667 00:35:04,779 --> 00:35:06,195 Ik ga dat vijf keuze te krijgen. 668 00:35:06,195 --> 00:35:08,980 669 00:35:08,980 --> 00:35:10,010 >> Ik ga terug naar de top. 670 00:35:10,010 --> 00:35:11,450 Welke ga ik kiezen tussen iets 671 00:35:11,450 --> 00:35:14,449 die groter dan of gelijk aan vier, of iets dat is gelijk aan vijf? 672 00:35:14,449 --> 00:35:17,140 Ik ga iets te nemen dat is ten minste vijf. 673 00:35:17,140 --> 00:35:20,490 Ik ga de laatste pad, alle de weg naar beneden naar de bodem. 674 00:35:20,490 --> 00:35:21,260 Er is een één. 675 00:35:21,260 --> 00:35:23,410 OK, althans ik ga om een ​​punt te krijgen. 676 00:35:23,410 --> 00:35:24,427 Ik ga door. 677 00:35:24,427 --> 00:35:25,760 Twee, oh, dat is beter dan één. 678 00:35:25,760 --> 00:35:27,100 Ik ga in ieder geval twee krijgen. 679 00:35:27,100 --> 00:35:28,610 Ik vind een drie. 680 00:35:28,610 --> 00:35:31,450 Ik weet dat ik ga tot drie te krijgen. 681 00:35:31,450 --> 00:35:34,690 >> En het punt boven dat, mijn tegenstander gaat 682 00:35:34,690 --> 00:35:38,540 me iets dat op te geven minder dan of gelijk aan drie. 683 00:35:38,540 --> 00:35:40,940 En nu kan ik stoppen. 684 00:35:40,940 --> 00:35:46,290 Omdat in de keuze tussen mij zijn in staat om een ​​vijf en mijn tegenstander te krijgen 685 00:35:46,290 --> 00:35:52,290 geeft me iets minder dan drie, Ik ben altijd van plan om die vijf te nemen. 686 00:35:52,290 --> 00:35:56,810 Dus ik denk niet te evalueren dat onderste deel van de boom helemaal. 687 00:35:56,810 --> 00:35:59,470 >> Nu kan dit lijken gering. 688 00:35:59,470 --> 00:36:03,630 Maar als kleine stukjes van de rekenkunde, groter dan en kleiner dan, 689 00:36:03,630 --> 00:36:10,640 hele delen van de weg te kunnen snijden deze exponentieel groeiende boom, 690 00:36:10,640 --> 00:36:14,280 die leidt tot een enorme hoeveelheid spaargeld, besparingen 691 00:36:14,280 --> 00:36:17,630 dat groot genoeg dat ik zijn kan beginnen te spelen competitief 692 00:36:17,630 --> 00:36:21,330 bij meer complexe spellen. 693 00:36:21,330 --> 00:36:27,030 >> Oké, als we kijken naar de grootte en de complexiteit van de verschillende games, 694 00:36:27,030 --> 00:36:29,470 tic-tac-teen was onze eenvoudig voorbeeld. 695 00:36:29,470 --> 00:36:32,150 We hebben een klein bord, drie kregen door drie. 696 00:36:32,150 --> 00:36:36,030 We krijgen hooguit een gemiddelde van ongeveer vier verschillende keuzes 697 00:36:36,030 --> 00:36:38,440 als we door het spel. 698 00:36:38,440 --> 00:36:42,720 We hebben ergens rond 10 de vijfde mogelijk verschillende bladeren. 699 00:36:42,720 --> 00:36:45,200 En het bouwen van een tic-tac-teen speler, nou ja, we deden het gewoon. 700 00:36:45,200 --> 00:36:47,460 Het is makkelijk. 701 00:36:47,460 --> 00:36:49,890 >> Als wij gaan op naar iets meer complex, zoals Connect Four. 702 00:36:49,890 --> 00:36:53,170 Herinner je je dit spel waar de kleine penningen vallen in? 703 00:36:53,170 --> 00:36:58,490 Het is een zes bij zeven boord, niet zo veel groter, nog steeds 704 00:36:58,490 --> 00:37:00,770 heeft ongeveer dezelfde vertakking factor als tic-tac-teen. 705 00:37:00,770 --> 00:37:05,410 Ik heb ongeveer vier keuzes waar ik dingen kan zetten. 706 00:37:05,410 --> 00:37:10,760 Maar nu, ik heb veel meer leidt 10 tot de macht 21. 707 00:37:10,760 --> 00:37:14,440 Dat is iets dat is makkelijk genoeg dat we lossen het meteen. 708 00:37:14,440 --> 00:37:17,560 >> Dammen, meer je complex-- kreeg een acht bij acht boord. 709 00:37:17,560 --> 00:37:20,570 Je bent slechts op de helft van de op elk gewenst moment, dat wel. 710 00:37:20,570 --> 00:37:24,930 Je hebt een vertakking gekregen factor dat is ongeveer 2,8. 711 00:37:24,930 --> 00:37:28,160 Nou, we hebben een paar gekregen beweegt u kunt nemen. 712 00:37:28,160 --> 00:37:33,870 Je hebt ongeveer 10 kreeg de 31 bladeren, grotere en grotere en grotere ruimtes. 713 00:37:33,870 --> 00:37:37,340 Als ik moet doorzoeken die groter en groter ruimtes, 714 00:37:37,340 --> 00:37:42,220 dat is wanneer dingen zoals alfa-beta en kunnen hele takken weg te snijden 715 00:37:42,220 --> 00:37:44,420 wordt het van essentieel belang. 716 00:37:44,420 --> 00:37:47,440 >> Nu, dammen was makkelijk genoeg in 1992. 717 00:37:47,440 --> 00:37:51,400 Een computerprogramma genaamd Chinook winnen van de wereld checkers 718 00:37:51,400 --> 00:37:53,590 kampioen, Marion Tinsley. 719 00:37:53,590 --> 00:37:57,260 Sindsdien, geen menselijke meester speler heeft 720 00:37:57,260 --> 00:38:02,290 in staat geweest om de beste te verslaan computationele systemen. 721 00:38:02,290 --> 00:38:06,570 Als we kijken naar iets als schaken, nu nogmaals, we hebben een acht bij acht boord. 722 00:38:06,570 --> 00:38:09,870 Maar we hebben veel complexer stukken, meer complexe bewegingen. 723 00:38:09,870 --> 00:38:14,610 We hebben een vertakkingsfactor van ongeveer 35, 35 mogelijke zetten gemiddeld 724 00:38:14,610 --> 00:38:20,030 dat ik, en een staat kan nemen space, een aantal bladeren 725 00:38:20,030 --> 00:38:28,950 dat is uitgegroeid tot 10 de stroom 123, enorme aantallen mogelijkheden. 726 00:38:28,950 --> 00:38:35,570 >> Zelfs nog, moderne processoren in staat zijn om dit te doen met succes. 727 00:38:35,570 --> 00:38:43,900 In 1995 en vervolgens in 1997, een computer programma genaamd Deep Blue gebouwd door IBM 728 00:38:43,900 --> 00:38:49,601 dat liep op een gigantische supercomputer de huidige wereldkampioen te verslaan, 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 Dit was een keerpunt. 732 00:38:56,650 --> 00:39:00,620 Vandaag, echter, dat dezelfde verwerking kracht zit op mijn MacBook. 733 00:39:00,620 --> 00:39:04,180 734 00:39:04,180 --> 00:39:06,440 >> Verwerkingssnelheid houdt steeds sneller en sneller. 735 00:39:06,440 --> 00:39:09,500 We kunnen meer en meer te evalueren planken sneller en sneller. 736 00:39:09,500 --> 00:39:14,550 Maar belangrijker we beter evaluatiefuncties en beter snoeien 737 00:39:14,550 --> 00:39:15,460 methoden. 738 00:39:15,460 --> 00:39:19,560 Dus we kunnen zoeken in de ruimte meer ingewikkeld. 739 00:39:19,560 --> 00:39:22,350 De grootste van de raad van bestuur games die we kunnen bedenken, 740 00:39:22,350 --> 00:39:26,310 zoiets Go dat is kreeg een 19 met 19 board, 741 00:39:26,310 --> 00:39:32,490 nu opeens zijn we voorbij het punt waar de computationele systemen kunnen winnen. 742 00:39:32,490 --> 00:39:34,530 Er is geen computationele systeem die er zijn 743 00:39:34,530 --> 00:39:38,880 dat kan verslaan een professionele Go-speler. 744 00:39:38,880 --> 00:39:45,000 De beste systemen vandaag rang het ongeveer het soort goede amateur niveau. 745 00:39:45,000 --> 00:39:49,285 Dus er is nog steeds vrij een beetje uit daar dat je niet om nog te krijgen. 746 00:39:49,285 --> 00:39:51,840 747 00:39:51,840 --> 00:39:55,360 >> Oké, deze traditionele bordspellen, 748 00:39:55,360 --> 00:39:58,560 dit soort systemen waar we bouwen deze minimax, of het heeft 749 00:39:58,560 --> 00:40:06,300 alfa-beta of niet, deze algoritmen werken omdat er bepaalde beperkingen. 750 00:40:06,300 --> 00:40:08,520 We hebben een perfecte informatie de wereld. 751 00:40:08,520 --> 00:40:11,690 We weten waar alle stukken zijn. 752 00:40:11,690 --> 00:40:13,570 De wereld is statisch. 753 00:40:13,570 --> 00:40:16,220 Niemand krijgt het verplaatsen stukken rond terwijl ik 754 00:40:16,220 --> 00:40:20,640 zitten denken, waarbij ik aan de beurt. 755 00:40:20,640 --> 00:40:23,140 Er is een actie ruimte dat is discreet. 756 00:40:23,140 --> 00:40:26,900 Ik kan mijn pion hier zetten, of ik kan mijn pion hier plaatsen. 757 00:40:26,900 --> 00:40:30,520 Ik ben niet toegestaan ​​om mijn pion op te zetten de lijn tussen de twee pleinen. 758 00:40:30,520 --> 00:40:34,430 759 00:40:34,430 --> 00:40:36,520 >> En tenslotte de acties deterministisch. 760 00:40:36,520 --> 00:40:39,790 Ik weet dat als ik zeg, toren te ridder drie, 761 00:40:39,790 --> 00:40:44,660 mijn toren gaat eindigen bij knight drie, mits het een geldige zet. 762 00:40:44,660 --> 00:40:47,830 Er is geen onzekerheid over. 763 00:40:47,830 --> 00:40:52,490 Nu, als ik ga om meer verschillende soorten games, 764 00:40:52,490 --> 00:40:55,960 we die veronderstellingen breken. 765 00:40:55,960 --> 00:41:00,020 >> Wat als ik naar iets zoals klassieke videogames? 766 00:41:00,020 --> 00:41:04,180 Hier is een selectie van video games uit de Atari 2600. 767 00:41:04,180 --> 00:41:05,180 Wat moet ik daar? 768 00:41:05,180 --> 00:41:08,440 Ik heb Frogger, Space kreeg Invallers, Pitfall en Pac-Man. 769 00:41:08,440 --> 00:41:11,290 770 00:41:11,290 --> 00:41:14,840 Welke soorten omgevingen moet ik hier nu? 771 00:41:14,840 --> 00:41:16,900 Welke van deze veronderstellingen moet ik breken? 772 00:41:16,900 --> 00:41:19,410 773 00:41:19,410 --> 00:41:21,570 >> Nou, het hangt af van het spel. 774 00:41:21,570 --> 00:41:28,170 Ik kon schaken op de 2600, en het zou net zoals het vroeger was. 775 00:41:28,170 --> 00:41:33,020 Voor de meeste van deze systemen is er volledige kennis over de wereld. 776 00:41:33,020 --> 00:41:36,300 Er is helemaal deterministische acties. 777 00:41:36,300 --> 00:41:38,330 Maar gewoonlijk, werelds niet langer statisch. 778 00:41:38,330 --> 00:41:41,970 Dat wil zeggen, terwijl ik daar ben zit wachten, is er iets beweegt. 779 00:41:41,970 --> 00:41:44,320 De geesten komen naar me. 780 00:41:44,320 --> 00:41:46,570 De schorpioen volgt me eronder. 781 00:41:46,570 --> 00:41:48,880 De space invaders zijn komt dichter en dichter. 782 00:41:48,880 --> 00:41:54,020 783 00:41:54,020 --> 00:41:55,510 Hoe goed we kunnen doen tegen deze? 784 00:41:55,510 --> 00:41:58,640 785 00:41:58,640 --> 00:42:02,790 >> Een paar jaar geleden, Google had een project genaamd 786 00:42:02,790 --> 00:42:12,030 DeepMind, waar ze opgeleid een computer programma om te spelen Atari 2600 games. 787 00:42:12,030 --> 00:42:16,120 En als je denkt dat dit niet ernstig bedrijfsleven, de resultaten van hun studie 788 00:42:16,120 --> 00:42:19,920 werden gepubliceerd in Nature, dus ongeveer net zo goed een publicatie 789 00:42:19,920 --> 00:42:22,500 als u eventueel kunt krijgen. 790 00:42:22,500 --> 00:42:24,340 En hier is hoe goed ze uitgevoerd. 791 00:42:24,340 --> 00:42:29,220 >> Ze hebben een algoritme dat zat en keek gewoon het scherm ingangen. 792 00:42:29,220 --> 00:42:34,080 Het kreeg dan ook geen instructies over de regels van het spel. 793 00:42:34,080 --> 00:42:42,610 En het werd verondersteld om erachter te komen, baseerde haar score, hoe goed het deed. 794 00:42:42,610 --> 00:42:46,560 Dit is een systeem dat gebruikt iets riep versterking leren. 795 00:42:46,560 --> 00:42:48,380 Dat wil zeggen dat het leek op zijn score. 796 00:42:48,380 --> 00:42:51,620 En als het kreeg een goede score, het zei, Ik moet die dingen onthouden. 797 00:42:51,620 --> 00:42:53,310 En ik moeten die opnieuw doen. 798 00:42:53,310 --> 00:42:56,450 En als het heeft een slechte score, het zei, Ik moet die dingen niet meer doen. 799 00:42:56,450 --> 00:42:59,750 800 00:42:59,750 --> 00:43:03,430 >> Dit is de prestatie van die geschoold stelsels 801 00:43:03,430 --> 00:43:07,490 mogen spelen voor een paar uur op elk spel, 802 00:43:07,490 --> 00:43:12,490 vergeleken met professionele gamers. 803 00:43:12,490 --> 00:43:19,670 Dus voor alle games die zijn aan de linkerkant van deze lijn, 804 00:43:19,670 --> 00:43:25,920 deze zelf-opgeleide computerprogramma presteerde beter dan de professionele gamers. 805 00:43:25,920 --> 00:43:29,690 En voor alles aan de rechts, de professionele gamers 806 00:43:29,690 --> 00:43:30,920 nog het beste. 807 00:43:30,920 --> 00:43:34,040 808 00:43:34,040 --> 00:43:36,850 Voor iets dat wist niets over de regels, dat 809 00:43:36,850 --> 00:43:43,020 wist niets over de structuur van de games, is dit indrukwekkende prestatie. 810 00:43:43,020 --> 00:43:45,660 En dit is wat we kunnen doen vandaag. 811 00:43:45,660 --> 00:43:50,239 >> Oké, zeg je, maar als we denken over AI in games, 812 00:43:50,239 --> 00:43:52,530 Normaal gesproken zijn we denken over de dingen die we kunnen eigenlijk 813 00:43:52,530 --> 00:43:54,180 gaan zitten en te spelen tegen. 814 00:43:54,180 --> 00:43:58,760 Als ik ga zitten en ik speel StarCraft, of ik speel gratis Sieve, 815 00:43:58,760 --> 00:44:01,870 de computer tegenstander is de persoon het beheersen van de Zerg, 816 00:44:01,870 --> 00:44:06,770 of regelen andere beschaving. 817 00:44:06,770 --> 00:44:11,920 Hoe doen die spelers eigenlijk hun bewegingen vinden? 818 00:44:11,920 --> 00:44:18,810 >> Nou, zijn deze games gestructureerd veel op dezelfde manier als onze bordspellen, 819 00:44:18,810 --> 00:44:22,250 deze games dat we gezamenlijk noemen vier X games, 820 00:44:22,250 --> 00:44:26,040 verkennen, expand-- vergeet degenen. 821 00:44:26,040 --> 00:44:26,980 Wat zijn dat? 822 00:44:26,980 --> 00:44:32,150 Verkennen, uit te breiden en te blussen, Ik denk dat is de laatste. 823 00:44:32,150 --> 00:44:36,060 Maar ze zijn in feite exploratie en heers spelen. 824 00:44:36,060 --> 00:44:41,020 Kenmerkend is dat de computer tegenstander Er is beperkte informatie. 825 00:44:41,020 --> 00:44:45,486 Ze weten niet precies wat er is er achter dat de mist van de oorlog. 826 00:44:45,486 --> 00:44:47,735 Ze niet krijgen om te zien wat je hebt in je inventaris. 827 00:44:47,735 --> 00:44:50,240 828 00:44:50,240 --> 00:44:52,800 >> Er is een omgeving die is dynamisch. 829 00:44:52,800 --> 00:44:56,180 Alles is aan het veranderen de hele tijd. 830 00:44:56,180 --> 00:45:00,290 Je krijgt niet om te zitten en wachten om uw verhuizing te nemen. 831 00:45:00,290 --> 00:45:02,810 Maar de meeste dingen zijn nog steeds discreet. 832 00:45:02,810 --> 00:45:04,200 Ik moet mijn stad hier plaatsen. 833 00:45:04,200 --> 00:45:06,750 Of moet ik mijn stad hier plaatsen. 834 00:45:06,750 --> 00:45:08,950 En alles is deterministisch. 835 00:45:08,950 --> 00:45:14,660 Als ik zeg, beweeg mijn eenheid hier, mijn eenheid beweegt hier, tenzij een obstakel plotseling 836 00:45:14,660 --> 00:45:17,700 in het spel komt. 837 00:45:17,700 --> 00:45:21,610 Nu, dat is niet alles computer spellen die er vandaag de dag. 838 00:45:21,610 --> 00:45:27,320 >> Als ik ga en ik speel een eerste type persoon spel, iets als Thief of Fallout 839 00:45:27,320 --> 00:45:33,350 of Skyrim, of Halo, nu Ik heb computer tegenstanders 840 00:45:33,350 --> 00:45:37,860 dat zijn er uit die moeten een heel andere situatie. 841 00:45:37,860 --> 00:45:40,020 Ze hebben wederom beperkte informatie. 842 00:45:40,020 --> 00:45:43,420 Ze kunnen alleen een zien bepaalde gezichtsveld. 843 00:45:43,420 --> 00:45:45,180 De omgeving is nog steeds dynamisch. 844 00:45:45,180 --> 00:45:48,280 Dingen veranderen de hele tijd. 845 00:45:48,280 --> 00:45:52,300 >> Maar nu heb ik een veel meer continue actie ruimte. 846 00:45:52,300 --> 00:45:57,170 Ik kan gewoon worden gluren een beetje uit de deuropening. 847 00:45:57,170 --> 00:46:00,650 En enkele spelletjes, mijn acties zijn stochastisch. 848 00:46:00,650 --> 00:46:04,590 Ik krijg om te proberen te springen over die muur, maar ik heb een kans op falen. 849 00:46:04,590 --> 00:46:08,280 850 00:46:08,280 --> 00:46:14,550 Deze soorten games worden steeds dichterbij en dichter bij de soorten besturingen 851 00:46:14,550 --> 00:46:17,330 dat wij bouwen in de robotica. 852 00:46:17,330 --> 00:46:21,050 >> In robotica, moeten we aannemen dat we beperkte informatie. 853 00:46:21,050 --> 00:46:23,070 We hebben sensoren die vertel ons over de hele wereld. 854 00:46:23,070 --> 00:46:25,860 We hebben een altijd veranderende, dynamische omgeving. 855 00:46:25,860 --> 00:46:30,440 We hebben een wereld waarin ruimte is continue, in plaats van discrete. 856 00:46:30,440 --> 00:46:36,260 En onze handelingen, als we proberen ze hebben een kans op falen. 857 00:46:36,260 --> 00:46:40,960 En in feite, moderne spel controllers voor uw Halo tegenstander, 858 00:46:40,960 --> 00:46:48,690 of voor degenen NPCs in Skyrim, in principe lopen kleine robotica architecturen. 859 00:46:48,690 --> 00:46:50,380 >> Ze voelen de wereld. 860 00:46:50,380 --> 00:46:52,910 Ze bouwen een model van de wereld. 861 00:46:52,910 --> 00:46:57,950 Ze berekenen op basis van een reeks doelen die ze willen bereiken. 862 00:46:57,950 --> 00:47:03,110 Ze zijn van plan acties gebaseerd op wat ze weten. 863 00:47:03,110 --> 00:47:07,940 En dat zijn precies dezelfde soort van systemen die wij bouwen in de robotica. 864 00:47:07,940 --> 00:47:11,420 Dus deze architecturen, om breng dit weer bij elkaar, 865 00:47:11,420 --> 00:47:14,500 zijn vaak dezelfde. 866 00:47:14,500 --> 00:47:16,340 >> Dus laten we kijken of we dat kunnen zien. 867 00:47:16,340 --> 00:47:19,210 Laten we teruggaan naar onze tic-tac-teen voorbeeld. 868 00:47:19,210 --> 00:47:22,690 En ik ga een paar vragen mijn postdocs te komen en me helpen. 869 00:47:22,690 --> 00:47:26,970 Dus Chen Ming en Alessandro, en Olivier, als jullie zouden komen. 870 00:47:26,970 --> 00:47:32,080 871 00:47:32,080 --> 00:47:35,440 En ik ga nodig een paar vrijwilligers 872 00:47:35,440 --> 00:47:37,590 >> OK, een hand op rechts zag ik daar in het midden. 873 00:47:37,590 --> 00:47:39,965 Laat me nog één iemand verder in de rug misschien. 874 00:47:39,965 --> 00:47:40,881 Oké, daar. 875 00:47:40,881 --> 00:47:41,490 Kom op maximaal. 876 00:47:41,490 --> 00:47:44,190 877 00:47:44,190 --> 00:47:45,335 Prima. 878 00:47:45,335 --> 00:47:49,490 Dus laten we dat klep naar beneden. 879 00:47:49,490 --> 00:48:03,700 En als jullie recht zou komen terug rond hier voor mij, fantastisch. 880 00:48:03,700 --> 00:48:06,580 >> Dus dit is een robot genaamd Baxter. 881 00:48:06,580 --> 00:48:10,880 En Baxter is een robot die een commercieel platform, ontworpen 882 00:48:10,880 --> 00:48:13,030 door een bedrijf genaamd Rethink. 883 00:48:13,030 --> 00:48:16,580 En deze robot is ontworpen voor kleinschalige productie. 884 00:48:16,580 --> 00:48:19,265 Maar vandaag gaan we gebruik het om tic-tac-teen spelen. 885 00:48:19,265 --> 00:48:21,930 886 00:48:21,930 --> 00:48:27,150 Nu, deze robot is ook iets Dat is vrij uniek. 887 00:48:27,150 --> 00:48:32,950 Want als ik ergens stonden dicht bij een standaard factory automation 888 00:48:32,950 --> 00:48:39,580 systeem, zou ik zeer ernstig zijn gevaar loopt gewond. 889 00:48:39,580 --> 00:48:45,600 >> Baxter is echter ontworpen om relatief veilig om te interageren met. 890 00:48:45,600 --> 00:48:48,680 En dus ik kan duwen op deze robot. 891 00:48:48,680 --> 00:48:52,350 En je kunt zien is het een beetje bit flexibel als het beweegt. 892 00:48:52,350 --> 00:48:57,250 En ik kan het verplaatsen waar ik zou het leuk vinden om te gaan. 893 00:48:57,250 --> 00:49:03,410 Nu in een normaal robotsysteem, zouden we een set van gewrichten hier 894 00:49:03,410 --> 00:49:07,970 dat zou direct zijn reageert op commando stand. 895 00:49:07,970 --> 00:49:13,180 En ze zouden niet per se zorg als ze bewegen door de open lucht, 896 00:49:13,180 --> 00:49:15,555 of indien zij verhuizen door mijn ribbenkast. 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 En meestal, als je hier met een industrieel systeem, 900 00:49:22,090 --> 00:49:23,400 zou je nergens in de buurt komen. 901 00:49:23,400 --> 00:49:26,280 Er zouden geel zijn veiligheid tape rondom het. 902 00:49:26,280 --> 00:49:28,310 Dit systeem heeft een lichtjes verschillend ontwerp 903 00:49:28,310 --> 00:49:32,130 vriendelijker en gemakkelijker voor mensen om te communiceren met, 904 00:49:32,130 --> 00:49:36,380 dat in elke verbinding, er is een bron. 905 00:49:36,380 --> 00:49:39,110 En in plaats van het regelen een exacte positie, 906 00:49:39,110 --> 00:49:43,110 controleren we een zekere torque, een zekere hoeveelheid kracht, 907 00:49:43,110 --> 00:49:45,874 dat we zouden graag op dat de lente. 908 00:49:45,874 --> 00:49:47,790 Oké, dus laat me neem hier onze vrijwilligers. 909 00:49:47,790 --> 00:49:48,540 Hoi wat is je naam? 910 00:49:48,540 --> 00:49:49,010 >> Publiek: Louis. 911 00:49:49,010 --> 00:49:49,635 >> SPEAKER: Louis. 912 00:49:49,635 --> 00:49:50,490 Fijn om je te zien. 913 00:49:50,490 --> 00:49:50,990 En? 914 00:49:50,990 --> 00:49:51,610 >> Publiek: David. 915 00:49:51,610 --> 00:49:51,960 >> SPEAKER: David. 916 00:49:51,960 --> 00:49:52,550 Leuk je te ontmoeten. 917 00:49:52,550 --> 00:49:54,508 Als jullie zou wachten hier voor een tweede, 918 00:49:54,508 --> 00:49:56,420 Ik ga u een kans om dit te doen. 919 00:49:56,420 --> 00:50:00,610 Dus deze robot, als je komen en als je duw op, 920 00:50:00,610 --> 00:50:03,780 zul je zien dat het beweegt een beetje. 921 00:50:03,780 --> 00:50:06,349 En als je het pak rechts hier op de pols net 922 00:50:06,349 --> 00:50:09,390 boven de plaats waar de knoppen zijn, is het lijkt alsof je moet grijpen de knoppen, 923 00:50:09,390 --> 00:50:13,100 maar pak recht boven het in plaats daarvan, zult u kunnen heel voorzichtig manipuleren 924 00:50:13,100 --> 00:50:14,545 door de ruimte. 925 00:50:14,545 --> 00:50:15,920 Louis, wilt u het eens proberen? 926 00:50:15,920 --> 00:50:19,465 Dus geef het gewoon een beetje duwen beginnen. 927 00:50:19,465 --> 00:50:23,190 En dan als je je vingers daar en vasthouden aan het, 928 00:50:23,190 --> 00:50:24,807 want het zal dan verder voor u. 929 00:50:24,807 --> 00:50:27,824 930 00:50:27,824 --> 00:50:29,365 Oké, wil je het eens proberen? 931 00:50:29,365 --> 00:50:29,980 Kom op maximaal. 932 00:50:29,980 --> 00:50:32,300 Dus geef het gewoon een zachte duwen daar beginnen. 933 00:50:32,300 --> 00:50:33,820 Je kunt voelen hoe het is. 934 00:50:33,820 --> 00:50:40,060 En dan als je het pak daar, zult u in staat om te manoeuvreren rond. 935 00:50:40,060 --> 00:50:41,280 >> OK. 936 00:50:41,280 --> 00:50:47,360 Zo typisch, dit soort van een robot zou worden gebruikt voor kleinschalige productie. 937 00:50:47,360 --> 00:50:50,980 En ik ga deze arm gewoon verder naar beneden uit de weg een beetje hier. 938 00:50:50,980 --> 00:50:55,750 Maar vandaag, we gaan het gebruiken Hetzelfde tic-tac-teen te spelen systeem 939 00:50:55,750 --> 00:50:59,520 gebaseerd op minimax die we eerder gebouwd. 940 00:50:59,520 --> 00:51:00,549 OK? 941 00:51:00,549 --> 00:51:02,340 Dus, jullie zijn elk gaat om een ​​spel te spelen. 942 00:51:02,340 --> 00:51:04,210 Louis, je gaat naar de eerste te zijn. 943 00:51:04,210 --> 00:51:05,920 Laat me gewoon houden hier voor een tweede. 944 00:51:05,920 --> 00:51:10,949 Ik ga heb je recht staan hier, net zodat iedereen kan je zien. 945 00:51:10,949 --> 00:51:11,990 Zijn jullie opgezet hier? 946 00:51:11,990 --> 00:51:13,120 >> ROBOT: Welkom. 947 00:51:13,120 --> 00:51:15,910 Laten we spelen tic-tac-teen. 948 00:51:15,910 --> 00:51:20,860 Gebruik uw token niet begrijpen voordat Ik zeg dat het jouw beurt is. 949 00:51:20,860 --> 00:51:22,050 Ik begin het spel. 950 00:51:22,050 --> 00:51:27,900 951 00:51:27,900 --> 00:51:28,750 Het is mijn beurt. 952 00:51:28,750 --> 00:51:47,002 953 00:51:47,002 --> 00:51:50,210 SPEAKER: Nu, als je zou een van te nemen uw stukken en ga je gang en plaats. 954 00:51:50,210 --> 00:51:51,446 ROBOT: Het is jouw beurt. 955 00:51:51,446 --> 00:51:53,430 [GELACH] 956 00:51:53,430 --> 00:51:54,836 Het is mijn beurt. 957 00:51:54,836 --> 00:51:56,820 [GELACH] 958 00:51:56,820 --> 00:52:12,196 959 00:52:12,196 --> 00:52:15,680 [GELACH] 960 00:52:15,680 --> 00:52:16,570 Het is jouw beurt. 961 00:52:16,570 --> 00:52:21,397 962 00:52:21,397 --> 00:52:23,688 SPEAKER: Het menselijk ras is reken op u hier, Louis. 963 00:52:23,688 --> 00:52:27,440 964 00:52:27,440 --> 00:52:28,350 >> ROBOT: Het is mijn beurt. 965 00:52:28,350 --> 00:52:44,810 966 00:52:44,810 --> 00:52:47,015 >> SPEAKER: Dus Baxter hier met succes geblokkeerd. 967 00:52:47,015 --> 00:52:49,670 968 00:52:49,670 --> 00:52:52,480 >> ROBOT: Het is jouw beurt. 969 00:52:52,480 --> 00:52:53,360 Het is mijn beurt. 970 00:52:53,360 --> 00:53:14,730 971 00:53:14,730 --> 00:53:16,810 Het is jouw beurt. 972 00:53:16,810 --> 00:53:17,760 Het is mijn beurt. 973 00:53:17,760 --> 00:53:21,330 974 00:53:21,330 --> 00:53:23,830 SPEAKER: En we laten Baxter voltooien van zijn laatste zet hier. 975 00:53:23,830 --> 00:53:36,622 976 00:53:36,622 --> 00:53:39,090 >> [GELACH] 977 00:53:39,090 --> 00:53:40,480 >> ROBOT: Dat is een gelijkspel. 978 00:53:40,480 --> 00:53:42,030 Ik zal de volgende keer winnen. 979 00:53:42,030 --> 00:53:43,365 >> [GELACH] 980 00:53:43,365 --> 00:53:45,210 >> SPEAKER: Oké, heel erg bedankt, Louis. 981 00:53:45,210 --> 00:53:46,094 Dankjewel. 982 00:53:46,094 --> 00:53:46,980 U kunt op deze manier te gaan. 983 00:53:46,980 --> 00:53:49,759 >> ROBOT: Ik begin het spel. 984 00:53:49,759 --> 00:53:51,800 SPEAKER: Dus laat me uitleggen om je nog een beetje 985 00:53:51,800 --> 00:53:55,410 bit voordat wij krijgen onze rematch hier. 986 00:53:55,410 --> 00:53:57,200 Wat er precies gebeurt? 987 00:53:57,200 --> 00:53:59,430 Zodat de robot heeft een camera up top hier. 988 00:53:59,430 --> 00:54:01,330 En het kijken neer op het bord. 989 00:54:01,330 --> 00:54:04,470 En het zien van de vraag of het heeft een rode O of een blauwe 990 00:54:04,470 --> 00:54:10,450 en witte X. Aangezien die krijgen die op de boord, dat is eigenlijk dezelfde ingang 991 00:54:10,450 --> 00:54:13,890 dat we zouden lezen vanaf onze datastructuur van ons scherm. 992 00:54:13,890 --> 00:54:17,290 Het waarop dezelfde minimax algoritme te zijn 993 00:54:17,290 --> 00:54:21,010 kunnen vinden waar te plaats een goed teken. 994 00:54:21,010 --> 00:54:24,820 >> En dan zijn we het geven van een commando over waar we zouden graag een teken te worden geplaatst. 995 00:54:24,820 --> 00:54:26,120 De arm beweegt uit. 996 00:54:26,120 --> 00:54:31,750 Het gebruik van een vacuümgrijper toepassing sommige zuigkracht die houten stuk, 997 00:54:31,750 --> 00:54:35,240 pick it up, verplaatsen naar de juiste spot, en vervolgens de zuigkracht los 998 00:54:35,240 --> 00:54:36,950 en vallen. 999 00:54:36,950 --> 00:54:38,990 Oké, we gaan te geven nog een schot 1000 00:54:38,990 --> 00:54:40,930 met een iets slimmer speler in. 1001 00:54:40,930 --> 00:54:42,290 Ben je klaar? 1002 00:54:42,290 --> 00:54:46,150 Oké, als je zou gelijk staan hier en geef a-- blijken deze manier 1003 00:54:46,150 --> 00:54:47,955 zodat u kunt zien iedereen. 1004 00:54:47,955 --> 00:54:48,830 En dan [onverstaanbaar]. 1005 00:54:48,830 --> 00:54:49,330 >> ROBOT: Het is mijn beurt. 1006 00:54:49,330 --> 00:54:50,455 >> SPEAKER: Baxter zal beginnen. 1007 00:54:50,455 --> 00:55:10,750 1008 00:55:10,750 --> 00:55:11,730 Het is jouw beurt. 1009 00:55:11,730 --> 00:55:16,490 1010 00:55:16,490 --> 00:55:17,520 Het is mijn beurt. 1011 00:55:17,520 --> 00:55:38,740 1012 00:55:38,740 --> 00:55:39,690 Het is jouw beurt. 1013 00:55:39,690 --> 00:55:46,330 1014 00:55:46,330 --> 00:55:47,165 Het is mijn beurt. 1015 00:55:47,165 --> 00:56:01,252 1016 00:56:01,252 --> 00:56:06,192 >> [GELACH] 1017 00:56:06,192 --> 00:56:08,542 >> SPEAKER: [FLUISTEREN] Net laat hem verder te gaan en te winnen. 1018 00:56:08,542 --> 00:56:09,500 ROBOT: Het is jouw beurt. 1019 00:56:09,500 --> 00:56:15,099 1020 00:56:15,099 --> 00:56:15,890 SPEAKER: Dat is OK. 1021 00:56:15,890 --> 00:56:20,390 1022 00:56:20,390 --> 00:56:21,360 >> ROBOT: Het is mijn beurt. 1023 00:56:21,360 --> 00:56:24,825 1024 00:56:24,825 --> 00:56:26,805 >> [GELACH] 1025 00:56:26,805 --> 00:56:42,650 1026 00:56:42,650 --> 00:56:43,510 >> Ik win. 1027 00:56:43,510 --> 00:56:45,620 >> [GELACH] 1028 00:56:45,620 --> 00:56:46,595 >> Ik begin het spel. 1029 00:56:46,595 --> 00:56:48,261 >> SPEAKER: Oké, dank u zeer. 1030 00:56:48,261 --> 00:56:50,180 1031 00:56:50,180 --> 00:56:55,590 Oké, ik denk dat we tijd hebben voor nog een uitstekende tic-tac-teen speler, 1032 00:56:55,590 --> 00:57:00,490 iemand die dit ding kan maken aan overeenkomen, wie weet wat ze doen. 1033 00:57:00,490 --> 00:57:03,010 >> [GELACH] 1034 00:57:03,010 --> 00:57:05,560 >> Wie gaat ons kampioen hier zijn? 1035 00:57:05,560 --> 00:57:08,110 Oké, je vrienden vrijwillig u. 1036 00:57:08,110 --> 00:57:11,190 Dat is goed genoeg voor mij. 1037 00:57:11,190 --> 00:57:12,194 Vertel me nog eens je naam. 1038 00:57:12,194 --> 00:57:12,860 Publiek: Tamir. 1039 00:57:12,860 --> 00:57:14,193 SPEAKER: Tamir, leuk je te zien. 1040 00:57:14,193 --> 00:57:19,270 Oké, nogmaals, we gaan je recht hier, dus iedereen kan je zien. 1041 00:57:19,270 --> 00:57:22,070 U bent onze vertegenwoordiger in deze wedstrijd nu. 1042 00:57:22,070 --> 00:57:24,540 Baxter is een en oh en oh. 1043 00:57:24,540 --> 00:57:26,300 Of sorry, een oh en één. 1044 00:57:26,300 --> 00:57:27,490 En het is aan jou hier. 1045 00:57:27,490 --> 00:57:29,340 Baxter krijgt om eerst te verplaatsen, dat wel. 1046 00:57:29,340 --> 00:57:30,435 Zo. 1047 00:57:30,435 --> 00:57:31,310 ROBOT: Het is mijn beurt. 1048 00:57:31,310 --> 00:57:45,226 1049 00:57:45,226 --> 00:57:48,208 >> [GELACH] 1050 00:57:48,208 --> 00:57:52,720 1051 00:57:52,720 --> 00:57:55,780 >> Het is jouw beurt. 1052 00:57:55,780 --> 00:57:56,845 Het is mijn beurt. 1053 00:57:56,845 --> 00:58:18,130 1054 00:58:18,130 --> 00:58:18,965 Het is jouw beurt. 1055 00:58:18,965 --> 00:58:28,751 1056 00:58:28,751 --> 00:58:30,248 Het is mijn beurt. 1057 00:58:30,248 --> 00:58:51,210 1058 00:58:51,210 --> 00:58:52,160 Het is jouw beurt. 1059 00:58:52,160 --> 00:59:00,854 1060 00:59:00,854 --> 00:59:03,365 >> [GELACH] 1061 00:59:03,365 --> 00:59:04,240 ROBOT: Het is mijn beurt. 1062 00:59:04,240 --> 00:59:06,930 SPEAKER: Het is een stuk moeilijker als je staat hier op, mensen. 1063 00:59:06,930 --> 00:59:19,400 1064 00:59:19,400 --> 00:59:21,840 [GELACH] 1065 00:59:21,840 --> 00:59:26,730 1066 00:59:26,730 --> 00:59:29,054 ROBOT: Jullie mensen zijn zo makkelijk te verslaan. 1067 00:59:29,054 --> 00:59:30,803 [Gelach en applaus] 1068 00:59:30,803 --> 00:59:31,886 SPEAKER: Heel erg bedankt. 1069 00:59:31,886 --> 00:59:34,692 ROBOT: ik win. 1070 00:59:34,692 --> 00:59:35,400 Ik begin het spel. 1071 00:59:35,400 --> 00:59:39,500 >> SPEAKER: Oké, dus bedankt zeer veel te Olivier, en Alessandro, 1072 00:59:39,500 --> 00:59:41,616 en Chen Ming. 1073 00:59:41,616 --> 00:59:45,600 >> [APPLAUS] 1074 00:59:45,600 --> 00:59:47,040 >> Ik wil nog een laatste punt te maken. 1075 00:59:47,040 --> 00:59:51,630 Dus Baxter aan het eindigen daar bedrogen. 1076 00:59:51,630 --> 00:59:54,160 1077 00:59:54,160 --> 00:59:56,310 En dat was onverwacht. 1078 00:59:56,310 --> 01:00:00,440 Één van de fantastische dingen over AI is dat we 1079 01:00:00,440 --> 01:00:05,070 werk te doen bij de KI, zodat we kunnen bouwen echt interessant en intelligente 1080 01:00:05,070 --> 01:00:06,930 inrichtingen. 1081 01:00:06,930 --> 01:00:10,130 Maar werken we ook doen in AI want het vertelt ons iets 1082 01:00:10,130 --> 01:00:13,940 over hoe mensen zijn intelligent. 1083 01:00:13,940 --> 01:00:17,280 >> Een van de favoriete studies uit mijn lab 1084 01:00:17,280 --> 01:00:23,660 kijken wat gebeurt wanneer machines onverwacht bedriegen. 1085 01:00:23,660 --> 01:00:27,070 We deden dit aanvankelijk niet met Baxter spelen tic-tac-teen, 1086 01:00:27,070 --> 01:00:30,340 maar met een kleinere robot genaamd Nao, die rock-paper-scissors gespeeld. 1087 01:00:30,340 --> 01:00:33,010 1088 01:00:33,010 --> 01:00:35,800 En soms na spelen veel en veel 1089 01:00:35,800 --> 01:00:41,580 van saaie rock-paper-scissors games, de robot zou gooien een gebaar, 1090 01:00:41,580 --> 01:00:48,616 verliezen, en dan plotseling veranderen haar gebaar en zeg, ik win. 1091 01:00:48,616 --> 01:00:50,480 >> [GELACH] 1092 01:00:50,480 --> 01:00:56,090 >> Nu, soms willen we ook de robot, net als een controle, gooi een gebaar, 1093 01:00:56,090 --> 01:01:01,270 winnen, en verander de gebaar te verliezen, gooi de wedstrijd, 1094 01:01:01,270 --> 01:01:04,070 bedriegen met het oog te verliezen. 1095 01:01:04,070 --> 01:01:07,540 En dat is lang niet zo overtuigend. 1096 01:01:07,540 --> 01:01:09,890 De robot die cheats om mensen te winnen 1097 01:01:09,890 --> 01:01:14,660 reageren alsof het uit om ze te krijgen, alsof het 1098 01:01:14,660 --> 01:01:17,690 is actief op zoek naar hun vernietiging. 1099 01:01:17,690 --> 01:01:19,210 >> [GELACH] 1100 01:01:19,210 --> 01:01:20,990 >> Het wordt een agent. 1101 01:01:20,990 --> 01:01:21,840 Het is als een persoon. 1102 01:01:21,840 --> 01:01:23,970 Heeft het geloof en intentie. 1103 01:01:23,970 --> 01:01:27,470 En het is niet goed voornemen. 1104 01:01:27,470 --> 01:01:33,790 En de robot die gooit de spel is gewoon niet goed. 1105 01:01:33,790 --> 01:01:36,990 Het is gewoon een gebroken apparaat. 1106 01:01:36,990 --> 01:01:41,405 Laat ik je een paar voorbeelden van dat van een paar van onze deelnemers. 1107 01:01:41,405 --> 01:01:43,990 1108 01:01:43,990 --> 01:01:45,600 Dus hier is vals spelen om te verliezen. 1109 01:01:45,600 --> 01:01:46,266 >> [VIDEO AFSPELEN] 1110 01:01:46,266 --> 01:01:47,010 - [Onverstaanbaar] winnen. 1111 01:01:47,010 --> 01:01:49,550 Laten we spelen. 1112 01:01:49,550 --> 01:01:50,538 >> -Wacht wat? 1113 01:01:50,538 --> 01:01:54,490 1114 01:01:54,490 --> 01:01:55,352 >> - [Onverstaanbaar] winnen. 1115 01:01:55,352 --> 01:01:58,280 Laten we spelen. 1116 01:01:58,280 --> 01:01:59,400 >> [Onverstaanbaar] winnen. 1117 01:01:59,400 --> 01:02:02,290 Laten we spelen. 1118 01:02:02,290 --> 01:02:05,490 >> SPEAKER: En hier is vals spelen om te winnen. 1119 01:02:05,490 --> 01:02:06,438 >> Ja, ik win. 1120 01:02:06,438 --> 01:02:07,394 Laten we spelen. 1121 01:02:07,394 --> 01:02:08,828 >> -Je Kan dat niet doen. 1122 01:02:08,828 --> 01:02:10,740 >> [GELACH] 1123 01:02:10,740 --> 01:02:12,174 1124 01:02:12,174 --> 01:02:13,979 >> Ja, ik win. 1125 01:02:13,979 --> 01:02:14,520 -Je speelde vals. 1126 01:02:14,520 --> 01:02:17,990 1127 01:02:17,990 --> 01:02:20,010 Je bedrogen nu. 1128 01:02:20,010 --> 01:02:21,140 >> Ja, ik win. 1129 01:02:21,140 --> 01:02:22,940 >> Hé, jij bedrieger. 1130 01:02:22,940 --> 01:02:26,670 U te bedriegen, super cheat. 1131 01:02:26,670 --> 01:02:27,650 >> [END AFSPELEN] 1132 01:02:27,650 --> 01:02:31,130 >> SPEAKER: Deze verschillende reacties snel 1133 01:02:31,130 --> 01:02:34,890 veranderen onze perceptie van het apparaat. 1134 01:02:34,890 --> 01:02:36,780 Betekent dit dat we bewust bouwen 1135 01:02:36,780 --> 01:02:40,370 machines die bedriegen, want dat is de beste techniek die we kunnen doen? 1136 01:02:40,370 --> 01:02:44,680 Nee, maar het vertelt ons iets echt interessant over mensen. 1137 01:02:44,680 --> 01:02:49,710 Dat ding dat jij en cheats steelt je overwinning, dat is 1138 01:02:49,710 --> 01:02:53,660 iets dat leeft, dat is animeren, dat is uit om u te krijgen. 1139 01:02:53,660 --> 01:02:54,680 Het heeft mentale toestand. 1140 01:02:54,680 --> 01:02:55,400 Heeft het geloof. 1141 01:02:55,400 --> 01:02:57,170 Het heeft de bedoeling. 1142 01:02:57,170 --> 01:03:01,540 >> Dat ding dat de handen van de spel voor u, dat is het niet. 1143 01:03:01,540 --> 01:03:04,670 Dat is gewoon niet goed. 1144 01:03:04,670 --> 01:03:08,900 Dit is in veel opzichten waarom het makkelijk om het spel te gooien met kinderen. 1145 01:03:08,900 --> 01:03:12,050 Maar als je probeert om ze te bedriegen en soort claimen overwinning 1146 01:03:12,050 --> 01:03:15,200 als, je weet wel, alleen maar om het te verkorten spel, zullen ze je pakken meteen. 1147 01:03:15,200 --> 01:03:19,040 1148 01:03:19,040 --> 01:03:23,140 Dit soort effecten die we zien dat uit AI, 1149 01:03:23,140 --> 01:03:26,490 ze leren ons veel over onszelf. 1150 01:03:26,490 --> 01:03:28,076 >> Oké, dat is het voor vandaag. 1151 01:03:28,076 --> 01:03:30,450 Hartelijk dank aan David en Harvard productieteam 1152 01:03:30,450 --> 01:03:32,350 voor naar beneden. 1153 01:03:32,350 --> 01:03:33,820 >> [APPLAUS] 1154 01:03:33,820 --> 01:03:36,760 1155 01:03:36,760 --> 01:03:41,840 >> We zien je voor een quiz, en dan voor een laatste lezing. 1156 01:03:41,840 --> 01:03:43,025 Een fijne dag verder. 1157 01:03:43,025 --> 01:03:44,965 >> [APPLAUS] 1158 01:03:44,965 --> 01:03:48,360 1159 01:03:48,360 --> 01:03:51,825 >> [Muziek] 1160 01:03:51,825 --> 01:03:54,950 DAVID J MALAN: Nou, waarschijnlijk moeten we om een ​​soort te introduceren van encryptie, 1161 01:03:54,950 --> 01:03:55,450 rechts? 1162 01:03:55,450 --> 01:03:58,650 Omdat dan de headers van Deze HTTP-verzoeken zal zijn 1163 01:03:58,650 --> 01:04:01,530 vervormd zodat iedereen proberen om uw verkeer snuiven 1164 01:04:01,530 --> 01:04:03,400 daadwerkelijk niet in staat zijn om ze te zien. 1165 01:04:03,400 --> 01:04:05,254 Dus wat is de oplossing voor dit probleem? 1166 01:04:05,254 --> 01:04:07,920 Nou, we moeten eigenlijk introduceren codering in de formule, 1167 01:04:07,920 --> 01:04:11,010 zodat wanneer die persoon verzenden van gegevens van A naar B, 1168 01:04:11,010 --> 01:04:12,390 we kunnen veilig send-- 1169 01:04:12,390 --> 01:04:14,590 >> [GELACH] 1170 01:04:14,590 --> 01:04:19,530 >> De informatie op een manier die de tegenstander kan niet, in feite, zien.