1 00:00:00,000 --> 00:00:01,924 >> [Prehrávanie hudby] 2 00:00:01,924 --> 00:00:10,600 3 00:00:10,600 --> 00:00:13,280 >> SPEAKER: Vitajte späť, všetci. 4 00:00:13,280 --> 00:00:15,440 To je CS50. 5 00:00:15,440 --> 00:00:21,040 A dnes, máme veľa zaujímavé veci hovoriť. 6 00:00:21,040 --> 00:00:25,500 Najprv však musím pripomenúť, vy z niekoľkých správnych vecí. 7 00:00:25,500 --> 00:00:30,160 Tento týždeň je jedným kvíz, streda alebo pre sekciu Yale 8 00:00:30,160 --> 00:00:32,940 v utorok a vo štvrtok, vo štvrtok. 9 00:00:32,940 --> 00:00:38,170 Existujú kvíz hodnotenie dnes večer na Yale, 5:30 až 7:00. 10 00:00:38,170 --> 00:00:40,030 Na Harvarde, že jeden včera zaznamenané. 11 00:00:40,030 --> 00:00:43,000 A každý môže sledovať že on-line. 12 00:00:43,000 --> 00:00:49,406 >> Aj tento týždeň, alebo začiatkom budúceho týždňa, máme náš posledný CS50 prednášku. 13 00:00:49,406 --> 00:00:51,450 [Stenu] Ja viem. 14 00:00:51,450 --> 00:00:54,140 To prišlo tak skoro. 15 00:00:54,140 --> 00:00:57,820 Yale študenti budú mať živý prednášať tu v právnickej fakulte 16 00:00:57,820 --> 00:00:59,920 hľadisko v piatok. 17 00:00:59,920 --> 00:01:01,140 K dispozícii bude tortu. 18 00:01:01,140 --> 00:01:05,570 Harvard študenti budú mať Posledná prednáška Sanders v pondelok. 19 00:01:05,570 --> 00:01:08,050 K dispozícii bude aj tortu. 20 00:01:08,050 --> 00:01:14,000 >> Aj tento týždeň v piatok, pre tých, ktorí z vás, ktorí sú na ceste do New Haven, 21 00:01:14,000 --> 00:01:15,740 máme CS50 Expo. 22 00:01:15,740 --> 00:01:18,850 Máme viac ako 30 rôzne skupiny registrované 23 00:01:18,850 --> 00:01:22,530 vám ukázať všetko, autonómnych plachetnice, 24 00:01:22,530 --> 00:01:27,170 pre systémy, ktoré uznávajú digitálne portréty, do počítača 25 00:01:27,170 --> 00:01:32,100 hudba a počítačovo produkoval hudbu. 26 00:01:32,100 --> 00:01:33,610 Takže prosím, pripojte sa k nám. 27 00:01:33,610 --> 00:01:36,460 Myslím, že to bude skvelý čas. 28 00:01:36,460 --> 00:01:40,320 >> Dnes sa však dostaneme k pokračovať v rozhovore o AI, 29 00:01:40,320 --> 00:01:43,150 o umelej inteligencii. 30 00:01:43,150 --> 00:01:46,070 A jedna z vecí, ktoré budeme sa dostať do dneška 31 00:01:46,070 --> 00:01:51,750 je predstava o tom, ako použiť AI riešiť problémy. 32 00:01:51,750 --> 00:01:54,690 A teraz, ako vždy, začnime s niečím jednoduchým. 33 00:01:54,690 --> 00:01:57,120 A ideme na začiatok s jednoduchej myšlienky. 34 00:01:57,120 --> 00:01:59,920 A to je pomocou vyhľadávania. 35 00:01:59,920 --> 00:02:06,990 >> Tak si predstavte na chvíľu, že som majú za úlohu, že musím hrať. 36 00:02:06,990 --> 00:02:11,970 A ja by som chcel mať túto úlohu automatizovaný nejaký softvérový agent. 37 00:02:11,970 --> 00:02:17,100 Predstavte si, že sa snažím si sadu letov z, povedzme, Boston 38 00:02:17,100 --> 00:02:20,040 do San Franciska. 39 00:02:20,040 --> 00:02:24,230 Mohol by som prejsť a ja som mohol použiť jeden z nádhernej on-line vyhľadávanie 40 00:02:24,230 --> 00:02:28,790 nástroja, ktorý sa chystá urobiť v podstate rovnaký proces, ktorý sme 41 00:02:28,790 --> 00:02:30,030 ísť na prechádzku do dneška. 42 00:02:30,030 --> 00:02:34,100 Ale ak ste nemali, že Nástroj, čo by ste urobil? 43 00:02:34,100 --> 00:02:37,570 >> No, mohol by ste vyzerať a vidieť a povedať, že som v Bostone. 44 00:02:37,570 --> 00:02:41,520 Aké lety sú k dispozícii? 45 00:02:41,520 --> 00:02:44,390 A teraz, možno mám tri Možné lety z Bostonu 46 00:02:44,390 --> 00:02:47,180 ktorý sa zmestí čas keď musím odísť. 47 00:02:47,180 --> 00:02:48,830 By som mohol letieť do Chicaga. 48 00:02:48,830 --> 00:02:50,130 Alebo by som mohol letieť do Miami. 49 00:02:50,130 --> 00:02:53,340 Alebo by som mohol letieť do New Yorku. 50 00:02:53,340 --> 00:02:56,980 Potom som mohol vyzerať z každého jeden z tých destinácie miest 51 00:02:56,980 --> 00:03:00,650 a premýšľať o tom, lokalitách Mohol by som možno dosiahnuť 52 00:03:00,650 --> 00:03:03,020 z každého z týchto jednotlivých miest. 53 00:03:03,020 --> 00:03:07,390 >> Takže možno z Chicaga, môžem dostať priamy let do San Franciska. 54 00:03:07,390 --> 00:03:09,550 To je skvelé. 55 00:03:09,550 --> 00:03:12,360 Alebo by som mohol dostať rokov do Denveru. 56 00:03:12,360 --> 00:03:16,970 Teraz, možno, že let do San Francisca je ideálnym riešením pre mňa, 57 00:03:16,970 --> 00:03:19,530 ale možno nie. 58 00:03:19,530 --> 00:03:22,180 Možno Hľadám niečo to je trochu niečo lacnejšie 59 00:03:22,180 --> 00:03:24,920 alebo trochu lepšie pre môj plán. 60 00:03:24,920 --> 00:03:29,197 A tak som sa mohol pozrieť na to, čo ostatní možnosti by mohlo byť vonku. 61 00:03:29,197 --> 00:03:30,280 Tak som sa mohol pozerať na Denver. 62 00:03:30,280 --> 00:03:33,870 A z Denveru, no, možno Môžem rokov do Austinu. 63 00:03:33,870 --> 00:03:37,080 A z Austinu, možno by som sa dostať Let do Phoenixu, a Phoenix 64 00:03:37,080 --> 00:03:40,190 do San Franciska. 65 00:03:40,190 --> 00:03:42,730 Teraz som neskončil. 66 00:03:42,730 --> 00:03:45,640 Vzhľadom k tomu, možno je tu priamy let z New Yorku 67 00:03:45,640 --> 00:03:47,850 do San Franciska, ktorý je ideálny pre mňa. 68 00:03:47,850 --> 00:03:53,354 Alebo možno je tu letu z Miami cez Denver, že je to oveľa lacnejšie. 69 00:03:53,354 --> 00:03:54,270 Takže som ešte musieť ísť. 70 00:03:54,270 --> 00:03:58,200 A stále sa pozrieť na všetky tie, mestá, ktoré som ešte preskúmaný. 71 00:03:58,200 --> 00:04:04,220 Musím vyčerpávajúcom skontrolovať všetky možnosti, že by som mohol mať. 72 00:04:04,220 --> 00:04:09,610 >> Takže z New Yorku, možno by som sa dostať Let do Nashvillu, a od Nashville 73 00:04:09,610 --> 00:04:10,336 do Austine. 74 00:04:10,336 --> 00:04:11,460 A potom viem, kde som. 75 00:04:11,460 --> 00:04:14,252 A potom viem, z Austinu, môžem pozrite sa na Phoenix a Phoenix 76 00:04:14,252 --> 00:04:14,960 do San Franciska. 77 00:04:14,960 --> 00:04:18,240 78 00:04:18,240 --> 00:04:22,830 Ak by som letieť najprv do Miami, aj keď, Možno, že môžem dostať z Miami rokov 79 00:04:22,830 --> 00:04:25,080 do Nashvillu, alebo z Miami do Austinu. 80 00:04:25,080 --> 00:04:27,950 81 00:04:27,950 --> 00:04:30,860 >> A teraz som sa snažil všetko z možností. 82 00:04:30,860 --> 00:04:36,310 Ja som vybudoval tento graf, ktorý Ukazuje mi všetky z možných ciest 83 00:04:36,310 --> 00:04:37,790 že by som mohol byť schopný prijať. 84 00:04:37,790 --> 00:04:40,510 85 00:04:40,510 --> 00:04:43,640 Keď sme sa predstavujú títo druhy problémov, 86 00:04:43,640 --> 00:04:47,870 nebudeme reprezentovať je výslovne ako tento graf, 87 00:04:47,870 --> 00:04:51,590 preto, že graf nepredstavuje histórie, kde sme preč. 88 00:04:51,590 --> 00:04:55,260 S vedomím, že som letel z Phoenix do San Franciska 89 00:04:55,260 --> 00:05:01,690 sa mi to povedať, či som prišiel cez Nashville, alebo prostredníctvom Denveri, alebo cez Miami. 90 00:05:01,690 --> 00:05:06,430 >> Takže to, čo budem robiť, namiesto toho je Vezmem rovnaký problém, 91 00:05:06,430 --> 00:05:09,140 a budem zastupovať ju ako strom. 92 00:05:09,140 --> 00:05:14,300 A na koreň stromu, u top, dám miesto, ktoré som začal, 93 00:05:14,300 --> 00:05:16,590 Boston. 94 00:05:16,590 --> 00:05:19,310 A z Bostonu, pozriem sa na všetky možné umiestnenia 95 00:05:19,310 --> 00:05:20,380 že môžem cestovať. 96 00:05:20,380 --> 00:05:25,480 No, v tomto prípade, mal som tri, Chicago, New York, a Miami. 97 00:05:25,480 --> 00:05:29,850 A potom budem skúmať každý z tieto deti vo stromu. 98 00:05:29,850 --> 00:05:32,690 >> Z Chicaga, som videl, že som mal dva lety. 99 00:05:32,690 --> 00:05:35,940 Mohol by som letieť priamo do San Francisco alebo do Denveru. 100 00:05:35,940 --> 00:05:37,740 Teraz San Francisco, to je môj cieľ. 101 00:05:37,740 --> 00:05:39,790 To je môj cieľ. 102 00:05:39,790 --> 00:05:42,220 To bude list tohto stromu. 103 00:05:42,220 --> 00:05:45,340 To znamená, že ja nikdy ísť Niekde po San Francisco. 104 00:05:45,340 --> 00:05:47,850 105 00:05:47,850 --> 00:05:50,340 Z Denveru, aj keď, Môžem letieť z Denveru 106 00:05:50,340 --> 00:05:54,220 Austin, Austin do Phoenixu, a z Phoenixu do San Franciska. 107 00:05:54,220 --> 00:05:56,050 A teraz zase, som dosiahol list. 108 00:05:56,050 --> 00:05:59,470 109 00:05:59,470 --> 00:06:03,980 >> Mohol by som potom sa vrátiť na ďalšie mesto, ktoré som doteraz plne preskúmané. 110 00:06:03,980 --> 00:06:07,440 To by bolo v New Yorku, choďte späť na vrchol môjho stromu, 111 00:06:07,440 --> 00:06:09,160 zostúpil do New Yorku. 112 00:06:09,160 --> 00:06:12,700 Z New Yorku, môžem pozrite sa Nashville, Nashville do Austinu, 113 00:06:12,700 --> 00:06:17,290 Austin do Phoenixu, a z Phoenixu do San Franciska. 114 00:06:17,290 --> 00:06:20,170 A nakoniec, jedno mesto som neboli pozrel na doteraz, Miami. 115 00:06:20,170 --> 00:06:24,600 >> No, z Miami som povedal, že mal dva Možnosti, Nashville či Austin. 116 00:06:24,600 --> 00:06:28,810 Ak by som pozrite sa na Nashville, no a potom som sa lietať od Nashville, do Austinu, do Phoenixu, 117 00:06:28,810 --> 00:06:29,640 do San Franciska. 118 00:06:29,640 --> 00:06:33,600 Ak by som pozrite sa na Austin, Lietam Austin, do Phoenixu, do San Franciska. 119 00:06:33,600 --> 00:06:36,340 A teraz mám strom. 120 00:06:36,340 --> 00:06:37,230 Je to úplný strom. 121 00:06:37,230 --> 00:06:41,890 Je to všetko o možnostiach a všetky cesty, ktoré som mohol vziať. 122 00:06:41,890 --> 00:06:44,310 To znamená, že ak začnem u koreň stromu na vrchole 123 00:06:44,310 --> 00:06:47,860 a ja som šiel do jedného z odíde, to mi hovorí nielen 124 00:06:47,860 --> 00:06:50,480 kam idem do skončiť, San Francisco, 125 00:06:50,480 --> 00:06:53,670 ale to mi hovorí, trasu, Musím vziať sa tam dostať. 126 00:06:53,670 --> 00:06:56,400 127 00:06:56,400 --> 00:06:59,690 >> Teraz, ktorý z nich je najlepší? 128 00:06:59,690 --> 00:07:02,430 No, nič o tom napriek tomu problém mi hovorí, 129 00:07:02,430 --> 00:07:04,710 ktoré z nich je najlepším riešením. 130 00:07:04,710 --> 00:07:09,270 Možno, že mi záleží najviac koľko času som vo vzduchu, 131 00:07:09,270 --> 00:07:12,350 alebo vzdialenosť, že lietam. 132 00:07:12,350 --> 00:07:16,410 V tomto prípade, Chicago do San Francisco môže byť najkratšia číslo 133 00:07:16,410 --> 00:07:18,910 mil vo vzduchu. 134 00:07:18,910 --> 00:07:20,860 >> Možno, že mi záleží cenu. 135 00:07:20,860 --> 00:07:23,680 A všetci vieme, priame lety sú zvyčajne drahšie. 136 00:07:23,680 --> 00:07:26,610 Takže možno, keby som to zobrať druh spätnú trasy 137 00:07:26,610 --> 00:07:30,650 cez Miami, Nashville, Austin, Phoenix, možno potom 138 00:07:30,650 --> 00:07:34,070 Mám za nižšiu cenu. 139 00:07:34,070 --> 00:07:36,440 Ale ja som mohol optimalizovať na niektorý kritériá, ktoré mi záleží. 140 00:07:36,440 --> 00:07:39,790 Kto má najlepší Rokov Wi-Fi, alebo ktoré 141 00:07:39,790 --> 00:07:43,110 letisko majú najlepšie jedlo k dispozícii. 142 00:07:43,110 --> 00:07:47,280 A každý z nich by mohol daj mi iné riešenie 143 00:07:47,280 --> 00:07:49,215 že vidím ako najlepší. 144 00:07:49,215 --> 00:07:51,990 145 00:07:51,990 --> 00:07:54,400 >> Tieto druhy problémov, kam ideme 146 00:07:54,400 --> 00:07:58,480 postaviť túto strom Možnosti a potom 147 00:07:58,480 --> 00:08:02,100 pozrieť sa na každú z nich individuálne cesty, a preskúmať 148 00:08:02,100 --> 00:08:05,270 ktoré z týchto spĺňa kritériom pre nás, 149 00:08:05,270 --> 00:08:08,790 budeme nazývať tie problémy vyhľadávania. 150 00:08:08,790 --> 00:08:11,280 A máme veľa algoritmy, z ktorých niektoré 151 00:08:11,280 --> 00:08:15,270 sme videli už ísť a preskúmať tie stromy. 152 00:08:15,270 --> 00:08:19,270 Mohli by sme to urobiť tak, že som práve urobil, je prehľadávanie do hĺbky, 153 00:08:19,270 --> 00:08:22,900 ísť dole tak ďaleko, ako to pôjde, až kým hit list, a potom sa vráti hore, 154 00:08:22,900 --> 00:08:24,787 a ísť späť dole. 155 00:08:24,787 --> 00:08:26,870 Alebo by sme mohli robiť to, čo je volal prehľadávanie do šírky. 156 00:08:26,870 --> 00:08:29,675 Mohli by sme rozšíriť všetko v hornej časti, a potom 157 00:08:29,675 --> 00:08:31,550 všetko jeden riadok pod, že, a potom 158 00:08:31,550 --> 00:08:35,240 všetko jeden riadok pod to. 159 00:08:35,240 --> 00:08:41,250 Tieto vyhľadávacie stromy sú zásadné pre AI. 160 00:08:41,250 --> 00:08:46,570 Ale oni nemajú dosť dostať to právo po celú dobu. 161 00:08:46,570 --> 00:08:51,600 V skutočnosti, v mnohých prípadoch že nám naozaj záleží, 162 00:08:51,600 --> 00:08:54,430 chceme vybudovať strom, ale nie v skutočnosti 163 00:08:54,430 --> 00:08:57,140 dostať sa, aby všetky rozhodnutia. 164 00:08:57,140 --> 00:09:00,940 >> To sú situácie, nazývané Adversarial vyhľadávanie, tiež známy 165 00:09:00,940 --> 00:09:05,390 ako ako písať hranie hier systémy a dostať za to zaplatené. 166 00:09:05,390 --> 00:09:07,940 Ale to sú druhy systémov, kde som 167 00:09:07,940 --> 00:09:12,920 mohol dostať na výber, keď idem z Boston, ktorý mesto idem na ďalšie. 168 00:09:12,920 --> 00:09:19,990 Ale po tom, niekto iný mohol dostať k rozhodnutiu o tom, kde som sa lietať. 169 00:09:19,990 --> 00:09:24,040 Takže stavať tieto druhy konštrukcie, my sme 170 00:09:24,040 --> 00:09:28,510 bude musieť vziať mierne iný prístup k nemu. 171 00:09:28,510 --> 00:09:31,060 Nebudeme môcť len hľadať cez strom 172 00:09:31,060 --> 00:09:35,000 anymore, pretože nie sme ten, ktorý je pod kontrolou 173 00:09:35,000 --> 00:09:38,180 každej z týchto rozhodovacích bodov. 174 00:09:38,180 --> 00:09:42,590 >> Takže poďme si predstaviť jednoduchý Hra ako tic-tac-toe. 175 00:09:42,590 --> 00:09:46,730 Mohol by som začať s úplne prázdny doska. 176 00:09:46,730 --> 00:09:49,580 A v tic-tac-toe, X sa dostane do hry ako prvý. 177 00:09:49,580 --> 00:09:53,890 A tak som mohol myslieť na všetky možné pohyby, ktoré by mohli urobiť X. 178 00:09:53,890 --> 00:09:57,420 A keď ja som ten, hrajúci X, to je skvelé. 179 00:09:57,420 --> 00:10:01,020 Mám deviatich možných presunie, že môžem robiť. 180 00:10:01,020 --> 00:10:05,000 Mohol by som dať X v niektorom z týchto deviatich polôh. 181 00:10:05,000 --> 00:10:10,710 >> A potom sa z každého z tých, I si predstaviť, čo sa bude diať ďalej. 182 00:10:10,710 --> 00:10:14,130 No, v tomto prípade je druhá hráč by si, aby zase. 183 00:10:14,130 --> 00:10:15,660 O by si, aby zase. 184 00:10:15,660 --> 00:10:19,510 A z každého z tých, tam by bolo osem rôznych miest 185 00:10:19,510 --> 00:10:22,980 že by mohli O miesto ich značku. 186 00:10:22,980 --> 00:10:25,790 >> Povedzme, rozhodol som sa, že som bol chystá dať X v stredu. 187 00:10:25,790 --> 00:10:28,810 To vždy sa zdá, ako dobrý otvorenie ťah. 188 00:10:28,810 --> 00:10:34,870 Mohol by som sa na pod tým, že osem možných pohyby, ktoré robí. O 189 00:10:34,870 --> 00:10:37,320 A teraz, keď som hral X, to je úžasné. 190 00:10:37,320 --> 00:10:41,740 Mám si vybrať, ktorý z nich Aj ísť na, ten uprostred. 191 00:10:41,740 --> 00:10:45,000 Ale teraz O dostane na výber. 192 00:10:45,000 --> 00:10:48,750 A ja nemám kontrolu po tomto rozhodnutí. 193 00:10:48,750 --> 00:10:51,670 >> Ale z každého z tých možných pozícií doska, 194 00:10:51,670 --> 00:10:54,020 je tu potom ďalšie set možností. 195 00:10:54,020 --> 00:10:56,700 Pokiaľ ide o byť my sa znovu obrátiť, urobil by som to 196 00:10:56,700 --> 00:11:01,500 dostanete vybrať a povedať, dobre, ak O presunie do dobre, 197 00:11:01,500 --> 00:11:06,110 prostredný miesto na ľavej strane, potom Mám sadu možností 198 00:11:06,110 --> 00:11:09,740 kde môžem vziať moju ďalší ťah. 199 00:11:09,740 --> 00:11:14,140 Z tých, mohol by som do úvahy všetky možnosti pod nimi. 200 00:11:14,140 --> 00:11:18,030 A potom O dostane vybrať si medzi tie. 201 00:11:18,030 --> 00:11:22,290 >> A mohol by som udržať budovanie tejto strom, kým som sa dostal do bodu, 202 00:11:22,290 --> 00:11:26,960 kde buď niekto vyhráva game--, ktorý je 203 00:11:26,960 --> 00:11:31,070 musíš byť považovaný za list node-- alebo doska je úplne plná 204 00:11:31,070 --> 00:11:32,704 a nikto vyhral. 205 00:11:32,704 --> 00:11:34,370 A to tiež bude koncový uzol. 206 00:11:34,370 --> 00:11:35,411 Že to bude remíza. 207 00:11:35,411 --> 00:11:37,820 208 00:11:37,820 --> 00:11:41,680 >> Ale ošemetná vec s týmto je, či to bola len pravidelné hľadanie 209 00:11:41,680 --> 00:11:44,269 problém, bol by som schopný povedzme, dobre, X by malo ísť sem. 210 00:11:44,269 --> 00:11:45,560 A O mal ísť cestou tam. 211 00:11:45,560 --> 00:11:46,770 A potom X mali ísť sem. 212 00:11:46,770 --> 00:11:48,269 A potom O mal ísť cestou tam. 213 00:11:48,269 --> 00:11:51,860 A potom sa môžete dostať tri X v rade, a ja som vyhral. 214 00:11:51,860 --> 00:11:54,870 A hra skončí v piatich pohybov, tri pre mňa, 215 00:11:54,870 --> 00:11:57,710 dva pre môj súper. 216 00:11:57,710 --> 00:12:01,300 Ale ja nie vždy si musíme vybrať, že. 217 00:12:01,300 --> 00:12:03,720 >> Takže namiesto toho, čo sme bude musieť urobiť 218 00:12:03,720 --> 00:12:06,270 sa budeme mať mať novú stratégiu. 219 00:12:06,270 --> 00:12:09,350 A stratégia, ktorá hra-hracie algoritmy často používajú 220 00:12:09,350 --> 00:12:12,000 je to, čo sa nazýva minimax. 221 00:12:12,000 --> 00:12:15,500 Ústrednou myšlienkou minimax je, že sme 222 00:12:15,500 --> 00:12:21,365 chystá vybrať ťah, ktorý dáva náš súper ten najhorší možný set 223 00:12:21,365 --> 00:12:22,790 pohybov, ktoré môžu robiť. 224 00:12:22,790 --> 00:12:25,570 225 00:12:25,570 --> 00:12:28,870 To nerobí mi k ničomu zvoliť ťah kde 226 00:12:28,870 --> 00:12:31,952 Mohol by som vyhrať po že, pretože môj súper nie je 227 00:12:31,952 --> 00:12:33,160 chystá dať mi tú šancu. 228 00:12:33,160 --> 00:12:37,770 Chystajú sa zvoliť niektoré hrozný výsledok pre mňa. 229 00:12:37,770 --> 00:12:42,010 Takže som sa, aby sa presunúť, ktorá núti môj súper 230 00:12:42,010 --> 00:12:45,760 urobiť niečo pre mňa lepšie. 231 00:12:45,760 --> 00:12:46,260 Dobre. 232 00:12:46,260 --> 00:12:48,410 Poďme sa pozrieť, ako to dopadne. 233 00:12:48,410 --> 00:12:51,640 Tak tu je náš algoritmus v pseudokódu. 234 00:12:51,640 --> 00:12:54,450 Budeme vytvárať Celá hra strom. 235 00:12:54,450 --> 00:12:56,757 Chystáme sa stavať celá štruktúra. 236 00:12:56,757 --> 00:12:57,840 A potom pôjdeme prejsť. 237 00:12:57,840 --> 00:13:02,100 A na samom dne v každom z koncovými uzly, v každom z listov, 238 00:13:02,100 --> 00:13:07,850 budeme hodnotiť, ako cenná je to pre mňa? 239 00:13:07,850 --> 00:13:11,690 A budeme sa hodnota vecí, ktoré sú dobré pre mňa ako pozitívne. 240 00:13:11,690 --> 00:13:14,460 Veci, ktoré nie sú dobré pre mňa bude menej pozitívne, alebo nula, 241 00:13:14,460 --> 00:13:16,480 či dokonca záporná. 242 00:13:16,480 --> 00:13:19,240 >> Takže v tic-tac-toe, možno víťazstvo je pre mňa dobré. 243 00:13:19,240 --> 00:13:20,290 To je jeden. 244 00:13:20,290 --> 00:13:22,400 A kravata je nula. 245 00:13:22,400 --> 00:13:26,230 A niečo, čo je strata pre ma, možno, že je to negatívne. 246 00:13:26,230 --> 00:13:29,620 Všetko, na čom záleží, je, že lepšie je to pre mňa, tým vyššie skóre 247 00:13:29,620 --> 00:13:32,160 to prijme. 248 00:13:32,160 --> 00:13:36,690 Z týchto možností na dno, potom budeme filter smerom nahor. 249 00:13:36,690 --> 00:13:40,650 A keď je to moja šanca na výber medzi sadou alternatív, 250 00:13:40,650 --> 00:13:44,460 Vyberiem si ten, ktorý je dostal najvyššie skóre. 251 00:13:44,460 --> 00:13:47,200 >> A vždy, keď je to moja oponenti sa obrátiť na výber, 252 00:13:47,200 --> 00:13:52,350 Budem predpokladať, že sa chystáte vybrať ten s najnižším skóre. 253 00:13:52,350 --> 00:13:56,090 A keď som to celú cestu až na vrchol stromu, 254 00:13:56,090 --> 00:14:03,150 Budem si vybrali cestu, ktorá dáva me to najlepší výsledok, že môžem dostať, 255 00:14:03,150 --> 00:14:09,110 za predpokladu, že môj súper robí všetky správne kroky. 256 00:14:09,110 --> 00:14:11,940 >> Dobre, takže sa pozrime, to v akcii ako prvý. 257 00:14:11,940 --> 00:14:14,980 A potom sa vlastne pozrite sa na kód pre ňu. 258 00:14:14,980 --> 00:14:16,780 Tak si predstavte Mám veľký strom. 259 00:14:16,780 --> 00:14:18,280 A teraz som to hrať tic-tac-toe. 260 00:14:18,280 --> 00:14:20,405 Chcel som dať niečo, čo trochu bohatší. 261 00:14:20,405 --> 00:14:23,560 Tak som dostal nejakú hru, kde tam je veľa rôznych skóre 262 00:14:23,560 --> 00:14:26,390 že by som mohol mať na konci. 263 00:14:26,390 --> 00:14:27,980 A tak som sa stavať tento celý strom. 264 00:14:27,980 --> 00:14:29,070 A ja som si sa pohybovať ako prvý. 265 00:14:29,070 --> 00:14:31,290 Som na koreň stromu. 266 00:14:31,290 --> 00:14:36,150 >> A ja sa dostanete na výber that-- tak som si maximalizovať cez ktorú prvom uzla. 267 00:14:36,150 --> 00:14:38,410 A potom sa môj súper dostane ísť. 268 00:14:38,410 --> 00:14:41,910 A potom som si ísť ešte raz. 269 00:14:41,910 --> 00:14:46,830 Tak sa na dne, mám sadu možnosti, ktoré som si môžu vybrať z, 270 00:14:46,830 --> 00:14:50,570 rôzne koncové stavy hry. 271 00:14:50,570 --> 00:14:54,980 Ak som sa v tom, že ďaleko ľavom rohu, 272 00:14:54,980 --> 00:14:58,867 a vidím, že mám na výber medzi osem, v sedem, a dva, 273 00:14:58,867 --> 00:15:00,450 no, ja som ten, ktorý dostane na výber. 274 00:15:00,450 --> 00:15:02,910 Takže budem voliť jeden z tých najlepších. 275 00:15:02,910 --> 00:15:05,650 Idem si vybrať osem. 276 00:15:05,650 --> 00:15:10,090 >> Takže viem, že či som niekedy pustiť sa do tohto bodu, 277 00:15:10,090 --> 00:15:13,890 Budem mať možnosť sa dostať, že osem bodov. 278 00:15:13,890 --> 00:15:17,410 Keby som skončí na ďalší bod nad, ďalší uzol nad, 279 00:15:17,410 --> 00:15:20,760 deväť, jeden, alebo šesť, no, ja som bude vybrať tie najlepšie z nich. 280 00:15:20,760 --> 00:15:21,950 Vyberiem si deväť. 281 00:15:21,950 --> 00:15:24,880 Keď budem mať možnosť voľby medzi dva, a štyri, a jeden, 282 00:15:24,880 --> 00:15:28,240 Vyberiem si štyri, čo je najvyššia. 283 00:15:28,240 --> 00:15:31,990 >> A teraz, keď som sa na úrovni nad tým, môj súper 284 00:15:31,990 --> 00:15:34,440 je jeden dostane, aby túto voľbu. 285 00:15:34,440 --> 00:15:37,040 Takže môj súper sa dostáva do vybrať, nechcem, aby mu 286 00:15:37,040 --> 00:15:39,250 to, čo sa deje ho dostať osem bodov, 287 00:15:39,250 --> 00:15:41,916 alebo mám dať mu vec, ktorá sa dám mu deväť bodov, 288 00:15:41,916 --> 00:15:45,240 alebo to, čo sa deje dať mu štyri body? 289 00:15:45,240 --> 00:15:49,130 A môj súper, pričom racionálne, sa deje 290 00:15:49,130 --> 00:15:53,470 zvoliť minimálne tých, sa chystá vybrať štyri. 291 00:15:53,470 --> 00:15:56,020 >> A môžem to urobiť cez celý strom. 292 00:15:56,020 --> 00:15:59,110 Môžem ísť dole k tomu prostredný sada troch. 293 00:15:59,110 --> 00:16:01,517 A ja si môžu vybrať medzi jeden, tri a päť. 294 00:16:01,517 --> 00:16:02,350 A ja som si vybrať. 295 00:16:02,350 --> 00:16:03,810 Tak som si vybrať päť. 296 00:16:03,810 --> 00:16:05,340 Môžem si vybrať tri, deväť, alebo dva. 297 00:16:05,340 --> 00:16:07,570 Mám na výber, takže vybrať si deväť. 298 00:16:07,570 --> 00:16:09,290 Šesť, päť, alebo dva, vybrať. 299 00:16:09,290 --> 00:16:11,539 Mám si vybrať šesť. 300 00:16:11,539 --> 00:16:13,080 Level nad tým, kto sa dostáva do vybrať? 301 00:16:13,080 --> 00:16:16,280 302 00:16:16,280 --> 00:16:18,140 Kto dostane na výber? 303 00:16:18,140 --> 00:16:20,000 Ten druhý chlap, môj súper. 304 00:16:20,000 --> 00:16:22,583 Takže oni si vyberú päť, deväť, alebo šesť, ktorý z nich? 305 00:16:22,583 --> 00:16:23,410 >> Divákov: Päť. 306 00:16:23,410 --> 00:16:25,250 >> SPEAKER: Oni si vybrať päť. 307 00:16:25,250 --> 00:16:27,400 Dostanú na výber minimum. 308 00:16:27,400 --> 00:16:29,690 A potom ten posledný, vybrať jednu, dve alebo tri. 309 00:16:29,690 --> 00:16:31,720 Mám na výber, takže vybrať tri. 310 00:16:31,720 --> 00:16:34,370 Deväť, sedem, alebo dva, vybrať deväť. 311 00:16:34,370 --> 00:16:37,070 A 11, šesť, alebo štyri, vybrať 11. 312 00:16:37,070 --> 00:16:41,190 Môj súper potom vyberie tri, deväť, alebo 11, zvolí minimálny. 313 00:16:41,190 --> 00:16:43,290 On mi dáva tri. 314 00:16:43,290 --> 00:16:47,780 A nakoniec v hornej časti strom, som si znovu zvoliť. 315 00:16:47,780 --> 00:16:51,190 A ja si musíme vybrať medzi štyri, päť, alebo tri. 316 00:16:51,190 --> 00:16:52,270 Tak som vziať päť. 317 00:16:52,270 --> 00:16:55,070 318 00:16:55,070 --> 00:17:00,891 >> Či som mať všetko pod kontrolou, ja by som ísť cestou, ktorá viedla k 11. 319 00:17:00,891 --> 00:17:02,390 Ale ja nechápem, aby túto voľbu. 320 00:17:02,390 --> 00:17:04,220 Ak mám ísť touto cestou. 321 00:17:04,220 --> 00:17:10,710 Môj súper ma nútiť do voľba, ktorá vedie k tri. 322 00:17:10,710 --> 00:17:14,530 Takže to najlepšie, čo môžem urobiť, je aby podnikli stredná vetva, 323 00:17:14,530 --> 00:17:19,859 urobiť túto voľbu, ktorá je nakoniec ma vedú k piatich bodov. 324 00:17:19,859 --> 00:17:23,230 To je to, čo robí minimax. 325 00:17:23,230 --> 00:17:23,807 >> Dobre. 326 00:17:23,807 --> 00:17:24,890 Poďme sa pozrieť na to. 327 00:17:24,890 --> 00:17:27,480 328 00:17:27,480 --> 00:17:32,330 Tak tu v CS50 IDE je program, ktorý 329 00:17:32,330 --> 00:17:36,540 implementuje minimax hrať tic-tac-toe. 330 00:17:36,540 --> 00:17:40,100 Chystáme sa stavať up reprezentácie. 331 00:17:40,100 --> 00:17:44,390 Budeme mať dva opponent-- alebo dvaja hráči, náš počítač 332 00:17:44,390 --> 00:17:46,090 prehrávač a človek hráč. 333 00:17:46,090 --> 00:17:48,980 334 00:17:48,980 --> 00:17:53,090 Číslo hráča z nich bude hrať O. To bude hráč stroj. 335 00:17:53,090 --> 00:17:55,747 Dostanú sa pohybovať druhým. 336 00:17:55,747 --> 00:17:57,830 A ten druhý hráč, náš ľudský hráč, bude X. 337 00:17:57,830 --> 00:17:59,880 >> A aby svoj život trochu jednoduché, idem 338 00:17:59,880 --> 00:18:03,060 označiť tento hráč negatívny jeden. 339 00:18:03,060 --> 00:18:05,026 Tak som si len násobiť záporným jedným vymeniť 340 00:18:05,026 --> 00:18:06,400 Medzi jeden hráč a ďalšie. 341 00:18:06,400 --> 00:18:09,030 342 00:18:09,030 --> 00:18:12,250 Dobre, takže sa poďme pozrieť na to, čo sme vlastne robiť. 343 00:18:12,250 --> 00:18:15,840 Budeme definovať našu dosku. 344 00:18:15,840 --> 00:18:19,060 Je to bude dobre, ideme aby mohla byť tri tri, 345 00:18:19,060 --> 00:18:21,580 alebo môžeme dokonca hrať Päť piatich alebo siedmich 346 00:18:21,580 --> 00:18:28,870 o sedem tic-tac-toe, keby ste ako je, na základe nejakého rozmeru D. 347 00:18:28,870 --> 00:18:31,260 >> A budeme mať pár pomocných funkcií 348 00:18:31,260 --> 00:18:34,360 že budem robiť veci, ako je inicializáciu screen-- alebo ľúto, 349 00:18:34,360 --> 00:18:38,900 inicializovať naše premenné, zrušte obrazovke, kresliť dosku na obrazovke, 350 00:18:38,900 --> 00:18:41,060 ten, ktorý kontroluje dosku či alebo nie 351 00:18:41,060 --> 00:18:44,520 tam je víťaz, ten, ktorý analyzuje prostredníctvom príkazového riadku, 352 00:18:44,520 --> 00:18:50,670 len pomoct, ten, ktorý číta v vstup, a jedna funkcia nazýva minimax. 353 00:18:50,670 --> 00:18:52,746 A to je ten, budeme záleží najviac. 354 00:18:52,746 --> 00:18:54,120 Ale pozrime sa najprv na hlavnej. 355 00:18:54,120 --> 00:18:57,490 356 00:18:57,490 --> 00:18:58,510 >> Čo budeme robiť? 357 00:18:58,510 --> 00:19:00,570 No, budeme analyzovať našu príkazový riadok, 358 00:19:00,570 --> 00:19:04,300 len čítať v a uvidíme, čo rozmer tabule by sme chceli mať. 359 00:19:04,300 --> 00:19:07,330 Budeme inicializovať našu dosku. 360 00:19:07,330 --> 00:19:10,360 A potom budeme zadajte jeden veľký divoký premet, opakovane 361 00:19:10,360 --> 00:19:16,630 prijímajú sa pohybuje, kým je hra vyhral, ​​alebo je tam nie doľava, presunie. 362 00:19:16,630 --> 00:19:20,560 Zakaždým, keď sme sa prejsť, že slučka, budeme vyčistiť obrazovku. 363 00:19:20,560 --> 00:19:23,290 Budeme čerpať dosku na obrazovke. 364 00:19:23,290 --> 00:19:28,750 A my sme zámerne druh oddeliť tieto preč ako podprogramy, 365 00:19:28,750 --> 00:19:32,030 takže nemáme príliš starať o podrobnostiach, ako k nim dochádza. 366 00:19:32,030 --> 00:19:33,480 >> Budete mať kód ešte dnes. 367 00:19:33,480 --> 00:19:37,970 A ak si chcete pozrieť a zistiť, je môžete všetky vidieť. 368 00:19:37,970 --> 00:19:39,890 Ale budeme čerpať doska na obrazovke. 369 00:19:39,890 --> 00:19:43,620 A potom budeme kontrolovať a vidieť, máme víťaza? 370 00:19:43,620 --> 00:19:46,290 Má niekto vyhral túto hru? 371 00:19:46,290 --> 00:19:49,260 Ak majú, budeme tlačiť out správy víťazstvo. 372 00:19:49,260 --> 00:19:51,680 A budeme hru ukončiť. 373 00:19:51,680 --> 00:19:54,510 >> Budeme tiež skontrolovať a zistiť, či tam je remíza. 374 00:19:54,510 --> 00:19:56,620 Bude ľahké zistiť, či tam je remíza. 375 00:19:56,620 --> 00:20:00,700 To znamená, že všetky priestory sú plné, ale tam nebol ešte víťaz. 376 00:20:00,700 --> 00:20:03,580 Môžeme prehlásiť kravatu a hotovo. 377 00:20:03,580 --> 00:20:10,530 Potom skutočný meat-- pokiaľ je to stroj hráč, 378 00:20:10,530 --> 00:20:14,120 budeme dovoliť, aby Stroj hráč vyhľadávať 379 00:20:14,120 --> 00:20:19,500 cez použitie tohto algoritmus minimax, nájsť najlepší ťah, že to môže. 380 00:20:19,500 --> 00:20:22,310 A potom budeme dal, že sa posunú nahor. 381 00:20:22,310 --> 00:20:27,640 >> V opačnom prípade, ak je to človek hráč, budeme čítať nejaký vstup od človeka. 382 00:20:27,640 --> 00:20:30,800 A potom nech je to človek prehrávač alebo prehrávač stroj, 383 00:20:30,800 --> 00:20:32,800 urobíme pár málo kúsky kontrolu chýb, 384 00:20:32,800 --> 00:20:36,910 uistite sa, že zostane v medziach skutočných rozmerov dosky 385 00:20:36,910 --> 00:20:40,040 že máme, uistite sa, že tento priestor je prázdny, 386 00:20:40,040 --> 00:20:43,570 že nikoho dať kus tam už. 387 00:20:43,570 --> 00:20:45,810 A potom si len dať kus na doske, 388 00:20:45,810 --> 00:20:51,550 zmeňte hráča k ďalšej vrstve, a prírastok koľko ťahov sa stalo. 389 00:20:51,550 --> 00:20:54,090 >> To je hlavná slučka pre Naše tic-tac-toe hra. 390 00:20:54,090 --> 00:20:57,000 391 00:20:57,000 --> 00:21:02,340 Minimax, potom, je presne to, algoritmus, ktorý sme predtým. 392 00:21:02,340 --> 00:21:04,710 Jediná úprava, ktorá sme urobili tak, že sme 393 00:21:04,710 --> 00:21:07,290 môže hrať vyššej rozmerné dosky je máme 394 00:21:07,290 --> 00:21:11,070 držal tento dodatočný parameter nazýva hĺbka. 395 00:21:11,070 --> 00:21:14,870 A hĺbka len hovorí, keď som vyhľadávanie smerom dole cez ten strom 396 00:21:14,870 --> 00:21:19,022 a ja som sa tak ďaleko dole za nejakú hĺbku úrovni 397 00:21:19,022 --> 00:21:20,730 že ja proste nechcem ísť ďalej, 398 00:21:20,730 --> 00:21:25,630 Idem sa zastaviť a len hodnotiť dosku v tomto bode. 399 00:21:25,630 --> 00:21:27,310 Pozriem sa a zistiť, či tam je víťaz. 400 00:21:27,310 --> 00:21:29,240 Ak je to víťaz, vráťte mi je. 401 00:21:29,240 --> 00:21:31,720 Inak, pôjdem cez slučku. 402 00:21:31,720 --> 00:21:34,380 A ja poviem, pre všetky možná miesta 403 00:21:34,380 --> 00:21:38,080 že by som mohol možno brať ako môj pohyb, budem 404 00:21:38,080 --> 00:21:43,760 vybudovať hypotetickú doska, ktoré zahŕňa môj pohyb na tejto doske, 405 00:21:43,760 --> 00:21:45,960 a potom rekurzívne zavolá minimax. 406 00:21:45,960 --> 00:21:49,360 407 00:21:49,360 --> 00:21:53,900 >> Ak je to môj krok, som si nájsť ten, ktorý má najväčšie skóre. 408 00:21:53,900 --> 00:21:58,710 Ak je to môjho oponenta ťah, zistíme, ten, ktorý má minimálne skóre. 409 00:21:58,710 --> 00:22:02,240 A všetko ostatné je Stačí nahrať vedenie. 410 00:22:02,240 --> 00:22:04,789 Dobre, takže uvidíme tento beh. 411 00:22:04,789 --> 00:22:06,830 Vlastne, možno môžeme získať niekoľko dobrovoľníkov 412 00:22:06,830 --> 00:22:09,930 prísť a hrať tic-tac-toe. 413 00:22:09,930 --> 00:22:12,780 [Nepočuteľný] jedného, ​​a jeden viac, dva, práve tam. 414 00:22:12,780 --> 00:22:13,550 Poď hore. 415 00:22:13,550 --> 00:22:19,290 416 00:22:19,290 --> 00:22:23,650 >> Tak poďme do toho a reštart to úplne. 417 00:22:23,650 --> 00:22:24,150 Takže, ahoj. 418 00:22:24,150 --> 00:22:24,920 >> Publikum: Dobrý deň. 419 00:22:24,920 --> 00:22:25,420 >> SPEAKER: Ako sa voláte? 420 00:22:25,420 --> 00:22:26,086 >> Divákov: Gorav. 421 00:22:26,086 --> 00:22:26,840 SPEAKER: Gorav. 422 00:22:26,840 --> 00:22:27,800 >> Divákov: Som Layla. 423 00:22:27,800 --> 00:22:29,490 >> SPEAKER: A Layla, a Layla, sorry. 424 00:22:29,490 --> 00:22:30,384 Poď hore. 425 00:22:30,384 --> 00:22:32,050 Gorav, budeme musieť ísť ako prvý. 426 00:22:32,050 --> 00:22:37,710 A ja vás požiadať, aby ste bol nie strašne dobré tic-tac-toe hráčom. 427 00:22:37,710 --> 00:22:40,130 OK, takže všetky tlak off na vás. 428 00:22:40,130 --> 00:22:44,660 Pozrime sa však, že náš stroj hráč môže skutočne urobiť niečo chytrého. 429 00:22:44,660 --> 00:22:45,310 Tak choďte do toho. 430 00:22:45,310 --> 00:22:49,830 Budeš typu, v ktorom súradníc by ste chceli, aby vaše X v. 431 00:22:49,830 --> 00:22:55,170 A0, OK, a stroj je preč hneď a dal svoju stopu v A1. 432 00:22:55,170 --> 00:22:56,640 >> Položte O na doske. 433 00:22:56,640 --> 00:22:58,970 Dobre, teraz choďte do toho. 434 00:22:58,970 --> 00:23:00,193 Kam by si chcel ísť? 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 Náš stroj hráč prijal prostredný námestie, zablokoval. 438 00:23:08,430 --> 00:23:10,320 Takže to bol dobrý, múdra vec pre to robiť. 439 00:23:10,320 --> 00:23:13,430 440 00:23:13,430 --> 00:23:14,250 Vy ste ho zablokoval. 441 00:23:14,250 --> 00:23:15,210 To je skvelé. 442 00:23:15,210 --> 00:23:16,390 Trvá roh tam. 443 00:23:16,390 --> 00:23:23,890 444 00:23:23,890 --> 00:23:30,430 >> A to bude vás nútiť vezmite poslednej priestor, B0. 445 00:23:30,430 --> 00:23:32,220 A hra končí remízou. 446 00:23:32,220 --> 00:23:35,030 Ale hral primeranú Hra proti vám, že jo? 447 00:23:35,030 --> 00:23:36,956 Dobre, ďakujem moc, Gorav. 448 00:23:36,956 --> 00:23:40,860 >> [APPLAUSE] 449 00:23:40,860 --> 00:23:44,723 >> Dobre, Layla, ideme up hry na vás tu. 450 00:23:44,723 --> 00:23:46,940 >> Publikum: Oh, skvelé. 451 00:23:46,940 --> 00:23:49,950 >> SPEAKER: Chystáme sa dať vy štyri štyrmi tic-tac-toe. 452 00:23:49,950 --> 00:23:54,760 Teraz, v štyroch štyrmi, musíte vyhrať s štyri v rade, nie tri v rade. 453 00:23:54,760 --> 00:23:56,135 A je to všetko tvoje. 454 00:23:56,135 --> 00:24:02,180 455 00:24:02,180 --> 00:24:04,420 Takže Layla vzal D1. 456 00:24:04,420 --> 00:24:11,730 Sme teraz bude nasledovať náš počítač prehrávač tu. 457 00:24:11,730 --> 00:24:16,910 Tri tromi tic-tac-toe je druh vec, ktorá je ľahké pre nás všetkých. 458 00:24:16,910 --> 00:24:21,960 Ale je to stále pekné vidieť počítačový hráč robiť chytré ťahy. 459 00:24:21,960 --> 00:24:23,725 Štyri štyrmi dostáva do byť trochu zložitejšie. 460 00:24:23,725 --> 00:24:42,960 461 00:24:42,960 --> 00:24:44,230 >> Dobrá práca. 462 00:24:44,230 --> 00:24:46,210 Dobre, takže Layla je zakončená. 463 00:24:46,210 --> 00:24:48,270 Jo, a my by sme mali skončiť tam. 464 00:24:48,270 --> 00:24:51,870 Ale poďme urobiť ešte jeden tady. 465 00:24:51,870 --> 00:24:53,480 Takže Layla, ďakujem. 466 00:24:53,480 --> 00:24:55,112 Dobrá práca. 467 00:24:55,112 --> 00:24:57,517 >> [APPLAUSE] 468 00:24:57,517 --> 00:25:00,410 469 00:25:00,410 --> 00:25:04,750 >> Takže naše tic-tac-toe hráč ide až do konca a nájde miest, 470 00:25:04,750 --> 00:25:07,040 rieši je pomocou tohto minimax. 471 00:25:07,040 --> 00:25:08,990 A mal som nastavenie hĺbky na to tak, že 472 00:25:08,990 --> 00:25:11,010 by sa bežať príliš rýchlo, čo je pravdepodobne dôvod, prečo 473 00:25:11,010 --> 00:25:16,790 Layla bol schopný ísť pekne dopredu ako ona, a urobil veľmi dobre. 474 00:25:16,790 --> 00:25:20,450 Ale tieto systémy, ktoré práve prejsť a hrubou silou 475 00:25:20,450 --> 00:25:23,870 ísť hlbšie a hlbšie a hlbšie, a držať hľadanie riešení 476 00:25:23,870 --> 00:25:29,890 že je potrebné tieto druhy systémov sú celkom úspešní v nich dobre, 477 00:25:29,890 --> 00:25:32,700 štandardné stolové hry. 478 00:25:32,700 --> 00:25:37,060 >> A v skutočnosti, ak sa pozrieme na Tri tromi tic-tac-toe hra, 479 00:25:37,060 --> 00:25:40,040 toto je v podstate vyriešený problém. 480 00:25:40,040 --> 00:25:45,430 A to je skvelý diagram od Randall Munroe v XKCD, 481 00:25:45,430 --> 00:25:52,130 ukazujúci, z ktorého by ste mali presunúť trvať, vzhľadom k tomu, pohyby svojho súpera sa. 482 00:25:52,130 --> 00:25:56,420 To je niečo, čo sme mohli, ľahko určiť dopredu. 483 00:25:56,420 --> 00:26:00,180 Ale to, čo sa deje, keď sa dostaneme do viac komplexné hry, viac zložité hry, 484 00:26:00,180 --> 00:26:05,690 tam, kde sú väčšie dosky, viac Možnosti, hlbšie stratégie? 485 00:26:05,690 --> 00:26:09,660 >> Ukazuje sa, že tento hrubou silou vyhľadávania stále 486 00:26:09,660 --> 00:26:14,150 robí rozumne dobre, s výnimkou keď sa dostanete do bodu, 487 00:26:14,150 --> 00:26:19,230 kde ten strom je tak veľký že nie je možné reprezentovať všetko. 488 00:26:19,230 --> 00:26:22,370 489 00:26:22,370 --> 00:26:28,280 Keď nemôžete vypočítať celý strom, keď nemôžete ísť dopredu a tlačiť 490 00:26:28,280 --> 00:26:32,204 si do bodu, kedy ste si dostal celý strom v pamäti, 491 00:26:32,204 --> 00:26:34,370 alebo či sa môžete dostať do pamäte, a to bude len 492 00:26:34,370 --> 00:26:39,200 trvať príliš dlho, aby prehľadávať to, čo musíte urobiť niečo múdrejší. 493 00:26:39,200 --> 00:26:42,620 494 00:26:42,620 --> 00:26:46,450 >> Aby bolo možné urobiť, aby vám musíte urobiť dve veci. 495 00:26:46,450 --> 00:26:49,030 Po prvé, musíte nájsť nejaký spôsob, ako obmedziť hĺbku. 496 00:26:49,030 --> 00:26:50,370 No, to je v poriadku. 497 00:26:50,370 --> 00:26:55,740 Môžeme nájsť nejaké pekné, úplné minimum a hovoria, môžete ísť tak hlboko iba. 498 00:26:55,740 --> 00:27:00,890 Ale keď to urobíte, to znamená, že vám majú tieto čiastočne neúplné dosiek. 499 00:27:00,890 --> 00:27:04,770 A musíte si vybrať, mám rád Tento čiastočne neúplné doska, 500 00:27:04,770 --> 00:27:08,600 alebo to čiastočne neúplný doska? 501 00:27:08,600 --> 00:27:11,910 >> A o naše štyri by štyroch tic-tac-toe hra, 502 00:27:11,910 --> 00:27:15,240 náš počítač hráč dostal dole do spodnej časti, a to povedal, 503 00:27:15,240 --> 00:27:16,800 Mám dve rôzne dosky. 504 00:27:16,800 --> 00:27:17,940 Ani jeden je víťazstvo. 505 00:27:17,940 --> 00:27:19,120 Ani jeden je strata. 506 00:27:19,120 --> 00:27:22,070 Ani jeden je kravata. 507 00:27:22,070 --> 00:27:24,100 Ako si mám vybrať medzi nimi? 508 00:27:24,100 --> 00:27:26,200 A to nemalo mať šikovný spôsob, ako robiť to. 509 00:27:26,200 --> 00:27:28,910 510 00:27:28,910 --> 00:27:32,850 >> Vidíme tento druh Vyhodnotenie sa stalo po celú dobu 511 00:27:32,850 --> 00:27:35,290 ako sme sa dostali do zložitejších hier. 512 00:27:35,290 --> 00:27:37,600 Šach je skvelým príkladom. 513 00:27:37,600 --> 00:27:41,550 V šachu, ktoré máme, najprv Zo všetkého, väčšie nastúpi. 514 00:27:41,550 --> 00:27:43,370 Máme oveľa viac kusov. 515 00:27:43,370 --> 00:27:47,930 A umiestnenie týchto kusov a spôsob, akým tieto kúsky pohybujú 516 00:27:47,930 --> 00:27:50,370 je kriticky dôležitá. 517 00:27:50,370 --> 00:27:53,700 Takže ak chcem použiť minimax, Musím byť schopný špecifikovať 518 00:27:53,700 --> 00:27:58,240 a hovoria, táto doska, kde nikto vyhrali alebo prehrali ešte, 519 00:27:58,240 --> 00:28:04,310 je trochu lepší ako ten druhý board, kde nikto vyhral alebo prehral. 520 00:28:04,310 --> 00:28:06,740 >> K tomu, by som mohol robiť veci, ako by som mohol len 521 00:28:06,740 --> 00:28:10,787 spočítať, koľko kusov musím a koľko kusov máte? 522 00:28:10,787 --> 00:28:12,870 Alebo by som mohol dať iný ks rôznych bodov. 523 00:28:12,870 --> 00:28:14,420 Moja kráľovná stojí 20 bodov. 524 00:28:14,420 --> 00:28:16,500 Tvoj pešiak stojí jeden bod. 525 00:28:16,500 --> 00:28:18,920 Kto má viac bodov celkovo? 526 00:28:18,920 --> 00:28:22,300 Alebo by som mohol uvažovať o veci, ako je, Kto má lepšiu pozíciu dosky? 527 00:28:22,300 --> 00:28:26,820 Čí je to na rade nabudúce, všetko, čo môžem 528 00:28:26,820 --> 00:28:31,220 to hodnotiť presnejšie , Ktorá z týchto možností 529 00:28:31,220 --> 00:28:34,660 je lepšie bez dôkladne zvažuje 530 00:28:34,660 --> 00:28:36,565 Každý krok, ktorý mohol prísť po tom. 531 00:28:36,565 --> 00:28:39,740 532 00:28:39,740 --> 00:28:45,130 >> Teraz, aby túto prácu, jedna z vecí, ktorá je 533 00:28:45,130 --> 00:28:48,680 stane naozaj dôležité Pre nás nie je len v pohybe rovno 534 00:28:48,680 --> 00:28:53,720 až na určitú hĺbku limitu, ale je schopný povedať, 535 00:28:53,720 --> 00:28:59,380 jeden z týchto nápadov, ktoré som máme, je tak zlé, že je to 536 00:28:59,380 --> 00:29:02,280 nie je stojí za zváženie všetky možné spôsoby, ako 537 00:29:02,280 --> 00:29:06,680 že veci môžu ísť od desiatich k piatim. 538 00:29:06,680 --> 00:29:12,760 K tomu pridáme do minimax princíp tzv Alpha-beta. 539 00:29:12,760 --> 00:29:16,340 A alfa-beta hovorí, ak máte zlý nápad, 540 00:29:16,340 --> 00:29:22,840 Nestrácajte čas sa snaží presne zistiť, ako zlé to je. 541 00:29:22,840 --> 00:29:24,990 >> Tak tu je to, čo budeme robiť. 542 00:29:24,990 --> 00:29:28,620 Budeme trvať rovnaký zásady, ktoré sme mali predtým, 543 00:29:28,620 --> 00:29:32,200 rovnaký typ minimax vyhľadávania, len sme 544 00:29:32,200 --> 00:29:37,570 bude sledovať, a to nielen z Skutočné hodnoty, ktoré máme, ale my budeme 545 00:29:37,570 --> 00:29:41,440 sledovať najlepší možný hodnota, ktorú by som mohol dostať, 546 00:29:41,440 --> 00:29:45,700 a najhorší možný Výsledok som mohol mať. 547 00:29:45,700 --> 00:29:50,470 A kedykoľvek ten najhorší možný vec vyzerá pravdepodobné, 548 00:29:50,470 --> 00:29:52,694 Budem opustiť túto časť stromu. 549 00:29:52,694 --> 00:29:54,610 A ja sa ani obťažovať pri pohľade na to ešte. 550 00:29:54,610 --> 00:29:57,680 551 00:29:57,680 --> 00:30:02,600 >> Dobre, tak si predstavte, že začneme s týmto istým presným hre stromu. 552 00:30:02,600 --> 00:30:05,200 A teraz sa chystáte ísť zase dole, celú cestu dole 553 00:30:05,200 --> 00:30:07,200 k tomuto ľavom dolnom rohu. 554 00:30:07,200 --> 00:30:11,180 A v tom ľavom dolnom rohu, sme vyzerať a vyhodnocujeme túto dosku. 555 00:30:11,180 --> 00:30:15,700 Možno je to štyri štyrmi tic-tac-toe doska, alebo možno je to šachovnicu. 556 00:30:15,700 --> 00:30:18,620 Ale my sa na to pozrieť, a budeme hodnotiť to, a dostaneme hodnotu osem. 557 00:30:18,620 --> 00:30:22,290 558 00:30:22,290 --> 00:30:28,030 >> V tomto bode, my vieme, že budeme mať aspoň 559 00:30:28,030 --> 00:30:32,380 osem bodov z tohto spodného rozhodnutia. 560 00:30:32,380 --> 00:30:36,620 Nezáleží na tom, čo ten druhý dva sú, že sedem a že dvaja. 561 00:30:36,620 --> 00:30:38,580 Tie by mohli byť akékoľvek hodnoty oni chceli byť. 562 00:30:38,580 --> 00:30:41,279 Chystáme sa dostať najmenej osem bodov. 563 00:30:41,279 --> 00:30:43,070 Dobre, ale mohli by sme choďte do toho a skontrolovať. 564 00:30:43,070 --> 00:30:45,080 Možno, že jeden z nich je lepšia ako osem. 565 00:30:45,080 --> 00:30:46,000 >> Pozerali sme sa na sedem. 566 00:30:46,000 --> 00:30:46,910 Je to lepšie ako osem? 567 00:30:46,910 --> 00:30:48,680 Nie, že sa nemení Náš názor vôbec. 568 00:30:48,680 --> 00:30:49,460 Pozerali sme sa na dva. 569 00:30:49,460 --> 00:30:50,543 Je to lepšie ako osem? 570 00:30:50,543 --> 00:30:52,580 Nie, že sa nemení Náš názor vôbec. 571 00:30:52,580 --> 00:30:55,480 Takže teraz vieme, že sme vyčerpali všetci tam možnosti. 572 00:30:55,480 --> 00:30:58,330 Nebudeme sa dostať niečo lepšie než osem. 573 00:30:58,330 --> 00:31:01,310 Chystáme sa dostať presne to osem. 574 00:31:01,310 --> 00:31:03,825 >> A tak sme sa zmeniť túto uzol a povedzme, že je teraz isté. 575 00:31:03,825 --> 00:31:07,010 576 00:31:07,010 --> 00:31:10,270 Sme prejsť o jednu úroveň vyššie, že. 577 00:31:10,270 --> 00:31:13,820 A teraz vieme niečo o tejto úrovni minimalizácie. 578 00:31:13,820 --> 00:31:18,560 Vieme, že sme nikdy dostať viac ako osem bodov, ak pôjdeme dole 579 00:31:18,560 --> 00:31:20,910 že smer. 580 00:31:20,910 --> 00:31:22,980 Vzhľadom k tomu, aj keď tí, Ďalšie dve vetvy dopadne 581 00:31:22,980 --> 00:31:26,170 aby bolo fantastické a stojí za to tisíce bodov každý, 582 00:31:26,170 --> 00:31:31,666 náš súper bude Daj nám minimum, a daj nám osem. 583 00:31:31,666 --> 00:31:32,790 Dobre, no, uvidíme. 584 00:31:32,790 --> 00:31:35,190 Budeme ďalej touto cestou. 585 00:31:35,190 --> 00:31:38,490 Ideme dole na túto stredu na ľavej strane. 586 00:31:38,490 --> 00:31:40,560 Pozeráme sa dole a vidíme tam je deväť. 587 00:31:40,560 --> 00:31:45,590 Vieme, že budeme mať aspoň deväť bodov tým, že ide dole 588 00:31:45,590 --> 00:31:47,720 že uprostred cesty. 589 00:31:47,720 --> 00:31:52,110 A v tomto bode, môžeme len pozastaviť. 590 00:31:52,110 --> 00:31:56,910 A môžeme povedať, pozrite, ja známymi v úrovni vyššie, 591 00:31:56,910 --> 00:32:01,160 Budem mať viac ako ôsmich body tým, že ide dole týmto smerom. 592 00:32:01,160 --> 00:32:05,670 Ale keď som išiel na polovicu cesta namiesto ľavej dráhy, 593 00:32:05,670 --> 00:32:08,980 Chcel by som získať aspoň deväť bodov. 594 00:32:08,980 --> 00:32:13,590 >> Môj súper sa nikdy nechaj ma ísť dole, že strednú cestu. 595 00:32:13,590 --> 00:32:14,650 Dostanú na výber. 596 00:32:14,650 --> 00:32:18,140 A idú zvoliť Cesta vľavo smerom k ôsmim, 597 00:32:18,140 --> 00:32:23,650 skôr než stredom smerom čo je najmenej deväť bodov. 598 00:32:23,650 --> 00:32:25,334 Takže na tom mieste, budem zastaviť. 599 00:32:25,334 --> 00:32:26,500 A ja poviem, že vieš, čo? 600 00:32:26,500 --> 00:32:29,990 Nechcem sa pozerať akýkoľvek viac sa v tomto smere. 601 00:32:29,990 --> 00:32:32,270 Pretože ja nikdy sa tam dostať. 602 00:32:32,270 --> 00:32:36,660 >> Môžem preskočiť, že jeden, a môžem preskočiť, že šesť, 603 00:32:36,660 --> 00:32:39,720 pretože to sa nikdy nestane. 604 00:32:39,720 --> 00:32:42,470 Takže ja pôjdem dole a budem uvažovať ďalšiu možnosť. 605 00:32:42,470 --> 00:32:44,830 Idem tam a hovorím, vidím dva. 606 00:32:44,830 --> 00:32:47,125 Viem, že keď dostanem až sem, ja som dostane aspoň dve. 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 Aj ďalej. 610 00:32:51,520 --> 00:32:52,440 Vidím štyri. 611 00:32:52,440 --> 00:32:54,920 Viem, že budem mať aspoň štyri. 612 00:32:54,920 --> 00:32:57,200 Je tu ešte veľa medzi štyri a osem, hoci. 613 00:32:57,200 --> 00:32:58,454 Tak som ďalej. 614 00:32:58,454 --> 00:32:59,870 Pozriem sa dolu a vidím, je tu ešte jedna. 615 00:32:59,870 --> 00:33:01,614 Tak jo, ja viem, ak Idem dole touto cestou, 616 00:33:01,614 --> 00:33:03,280 Budem mať možnosť vybrať si štyri. 617 00:33:03,280 --> 00:33:06,540 618 00:33:06,540 --> 00:33:08,980 Čo sa môj súper bude robiť? 619 00:33:08,980 --> 00:33:12,310 Medzi niečo, čo mi dáva osem, niečo, čo mi dáva štyri, 620 00:33:12,310 --> 00:33:14,730 a niečo, čo mi dáva najmenej deväť, 621 00:33:14,730 --> 00:33:17,550 dobre, že to bude dať mi štyri. 622 00:33:17,550 --> 00:33:20,110 A ja teraz viem, u veľmi top, idem 623 00:33:20,110 --> 00:33:23,145 aby bolo možné získať minimálne štyri body z tejto hry. 624 00:33:23,145 --> 00:33:27,030 625 00:33:27,030 --> 00:33:30,900 >> Celá myšlienka alfa-beta je odrezať diely strom tak, 626 00:33:30,900 --> 00:33:32,530 že nemám pozerať sa na ne už nie. 627 00:33:32,530 --> 00:33:35,964 Ale to stále vyzerá, ako som bol pri pohľade na veľa stromu. 628 00:33:35,964 --> 00:33:36,880 Poďme ďalej nadol. 629 00:33:36,880 --> 00:33:38,305 Pôjdeme dole ten budúci teraz. 630 00:33:38,305 --> 00:33:39,680 Dole na dne, nájdem jeden. 631 00:33:39,680 --> 00:33:41,030 Viem, že budem mať aspoň jednu. 632 00:33:41,030 --> 00:33:41,690 Som hľadať ďalej. 633 00:33:41,690 --> 00:33:42,625 >> Nájdem tri. 634 00:33:42,625 --> 00:33:44,250 Viem, že budem mať aspoň tri. 635 00:33:44,250 --> 00:33:44,840 Aj ďalej. 636 00:33:44,840 --> 00:33:45,660 Nájdem päť. 637 00:33:45,660 --> 00:33:49,760 Ja viem, že som sa dostať päť keď som si v tejto ceste. 638 00:33:49,760 --> 00:33:52,580 A tiež viem, potom že môj súper, ak I 639 00:33:52,580 --> 00:33:55,510 vyberte stred tri veľké možnosti, 640 00:33:55,510 --> 00:34:01,440 že to bude, aby mi niečo, čo je päť alebo menej. 641 00:34:01,440 --> 00:34:02,150 >> OK. 642 00:34:02,150 --> 00:34:03,400 Môžem pokračovať tam. 643 00:34:03,400 --> 00:34:06,470 Môžem sa pozrieť dole a ja Dá sa povedať, čo mám 644 00:34:06,470 --> 00:34:08,239 získať, keď idem po strednú cestu? 645 00:34:08,239 --> 00:34:09,909 Idem sa dostať, dobre, tri tam. 646 00:34:09,909 --> 00:34:12,080 Idem si pre niečo to je najmenej tri. 647 00:34:12,080 --> 00:34:16,030 Je tu ešte veci medzi tri a päť, tak som hľadať ďalej. 648 00:34:16,030 --> 00:34:20,203 Oh, deväť, budem určite prevziať, že viac ako tri. 649 00:34:20,203 --> 00:34:22,744 Chystám sa získať aspoň deväť keď pôjdem dole, že strednú cestu. 650 00:34:22,744 --> 00:34:25,530 651 00:34:25,530 --> 00:34:31,010 >> A teraz môj súper zastaví a hovorí: vyzerať, že to nemá zmysel ešte. 652 00:34:31,010 --> 00:34:33,669 Viem, že môj minimalizácia súper, je to 653 00:34:33,669 --> 00:34:36,210 chystá dať mi vec, ktorá sa menšia alebo rovná piatimi, 654 00:34:36,210 --> 00:34:39,030 skôr než vec, ktorá sa väčší alebo rovný deväť. 655 00:34:39,030 --> 00:34:39,530 Aj zastaviť. 656 00:34:39,530 --> 00:34:40,779 Nechcem vyzerať viac sa na to. 657 00:34:40,779 --> 00:34:43,280 Aj ďalej. 658 00:34:43,280 --> 00:34:44,850 >> Pozriem sa dole na tento jeden. 659 00:34:44,850 --> 00:34:46,370 Až na dno, nájdem šesť. 660 00:34:46,370 --> 00:34:50,040 Ja viem, že som sa získať aspoň šesť. 661 00:34:50,040 --> 00:34:53,130 A čo mám robiť? 662 00:34:53,130 --> 00:34:54,877 Nemôžem prestať. 663 00:34:54,877 --> 00:34:57,460 Pretože je voľba medzi niečo, čo je najmenej šesť 664 00:34:57,460 --> 00:34:59,250 a niečo, čo je menej ako päť, on je 665 00:34:59,250 --> 00:35:02,570 chystá dať mi tú vec To je menej ako päť. 666 00:35:02,570 --> 00:35:04,779 A teraz viem, že idem ako dostať presne to, že voľba. 667 00:35:04,779 --> 00:35:06,195 Chystám sa dostať, že päť voľbu. 668 00:35:06,195 --> 00:35:08,980 669 00:35:08,980 --> 00:35:10,010 >> Vrátim sa až na vrchol. 670 00:35:10,010 --> 00:35:11,450 Čo budem vybrať medzi niečím 671 00:35:11,450 --> 00:35:14,449 to je väčší alebo rovný štyrom, alebo niečo, čo je rovná piatich? 672 00:35:14,449 --> 00:35:17,140 Idem si niečo to je najmenej päť. 673 00:35:17,140 --> 00:35:20,490 Idem dole na poslednej ceste, všetky cesta dole na dno. 674 00:35:20,490 --> 00:35:21,260 Zaznie tam taky jeden. 675 00:35:21,260 --> 00:35:23,410 OK, aspoň budem mať jeden bod. 676 00:35:23,410 --> 00:35:24,427 Aj ďalej. 677 00:35:24,427 --> 00:35:25,760 Dva, ach, je to lepšie ako jeden. 678 00:35:25,760 --> 00:35:27,100 Chystám sa získať aspoň dva. 679 00:35:27,100 --> 00:35:28,610 Nájdem tri. 680 00:35:28,610 --> 00:35:31,450 Ja viem, že som sa dostať tri. 681 00:35:31,450 --> 00:35:34,690 >> A bod vyššie uvedeného vyplýva, môj súper sa deje 682 00:35:34,690 --> 00:35:38,540 aby mi dal niečo, čo je menšie ako alebo rovný trom. 683 00:35:38,540 --> 00:35:40,940 A teraz môžem zastaviť. 684 00:35:40,940 --> 00:35:46,290 Vzhľadom k tomu, v voľba medzi mnou bytia možnosť získať päť a môj súper 685 00:35:46,290 --> 00:35:52,290 to, že mi niečo menej ako tri, Ja som vždy bude trvať, že päť. 686 00:35:52,290 --> 00:35:56,810 Takže si nemyslím, že hodnotiť Spodná časť stromu vôbec. 687 00:35:56,810 --> 00:35:59,470 >> A teraz, sa to môže zdať menšie. 688 00:35:59,470 --> 00:36:03,630 Ale keď malé kúsky aritmetiky, väčšie ako a menšie ako, 689 00:36:03,630 --> 00:36:10,640 môže odrezať celej časti tento exponenciálne rastúci strom, 690 00:36:10,640 --> 00:36:14,280 ktorá vedie k obrovskej Množstvo sporenia, úspory 691 00:36:14,280 --> 00:36:17,630 ktoré sú dostatočne veľké, že som Môžete začať hrať konkurenčne 692 00:36:17,630 --> 00:36:21,330 u zložitejších hier. 693 00:36:21,330 --> 00:36:27,030 >> Dobre, ak sa pozrieme na veľkosti a zložitosti rôznych hier, 694 00:36:27,030 --> 00:36:29,470 tic-tac-toe bol náš jednoduchý príklad. 695 00:36:29,470 --> 00:36:32,150 Máme malú dosku, tri tromi. 696 00:36:32,150 --> 00:36:36,030 Dostávame, nanajvýš priemerne asi štyri rôzne voľby 697 00:36:36,030 --> 00:36:38,440 ako sme prejsť hru. 698 00:36:38,440 --> 00:36:42,720 Máme niekde okolo 10 k piatej možné rôzne listy. 699 00:36:42,720 --> 00:36:45,200 A budovanie tic-tac-toe hráč, dobre, len sme to urobili. 700 00:36:45,200 --> 00:36:47,460 Je to ľahké. 701 00:36:47,460 --> 00:36:49,890 >> Ak by sme ísť až na niečo viac komplexné, ako Connect Four. 702 00:36:49,890 --> 00:36:53,170 Spomínate si na túto hru, kde pustíte malé tokeny? 703 00:36:53,170 --> 00:36:58,490 Je to šesť od siedmich doska, Nie je to oveľa väčšie, stále 704 00:36:58,490 --> 00:37:00,770 má približne rovnakú rozvetvenie faktorom tic-tac-toe. 705 00:37:00,770 --> 00:37:05,410 Mám asi štyri možnosti kde môžem dať veci do. 706 00:37:05,410 --> 00:37:10,760 Ale teraz, mám oveľa viac vedie 10 k 21. moci. 707 00:37:10,760 --> 00:37:14,440 To je niečo, čo je ľahké natoľko, že sme riešiť to hneď. 708 00:37:14,440 --> 00:37:17,560 >> Dáma, viac complex-- vás Dostal osem osem palube. 709 00:37:17,560 --> 00:37:20,570 Si len na polovicu im kedykoľvek, hoci. 710 00:37:20,570 --> 00:37:24,930 Máte vetvenia faktorom, ktorý je asi 2,8. 711 00:37:24,930 --> 00:37:28,160 No, máme pár pohybuje si môžete vziať. 712 00:37:28,160 --> 00:37:33,870 Vy ste asi 10 dostal do 31. listy, väčšie a väčšie, a väčšie priestory. 713 00:37:33,870 --> 00:37:37,340 Ako som prehľadávať tie väčšie a väčšie priestory, 714 00:37:37,340 --> 00:37:42,220 to je, keď sa veci, ako je alfa-beta a budú môcť odrezať celé odvetvia 715 00:37:42,220 --> 00:37:44,420 stáva zásadný. 716 00:37:44,420 --> 00:37:47,440 >> Teraz, dáma bolo dosť ľahké v roku 1992. 717 00:37:47,440 --> 00:37:51,400 Počítačový program nazvaný Chinook porazil svetovej dáma 718 00:37:51,400 --> 00:37:53,590 šampiónov, Marion Tinsley. 719 00:37:53,590 --> 00:37:57,260 A od tej doby, no človek majster hráč má 720 00:37:57,260 --> 00:38:02,290 bol schopný poraziť tie najlepšie výpočtové systémy. 721 00:38:02,290 --> 00:38:06,570 Ak sa pozrieme na niečo ako šach, teraz zase, máme osem osem palube. 722 00:38:06,570 --> 00:38:09,870 Ale my máme oveľa zložitejšie kusy, oveľa zložitejšie pohyby. 723 00:38:09,870 --> 00:38:14,610 Máme vetvenia faktor o 35, 35 možných ťahov v priemere 724 00:38:14,610 --> 00:38:20,030 že môžem vziať, a stať priestor, počet listov 725 00:38:20,030 --> 00:38:28,950 ktorý vyrástol na 10 až 123. moci, obrovské množstvo možností. 726 00:38:28,950 --> 00:38:35,570 >> Dokonca stále, moderné procesory sú schopní to urobiť úspešne. 727 00:38:35,570 --> 00:38:43,900 V roku 1995 a potom v roku 1997, v počítači program s názvom Deep Blue postavený IBM 728 00:38:43,900 --> 00:38:49,601 ktorý bežal na obrie superpočítači porazil aktuálny majster sveta, 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 To bol zlom. 732 00:38:56,650 --> 00:39:00,620 Dnes sa však, že rovnaké spracovanie napájanie sedí na mojom MacBook. 733 00:39:00,620 --> 00:39:04,180 734 00:39:04,180 --> 00:39:06,440 >> Rýchlosť spracovania udržuje stále rýchlejšie a rýchlejšie. 735 00:39:06,440 --> 00:39:09,500 Môžeme hodnotiť viac a viac dosky rýchlejší a rýchlejší. 736 00:39:09,500 --> 00:39:14,550 Ale ešte dôležitejšie je, že máme lepší vyhodnocovacie funkcie a lepšie prerezávanie 737 00:39:14,550 --> 00:39:15,460 metódy. 738 00:39:15,460 --> 00:39:19,560 Takže môžeme prehľadať priestor viac komplexne. 739 00:39:19,560 --> 00:39:22,350 Najväčší dosky hry, že môžeme myslieť, 740 00:39:22,350 --> 00:39:26,310 niečo ako Go to dostal 19 19 dosku, 741 00:39:26,310 --> 00:39:32,490 teraz zrazu, sme za bod kde výpočtových systémov vyhrať. 742 00:39:32,490 --> 00:39:34,530 Nie je výpočtovej Systém vonku 743 00:39:34,530 --> 00:39:38,880 , Ktorý môže poraziť profesionálnych hráčov Go. 744 00:39:38,880 --> 00:39:45,000 Najlepšie systémy dnes poradí ju o druh dobré amatérskej úrovni. 745 00:39:45,000 --> 00:39:49,285 Takže tam je ešte celkom trochu mimo tam, že sa nemôžete dostať do ešte. 746 00:39:49,285 --> 00:39:51,840 747 00:39:51,840 --> 00:39:55,360 >> Dobre, tieto tradičné stolové hry, 748 00:39:55,360 --> 00:39:58,560 tieto druhy systémov, kde sme stavať tento minimax, či už je to tu 749 00:39:58,560 --> 00:40:06,300 alfa-beta, alebo nie, tieto algoritmy pracujú preto, že existujú určité obmedzenia. 750 00:40:06,300 --> 00:40:08,520 Máme dokonalé informácie o svete. 751 00:40:08,520 --> 00:40:11,690 Vieme, kde sú všetky diely sú. 752 00:40:11,690 --> 00:40:13,570 Svet je statické. 753 00:40:13,570 --> 00:40:16,220 Nikto sa presunúť kúsky okolo, zatiaľ čo ja som 754 00:40:16,220 --> 00:40:20,640 tam sedí myslenia, vzal ma príde rad. 755 00:40:20,640 --> 00:40:23,140 Je tu akčné priestor, ktorý je diskrétne. 756 00:40:23,140 --> 00:40:26,900 Môžem dať svoje pešiaka tu, alebo si dať svoje pešiaka tu. 757 00:40:26,900 --> 00:40:30,520 Ja nesmiem dať svoje pešiaka na čiara medzi dvoma štvorcov. 758 00:40:30,520 --> 00:40:34,430 759 00:40:34,430 --> 00:40:36,520 >> A konečne, akcie sú deterministické. 760 00:40:36,520 --> 00:40:39,790 Viem, že keď poviem, veža na rytiera tri, 761 00:40:39,790 --> 00:40:44,660 moja veža sa chystá skončiť na rytiera tri, tak dlho, ako je to platný ťah. 762 00:40:44,660 --> 00:40:47,830 Neexistuje žiadna neistota o tom. 763 00:40:47,830 --> 00:40:52,490 Teraz, keď som ísť do viac rôzne druhy hier, 764 00:40:52,490 --> 00:40:55,960 musíme prelomiť tieto predpoklady. 765 00:40:55,960 --> 00:41:00,020 >> Čo keď pôjdem k niečomu ako klasických videohier? 766 00:41:00,020 --> 00:41:04,180 Tu je výber z videa hry z Atari 2600. 767 00:41:04,180 --> 00:41:05,180 Čo mám tam hore? 768 00:41:05,180 --> 00:41:08,440 Mám Frogger, Vesmírnej Invaders, Pitfall a Pac-Man. 769 00:41:08,440 --> 00:41:11,290 770 00:41:11,290 --> 00:41:14,840 Aké druhy prostredia mám tu teraz? 771 00:41:14,840 --> 00:41:16,900 Ktorý z týchto predpokladov musím zlomiť? 772 00:41:16,900 --> 00:41:19,410 773 00:41:19,410 --> 00:41:21,570 >> No, to záleží na hre. 774 00:41:21,570 --> 00:41:28,170 Mohol by som hrať šach na 2600, a by to bolo, rovnako ako tomu bolo predtým. 775 00:41:28,170 --> 00:41:33,020 Pre väčšinu z týchto systémov, je tu Kompletné vedomosti o svete. 776 00:41:33,020 --> 00:41:36,300 K dispozícii je kompletne deterministické akcie. 777 00:41:36,300 --> 00:41:38,330 Ale obvykle, svet je už nie je statická. 778 00:41:38,330 --> 00:41:41,970 To znamená, že zatiaľ čo ja som tam sedí čakanie, niečo sa pohybuje. 779 00:41:41,970 --> 00:41:44,320 Duchovia sú na ceste k mňa dostať. 780 00:41:44,320 --> 00:41:46,570 Škorpión je za mnou pod ním. 781 00:41:46,570 --> 00:41:48,880 Tieto Space Invaders sú príde bližšie a bližšie. 782 00:41:48,880 --> 00:41:54,020 783 00:41:54,020 --> 00:41:55,510 Ako dobre môžeme urobiť proti nim? 784 00:41:55,510 --> 00:41:58,640 785 00:41:58,640 --> 00:42:02,790 >> Pred niekoľkými rokmi, Google bol projekt s názvom 786 00:42:02,790 --> 00:42:12,030 DeepMind, kde trénoval počítač Program hrať Atari 2600 hier. 787 00:42:12,030 --> 00:42:16,120 A ak si myslíte, že to nie je vážne podnikania, výsledky ich štúdie 788 00:42:16,120 --> 00:42:19,920 boli publikované v Nature, tak len asi tak dobrý publikácia 789 00:42:19,920 --> 00:42:22,500 ako si môžeš získať. 790 00:42:22,500 --> 00:42:24,340 A tu je, ako dobre oni hrali. 791 00:42:24,340 --> 00:42:29,220 >> Majú algoritmus, ktorý sedel a díval sa len na obrazovke vstupy. 792 00:42:29,220 --> 00:42:34,080 To dostalo žiadne inštrukcie vôbec o pravidlách hry. 793 00:42:34,080 --> 00:42:42,610 A to malo prísť na to, na základe svojej skóre, ako dobre to robí. 794 00:42:42,610 --> 00:42:46,560 Jednalo sa o systém, ktorý používa niečo volal učenia zosilnenie. 795 00:42:46,560 --> 00:42:48,380 To znamená, že sa pozrel na svoje skóre. 796 00:42:48,380 --> 00:42:51,620 A či to mám dobré skóre, to povedal, Mal by som si tie veci. 797 00:42:51,620 --> 00:42:53,310 A ja som mal robiť tie znova. 798 00:42:53,310 --> 00:42:56,450 A či to mám zle, to povedal, Nemal by som urobiť znovu tie veci. 799 00:42:56,450 --> 00:42:59,750 800 00:42:59,750 --> 00:43:03,430 >> To je výkon z týchto vyškolených systémov 801 00:43:03,430 --> 00:43:07,490 nechá hrať za Pár hodín na každú hru, 802 00:43:07,490 --> 00:43:12,490 porovnané s profesionálnymi hráčmi. 803 00:43:12,490 --> 00:43:19,670 Takže pre všetky hry, ktoré sú na ľavej strane tejto línie, 804 00:43:19,670 --> 00:43:25,920 Toto self-cvičil počítačový program prekonala profesionálnych hráčov. 805 00:43:25,920 --> 00:43:29,690 A za všetko do pravdu, profesionálnymi hráčmi 806 00:43:29,690 --> 00:43:30,920 boli stále najlepší. 807 00:43:30,920 --> 00:43:34,040 808 00:43:34,040 --> 00:43:36,850 Za niečo, čo vedel nič o pravidlách, ktoré 809 00:43:36,850 --> 00:43:43,020 nevedel nič o štruktúre hry, to je pôsobivé predstavenie. 810 00:43:43,020 --> 00:43:45,660 A to je to, čo sme schopní urobiť dnes. 811 00:43:45,660 --> 00:43:50,239 >> OK, hovoríte, ale ak budeme premýšľať o tom, AI v hrách, 812 00:43:50,239 --> 00:43:52,530 normálne si myslíme, že o Veci, ktoré môžeme v skutočnosti 813 00:43:52,530 --> 00:43:54,180 sadnúť a hrať proti. 814 00:43:54,180 --> 00:43:58,760 Ak by som si sadnúť a ja hrať StarCraft, alebo hrám zadarmo Sito, 815 00:43:58,760 --> 00:44:01,870 počítač súper je osoba, ktorá kontroluje Zergov, 816 00:44:01,870 --> 00:44:06,770 alebo riadenie druhej civilizácie. 817 00:44:06,770 --> 00:44:11,920 Ako sa títo hráči skutočne nájsť svoj ťah? 818 00:44:11,920 --> 00:44:18,810 >> No, tieto hry sú štruktúrované veľa rovnaký cesta ako naše stolové hry, 819 00:44:18,810 --> 00:44:22,250 Tieto hry, ktoré budeme súhrnne nazývajú štyri na X Games, 820 00:44:22,250 --> 00:44:26,040 preskúmať, expand-- zabudnúť na tie. 821 00:44:26,040 --> 00:44:26,980 Čo sú zač? 822 00:44:26,980 --> 00:44:32,150 Preskúmať, rozširovať, a uhasiť, Myslím si, že je posledná. 823 00:44:32,150 --> 00:44:36,060 Ale sú v zásade prieskum a Conquer hry. 824 00:44:36,060 --> 00:44:41,020 Typicky, počítač súper tam má obmedzené informácie. 825 00:44:41,020 --> 00:44:45,486 Nevedia presne, čo je to deje za tej hmle vojny. 826 00:44:45,486 --> 00:44:47,735 Oni nie sú vidieť na vlastné oči, čo Máte vo vašom inventári. 827 00:44:47,735 --> 00:44:50,240 828 00:44:50,240 --> 00:44:52,800 >> K dispozícii je prostredie, ktoré je dynamické. 829 00:44:52,800 --> 00:44:56,180 Všetko sa mení po celú dobu. 830 00:44:56,180 --> 00:45:00,290 Nemusíte dostať sedieť a dočkať, aby sa váš pohyb. 831 00:45:00,290 --> 00:45:02,810 Ale väčšina vecí sú stále diskrétne. 832 00:45:02,810 --> 00:45:04,200 Musím dať svoje mesto tu. 833 00:45:04,200 --> 00:45:06,750 Alebo musím dať moje mesto tu. 834 00:45:06,750 --> 00:45:08,950 A všetko je deterministický. 835 00:45:08,950 --> 00:45:14,660 Keď hovorím, pohnúť jednotkou tu, môj prístroj sa pohybuje tu, pokiaľ nie je prekážkou náhle 836 00:45:14,660 --> 00:45:17,700 vstúpi do hry. 837 00:45:17,700 --> 00:45:21,610 Teraz, že to nie je všetko počítač hry, ktoré sú tam dnes. 838 00:45:21,610 --> 00:45:27,320 >> Ak by som ísť a ja hrať prvá osoba typu hra, niečo ako zlodej alebo Falloutu 839 00:45:27,320 --> 00:45:33,350 alebo Skyrim, alebo Halo, teraz Mám počítačovým protivníkom 840 00:45:33,350 --> 00:45:37,860 že sú tam, že majú veľmi odlišná situácia. 841 00:45:37,860 --> 00:45:40,020 Majú opäť obmedzené informácie. 842 00:45:40,020 --> 00:45:43,420 Oni len možné uvidieť istá zorné pole. 843 00:45:43,420 --> 00:45:45,180 Životné prostredie je stále dynamický. 844 00:45:45,180 --> 00:45:48,280 Veci sa menia po celú dobu. 845 00:45:48,280 --> 00:45:52,300 >> Ale teraz mám oveľa viac kontinuálne akcie priestor. 846 00:45:52,300 --> 00:45:57,170 Môžem byť len pokukování trochu z dverí. 847 00:45:57,170 --> 00:46:00,650 A niektoré hry, my akcie sú stochastické. 848 00:46:00,650 --> 00:46:04,590 Mám sa pokúsiť preskočiť tú stenu, ale mám šancu na zlyhanie. 849 00:46:04,590 --> 00:46:08,280 850 00:46:08,280 --> 00:46:14,550 Tieto typy hier sú stále bližšie a bližšie k druhom regulátorov 851 00:46:14,550 --> 00:46:17,330 že staviame v robotike. 852 00:46:17,330 --> 00:46:21,050 >> V robotike, musíme predpokladať, že máme obmedzené množstvo informácií. 853 00:46:21,050 --> 00:46:23,070 Máme senzory, ktoré povedzte nám o svete. 854 00:46:23,070 --> 00:46:25,860 Máme vždy sa meniace, dynamické prostredie. 855 00:46:25,860 --> 00:46:30,440 Máme svet, v ktorom je priestor kontinuálne, skôr než diskrétne. 856 00:46:30,440 --> 00:46:36,260 A naše akcie, kedy sa snažíme oni, majú šancu na zlyhanie. 857 00:46:36,260 --> 00:46:40,960 A v skutočnosti, moderné hra regulátory pre Vašu Halo súpera, 858 00:46:40,960 --> 00:46:48,690 alebo pre tých, NPC v Skyrim, v podstate spustiť malé robotiky architektúry. 859 00:46:48,690 --> 00:46:50,380 >> Vnímajú svet. 860 00:46:50,380 --> 00:46:52,910 Vychádzajú model na svete. 861 00:46:52,910 --> 00:46:57,950 Oni výpočtových založený na súbore cieľov, ktoré by chcel dosiahnuť. 862 00:46:57,950 --> 00:47:03,110 Plánujú akcie založené Na to, čo vedia. 863 00:47:03,110 --> 00:47:07,940 A to sú presne tie isté druhy systémov, ktoré budujeme v robotike. 864 00:47:07,940 --> 00:47:11,420 Takže tieto architektúry, aby priniesť to späť dohromady, 865 00:47:11,420 --> 00:47:14,500 sú často úplne rovnaké. 866 00:47:14,500 --> 00:47:16,340 >> Tak uvidíme, či môžeme vidieť, že. 867 00:47:16,340 --> 00:47:19,210 Poďme sa vrátiť k našej Príkladom tic-tac-toe. 868 00:47:19,210 --> 00:47:22,690 A ja som sa opýtať pár mojich post-docs prísť a pomôžte mi. 869 00:47:22,690 --> 00:47:26,970 Takže Chen Ming, a Alessandro a Olivier, či vy by prísť. 870 00:47:26,970 --> 00:47:32,080 871 00:47:32,080 --> 00:47:35,440 A ja budem potrebovať pár dobrovoľníkov 872 00:47:35,440 --> 00:47:37,590 >> OK, som videl ruku právo tam uprostred. 873 00:47:37,590 --> 00:47:39,965 Dovoľte mi, aby som ešte raz, niekto ďalej v zadnej možná. 874 00:47:39,965 --> 00:47:40,881 Dobre, tamto. 875 00:47:40,881 --> 00:47:41,490 Poď hore. 876 00:47:41,490 --> 00:47:44,190 877 00:47:44,190 --> 00:47:45,335 Dobre. 878 00:47:45,335 --> 00:47:49,490 Takže poďme prijať, že kryt dole. 879 00:47:49,490 --> 00:48:03,700 A ak by sa vy prísť hneď staré tu pre mňa fantastické. 880 00:48:03,700 --> 00:48:06,580 >> Takže toto je robot s názvom Baxter. 881 00:48:06,580 --> 00:48:10,880 A Baxter je robot, ktorý je obchodná platforma, navrhnutý 882 00:48:10,880 --> 00:48:13,030 spoločnosť s názvom Prehodnotiť. 883 00:48:13,030 --> 00:48:16,580 A tento robot je určený drobného spracovateľského priemyslu. 884 00:48:16,580 --> 00:48:19,265 Ale dnes budeme ju použiť hrať tic-tac-toe. 885 00:48:19,265 --> 00:48:21,930 886 00:48:21,930 --> 00:48:27,150 Teraz, tento robot je tiež niečo to je pomerne unikátny. 887 00:48:27,150 --> 00:48:32,950 Pretože keď som stála kdekoľvek V jeho blízkosti je štandardná priemyselnej automatizácie 888 00:48:32,950 --> 00:48:39,580 systém, bol by som v samom hrobe Nebezpečenstvo poranenia. 889 00:48:39,580 --> 00:48:45,600 >> Baxter, však, je navrhnutý tak, aby relatívne bezpečné pre interakciu s. 890 00:48:45,600 --> 00:48:48,680 A tak som sa môžu tlačiť na tomto robota. 891 00:48:48,680 --> 00:48:52,350 A môžete vidieť, že je to trochu bit flexibilné, ako sa pohybuje okolo. 892 00:48:52,350 --> 00:48:57,250 A môžem premiestniť ju kde by som rád, aby to ísť. 893 00:48:57,250 --> 00:49:03,410 Teraz v normálnej robotického systému, budeme mať niekoľko spojov tu 894 00:49:03,410 --> 00:49:07,970 ktorý by bol priamo reakciu na príkazy polohy. 895 00:49:07,970 --> 00:49:13,180 A oni by nutne jedno, ak boli v pohybe po čerstvom vzduchu, 896 00:49:13,180 --> 00:49:15,555 alebo ak boli v pohybe cez môj hrudného koša. 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 A zvyčajne, ak ste boli tu sa priemyselných systémov, 900 00:49:22,090 --> 00:49:23,400 by si ísť nikde blízko toho. 901 00:49:23,400 --> 00:49:26,280 Tam by bol žltý Bezpečnostné pásky okolo neho. 902 00:49:26,280 --> 00:49:28,310 Tento systém má mierne odlišné konštrukcie 903 00:49:28,310 --> 00:49:32,130 byť priateľskejší a jednoduchšie pre ľudí, komunikovať s, 904 00:49:32,130 --> 00:49:36,380 v tom, že v každom kĺbe, je tu jar. 905 00:49:36,380 --> 00:49:39,110 A skôr než riadenie presná poloha, 906 00:49:39,110 --> 00:49:43,110 ovládame určité množstvo krútiaci moment, určité množstvo sily, 907 00:49:43,110 --> 00:49:45,874 že by sme chceli byť na tomto jar. 908 00:49:45,874 --> 00:49:47,790 Dobre, tak nech ma vziať našu dobrovoľníci tu. 909 00:49:47,790 --> 00:49:48,540 Ahoj ako sa voláš? 910 00:49:48,540 --> 00:49:49,010 >> Divákov: Louis. 911 00:49:49,010 --> 00:49:49,635 >> SPEAKER: Louis. 912 00:49:49,635 --> 00:49:50,490 Rád ťa vidím. 913 00:49:50,490 --> 00:49:50,990 A? 914 00:49:50,990 --> 00:49:51,610 >> Divákov: David. 915 00:49:51,610 --> 00:49:51,960 >> SPEAKER: David. 916 00:49:51,960 --> 00:49:52,550 Rád som ťa spoznal. 917 00:49:52,550 --> 00:49:54,508 Ak by si chlapci čakať tu na sekundu, 918 00:49:54,508 --> 00:49:56,420 Budem vám možnosť to urobiť. 919 00:49:56,420 --> 00:50:00,610 Takže tento robot, ak ste prišli a ak sa na ňu ľahko zatlačte, 920 00:50:00,610 --> 00:50:03,780 budete vidieť, že pohybuje sa trochu. 921 00:50:03,780 --> 00:50:06,349 A ak si to urvat pravdu tu na zápästie len 922 00:50:06,349 --> 00:50:09,390 nad miestom, kde sa tieto tlačidlá sú, to vyzerá, ako by ste mali chytiť tlačidiel, 923 00:50:09,390 --> 00:50:13,100 ale chytiť priamo nad ním namiesto toho, budete bolo možné veľmi jemne manipulovať 924 00:50:13,100 --> 00:50:14,545 vesmírom. 925 00:50:14,545 --> 00:50:15,920 Louis, chcete skúsiť to? 926 00:50:15,920 --> 00:50:19,465 Tak daj to len trochu tlačiť začať. 927 00:50:19,465 --> 00:50:23,190 A potom, keď dáte prsty tu a držať na to, 928 00:50:23,190 --> 00:50:24,807 pretože sa bude pohybovať na vás, potom. 929 00:50:24,807 --> 00:50:27,824 930 00:50:27,824 --> 00:50:29,365 Dobre, chcete skúsiť to? 931 00:50:29,365 --> 00:50:29,980 Poď hore. 932 00:50:29,980 --> 00:50:32,300 Tak daj to len jemný tlačiť tam začať. 933 00:50:32,300 --> 00:50:33,820 Môžete cítiť, aké to je. 934 00:50:33,820 --> 00:50:40,060 A potom, ak ste to chytiť priamo tam, budete mať možnosť manévrovať okolo. 935 00:50:40,060 --> 00:50:41,280 >> OK. 936 00:50:41,280 --> 00:50:47,360 Takže väčšinou, by tento druh robota použiť na výrobu v malom meradle. 937 00:50:47,360 --> 00:50:50,980 A ja sa presunúť ruku len dole z cesty trochu tu. 938 00:50:50,980 --> 00:50:55,750 Ale dnes, budeme používať Rovnaký tic-tac-toe herný systém 939 00:50:55,750 --> 00:50:59,520 založené na minimax, že sme postavili skôr. 940 00:50:59,520 --> 00:51:00,549 OK? 941 00:51:00,549 --> 00:51:02,340 Takže, vy ste každý bude hrať hru. 942 00:51:02,340 --> 00:51:04,210 Louis, budete ako prvý. 943 00:51:04,210 --> 00:51:05,920 Dovoľte mi len držať tu na chvíľku. 944 00:51:05,920 --> 00:51:10,949 Budem mať stojíte pravdu tu, len tak môže každý vidieť. 945 00:51:10,949 --> 00:51:11,990 Vy ste chlapci nastavenia tu? 946 00:51:11,990 --> 00:51:13,120 >> ROBOT: Vitajte. 947 00:51:13,120 --> 00:51:15,910 Poďme si hrať tic-tac-toe. 948 00:51:15,910 --> 00:51:20,860 Nedržte token pred Ja hovorím, že je to na tebe. 949 00:51:20,860 --> 00:51:22,050 Aj spustiť hru. 950 00:51:22,050 --> 00:51:27,900 951 00:51:27,900 --> 00:51:28,750 Je rad na mňa. 952 00:51:28,750 --> 00:51:47,002 953 00:51:47,002 --> 00:51:50,210 SPEAKER: Teraz, keď mohol mať jednu z vaše kúsky a choďte do toho a umiestnite ju. 954 00:51:50,210 --> 00:51:51,446 ROBOT: Je to na tebe. 955 00:51:51,446 --> 00:51:53,430 [SMIECH] 956 00:51:53,430 --> 00:51:54,836 Je rad na mňa. 957 00:51:54,836 --> 00:51:56,820 [SMIECH] 958 00:51:56,820 --> 00:52:12,196 959 00:52:12,196 --> 00:52:15,680 [SMIECH] 960 00:52:15,680 --> 00:52:16,570 Je to na tebe. 961 00:52:16,570 --> 00:52:21,397 962 00:52:21,397 --> 00:52:23,688 SPEAKER: Ľudská rasa je Spolieham sa na teba, Louisovi. 963 00:52:23,688 --> 00:52:27,440 964 00:52:27,440 --> 00:52:28,350 >> ROBOT: Je rad na mne. 965 00:52:28,350 --> 00:52:44,810 966 00:52:44,810 --> 00:52:47,015 >> SPEAKER: Takže Baxter tu úspešne blokovaný. 967 00:52:47,015 --> 00:52:49,670 968 00:52:49,670 --> 00:52:52,480 >> ROBOT: Je to na tebe. 969 00:52:52,480 --> 00:52:53,360 Je rad na mňa. 970 00:52:53,360 --> 00:53:14,730 971 00:53:14,730 --> 00:53:16,810 Je to na tebe. 972 00:53:16,810 --> 00:53:17,760 Je rad na mňa. 973 00:53:17,760 --> 00:53:21,330 974 00:53:21,330 --> 00:53:23,830 SPEAKER: A necháme Baxter dokončiť svoj posledný ťah tu. 975 00:53:23,830 --> 00:53:36,622 976 00:53:36,622 --> 00:53:39,090 >> [SMIECH] 977 00:53:39,090 --> 00:53:40,480 >> ROBOT: To je kravatu. 978 00:53:40,480 --> 00:53:42,030 Ja vyhrá nabudúce. 979 00:53:42,030 --> 00:53:43,365 >> [SMIECH] 980 00:53:43,365 --> 00:53:45,210 >> SPEAKER: Dobre, Vďaka moc, Louis. 981 00:53:45,210 --> 00:53:46,094 Ďakujem. 982 00:53:46,094 --> 00:53:46,980 Môžete ísť touto cestou. 983 00:53:46,980 --> 00:53:49,759 >> ROBOT: I spustite hry. 984 00:53:49,759 --> 00:53:51,800 SPEAKER: Takže dovoľte mi vysvetliť pre vás ešte jeden malý 985 00:53:51,800 --> 00:53:55,410 bit než sa dostaneme naši odvetu tu. 986 00:53:55,410 --> 00:53:57,200 Čo presne sa deje? 987 00:53:57,200 --> 00:53:59,430 Takže robot má kamerový hore vrchol tu. 988 00:53:59,430 --> 00:54:01,330 A to je díval sa na doske. 989 00:54:01,330 --> 00:54:04,470 A je to vidieť, či je to tu červenou O alebo modrá 990 00:54:04,470 --> 00:54:10,450 a biela X. Rovnako ako tie, ktoré si umiestni na tabule, to je v podstate rovnaký vstup 991 00:54:10,450 --> 00:54:13,890 že budeme čítať od naša štruktúra dát z našej obrazovky. 992 00:54:13,890 --> 00:54:17,290 Je to beh rovnaké minimax algoritmus, ktorý bude 993 00:54:17,290 --> 00:54:21,010 schopní zistiť, kde sa umiestnite dobrou token. 994 00:54:21,010 --> 00:54:24,820 >> A potom dávame povel o kde by sme chceli token má byť umiestnená. 995 00:54:24,820 --> 00:54:26,120 Rameno sa pohybuje von. 996 00:54:26,120 --> 00:54:31,750 Je to pomocou vákuovej chápadlá aplikovať niektoré sacie uvedeného dreveného kusu, 997 00:54:31,750 --> 00:54:35,240 si to vyzdvihnúť, presuňte ho doprava miesto, a potom uvoľnite sania 998 00:54:35,240 --> 00:54:36,950 a umiestnite ho. 999 00:54:36,950 --> 00:54:38,990 Dobre, ideme dať mu ešte jednu ranu 1000 00:54:38,990 --> 00:54:40,930 s mierne múdrejší prehrávača tu. 1001 00:54:40,930 --> 00:54:42,290 Ste pripravení? 1002 00:54:42,290 --> 00:54:46,150 Dobrá, ak by ste postaviť až tu a dať je-- dopadlo takhle 1003 00:54:46,150 --> 00:54:47,955 takže môžete vidieť všetky. 1004 00:54:47,955 --> 00:54:48,830 A potom [nepočuteľných]. 1005 00:54:48,830 --> 00:54:49,330 >> ROBOT: Je rad na mne. 1006 00:54:49,330 --> 00:54:50,455 >> SPEAKER: Baxter sa spustí. 1007 00:54:50,455 --> 00:55:10,750 1008 00:55:10,750 --> 00:55:11,730 Je to na tebe. 1009 00:55:11,730 --> 00:55:16,490 1010 00:55:16,490 --> 00:55:17,520 Je rad na mňa. 1011 00:55:17,520 --> 00:55:38,740 1012 00:55:38,740 --> 00:55:39,690 Je to na tebe. 1013 00:55:39,690 --> 00:55:46,330 1014 00:55:46,330 --> 00:55:47,165 Je rad na mňa. 1015 00:55:47,165 --> 00:56:01,252 1016 00:56:01,252 --> 00:56:06,192 >> [SMIECH] 1017 00:56:06,192 --> 00:56:08,542 >> SPEAKER: [šepká] Just ho nechať ísť dopredu a vyhrať. 1018 00:56:08,542 --> 00:56:09,500 ROBOT: Je to na tebe. 1019 00:56:09,500 --> 00:56:15,099 1020 00:56:15,099 --> 00:56:15,890 SPEAKER: To je v poriadku. 1021 00:56:15,890 --> 00:56:20,390 1022 00:56:20,390 --> 00:56:21,360 >> ROBOT: Je rad na mne. 1023 00:56:21,360 --> 00:56:24,825 1024 00:56:24,825 --> 00:56:26,805 >> [SMIECH] 1025 00:56:26,805 --> 00:56:42,650 1026 00:56:42,650 --> 00:56:43,510 >> Vyhrám. 1027 00:56:43,510 --> 00:56:45,620 >> [SMIECH] 1028 00:56:45,620 --> 00:56:46,595 >> Aj spustiť hru. 1029 00:56:46,595 --> 00:56:48,261 >> SPEAKER: Dobre, ďakujem moc. 1030 00:56:48,261 --> 00:56:50,180 1031 00:56:50,180 --> 00:56:55,590 Dobre, myslím, že máme čas na ešte jeden vynikajúci tic-tac-toe player, 1032 00:56:55,590 --> 00:57:00,490 niekto, kto môže dať túto vec zápas, kto vie, čo robia. 1033 00:57:00,490 --> 00:57:03,010 >> [SMIECH] 1034 00:57:03,010 --> 00:57:05,560 >> Kto to bude naším majstrom tu? 1035 00:57:05,560 --> 00:57:08,110 Dobre, vaši priatelia vás prihlásil. 1036 00:57:08,110 --> 00:57:11,190 To je dosť dobré pre mňa. 1037 00:57:11,190 --> 00:57:12,194 Povedz mi znova svoje meno. 1038 00:57:12,194 --> 00:57:12,860 Divákov: Tamir. 1039 00:57:12,860 --> 00:57:14,193 SPEAKER: Tamir, rád vás vidím. 1040 00:57:14,193 --> 00:57:19,270 Tak jo, zase budeme, aby vám a to až tu, takže každý môže vidieť. 1041 00:57:19,270 --> 00:57:22,070 Ste náš zástupca V tomto stretnutí teraz. 1042 00:57:22,070 --> 00:57:24,540 Baxter je jeden a oh oh a. 1043 00:57:24,540 --> 00:57:26,300 Alebo Ospravedlňujem sa, jeden oh a jeden. 1044 00:57:26,300 --> 00:57:27,490 A to je len na vás tu. 1045 00:57:27,490 --> 00:57:29,340 Baxter dostane pohybovať ako prvý, hoci. 1046 00:57:29,340 --> 00:57:30,435 So. 1047 00:57:30,435 --> 00:57:31,310 ROBOT: Je rad na mne. 1048 00:57:31,310 --> 00:57:45,226 1049 00:57:45,226 --> 00:57:48,208 >> [SMIECH] 1050 00:57:48,208 --> 00:57:52,720 1051 00:57:52,720 --> 00:57:55,780 >> Je to na tebe. 1052 00:57:55,780 --> 00:57:56,845 Je rad na mňa. 1053 00:57:56,845 --> 00:58:18,130 1054 00:58:18,130 --> 00:58:18,965 Je to na tebe. 1055 00:58:18,965 --> 00:58:28,751 1056 00:58:28,751 --> 00:58:30,248 Je rad na mňa. 1057 00:58:30,248 --> 00:58:51,210 1058 00:58:51,210 --> 00:58:52,160 Je to na tebe. 1059 00:58:52,160 --> 00:59:00,854 1060 00:59:00,854 --> 00:59:03,365 >> [SMIECH] 1061 00:59:03,365 --> 00:59:04,240 ROBOT: Je rad na mne. 1062 00:59:04,240 --> 00:59:06,930 SPEAKER: Je to oveľa ťažšie, keď stojíte tu, ľudí. 1063 00:59:06,930 --> 00:59:19,400 1064 00:59:19,400 --> 00:59:21,840 [SMIECH] 1065 00:59:21,840 --> 00:59:26,730 1066 00:59:26,730 --> 00:59:29,054 ROBOT: Vy ľudia ste tak ľahké poraziť. 1067 00:59:29,054 --> 00:59:30,803 [Smiech a APPLAUSE] 1068 00:59:30,803 --> 00:59:31,886 SPEAKER: Vďaka moc. 1069 00:59:31,886 --> 00:59:34,692 ROBOT: Aj vyhrať. 1070 00:59:34,692 --> 00:59:35,400 Aj spustiť hru. 1071 00:59:35,400 --> 00:59:39,500 >> Prednášajúci: Dobre, takže vďaka veľmi veľa Olivier, a Alessandro, 1072 00:59:39,500 --> 00:59:41,616 a Chen Ming. 1073 00:59:41,616 --> 00:59:45,600 >> [APPLAUSE] 1074 00:59:45,600 --> 00:59:47,040 >> Chcem, aby jeden posledný bod. 1075 00:59:47,040 --> 00:59:51,630 Takže Baxter u veľmi nekončí, podvádzal. 1076 00:59:51,630 --> 00:59:54,160 1077 00:59:54,160 --> 00:59:56,310 A to bolo nečakané. 1078 00:59:56,310 --> 01:00:00,440 Jeden z fantastický veci, o AI je, že sme 1079 01:00:00,440 --> 01:00:05,070 robiť prácu v AI tak, aby sme mohli budovať naozaj zaujímavé a inteligentné 1080 01:00:05,070 --> 01:00:06,930 zariadení. 1081 01:00:06,930 --> 01:00:10,130 Ale aj my robiť prácu v AI pretože nám to hovorí niečo 1082 01:00:10,130 --> 01:00:13,940 o tom, ako ľudia sú inteligentné. 1083 01:00:13,940 --> 01:00:17,280 >> Jeden z najobľúbenejších štúdie z mojej laboratóriu je 1084 01:00:17,280 --> 01:00:23,660 pri pohľade na to, čo sa stane, keď stroja nečakane podvádzať. 1085 01:00:23,660 --> 01:00:27,070 Urobili sme to pôvodne nie s Baxter hrať tic-tac-toe, 1086 01:00:27,070 --> 01:00:30,340 ale s menším robot menom Nao, kto hral Kameň, papier, nožnice. 1087 01:00:30,340 --> 01:00:33,010 1088 01:00:33,010 --> 01:00:35,800 A niekedy po hrať veľa a veľa 1089 01:00:35,800 --> 01:00:41,580 nudné Kameň, papier, nožnice hry, robot bude hodiť gesto, 1090 01:00:41,580 --> 01:00:48,616 stratiť, a potom náhle zmeniť jeho gesto a povedať, že som vyhral. 1091 01:00:48,616 --> 01:00:50,480 >> [SMIECH] 1092 01:00:50,480 --> 01:00:56,090 >> Teraz, niekedy by sme tiež robota, rovnako ako kontrola, hodiť gesto, 1093 01:00:56,090 --> 01:01:01,270 vyhrať, a zmeniť jeho gesto stratiť, hádzať zápas, 1094 01:01:01,270 --> 01:01:04,070 podvádzať, aby sa stratiť. 1095 01:01:04,070 --> 01:01:07,540 A to nie je zďaleka tak presvedčivý. 1096 01:01:07,540 --> 01:01:09,890 Robot, ktorý podvádza s cieľom vyhrať ľudí 1097 01:01:09,890 --> 01:01:14,660 reagovať, ako keby to je , Aby ich dostať, to páči 1098 01:01:14,660 --> 01:01:17,690 aktívne hľadá ich zničenie. 1099 01:01:17,690 --> 01:01:19,210 >> [SMIECH] 1100 01:01:19,210 --> 01:01:20,990 >> To sa stáva agent. 1101 01:01:20,990 --> 01:01:21,840 Je to ako človek. 1102 01:01:21,840 --> 01:01:23,970 To má vieru a zámer. 1103 01:01:23,970 --> 01:01:27,470 A nie je to dobrý úmysel. 1104 01:01:27,470 --> 01:01:33,790 A robot, ktorý hodí Hra je jednoducho nefunguje. 1105 01:01:33,790 --> 01:01:36,990 Je to len rozbité zariadenia. 1106 01:01:36,990 --> 01:01:41,405 Ukážem vám niekoľko príkladov z toho z niekoľkých našich účastníkov. 1107 01:01:41,405 --> 01:01:43,990 1108 01:01:43,990 --> 01:01:45,600 Tak tu je podvádzanie, aby sa stratiť. 1109 01:01:45,600 --> 01:01:46,266 >> [Videoprehrávanie] 1110 01:01:46,266 --> 01:01:47,010 - [Nepočuteľný] vyhrať. 1111 01:01:47,010 --> 01:01:49,550 Poďme hrať. 1112 01:01:49,550 --> 01:01:50,538 >> -Počkaj čo? 1113 01:01:50,538 --> 01:01:54,490 1114 01:01:54,490 --> 01:01:55,352 >> - [Nepočuteľný] vyhrať. 1115 01:01:55,352 --> 01:01:58,280 Poďme hrať. 1116 01:01:58,280 --> 01:01:59,400 >> [Nepočuteľný] vyhrať. 1117 01:01:59,400 --> 01:02:02,290 Poďme hrať. 1118 01:02:02,290 --> 01:02:05,490 >> SPEAKER: A tu je podvádzanie vyhrať. 1119 01:02:05,490 --> 01:02:06,438 >> Áno, som vyhrať. 1120 01:02:06,438 --> 01:02:07,394 Poďme hrať. 1121 01:02:07,394 --> 01:02:08,828 >> -Nemůžeš Urobiť. 1122 01:02:08,828 --> 01:02:10,740 >> [SMIECH] 1123 01:02:10,740 --> 01:02:12,174 1124 01:02:12,174 --> 01:02:13,979 >> Áno, som vyhrať. 1125 01:02:13,979 --> 01:02:14,520 -Ty Podvádzal. 1126 01:02:14,520 --> 01:02:17,990 1127 01:02:17,990 --> 01:02:20,010 Teraz podvádzal. 1128 01:02:20,010 --> 01:02:21,140 >> Áno, som vyhrať. 1129 01:02:21,140 --> 01:02:22,940 >> Hej, ty podvodníčka. 1130 01:02:22,940 --> 01:02:26,670 Môžete podvádzať, super podvádzať. 1131 01:02:26,670 --> 01:02:27,650 >> [END Prehrávanie] 1132 01:02:27,650 --> 01:02:31,130 >> SPEAKER: Tieto rozdielne Reakcia rýchlo 1133 01:02:31,130 --> 01:02:34,890 zmeniť naše vnímanie zariadení. 1134 01:02:34,890 --> 01:02:36,780 Znamená to, že sme zámerne budovať 1135 01:02:36,780 --> 01:02:40,370 stroje, ktoré podvádzajú, pretože to je najlepšie inžinierstva, ktoré môžeme robiť? 1136 01:02:40,370 --> 01:02:44,680 Nie, ale to nám hovorí niečo naozaj zaujímavé o ľuďoch. 1137 01:02:44,680 --> 01:02:49,710 Tá vec, ktorá vás a podvádza kradne vaše víťazstvo, to je 1138 01:02:49,710 --> 01:02:53,660 niečo, čo je nažive, to je animovať, že je von dostať vás. 1139 01:02:53,660 --> 01:02:54,680 To má duševný stav. 1140 01:02:54,680 --> 01:02:55,400 To má vieru. 1141 01:02:55,400 --> 01:02:57,170 To má v úmysle. 1142 01:02:57,170 --> 01:03:01,540 >> To, čo rukami Hra vám, že to nie je. 1143 01:03:01,540 --> 01:03:04,670 To je jednoducho nefunguje. 1144 01:03:04,670 --> 01:03:08,900 To je v mnohých ohľadoch, prečo je to ľahké hodiť hru s deťmi. 1145 01:03:08,900 --> 01:03:12,050 Ale ak sa pokúsite podvádzať a druh tvrdí víťazstvo 1146 01:03:12,050 --> 01:03:15,200 keď, viete, len aby skrátiť hra, oni ťa chytí hneď. 1147 01:03:15,200 --> 01:03:19,040 1148 01:03:19,040 --> 01:03:23,140 Tieto typy účinkov, ktoré vidíme prichádza z AI, 1149 01:03:23,140 --> 01:03:26,490 Učí nás veľa o sebe. 1150 01:03:26,490 --> 01:03:28,076 >> Dobre, to je pre dnešok všetko. 1151 01:03:28,076 --> 01:03:30,450 Vďaka moc Dávidovi a produkčný tím Harvard 1152 01:03:30,450 --> 01:03:32,350 prišla dole. 1153 01:03:32,350 --> 01:03:33,820 >> [APPLAUSE] 1154 01:03:33,820 --> 01:03:36,760 1155 01:03:36,760 --> 01:03:41,840 >> Uvidíme sa za jeden kvíz, a potom na poslednú prednáške. 1156 01:03:41,840 --> 01:03:43,025 Majú veľký deň. 1157 01:03:43,025 --> 01:03:44,965 >> [APPLAUSE] 1158 01:03:44,965 --> 01:03:48,360 1159 01:03:48,360 --> 01:03:51,825 >> [Prehrávanie hudby] 1160 01:03:51,825 --> 01:03:54,950 DAVID J Malan: No, my pravdepodobne potrebovať zaviesť nejaký druh šifrovania, 1161 01:03:54,950 --> 01:03:55,450 v poriadku? 1162 01:03:55,450 --> 01:03:58,650 Pretože potom hlavičiek Tieto požiadavky HTTP budú 1163 01:03:58,650 --> 01:04:01,530 miešaná tak, že niekto sa snaží čuchať váš prevádzku 1164 01:04:01,530 --> 01:04:03,400 nebude v skutočnosti je môcť vidieť. 1165 01:04:03,400 --> 01:04:05,254 Takže aké je riešenie tohto problému? 1166 01:04:05,254 --> 01:04:07,920 No, musíme skutočne zaviesť šifrovanie do vzorca, 1167 01:04:07,920 --> 01:04:11,010 tak, že keď táto osoba je prenášanie dát z A do B, 1168 01:04:11,010 --> 01:04:12,390 môžeme bezpečne send-- 1169 01:04:12,390 --> 01:04:14,590 >> [SMIECH] 1170 01:04:14,590 --> 01:04:19,530 >> Informácie v tak, že protivník nemôže v skutočnosti vidieť.