1 00:00:00,000 --> 00:00:01,924 >> [Música tocando] 2 00:00:01,924 --> 00:00:10,600 3 00:00:10,600 --> 00:00:13,280 >> COLUMNA: Benvido de volta, todo o mundo. 4 00:00:13,280 --> 00:00:15,440 Este é CS50. 5 00:00:15,440 --> 00:00:21,040 E hoxe, temos unha morea de cousas interesantes para falar. 6 00:00:21,040 --> 00:00:25,500 Primeiro, porén, eu teño que lembrá- vostede dalgunhas cousas administrativas. 7 00:00:25,500 --> 00:00:30,160 Esta semana é un cuestionario, quarta- ou á sección de Yale 8 00:00:30,160 --> 00:00:32,940 os martes e xoves, o xoves. 9 00:00:32,940 --> 00:00:38,170 Non hai comentarios de quiz esta noite na Universidade de Yale, 05:30 - 07:00. 10 00:00:38,170 --> 00:00:40,030 En Harvard, gravaron un onte. 11 00:00:40,030 --> 00:00:43,000 E todo o mundo pode ver que en liña. 12 00:00:43,000 --> 00:00:49,406 >> Ademais, esta semana ou principios da próxima semana, nós temos a nosa última charla CS50. 13 00:00:49,406 --> 00:00:51,450 [Xemidos] Sei. 14 00:00:51,450 --> 00:00:54,140 Veu axiña. 15 00:00:54,140 --> 00:00:57,820 Estudantes de Yale terá un live charla aquí na escola de dereito 16 00:00:57,820 --> 00:00:59,920 auditorio o venres. 17 00:00:59,920 --> 00:01:01,140 Haberá bolo. 18 00:01:01,140 --> 00:01:05,570 Estudantes de Harvard terá a última charla en Sanders o luns. 19 00:01:05,570 --> 00:01:08,050 Haberá tamén bolo. 20 00:01:08,050 --> 00:01:14,000 >> Ademais, esta semana o venres, para os de vostedes que están vindo para New Haven, 21 00:01:14,000 --> 00:01:15,740 temos a Expo CS50. 22 00:01:15,740 --> 00:01:18,850 Temos máis de 30 distintos grupos rexistrados 23 00:01:18,850 --> 00:01:22,530 para lle amosar todo de veleiros autónomos, 24 00:01:22,530 --> 00:01:27,170 para sistemas que recoñecen retratos dixitais, para o ordenador 25 00:01:27,170 --> 00:01:32,100 música e música producida por ordenador. 26 00:01:32,100 --> 00:01:33,610 Entón, por favor unirse a nós. 27 00:01:33,610 --> 00:01:36,460 Eu creo que vai ser un gran momento. 28 00:01:36,460 --> 00:01:40,320 >> Hoxe, porén, hai que seguir a falar de AI, 29 00:01:40,320 --> 00:01:43,150 sobre a intelixencia artificial. 30 00:01:43,150 --> 00:01:46,070 E unha das cousas que nós estamos indo a chegar ao hoxe 31 00:01:46,070 --> 00:01:51,750 é a idea de como usar o AI para resolver problemas. 32 00:01:51,750 --> 00:01:54,690 Agora, como sempre, imos comezar con algo sinxelo. 33 00:01:54,690 --> 00:01:57,120 E nós imos comezar cunha idea simple. 34 00:01:57,120 --> 00:01:59,920 E iso é a través da investigación. 35 00:01:59,920 --> 00:02:06,990 >> Entón, imaxine por un minuto que eu ten unha tarefa que eu teño para realizar. 36 00:02:06,990 --> 00:02:11,970 E gustaríame ter esa tarefa automatizado por algún axente software. 37 00:02:11,970 --> 00:02:17,100 Imaxina que eu estou tentando reservar un conxunto de voos desde, digamos, Boston 38 00:02:17,100 --> 00:02:20,040 a San Francisco. 39 00:02:20,040 --> 00:02:24,230 Podería pasar e eu podería usar un de busca en liña marabillosa 40 00:02:24,230 --> 00:02:28,790 ferramentas, o que vai facer basicamente o mesmo proceso que estamos 41 00:02:28,790 --> 00:02:30,030 indo a pé ata hoxe. 42 00:02:30,030 --> 00:02:34,100 Pero se non ten que ferramenta, o que faría? 43 00:02:34,100 --> 00:02:37,570 >> Ben, pode ollar e ver e dicir, eu estou en Boston. 44 00:02:37,570 --> 00:02:41,520 O que os voos están dispoñibles para min? 45 00:02:41,520 --> 00:02:44,390 Agora, quizais teña tres posibles voos desde Boston 46 00:02:44,390 --> 00:02:47,180 que vai caber o tempo cando eu teño saír. 47 00:02:47,180 --> 00:02:48,830 Podería voar Chicago. 48 00:02:48,830 --> 00:02:50,130 Ou eu podería voar Miami. 49 00:02:50,130 --> 00:02:53,340 Ou eu podería voar a Nova York. 50 00:02:53,340 --> 00:02:56,980 Podería, entón, mirar de cada un unha desas cidades de destino 51 00:02:56,980 --> 00:03:00,650 e pensar sobre o que locais Podería chegar 52 00:03:00,650 --> 00:03:03,020 de cada unha destas cidades individuais. 53 00:03:03,020 --> 00:03:07,390 >> Entón, talvez desde Chicago, podo conseguir un voo directo para San Francisco. 54 00:03:07,390 --> 00:03:09,550 Isto é excelente. 55 00:03:09,550 --> 00:03:12,360 Ou eu podería incorporarse un voo para Denver. 56 00:03:12,360 --> 00:03:16,970 Agora, quizais que o voo a San Francisco é a solución perfecta para min, 57 00:03:16,970 --> 00:03:19,530 pero quizais non. 58 00:03:19,530 --> 00:03:22,180 Poida que eu estou buscando algo iso é un pouco máis barato 59 00:03:22,180 --> 00:03:24,920 ou un pouco mellor para o meu horario. 60 00:03:24,920 --> 00:03:29,197 E para que eu puidese ver o que outros posibilidades poden estar aí. 61 00:03:29,197 --> 00:03:30,280 Entón, eu podería ollar para Denver. 62 00:03:30,280 --> 00:03:33,870 E a partir de Denver, así, quizais Podo ir nun voo para Austin. 63 00:03:33,870 --> 00:03:37,080 E a partir de Austin, quizais eu poida obter unha voo para Phoenix e da Phoenix 64 00:03:37,080 --> 00:03:40,190 a San Francisco. 65 00:03:40,190 --> 00:03:42,730 Agora, eu non estou preparado aínda. 66 00:03:42,730 --> 00:03:45,640 Porque quizais haxa unha con voos directos de Nova York 67 00:03:45,640 --> 00:03:47,850 a San Francisco que é perfecto para min. 68 00:03:47,850 --> 00:03:53,354 Ou que haxa un voo de Miami mediante Denver que é moito máis barato. 69 00:03:53,354 --> 00:03:54,270 Entón, eu teño que ir. 70 00:03:54,270 --> 00:03:58,200 E eu aínda teño que mirar a quen cidades que aínda non investigados. 71 00:03:58,200 --> 00:04:04,220 Teño que comprobar exhaustivamente todas as posibilidades que poida ter. 72 00:04:04,220 --> 00:04:09,610 >> Así, a partir de Nova York, quizais eu poida obter unha voo para Nashville, e de Nashville 73 00:04:09,610 --> 00:04:10,336 para Austin. 74 00:04:10,336 --> 00:04:11,460 E entón eu sei onde estou. 75 00:04:11,460 --> 00:04:14,252 E entón eu sei desde Austin, podo voar Phoenix e da 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 Se eu voar Miami primeira, con todo, quizais eu poida coller un voo de Miami 79 00:04:22,830 --> 00:04:25,080 para Nashville, ou desde Miami para Austin. 80 00:04:25,080 --> 00:04:27,950 81 00:04:27,950 --> 00:04:30,860 >> E agora eu tente todo das posibilidades. 82 00:04:30,860 --> 00:04:36,310 Eu constrúe-se neste gráfico que me mostra todas as posibles rutas 83 00:04:36,310 --> 00:04:37,790 que eu podería ser capaz de tomar. 84 00:04:37,790 --> 00:04:40,510 85 00:04:40,510 --> 00:04:43,640 Cando nós representamos estes tipo de problemas, 86 00:04:43,640 --> 00:04:47,870 non estamos indo para representar Los explicitamente como este gráfico, 87 00:04:47,870 --> 00:04:51,590 porque ese gráfico non representa a historia onde fomos. 88 00:04:51,590 --> 00:04:55,260 Sabendo que eu voei de Phoenix para San Francisco 89 00:04:55,260 --> 00:05:01,690 non me diga se eu vin a través Nashville, ou a través de Denver, ou a través de Miami. 90 00:05:01,690 --> 00:05:06,430 >> Entón, o que vou facer é no canto Vou levar este mesmo problema, 91 00:05:06,430 --> 00:05:09,140 e eu vou representa-lo como unha árbore. 92 00:05:09,140 --> 00:05:14,300 E na raíz da árbore, na arriba, eu vou poñer o lugar que eu comece, 93 00:05:14,300 --> 00:05:16,590 Boston. 94 00:05:16,590 --> 00:05:19,310 E a partir de Boston, eu vou mirar para todos os posibles lugares 95 00:05:19,310 --> 00:05:20,380 que eu poida viaxar. 96 00:05:20,380 --> 00:05:25,480 Ben, neste caso, eu tiña tres, Chicago, Nova York e Miami. 97 00:05:25,480 --> 00:05:29,850 E entón eu vou explorar cada un dos eses nenos na árbore. 98 00:05:29,850 --> 00:05:32,690 >> De Chicago, vin que tiña dous voos. 99 00:05:32,690 --> 00:05:35,940 Eu podería voar directamente San Francisco ou Denver. 100 00:05:35,940 --> 00:05:37,740 Agora San Francisco, que é o meu obxectivo. 101 00:05:37,740 --> 00:05:39,790 Ese é o meu destino. 102 00:05:39,790 --> 00:05:42,220 Isto vai ser unha folla desa árbore. 103 00:05:42,220 --> 00:05:45,340 É dicir, eu nunca estou indo a ir nalgún lugar tras San Francisco. 104 00:05:45,340 --> 00:05:47,850 105 00:05:47,850 --> 00:05:50,340 De Denver, aínda que, Podo voar desde Denver 106 00:05:50,340 --> 00:05:54,220 para Austin, desde Austin para Phoenix, e de Phoenix a San Francisco. 107 00:05:54,220 --> 00:05:56,050 E agora de novo, cheguei a unha folla. 108 00:05:56,050 --> 00:05:59,470 109 00:05:59,470 --> 00:06:03,980 >> Podería, entón, volver á seguinte cidade que aínda non totalmente explotado. 110 00:06:03,980 --> 00:06:07,440 Iso sería Nova York, ir vólvese para o cumio da miña árbore, 111 00:06:07,440 --> 00:06:09,160 descendan a Nova York. 112 00:06:09,160 --> 00:06:12,700 De Nova York, podo voar Nashville, de Nashville a Austin, 113 00:06:12,700 --> 00:06:17,290 de Austin para Phoenix, e desde Phoenix a San Francisco. 114 00:06:17,290 --> 00:06:20,170 E, finalmente, unha cidade que eu non mirei aínda, Miami. 115 00:06:20,170 --> 00:06:24,600 >> Ben, dende Miami dixen que tiña dous posibilidades, Nashville ou Austin. 116 00:06:24,600 --> 00:06:28,810 Se eu voar Nashville, ben, entón eu voo desde Nashville, para Austin, para Phoenix, 117 00:06:28,810 --> 00:06:29,640 a San Francisco. 118 00:06:29,640 --> 00:06:33,600 Se eu voar Austin, eu voo Austin, para Phoenix, a San Francisco. 119 00:06:33,600 --> 00:06:36,340 E agora eu teño unha árbore. 120 00:06:36,340 --> 00:06:37,230 É unha árbore completa. 121 00:06:37,230 --> 00:06:41,890 É todas as posibilidades e todos os camiños que eu podería tomar. 122 00:06:41,890 --> 00:06:44,310 É dicir, se eu comezar a raíz da árbore na parte superior 123 00:06:44,310 --> 00:06:47,860 e eu baixar a un dos sae, el dime non só 124 00:06:47,860 --> 00:06:50,480 onde eu vou acabar, San Francisco, 125 00:06:50,480 --> 00:06:53,670 pero me di a ruta que Necesito levar para chegar alí. 126 00:06:53,670 --> 00:06:56,400 127 00:06:56,400 --> 00:06:59,690 >> Agora, cal destes é o mellor? 128 00:06:59,690 --> 00:07:02,430 Ben, nada sobre iso problema aínda me di 129 00:07:02,430 --> 00:07:04,710 cal delas é a mellor solución. 130 00:07:04,710 --> 00:07:09,270 Poida que eu me importa máis sobre canto tempo eu estou no aire, 131 00:07:09,270 --> 00:07:12,350 ou a distancia que estou voando. 132 00:07:12,350 --> 00:07:16,410 Nese caso, Chicago para San Francisco pode ser menor número 133 00:07:16,410 --> 00:07:18,910 de millas no aire. 134 00:07:18,910 --> 00:07:20,860 >> Poida que eu me preocupo co custo. 135 00:07:20,860 --> 00:07:23,680 E todos sabemos voos directos son xeralmente máis caros. 136 00:07:23,680 --> 00:07:26,610 Entón, talvez si levar isto tipo de ruta cara atrás 137 00:07:26,610 --> 00:07:30,650 través de Miami, Nashville, Austin, Phoenix, quizais, a continuación, 138 00:07:30,650 --> 00:07:34,070 Eu recibín un prezo máis baixo. 139 00:07:34,070 --> 00:07:36,440 Pero eu podería optimizar en calquera criterios que me interesa. 140 00:07:36,440 --> 00:07:39,790 Quen ten o mellor en voo WiFi, ou que 141 00:07:39,790 --> 00:07:43,110 aeroportos teñen a mellor comida dispoñible. 142 00:07:43,110 --> 00:07:47,280 E cada un destes pode me dar unha solución diferente 143 00:07:47,280 --> 00:07:49,215 que eu vexo como o mellor. 144 00:07:49,215 --> 00:07:51,990 145 00:07:51,990 --> 00:07:54,400 >> Estes tipos de problemas, onde imos 146 00:07:54,400 --> 00:07:58,480 para construír esta árbore de posibilidades e logo 147 00:07:58,480 --> 00:08:02,100 ollar para cada un destes camiños individuais, e examinar 148 00:08:02,100 --> 00:08:05,270 cal destes fulfills un criterio para nós, 149 00:08:05,270 --> 00:08:08,790 imos chamá- estes problemas de procura. 150 00:08:08,790 --> 00:08:11,280 E nós temos lotes de algoritmos, algúns dos cales 151 00:08:11,280 --> 00:08:15,270 vimos xa, ir e explorar aquelas árbores. 152 00:08:15,270 --> 00:08:19,270 Poderiamos facelo do xeito que eu só fixen, unha busca en profundidade, 153 00:08:19,270 --> 00:08:22,900 indo para abaixo, tanto como pudermos ata nós bateu unha folla, e, a continuación, volvéndose, 154 00:08:22,900 --> 00:08:24,787 e indo para a dereita de volta para abaixo. 155 00:08:24,787 --> 00:08:26,870 Ou podemos facer o que é chamado de procura en anchura. 156 00:08:26,870 --> 00:08:29,675 Poderiamos ampliar todo na parte superior, e, a continuación 157 00:08:29,675 --> 00:08:31,550 todo nunha liña debaixo que, a continuación, 158 00:08:31,550 --> 00:08:35,240 todo unha liña debaixo daquel. 159 00:08:35,240 --> 00:08:41,250 Estas árbores de busca son fundamentais para a AI. 160 00:08:41,250 --> 00:08:46,570 Pero eles non obter completamente seguro o tempo. 161 00:08:46,570 --> 00:08:51,600 De feito, en moitos dos casos que realmente se preocupan, 162 00:08:51,600 --> 00:08:54,430 queremos construír unha árbore, pero nós non, en realidade, 163 00:08:54,430 --> 00:08:57,140 comeza a facer todas as decisións. 164 00:08:57,140 --> 00:09:00,940 >> Estas son situacións chamadas busca adversarial, tamén coñecido 165 00:09:00,940 --> 00:09:05,390 como a forma de escribir rol sistemas e ser pago por iso. 166 00:09:05,390 --> 00:09:07,940 Pero estes son os tipos de sistemas onde 167 00:09:07,940 --> 00:09:12,920 Pode comezar a escoller cando ir de Boston, que cidade ir á seguinte. 168 00:09:12,920 --> 00:09:19,990 Pero despois diso, alguén pode obter para tomar a decisión sobre onde eu voar. 169 00:09:19,990 --> 00:09:24,040 Polo tanto, para construír estes tipos de estruturas, estamos 170 00:09:24,040 --> 00:09:28,510 vai ter que tomar un pouco visión diferente para el. 171 00:09:28,510 --> 00:09:31,060 Non imos ser capaces de pode buscar a través da árbore 172 00:09:31,060 --> 00:09:35,000 máis, porque non somos o que está no control 173 00:09:35,000 --> 00:09:38,180 de cada un destes puntos de decisión. 174 00:09:38,180 --> 00:09:42,590 >> Entón, imos imaxinar unha simple xogo como tic-tac-toe. 175 00:09:42,590 --> 00:09:46,730 Podería comezar cun Placa completamente en branco. 176 00:09:46,730 --> 00:09:49,580 E en tic-tac-dedo do pé, X pode xogar primeiro. 177 00:09:49,580 --> 00:09:53,890 E para que eu puidese pensar en todo o movementos posibles que X podería facer. 178 00:09:53,890 --> 00:09:57,420 E se eu son o único xogo X, iso é óptimo. 179 00:09:57,420 --> 00:10:01,020 Teño nove posible move o que podo facer. 180 00:10:01,020 --> 00:10:05,000 Podería poñer un X en calquera destes nove posicións. 181 00:10:05,000 --> 00:10:10,710 >> E, a continuación, a partir de cada un destes, I podía imaxinar o que acontece a continuación. 182 00:10:10,710 --> 00:10:14,130 Ben, neste caso, a outra xogador comezaría a tomar un rumbo. 183 00:10:14,130 --> 00:10:15,660 O comezaría a tomar un rumbo. 184 00:10:15,660 --> 00:10:19,510 E de cada un destes, hai sería oito lugares distintos 185 00:10:19,510 --> 00:10:22,980 O que podería poñer o marcador. 186 00:10:22,980 --> 00:10:25,790 >> Imos dicir que eu decidir que eu era vai poñer un X no centro. 187 00:10:25,790 --> 00:10:28,810 Que sempre parece que un bo movemento de apertura. 188 00:10:28,810 --> 00:10:34,870 Podería mirar para abaixo que, a oito movementos posibles que O fai. 189 00:10:34,870 --> 00:10:37,320 Agora, se eu estou xogando X, que é marabilloso. 190 00:10:37,320 --> 00:10:41,740 Comezar a escoller cal deles eu ir ao un no medio. 191 00:10:41,740 --> 00:10:45,000 Pero agora ó comeza a escoller. 192 00:10:45,000 --> 00:10:48,750 E eu non teño control sobre esta decisión. 193 00:10:48,750 --> 00:10:51,670 >> Pero a partir de cada un destes posibles posicións de mesa, 194 00:10:51,670 --> 00:10:54,020 hai entón outro conxunto de posibilidades. 195 00:10:54,020 --> 00:10:56,700 Cando se trata de ser miña vez de novo, eu faría 196 00:10:56,700 --> 00:11:01,500 comeza a escoller e dicir, ben, O móvese para o ben, 197 00:11:01,500 --> 00:11:06,110 o punto medio do lado esquerdo, a continuación, Eu teño un conxunto de posibilidades 198 00:11:06,110 --> 00:11:09,740 onde eu poida tomar o meu seguinte paso. 199 00:11:09,740 --> 00:11:14,140 Destes, eu podería considerar todos as posibilidades debaixo deles. 200 00:11:14,140 --> 00:11:18,030 E, a continuación, o obtería para escoller entre aqueles. 201 00:11:18,030 --> 00:11:22,290 >> E eu podería continuar a construír esta árbore ata que cheguei ao punto 202 00:11:22,290 --> 00:11:26,960 onde queira alguén gaña o que é game-- 203 00:11:26,960 --> 00:11:31,070 ten que ser considerada unha folla node-- ou o consello está completamente cheo 204 00:11:31,070 --> 00:11:32,704 e ninguén gañou. 205 00:11:32,704 --> 00:11:34,370 E iso tamén vai ser un nodo folla. 206 00:11:34,370 --> 00:11:35,411 Isto vai ser un empate. 207 00:11:35,411 --> 00:11:37,820 208 00:11:37,820 --> 00:11:41,680 >> Pero a cousa complicada con isto é se iso fose só unha investigación regular 209 00:11:41,680 --> 00:11:44,269 problema, eu sería capaz de digamos, así, X debe ir aquí. 210 00:11:44,269 --> 00:11:45,560 E O camiño debe ir máis alá. 211 00:11:45,560 --> 00:11:46,770 E entón X debe ir aquí. 212 00:11:46,770 --> 00:11:48,269 E, a continuación, debe ir O camiño ata alí. 213 00:11:48,269 --> 00:11:51,860 E entón X pode obter tres nunha cola, e eu gañar. 214 00:11:51,860 --> 00:11:54,870 E o xogo sería máis en cinco movementos, tres para min, 215 00:11:54,870 --> 00:11:57,710 dous para o meu adversario. 216 00:11:57,710 --> 00:12:01,300 Pero eu non sempre consegue escoller iso. 217 00:12:01,300 --> 00:12:03,720 >> Entón, en vez diso, o que somos vai ter que facer 218 00:12:03,720 --> 00:12:06,270 é que nós imos ter para ter unha nova estratexia. 219 00:12:06,270 --> 00:12:09,350 E que a estratexia algoritmos xogo-playing adoitan usar 220 00:12:09,350 --> 00:12:12,000 é o que se chama minimax. 221 00:12:12,000 --> 00:12:15,500 A idea central do minimax é que somos 222 00:12:15,500 --> 00:12:21,365 vai escoller o movemento que dá o noso adversario o peor conxunto posible 223 00:12:21,365 --> 00:12:22,790 de movementos que poden facer. 224 00:12:22,790 --> 00:12:25,570 225 00:12:25,570 --> 00:12:28,870 Non me fai ningún ben para escoller un movemento onde 226 00:12:28,870 --> 00:12:31,952 Eu podería ser capaz de vencer despois que, xa que o meu adversario non é 227 00:12:31,952 --> 00:12:33,160 me vai dar esa oportunidade. 228 00:12:33,160 --> 00:12:37,770 Van escoller algúns resultado terrible para min. 229 00:12:37,770 --> 00:12:42,010 Entón eu vou facer o move que forza o meu adversario 230 00:12:42,010 --> 00:12:45,760 para facer algo mellor para min. 231 00:12:45,760 --> 00:12:46,260 Todo ben. 232 00:12:46,260 --> 00:12:48,410 Imos ver como iso se desenvolve. 233 00:12:48,410 --> 00:12:51,640 Entón aquí está o noso algoritmo en pseudocódigo. 234 00:12:51,640 --> 00:12:54,450 Estamos indo para xerar toda a árbore de xogo. 235 00:12:54,450 --> 00:12:56,757 Nós imos construír toda a estrutura. 236 00:12:56,757 --> 00:12:57,840 E entón nós imos pasar. 237 00:12:57,840 --> 00:13:02,100 E aínda no fondo de cada un dos nós terminais, en cada unha das follas, 238 00:13:02,100 --> 00:13:07,850 imos avaliar como valioso é que para min? 239 00:13:07,850 --> 00:13:11,690 E nós estamos indo para as cousas de valor que son bos para min como positivo. 240 00:13:11,690 --> 00:13:14,460 As cousas que non son boas para min será menos positivo ou cero, 241 00:13:14,460 --> 00:13:16,480 ou mesmo negativo. 242 00:13:16,480 --> 00:13:19,240 >> Así, en tic-tac-toe, quizais unha vitoria para min é bo. 243 00:13:19,240 --> 00:13:20,290 Esa é unha pregunta. 244 00:13:20,290 --> 00:13:22,400 E un empate é cero. 245 00:13:22,400 --> 00:13:26,230 E algo que é unha perda para me, quizais iso é unha negativa. 246 00:13:26,230 --> 00:13:29,620 Todo o que importa é que o mellor é para min, canto maior sexa a puntuación 247 00:13:29,620 --> 00:13:32,160 recibe. 248 00:13:32,160 --> 00:13:36,690 A partir destas posibilidades no fondo, entón imos filtrar cara arriba. 249 00:13:36,690 --> 00:13:40,650 E cando é a miña oportunidade de escoller entre un conxunto de alternativas, 250 00:13:40,650 --> 00:13:44,460 Vou escoller o que é obtivo a maior puntuación. 251 00:13:44,460 --> 00:13:47,200 >> E sempre que el é o meu opoñentes virar para escoller, 252 00:13:47,200 --> 00:13:52,350 Vou asumir que eles están indo a escoller aquel coa puntuación máis baixa. 253 00:13:52,350 --> 00:13:56,090 E se eu fai iso todo o camiño ata o cumio da árbore, 254 00:13:56,090 --> 00:14:03,150 Vou escoller un camiño que dá me o mellor resultado que eu poida obter, 255 00:14:03,150 --> 00:14:09,110 asumindo que o meu adversario fai todos os movementos certos. 256 00:14:09,110 --> 00:14:11,940 >> Todo ben, entón imos ver iso en acción por primeira vez. 257 00:14:11,940 --> 00:14:14,980 E entón nós imos realmente mirar para o código para el. 258 00:14:14,980 --> 00:14:16,780 Entón imaxine teño este gran árbore. 259 00:14:16,780 --> 00:14:18,280 E agora eu non estou xogando tic-tac-toe. 260 00:14:18,280 --> 00:14:20,405 Quería darlle que un simple rico. 261 00:14:20,405 --> 00:14:23,560 Entón, eu teño un pouco de xogo onde hai moitas puntuacións diferentes 262 00:14:23,560 --> 00:14:26,390 que eu podería ter ao final. 263 00:14:26,390 --> 00:14:27,980 E así eu construír esa árbore completa. 264 00:14:27,980 --> 00:14:29,070 E comezo a mover en primeiro lugar. 265 00:14:29,070 --> 00:14:31,290 Eu son a raíz da árbore. 266 00:14:31,290 --> 00:14:36,150 >> E comezar a escoller isso-- iso fico para dar a través daquel primeiro nó. 267 00:14:36,150 --> 00:14:38,410 E entón o meu adversario ten que ir. 268 00:14:38,410 --> 00:14:41,910 E entón eu teño que ir unha vez máis. 269 00:14:41,910 --> 00:14:46,830 Así, na parte inferior, eu teño un conxunto de posibilidades que podo escoller, 270 00:14:46,830 --> 00:14:50,570 diferentes estados terminais do xogo. 271 00:14:50,570 --> 00:14:54,980 Se eu estou abaixo en que extrema esquerda canto, 272 00:14:54,980 --> 00:14:58,867 e eu ver que eu teño unha selección entre un e oito, sete, e un dous, 273 00:14:58,867 --> 00:15:00,450 ben, eu son o único que comeza a escoller. 274 00:15:00,450 --> 00:15:02,910 Entón, eu estou indo a escoller o mellor da xente. 275 00:15:02,910 --> 00:15:05,650 Vou escoller o oito. 276 00:15:05,650 --> 00:15:10,090 >> Entón eu sei que eu baixar a ese punto, 277 00:15:10,090 --> 00:15:13,890 Eu vou ser capaz de conseguir que os oito puntos. 278 00:15:13,890 --> 00:15:17,410 Se eu acabar no seguinte punto sobre, sobre o próximo no, 279 00:15:17,410 --> 00:15:20,760 un nove, un, ou un seis, así, eu son vai escoller a mellor delas. 280 00:15:20,760 --> 00:15:21,950 Vou escoller a nove. 281 00:15:21,950 --> 00:15:24,880 Se eu tivera unha selección entre dous e catro, e un, 282 00:15:24,880 --> 00:15:28,240 Vou escoller a catro, o máis alto. 283 00:15:28,240 --> 00:15:31,990 >> Agora, se eu ollar para o nivel enriba diso, meu adversario 284 00:15:31,990 --> 00:15:34,440 é o que se ten que facer esa escolla. 285 00:15:34,440 --> 00:15:37,040 Entón, o meu adversario comeza a escoller, gustaríame darlle 286 00:15:37,040 --> 00:15:39,250 o único que está a suceder para tiralo oito puntos, 287 00:15:39,250 --> 00:15:41,916 ou eu darlle a cousa que é vai darlle nove puntos, 288 00:15:41,916 --> 00:15:45,240 ou a cousa que está a suceder para darlle catro puntos? 289 00:15:45,240 --> 00:15:49,130 E o meu adversario, sendo racional, vai 290 00:15:49,130 --> 00:15:53,470 escoller o menos daqueles, vai escoller a catro. 291 00:15:53,470 --> 00:15:56,020 >> E podo facelo a través de toda a árbore. 292 00:15:56,020 --> 00:15:59,110 Podo ir para abaixo para que conxunto do medio de tres. 293 00:15:59,110 --> 00:16:01,517 E podo escoller entre un, tres e cinco. 294 00:16:01,517 --> 00:16:02,350 E comezar a escoller. 295 00:16:02,350 --> 00:16:03,810 Entón eu escoller un de cinco. 296 00:16:03,810 --> 00:16:05,340 Podo escoller tres, nove ou dous. 297 00:16:05,340 --> 00:16:07,570 Comezar a escoller, entón eu escoller o nove. 298 00:16:07,570 --> 00:16:09,290 Seis, cinco, ou dous, eu escollo. 299 00:16:09,290 --> 00:16:11,539 Comezar a escoller a seis. 300 00:16:11,539 --> 00:16:13,080 Nivel superior que, quen comeza a escoller? 301 00:16:13,080 --> 00:16:16,280 302 00:16:16,280 --> 00:16:18,140 Quen comeza a escoller? 303 00:16:18,140 --> 00:16:20,000 O outro cara, o meu adversario. 304 00:16:20,000 --> 00:16:22,583 Entón, eles escoller cinco, nove, ou seis, que? 305 00:16:22,583 --> 00:16:23,410 >> Audiencia: A cinco. 306 00:16:23,410 --> 00:16:25,250 >> COLUMNA: Eles escollen a cinco. 307 00:16:25,250 --> 00:16:27,400 Comezan a escoller o mínimo. 308 00:16:27,400 --> 00:16:29,690 E, a continuación, o último, escoller un, dous, ou tres. 309 00:16:29,690 --> 00:16:31,720 Comezar a escoller, entón eu escoller tres. 310 00:16:31,720 --> 00:16:34,370 Nove, sete, ou dous, eu escollo nove. 311 00:16:34,370 --> 00:16:37,070 E 11, seis, ou catro, eu escoller 11. 312 00:16:37,070 --> 00:16:41,190 Meu opoñente logo escolle tres, nove, ou 11, escolle o mínimo. 313 00:16:41,190 --> 00:16:43,290 El me dá un tres. 314 00:16:43,290 --> 00:16:47,780 E, finalmente, na parte superior da a árbore, comezar a escoller de novo. 315 00:16:47,780 --> 00:16:51,190 E comezar a escoller entre catro, cinco ou tres. 316 00:16:51,190 --> 00:16:52,270 Entón eu levo a cinco. 317 00:16:52,270 --> 00:16:55,070 318 00:16:55,070 --> 00:17:00,891 >> Se eu teño que controlar todo, eu tomar o camiño que levou ao 11. 319 00:17:00,891 --> 00:17:02,390 Pero eu non conseguir facer esa escolla. 320 00:17:02,390 --> 00:17:04,220 Se eu ir por ese camiño. 321 00:17:04,220 --> 00:17:10,710 Meu opoñente me vai obrigar a a elección que conduce a un de tres. 322 00:17:10,710 --> 00:17:14,530 Entón, o mellor que podo facer é para dar ese ramo medio, 323 00:17:14,530 --> 00:17:19,859 facer esa elección é que, finalmente, me vai levar a cinco puntos. 324 00:17:19,859 --> 00:17:23,230 Isto é o que fai minimax. 325 00:17:23,230 --> 00:17:23,807 >> Todo ben. 326 00:17:23,807 --> 00:17:24,890 Imos dar un ollo niso. 327 00:17:24,890 --> 00:17:27,480 328 00:17:27,480 --> 00:17:32,330 Entón, aquí no CS50 IDE é un programa que 329 00:17:32,330 --> 00:17:36,540 aplica minimax xogar tic-tac-toe. 330 00:17:36,540 --> 00:17:40,100 Nós imos construír Se unha representación. 331 00:17:40,100 --> 00:17:44,390 Nós imos ter dous opponent-- ou dous xogadores, o noso ordenador 332 00:17:44,390 --> 00:17:46,090 xogador e un xogador humano. 333 00:17:46,090 --> 00:17:48,980 334 00:17:48,980 --> 00:17:53,090 O xogador número un xogará o O. Isto vai ser o xogador máquina. 335 00:17:53,090 --> 00:17:55,747 Comezan a moverse segundo. 336 00:17:55,747 --> 00:17:57,830 E o outro xogador, o noso xogador humano, será X. 337 00:17:57,830 --> 00:17:59,880 >> E para facer a miña vida un pouco simple, eu vou 338 00:17:59,880 --> 00:18:03,060 etiquetar este xogador un negativo. 339 00:18:03,060 --> 00:18:05,026 Entón eu só podo multiplicar por un negativo para intercambiar 340 00:18:05,026 --> 00:18:06,400 entre un e outro xogador. 341 00:18:06,400 --> 00:18:09,030 342 00:18:09,030 --> 00:18:12,250 Todo ben, entón imos dar un ollo o que en realidade imos facer. 343 00:18:12,250 --> 00:18:15,840 Nós imos definir o noso consello. 344 00:18:15,840 --> 00:18:19,060 Será, así, nós imos para permitir que sexa tres por tres, 345 00:18:19,060 --> 00:18:21,580 ou podemos incluso xogar cinco por cinco ou sete 346 00:18:21,580 --> 00:18:28,870 por sete tic-tac-dedo do pé se como, en base a algunha dimensión D. 347 00:18:28,870 --> 00:18:31,260 >> E nós imos ter un matrimonio de funcións auxiliares 348 00:18:31,260 --> 00:18:34,360 que vai facer cousas como iniciar o screen-- ou desculpe, 349 00:18:34,360 --> 00:18:38,900 iniciar nosas variables, desmarque a pantalla, chamar a bordo da pantalla, 350 00:18:38,900 --> 00:18:41,060 un que impón unha tarxeta a ver se ou non 351 00:18:41,060 --> 00:18:44,520 hai un gañador, o que analiza a través da liña de comandos, 352 00:18:44,520 --> 00:18:50,670 só para axudar, o que le en entrada, e unha función chamada minimax. 353 00:18:50,670 --> 00:18:52,746 E iso é o que imos máis lle gusta. 354 00:18:52,746 --> 00:18:54,120 Pero imos ollar primeiro para o inicio. 355 00:18:54,120 --> 00:18:57,490 356 00:18:57,490 --> 00:18:58,510 >> O que imos facer? 357 00:18:58,510 --> 00:19:00,570 Ben, imos analizar a liña de comandos, 358 00:19:00,570 --> 00:19:04,300 acaba de ler e ver que tarxeta de dimensión que nós queremos ter. 359 00:19:04,300 --> 00:19:07,330 Imos comezar o noso consello. 360 00:19:07,330 --> 00:19:10,360 E entón nós imos entrar nun gran lazo salvaxe, repetidamente 361 00:19:10,360 --> 00:19:16,630 aceptar móvese ata que o xogo é gañou, ou non hai ningún movemento á esquerda. 362 00:19:16,630 --> 00:19:20,560 Cada vez que pasar por iso loop, imos limpar a pantalla. 363 00:19:20,560 --> 00:19:23,290 Imos chamar a bordo da pantalla. 364 00:19:23,290 --> 00:19:28,750 E nós estamos deliberadamente tipo de abstraindo estes afastado como subrutinas, 365 00:19:28,750 --> 00:19:32,030 de xeito que non hai que preocuparse moito sobre os detalles de como acontecen. 366 00:19:32,030 --> 00:19:33,480 >> Terá o código máis tarde hoxe. 367 00:19:33,480 --> 00:19:37,970 E se queres ollar a través e descubrir, pode ve-los todos. 368 00:19:37,970 --> 00:19:39,890 Pero nós imos deseñar unha tarxeta na pantalla. 369 00:19:39,890 --> 00:19:43,620 E entón nós imos comprobar e ver, temos un gañador? 370 00:19:43,620 --> 00:19:46,290 Alguén gañou este xogo? 371 00:19:46,290 --> 00:19:49,260 No caso de que teñen, imos imprimir unha mensaxe de vitoria. 372 00:19:49,260 --> 00:19:51,680 E nós imos rematar o partido. 373 00:19:51,680 --> 00:19:54,510 >> Tamén imos comprobar e ver se hai un empate. 374 00:19:54,510 --> 00:19:56,620 Vai ser doado para ver se hai un empate. 375 00:19:56,620 --> 00:20:00,700 Isto significa que todos os espazos están cheos, pero non houbo aínda un gañador. 376 00:20:00,700 --> 00:20:03,580 Podemos declarar un empate e pode facer. 377 00:20:03,580 --> 00:20:10,530 A continuación, o certo se meat-- é un xogador de máquina, 378 00:20:10,530 --> 00:20:14,120 imos permitir que xogador máquina descriptor 379 00:20:14,120 --> 00:20:19,500 mediante o uso deste algoritmo minimax, para atopar a mellor xogada que pode. 380 00:20:19,500 --> 00:20:22,310 E entón nós imos poñer este movemento cara arriba. 381 00:20:22,310 --> 00:20:27,640 >> Se non, se é un xogador humano, leremos algunha entrada do humano. 382 00:20:27,640 --> 00:20:30,800 E entón se é o humano xogador ou o xogador máquina, 383 00:20:30,800 --> 00:20:32,800 imos facer un par pouco bits de comprobación de erros, 384 00:20:32,800 --> 00:20:36,910 garantir que se mantén dentro dos límites das dimensións reais do bordo 385 00:20:36,910 --> 00:20:40,040 que temos, asegúrese que é o que o espazo baleiro, 386 00:20:40,040 --> 00:20:43,570 que ninguén poñer unha peza xa estaba alí. 387 00:20:43,570 --> 00:20:45,810 E entón nós imos só poñer unha peza no taboleiro, 388 00:20:45,810 --> 00:20:51,550 cambiar o xogador para a capa seguinte, e incrementar cantos movementos acontecer. 389 00:20:51,550 --> 00:20:54,090 >> Ese é o principal lazo para o noso xogo tic-tac-toe. 390 00:20:54,090 --> 00:20:57,000 391 00:20:57,000 --> 00:21:02,340 Minimax, entón, é exactamente o algoritmo que antes. 392 00:21:02,340 --> 00:21:04,710 O único axuste que fixemos, para que poidamos 393 00:21:04,710 --> 00:21:07,290 pode desempeñar maior placas dimensionais é que temos 394 00:21:07,290 --> 00:21:11,070 mantido este parámetro adicional chamado profundidade. 395 00:21:11,070 --> 00:21:14,870 E profundidade só di, se eu son busca abaixo través daquela árbore 396 00:21:14,870 --> 00:21:19,022 e eu fico tan lonxe para abaixo ademais de algún nivel de profundidade 397 00:21:19,022 --> 00:21:20,730 que eu só non quero para ir máis lonxe, 398 00:21:20,730 --> 00:21:25,630 Vou deixar e só avaliar a bordo naquel momento. 399 00:21:25,630 --> 00:21:27,310 Vou comprobar e ver se hai un gañador. 400 00:21:27,310 --> 00:21:29,240 Se hai un gañador, eu devolve-los. 401 00:21:29,240 --> 00:21:31,720 Se non, eu vou pasar por un loop. 402 00:21:31,720 --> 00:21:34,380 E eu vou dicir, para todos as posibles localizacións 403 00:21:34,380 --> 00:21:38,080 que eu podería posiblemente tomar como miña cambio, eu vou 404 00:21:38,080 --> 00:21:43,760 construír unha placa hipotética que inclúe a miña xogada na que o consello, 405 00:21:43,760 --> 00:21:45,960 e, a continuación, chama recursivamente minimax. 406 00:21:45,960 --> 00:21:49,360 407 00:21:49,360 --> 00:21:53,900 >> Se é a miña xogada, eu teño que atopar o aquel que ten a maior puntuación. 408 00:21:53,900 --> 00:21:58,710 Se é movemento do meu opoñente, atopamos aquel que ten a puntuación mínima. 409 00:21:58,710 --> 00:22:02,240 E todo o demais é mantendo só rexistro. 410 00:22:02,240 --> 00:22:04,789 Todo ben, entón imos ver esta carreira. 411 00:22:04,789 --> 00:22:06,830 En realidade, talvez o que pudermos obter un par de voluntarios 412 00:22:06,830 --> 00:22:09,930 para vir e xogar tic-tac-toe. 413 00:22:09,930 --> 00:22:12,780 [Inaudível] un, e un máis, dous, alí mesmo. 414 00:22:12,780 --> 00:22:13,550 Imos cara arriba. 415 00:22:13,550 --> 00:22:19,290 416 00:22:19,290 --> 00:22:23,650 >> Entón, imos adiante e reinicie esta completamente. 417 00:22:23,650 --> 00:22:24,150 Entón, ola. 418 00:22:24,150 --> 00:22:24,920 >> Audiencia: Ola. 419 00:22:24,920 --> 00:22:25,420 >> COLUMNA: Cal é o seu nome? 420 00:22:25,420 --> 00:22:26,086 >> Audiencia: Gorav. 421 00:22:26,086 --> 00:22:26,840 COLUMNA: Gorav. 422 00:22:26,840 --> 00:22:27,800 >> Audiencia: Eu son Layla. 423 00:22:27,800 --> 00:22:29,490 >> Orador: E Layla, e Layla, desculpe. 424 00:22:29,490 --> 00:22:30,384 Imos cara arriba. 425 00:22:30,384 --> 00:22:32,050 Gorav, nós imos ter que ir primeiro. 426 00:22:32,050 --> 00:22:37,710 E eu vou pedir-lle para ser un non terriblemente bo xogador tic-tac-toe. 427 00:22:37,710 --> 00:22:40,130 OK, entón toda a presión está fóra en ti. 428 00:22:40,130 --> 00:22:44,660 A ver, porén, que a nosa máquina xogador pode realmente facer algo intelixente. 429 00:22:44,660 --> 00:22:45,310 Entón vai adiante. 430 00:22:45,310 --> 00:22:49,830 Vai escribir en que coordinan desexa poñer o seu X in. 431 00:22:49,830 --> 00:22:55,170 A0, OK, ea máquina ha ir inmediatamente e poñer a súa marca na A1. 432 00:22:55,170 --> 00:22:56,640 >> Pon a O no taboleiro. 433 00:22:56,640 --> 00:22:58,970 Todo ben, agora vai adiante. 434 00:22:58,970 --> 00:23:00,193 Onde quere ir? 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 Noso xogador máquina tomou o cadrado do medio, bloqueou ti. 438 00:23:08,430 --> 00:23:10,320 Así, foi unha boa, cousa intelixente para que faga. 439 00:23:10,320 --> 00:23:13,430 440 00:23:13,430 --> 00:23:14,250 Bloqueou. 441 00:23:14,250 --> 00:23:15,210 Isto é excelente. 442 00:23:15,210 --> 00:23:16,390 El marca o canto alí. 443 00:23:16,390 --> 00:23:23,890 444 00:23:23,890 --> 00:23:30,430 >> E vai forza-lo a tomar o último espazo, B0. 445 00:23:30,430 --> 00:23:32,220 E o xogo termina en empate. 446 00:23:32,220 --> 00:23:35,030 Pero tivo un razoable xogo contra ti, non? 447 00:23:35,030 --> 00:23:36,956 Todo ben, moitas grazas, Gorav. 448 00:23:36,956 --> 00:23:40,860 >> [Aplausos] 449 00:23:40,860 --> 00:23:44,723 >> Todo ben, Layla, imos o xogo en ti aquí. 450 00:23:44,723 --> 00:23:46,940 >> Audiencia: Oh, gran. 451 00:23:46,940 --> 00:23:49,950 >> COLUMNA: Estamos indo dar- vostede catro por catro tic-tac-toe. 452 00:23:49,950 --> 00:23:54,760 Agora, en catro por catro, tes que gañar con catro nunha fileira, e non tres nunha fileira. 453 00:23:54,760 --> 00:23:56,135 E é toda súa. 454 00:23:56,135 --> 00:24:02,180 455 00:24:02,180 --> 00:24:04,420 Así Layla levou D1. 456 00:24:04,420 --> 00:24:11,730 Estamos indo a seguir noso xogador do ordenador aquí. 457 00:24:11,730 --> 00:24:16,910 Tres por tres tic-tac-toe é o tipo de que é doado para todos nós. 458 00:24:16,910 --> 00:24:21,960 Senón que é bo ver o xogador do ordenador facendo movementos intelixentes. 459 00:24:21,960 --> 00:24:23,725 Catro por catro comeza a ser un pouco máis complicado. 460 00:24:23,725 --> 00:24:42,960 461 00:24:42,960 --> 00:24:44,230 >> Moi ben feito. 462 00:24:44,230 --> 00:24:46,210 Todo ben, entón Layla do finalizou. 463 00:24:46,210 --> 00:24:48,270 Oh, e debemos terminar alí. 464 00:24:48,270 --> 00:24:51,870 Pero imos facer unha aquí. 465 00:24:51,870 --> 00:24:53,480 Entón, Layla, grazas. 466 00:24:53,480 --> 00:24:55,112 Moi ben feito. 467 00:24:55,112 --> 00:24:57,517 >> [Aplausos] 468 00:24:57,517 --> 00:25:00,410 469 00:25:00,410 --> 00:25:04,750 >> Así, o noso xogador tic-tac-toe vai ea través atopa locais, 470 00:25:04,750 --> 00:25:07,040 resolve-los usando este minimax. 471 00:25:07,040 --> 00:25:08,990 E eu tiña unha configuración de profundidade en que, para que 472 00:25:08,990 --> 00:25:11,010 non ía correr moi rápido, que pode ser porque 473 00:25:11,010 --> 00:25:16,790 Layla soubo ir ben fronte como se fixo, e fixo moi ben. 474 00:25:16,790 --> 00:25:20,450 Pero estes sistemas que pasar e forza bruta 475 00:25:20,450 --> 00:25:23,870 ir máis fondo e máis profundo, e máis profundo, e manter a atopar a solución 476 00:25:23,870 --> 00:25:29,890 que precisan, estes tipos de sistemas son bastante exitoso para estes, ben, 477 00:25:29,890 --> 00:25:32,700 xogos de mesa por defecto. 478 00:25:32,700 --> 00:25:37,060 >> E, de feito, se miramos un tres por tres xogo tic-tac-toe, 479 00:25:37,060 --> 00:25:40,040 este é basicamente un problema resolto. 480 00:25:40,040 --> 00:25:45,430 E este é un diagrama marabilloso Randall Munroe de xkcd en, 481 00:25:45,430 --> 00:25:52,130 mostrando que ten que moverse tomar, dada movementos do seu opoñente. 482 00:25:52,130 --> 00:25:56,420 Isto é algo que poderiamos facilmente especificar antes de tempo. 483 00:25:56,420 --> 00:26:00,180 Pero o que ocorre cando chegamos a máis xogos complexos, xogos máis complicados, 484 00:26:00,180 --> 00:26:05,690 onde existen placas grandes, máis posibilidades, a estratexia máis profunda? 485 00:26:05,690 --> 00:26:09,660 >> Acontece que este forza bruta busca aínda 486 00:26:09,660 --> 00:26:14,150 fai bastante ben, agás cando chegar ao punto 487 00:26:14,150 --> 00:26:19,230 onde a árbore é tan grande que non pode representar todo. 488 00:26:19,230 --> 00:26:22,370 489 00:26:22,370 --> 00:26:28,280 Cando non pode calcular toda a árbore, cando non pode ir para adiante e empuxe 490 00:26:28,280 --> 00:26:32,204 Se para o punto onde ten comezara a árbore enteira na memoria, 491 00:26:32,204 --> 00:26:34,370 ou se pode obterse na memoria e ela só vai 492 00:26:34,370 --> 00:26:39,200 levalo moito tempo para buscar Lo, ten que facer algo máis intelixente. 493 00:26:39,200 --> 00:26:42,620 494 00:26:42,620 --> 00:26:46,450 >> Co fin de facer iso, ten que facer dúas cousas. 495 00:26:46,450 --> 00:26:49,030 En primeiro lugar, ten que atopar algún forma de limitar a súa profundidade. 496 00:26:49,030 --> 00:26:50,370 Ben, iso é OK. 497 00:26:50,370 --> 00:26:55,740 Podemos atopar algunhas agradables, mínimo e dicir, só se pode ir tan fondo. 498 00:26:55,740 --> 00:27:00,890 Pero cando fai isto, iso significa que ter estes ferros parcialmente incompletos. 499 00:27:00,890 --> 00:27:04,770 E ten que escoller, eu gusto esta tarxeta parcialmente incompleta, 500 00:27:04,770 --> 00:27:08,600 ou esta tarxeta parcialmente incompleta? 501 00:27:08,600 --> 00:27:11,910 >> E nos nosos catro por catro xogo tic-tac-toe, 502 00:27:11,910 --> 00:27:15,240 noso xogador do ordenador descendeu para a parte inferior e dixo, 503 00:27:15,240 --> 00:27:16,800 Teño dúas placas diferentes. 504 00:27:16,800 --> 00:27:17,940 Ningún dos dous é unha vitoria. 505 00:27:17,940 --> 00:27:19,120 Ningún dos dous é unha perda. 506 00:27:19,120 --> 00:27:22,070 Ningún dos dous é un empate. 507 00:27:22,070 --> 00:27:24,100 Como podo escoller entre eles? 508 00:27:24,100 --> 00:27:26,200 E el non tiña unha forma intelixente de facelo. 509 00:27:26,200 --> 00:27:28,910 510 00:27:28,910 --> 00:27:32,850 >> Vemos este tipo de avaliación acontecen o tempo 511 00:27:32,850 --> 00:27:35,290 como nós entrar en xogos máis complexos. 512 00:27:35,290 --> 00:27:37,600 O xadrez é un gran exemplo. 513 00:27:37,600 --> 00:27:41,550 No xadrez, temos, en primeiro lugar de todo, unha tarxeta de maior. 514 00:27:41,550 --> 00:27:43,370 Temos moito máis pezas. 515 00:27:43,370 --> 00:27:47,930 E o posicionamento destas pezas e do xeito que estas pezas se moven 516 00:27:47,930 --> 00:27:50,370 é criticamente importante. 517 00:27:50,370 --> 00:27:53,700 Entón, se eu queira utilizar minimax, Necesito poder especificar 518 00:27:53,700 --> 00:27:58,240 e dicir, esta tarxeta, onde ninguén gañou ou perdeu, con todo, 519 00:27:58,240 --> 00:28:04,310 é dalgunha forma mellor que estoutro tarxeta, onde ninguén gañou ou perdeu. 520 00:28:04,310 --> 00:28:06,740 >> Para iso, eu podería fazê- cousas como eu podería só 521 00:28:06,740 --> 00:28:10,787 contar cantas pezas que eu teño e cantas pezas ten? 522 00:28:10,787 --> 00:28:12,870 Ou eu podería dar diferente pezas puntos diferentes. 523 00:28:12,870 --> 00:28:14,420 Miña raíña vale 20 puntos. 524 00:28:14,420 --> 00:28:16,500 Seu peón vale un punto. 525 00:28:16,500 --> 00:28:18,920 Quen ten máis puntos en total? 526 00:28:18,920 --> 00:28:22,300 Ou eu podería considerar cousas como: quen ten o mellor posición do taboleiro? 527 00:28:22,300 --> 00:28:26,820 Quen é a quenda seguinte, calquera cousa que eu poida 528 00:28:26,820 --> 00:28:31,220 non para avaliar con máis precisión cal destas posibilidades 529 00:28:31,220 --> 00:28:34,660 é mellor sen considerando exhaustivamente 530 00:28:34,660 --> 00:28:36,565 cada movemento que podería vir despois diso. 531 00:28:36,565 --> 00:28:39,740 532 00:28:39,740 --> 00:28:45,130 >> Agora, para facer este traballo, unha das cousas que é 533 00:28:45,130 --> 00:28:48,680 vai facer realmente importante para nós non é só movendo en liña recta 534 00:28:48,680 --> 00:28:53,720 ata unha determinada profundidade límite, pero ser capaz de dicir: 535 00:28:53,720 --> 00:28:59,380 unha desas ideas que eu teñen é tan malo que é 536 00:28:59,380 --> 00:29:02,280 non paga a pena considerar todas as formas posibles 537 00:29:02,280 --> 00:29:06,680 que as cousas poden ir de mal a peor. 538 00:29:06,680 --> 00:29:12,760 Para iso, imos engadir minimax un principio chamado alph-beta. 539 00:29:12,760 --> 00:29:16,340 E alfa-beta di, se ten unha mala idea, 540 00:29:16,340 --> 00:29:22,840 non perda o seu tempo tentando descubrir como é malo. 541 00:29:22,840 --> 00:29:24,990 >> Entón aquí está o que imos facer. 542 00:29:24,990 --> 00:29:28,620 Nós imos ter o mesmo principios que tiñamos antes, 543 00:29:28,620 --> 00:29:32,200 o mesmo tipo minimax de investigación, só somos 544 00:29:32,200 --> 00:29:37,570 vai seguir, non só do valores reais de que dispoñemos, pero imos 545 00:29:37,570 --> 00:29:41,440 seguir o mellor posible valor que puiden chegar, 546 00:29:41,440 --> 00:29:45,700 eo peor posible resultado que eu podería ter. 547 00:29:45,700 --> 00:29:50,470 E calquera momento o peor posible cousa é mirar probable, 548 00:29:50,470 --> 00:29:52,694 Vou deixar esa parte da árbore. 549 00:29:52,694 --> 00:29:54,610 E eu non vou incomodar mesmo mirando para el anymore. 550 00:29:54,610 --> 00:29:57,680 551 00:29:57,680 --> 00:30:02,600 >> Todo ben, entón imaxine que comecemos con esta mesma árbore xogo exacto. 552 00:30:02,600 --> 00:30:05,200 E agora estamos indo a ir de novo, todo o camiño 553 00:30:05,200 --> 00:30:07,200 para que parte inferior esquerda. 554 00:30:07,200 --> 00:30:11,180 E nese parte inferior esquerda canto, nós mirar e avaliamos esta tarxeta. 555 00:30:11,180 --> 00:30:15,700 Quizais sexa un catro por catro tic-tac-toe tarxeta, ou que é un taboleiro de xadrez. 556 00:30:15,700 --> 00:30:18,620 Pero miramos para el, e nós avaliamos Lo, e temos un valor de oito. 557 00:30:18,620 --> 00:30:22,290 558 00:30:22,290 --> 00:30:28,030 >> Nese punto, sabemos que nós estamos indo a obter, polo menos, 559 00:30:28,030 --> 00:30:32,380 oito puntos de esta decisión inferior. 560 00:30:32,380 --> 00:30:36,620 Non importa o que o outro dous son, que sete e que dous. 561 00:30:36,620 --> 00:30:38,580 Poderían ser calquera valores querían ser. 562 00:30:38,580 --> 00:30:41,279 Nós imos chegar a menos oito puntos. 563 00:30:41,279 --> 00:30:43,070 Todo ben, pero poderiamos dalle confía. 564 00:30:43,070 --> 00:30:45,080 Quizais un deles é mellor que oito. 565 00:30:45,080 --> 00:30:46,000 >> Nós miramos para o sete. 566 00:30:46,000 --> 00:30:46,910 Está mellor que oito? 567 00:30:46,910 --> 00:30:48,680 Non, iso non cambia nosa opinión en todo. 568 00:30:48,680 --> 00:30:49,460 Nós miramos para os dous. 569 00:30:49,460 --> 00:30:50,543 Está mellor que oito? 570 00:30:50,543 --> 00:30:52,580 Non, iso non cambia nosa opinión en todo. 571 00:30:52,580 --> 00:30:55,480 Polo tanto, agora sabemos que xa esgotou todas as posibilidades alí. 572 00:30:55,480 --> 00:30:58,330 Non estamos indo a chegar nada mellor que oito. 573 00:30:58,330 --> 00:31:01,310 Estamos indo para obter exactamente oito. 574 00:31:01,310 --> 00:31:03,825 >> E así nós cambiamos ese nó e digamos, que é agora unha certeza. 575 00:31:03,825 --> 00:31:07,010 576 00:31:07,010 --> 00:31:10,270 Nós subir un nivel por riba diso. 577 00:31:10,270 --> 00:31:13,820 E agora sabemos algo sobre ese nivel de minimización. 578 00:31:13,820 --> 00:31:18,560 Sabemos que nunca chegaremos máis de oito puntos se descendemos 579 00:31:18,560 --> 00:31:20,910 nesa dirección. 580 00:31:20,910 --> 00:31:22,980 Porque aínda que os outros dous ramos vir 581 00:31:22,980 --> 00:31:26,170 para ser fantástico e paga a pena miles de puntos, cada, 582 00:31:26,170 --> 00:31:31,666 o noso adversario daranos a mínimo, e nos dá a oito. 583 00:31:31,666 --> 00:31:32,790 Todo ben, ben, imos ver. 584 00:31:32,790 --> 00:31:35,190 Seguiremos por ese camiño. 585 00:31:35,190 --> 00:31:38,490 Descendemos para que medio á esquerda. 586 00:31:38,490 --> 00:31:40,560 Miramos para abaixo e vemos que hai un nove. 587 00:31:40,560 --> 00:31:45,590 Sabemos que imos chegar polo menos nove puntos, indo para abaixo 588 00:31:45,590 --> 00:31:47,720 que camiño do medio. 589 00:31:47,720 --> 00:31:52,110 E, neste punto, podemos só facer unha pausa. 590 00:31:52,110 --> 00:31:56,910 E podemos dicir, mira, eu coñecer o nivel anterior, 591 00:31:56,910 --> 00:32:01,160 Eu estou indo a obter non máis que oito apunta cara abaixo, indo nesta dirección. 592 00:32:01,160 --> 00:32:05,670 Pero se eu fun para o medio camiño en vez do camiño da esquerda, 593 00:32:05,670 --> 00:32:08,980 Quere obter polo menos nove puntos. 594 00:32:08,980 --> 00:32:13,590 >> Meu opoñente é nunca vai déixeme ir por ese camiño do medio. 595 00:32:13,590 --> 00:32:14,650 Comezan a escoller. 596 00:32:14,650 --> 00:32:18,140 E eles están indo a escoller o camiño á esquerda en dirección a oito, 597 00:32:18,140 --> 00:32:23,650 no canto de no medio cara o que é, polo menos, nove puntos. 598 00:32:23,650 --> 00:32:25,334 Entón, nese punto, vou parar. 599 00:32:25,334 --> 00:32:26,500 E eu vou dicir, xa sabe o que? 600 00:32:26,500 --> 00:32:29,990 Non teño que mirar para máis baixo nesa dirección. 601 00:32:29,990 --> 00:32:32,270 Porque eu non vou chegar alí. 602 00:32:32,270 --> 00:32:36,660 >> Podo ignorar que un, e podo ignorar que seis, 603 00:32:36,660 --> 00:32:39,720 porque iso non vai ocorrer. 604 00:32:39,720 --> 00:32:42,470 Entón, eu vou baixar e eu vou Considero o seguinte posibilidade. 605 00:32:42,470 --> 00:32:44,830 Eu vou alí e digo, eu vexo un dous. 606 00:32:44,830 --> 00:32:47,125 Sei que se eu ficar aquí, eu son se ve polo menos dous. 607 00:32:47,125 --> 00:32:49,810 608 00:32:49,810 --> 00:32:50,470 Aceptar. 609 00:32:50,470 --> 00:32:51,520 I continuar. 610 00:32:51,520 --> 00:32:52,440 Eu vexo un catro. 611 00:32:52,440 --> 00:32:54,920 Sei que estou indo a obter, polo menos, catro. 612 00:32:54,920 --> 00:32:57,200 Aínda hai moito entre catro e oito, con todo. 613 00:32:57,200 --> 00:32:58,454 Entón eu sigo indo. 614 00:32:58,454 --> 00:32:59,870 Eu ollo para abaixo e vexo que hai un. 615 00:32:59,870 --> 00:33:01,614 Todo ben, sei que se I ir por este camiño, 616 00:33:01,614 --> 00:33:03,280 Eu vou ser capaz de elixir o catro. 617 00:33:03,280 --> 00:33:06,540 618 00:33:06,540 --> 00:33:08,980 Que o meu adversario vai facer? 619 00:33:08,980 --> 00:33:12,310 Entre algo que me dá oito, algo que me dá catro, 620 00:33:12,310 --> 00:33:14,730 e que algo me dá, polo menos, nove, 621 00:33:14,730 --> 00:33:17,550 ben, que vai me dar catro. 622 00:33:17,550 --> 00:33:20,110 E sei agora no moi alto, eu vou 623 00:33:20,110 --> 00:33:23,145 para poder obter, polo menos, catro puntos fóra deste xogo. 624 00:33:23,145 --> 00:33:27,030 625 00:33:27,030 --> 00:33:30,900 >> Toda a idea de alfa-beta é cortar partes da árbore para 626 00:33:30,900 --> 00:33:32,530 que eu non mirar para eles anymore. 627 00:33:32,530 --> 00:33:35,964 Pero aínda parece que eu estiven mirando para unha chea de árbore. 628 00:33:35,964 --> 00:33:36,880 Seguiremos indo para abaixo. 629 00:33:36,880 --> 00:33:38,305 Imos descender a próxima agora. 630 00:33:38,305 --> 00:33:39,680 Alí no fondo, eu atopar un. 631 00:33:39,680 --> 00:33:41,030 Sei que estou indo a obter, polo menos, un. 632 00:33:41,030 --> 00:33:41,690 Eu fico mirando. 633 00:33:41,690 --> 00:33:42,625 >> I atopar un tres. 634 00:33:42,625 --> 00:33:44,250 Sei que estou indo a obter, polo menos, tres. 635 00:33:44,250 --> 00:33:44,840 I continuar. 636 00:33:44,840 --> 00:33:45,660 I atopar un cinco. 637 00:33:45,660 --> 00:33:49,760 Sei que estou indo a obter cinco se eu baixar ese camiño. 638 00:33:49,760 --> 00:33:52,580 E eu tamén sei, a continuación, que o meu adversario, se eu 639 00:33:52,580 --> 00:33:55,510 escoller o medio de os tres grandes opcións, 640 00:33:55,510 --> 00:34:01,440 el me vai dar algo que é cinco ou menos. 641 00:34:01,440 --> 00:34:02,150 >> Aceptar. 642 00:34:02,150 --> 00:34:03,400 Podo seguir aí. 643 00:34:03,400 --> 00:34:06,470 Podo ollar para abaixo e eu pódese dicir, que eu vou 644 00:34:06,470 --> 00:34:08,239 de obter, se eu baixar o camiño do medio? 645 00:34:08,239 --> 00:34:09,909 Eu estou indo a obter, así, tres alí. 646 00:34:09,909 --> 00:34:12,080 Eu estou indo a obter algo que é polo menos tres. 647 00:34:12,080 --> 00:34:16,030 Aínda hai cousas entre tres e cinco, entón eu continúe a buscar. 648 00:34:16,030 --> 00:34:20,203 Oh, un nove, eu vou sempre levar isto ao longo dun tres. 649 00:34:20,203 --> 00:34:22,744 Eu estou indo a obter, polo menos, nove se eu for por ese camiño do medio. 650 00:34:22,744 --> 00:34:25,530 651 00:34:25,530 --> 00:34:31,010 >> Agora o meu adversario para e di: mire, non hai ningún punto anymore. 652 00:34:31,010 --> 00:34:33,669 Sei que o meu minimización opoñente, é 653 00:34:33,669 --> 00:34:36,210 me vai dar a cousa que é menos que ou igual a cinco, 654 00:34:36,210 --> 00:34:39,030 ao contrario da cousa que é maior que ou igual a nove. 655 00:34:39,030 --> 00:34:39,530 Eu paro. 656 00:34:39,530 --> 00:34:40,779 Non ollo máis para iso. 657 00:34:40,779 --> 00:34:43,280 I continuar. 658 00:34:43,280 --> 00:34:44,850 >> Eu ollo para abaixo nun presente. 659 00:34:44,850 --> 00:34:46,370 Ata o fondo, creo un seis. 660 00:34:46,370 --> 00:34:50,040 Sei que estou indo a obter, polo menos, seis. 661 00:34:50,040 --> 00:34:53,130 E o que podo facer? 662 00:34:53,130 --> 00:34:54,877 Podo parar. 663 00:34:54,877 --> 00:34:57,460 Porque non hai unha selección entre algo que é, polo menos, seis 664 00:34:57,460 --> 00:34:59,250 e algo que é menos de cinco anos, é 665 00:34:59,250 --> 00:35:02,570 vai dar-me a cousa que é menos que cinco. 666 00:35:02,570 --> 00:35:04,779 E agora sei que vou para obter exactamente esa opción. 667 00:35:04,779 --> 00:35:06,195 Eu estou indo a obter cinco elección. 668 00:35:06,195 --> 00:35:08,980 669 00:35:08,980 --> 00:35:10,010 >> Eu volver a subir ata o cumio. 670 00:35:10,010 --> 00:35:11,450 Que é que eu vou escoller entre algo 671 00:35:11,450 --> 00:35:14,449 que é maior que ou igual a catro, ou algo que é igual a cinco? 672 00:35:14,449 --> 00:35:17,140 Vou tomar algo que é, polo menos, cinco anos. 673 00:35:17,140 --> 00:35:20,490 Descendo o último camiño, todo o camiño ata o fondo. 674 00:35:20,490 --> 00:35:21,260 Hai un un. 675 00:35:21,260 --> 00:35:23,410 OK, polo menos eu estou indo a obter un punto. 676 00:35:23,410 --> 00:35:24,427 I continuar. 677 00:35:24,427 --> 00:35:25,760 Dous, oh, iso é mellor que unha. 678 00:35:25,760 --> 00:35:27,100 Eu estou indo a obter, polo menos, dous. 679 00:35:27,100 --> 00:35:28,610 I atopar un tres. 680 00:35:28,610 --> 00:35:31,450 Sei que estou indo a obter tres. 681 00:35:31,450 --> 00:35:34,690 >> E o punto de arriba que, o meu adversario vai 682 00:35:34,690 --> 00:35:38,540 para me dar algo que é menos que ou igual a tres. 683 00:35:38,540 --> 00:35:40,940 E agora podo parar. 684 00:35:40,940 --> 00:35:46,290 Porque na elección entre eu estar capaz de obter un cinco e meu opoñente 685 00:35:46,290 --> 00:35:52,290 dándome algo inferior a tres, Sempre vou ter que cinco. 686 00:35:52,290 --> 00:35:56,810 Así que non avaliar que parte inferior da árbore de todo. 687 00:35:56,810 --> 00:35:59,470 >> Agora, isto pode parecer menor. 688 00:35:59,470 --> 00:36:03,630 Pero cando pequenos anacos de aritmética, superior e inferior, 689 00:36:03,630 --> 00:36:10,640 pode cortar partes enteiras de esta árbore en crecemento exponencial, 690 00:36:10,640 --> 00:36:14,280 que conduce a un enorme cantidade de aforro, aforro 691 00:36:14,280 --> 00:36:17,630 que son grandes abondo para que eu Pode comezar a xogar competitivamente 692 00:36:17,630 --> 00:36:21,330 en xogos máis complexos. 693 00:36:21,330 --> 00:36:27,030 >> Todo ben, se miramos para o tamaño e complexidade de xogos distintos, 694 00:36:27,030 --> 00:36:29,470 tic-tac-toe foi o noso exemplo fácil. 695 00:36:29,470 --> 00:36:32,150 Temos unha pequena placa, tres por tres. 696 00:36:32,150 --> 00:36:36,030 Estivemos con, como máximo, unha media de preto de catro diferentes opcións 697 00:36:36,030 --> 00:36:38,440 como nós atravesamos o xogo. 698 00:36:38,440 --> 00:36:42,720 Temos algo en torno de 10 a posibles follas diferentes quinto. 699 00:36:42,720 --> 00:36:45,200 Ea construción dun tic-tac-toe xogador, ben, só fixen iso. 700 00:36:45,200 --> 00:36:47,460 É doado. 701 00:36:47,460 --> 00:36:49,890 >> Ou tamén ata algo máis complexo, como Connect Four. 702 00:36:49,890 --> 00:36:53,170 Vostede recorda deste xogo onde deixar caer as pequenas fichas? 703 00:36:53,170 --> 00:36:58,490 É unha tarxeta de seis por sete, non moi grande, aínda 704 00:36:58,490 --> 00:37:00,770 ten aproximadamente a mesma galla factor como tic-tac-toe. 705 00:37:00,770 --> 00:37:05,410 Teño preto de catro opcións onde podo poñer as cousas en. 706 00:37:05,410 --> 00:37:10,760 Pero agora, eu teño moito máis leva, 10 elevado á potencia 21. 707 00:37:10,760 --> 00:37:14,440 Isto é algo que é doado abondo para que resolver-lo inmediatamente. 708 00:37:14,440 --> 00:37:17,560 >> Checkers, máis complex-- ten un oito por oito bordo. 709 00:37:17,560 --> 00:37:20,570 Está só na metade da los en calquera momento, con todo. 710 00:37:20,570 --> 00:37:24,930 Ten unha ramificación factor que é preto de 2,8. 711 00:37:24,930 --> 00:37:28,160 Ben, temos unha parella move-se pode tomar. 712 00:37:28,160 --> 00:37:33,870 Ten preto de 10 a 31 de follas, espazos maiores e máis grandes, e grandes. 713 00:37:33,870 --> 00:37:37,340 Como eu teño que buscar estes espazos cada vez máis grandes, 714 00:37:37,340 --> 00:37:42,220 que é cando as cousas como beta e alfa- sendo capaz de cortar ramas enteiros 715 00:37:42,220 --> 00:37:44,420 pasa a ser esencial. 716 00:37:44,420 --> 00:37:47,440 >> Agora, damas foi fácil o suficiente en 1992. 717 00:37:47,440 --> 00:37:51,400 Un programa de ordenador chamado Chinook bater as damas mundo 718 00:37:51,400 --> 00:37:53,590 campión, Marion Tinsley. 719 00:37:53,590 --> 00:37:57,260 E, desde entón, non xogador de mestre humano ten 720 00:37:57,260 --> 00:38:02,290 foi capaz de vencer o mellor sistemas computacionais. 721 00:38:02,290 --> 00:38:06,570 Mira algo como xadrez, agora de novo, temos un oito por oito bordo. 722 00:38:06,570 --> 00:38:09,870 Pero temos moito máis complexo pezas, tanto os movementos máis complexos. 723 00:38:09,870 --> 00:38:14,610 Temos un factor de ramificación duns 35, 35 movementos posibles en media 724 00:38:14,610 --> 00:38:20,030 que eu poida tomar, e un estado espazo, un número de follas 725 00:38:20,030 --> 00:38:28,950 que creceu de 10 a 123 o poder, un número enorme de posibilidades. 726 00:38:28,950 --> 00:38:35,570 >> Aínda así, os procesadores modernos son capaces de facelo correctamente. 727 00:38:35,570 --> 00:38:43,900 En 1995 e, a continuación, en 1997, un ordenador programa chamado Deep Blue construído pola IBM 728 00:38:43,900 --> 00:38:49,601 que corría nun supercomputador xigante bater o actual campión mundial, 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 Este foi un punto de viraxe. 732 00:38:56,650 --> 00:39:00,620 Hoxe, porén, que a mesma transformación poder senta no meu MacBook. 733 00:39:00,620 --> 00:39:04,180 734 00:39:04,180 --> 00:39:06,440 >> Velocidade de procesamento mantén quedando máis rápido e máis rápido. 735 00:39:06,440 --> 00:39:09,500 Podemos valorar máis e máis placas máis rápidas e máis rápido. 736 00:39:09,500 --> 00:39:14,550 Pero o máis importante, temos mellor funcións de avaliación e mellor poda 737 00:39:14,550 --> 00:39:15,460 métodos. 738 00:39:15,460 --> 00:39:19,560 Así, podemos buscar o espazo máis complexo. 739 00:39:19,560 --> 00:39:22,350 A maior do consello xogos que podemos pensar, 740 00:39:22,350 --> 00:39:26,310 Vai algo como isto é ten unha tarxeta de 19 por 19, 741 00:39:26,310 --> 00:39:32,490 Agora, de súpeto, estamos alén do punto onde os sistemas computacionais pode gañar. 742 00:39:32,490 --> 00:39:34,530 Non hai ningún computacional sistema por aí 743 00:39:34,530 --> 00:39:38,880 que pode bater un xogador profesional Go. 744 00:39:38,880 --> 00:39:45,000 Os mellores sistemas de hoxe clasificalos lo sobre o tipo de bo nivel afeccionado. 745 00:39:45,000 --> 00:39:49,285 Así, aínda hai un pouco para fóra hai que non pode chegar a aínda. 746 00:39:49,285 --> 00:39:51,840 747 00:39:51,840 --> 00:39:55,360 >> Todo ben, estas xogos de mesa tradicionais, 748 00:39:55,360 --> 00:39:58,560 este tipo de sistemas onde construír esa minimax, se ten 749 00:39:58,560 --> 00:40:06,300 alfa-beta ou non, estes algoritmos de traballar porque hai certas restricións. 750 00:40:06,300 --> 00:40:08,520 Temos a información perfecta sobre o mundo. 751 00:40:08,520 --> 00:40:11,690 Sabemos onde están todas as pezas. 752 00:40:11,690 --> 00:40:13,570 O mundo é estático. 753 00:40:13,570 --> 00:40:16,220 Ninguén queda para mover o anacos de todo, mentres eu estou 754 00:40:16,220 --> 00:40:20,640 sentado alí pensando, tomando miña vez. 755 00:40:20,640 --> 00:40:23,140 Hai un espazo de acción que é discreta. 756 00:40:23,140 --> 00:40:26,900 Podo poñer o meu peón aquí, ou podo poñer o meu peón aquí. 757 00:40:26,900 --> 00:40:30,520 Eu non estou autorizado a poñer o meu peón en a liña entre os dous cadrados. 758 00:40:30,520 --> 00:40:34,430 759 00:40:34,430 --> 00:40:36,520 >> E, finalmente, as accións son deterministas. 760 00:40:36,520 --> 00:40:39,790 Sei que se eu digo, Rook cabaleiro para tres, 761 00:40:39,790 --> 00:40:44,660 miña torre vai acabar no cabaleiro tres, sempre que é un movemento válido. 762 00:40:44,660 --> 00:40:47,830 Non hai incerteza sobre iso. 763 00:40:47,830 --> 00:40:52,490 Agora, como eu ir máis distintos tipos de xogos, 764 00:40:52,490 --> 00:40:55,960 temos que romper esas suposicións. 765 00:40:55,960 --> 00:41:00,020 >> E se eu ir a algo como clásicos videoxogos? 766 00:41:00,020 --> 00:41:04,180 Aquí está unha selección de vídeos xogos do Atari 2600. 767 00:41:04,180 --> 00:41:05,180 O que eu teño alí enriba? 768 00:41:05,180 --> 00:41:08,440 Teño Frogger, Espazo Invaders, Pitfall, e Pac-Man. 769 00:41:08,440 --> 00:41:11,290 770 00:41:11,290 --> 00:41:14,840 Que tipo de ambientes eu teño aquí agora? 771 00:41:14,840 --> 00:41:16,900 Cal destas premisas eu teño que romper? 772 00:41:16,900 --> 00:41:19,410 773 00:41:19,410 --> 00:41:21,570 >> Ben, iso depende do xogo. 774 00:41:21,570 --> 00:41:28,170 Podería xogar xadrez en 2600, e sería exactamente como era antes. 775 00:41:28,170 --> 00:41:33,020 Para a maioría destes sistemas, hai coñecemento completo sobre o mundo. 776 00:41:33,020 --> 00:41:36,300 Hai completamente accións determinista. 777 00:41:36,300 --> 00:41:38,330 Pero, xeralmente, o mundo non estático. 778 00:41:38,330 --> 00:41:41,970 É dicir, mentres eu estou sentado alí esperando, algo se está movendo. 779 00:41:41,970 --> 00:41:44,320 As pantasmas están vindo para me incorporarse. 780 00:41:44,320 --> 00:41:46,570 O escorpión me seguindo por baixo. 781 00:41:46,570 --> 00:41:48,880 Os invasores do espazo son chegando cada vez máis preto. 782 00:41:48,880 --> 00:41:54,020 783 00:41:54,020 --> 00:41:55,510 Como ben podemos facer contra iso? 784 00:41:55,510 --> 00:41:58,640 785 00:41:58,640 --> 00:42:02,790 >> Hai uns anos, Google tiña un proxecto chamado 786 00:42:02,790 --> 00:42:12,030 DeepMind onde adestraron un ordenador programa de xogar Atari 2600 xogos. 787 00:42:12,030 --> 00:42:16,120 E se pensas que iso non é grave negocio, os resultados do seu estudo 788 00:42:16,120 --> 00:42:19,920 foron publicados na revista Nature, de xeito case tan bo unha publicación 789 00:42:19,920 --> 00:42:22,500 como pode eventualmente chegar. 790 00:42:22,500 --> 00:42:24,340 E aquí está como ben eles realizados. 791 00:42:24,340 --> 00:42:29,220 >> Teñen un algoritmo que se sentou e viu só as entradas de pantalla. 792 00:42:29,220 --> 00:42:34,080 Ten ningunha instrución que sexa sobre as regras do xogo. 793 00:42:34,080 --> 00:42:42,610 E era para descubrir, baseou a súa puntuación, o quão ben el estaba facendo. 794 00:42:42,610 --> 00:42:46,560 Este foi un sistema que utiliza algo chamado de aprendizaxe por reforzo. 795 00:42:46,560 --> 00:42:48,380 É dicir, el ollou para a súa puntuación. 796 00:42:48,380 --> 00:42:51,620 E se obtivo unha boa puntuación, el dixo: Eu debería me lembrar desas cousas. 797 00:42:51,620 --> 00:42:53,310 E eu debería facer os outra vez. 798 00:42:53,310 --> 00:42:56,450 E se obtivo unha nota malo, el dixo: Non debería facer isto de novo. 799 00:42:56,450 --> 00:42:59,750 800 00:42:59,750 --> 00:43:03,430 >> Este é o rendemento destes sistemas formados 801 00:43:03,430 --> 00:43:07,490 autorizado a xogar por un unhas horas en cada partido, 802 00:43:07,490 --> 00:43:12,490 comparados con xogadores profesionais. 803 00:43:12,490 --> 00:43:19,670 Polo tanto, para todos os xogos que están cara á esquerda desta liña, 804 00:43:19,670 --> 00:43:25,920 Este programa de ordenador auto-adestrados superaron os xogadores profesionais. 805 00:43:25,920 --> 00:43:29,690 E para que todo o dereito, os xogadores profesionais 806 00:43:29,690 --> 00:43:30,920 aínda foron os mellores. 807 00:43:30,920 --> 00:43:34,040 808 00:43:34,040 --> 00:43:36,850 Para algo que sabía nada sobre as normas, que 809 00:43:36,850 --> 00:43:43,020 non sabía nada sobre a estrutura do xogos, este é un desempeño impresionante. 810 00:43:43,020 --> 00:43:45,660 E iso é o que nós somos capaces de facer hoxe. 811 00:43:45,660 --> 00:43:50,239 >> OK, di, pero se nós pensar AI en xogos, 812 00:43:50,239 --> 00:43:52,530 normalmente pensamos sobre a cousas que podemos realmente 813 00:43:52,530 --> 00:43:54,180 sentir e xogar contra. 814 00:43:54,180 --> 00:43:58,760 Se eu me sento e toco StarCraft, ou eu xogo gratuíto Sieve, 815 00:43:58,760 --> 00:44:01,870 o adversario é o equipo persoa que controla o Zerg, 816 00:44:01,870 --> 00:44:06,770 ou o control do outro civilización. 817 00:44:06,770 --> 00:44:11,920 Como eses xogadores realmente atopar os seus movementos? 818 00:44:11,920 --> 00:44:18,810 >> Ben, estes xogos son estruturados do mesmo xeito que os nosos xogos de mesa, 819 00:44:18,810 --> 00:44:22,250 estes xogos que imos chamar colectivamente catro xogos X, 820 00:44:22,250 --> 00:44:26,040 explorar, expand-- esquecer os queridos. 821 00:44:26,040 --> 00:44:26,980 Que son? 822 00:44:26,980 --> 00:44:32,150 Explorar, expandir e extinguir, Creo que é a última. 823 00:44:32,150 --> 00:44:36,060 Pero son basicamente xogos de explotación e conquistar. 824 00:44:36,060 --> 00:44:41,020 Normalmente, o adversario do ordenador non ten información limitadas. 825 00:44:41,020 --> 00:44:45,486 Eles non saben o que está pasando por tras desa néboa da guerra. 826 00:44:45,486 --> 00:44:47,735 Eles non poden ver o que ten no seu inventario. 827 00:44:47,735 --> 00:44:50,240 828 00:44:50,240 --> 00:44:52,800 >> Hai un ambiente que é dinámico. 829 00:44:52,800 --> 00:44:56,180 Todo está cambiando o tempo. 830 00:44:56,180 --> 00:45:00,290 Non pode sentir-se e esperar a tomar a súa xogada. 831 00:45:00,290 --> 00:45:02,810 Pero a maioría das cousas que aínda son discretos. 832 00:45:02,810 --> 00:45:04,200 Teño que poñer a miña cidade aquí. 833 00:45:04,200 --> 00:45:06,750 Ou eu teño que poñer a miña cidade aquí. 834 00:45:06,750 --> 00:45:08,950 E todo é determinista. 835 00:45:08,950 --> 00:45:14,660 Cando digo, mover miña unidade aquí, miña unidade move-se aquí, a non ser un obstáculo de súpeto 836 00:45:14,660 --> 00:45:17,700 entra en xogo. 837 00:45:17,700 --> 00:45:21,610 Agora, iso non é todo ordenador xogos que están por aí hoxe. 838 00:45:21,610 --> 00:45:27,320 >> Se eu ir e eu xogo un primeiro tipo persoa xogo, algo así como ladrón ou Fallout 839 00:45:27,320 --> 00:45:33,350 ou Skyrim, ou o Halo, agora Teño adversarios controlados por ordenador 840 00:45:33,350 --> 00:45:37,860 que están aí fóra, que teñen unha situación moi diferente. 841 00:45:37,860 --> 00:45:40,020 Teñen, de novo, información limitadas. 842 00:45:40,020 --> 00:45:43,420 Eles só poden ver un seguro campo de visión. 843 00:45:43,420 --> 00:45:45,180 O ambiente é aínda dinámico. 844 00:45:45,180 --> 00:45:48,280 As cousas están cambiando o tempo. 845 00:45:48,280 --> 00:45:52,300 >> Pero agora eu teño un moito máis espazo de acción continua. 846 00:45:52,300 --> 00:45:57,170 Podo ser só amosar unha pouco fóra da porta. 847 00:45:57,170 --> 00:46:00,650 E algúns xogos, a miña accións son estocástica. 848 00:46:00,650 --> 00:46:04,590 Comezar a tentar ir sobre esa parede, pero eu teño a oportunidade de fracasar. 849 00:46:04,590 --> 00:46:08,280 850 00:46:08,280 --> 00:46:14,550 Estes tipos de xogos están achegando e máis próximas aos tipos de controladores 851 00:46:14,550 --> 00:46:17,330 que nós construímos en robótica. 852 00:46:17,330 --> 00:46:21,050 >> En robótica, temos que asumir que temos información limitada. 853 00:46:21,050 --> 00:46:23,070 Temos que sensores conte-nos sobre o mundo. 854 00:46:23,070 --> 00:46:25,860 Temos un sempre mudando, ambiente dinámico. 855 00:46:25,860 --> 00:46:30,440 Temos un mundo no que o espazo é continua, no canto de discreta. 856 00:46:30,440 --> 00:46:36,260 E nós, cando intentamos eles, ten unha oportunidade de fracasar. 857 00:46:36,260 --> 00:46:40,960 E, de feito, xogo moderno controladores para o seu adversario de Halo, 858 00:46:40,960 --> 00:46:48,690 ou para os NPCs en Skyrim basicamente realizar pequenas arquitecturas robóticas. 859 00:46:48,690 --> 00:46:50,380 >> Eles senten o mundo. 860 00:46:50,380 --> 00:46:52,910 Eles construír un modelo do mundo. 861 00:46:52,910 --> 00:46:57,950 Eles computam en base a un conxunto de obxectivos que quere realizar. 862 00:46:57,950 --> 00:47:03,110 Planean accións baseadas sobre o que saben. 863 00:47:03,110 --> 00:47:07,940 E eses son exactamente os mesmos tipos dos sistemas que construímos en robótica. 864 00:47:07,940 --> 00:47:11,420 Así, estas arquitecturas, para traer iso de volta xuntos, 865 00:47:11,420 --> 00:47:14,500 son moitas veces moi o mesmo. 866 00:47:14,500 --> 00:47:16,340 >> Entón, imos ver se podemos ver iso. 867 00:47:16,340 --> 00:47:19,210 Imos volver ao noso exemplo tic-tac-toe. 868 00:47:19,210 --> 00:47:22,690 E eu vou pedir un par de meu post-docs para vir e me axudar. 869 00:47:22,690 --> 00:47:26,970 Entón, Chen Ming, e Alessandro, e Olivier, se vostedes virían para arriba. 870 00:47:26,970 --> 00:47:32,080 871 00:47:32,080 --> 00:47:35,440 E eu vou ter un par de voluntarios 872 00:47:35,440 --> 00:47:37,590 >> OK, eu vin un dereito man alí no medio. 873 00:47:37,590 --> 00:47:39,965 Deixe-me dar un máis, alguén aínda máis na parte de atrás, quizais. 874 00:47:39,965 --> 00:47:40,881 Todo ben, alí. 875 00:47:40,881 --> 00:47:41,490 Imos cara arriba. 876 00:47:41,490 --> 00:47:44,190 877 00:47:44,190 --> 00:47:45,335 Todo ben. 878 00:47:45,335 --> 00:47:49,490 Polo tanto, imos ter que cubrir para abaixo. 879 00:47:49,490 --> 00:48:03,700 E se vostedes virían dereita de volta por aquí para min, fantástico. 880 00:48:03,700 --> 00:48:06,580 >> Polo tanto, este é un robot chamado Baxter. 881 00:48:06,580 --> 00:48:10,880 E Baxter é un robot que é unha plataforma comercial, deseñado 882 00:48:10,880 --> 00:48:13,030 por unha empresa chamada Rethink. 883 00:48:13,030 --> 00:48:16,580 E este robot está concibida para a fabricación en pequena escala. 884 00:48:16,580 --> 00:48:19,265 Pero hoxe imos usalo para xogar tic-tac-toe. 885 00:48:19,265 --> 00:48:21,930 886 00:48:21,930 --> 00:48:27,150 Agora, este robot tamén é algo que é relativamente única. 887 00:48:27,150 --> 00:48:32,950 Porque se eu estivese en pé en calquera lugar preto dunha fábrica automatización estándar 888 00:48:32,950 --> 00:48:39,580 sistema, eu estaría en moi grave perigo de ser ferido. 889 00:48:39,580 --> 00:48:45,600 >> Baxter, con todo, foi concibida para ser relativamente seguro para interactuar con. 890 00:48:45,600 --> 00:48:48,680 E para que eu poida empurrar este robot. 891 00:48:48,680 --> 00:48:52,350 E podes ver que é un pouco pouco flexible que se move arredor. 892 00:48:52,350 --> 00:48:57,250 E podo reposicioná la onde me gustaría que vaia. 893 00:48:57,250 --> 00:49:03,410 Agora nun sistema robótico normal, teriamos un conxunto de articulacións aquí 894 00:49:03,410 --> 00:49:07,970 que sería directamente respondendo aos mandos de posición. 895 00:49:07,970 --> 00:49:13,180 E non necesariamente se preocupan se estaban movendo a través de aire libre, 896 00:49:13,180 --> 00:49:15,555 ou no caso de que estaban movendo a través da miña caixa torácica. 897 00:49:15,555 --> 00:49:18,410 898 00:49:18,410 --> 00:49:19,120 >> Aceptar. 899 00:49:19,120 --> 00:49:22,090 E normalmente, se fose aquí cun sistema industrial, 900 00:49:22,090 --> 00:49:23,400 ía a ningunha parte preto del. 901 00:49:23,400 --> 00:49:26,280 Habería amarelo cinta de seguridade ao redor del. 902 00:49:26,280 --> 00:49:28,310 Este sistema ten un deseño lixeiramente diferente 903 00:49:28,310 --> 00:49:32,130 para ser máis agradable e máis fácil para a xente a interactuar con, 904 00:49:32,130 --> 00:49:36,380 en que en cada unha das xuntas, hai unha primavera. 905 00:49:36,380 --> 00:49:39,110 E, no canto de controlar unha posición exacta, 906 00:49:39,110 --> 00:49:43,110 que controla unha certa cantidade de de par, unha certa cantidade de forza, 907 00:49:43,110 --> 00:49:45,874 que queremos estar nesa primavera. 908 00:49:45,874 --> 00:49:47,790 Todo ben, entón déixenme levar os nosos voluntarios aquí. 909 00:49:47,790 --> 00:49:48,540 Ola, cal é o seu nome? 910 00:49:48,540 --> 00:49:49,010 >> Audiencia: Louis. 911 00:49:49,010 --> 00:49:49,635 >> COLUMNA: Louis. 912 00:49:49,635 --> 00:49:50,490 Encantado de verte. 913 00:49:50,490 --> 00:49:50,990 E? 914 00:49:50,990 --> 00:49:51,610 >> Audiencia: David. 915 00:49:51,610 --> 00:49:51,960 >> COLUMNA: David. 916 00:49:51,960 --> 00:49:52,550 Encantado de coñecerte. 917 00:49:52,550 --> 00:49:54,508 Se vós esperarían aquí por un segundo, 918 00:49:54,508 --> 00:49:56,420 Vou darlle a oportunidade de facelo. 919 00:49:56,420 --> 00:50:00,610 Polo tanto, este robot, se vir cara arriba e se empurrar delicada sobre el, 920 00:50:00,610 --> 00:50:03,780 vai ver que se move un pouco. 921 00:50:03,780 --> 00:50:06,349 E se agarralo lo dereito aquí no pulso só 922 00:50:06,349 --> 00:50:09,390 sobre onde os botóns son, el Parece que ten que coller os botóns, 923 00:50:09,390 --> 00:50:13,100 pero cara á dereita por riba no seu lugar, vai poder manipular a ser moi suavemente 924 00:50:13,100 --> 00:50:14,545 a través do espazo. 925 00:50:14,545 --> 00:50:15,920 Louis, quere darlle un intento? 926 00:50:15,920 --> 00:50:19,465 Entón, darlle un pouco empurrar para comezar. 927 00:50:19,465 --> 00:50:23,190 E entón se pór os dedos alí e coller a el, 928 00:50:23,190 --> 00:50:24,807 porque vai pasar para ti, entón. 929 00:50:24,807 --> 00:50:27,824 930 00:50:27,824 --> 00:50:29,365 Todo ben, quere darlle un intento? 931 00:50:29,365 --> 00:50:29,980 Imos cara arriba. 932 00:50:29,980 --> 00:50:32,300 Entón, darlle só unha lixeira empurrar alí para comezar. 933 00:50:32,300 --> 00:50:33,820 Pode sentir o que é como. 934 00:50:33,820 --> 00:50:40,060 E entón se agarralo lo alí mesmo, vai ser capaz de manobrar en torno. 935 00:50:40,060 --> 00:50:41,280 >> Aceptar. 936 00:50:41,280 --> 00:50:47,360 Entón, normalmente, este tipo de un robot faría pode empregar para a fabricación de pequena escala. 937 00:50:47,360 --> 00:50:50,980 E eu vou mover este brazo só abaixo fóra do camiño un pouco aquí. 938 00:50:50,980 --> 00:50:55,750 Pero hoxe, nós estamos indo a usar o mesmo sistema de xogo tic-tac-toe 939 00:50:55,750 --> 00:50:59,520 baseado minimax que construímos antes. 940 00:50:59,520 --> 00:51:00,549 OK? 941 00:51:00,549 --> 00:51:02,340 Entón, vostedes son cada vai xogar un partido. 942 00:51:02,340 --> 00:51:04,210 Louis, está indo a ser o primeiro. 943 00:51:04,210 --> 00:51:05,920 Déixeme só realizarse aquí por un segundo. 944 00:51:05,920 --> 00:51:10,949 Vou ter que estar ben aquí, só para que todos poidan velo. 945 00:51:10,949 --> 00:51:11,990 Vostedes están configurar aquí? 946 00:51:11,990 --> 00:51:13,120 >> ROBOT: Benvido. 947 00:51:13,120 --> 00:51:15,910 Imos xogar tic-tac-toe. 948 00:51:15,910 --> 00:51:20,860 Non suxeite o token antes Digo que é a súa vez. 949 00:51:20,860 --> 00:51:22,050 Eu iniciar o xogo. 950 00:51:22,050 --> 00:51:27,900 951 00:51:27,900 --> 00:51:28,750 É a miña vez. 952 00:51:28,750 --> 00:51:47,002 953 00:51:47,002 --> 00:51:50,210 COLUMNA: Agora, se puidese tomar unha das as súas pezas e ir adiante e poñelas. 954 00:51:50,210 --> 00:51:51,446 ROBOT: É a súa vez. 955 00:51:51,446 --> 00:51:53,430 [Risas] 956 00:51:53,430 --> 00:51:54,836 É a miña vez. 957 00:51:54,836 --> 00:51:56,820 [Risas] 958 00:51:56,820 --> 00:52:12,196 959 00:52:12,196 --> 00:52:15,680 [Risas] 960 00:52:15,680 --> 00:52:16,570 É a súa vez. 961 00:52:16,570 --> 00:52:21,397 962 00:52:21,397 --> 00:52:23,688 Speak: A raza humana é contando con vostede aquí, Louis. 963 00:52:23,688 --> 00:52:27,440 964 00:52:27,440 --> 00:52:28,350 >> ROBOT: É a miña vez. 965 00:52:28,350 --> 00:52:44,810 966 00:52:44,810 --> 00:52:47,015 >> COLUMNA: Entón Baxter bloqueado correctamente aquí. 967 00:52:47,015 --> 00:52:49,670 968 00:52:49,670 --> 00:52:52,480 >> ROBOT: É a súa vez. 969 00:52:52,480 --> 00:52:53,360 É a miña vez. 970 00:52:53,360 --> 00:53:14,730 971 00:53:14,730 --> 00:53:16,810 É a súa vez. 972 00:53:16,810 --> 00:53:17,760 É a miña vez. 973 00:53:17,760 --> 00:53:21,330 974 00:53:21,330 --> 00:53:23,830 Orador: E nós imos deixar Baxter rematar a súa última xogada aquí. 975 00:53:23,830 --> 00:53:36,622 976 00:53:36,622 --> 00:53:39,090 >> [Risas] 977 00:53:39,090 --> 00:53:40,480 >> ROBOT: Isto é un empate. 978 00:53:40,480 --> 00:53:42,030 Eu vou gañar a próxima vez. 979 00:53:42,030 --> 00:53:43,365 >> [Risas] 980 00:53:43,365 --> 00:53:45,210 >> COLUMNA: Todo ben, moitas grazas, Louis. 981 00:53:45,210 --> 00:53:46,094 Grazas. 982 00:53:46,094 --> 00:53:46,980 Pode ir por este camiño. 983 00:53:46,980 --> 00:53:49,759 >> ROBOT: eu iniciar o xogo. 984 00:53:49,759 --> 00:53:51,800 COLUMNA: Entón deixe-me explicar para ti un pouco máis 985 00:53:51,800 --> 00:53:55,410 pouco antes de chegar a nosa revancha aquí. 986 00:53:55,410 --> 00:53:57,200 O que é exactamente está a suceder? 987 00:53:57,200 --> 00:53:59,430 Así, o robot ten unha cámara enriba aquí. 988 00:53:59,430 --> 00:54:01,330 E está mirando para a tarxeta. 989 00:54:01,330 --> 00:54:04,470 E está a ver se ten un O vermello é un azul 990 00:54:04,470 --> 00:54:10,450 e X. branco como aqueles colócanse no tarxeta, que é basicamente a mesma entrada 991 00:54:10,450 --> 00:54:13,890 que estariamos lendo desde nosa estrutura de datos da nosa pantalla. 992 00:54:13,890 --> 00:54:17,290 Está executando o mesmo algoritmo minimax ser 993 00:54:17,290 --> 00:54:21,010 capaz de atopar onde poñer un bo sinal. 994 00:54:21,010 --> 00:54:24,820 >> E entón nós estamos dando un comando sobre onde nós quere un token para ser instalado. 995 00:54:24,820 --> 00:54:26,120 O brazo está movendo para fóra. 996 00:54:26,120 --> 00:54:31,750 É a usar un dispositivo de comprensión de baleiro para aplicar algunha succión para que a peza de madeira, 997 00:54:31,750 --> 00:54:35,240 pegalo, mover para a dereita local, e a continuación, solte a succión 998 00:54:35,240 --> 00:54:36,950 e déixea. 999 00:54:36,950 --> 00:54:38,990 Todo ben, imos para darlle un tiro 1000 00:54:38,990 --> 00:54:40,930 con un xogador algo máis intelixente aquí. 1001 00:54:40,930 --> 00:54:42,290 Está preparado? 1002 00:54:42,290 --> 00:54:46,150 Todo ben, se queda ata aquí e dar um-- resultando nese camiño 1003 00:54:46,150 --> 00:54:47,955 para que poida ver todo o mundo. 1004 00:54:47,955 --> 00:54:48,830 E entón [inaudível]. 1005 00:54:48,830 --> 00:54:49,330 >> ROBOT: É a miña vez. 1006 00:54:49,330 --> 00:54:50,455 >> COLUMNA: Baxter vai comezar. 1007 00:54:50,455 --> 00:55:10,750 1008 00:55:10,750 --> 00:55:11,730 É a súa vez. 1009 00:55:11,730 --> 00:55:16,490 1010 00:55:16,490 --> 00:55:17,520 É a miña vez. 1011 00:55:17,520 --> 00:55:38,740 1012 00:55:38,740 --> 00:55:39,690 É a súa vez. 1013 00:55:39,690 --> 00:55:46,330 1014 00:55:46,330 --> 00:55:47,165 É a miña vez. 1015 00:55:47,165 --> 00:56:01,252 1016 00:56:01,252 --> 00:56:06,192 >> [Risas] 1017 00:56:06,192 --> 00:56:08,542 >> COLUMNA: [murmurada] Só deixar ir adiante e gañar. 1018 00:56:08,542 --> 00:56:09,500 ROBOT: É a súa vez. 1019 00:56:09,500 --> 00:56:15,099 1020 00:56:15,099 --> 00:56:15,890 COLUMNA: Isto é OK. 1021 00:56:15,890 --> 00:56:20,390 1022 00:56:20,390 --> 00:56:21,360 >> ROBOT: É a miña vez. 1023 00:56:21,360 --> 00:56:24,825 1024 00:56:24,825 --> 00:56:26,805 >> [Risas] 1025 00:56:26,805 --> 00:56:42,650 1026 00:56:42,650 --> 00:56:43,510 >> Eu gañar. 1027 00:56:43,510 --> 00:56:45,620 >> [Risas] 1028 00:56:45,620 --> 00:56:46,595 >> Eu iniciar o xogo. 1029 00:56:46,595 --> 00:56:48,261 >> COLUMNA: Todo ben, moitas grazas. 1030 00:56:48,261 --> 00:56:50,180 1031 00:56:50,180 --> 00:56:55,590 Todo ben, eu creo que temos tempo para máis un excelente xogador de tic-tac-toe, 1032 00:56:55,590 --> 00:57:00,490 alguén que pode poñer esa cousa de corresponden, que sabe o que está facendo. 1033 00:57:00,490 --> 00:57:03,010 >> [Risas] 1034 00:57:03,010 --> 00:57:05,560 >> Quen será o noso campión aquí? 1035 00:57:05,560 --> 00:57:08,110 Todo ben, os seus amigos ofrecéronlle. 1036 00:57:08,110 --> 00:57:11,190 Iso é bo o suficiente para min. 1037 00:57:11,190 --> 00:57:12,194 Dime o seu nome de novo. 1038 00:57:12,194 --> 00:57:12,860 Audiencia: Tamir. 1039 00:57:12,860 --> 00:57:14,193 COLUMNA: Tamir, bo velo. 1040 00:57:14,193 --> 00:57:19,270 Todo ben, unha vez máis, imos poñelas ata aquí para que todos poidan velo. 1041 00:57:19,270 --> 00:57:22,070 Vostede é o noso representante neste xogo agora. 1042 00:57:22,070 --> 00:57:24,540 Baxter é un e Oh e Oh. 1043 00:57:24,540 --> 00:57:26,300 Ou Sentímolo, unha oh e un. 1044 00:57:26,300 --> 00:57:27,490 E cómpre a vostede aquí. 1045 00:57:27,490 --> 00:57:29,340 Baxter comezará a mover-se en primeiro lugar, con todo. 1046 00:57:29,340 --> 00:57:30,435 So. 1047 00:57:30,435 --> 00:57:31,310 ROBOT: É a miña vez. 1048 00:57:31,310 --> 00:57:45,226 1049 00:57:45,226 --> 00:57:48,208 >> [Risas] 1050 00:57:48,208 --> 00:57:52,720 1051 00:57:52,720 --> 00:57:55,780 >> É a súa vez. 1052 00:57:55,780 --> 00:57:56,845 É a miña vez. 1053 00:57:56,845 --> 00:58:18,130 1054 00:58:18,130 --> 00:58:18,965 É a súa vez. 1055 00:58:18,965 --> 00:58:28,751 1056 00:58:28,751 --> 00:58:30,248 É a miña vez. 1057 00:58:30,248 --> 00:58:51,210 1058 00:58:51,210 --> 00:58:52,160 É a súa vez. 1059 00:58:52,160 --> 00:59:00,854 1060 00:59:00,854 --> 00:59:03,365 >> [Risas] 1061 00:59:03,365 --> 00:59:04,240 ROBOT: É a miña vez. 1062 00:59:04,240 --> 00:59:06,930 COLUMNA: É moito máis difícil cando está de pé aquí, xente. 1063 00:59:06,930 --> 00:59:19,400 1064 00:59:19,400 --> 00:59:21,840 [Risas] 1065 00:59:21,840 --> 00:59:26,730 1066 00:59:26,730 --> 00:59:29,054 ROBOT: Vostedes humanos son tan fáciles de bater. 1067 00:59:29,054 --> 00:59:30,803 [Risas e aplausos] 1068 00:59:30,803 --> 00:59:31,886 COLUMNA: Moitas grazas. 1069 00:59:31,886 --> 00:59:34,692 ROBOT: eu gañar. 1070 00:59:34,692 --> 00:59:35,400 Eu iniciar o xogo. 1071 00:59:35,400 --> 00:59:39,500 >> Palestrante: Todo ben, entón moitas grazas moi a Olivier, e Alessandro, 1072 00:59:39,500 --> 00:59:41,616 e Chen Ming. 1073 00:59:41,616 --> 00:59:45,600 >> [Aplausos] 1074 00:59:45,600 --> 00:59:47,040 >> Quero facer un último punto. 1075 00:59:47,040 --> 00:59:51,630 Así Baxter no propio remata aí, enganado. 1076 00:59:51,630 --> 00:59:54,160 1077 00:59:54,160 --> 00:59:56,310 E iso era inesperado. 1078 00:59:56,310 --> 01:00:00,440 Un dos fantástica cousas sobre AI é que 1079 01:00:00,440 --> 01:00:05,070 facer o traballo en AI para que poidamos construír realmente interesante e intelixente 1080 01:00:05,070 --> 01:00:06,930 dispositivos. 1081 01:00:06,930 --> 01:00:10,130 Pero nós tamén facemos traballo en AI porque nos di algo 1082 01:00:10,130 --> 01:00:13,940 sobre como os humanos son intelixentes. 1083 01:00:13,940 --> 01:00:17,280 >> Un dos favoritos estudos de meu laboratorio é 1084 01:00:17,280 --> 01:00:23,660 mirando para o que ocorre cando máquinas de vez trampas. 1085 01:00:23,660 --> 01:00:27,070 Fixemos iso orixinalmente non con Baxter xogar tic-tac-dedo do pé, 1086 01:00:27,070 --> 01:00:30,340 pero cun robot menor chamado Non, que xogou pedra-papel-tesouro. 1087 01:00:30,340 --> 01:00:33,010 1088 01:00:33,010 --> 01:00:35,800 E, ás veces despois xogando lotes e lotes 1089 01:00:35,800 --> 01:00:41,580 de perforación de xogos de pedra-papel-tesouro, o robot xogaría un xesto, 1090 01:00:41,580 --> 01:00:48,616 perder, e, a continuación, cambiar de súpeto seu xesto e dicir, eu gañou. 1091 01:00:48,616 --> 01:00:50,480 >> [Risas] 1092 01:00:50,480 --> 01:00:56,090 >> Agora, ás veces tamén teriamos o robot, así como un control, xogue un xesto, 1093 01:00:56,090 --> 01:01:01,270 gañar, e cambiar o seu xesto que perder, xogar o partido, 1094 01:01:01,270 --> 01:01:04,070 enganar a fin de perder. 1095 01:01:04,070 --> 01:01:07,540 E iso non é tan atractivo. 1096 01:01:07,540 --> 01:01:09,890 O robot que engana a fin de gañar persoas 1097 01:01:09,890 --> 01:01:14,660 para responder como se fose para obtelos, como 1098 01:01:14,660 --> 01:01:17,690 está esforzarse para a súa destrución. 1099 01:01:17,690 --> 01:01:19,210 >> [Risas] 1100 01:01:19,210 --> 01:01:20,990 >> Pasa a ser un axente. 1101 01:01:20,990 --> 01:01:21,840 É como se fose unha persoa. 1102 01:01:21,840 --> 01:01:23,970 Ten crenza e intención. 1103 01:01:23,970 --> 01:01:27,470 E non é boa intención. 1104 01:01:27,470 --> 01:01:33,790 E o robot que xoga o xogo é só mal funcionamento. 1105 01:01:33,790 --> 01:01:36,990 É só un dispositivo roto. 1106 01:01:36,990 --> 01:01:41,405 Deixe-me amosar-lle un par de exemplos de que a partir de algúns dos nosos participantes. 1107 01:01:41,405 --> 01:01:43,990 1108 01:01:43,990 --> 01:01:45,600 Entón aquí está traizoando a fin de perder. 1109 01:01:45,600 --> 01:01:46,266 >> [REPRODUCIÓN DE VIDEO] 1110 01:01:46,266 --> 01:01:47,010 - [Inaudível] gañar. 1111 01:01:47,010 --> 01:01:49,550 Xoguemos. 1112 01:01:49,550 --> 01:01:50,538 >> Espere, o que? 1113 01:01:50,538 --> 01:01:54,490 1114 01:01:54,490 --> 01:01:55,352 >> - [Inaudível] gañar. 1115 01:01:55,352 --> 01:01:58,280 Xoguemos. 1116 01:01:58,280 --> 01:01:59,400 >> [Inaudível] gañar. 1117 01:01:59,400 --> 01:02:02,290 Xoguemos. 1118 01:02:02,290 --> 01:02:05,490 >> Orador: E aquí é trampa para gañar. 1119 01:02:05,490 --> 01:02:06,438 >> Si, eu gañou. 1120 01:02:06,438 --> 01:02:07,394 Xoguemos. 1121 01:02:07,394 --> 01:02:08,828 >> -Vostede Non pode facelo. 1122 01:02:08,828 --> 01:02:10,740 >> [Risas] 1123 01:02:10,740 --> 01:02:12,174 1124 01:02:12,174 --> 01:02:13,979 >> Si, eu gañou. 1125 01:02:13,979 --> 01:02:14,520 -Vostede Traizoou. 1126 01:02:14,520 --> 01:02:17,990 1127 01:02:17,990 --> 01:02:20,010 Vostede traizoou agora. 1128 01:02:20,010 --> 01:02:21,140 >> Si, eu gañou. 1129 01:02:21,140 --> 01:02:22,940 >> Ei, trampóns. 1130 01:02:22,940 --> 01:02:26,670 Vostede enganar, super fraude. 1131 01:02:26,670 --> 01:02:27,650 >> [FIN DE REPRODUCIÓN] 1132 01:02:27,650 --> 01:02:31,130 >> COLUMNA: Estes diferente reaccións rapidamente 1133 01:02:31,130 --> 01:02:34,890 cambiar a nosa percepción do dispositivo. 1134 01:02:34,890 --> 01:02:36,780 Isto significa que nós deliberadamente construír 1135 01:02:36,780 --> 01:02:40,370 máquinas que se enganan porque iso a mellor enxeñaría que podemos facer? 1136 01:02:40,370 --> 01:02:44,680 Non, pero dinos algo realmente interesante sobre as persoas. 1137 01:02:44,680 --> 01:02:49,710 Aquela cousa que engana e rouba a súa vitoria, que é 1138 01:02:49,710 --> 01:02:53,660 algo que está vivo, que é animar, que está fóra para comeza-lo. 1139 01:02:53,660 --> 01:02:54,680 Ten estado mental. 1140 01:02:54,680 --> 01:02:55,400 Ten crenza. 1141 01:02:55,400 --> 01:02:57,170 Ten a intención. 1142 01:02:57,170 --> 01:03:01,540 >> Aquela que as mans xogo para ti, que non é. 1143 01:03:01,540 --> 01:03:04,670 Isto é só mal funcionamento. 1144 01:03:04,670 --> 01:03:08,900 Isto é, en moitos aspectos, porque é fácil de xogar o xogo cos nenos. 1145 01:03:08,900 --> 01:03:12,050 Pero se tentar erro-los e tipo de reivindicar a vitoria 1146 01:03:12,050 --> 01:03:15,200 cando, xa sabe, só para acurtar o xogo, eles van pegá-lo inmediatamente. 1147 01:03:15,200 --> 01:03:19,040 1148 01:03:19,040 --> 01:03:23,140 Estes tipos de efectos que vemos que sae da AI, 1149 01:03:23,140 --> 01:03:26,490 eles nos ensinan moito sobre nós mesmos. 1150 01:03:26,490 --> 01:03:28,076 >> Todo ben, iso é por hoxe. 1151 01:03:28,076 --> 01:03:30,450 Moitas grazas a David e o equipo de produción Harvard 1152 01:03:30,450 --> 01:03:32,350 para baixar. 1153 01:03:32,350 --> 01:03:33,820 >> [Aplausos] 1154 01:03:33,820 --> 01:03:36,760 1155 01:03:36,760 --> 01:03:41,840 >> Imos velo nun cuestionario, e, a continuación, para unha última charla. 1156 01:03:41,840 --> 01:03:43,025 Que teñas un día fantástico. 1157 01:03:43,025 --> 01:03:44,965 >> [Aplausos] 1158 01:03:44,965 --> 01:03:48,360 1159 01:03:48,360 --> 01:03:51,825 >> [Música tocando] 1160 01:03:51,825 --> 01:03:54,950 DAVID Malan J: Ben, nós probablemente precisa para introducir algún tipo de cifrado, 1161 01:03:54,950 --> 01:03:55,450 non? 1162 01:03:55,450 --> 01:03:58,650 Porque, entón, as cabeceiras de esas peticións HTTP será 1163 01:03:58,650 --> 01:04:01,530 revoltos para que calquera persoa intentando capturar tráfico 1164 01:04:01,530 --> 01:04:03,400 non vai realmente ser capaz de velos. 1165 01:04:03,400 --> 01:04:05,254 Entón, cal é a solución a este problema? 1166 01:04:05,254 --> 01:04:07,920 Ben, necesitamos realmente introducir cifrado na fórmula, 1167 01:04:07,920 --> 01:04:11,010 de xeito que cando esa persoa a transmisión de datos a partir de A para B, 1168 01:04:11,010 --> 01:04:12,390 podemos seguramente send-- 1169 01:04:12,390 --> 01:04:14,590 >> [Risas] 1170 01:04:14,590 --> 01:04:19,530 >> A información dun xeito que o adversario non pode, de feito, velo.