1 00:00:00,000 --> 00:00:01,924 >> [REPRODUCCIÓ DE MÚSICA] 2 00:00:01,924 --> 00:00:10,600 3 00:00:10,600 --> 00:00:13,280 >> ALTAVEU: Benvingut de nou, tothom. 4 00:00:13,280 --> 00:00:15,440 Això és CS50. 5 00:00:15,440 --> 00:00:21,040 I avui, tenim una gran quantitat de coses interessants que parlar. 6 00:00:21,040 --> 00:00:25,500 Primer, però, he de recordar- que d'algunes coses administratives. 7 00:00:25,500 --> 00:00:30,160 Aquesta setmana és prova un, dimecres o per a la secció de Yale 8 00:00:30,160 --> 00:00:32,940 els dimarts i dijous, dijous. 9 00:00:32,940 --> 00:00:38,170 Hi ha opinions de concursos aquesta nit a la Universitat de Yale, dos quarts-7: 00. 10 00:00:38,170 --> 00:00:40,030 A Harvard, van gravar un sol ahir. 11 00:00:40,030 --> 00:00:43,000 I tothom pot veure que en línia. 12 00:00:43,000 --> 00:00:49,406 >> A més, aquesta setmana o principis de la setmana que ve, tenim la nostra última conferència CS50. 13 00:00:49,406 --> 00:00:51,450 [Gemecs] sé. 14 00:00:51,450 --> 00:00:54,140 Va arribar tan aviat. 15 00:00:54,140 --> 00:00:57,820 Estudiants de Yale tindran un viu donar una conferència aquí a la Facultat de Dret 16 00:00:57,820 --> 00:00:59,920 Auditori divendres. 17 00:00:59,920 --> 00:01:01,140 Hi haurà coca. 18 00:01:01,140 --> 00:01:05,570 Estudiants de Harvard tindran la última conferència a Sanders dilluns. 19 00:01:05,570 --> 00:01:08,050 També hi haurà coca. 20 00:01:08,050 --> 00:01:14,000 >> A més, aquesta setmana el divendres, per a aquells de vostès que estan arribant a New Haven, 21 00:01:14,000 --> 00:01:15,740 tenim l'Expo CS50. 22 00:01:15,740 --> 00:01:18,850 Tenim més de 30 diferents grups registrats 23 00:01:18,850 --> 00:01:22,530 per mostrar-li tot de velers autònomes, 24 00:01:22,530 --> 00:01:27,170 als sistemes que reconeixen retrats digitals, a l'ordinador 25 00:01:27,170 --> 00:01:32,100 la música i la música per ordinador produïda. 26 00:01:32,100 --> 00:01:33,610 Així que si us plau, uneix-t'hi. 27 00:01:33,610 --> 00:01:36,460 Crec que serà un bon moment. 28 00:01:36,460 --> 00:01:40,320 >> Avui, però, arribem a seguir parlant d'AI, 29 00:01:40,320 --> 00:01:43,150 sobre la intel·ligència artificial. 30 00:01:43,150 --> 00:01:46,070 I una de les coses que anem a arribar a l'actualitat 31 00:01:46,070 --> 00:01:51,750 és la idea de com AI utilitzar per resoldre problemes. 32 00:01:51,750 --> 00:01:54,690 Ara, com sempre, anem a començar amb una cosa senzilla. 33 00:01:54,690 --> 00:01:57,120 I anem a començar amb una idea simple. 34 00:01:57,120 --> 00:01:59,920 I això és mitjançant la recerca. 35 00:01:59,920 --> 00:02:06,990 >> Així que imagini per un moment que jo tenen una tasca que he de dur a terme. 36 00:02:06,990 --> 00:02:11,970 I m'agradaria tenir aquesta tasca automatitzat per algun agent programari. 37 00:02:11,970 --> 00:02:17,100 Imagina't que jo estic tractant de reservar un conjunt de vols procedents de, diguem, Boston 38 00:02:17,100 --> 00:02:20,040 a San Francisco. 39 00:02:20,040 --> 00:02:24,230 Jo podria anar a través i cal fer això un de la meravellosa recerca en línia 40 00:02:24,230 --> 00:02:28,790 eines, que es van a fer bàsicament el mateix procés que estem 41 00:02:28,790 --> 00:02:30,030 anar a caminar a través de l'actualitat. 42 00:02:30,030 --> 00:02:34,100 Però si vostè no ha de eina, què faries? 43 00:02:34,100 --> 00:02:37,570 >> Bé, podries mirar i veig i dic, estic a Boston. 44 00:02:37,570 --> 00:02:41,520 Quin vols estan disponibles per a mi? 45 00:02:41,520 --> 00:02:44,390 Ara, potser Tinc tres possibles vols fora de Boston 46 00:02:44,390 --> 00:02:47,180 que s'ajusti el temps quan he de sortir. 47 00:02:47,180 --> 00:02:48,830 Podia volar a Chicago. 48 00:02:48,830 --> 00:02:50,130 O podria volar a Miami. 49 00:02:50,130 --> 00:02:53,340 O podria volar a Nova York. 50 00:02:53,340 --> 00:02:56,980 Llavors jo podria mirar de cada una d'aquelles ciutats de destinació 51 00:02:56,980 --> 00:03:00,650 i pensar en quins llocs Jo podria arribar a 52 00:03:00,650 --> 00:03:03,020 de cadascuna d'aquestes ciutats individuals. 53 00:03:03,020 --> 00:03:07,390 >> Així que potser de Chicago, puc aconseguir un vol directe a San Francisco. 54 00:03:07,390 --> 00:03:09,550 Això és excel·lent. 55 00:03:09,550 --> 00:03:12,360 O podria aconseguir un vol a Denver. 56 00:03:12,360 --> 00:03:16,970 Ara, potser aquest vol a San Francisco és la solució perfecta per a mi, 57 00:03:16,970 --> 00:03:19,530 però potser no. 58 00:03:19,530 --> 00:03:22,180 Potser estic buscant alguna cosa això és una mica més econòmic 59 00:03:22,180 --> 00:03:24,920 o una mica millor per a la meva agenda. 60 00:03:24,920 --> 00:03:29,197 I perquè pogués buscar allò altre possibilitats podrien ser-hi. 61 00:03:29,197 --> 00:03:30,280 Així que podria mirar a Denver. 62 00:03:30,280 --> 00:03:33,870 I a partir de Denver, bé, potser Puc aconseguir un vol a Austin. 63 00:03:33,870 --> 00:03:37,080 I des de Austin, potser pugui aconseguir un vol a Phoenix, i des de Phoenix 64 00:03:37,080 --> 00:03:40,190 a San Francisco. 65 00:03:40,190 --> 00:03:42,730 Ara, jo no he acabat encara. 66 00:03:42,730 --> 00:03:45,640 Perquè potser hi ha una vol directe des de Nova York 67 00:03:45,640 --> 00:03:47,850 a San Francisco, que és perfecte per a mi. 68 00:03:47,850 --> 00:03:53,354 O potser hi ha un vol des de Miami a través de Denver que és molt més barat. 69 00:03:53,354 --> 00:03:54,270 Així que encara he d'anar. 70 00:03:54,270 --> 00:03:58,200 I encara he de mirar a tots els ciutats que no he investigat encara. 71 00:03:58,200 --> 00:04:04,220 He de revisar exhaustivament tots les possibilitats que podria tenir. 72 00:04:04,220 --> 00:04:09,610 >> Així que, des de Nova York, potser pugui aconseguir un vol a Nashville, i des de Nashville 73 00:04:09,610 --> 00:04:10,336 a Austin. 74 00:04:10,336 --> 00:04:11,460 I llavors sé on sóc. 75 00:04:11,460 --> 00:04:14,252 I llavors sé d'Austin, que pugui volar a Phoenix, i des de Phoenix 76 00:04:14,252 --> 00:04:14,960 a San Francisco. 77 00:04:14,960 --> 00:04:18,240 78 00:04:18,240 --> 00:04:22,830 Si vol primer a Miami, però, potser pugui aconseguir un vol de Miami 79 00:04:22,830 --> 00:04:25,080 a Nashville, o des de Miami a Austin. 80 00:04:25,080 --> 00:04:27,950 81 00:04:27,950 --> 00:04:30,860 >> I ara ho he intentat tot de les possibilitats. 82 00:04:30,860 --> 00:04:36,310 He construït aquest gràfic que em mostra totes les possibles rutes 83 00:04:36,310 --> 00:04:37,790 que jo podria ser capaç de prendre. 84 00:04:37,790 --> 00:04:40,510 85 00:04:40,510 --> 00:04:43,640 Quan representem aquests tipus de problemes, 86 00:04:43,640 --> 00:04:47,870 no representarem elles explícitament com aquest gràfic, 87 00:04:47,870 --> 00:04:51,590 perquè aquest gràfic no representa la història d'on hem anat. 88 00:04:51,590 --> 00:04:55,260 Sabent que vaig volar de Phoenix a San Francisco 89 00:04:55,260 --> 00:05:01,690 no dir-me si he vingut a través Nashville, o per mitjà de Denver, o per mitjà de Miami. 90 00:05:01,690 --> 00:05:06,430 >> Llavors, què faré en canvi és Em quedo amb aquest mateix problema, 91 00:05:06,430 --> 00:05:09,140 i vaig a representar com un arbre. 92 00:05:09,140 --> 00:05:14,300 I a l'arrel de l'arbre, al dalt, vaig a posar el lloc en què vaig començar, 93 00:05:14,300 --> 00:05:16,590 Boston. 94 00:05:16,590 --> 00:05:19,310 I a partir de Boston, ho veuré de totes les possibles ubicacions 95 00:05:19,310 --> 00:05:20,380 que puc viatjar. 96 00:05:20,380 --> 00:05:25,480 Bé, en aquest cas, jo tenia tres, Chicago, Nova York i Miami. 97 00:05:25,480 --> 00:05:29,850 I després vaig a explorar cadascun aquests nens en l'arbre. 98 00:05:29,850 --> 00:05:32,690 >> Des de Chicago, vaig veure que tenia dos vols. 99 00:05:32,690 --> 00:05:35,940 Podia volar directament a Sant Francesc o Denver. 100 00:05:35,940 --> 00:05:37,740 Ara San Francisco, que és el meu objectiu. 101 00:05:37,740 --> 00:05:39,790 Aquest és el meu destí. 102 00:05:39,790 --> 00:05:42,220 Això va ser un full d'aquest arbre. 103 00:05:42,220 --> 00:05:45,340 És a dir, jo mai vaig a anar algun lloc després de Sant Francesc. 104 00:05:45,340 --> 00:05:47,850 105 00:05:47,850 --> 00:05:50,340 De Denver, però, Puc volar des de Denver 106 00:05:50,340 --> 00:05:54,220 a Austin, d'Austin a Phoenix, i des de Phoenix a San Francisco. 107 00:05:54,220 --> 00:05:56,050 I ara de nou, he arribat a un full. 108 00:05:56,050 --> 00:05:59,470 109 00:05:59,470 --> 00:06:03,980 >> Llavors podria tornar a la següent ciutat que no he explorat. 110 00:06:03,980 --> 00:06:07,440 Això seria Nova York, anar de nou fins a la part superior del meu arbre, 111 00:06:07,440 --> 00:06:09,160 venir a Nova York. 112 00:06:09,160 --> 00:06:12,700 Des de Nova York, puc volar a Nashville, de Nashville a Austin, 113 00:06:12,700 --> 00:06:17,290 d'Austin a Phoenix, i de Phoenix a San Francisco. 114 00:06:17,290 --> 00:06:20,170 I, finalment, una ciutat en la qual no han mirat encara, de Miami. 115 00:06:20,170 --> 00:06:24,600 >> Bé, des de Miami em va dir que jo tenia de dos possibilitats, Nashville o Austin. 116 00:06:24,600 --> 00:06:28,810 Si vol a Nashville, bé, llavors jo vol de Nashville, a Austin, a Phoenix, 117 00:06:28,810 --> 00:06:29,640 a San Francisco. 118 00:06:29,640 --> 00:06:33,600 Si vol a Austin, vol Austin, a Phoenix, a San Francisco. 119 00:06:33,600 --> 00:06:36,340 I ara tinc un arbre. 120 00:06:36,340 --> 00:06:37,230 És un arbre. 121 00:06:37,230 --> 00:06:41,890 És tot de les possibilitats i tots els camins que podria prendre. 122 00:06:41,890 --> 00:06:44,310 És a dir, si em poso al arrel de l'arbre a la part superior 123 00:06:44,310 --> 00:06:47,860 i me'n vaig a un dels deixa, em diu, no només 124 00:06:47,860 --> 00:06:50,480 on vaig a acabar, Sant Francesc, 125 00:06:50,480 --> 00:06:53,670 però em diu que la ruta que He de prendre per arribar-hi. 126 00:06:53,670 --> 00:06:56,400 127 00:06:56,400 --> 00:06:59,690 >> Ara, quin d'ells és el millor? 128 00:06:59,690 --> 00:07:02,430 Bé, res d'això problema encara em diu 129 00:07:02,430 --> 00:07:04,710 quina d'elles és la millor solució. 130 00:07:04,710 --> 00:07:09,270 Potser em preocupo més sobre la quantitat de temps que estic en l'aire, 131 00:07:09,270 --> 00:07:12,350 o la distància que estic volant. 132 00:07:12,350 --> 00:07:16,410 En aquest cas, Chicago a Sant Francisco podria ser el nombre més curt 133 00:07:16,410 --> 00:07:18,910 de milles en l'aire. 134 00:07:18,910 --> 00:07:20,860 >> Potser m'importa el cost. 135 00:07:20,860 --> 00:07:23,680 I tots sabem vols directes solen ser més cars. 136 00:07:23,680 --> 00:07:26,610 Així que potser si prenc aquesta tipus de ruta cap enrere 137 00:07:26,610 --> 00:07:30,650 per Miami, Nashville, Austin, Phoenix, potser llavors 138 00:07:30,650 --> 00:07:34,070 Em surt un preu més baix. 139 00:07:34,070 --> 00:07:36,440 Però podria optimitzar en qualsevol criteris que m'importen. 140 00:07:36,440 --> 00:07:39,790 Qui té el millor de vol Wi-Fi, o que 141 00:07:39,790 --> 00:07:43,110 aeroports tenen la millor menjar disponible. 142 00:07:43,110 --> 00:07:47,280 I cada un dels que podria dóna'm una solució diferent 143 00:07:47,280 --> 00:07:49,215 que veig com el millor. 144 00:07:49,215 --> 00:07:51,990 145 00:07:51,990 --> 00:07:54,400 >> Aquest tipus de problemes, on anem 146 00:07:54,400 --> 00:07:58,480 per construir aquest arbre de possibilitats, i després 147 00:07:58,480 --> 00:08:02,100 mirar a cada un dels camins individuals, i examinar 148 00:08:02,100 --> 00:08:05,270 quines d'aquestes fulfills un criteri per a nosaltres, 149 00:08:05,270 --> 00:08:08,790 anem a trucar els problemes de cerca. 150 00:08:08,790 --> 00:08:11,280 I tenim un munt de algoritmes, alguns dels quals 151 00:08:11,280 --> 00:08:15,270 hem vist ja, per anar i explorar aquests arbres. 152 00:08:15,270 --> 00:08:19,270 Podríem fer-ho de la manera que jo acabo de fer una recerca en profunditat, 153 00:08:19,270 --> 00:08:22,900 baixant pel que pugui fins que colpejar un full, i després tornar cap amunt, 154 00:08:22,900 --> 00:08:24,787 i va dret cap avall. 155 00:08:24,787 --> 00:08:26,870 O podríem fer el que és anomenada recerca en amplitud. 156 00:08:26,870 --> 00:08:29,675 Podríem ampliar tot a la part superior, i després 157 00:08:29,675 --> 00:08:31,550 tot el que una línia sota d'això, i després 158 00:08:31,550 --> 00:08:35,240 tot el que una línia per sota d'això. 159 00:08:35,240 --> 00:08:41,250 Aquests arbres de cerca són fonamentals per a la IA. 160 00:08:41,250 --> 00:08:46,570 Però ells no arriben a obtenir el correcte tot el temps. 161 00:08:46,570 --> 00:08:51,600 De fet, en molts dels casos que realment importa, 162 00:08:51,600 --> 00:08:54,430 volem construir un arbre, però no ho fem realitat 163 00:08:54,430 --> 00:08:57,140 arribar a fer totes les decisions. 164 00:08:57,140 --> 00:09:00,940 >> Aquestes són situacions trucades Cerca acusatori, també conegut 165 00:09:00,940 --> 00:09:05,390 com la forma d'escriure de jocs de joc sistemes i els paga per això. 166 00:09:05,390 --> 00:09:07,940 Però aquests són els tipus dels sistemes on 167 00:09:07,940 --> 00:09:12,920 podria arribar a triar quan vaig de Boston, que la ciutat em passi a la següent. 168 00:09:12,920 --> 00:09:19,990 Però després d'això, algú podria obtenir per prendre la decisió sobre on jo vol. 169 00:09:19,990 --> 00:09:24,040 Així que per construir aquests tipus d'estructures, estem 170 00:09:24,040 --> 00:09:28,510 va haver de prendre una mica enfocament diferent a ella. 171 00:09:28,510 --> 00:09:31,060 No serem capaços de només has de buscar a través de l'arbre 172 00:09:31,060 --> 00:09:35,000 més, perquè no estem el que té el control 173 00:09:35,000 --> 00:09:38,180 de cada un d'aquests punts de decisió. 174 00:09:38,180 --> 00:09:42,590 >> Així que imaginem una senzilla joc com el tic-tac-toe. 175 00:09:42,590 --> 00:09:46,730 Podria començar amb una tauler completament en blanc. 176 00:09:46,730 --> 00:09:49,580 I en tic-tac-dit del peu, X arriba a jugar primer. 177 00:09:49,580 --> 00:09:53,890 I pel que podia pensar en tot el possibles moviments que X podria fer. 178 00:09:53,890 --> 00:09:57,420 I si jo sóc el joc la X, que és gran. 179 00:09:57,420 --> 00:10:01,020 Tinc nou possibles moviments que PUC. 180 00:10:01,020 --> 00:10:05,000 Podria posar una X en qualsevol d'aquests nou posicions. 181 00:10:05,000 --> 00:10:10,710 >> I després de cada un dels, I podia imaginar el que succeirà després. 182 00:10:10,710 --> 00:10:14,130 Doncs bé, en aquest cas, l'altre jugador podria arribar a fer un volt. 183 00:10:14,130 --> 00:10:15,660 O podria arribar a fer un volt. 184 00:10:15,660 --> 00:10:19,510 I a partir de cada un d'ells, hi ha seria vuit llocs diferents 185 00:10:19,510 --> 00:10:22,980 O que podria posar el seu marcador. 186 00:10:22,980 --> 00:10:25,790 >> Diguem que jo vaig decidir que jo era posarà una X al centre. 187 00:10:25,790 --> 00:10:28,810 Això sempre sembla com un bon moviment d'obertura. 188 00:10:28,810 --> 00:10:34,870 Podia mirar sota d'això, la vuit moviments possibles que O fa. 189 00:10:34,870 --> 00:10:37,320 Ara bé, si estic jugant X, això és meravellós. 190 00:10:37,320 --> 00:10:41,740 Tinc l'oportunitat de triar quin d'ells em anar a, l'un al centre. 191 00:10:41,740 --> 00:10:45,000 Però ara O ha de triar. 192 00:10:45,000 --> 00:10:48,750 I jo no tinc control sobre aquesta decisió. 193 00:10:48,750 --> 00:10:51,670 >> Però a partir de cada un dels possibles posicions de taula, 194 00:10:51,670 --> 00:10:54,020 hi ha després una altra conjunt de possibilitats. 195 00:10:54,020 --> 00:10:56,700 Quan es tracta de ser el meu torn de nou, ho faria 196 00:10:56,700 --> 00:11:01,500 arribar a escollir i dir, bé, O si es mou en el, bé, 197 00:11:01,500 --> 00:11:06,110 el punt mig a l'esquerra, a continuació, Tinc un conjunt de possibilitats 198 00:11:06,110 --> 00:11:09,740 on puc prendre el meu proper moviment. 199 00:11:09,740 --> 00:11:14,140 D'aquests, jo podria considerar tots les possibilitats sota d'ells. 200 00:11:14,140 --> 00:11:18,030 I llavors O obtindria per triar entre aquells. 201 00:11:18,030 --> 00:11:22,290 >> I podria seguir construint aquest arbre a terme fins que va arribar al punt 202 00:11:22,290 --> 00:11:26,960 on sigui algú guanya el game-- que és 203 00:11:26,960 --> 00:11:31,070 Ha de ser considerada un full node-- o la junta està completament ple 204 00:11:31,070 --> 00:11:32,704 i ningú ha guanyat. 205 00:11:32,704 --> 00:11:34,370 I això també va a ser un node fulla. 206 00:11:34,370 --> 00:11:35,411 Això serà un empat. 207 00:11:35,411 --> 00:11:37,820 208 00:11:37,820 --> 00:11:41,680 >> Però la cosa difícil amb això és si això fos només una cerca normal 209 00:11:41,680 --> 00:11:44,269 problema, jo seria capaç de diguem, bé, X hauria d'anar aquí. 210 00:11:44,269 --> 00:11:45,560 I O ha d'anar molt més enllà. 211 00:11:45,560 --> 00:11:46,770 I llavors X ha d'anar per aquí. 212 00:11:46,770 --> 00:11:48,269 I llavors O ha d'anar molt més enllà. 213 00:11:48,269 --> 00:11:51,860 I llavors X pot aconseguir tres en una fila, i jo guanyo. 214 00:11:51,860 --> 00:11:54,870 I el joc hauria acabat en cinc moviments, tres per a mi, 215 00:11:54,870 --> 00:11:57,710 2 per a la meva oponent. 216 00:11:57,710 --> 00:12:01,300 Però no sempre em donen a triar això. 217 00:12:01,300 --> 00:12:03,720 >> Així que en comptes, del que som va a haver de fer 218 00:12:03,720 --> 00:12:06,270 és que tindrem tenir una nova estratègia. 219 00:12:06,270 --> 00:12:09,350 I l'estratègia que algoritmes joc de papers solen utilitzar 220 00:12:09,350 --> 00:12:12,000 és el que s'anomena minimax. 221 00:12:12,000 --> 00:12:15,500 La idea central de minimax és que estem 222 00:12:15,500 --> 00:12:21,365 anar a recollir el moviment que dóna nostre adversari la pitjor quantitat possible 223 00:12:21,365 --> 00:12:22,790 de moviments que poden fer. 224 00:12:22,790 --> 00:12:25,570 225 00:12:25,570 --> 00:12:28,870 No em fa cap bé triar un moviment on 226 00:12:28,870 --> 00:12:31,952 Jo podria ser capaç de guanyar després que, a causa de la meva oponent no és 227 00:12:31,952 --> 00:12:33,160 em va donar aquesta oportunitat. 228 00:12:33,160 --> 00:12:37,770 Van a triar algun horrible resultat per a mi. 229 00:12:37,770 --> 00:12:42,010 Així que em vaig a fer el moviment que obliga al meu oponent 230 00:12:42,010 --> 00:12:45,760 fer alguna cosa millor per a mi. 231 00:12:45,760 --> 00:12:46,260 Tot bé. 232 00:12:46,260 --> 00:12:48,410 Anem a veure com es desenvolupa. 233 00:12:48,410 --> 00:12:51,640 Així que aquí està el nostre algoritme en pseudocodi. 234 00:12:51,640 --> 00:12:54,450 Anem a generar tot l'arbre de joc. 235 00:12:54,450 --> 00:12:56,757 Construirem tota l'estructura. 236 00:12:56,757 --> 00:12:57,840 I després anirem a través. 237 00:12:57,840 --> 00:13:02,100 I a la part inferior en cadascuna de les nodes terminals, en cadascuna de les fulles, 238 00:13:02,100 --> 00:13:07,850 avaluarem com valuós és que a mi? 239 00:13:07,850 --> 00:13:11,690 I anem a valorar les coses que són bones per a mi com ser positiu. 240 00:13:11,690 --> 00:13:14,460 Les coses que no són bones per a mi serà menys positiu, o zero, 241 00:13:14,460 --> 00:13:16,480 o fins i tot negatiu. 242 00:13:16,480 --> 00:13:19,240 >> Així que en el tic-tac-dit del peu, potser una victòria per a mi és bo. 243 00:13:19,240 --> 00:13:20,290 Aquesta és una pregunta. 244 00:13:20,290 --> 00:13:22,400 I un empat és zero. 245 00:13:22,400 --> 00:13:26,230 I una cosa que és una pèrdua per mi, potser això és una negativa. 246 00:13:26,230 --> 00:13:29,620 Tot el que importa és que el millor que és per a mi, a major puntuació 247 00:13:29,620 --> 00:13:32,160 que rep. 248 00:13:32,160 --> 00:13:36,690 A partir d'aquestes possibilitats en el part inferior, a continuació, anem a filtrar cap amunt. 249 00:13:36,690 --> 00:13:40,650 I quan és la meva oportunitat de triar entre un conjunt d'alternatives, 250 00:13:40,650 --> 00:13:44,460 Vaig a triar el que sigui va obtenir la puntuació més alt. 251 00:13:44,460 --> 00:13:47,200 >> I cada vegada que és el meu opositors tornen a triar, 252 00:13:47,200 --> 00:13:52,350 Vaig a assumir que van a triar el que tingui la puntuació més baixa. 253 00:13:52,350 --> 00:13:56,090 I si faig això tot el camí fins a la part superior de l'arbre, 254 00:13:56,090 --> 00:14:03,150 T'he triat un camí que dóna mi el millor resultat que puc aconseguir, 255 00:14:03,150 --> 00:14:09,110 suposant que el meu oponent fa tots els moviments correctes. 256 00:14:09,110 --> 00:14:11,940 >> Molt bé, així que anem a veure això en acció primer. 257 00:14:11,940 --> 00:14:14,980 I després anem a realitat mirar el codi per a això. 258 00:14:14,980 --> 00:14:16,780 Així que imaginin tinc aquest gran arbre. 259 00:14:16,780 --> 00:14:18,280 I ara no estic jugant tic-tac-toe. 260 00:14:18,280 --> 00:14:20,405 Volia donar-li cosa una mica més ric. 261 00:14:20,405 --> 00:14:23,560 Així que tinc una mica de joc en el qual hi ha molts diferents puntuacions 262 00:14:23,560 --> 00:14:26,390 que jo pogués tenir en el final. 263 00:14:26,390 --> 00:14:27,980 I així jo construir aquest arbre. 264 00:14:27,980 --> 00:14:29,070 I arribo a moure primer. 265 00:14:29,070 --> 00:14:31,290 Estic a l'arrel de l'arbre. 266 00:14:31,290 --> 00:14:36,150 >> I puc triar que-- la qual cosa obtenir per maximitzar a través d'aquest primer node. 267 00:14:36,150 --> 00:14:38,410 I llavors el meu oponent arriba a anar. 268 00:14:38,410 --> 00:14:41,910 I després he d'anar un cop més. 269 00:14:41,910 --> 00:14:46,830 Així que a baix en el fons, tinc un conjunt de possibilitats que puc triar, 270 00:14:46,830 --> 00:14:50,570 diferents estats terminals de joc. 271 00:14:50,570 --> 00:14:54,980 Si estic en aquest extrema esquerra cantonada, 272 00:14:54,980 --> 00:14:58,867 i veig que tinc una opció entre un vuit, set, i dos, 273 00:14:58,867 --> 00:15:00,450 bé, jo sóc el que ha de triar. 274 00:15:00,450 --> 00:15:02,910 Així que vaig a triar el millor un d'aquests. 275 00:15:02,910 --> 00:15:05,650 Vaig a triar el vuit. 276 00:15:05,650 --> 00:15:10,090 >> Així que sé que si mai baixar a aquest punt, 277 00:15:10,090 --> 00:15:13,890 Vaig a ser capaç d'aconseguir que els vuit punts. 278 00:15:13,890 --> 00:15:17,410 Si terme en el següent punt sobre, el següent node a través, 279 00:15:17,410 --> 00:15:20,760 1 nou, u, o 6, bé, estic va a triar la millor d'elles. 280 00:15:20,760 --> 00:15:21,950 Vaig a triar als nou. 281 00:15:21,950 --> 00:15:24,880 Si he de triar entre 2, i quatre, i un, 282 00:15:24,880 --> 00:15:28,240 Vaig a triar els quatre, el més alt. 283 00:15:28,240 --> 00:15:31,990 >> Ara, si miro a nivell sobre d'això, el meu oponent 284 00:15:31,990 --> 00:15:34,440 és el que arriba a prendre aquesta decisió. 285 00:15:34,440 --> 00:15:37,040 Així que el meu oponent arriba a trio, vull donar-li 286 00:15:37,040 --> 00:15:39,250 el que està passant per aconseguir que vuit punts, 287 00:15:39,250 --> 00:15:41,916 o no li dono el que és va a donar-li nou punts, 288 00:15:41,916 --> 00:15:45,240 o el que està passant per donar-li quatre punts? 289 00:15:45,240 --> 00:15:49,130 I el meu oponent, sent racional, que està passant 290 00:15:49,130 --> 00:15:53,470 per triar el mínim dels, es va a triar dels quatre. 291 00:15:53,470 --> 00:15:56,020 >> I jo puc fer això a través de tot l'arbre. 292 00:15:56,020 --> 00:15:59,110 Jo puc anar a que ajust mitjana de tres. 293 00:15:59,110 --> 00:16:01,517 I puc triar entre un, tres-cinc. 294 00:16:01,517 --> 00:16:02,350 I tinc l'oportunitat de triar. 295 00:16:02,350 --> 00:16:03,810 Així que trio un cinc. 296 00:16:03,810 --> 00:16:05,340 Puc triar tres, nou, o dos. 297 00:16:05,340 --> 00:16:07,570 Tinc l'oportunitat de triar, així que trio el nou. 298 00:16:07,570 --> 00:16:09,290 Sis, cinc, o dos, jo trio. 299 00:16:09,290 --> 00:16:11,539 Tinc l'oportunitat de triar el sis. 300 00:16:11,539 --> 00:16:13,080 Nivell per sobre d'això, qui va a triar? 301 00:16:13,080 --> 00:16:16,280 302 00:16:16,280 --> 00:16:18,140 Qui ha de triar? 303 00:16:18,140 --> 00:16:20,000 L'altre noi, el meu oponent. 304 00:16:20,000 --> 00:16:22,583 Així que triïn 5, 09:00, o sis, quin? 305 00:16:22,583 --> 00:16:23,410 >> AUDIÈNCIA: El cinc. 306 00:16:23,410 --> 00:16:25,250 >> ALTAVEU: Trien els cinc. 307 00:16:25,250 --> 00:16:27,400 Arriben a triar el mínim. 308 00:16:27,400 --> 00:16:29,690 I després l'últim, triar un, dos, o tres. 309 00:16:29,690 --> 00:16:31,720 Tinc l'oportunitat de triar, així que escollir tres. 310 00:16:31,720 --> 00:16:34,370 Nou, set, o dos, em trien nou. 311 00:16:34,370 --> 00:16:37,070 I 11, sis, o quatre, trio 11. 312 00:16:37,070 --> 00:16:41,190 El meu oponent i després tria tres, 09:00, 11 o, tria el mínim. 313 00:16:41,190 --> 00:16:43,290 Ell em dóna un 3. 314 00:16:43,290 --> 00:16:47,780 I, finalment, a la part superior de l'arbre, he de triar de nou. 315 00:16:47,780 --> 00:16:51,190 I tinc l'oportunitat de triar entre quatre, cinc, o tres. 316 00:16:51,190 --> 00:16:52,270 Així que em prenc el cinc. 317 00:16:52,270 --> 00:16:55,070 318 00:16:55,070 --> 00:17:00,891 >> Si he de controlar-ho tot, m'agradaria prendre el camí que va portar a la 11. 319 00:17:00,891 --> 00:17:02,390 Però no he de fer aquesta elecció. 320 00:17:02,390 --> 00:17:04,220 Si vaig per aquest camí. 321 00:17:04,220 --> 00:17:10,710 El meu oponent m'obligarà a l'elecció que condueix a un 3. 322 00:17:10,710 --> 00:17:14,530 Així que el millor que puc fer és prendre aquesta branca mitjana, 323 00:17:14,530 --> 00:17:19,859 prendre aquesta decisió que és, finalment, em va portar a cinc punts. 324 00:17:19,859 --> 00:17:23,230 Això és el que fa minimax. 325 00:17:23,230 --> 00:17:23,807 >> Tot bé. 326 00:17:23,807 --> 00:17:24,890 Anem a fer una ullada a això. 327 00:17:24,890 --> 00:17:27,480 328 00:17:27,480 --> 00:17:32,330 Així que aquí al CS50 IDE és un programa que 329 00:17:32,330 --> 00:17:36,540 implementa minimax per jugar tic-tac-toe. 330 00:17:36,540 --> 00:17:40,100 Construirem una representació. 331 00:17:40,100 --> 00:17:44,390 Tindrem de dos opponent-- o dos jugadors, el nostre ordinador 332 00:17:44,390 --> 00:17:46,090 jugador i un jugador humà. 333 00:17:46,090 --> 00:17:48,980 334 00:17:48,980 --> 00:17:53,090 El jugador número u serà jugant l'O Aquest serà el jugador de la màquina. 335 00:17:53,090 --> 00:17:55,747 Arriben a moure segons. 336 00:17:55,747 --> 00:17:57,830 I l'altre jugador, la nostra jugador humà, serà X. 337 00:17:57,830 --> 00:17:59,880 >> I per fer de la meva vida una mica simple, vaig 338 00:17:59,880 --> 00:18:03,060 etiquetar aquest jugador negativa. 339 00:18:03,060 --> 00:18:05,026 Així que només puc multiplicar per un de negatiu per intercanviar 340 00:18:05,026 --> 00:18:06,400 entre un jugador i l'altre. 341 00:18:06,400 --> 00:18:09,030 342 00:18:09,030 --> 00:18:12,250 Molt bé, així que anem a fer una ullada a el que estem realment va a fer. 343 00:18:12,250 --> 00:18:15,840 Anem a definir la nostra junta. 344 00:18:15,840 --> 00:18:19,060 Serà, bé, anem per permetre que sigui de tres per tres, 345 00:18:19,060 --> 00:18:21,580 o fins i tot podem jugar cinc per cinc o set 346 00:18:21,580 --> 00:18:28,870 a les set de tic-tac-toe Si voleu de la mateixa manera que, basant-se alguna dimensió D. 347 00:18:28,870 --> 00:18:31,260 >> I tindrem un parell de funcions d'ajuda 348 00:18:31,260 --> 00:18:34,360 que va a fer les coses com inicialitzar el screen-- o ho sento, 349 00:18:34,360 --> 00:18:38,900 inicialitzar les nostres variables, desactivi la pantalla, dibuixar el tauler a la pantalla, 350 00:18:38,900 --> 00:18:41,060 ha una que comprova una taula per veure si és o no 351 00:18:41,060 --> 00:18:44,520 hi ha un guanyador, que analitza a través de la línia d'ordres, 352 00:18:44,520 --> 00:18:50,670 només per ajudar, un que llegeix d'entrada, i una funció anomenada minimax. 353 00:18:50,670 --> 00:18:52,746 I això és el anem preocupem més sobre. 354 00:18:52,746 --> 00:18:54,120 Però vegem primer en el principal. 355 00:18:54,120 --> 00:18:57,490 356 00:18:57,490 --> 00:18:58,510 >> Què fem? 357 00:18:58,510 --> 00:19:00,570 Bé, anem a analitzar la nostra línia d'ordres, 358 00:19:00,570 --> 00:19:04,300 acabo de llegir i veure el taula de dimensió ens agradaria tenir. 359 00:19:04,300 --> 00:19:07,330 Anem a inicialitzem la nostra junta. 360 00:19:07,330 --> 00:19:10,360 I després entrarem en un llaç salvatge gran, en repetides ocasions 361 00:19:10,360 --> 00:19:16,630 acceptar mou fins que el joc és bestiar, o no hi ha cap moviment a l'esquerra. 362 00:19:16,630 --> 00:19:20,560 Cada vegada que anem a través d'aquest llaç, anem a esborrar la pantalla. 363 00:19:20,560 --> 00:19:23,290 Anem a dibuixar el tauler a la pantalla. 364 00:19:23,290 --> 00:19:28,750 I estem deliberadament tipus de abstreure aquestes lluny com subrutines, 365 00:19:28,750 --> 00:19:32,030 de manera que no hem de preocupar-se massa sobre els detalls de la forma en què es produeixin. 366 00:19:32,030 --> 00:19:33,480 >> Vas a tenir el codi més tard avui. 367 00:19:33,480 --> 00:19:37,970 I si vols mirar a través de i esbrinar, es pot veure tots ells. 368 00:19:37,970 --> 00:19:39,890 Però anem a dibuixar una taula a la pantalla. 369 00:19:39,890 --> 00:19:43,620 I després anem a comprovar i veure, tenim un guanyador? 370 00:19:43,620 --> 00:19:46,290 Algú ha guanyat aquest joc? 371 00:19:46,290 --> 00:19:49,260 Si és així, anem a imprimir un missatge de victòria. 372 00:19:49,260 --> 00:19:51,680 I anem a acabar el joc. 373 00:19:51,680 --> 00:19:54,510 >> També Comprovarem i veure si hi ha un empat. 374 00:19:54,510 --> 00:19:56,620 Serà fàcil veure si hi ha un empat. 375 00:19:56,620 --> 00:20:00,700 Això vol dir que tots els espais estan plens, però no ha estat un guanyador encara. 376 00:20:00,700 --> 00:20:03,580 Podem declarar un empat i per fer. 377 00:20:03,580 --> 00:20:10,530 Llavors la veritable meat-- si és un jugador de la màquina, 378 00:20:10,530 --> 00:20:14,120 permetrem que jugador de la màquina a la recerca 379 00:20:14,120 --> 00:20:19,500 mitjançant l'ús d'aquest algorisme minimax, per trobar la millor mesura que es pot. 380 00:20:19,500 --> 00:20:22,310 I després posarem que es mouen cap amunt. 381 00:20:22,310 --> 00:20:27,640 >> Altrament, si es tracta d'un jugador humà, llegirem algunes aportacions de l'humà. 382 00:20:27,640 --> 00:20:30,800 I després si és l'ésser humà jugador o el jugador de la màquina, 383 00:20:30,800 --> 00:20:32,800 farem un parell mica bits de comprovació d'errors, 384 00:20:32,800 --> 00:20:36,910 assegureu-vos que es manté dins dels límits de les dimensions reals de la junta 385 00:20:36,910 --> 00:20:40,040 que tenim, assegureu-vos que aquest espai està buit, 386 00:20:40,040 --> 00:20:43,570 que ningú va posar una peça en allà ja. 387 00:20:43,570 --> 00:20:45,810 I llavors només haurem de posar una peça en el tauler, 388 00:20:45,810 --> 00:20:51,550 canviar el jugador a la següent capa, i incrementar el nombre de moviments han succeït. 389 00:20:51,550 --> 00:20:54,090 >> Aquest és el bucle principal de el nostre joc tic-tac-toe. 390 00:20:54,090 --> 00:20:57,000 391 00:20:57,000 --> 00:21:02,340 Minimax, llavors, és exactament l'algoritme que abans. 392 00:21:02,340 --> 00:21:04,710 L'únic ajust que hem fet el que hem 393 00:21:04,710 --> 00:21:07,290 pot jugar més alta taules dimensionals és que hem 394 00:21:07,290 --> 00:21:11,070 guardat aquest paràmetre extra anomenat profunditat. 395 00:21:11,070 --> 00:21:14,870 I la profunditat només diu, si estic buscar cap avall a través d'aquest arbre 396 00:21:14,870 --> 00:21:19,022 i em poso tan avall més enllà d'una certa profunditat nivell 397 00:21:19,022 --> 00:21:20,730 que jo simplement no vull per anar més lluny, 398 00:21:20,730 --> 00:21:25,630 Vaig a parar i simplement avaluar la junta en aquest punt. 399 00:21:25,630 --> 00:21:27,310 Vaig a comprovar i veure si hi ha un guanyador. 400 00:21:27,310 --> 00:21:29,240 Si hi ha un guanyador, jo els torno. 401 00:21:29,240 --> 00:21:31,720 Altrament, vaig a anar a través d'un bucle. 402 00:21:31,720 --> 00:21:34,380 I vaig a dir, per a tots les possibles ubicacions 403 00:21:34,380 --> 00:21:38,080 pugui jo prendre la meva moviment, vaig a 404 00:21:38,080 --> 00:21:43,760 construir una taula hipotètica que inclou un dels meus moviments en aquest tauler, 405 00:21:43,760 --> 00:21:45,960 i després crida recursivament minimax. 406 00:21:45,960 --> 00:21:49,360 407 00:21:49,360 --> 00:21:53,900 >> Si es tracta d'un dels meus moviments, em surt per trobar el un que té la puntuació més gran. 408 00:21:53,900 --> 00:21:58,710 Si es tracta de la decisió del meu oponent, trobem el que té la puntuació mínima. 409 00:21:58,710 --> 00:22:02,240 I tota la resta és manteniment sol registre. 410 00:22:02,240 --> 00:22:04,789 Molt bé, així que anem a veure aquesta cursa. 411 00:22:04,789 --> 00:22:06,830 En realitat, potser puguem aconseguir un parell de voluntaris 412 00:22:06,830 --> 00:22:09,930 per venir i jugar tic-tac-toe. 413 00:22:09,930 --> 00:22:12,780 [Inaudible] un, i un més, dues, just aquí. 414 00:22:12,780 --> 00:22:13,550 Anem cap amunt. 415 00:22:13,550 --> 00:22:19,290 416 00:22:19,290 --> 00:22:23,650 >> Així que seguirem endavant i reiniciar aquest completament. 417 00:22:23,650 --> 00:22:24,150 Així, hola. 418 00:22:24,150 --> 00:22:24,920 >> AUDIÈNCIA: Hola. 419 00:22:24,920 --> 00:22:25,420 >> ALTAVEU: Quin és el teu nom? 420 00:22:25,420 --> 00:22:26,086 >> AUDIÈNCIA: Gorav. 421 00:22:26,086 --> 00:22:26,840 ALTAVEU: Gorav. 422 00:22:26,840 --> 00:22:27,800 >> AUDIÈNCIA: Sóc Layla. 423 00:22:27,800 --> 00:22:29,490 >> ALTAVEU: I Layla, i Layla, ho sento. 424 00:22:29,490 --> 00:22:30,384 Anem cap amunt. 425 00:22:30,384 --> 00:22:32,050 Gorav, anem a haver d'anar primer. 426 00:22:32,050 --> 00:22:37,710 I vaig a demanar-li que ser un no terriblement bon jugador tic-tac-toe. 427 00:22:37,710 --> 00:22:40,130 OK, així que tota la pressió està fora de tu. 428 00:22:40,130 --> 00:22:44,660 Anem a veure, però, que la nostra màquina El jugador pot realment fer alguna cosa intel·ligent. 429 00:22:44,660 --> 00:22:45,310 Així que endavant. 430 00:22:45,310 --> 00:22:49,830 Vostè va a escriure en el qual coordinarà que li agradaria posar el seu X en. 431 00:22:49,830 --> 00:22:55,170 A0, OK, i la màquina s'ha anat immediatament i posar la seva marca en A1. 432 00:22:55,170 --> 00:22:56,640 >> Poseu la O al tauler. 433 00:22:56,640 --> 00:22:58,970 Molt bé, ara seguir endavant. 434 00:22:58,970 --> 00:23:00,193 On voldries anar? 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 El nostre jugador de la màquina ha pres la plaça central, es va bloquejar. 438 00:23:08,430 --> 00:23:10,320 Així que va ser una bona, el més intel·ligent perquè ho faci. 439 00:23:10,320 --> 00:23:13,430 440 00:23:13,430 --> 00:23:14,250 Vostè ha bloquejat. 441 00:23:14,250 --> 00:23:15,210 Això és excel·lent. 442 00:23:15,210 --> 00:23:16,390 Es treu el córner allà. 443 00:23:16,390 --> 00:23:23,890 444 00:23:23,890 --> 00:23:30,430 >> I que va a obligar-te a prendre l'últim espai, B0. 445 00:23:30,430 --> 00:23:32,220 I el joc acaba en empat. 446 00:23:32,220 --> 00:23:35,030 Però va tenir un raonable joc en contra de vostè, ¿no? 447 00:23:35,030 --> 00:23:36,956 Molt bé, moltes gràcies, Gorav. 448 00:23:36,956 --> 00:23:40,860 >> [Aplaudiments] 449 00:23:40,860 --> 00:23:44,723 >> Molt bé, Layla, anem el joc d'aquí. 450 00:23:44,723 --> 00:23:46,940 >> AUDIÈNCIA: Oh, genial. 451 00:23:46,940 --> 00:23:49,950 >> ALTAVEU: Anem a donar que quatre per quatre tic-tac-toe. 452 00:23:49,950 --> 00:23:54,760 Ara, en quatre per quatre, el que has de guanyar amb quatre partits en fila, no tres en una fila. 453 00:23:54,760 --> 00:23:56,135 I és tot teu. 454 00:23:56,135 --> 00:24:02,180 455 00:24:02,180 --> 00:24:04,420 Així Layla va prendre D1. 456 00:24:04,420 --> 00:24:11,730 Ara seguirem nostre jugador de l'ordinador aquí. 457 00:24:11,730 --> 00:24:16,910 De tres en tres tic-tac-dit del peu és el tipus de cosa que és fàcil per a tots nosaltres. 458 00:24:16,910 --> 00:24:21,960 Però tot i així és agradable veure el jugador de l'ordinador fent moviments intel·ligents. 459 00:24:21,960 --> 00:24:23,725 Quatre per quatre arriba a ser una mica més complicat. 460 00:24:23,725 --> 00:24:42,960 461 00:24:42,960 --> 00:24:44,230 >> Ben fet. 462 00:24:44,230 --> 00:24:46,210 Molt bé, així que Layla de rematar. 463 00:24:46,210 --> 00:24:48,270 Ah, i que hauria d'haver acabat allà. 464 00:24:48,270 --> 00:24:51,870 Però farem una més aquí. 465 00:24:51,870 --> 00:24:53,480 Així que Layla, gràcies. 466 00:24:53,480 --> 00:24:55,112 Ben fet. 467 00:24:55,112 --> 00:24:57,517 >> [Aplaudiments] 468 00:24:57,517 --> 00:25:00,410 469 00:25:00,410 --> 00:25:04,750 >> Així que el nostre reproductor de tic-tac-toe va a través i descobreix llocs, 470 00:25:04,750 --> 00:25:07,040 resol usant aquest minimax. 471 00:25:07,040 --> 00:25:08,990 I jo tenia un ajust de profunditat en que perquè es 472 00:25:08,990 --> 00:25:11,010 no aniria massa ràpid, que és probablement la raó per 473 00:25:11,010 --> 00:25:16,790 Layla va ser capaç d'anar molt bé abans com ho va fer, i ho va fer molt bé. 474 00:25:16,790 --> 00:25:20,450 Però aquests sistemes que simplement anar a través i la força bruta 475 00:25:20,450 --> 00:25:23,870 anar més profund, i més profund, i més profund, i seguir trobant la solució 476 00:25:23,870 --> 00:25:29,890 que necessiten, aquest tipus de sistemes són força èxit en aquests, així, 477 00:25:29,890 --> 00:25:32,700 jocs de taula estàndard. 478 00:25:32,700 --> 00:25:37,060 >> I de fet, si ens fixem en un de tres en tres joc tic-tac-dit del peu, 479 00:25:37,060 --> 00:25:40,040 això és bàsicament un problema resolt. 480 00:25:40,040 --> 00:25:45,430 I això és un diagrama meravellosa de Randall Munroe en XKCD, 481 00:25:45,430 --> 00:25:52,130 mostrant què vostè ha de moure prendre, tenint en compte els moviments del teu oponent. 482 00:25:52,130 --> 00:25:56,420 Això és una cosa que vam poder especificar fàcilment abans d'hora. 483 00:25:56,420 --> 00:26:00,180 Però, què passa quan arribem a més jocs complexos, jocs més complexos, 484 00:26:00,180 --> 00:26:05,690 on hi ha taules més grans, més possibilitats, l'estratègia més profunda? 485 00:26:05,690 --> 00:26:09,660 >> Resulta que aquest força bruta buscant encara 486 00:26:09,660 --> 00:26:14,150 fa raonablement bé, excepte quan arribis al punt 487 00:26:14,150 --> 00:26:19,230 on aquest arbre és tan gran que no es pot representar tot. 488 00:26:19,230 --> 00:26:22,370 489 00:26:22,370 --> 00:26:28,280 Quan no es pot calcular tot l'arbre, quan no es pot anar cap endavant i empenta 490 00:26:28,280 --> 00:26:32,204 a tu mateix fins al punt on vostè ha aconseguit tot l'arbre en la memòria, 491 00:26:32,204 --> 00:26:34,370 o si ho pot aconseguir en la memòria i s'acaba 492 00:26:34,370 --> 00:26:39,200 portarà massa temps per buscar a través de ell, vostè ha de fer alguna cosa més intel·ligent. 493 00:26:39,200 --> 00:26:42,620 494 00:26:42,620 --> 00:26:46,450 >> Per tal de fer això, ha de fer dues coses. 495 00:26:46,450 --> 00:26:49,030 En primer lloc, vostè ha de trobar alguna manera de limitar la seva profunditat. 496 00:26:49,030 --> 00:26:50,370 Bé, això està bé. 497 00:26:50,370 --> 00:26:55,740 Podem trobar algunes bones, mínim i dir, només es pot anar tan profund. 498 00:26:55,740 --> 00:27:00,890 Però quan ho fa, que significa tenir aquests taulers parcialment incompletes. 499 00:27:00,890 --> 00:27:04,770 I vostè ha de triar, el que m'agrada aquest tauler parcialment incompleta, 500 00:27:04,770 --> 00:27:08,600 o aquest tauler parcialment incomplet? 501 00:27:08,600 --> 00:27:11,910 >> I en els nostres quatre per quatre jocs tic-tac-dit del peu, 502 00:27:11,910 --> 00:27:15,240 nostre jugador de l'ordinador es va baixar a la part inferior i es va dir, 503 00:27:15,240 --> 00:27:16,800 Tinc dues taules diferents. 504 00:27:16,800 --> 00:27:17,940 Cap dels dos és una victòria. 505 00:27:17,940 --> 00:27:19,120 Cap dels dos és una pèrdua. 506 00:27:19,120 --> 00:27:22,070 Cap dels dos és un empat. 507 00:27:22,070 --> 00:27:24,100 Com puc escollir entre ells? 508 00:27:24,100 --> 00:27:26,200 I no tenia un forma intel·ligent de fer-ho. 509 00:27:26,200 --> 00:27:28,910 510 00:27:28,910 --> 00:27:32,850 >> Veiem aquest tipus de Avaluació passa tot el temps 511 00:27:32,850 --> 00:27:35,290 a mesura que en els jocs més complexos. 512 00:27:35,290 --> 00:27:37,600 Els escacs és un gran exemple. 513 00:27:37,600 --> 00:27:41,550 En els escacs, tenim, en primer lloc de tot, un tauler més gran. 514 00:27:41,550 --> 00:27:43,370 Tenim molts més peces. 515 00:27:43,370 --> 00:27:47,930 I el posicionament d'aquestes peces i la forma en què aquestes peces es mouen 516 00:27:47,930 --> 00:27:50,370 és de vital importància. 517 00:27:50,370 --> 00:27:53,700 Així que si vull fer servir minimax, He de ser capaç d'especificar 518 00:27:53,700 --> 00:27:58,240 i dir, aquest tauler, on ningú ha guanyat o perdut, però, 519 00:27:58,240 --> 00:28:04,310 és d'alguna manera millor que aquesta altra tauler, on ningú ha guanyat o perdut. 520 00:28:04,310 --> 00:28:06,740 >> Per fer això, jo podria fer coses com jo podria 521 00:28:06,740 --> 00:28:10,787 comptar quantes tinc i totes les tens? 522 00:28:10,787 --> 00:28:12,870 O podria donar diferents peces diferents punts. 523 00:28:12,870 --> 00:28:14,420 El meu reina val 20 punts. 524 00:28:14,420 --> 00:28:16,500 El seu peó val un punt. 525 00:28:16,500 --> 00:28:18,920 Qui té més punts en total? 526 00:28:18,920 --> 00:28:22,300 O podria considerar coses com: qui té la millor posició al tauler? 527 00:28:22,300 --> 00:28:26,820 A qui li toca el pròxim, tot el que puc 528 00:28:26,820 --> 00:28:31,220 no per avaluar amb més precisió quina d'aquestes possibilitats 529 00:28:31,220 --> 00:28:34,660 és millor sense tenint en compte de manera exhaustiva 530 00:28:34,660 --> 00:28:36,565 cada moviment que podria venir després d'això. 531 00:28:36,565 --> 00:28:39,740 532 00:28:39,740 --> 00:28:45,130 >> Ara per fer aquest treball, una de les coses que és 533 00:28:45,130 --> 00:28:48,680 serà realment important per a nosaltres no és només movent recta 534 00:28:48,680 --> 00:28:53,720 fins a una profunditat particular, límit, però ser capaç de dir, 535 00:28:53,720 --> 00:28:59,380 d'aquestes idees que jo tenir és tan dolent que és 536 00:28:59,380 --> 00:29:02,280 No val la pena considerar totes les possibles formes 537 00:29:02,280 --> 00:29:06,680 que les coses poden anar de mal en pitjor. 538 00:29:06,680 --> 00:29:12,760 Per a això, anem a afegir a minimax un principi anomenat alph-beta. 539 00:29:12,760 --> 00:29:16,340 I alfa-beta diu, si vostè té una mala idea, 540 00:29:16,340 --> 00:29:22,840 no perdis el teu temps intentant saber exactament el dolent que és. 541 00:29:22,840 --> 00:29:24,990 >> Així que aquí és el que farem. 542 00:29:24,990 --> 00:29:28,620 Anem a prendre la mateixa principis que teníem abans, 543 00:29:28,620 --> 00:29:32,200 el mateix tipus minimax de recerca, només estem 544 00:29:32,200 --> 00:29:37,570 va un seguiment, no només de la valors reals que tenim, però anem a 545 00:29:37,570 --> 00:29:41,440 realitzar un seguiment de la millor manera possible valor que podria aconseguir, 546 00:29:41,440 --> 00:29:45,700 i el pitjor possible resultat que podria tenir. 547 00:29:45,700 --> 00:29:50,470 I cada vegada el pitjor possible Ho està buscant probable, 548 00:29:50,470 --> 00:29:52,694 Vaig a abandonar aquesta part de l'arbre. 549 00:29:52,694 --> 00:29:54,610 I no vaig tan sols es molesten mirant més. 550 00:29:54,610 --> 00:29:57,680 551 00:29:57,680 --> 00:30:02,600 >> Molt bé, així que imaginem que comencem amb aquest mateix arbre exacta joc. 552 00:30:02,600 --> 00:30:05,200 I ara anirem de nou, fins al fons 553 00:30:05,200 --> 00:30:07,200 a aquesta cantonada inferior esquerra. 554 00:30:07,200 --> 00:30:11,180 I en aquesta part inferior esquerra cantonada, ens mirem i avaluem aquest fòrum. 555 00:30:11,180 --> 00:30:15,700 Potser és un quatre per quatre tic-tac-toe tauler, o potser és un tauler d'escacs. 556 00:30:15,700 --> 00:30:18,620 Però ho mirem i avaluem , I obtenim un valor de vuit. 557 00:30:18,620 --> 00:30:22,290 558 00:30:22,290 --> 00:30:28,030 >> En aquest punt, sabem que anem a aconseguir almenys 559 00:30:28,030 --> 00:30:32,380 vuit punts d'aquesta decisió final. 560 00:30:32,380 --> 00:30:36,620 No importa el que l'altre 2 són, què set i que dos. 561 00:30:36,620 --> 00:30:38,580 Podrien ser qualsevol valor volien ser. 562 00:30:38,580 --> 00:30:41,279 Anem a arribar a menys vuit punts. 563 00:30:41,279 --> 00:30:43,070 Molt bé, però que vam poder seguir endavant i comprovar. 564 00:30:43,070 --> 00:30:45,080 Potser un d'ells és millor que huit. 565 00:30:45,080 --> 00:30:46,000 >> Ens fixem en els set. 566 00:30:46,000 --> 00:30:46,910 ¿Això és millor que huit? 567 00:30:46,910 --> 00:30:48,680 No, això no canvia la nostra opinió en absolut. 568 00:30:48,680 --> 00:30:49,460 Ens fixem en els dos. 569 00:30:49,460 --> 00:30:50,543 ¿Això és millor que huit? 570 00:30:50,543 --> 00:30:52,580 No, això no canvia la nostra opinió en absolut. 571 00:30:52,580 --> 00:30:55,480 Així que ara que sabem que hem esgotat totes les possibilitats allà. 572 00:30:55,480 --> 00:30:58,330 No anem a aconseguir res millor que huit. 573 00:30:58,330 --> 00:31:01,310 Aconseguirem exactament 8. 574 00:31:01,310 --> 00:31:03,825 >> I així canviem aquest node i per exemple, és ara una certesa. 575 00:31:03,825 --> 00:31:07,010 576 00:31:07,010 --> 00:31:10,270 Vam pujar un nivell per sobre d'això. 577 00:31:10,270 --> 00:31:13,820 I ara sabem alguna cosa sobre aquest nivell de minimització. 578 00:31:13,820 --> 00:31:18,560 Sabem que mai arribarem més de vuit punts si baixen 579 00:31:18,560 --> 00:31:20,910 aquesta direcció. 580 00:31:20,910 --> 00:31:22,980 Perquè fins i tot si els altres dues branques resulten 581 00:31:22,980 --> 00:31:26,170 a ser fantàstic i val la pena milers de punts cada un, 582 00:31:26,170 --> 00:31:31,666 nostre oponent ens donarà la mínim, i ens donen les vuit. 583 00:31:31,666 --> 00:31:32,790 Molt bé, bé, anem a veure. 584 00:31:32,790 --> 00:31:35,190 Seguirem endavant per aquest camí. 585 00:31:35,190 --> 00:31:38,490 Baixem a la mitjana de l'esquerra. 586 00:31:38,490 --> 00:31:40,560 Mirem cap avall i veiem que hi ha un nou. 587 00:31:40,560 --> 00:31:45,590 Sabem que anem a aconseguir almenys nou punts per anar a baix 588 00:31:45,590 --> 00:31:47,720 aquest camí mig. 589 00:31:47,720 --> 00:31:52,110 I en aquest punt, només podem fer una pausa. 590 00:31:52,110 --> 00:31:56,910 I podem dir, mira, conèixer en el nivell anterior, 591 00:31:56,910 --> 00:32:01,160 Vaig a tenir no més de vuit assenyala baixant aquesta direcció. 592 00:32:01,160 --> 00:32:05,670 Però si anava per la meitat camí en lloc del camí de l'esquerra, 593 00:32:05,670 --> 00:32:08,980 M'agradaria tenir almenys nou punts. 594 00:32:08,980 --> 00:32:13,590 >> El meu oponent mai va a m'ho dius a mi anar per aquest camí mig. 595 00:32:13,590 --> 00:32:14,650 Arriben a triar. 596 00:32:14,650 --> 00:32:18,140 I ells van a triar el ruta a l'esquerra en direcció als vuit, 597 00:32:18,140 --> 00:32:23,650 en lloc de pel centre cap el que hi ha almenys nou punts. 598 00:32:23,650 --> 00:32:25,334 Així que en aquest moment, vaig a deixar. 599 00:32:25,334 --> 00:32:26,500 I vaig a dir, saps què? 600 00:32:26,500 --> 00:32:29,990 Jo no he de mirar més avall en aquesta direcció. 601 00:32:29,990 --> 00:32:32,270 Perquè jo mai vaig a arribar-hi. 602 00:32:32,270 --> 00:32:36,660 >> Puc passar per alt que un, i puc passar per alt que 6, 603 00:32:36,660 --> 00:32:39,720 perquè això mai succeirà. 604 00:32:39,720 --> 00:32:42,470 Així que vaig a anar cap avall i vaig a considerar la següent possibilitat. 605 00:32:42,470 --> 00:32:44,830 Vaig allà i em dic, veig un dos. 606 00:32:44,830 --> 00:32:47,125 Sé que si em poso a aquí, estic aconseguirà almenys dos. 607 00:32:47,125 --> 00:32:49,810 608 00:32:49,810 --> 00:32:50,470 D'ACORD. 609 00:32:50,470 --> 00:32:51,520 Segueixo endavant. 610 00:32:51,520 --> 00:32:52,440 Veig un quatre. 611 00:32:52,440 --> 00:32:54,920 Sé que vaig a aconseguir almenys quatre. 612 00:32:54,920 --> 00:32:57,200 Encara hi ha molt entre 04:08, però. 613 00:32:57,200 --> 00:32:58,454 Així que segueixo endavant. 614 00:32:58,454 --> 00:32:59,870 Miro cap avall i veig que hi ha un. 615 00:32:59,870 --> 00:33:01,614 Està bé, sé que si Vaig per aquest camí, 616 00:33:01,614 --> 00:33:03,280 Jo seré capaç de triar els quatre. 617 00:33:03,280 --> 00:33:06,540 618 00:33:06,540 --> 00:33:08,980 El que el meu oponent va a fer? 619 00:33:08,980 --> 00:33:12,310 Entre una cosa que em dóna 08:00, una cosa que em dona quatre, 620 00:33:12,310 --> 00:33:14,730 i una cosa que em dóna, almenys, nou, 621 00:33:14,730 --> 00:33:17,550 bo, ell em va donar als quatre. 622 00:33:17,550 --> 00:33:20,110 I sé que ara al el més alt, em vaig 623 00:33:20,110 --> 00:33:23,145 ser capaç d'aconseguir almenys quatre punts sobre aquest joc. 624 00:33:23,145 --> 00:33:27,030 625 00:33:27,030 --> 00:33:30,900 >> La idea d'alfa-beta és tallar parts de l'arbre per 626 00:33:30,900 --> 00:33:32,530 que jo no miro més. 627 00:33:32,530 --> 00:33:35,964 Però encara es veu com si hagués estat mirant un munt d'arbre. 628 00:33:35,964 --> 00:33:36,880 Anem a mantenir a la baixa. 629 00:33:36,880 --> 00:33:38,305 Baixarem el següent moment. 630 00:33:38,305 --> 00:33:39,680 En el fons, em sembla un u. 631 00:33:39,680 --> 00:33:41,030 Sé que vaig a aconseguir almenys un. 632 00:33:41,030 --> 00:33:41,690 Segueixo buscant. 633 00:33:41,690 --> 00:33:42,625 >> Em sembla un 3. 634 00:33:42,625 --> 00:33:44,250 Sé que vaig a aconseguir almenys tres. 635 00:33:44,250 --> 00:33:44,840 Segueixo endavant. 636 00:33:44,840 --> 00:33:45,660 Em sembla un cinc. 637 00:33:45,660 --> 00:33:49,760 Sé que tindré de cinc si em poso en aquest camí. 638 00:33:49,760 --> 00:33:52,580 I també sé llavors que el meu oponent, si 639 00:33:52,580 --> 00:33:55,510 triar el mitjà de els tres grans opcions, 640 00:33:55,510 --> 00:34:01,440 ell va a donar-me cosa que és cinc o menys. 641 00:34:01,440 --> 00:34:02,150 >> D'ACORD. 642 00:34:02,150 --> 00:34:03,400 Puc seguir allà. 643 00:34:03,400 --> 00:34:06,470 Puc mirar cap avall i jo pot dir, què vaig 644 00:34:06,470 --> 00:34:08,239 aconseguir si vaig pel camí del mig? 645 00:34:08,239 --> 00:34:09,909 Jo vaig a aconseguir, així, tres allà. 646 00:34:09,909 --> 00:34:12,080 Vaig a aconseguir alguna cosa això és almenys tres. 647 00:34:12,080 --> 00:34:16,030 Encara hi ha coses entre 03:05, de manera que seguir buscant. 648 00:34:16,030 --> 00:34:20,203 Oh, 1 nou, vaig definitivament prendre que més d'un 3. 649 00:34:20,203 --> 00:34:22,744 Vaig a aconseguir almenys nou si em vaig per aquest camí mig. 650 00:34:22,744 --> 00:34:25,530 651 00:34:25,530 --> 00:34:31,010 >> Ara la meva oponent s'atura i diu: mira, no té sentit ja. 652 00:34:31,010 --> 00:34:33,669 Jo sé que el meu oponent minimització, ell és 653 00:34:33,669 --> 00:34:36,210 em va donar el que és menys d'o igual a cinc, 654 00:34:36,210 --> 00:34:39,030 en lloc del que és major o igual a nou. 655 00:34:39,030 --> 00:34:39,530 M'aturo. 656 00:34:39,530 --> 00:34:40,779 No em veig més en això. 657 00:34:40,779 --> 00:34:43,280 Segueixo endavant. 658 00:34:43,280 --> 00:34:44,850 >> Miro cap avall en aquest cas. 659 00:34:44,850 --> 00:34:46,370 Fins al fons, em sembla un 6. 660 00:34:46,370 --> 00:34:50,040 Sé que vaig a aconseguir almenys sis. 661 00:34:50,040 --> 00:34:53,130 I què puc fer jo? 662 00:34:53,130 --> 00:34:54,877 Jo puc parar. 663 00:34:54,877 --> 00:34:57,460 Perquè hi ha una elecció entre cosa que és com a mínim sis 664 00:34:57,460 --> 00:34:59,250 i una cosa que és menys de cinc, que és 665 00:34:59,250 --> 00:35:02,570 em va donar la cosa això és menys de cinc. 666 00:35:02,570 --> 00:35:04,779 I ara sé que vaig per obtenir exactament aquesta elecció. 667 00:35:04,779 --> 00:35:06,195 Vaig a aconseguir que 5 elecció. 668 00:35:06,195 --> 00:35:08,980 669 00:35:08,980 --> 00:35:10,010 >> Torno al cim. 670 00:35:10,010 --> 00:35:11,450 Què vaig a triar entre una cosa 671 00:35:11,450 --> 00:35:14,449 això és més gran o igual a quatre, o alguna cosa que és igual a cinc? 672 00:35:14,449 --> 00:35:17,140 Me'n vaig a prendre alguna cosa això és, almenys, cinc anys. 673 00:35:17,140 --> 00:35:20,490 Vaig per l'última ruta, tot el camí fins a la part inferior. 674 00:35:20,490 --> 00:35:21,260 Hi ha un. 675 00:35:21,260 --> 00:35:23,410 Acceptar, almenys jo vaig a aconseguir un punt. 676 00:35:23,410 --> 00:35:24,427 Segueixo endavant. 677 00:35:24,427 --> 00:35:25,760 Dos, oh, això és millor que un. 678 00:35:25,760 --> 00:35:27,100 Vaig a aconseguir almenys dues. 679 00:35:27,100 --> 00:35:28,610 Em sembla un 3. 680 00:35:28,610 --> 00:35:31,450 Sé que vaig a tenir tres. 681 00:35:31,450 --> 00:35:34,690 >> I el punt per sobre d'això, el meu oponent va 682 00:35:34,690 --> 00:35:38,540 que em donés alguna cosa que és menor o igual a tres. 683 00:35:38,540 --> 00:35:40,940 I ara puc parar. 684 00:35:40,940 --> 00:35:46,290 A causa de que en l'elecció entre mi ser capaç d'aconseguir un cinc i el meu oponent 685 00:35:46,290 --> 00:35:52,290 donar-me una mica menys de tres, Jo sempre vaig a tenir que cinc. 686 00:35:52,290 --> 00:35:56,810 Així que no avaluo que part inferior de l'arbre en absolut. 687 00:35:56,810 --> 00:35:59,470 >> Ara, això pot semblar menor. 688 00:35:59,470 --> 00:36:03,630 Però quan petits trossos de l'aritmètica, més gran que i menor que, 689 00:36:03,630 --> 00:36:10,640 poden tallar parts senceres de aquest arbre que creix exponencialment, 690 00:36:10,640 --> 00:36:14,280 que condueix a una enorme quantitat d'estalvi, estalvi 691 00:36:14,280 --> 00:36:17,630 que són prou grans que jo pot començar a jugar competitivament 692 00:36:17,630 --> 00:36:21,330 en els jocs més complexos. 693 00:36:21,330 --> 00:36:27,030 >> Molt bé, si ens fixem en la grandària i la complexitat dels diferents jocs, 694 00:36:27,030 --> 00:36:29,470 tic-tac-toe era el nostre senzill exemple. 695 00:36:29,470 --> 00:36:32,150 Tenim una taula petita, de tres en tres. 696 00:36:32,150 --> 00:36:36,030 Tenim, com a màxim, una mitjana de prop de quatre opcions diferents 697 00:36:36,030 --> 00:36:38,440 a mesura que avancem en el joc. 698 00:36:38,440 --> 00:36:42,720 Tenim algun lloc al voltant de 10 a la cinquè possibles fulles diferents. 699 00:36:42,720 --> 00:36:45,200 I la construcció d'un tres en ratlla jugador, així, només ho va fer. 700 00:36:45,200 --> 00:36:47,460 És fàcil. 701 00:36:47,460 --> 00:36:49,890 >> Si pugem a alguna cosa més complexa, com Connecta Quatre. 702 00:36:49,890 --> 00:36:53,170 Te'n recordes d'aquest joc on li cau les petites fitxes en? 703 00:36:53,170 --> 00:36:58,490 És un tauler de sis per set, No és molt més gran, encara 704 00:36:58,490 --> 00:37:00,770 té aproximadament la mateixa ramificació factoritzar com tic-tac-toe. 705 00:37:00,770 --> 00:37:05,410 Tinc unes quatre opcions on puc posar les coses en. 706 00:37:05,410 --> 00:37:10,760 Però ara, tinc molt més condueix, 10 elevat a 21. 707 00:37:10,760 --> 00:37:14,440 Això és una cosa que és fàcil n'hi ha prou que es resol immediatament. 708 00:37:14,440 --> 00:37:17,560 >> Dames, més complex-- va aconseguir un vuit per vuit bord. 709 00:37:17,560 --> 00:37:20,570 Vostè és només en la meitat de en qualsevol moment, però. 710 00:37:20,570 --> 00:37:24,930 Vostè té una ramificació factor que és aproximadament 2,8. 711 00:37:24,930 --> 00:37:28,160 Bé, tenim un parell moviments que pot prendre. 712 00:37:28,160 --> 00:37:33,870 Tens 10 a les fulles 31ª, espais més grans i més grans, i més gran. 713 00:37:33,870 --> 00:37:37,340 Com he de buscar a través de aquests espais cada vegada més grans, 714 00:37:37,340 --> 00:37:42,220 que és quan coses com alfa-beta i ser capaç de tallar branques senceres 715 00:37:42,220 --> 00:37:44,420 esdevé essencial. 716 00:37:44,420 --> 00:37:47,440 >> Ara, les dames era bastant fàcil en 1992. 717 00:37:47,440 --> 00:37:51,400 Un programa d'ordinador anomenat Chinook va vèncer als inspectors món 718 00:37:51,400 --> 00:37:53,590 campió, Marion Tinsley. 719 00:37:53,590 --> 00:37:57,260 I des de llavors, no reproductor mestre humà té 720 00:37:57,260 --> 00:38:02,290 estat capaç de vèncer als millors sistemes computacionals. 721 00:38:02,290 --> 00:38:06,570 Si ens fixem en una mena escacs, ara de nou, tenim un vuit per vuit bord. 722 00:38:06,570 --> 00:38:09,870 Però tenim molt més complex peces, moviments molt més complex. 723 00:38:09,870 --> 00:38:14,610 Comptem amb un factor de ramificació d'aproximadament 35, 35 moviments possibles de mitjana 724 00:38:14,610 --> 00:38:20,030 que puc prendre, i un estat espai, un nombre de fulls 725 00:38:20,030 --> 00:38:28,950 que ha crescut de 10 a la potència 123, un enorme nombre de possibilitats. 726 00:38:28,950 --> 00:38:35,570 >> Tot i això, els processadors moderns són capaços de fer això amb èxit. 727 00:38:35,570 --> 00:38:43,900 El 1995 i després en 1997, un ordinador programa anomenat Deep Blue construït per IBM 728 00:38:43,900 --> 00:38:49,601 que va córrer en un superordinador gegant batre l'actual campió del món, 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 Aquest va ser un punt d'inflexió. 732 00:38:56,650 --> 00:39:00,620 Avui en dia, però, que mateix processament el poder se senti en el meu MacBook. 733 00:39:00,620 --> 00:39:04,180 734 00:39:04,180 --> 00:39:06,440 >> La velocitat de processament manté cada vegada més ràpid i més ràpid. 735 00:39:06,440 --> 00:39:09,500 Podem avaluar més taulers més ràpids i més ràpid. 736 00:39:09,500 --> 00:39:14,550 Però el més important, tenim millor funcions d'avaluació i una millor poda 737 00:39:14,550 --> 00:39:15,460 mètodes. 738 00:39:15,460 --> 00:39:19,560 Així que podem buscar a la espai més complexa. 739 00:39:19,560 --> 00:39:22,350 El major de la junta jocs que podem imaginar, 740 00:39:22,350 --> 00:39:26,310 alguna cosa així com Go que és té un tauler de 19 per 19, 741 00:39:26,310 --> 00:39:32,490 ara, de cop i volta, estem més enllà del punt on els sistemes computacionals poden guanyar. 742 00:39:32,490 --> 00:39:34,530 No hi ha computacional sistema per aquí 743 00:39:34,530 --> 00:39:38,880 que pot vèncer a un jugador professional de Go. 744 00:39:38,880 --> 00:39:45,000 El millor rang d'avui els sistemes s'acosta la classe de bon nivell amateur. 745 00:39:45,000 --> 00:39:49,285 Així que encara hi ha una mica fora allà on no es pot arribar a encara. 746 00:39:49,285 --> 00:39:51,840 747 00:39:51,840 --> 00:39:55,360 >> Molt bé, aquests jocs de taula tradicionals, 748 00:39:55,360 --> 00:39:58,560 aquest tipus de sistemes en què construir aquesta minimax, si té 749 00:39:58,560 --> 00:40:06,300 alfa-beta o no, aquests algoritmes treballen perquè hi ha certes restriccions. 750 00:40:06,300 --> 00:40:08,520 Tenim informació perfecta sobre el món. 751 00:40:08,520 --> 00:40:11,690 Sabem que totes les peces són. 752 00:40:11,690 --> 00:40:13,570 El món és estàtic. 753 00:40:13,570 --> 00:40:16,220 Ningú arriba a moure el peces al voltant mentre estic 754 00:40:16,220 --> 00:40:20,640 assegut allà pensant, prenent el meu torn. 755 00:40:20,640 --> 00:40:23,140 Hi ha un espai d'acció que és discreta. 756 00:40:23,140 --> 00:40:26,900 Jo puc posar el meu afany aquí, o puc posar el meu afany aquí. 757 00:40:26,900 --> 00:40:30,520 No em permet posar la meva obstinació a la línia entre els dos quadrats. 758 00:40:30,520 --> 00:40:34,430 759 00:40:34,430 --> 00:40:36,520 >> I finalment, les accions són deterministes. 760 00:40:36,520 --> 00:40:39,790 Jo sé que si dic, torre a cavaller 3, 761 00:40:39,790 --> 00:40:44,660 la meva torre va a acabar en cavaller tres, sempre i quan es tracta d'un moviment vàlid. 762 00:40:44,660 --> 00:40:47,830 No hi ha incertesa sobre això. 763 00:40:47,830 --> 00:40:52,490 Ara, a mesura que vagi a més diferents tipus de jocs, 764 00:40:52,490 --> 00:40:55,960 hem de trencar aquestes suposicions. 765 00:40:55,960 --> 00:41:00,020 >> I si vaig a alguna cosa com els videojocs clàssics? 766 00:41:00,020 --> 00:41:04,180 Heus aquí una selecció de vídeo jocs de l'Atari 2600. 767 00:41:04,180 --> 00:41:05,180 Què he allà dalt? 768 00:41:05,180 --> 00:41:08,440 Tinc Frogger, Espai Invaders, trampa, i Pac-Man. 769 00:41:08,440 --> 00:41:11,290 770 00:41:11,290 --> 00:41:14,840 Quin tipus d'ambients tinc aquí ara? 771 00:41:14,840 --> 00:41:16,900 Quin d'aquests supòsits ¿He de trencar? 772 00:41:16,900 --> 00:41:19,410 773 00:41:19,410 --> 00:41:21,570 >> Bé, depèn del joc. 774 00:41:21,570 --> 00:41:28,170 Podria jugar escacs en el 2600, i seria com ho era abans. 775 00:41:28,170 --> 00:41:33,020 Per a la majoria d'aquests sistemes, hi ha coneixement complet sobre el món. 776 00:41:33,020 --> 00:41:36,300 Hi ha completament accions determinista. 777 00:41:36,300 --> 00:41:38,330 Però en general, el món de ja no estàtica. 778 00:41:38,330 --> 00:41:41,970 És a dir, mentre estic assegut allà esperant, alguna cosa es mou. 779 00:41:41,970 --> 00:41:44,320 Els fantasmes vénen a buscar-me. 780 00:41:44,320 --> 00:41:46,570 L'escorpí m'està seguint sota. 781 00:41:46,570 --> 00:41:48,880 Els invasors de l'espai són cada vegada més a prop. 782 00:41:48,880 --> 00:41:54,020 783 00:41:54,020 --> 00:41:55,510 Què tan bé podem fer contra això? 784 00:41:55,510 --> 00:41:58,640 785 00:41:58,640 --> 00:42:02,790 >> Fa uns anys, Google hi havia un projecte anomenat 786 00:42:02,790 --> 00:42:12,030 DeepMind, on van entrenar un ordinador programa per jugar jocs d'Atari 2600. 787 00:42:12,030 --> 00:42:16,120 I si vostè pensa que això no és greu negoci, els resultats del seu estudi 788 00:42:16,120 --> 00:42:19,920 es van publicar a la revista Nature, per la qual gairebé tan bo una publicació 789 00:42:19,920 --> 00:42:22,500 com es pot aconseguir possiblement. 790 00:42:22,500 --> 00:42:24,340 I això és el bé que es duen a terme. 791 00:42:24,340 --> 00:42:29,220 >> Tenen un algoritme que es va asseure i va veure només les entrades de la pantalla. 792 00:42:29,220 --> 00:42:34,080 Es va posar cap instrucció en absolut sobre les regles del joc. 793 00:42:34,080 --> 00:42:42,610 I se suposava que esbrinar, basa la seva puntuació, el bé que estava fent. 794 00:42:42,610 --> 00:42:46,560 Això era un sistema que utilitza alguna cosa anomenat aprenentatge per reforç. 795 00:42:46,560 --> 00:42:48,380 És a dir, que es veia en la seva puntuació. 796 00:42:48,380 --> 00:42:51,620 I si té un bon puntuació, va dir, He de recordar aquestes coses. 797 00:42:51,620 --> 00:42:53,310 I que he de fer els de nou. 798 00:42:53,310 --> 00:42:56,450 I si té una mala puntuació, es va dir, No hauria de fer aquestes coses de nou. 799 00:42:56,450 --> 00:42:59,750 800 00:42:59,750 --> 00:43:03,430 >> Aquest és el rendiment d'aquests sistemes formats 801 00:43:03,430 --> 00:43:07,490 permès jugar per a un poques hores en cada joc, 802 00:43:07,490 --> 00:43:12,490 comparat contra els jugadors professionals. 803 00:43:12,490 --> 00:43:19,670 Així que per a tots els jocs que són a la banda esquerra d'aquesta línia, 804 00:43:19,670 --> 00:43:25,920 Aquest programa informàtic autodidacta superat als jugadors professionals. 805 00:43:25,920 --> 00:43:29,690 I perquè tot el dreta, els jugadors professionals 806 00:43:29,690 --> 00:43:30,920 van ser sent el millor. 807 00:43:30,920 --> 00:43:34,040 808 00:43:34,040 --> 00:43:36,850 Per a alguna cosa que sabia res sobre les regles, que 809 00:43:36,850 --> 00:43:43,020 no sabia res de l'estructura de la jocs, es tracta d'un rendiment impressionant. 810 00:43:43,020 --> 00:43:45,660 I això és el que som capaços de fer avui. 811 00:43:45,660 --> 00:43:50,239 >> OK, vostè diu, però si pensar en la IA en els jocs, 812 00:43:50,239 --> 00:43:52,530 Normalment pensem en el coses que podem realitat 813 00:43:52,530 --> 00:43:54,180 seure i jugar en contra. 814 00:43:54,180 --> 00:43:58,760 Si em sento i toco StarCraft, o el joc lliure del tamís, 815 00:43:58,760 --> 00:44:01,870 l'opositor de l'ordinador és la persona que controla els Zerg, 816 00:44:01,870 --> 00:44:06,770 o el control de l'altra civilització. 817 00:44:06,770 --> 00:44:11,920 Com fan els jugadors realment trobar els seus moviments? 818 00:44:11,920 --> 00:44:18,810 >> Bé, aquests jocs estan estructurats de la mateixa manera com els nostres jocs de taula, 819 00:44:18,810 --> 00:44:22,250 aquests jocs que anem a col·lectivament trucar a quatre jocs de X, 820 00:44:22,250 --> 00:44:26,040 explorar, expand-- oblidar les estimats. 821 00:44:26,040 --> 00:44:26,980 Que són ells? 822 00:44:26,980 --> 00:44:32,150 Explora, ampliar i extingir, Crec que és l'últim. 823 00:44:32,150 --> 00:44:36,060 Però són bàsicament exploració i conquesta jocs. 824 00:44:36,060 --> 00:44:41,020 Normalment, l'opositor de l'ordinador allà té informació limitada. 825 00:44:41,020 --> 00:44:45,486 Ells no saben exactament el que està passant darrere d'aquesta boira de la guerra. 826 00:44:45,486 --> 00:44:47,735 Ells no arriben a veure què que té en el seu inventari. 827 00:44:47,735 --> 00:44:50,240 828 00:44:50,240 --> 00:44:52,800 >> Hi ha un ambient que és dinàmic. 829 00:44:52,800 --> 00:44:56,180 Tot està canviant tot el temps. 830 00:44:56,180 --> 00:45:00,290 No et donen per seure i esperar per prendre la seva decisió. 831 00:45:00,290 --> 00:45:02,810 Però la majoria de les coses són encara discreta. 832 00:45:02,810 --> 00:45:04,200 He de posar la meva ciutat aquí. 833 00:45:04,200 --> 00:45:06,750 O he de posar la meva ciutat aquí. 834 00:45:06,750 --> 00:45:08,950 I tot és determinista. 835 00:45:08,950 --> 00:45:14,660 Quan dic, moure la meva unitat aquí, el meu unitat mou aquí, a menys que un obstacle de sobte 836 00:45:14,660 --> 00:45:17,700 entra en joc. 837 00:45:17,700 --> 00:45:21,610 Ara, això no és tot equip jocs que estan per aquí avui en dia. 838 00:45:21,610 --> 00:45:27,320 >> Si vaig i toco un primer tipus persona joc, una mena de lladre o Fallout 839 00:45:27,320 --> 00:45:33,350 o Skyrim o Halo, ara Tinc oponents de l'ordinador 840 00:45:33,350 --> 00:45:37,860 que hi són fora que tenen una situació molt diferent. 841 00:45:37,860 --> 00:45:40,020 Tenen, de nou, la informació limitada. 842 00:45:40,020 --> 00:45:43,420 Ells només poden veure una determinat camp de visió. 843 00:45:43,420 --> 00:45:45,180 El medi ambient és encara dinàmic. 844 00:45:45,180 --> 00:45:48,280 Les coses estan canviant tot el temps. 845 00:45:48,280 --> 00:45:52,300 >> Però ara tinc una molt més espai d'acció contínua. 846 00:45:52,300 --> 00:45:57,170 Puc ser simplement una Fer una ullada mica fora de la porta. 847 00:45:57,170 --> 00:46:00,650 I alguns jocs, el meu accions són estocàstic. 848 00:46:00,650 --> 00:46:04,590 Tinc l'oportunitat de tractar de saltar per sobre d'aquesta paret, però tinc l'oportunitat de fracassar. 849 00:46:04,590 --> 00:46:08,280 850 00:46:08,280 --> 00:46:14,550 Aquest tipus de jocs són cada vegada més a prop i més a prop dels tipus de controladors 851 00:46:14,550 --> 00:46:17,330 que construïm en la robòtica. 852 00:46:17,330 --> 00:46:21,050 >> En robòtica, hem d'assumir que tinguem la informació limitada. 853 00:46:21,050 --> 00:46:23,070 Tenim sensors que ens diuen sobre el món. 854 00:46:23,070 --> 00:46:25,860 Tenim una sempre canviant, entorn dinàmic. 855 00:46:25,860 --> 00:46:30,440 Tenim un món en el qual l'espai és contínua, en lloc de discrets. 856 00:46:30,440 --> 00:46:36,260 I les nostres accions, quan tractem ells, tenen una probabilitat de fracassar. 857 00:46:36,260 --> 00:46:40,960 I de fet, joc modern controladors del teu oponent Halo, 858 00:46:40,960 --> 00:46:48,690 o per a aquells NPCs en Skyrim, bàsicament, executar petites arquitectures robòtica. 859 00:46:48,690 --> 00:46:50,380 >> Senten el món. 860 00:46:50,380 --> 00:46:52,910 Ells construeixen un model del món. 861 00:46:52,910 --> 00:46:57,950 Calculen basen en un conjunt de metes que els agradaria dur a terme. 862 00:46:57,950 --> 00:47:03,110 Planegen accions basades en el que saben. 863 00:47:03,110 --> 00:47:07,940 I aquests són exactament els mateixos tipus dels sistemes que construïm en la robòtica. 864 00:47:07,940 --> 00:47:11,420 Així que aquestes arquitectures, a portar aquest nou junts, 865 00:47:11,420 --> 00:47:14,500 sovint són exactament el mateix. 866 00:47:14,500 --> 00:47:16,340 >> Així que anem a veure si podem veure això. 867 00:47:16,340 --> 00:47:19,210 Tornem al nostre exemple tic-tac-toe. 868 00:47:19,210 --> 00:47:22,690 I jo vaig a demanar un parell de la meva post-docs per arribar i m'ajuden. 869 00:47:22,690 --> 00:47:26,970 Així Chen Ming, i Alessandro, i Olivier, si vostès vindria. 870 00:47:26,970 --> 00:47:32,080 871 00:47:32,080 --> 00:47:35,440 I necessitaré un parell de voluntaris 872 00:47:35,440 --> 00:47:37,590 >> OK, vaig veure un dret mà allà al mig. 873 00:47:37,590 --> 00:47:39,965 Vull aprofitar un més, algú més enrere potser. 874 00:47:39,965 --> 00:47:40,881 Molt bé, per aquí. 875 00:47:40,881 --> 00:47:41,490 Anem cap amunt. 876 00:47:41,490 --> 00:47:44,190 877 00:47:44,190 --> 00:47:45,335 Tot bé. 878 00:47:45,335 --> 00:47:49,490 Així que donem que tapa cap avall. 879 00:47:49,490 --> 00:48:03,700 I si vostès vindrien dret volta per aquí per a mi, fantàstic. 880 00:48:03,700 --> 00:48:06,580 >> Així que aquest és un robot anomenat Baxter. 881 00:48:06,580 --> 00:48:10,880 I Baxter és un robot que és un plataforma comercial, dissenyat 882 00:48:10,880 --> 00:48:13,030 per una companyia anomenada Rethink. 883 00:48:13,030 --> 00:48:16,580 I aquest robot està dissenyat per a la fabricació a petita escala. 884 00:48:16,580 --> 00:48:19,265 Però avui anem a usar-lo per jugar tic-tac-toe. 885 00:48:19,265 --> 00:48:21,930 886 00:48:21,930 --> 00:48:27,150 Ara, aquest robot també és una cosa això és relativament únic. 887 00:48:27,150 --> 00:48:32,950 Perquè si estigués de peu en qualsevol lloc prop d'una automatització de fàbrica estàndard 888 00:48:32,950 --> 00:48:39,580 sistema, jo estaria en molt greu perill de ser ferit. 889 00:48:39,580 --> 00:48:45,600 >> Baxter, però, està dissenyat per a ser relativament segur per interactuar amb. 890 00:48:45,600 --> 00:48:48,680 I perquè pugui seguir endavant aquest robot. 891 00:48:48,680 --> 00:48:52,350 I es pot veure que és una mica poc flexibles, ja que es mou al voltant. 892 00:48:52,350 --> 00:48:57,250 I puc canviar la seva posició on m'agradaria que fos. 893 00:48:57,250 --> 00:49:03,410 Ara bé, en un sistema robòtic normals, tindríem un conjunt d'articulacions aquí 894 00:49:03,410 --> 00:49:07,970 això seria directament respondre a les ordres de posició. 895 00:49:07,970 --> 00:49:13,180 I ells no els importaria necessàriament si es movien a través de l'aire lliure, 896 00:49:13,180 --> 00:49:15,555 o si es movien a través del meu caixa toràcica. 897 00:49:15,555 --> 00:49:18,410 898 00:49:18,410 --> 00:49:19,120 >> D'ACORD. 899 00:49:19,120 --> 00:49:22,090 I en general, si eren aquí amb un sistema industrial, 900 00:49:22,090 --> 00:49:23,400 va anar enlloc a prop seu. 901 00:49:23,400 --> 00:49:26,280 Hi hauria groga cinta de seguretat al seu voltant. 902 00:49:26,280 --> 00:49:28,310 Aquest sistema té una lleugerament diferent disseny 903 00:49:28,310 --> 00:49:32,130 per ser més amable i més fàcil perquè les persones interactuen amb, 904 00:49:32,130 --> 00:49:36,380 perquè en cada conjunt, hi ha un ressort. 905 00:49:36,380 --> 00:49:39,110 I en lloc de controlar una posició exacta, 906 00:49:39,110 --> 00:49:43,110 controlem una certa quantitat de torque, una certa quantitat de força, 907 00:49:43,110 --> 00:49:45,874 que ens agradaria estar en aquesta primavera. 908 00:49:45,874 --> 00:49:47,790 Molt bé, així que em va deixar prendre els nostres voluntaris aquí. 909 00:49:47,790 --> 00:49:48,540 Hola, com et dius? 910 00:49:48,540 --> 00:49:49,010 >> AUDIÈNCIA: Louis. 911 00:49:49,010 --> 00:49:49,635 >> ALTAVEU: Louis. 912 00:49:49,635 --> 00:49:50,490 Encantat de veure't. 913 00:49:50,490 --> 00:49:50,990 ¿I? 914 00:49:50,990 --> 00:49:51,610 >> AUDIÈNCIA: David. 915 00:49:51,610 --> 00:49:51,960 >> ALTAVEU: David. 916 00:49:51,960 --> 00:49:52,550 Encantat de conéixer-te. 917 00:49:52,550 --> 00:49:54,508 Si vostès esperarien aquí per un segon, 918 00:49:54,508 --> 00:49:56,420 Vaig a donar-li l'oportunitat de fer això. 919 00:49:56,420 --> 00:50:00,610 Així que aquest robot, si arribar i si es pressiona suaument sobre ella, 920 00:50:00,610 --> 00:50:03,780 vas a veure que es mou una mica. 921 00:50:03,780 --> 00:50:06,349 I si agafes les coses bé aquí al canell just 922 00:50:06,349 --> 00:50:09,390 per sobre d'on són aquests botons, es sembla que vostè ha de prendre els botons, 923 00:50:09,390 --> 00:50:13,100 però agafa just a sobre de la seva lloc, se li ser capaç de manipular molt suaument 924 00:50:13,100 --> 00:50:14,545 a través de l'espai. 925 00:50:14,545 --> 00:50:15,920 Louis, vol donar-li una oportunitat? 926 00:50:15,920 --> 00:50:19,465 Així que donar-li una mica empenta per començar. 927 00:50:19,465 --> 00:50:23,190 I després si poses els teus dits just allà i aferrar-se a ell, 928 00:50:23,190 --> 00:50:24,807 perquè va a moure per a vostè llavors. 929 00:50:24,807 --> 00:50:27,824 930 00:50:27,824 --> 00:50:29,365 Molt bé, vostè vol donar-li una oportunitat? 931 00:50:29,365 --> 00:50:29,980 Anem cap amunt. 932 00:50:29,980 --> 00:50:32,300 Així que donar-li només un gentil empènyer allà per començar. 933 00:50:32,300 --> 00:50:33,820 Vostè pot sentir el que se sent. 934 00:50:33,820 --> 00:50:40,060 I després, si agafes allà mateix, podràs maniobrar voltant. 935 00:50:40,060 --> 00:50:41,280 >> D'ACORD. 936 00:50:41,280 --> 00:50:47,360 Així Típicament, aquest tipus d'un robot faria ser utilitzat per a la fabricació a petita escala. 937 00:50:47,360 --> 00:50:50,980 I em vaig a moure aquest braç just baix del camí una mica aquí. 938 00:50:50,980 --> 00:50:55,750 Però avui en dia, utilitzarem el mateix sistema de joc tic-tac-toe 939 00:50:55,750 --> 00:50:59,520 basat en Minimax que construïm abans. 940 00:50:59,520 --> 00:51:00,549 D'ACORD? 941 00:51:00,549 --> 00:51:02,340 Així que, vostès són cada jugarà un joc. 942 00:51:02,340 --> 00:51:04,210 Louis, seràs el primer. 943 00:51:04,210 --> 00:51:05,920 Permetin-me sostinc aquí per un segon. 944 00:51:05,920 --> 00:51:10,949 Vaig a tenir posa de peu dret aquí, només perquè tothom pugui veure-ho. 945 00:51:10,949 --> 00:51:11,990 Esteu establir aquí? 946 00:51:11,990 --> 00:51:13,120 >> ROBOT: Benvingut. 947 00:51:13,120 --> 00:51:15,910 Anem a jugar tic-tac-toe. 948 00:51:15,910 --> 00:51:20,860 No adherència el token abans Jo dic que és el seu torn. 949 00:51:20,860 --> 00:51:22,050 Començo el joc. 950 00:51:22,050 --> 00:51:27,900 951 00:51:27,900 --> 00:51:28,750 És el meu torn. 952 00:51:28,750 --> 00:51:47,002 953 00:51:47,002 --> 00:51:50,210 ALTAVEU: Ara, si vostè podria prendre una de les seves peces i seguir endavant i el col·loquen. 954 00:51:50,210 --> 00:51:51,446 ROBOT: És el seu torn. 955 00:51:51,446 --> 00:51:53,430 [El] 956 00:51:53,430 --> 00:51:54,836 És el meu torn. 957 00:51:54,836 --> 00:51:56,820 [El] 958 00:51:56,820 --> 00:52:12,196 959 00:52:12,196 --> 00:52:15,680 [El] 960 00:52:15,680 --> 00:52:16,570 És el seu torn. 961 00:52:16,570 --> 00:52:21,397 962 00:52:21,397 --> 00:52:23,688 ALTAVEU: La raça humana és comptant amb vostès aquí, Louis. 963 00:52:23,688 --> 00:52:27,440 964 00:52:27,440 --> 00:52:28,350 >> ROBOT: És el meu torn. 965 00:52:28,350 --> 00:52:44,810 966 00:52:44,810 --> 00:52:47,015 >> ALTAVEU: Així Baxter bloquejat amb èxit aquí. 967 00:52:47,015 --> 00:52:49,670 968 00:52:49,670 --> 00:52:52,480 >> ROBOT: És el seu torn. 969 00:52:52,480 --> 00:52:53,360 És el meu torn. 970 00:52:53,360 --> 00:53:14,730 971 00:53:14,730 --> 00:53:16,810 És el seu torn. 972 00:53:16,810 --> 00:53:17,760 És el meu torn. 973 00:53:17,760 --> 00:53:21,330 974 00:53:21,330 --> 00:53:23,830 ALTAVEU: I deixarem que Baxter acabar a terme el seu últim moviment aquí. 975 00:53:23,830 --> 00:53:36,622 976 00:53:36,622 --> 00:53:39,090 >> [El] 977 00:53:39,090 --> 00:53:40,480 >> ROBOT: Això és un empat. 978 00:53:40,480 --> 00:53:42,030 Vaig a guanyar la propera vegada. 979 00:53:42,030 --> 00:53:43,365 >> [El] 980 00:53:43,365 --> 00:53:45,210 >> ALTAVEU: Molt bé, moltes gràcies, Louis. 981 00:53:45,210 --> 00:53:46,094 Gràcies. 982 00:53:46,094 --> 00:53:46,980 Vostè pot anar d'aquesta manera. 983 00:53:46,980 --> 00:53:49,759 >> ROBOT: començo el joc. 984 00:53:49,759 --> 00:53:51,800 ALTAVEU: Llavors m'ho dius a mi explicar- a vostè una mica més 985 00:53:51,800 --> 00:53:55,410 poc abans d'arribar a la nostra revenja aquí. 986 00:53:55,410 --> 00:53:57,200 Què és exactament que està passant? 987 00:53:57,200 --> 00:53:59,430 Així que el robot té una càmera a sobre de la tapa aquí. 988 00:53:59,430 --> 00:54:01,330 I està mirant cap avall en el tauler. 989 00:54:01,330 --> 00:54:04,470 I està veient si que té una junta de color vermell o blau 990 00:54:04,470 --> 00:54:10,450 i X. blanc Com aquells aconseguir col·loca en el tauler, que és bàsicament la mateixa entrada 991 00:54:10,450 --> 00:54:13,890 que estaríem llegint des la nostra estructura de dades de la nostra pantalla. 992 00:54:13,890 --> 00:54:17,290 S'està corrent la mateixa algoritme minimax sigui 993 00:54:17,290 --> 00:54:21,010 capaços de trobar on col·locar un bon senyal. 994 00:54:21,010 --> 00:54:24,820 >> I llavors li estem donant una ordre sobre on ens agradaria una fitxa per a ser col·locat. 995 00:54:24,820 --> 00:54:26,120 El braç es mou cap a fora. 996 00:54:26,120 --> 00:54:31,750 Es tracta d'utilitzar una pinça de buit per aplicar alguns de succió per a aquesta peça de fusta, 997 00:54:31,750 --> 00:54:35,240 recollir-lo, moure'l a la dreta lloc i, a continuació, deixeu anar la succió 998 00:54:35,240 --> 00:54:36,950 i deixar-lo anar. 999 00:54:36,950 --> 00:54:38,990 Molt bé, anem per donar-li una oportunitat més 1000 00:54:38,990 --> 00:54:40,930 amb un jugador una mica més intel·ligent aquí. 1001 00:54:40,930 --> 00:54:42,290 Estàs preparat? 1002 00:54:42,290 --> 00:54:46,150 Molt bé, si parava fins aquí i donar A-- resultar d'aquesta manera 1003 00:54:46,150 --> 00:54:47,955 perquè pugui veure tothom. 1004 00:54:47,955 --> 00:54:48,830 I després [inaudible]. 1005 00:54:48,830 --> 00:54:49,330 >> ROBOT: És el meu torn. 1006 00:54:49,330 --> 00:54:50,455 >> ALTAVEU: Baxter, s'iniciarà. 1007 00:54:50,455 --> 00:55:10,750 1008 00:55:10,750 --> 00:55:11,730 És el seu torn. 1009 00:55:11,730 --> 00:55:16,490 1010 00:55:16,490 --> 00:55:17,520 És el meu torn. 1011 00:55:17,520 --> 00:55:38,740 1012 00:55:38,740 --> 00:55:39,690 És el seu torn. 1013 00:55:39,690 --> 00:55:46,330 1014 00:55:46,330 --> 00:55:47,165 És el meu torn. 1015 00:55:47,165 --> 00:56:01,252 1016 00:56:01,252 --> 00:56:06,192 >> [El] 1017 00:56:06,192 --> 00:56:08,542 >> ALTAVEU: [WHISPERING] Just ho va deixar anar endavant i guanyar. 1018 00:56:08,542 --> 00:56:09,500 ROBOT: És el seu torn. 1019 00:56:09,500 --> 00:56:15,099 1020 00:56:15,099 --> 00:56:15,890 ALTAVEU: Això està bé. 1021 00:56:15,890 --> 00:56:20,390 1022 00:56:20,390 --> 00:56:21,360 >> ROBOT: És el meu torn. 1023 00:56:21,360 --> 00:56:24,825 1024 00:56:24,825 --> 00:56:26,805 >> [El] 1025 00:56:26,805 --> 00:56:42,650 1026 00:56:42,650 --> 00:56:43,510 >> Jo guanyo. 1027 00:56:43,510 --> 00:56:45,620 >> [El] 1028 00:56:45,620 --> 00:56:46,595 >> Començo el joc. 1029 00:56:46,595 --> 00:56:48,261 >> ALTAVEU: Molt bé, moltes gràcies. 1030 00:56:48,261 --> 00:56:50,180 1031 00:56:50,180 --> 00:56:55,590 Molt bé, crec que tenim temps per una més excel·lent jugador de tic-tac-dit del peu, 1032 00:56:55,590 --> 00:57:00,490 algú que pot posar aquesta cosa coincideixen, que sap el que estan fent. 1033 00:57:00,490 --> 00:57:03,010 >> [El] 1034 00:57:03,010 --> 00:57:05,560 >> Qui serà el nostre campió aquí? 1035 00:57:05,560 --> 00:57:08,110 Molt bé, els seus amics li va oferir. 1036 00:57:08,110 --> 00:57:11,190 Això és suficient per a mi. 1037 00:57:11,190 --> 00:57:12,194 Digues-me el teu nom una altra vegada. 1038 00:57:12,194 --> 00:57:12,860 AUDIÈNCIA: Tamir. 1039 00:57:12,860 --> 00:57:14,193 ALTAVEU: Tamir, m'alegro de veure't. 1040 00:57:14,193 --> 00:57:19,270 Molt bé, de nou, anem a posar-li fins aquí perquè tothom pugui veure-ho. 1041 00:57:19,270 --> 00:57:22,070 Vostè és el nostre representant en aquest partit ara. 1042 00:57:22,070 --> 00:57:24,540 Baxter és un i oh i oh. 1043 00:57:24,540 --> 00:57:26,300 O ho sento, un oh i un. 1044 00:57:26,300 --> 00:57:27,490 I li toca a vostè aquí. 1045 00:57:27,490 --> 00:57:29,340 Baxter s'arriba a moure primer, però. 1046 00:57:29,340 --> 00:57:30,435 So. 1047 00:57:30,435 --> 00:57:31,310 ROBOT: És el meu torn. 1048 00:57:31,310 --> 00:57:45,226 1049 00:57:45,226 --> 00:57:48,208 >> [El] 1050 00:57:48,208 --> 00:57:52,720 1051 00:57:52,720 --> 00:57:55,780 >> És el seu torn. 1052 00:57:55,780 --> 00:57:56,845 És el meu torn. 1053 00:57:56,845 --> 00:58:18,130 1054 00:58:18,130 --> 00:58:18,965 És el seu torn. 1055 00:58:18,965 --> 00:58:28,751 1056 00:58:28,751 --> 00:58:30,248 És el meu torn. 1057 00:58:30,248 --> 00:58:51,210 1058 00:58:51,210 --> 00:58:52,160 És el seu torn. 1059 00:58:52,160 --> 00:59:00,854 1060 00:59:00,854 --> 00:59:03,365 >> [El] 1061 00:59:03,365 --> 00:59:04,240 ROBOT: És el meu torn. 1062 00:59:04,240 --> 00:59:06,930 ALTAVEU: És molt més difícil quan vostè està de peu aquí, amics. 1063 00:59:06,930 --> 00:59:19,400 1064 00:59:19,400 --> 00:59:21,840 [El] 1065 00:59:21,840 --> 00:59:26,730 1066 00:59:26,730 --> 00:59:29,054 ROBOT: Vostès els humans són tan fàcils de superar. 1067 00:59:29,054 --> 00:59:30,803 [Riures i aplaudiments] 1068 00:59:30,803 --> 00:59:31,886 ALTAVEU: Moltes gràcies. 1069 00:59:31,886 --> 00:59:34,692 ROBOT: jo guanyo. 1070 00:59:34,692 --> 00:59:35,400 Començo el joc. 1071 00:59:35,400 --> 00:59:39,500 >> ALTAVEU: D'acord, moltes gràcies molt que Olivier, i Alessandro, 1072 00:59:39,500 --> 00:59:41,616 i Chen Ming. 1073 00:59:41,616 --> 00:59:45,600 >> [Aplaudiments] 1074 00:59:45,600 --> 00:59:47,040 >> Vull fer un últim punt. 1075 00:59:47,040 --> 00:59:51,630 Així Baxter en el molt acabar allà, enganyat. 1076 00:59:51,630 --> 00:59:54,160 1077 00:59:54,160 --> 00:59:56,310 I això va ser inesperat. 1078 00:59:56,310 --> 01:00:00,440 Un del fantàstic coses de la IA és que ens 1079 01:00:00,440 --> 01:00:05,070 fer el treball en AI perquè puguem construir realment interessant i intel·ligent 1080 01:00:05,070 --> 01:00:06,930 dispositius. 1081 01:00:06,930 --> 01:00:10,130 Però també fem treballs en IA perquè ens diu alguna cosa 1082 01:00:10,130 --> 01:00:13,940 sobre com els humans són intel·ligents. 1083 01:00:13,940 --> 01:00:17,280 >> Un dels favorits estudis realitzats en el meu laboratori és 1084 01:00:17,280 --> 01:00:23,660 mirant el que passa quan màquines enganyen inesperadament. 1085 01:00:23,660 --> 01:00:27,070 Ho vam fer originalment no amb Baxter jugar tic-tac-dit del peu, 1086 01:00:27,070 --> 01:00:30,340 però amb un robot més petit anomenat Nau, qui va jugar pedra-paper-tisores. 1087 01:00:30,340 --> 01:00:33,010 1088 01:00:33,010 --> 01:00:35,800 I de vegades després jugar munts i munts 1089 01:00:35,800 --> 01:00:41,580 d'avorrir pedra-paper-tisores jocs, el robot llançaria un gest, 1090 01:00:41,580 --> 01:00:48,616 perdre, i després canviar de cop i volta el seu gest i dir, jo guanyo. 1091 01:00:48,616 --> 01:00:50,480 >> [El] 1092 01:00:50,480 --> 01:00:56,090 >> Ara, de vegades nosaltres també tindríem el robot, així com un control, llançar un gest, 1093 01:00:56,090 --> 01:01:01,270 guanyar, i canviar el seu gest perdre, llençar el partit, 1094 01:01:01,270 --> 01:01:04,070 trampes per perdre. 1095 01:01:04,070 --> 01:01:07,540 I això no és tan convincent. 1096 01:01:07,540 --> 01:01:09,890 El robot que enganya per tal de guanyar-se la gent 1097 01:01:09,890 --> 01:01:14,660 respondre a com si fos a per ells, de la mateixa manera que 1098 01:01:14,660 --> 01:01:17,690 està buscant activament la seva destrucció. 1099 01:01:17,690 --> 01:01:19,210 >> [El] 1100 01:01:19,210 --> 01:01:20,990 >> Es converteix en un agent. 1101 01:01:20,990 --> 01:01:21,840 És com una persona. 1102 01:01:21,840 --> 01:01:23,970 Té la creença i la intenció. 1103 01:01:23,970 --> 01:01:27,470 I no és una bona intenció. 1104 01:01:27,470 --> 01:01:33,790 I el robot que llança la joc és simplement un mal funcionament. 1105 01:01:33,790 --> 01:01:36,990 És només un dispositiu danyat. 1106 01:01:36,990 --> 01:01:41,405 Et vaig a ensenyar un parell d'exemples que a partir d'alguns dels nostres participants. 1107 01:01:41,405 --> 01:01:43,990 1108 01:01:43,990 --> 01:01:45,600 Així que aquí està l'engany per tal de perdre. 1109 01:01:45,600 --> 01:01:46,266 >> [REPRODUCCIÓ DE VÍDEO] 1110 01:01:46,266 --> 01:01:47,010 - [Inaudible] guanyar. 1111 01:01:47,010 --> 01:01:49,550 Anem a jugar. 1112 01:01:49,550 --> 01:01:50,538 >> -Espera Què? 1113 01:01:50,538 --> 01:01:54,490 1114 01:01:54,490 --> 01:01:55,352 >> - [Inaudible] guanyar. 1115 01:01:55,352 --> 01:01:58,280 Anem a jugar. 1116 01:01:58,280 --> 01:01:59,400 >> [Inaudible] guanyar. 1117 01:01:59,400 --> 01:02:02,290 Anem a jugar. 1118 01:02:02,290 --> 01:02:05,490 >> ALTAVEU: I aquí és fer trampa per guanyar. 1119 01:02:05,490 --> 01:02:06,438 >> -Sí, Jo guanyo. 1120 01:02:06,438 --> 01:02:07,394 Anem a jugar. 1121 01:02:07,394 --> 01:02:08,828 >> -No Pots fer això. 1122 01:02:08,828 --> 01:02:10,740 >> [El] 1123 01:02:10,740 --> 01:02:12,174 1124 01:02:12,174 --> 01:02:13,979 >> -Sí, Jo guanyo. 1125 01:02:13,979 --> 01:02:14,520 -Vostè Enganyat. 1126 01:02:14,520 --> 01:02:17,990 1127 01:02:17,990 --> 01:02:20,010 Vas fer trampa ara. 1128 01:02:20,010 --> 01:02:21,140 >> -Sí, Jo guanyo. 1129 01:02:21,140 --> 01:02:22,940 >> -Escolta, Et trampós. 1130 01:02:22,940 --> 01:02:26,670 Fas trampa, super trampós. 1131 01:02:26,670 --> 01:02:27,650 >> [FI DE REPRODUCCIÓ] 1132 01:02:27,650 --> 01:02:31,130 >> ALTAVEU: Aquests diferents reaccions ràpidament 1133 01:02:31,130 --> 01:02:34,890 canviar la nostra percepció del dispositiu. 1134 01:02:34,890 --> 01:02:36,780 Significa això que deliberadament construïm 1135 01:02:36,780 --> 01:02:40,370 màquines que fan trampa perquè això és la millor enginyeria que podem fer? 1136 01:02:40,370 --> 01:02:44,680 No, però ens diu alguna cosa realment interessant de la gent. 1137 01:02:44,680 --> 01:02:49,710 Aquesta cosa que vostè i els tramposos roba la seva victòria, això és 1138 01:02:49,710 --> 01:02:53,660 alguna cosa que està viu, que és animen, això és tractant de fer-te mal. 1139 01:02:53,660 --> 01:02:54,680 Té l'estat mental. 1140 01:02:54,680 --> 01:02:55,400 Té la creença. 1141 01:02:55,400 --> 01:02:57,170 Té la intenció. 1142 01:02:57,170 --> 01:03:01,540 >> Aquesta cosa que lliura el joc per a tu, que no ho és. 1143 01:03:01,540 --> 01:03:04,670 Això és només un mal funcionament. 1144 01:03:04,670 --> 01:03:08,900 Això és en molts sentits per què és fàcil llançar el joc amb els nens. 1145 01:03:08,900 --> 01:03:12,050 Però si intenta enganyar- i una espècie de cantar victòria 1146 01:03:12,050 --> 01:03:15,200 quan, ja saps, per escurçar el joc, t'atrapen immediatament. 1147 01:03:15,200 --> 01:03:19,040 1148 01:03:19,040 --> 01:03:23,140 Aquest tipus d'efectes que veiem que surt de la IA, 1149 01:03:23,140 --> 01:03:26,490 ens ensenyen molt sobre nosaltres mateixos. 1150 01:03:26,490 --> 01:03:28,076 >> Molt bé, això és tot per avui. 1151 01:03:28,076 --> 01:03:30,450 Moltes gràcies a David i l'equip de producció de Harvard 1152 01:03:30,450 --> 01:03:32,350 per venir. 1153 01:03:32,350 --> 01:03:33,820 >> [Aplaudiments] 1154 01:03:33,820 --> 01:03:36,760 1155 01:03:36,760 --> 01:03:41,840 >> Ens veiem a prova un, i després per una última conferència. 1156 01:03:41,840 --> 01:03:43,025 Que tinguis un bon dia. 1157 01:03:43,025 --> 01:03:44,965 >> [Aplaudiments] 1158 01:03:44,965 --> 01:03:48,360 1159 01:03:48,360 --> 01:03:51,825 >> [REPRODUCCIÓ DE MÚSICA] 1160 01:03:51,825 --> 01:03:54,950 DAVID J Malan: Bé, probablement necessitem per a introduir algun tipus de xifrat, 1161 01:03:54,950 --> 01:03:55,450 Oi? 1162 01:03:55,450 --> 01:03:58,650 Perquè llavors les capçaleres de aquestes peticions HTTP seran 1163 01:03:58,650 --> 01:04:01,530 remenats perquè qualsevol persona tractant d'ensumar el trànsit 1164 01:04:01,530 --> 01:04:03,400 serà en realitat no ser capaç de veure'ls. 1165 01:04:03,400 --> 01:04:05,254 Quina és la solució a aquest problema? 1166 01:04:05,254 --> 01:04:07,920 Bé, hem d'introduir en realitat xifrat en la fórmula, 1167 01:04:07,920 --> 01:04:11,010 de manera que quan aquesta persona està transmetre dades des de A a B, 1168 01:04:11,010 --> 01:04:12,390 podem send-- segura 1169 01:04:12,390 --> 01:04:14,590 >> [El] 1170 01:04:14,590 --> 01:04:19,530 >> La informació d'una manera que la adversari no pot, de fet, veure-ho.