1 00:00:00,000 --> 00:00:01,924 >> [Musiikkia] 2 00:00:01,924 --> 00:00:10,600 3 00:00:10,600 --> 00:00:13,280 >> SPEAKER: Tervetuloa takaisin, kaikille. 4 00:00:13,280 --> 00:00:15,440 Tämä on CS50. 5 00:00:15,440 --> 00:00:21,040 Ja tänään, meillä on paljon mielenkiintoisia asioita puhua. 6 00:00:21,040 --> 00:00:25,500 Ensinnäkin, vaikka, minun on muistutettava sinulle muutamia hallinnollisen asioita. 7 00:00:25,500 --> 00:00:30,160 Tällä viikolla on tietokilpailu yksi keskiviikkona tai Yale jakso 8 00:00:30,160 --> 00:00:32,940 tiistaisin ja torstaisin, torstaina. 9 00:00:32,940 --> 00:00:38,170 On tietokilpailu arvosteluja tänään Yalen, 5:30-07:00. 10 00:00:38,170 --> 00:00:40,030 Harvardin, he nauhoittivat yksi eilen. 11 00:00:40,030 --> 00:00:43,000 Ja jokainen voi katsella että verkossa. 12 00:00:43,000 --> 00:00:49,406 >> Myös tällä viikolla tai ensi viikon alussa, meillä on viime CS50 luento. 13 00:00:49,406 --> 00:00:51,450 [Huokaukset] Tiedän. 14 00:00:51,450 --> 00:00:54,140 Se tuli näin pian. 15 00:00:54,140 --> 00:00:57,820 Yalen opiskelijat on live luento tässä laissa koulussa 16 00:00:57,820 --> 00:00:59,920 auditorio perjantaina. 17 00:00:59,920 --> 00:01:01,140 Tulee kakku. 18 00:01:01,140 --> 00:01:05,570 Harvardin opiskelijalla on viimeinen luento Sanders maanantaina. 19 00:01:05,570 --> 00:01:08,050 Mukana on myös kakku. 20 00:01:08,050 --> 00:01:14,000 >> Myös tällä viikolla perjantaina, niille teistä, jotka tulevat New Haven, 21 00:01:14,000 --> 00:01:15,740 meillä CS50 Expo. 22 00:01:15,740 --> 00:01:18,850 Meillä on yli 30 eri rekisteröity 23 00:01:18,850 --> 00:01:22,530 näyttämään kaiken riippumattomiin purjeveneet, 24 00:01:22,530 --> 00:01:27,170 järjestelmiin, jotka tunnistavat digitaalinen muotokuvia, tietokoneeseen 25 00:01:27,170 --> 00:01:32,100 musiikki ja tietokone tuotettua musiikkia. 26 00:01:32,100 --> 00:01:33,610 Joten voit liittyä meihin. 27 00:01:33,610 --> 00:01:36,460 Minusta se tulee olemaan hauskaa. 28 00:01:36,460 --> 00:01:40,320 >> Tänään kuitenkin saamme jatkaa puhumme AI, 29 00:01:40,320 --> 00:01:43,150 noin tekoäly. 30 00:01:43,150 --> 00:01:46,070 Ja yksi niistä asioista, jotka aiomme päästä tänään 31 00:01:46,070 --> 00:01:51,750 on ajatus siitä, miten käyttää AI ratkaista ongelmia. 32 00:01:51,750 --> 00:01:54,690 Nyt, kuten aina, aloitetaan jotain yksinkertaista. 33 00:01:54,690 --> 00:01:57,120 Ja aiomme aloittaa yksinkertainen idea. 34 00:01:57,120 --> 00:01:59,920 Ja se on käyttämällä hakua. 35 00:01:59,920 --> 00:02:06,990 >> Joten kuvitella hetken, että olen on tehtävä, että minun täytyy tehdä. 36 00:02:06,990 --> 00:02:11,970 Ja haluaisin olla, että tehtävä automatisoida joitakin ohjelmia agentti. 37 00:02:11,970 --> 00:02:17,100 Kuvittele, että olen yrittänyt varata joukko Lentojen, sanokaamme, Boston 38 00:02:17,100 --> 00:02:20,040 San Francisco. 39 00:02:20,040 --> 00:02:24,230 Voisin mennä läpi ja voisin käyttää yksi ihana online-haku 40 00:02:24,230 --> 00:02:28,790 työkalut, joka tulee tekemään pohjimmiltaan sama prosessi, että olemme 41 00:02:28,790 --> 00:02:30,030 aikoo kävellä läpi tänään. 42 00:02:30,030 --> 00:02:34,100 Mutta jos sinulla ei ole, että työkalu, mitä tekisit? 43 00:02:34,100 --> 00:02:37,570 >> No, voisit katsoa ja nähdä ja sanoa, olen Bostonissa. 44 00:02:37,570 --> 00:02:41,520 Mitä lennot ovat käytettävissä? 45 00:02:41,520 --> 00:02:44,390 Nyt, ehkä minulla on kolme mahdollinen lennot ulos Boston 46 00:02:44,390 --> 00:02:47,180 joka sopii aika kun minun täytyy lähteä. 47 00:02:47,180 --> 00:02:48,830 Voisin lentää Chicagoon. 48 00:02:48,830 --> 00:02:50,130 Tai voisin lentää Miamiin. 49 00:02:50,130 --> 00:02:53,340 Tai voisin lentää New Yorkiin. 50 00:02:53,340 --> 00:02:56,980 Voisin sitten katsoa jokaisesta yksi niistä kohdekaupunkien 51 00:02:56,980 --> 00:03:00,650 ja miettiä, mitä paikkoja Voisin ehkä päästä 52 00:03:00,650 --> 00:03:03,020 kunkin näistä yksittäisten kaupunkien. 53 00:03:03,020 --> 00:03:07,390 >> Joten ehkä Chicagosta, saan suora lento San Francisco. 54 00:03:07,390 --> 00:03:09,550 Se on erinomainen. 55 00:03:09,550 --> 00:03:12,360 Tai saisin lento Denver. 56 00:03:12,360 --> 00:03:16,970 Nyt, ehkä se lento San Francisco on täydellinen ratkaisu minulle, 57 00:03:16,970 --> 00:03:19,530 mutta ehkä ei. 58 00:03:19,530 --> 00:03:22,180 Ehkä Etsin jotain että on hieman halvempi 59 00:03:22,180 --> 00:03:24,920 tai hieman paremmin minun aikatauluni. 60 00:03:24,920 --> 00:03:29,197 Ja niin voisin katsoa mitä muut mahdollisuuksista saattaa olla siellä. 61 00:03:29,197 --> 00:03:30,280 Niin voisin katsoa Denver. 62 00:03:30,280 --> 00:03:33,870 Ja Denver, hyvin, ehkä Saan lento Austin. 63 00:03:33,870 --> 00:03:37,080 Ja Austin, ehkä saan lento Phoenix, ja Phoenix 64 00:03:37,080 --> 00:03:40,190 San Francisco. 65 00:03:40,190 --> 00:03:42,730 Nyt, en ole tehnyt vielä. 66 00:03:42,730 --> 00:03:45,640 Koska ehkä siellä suora lento New Yorkista 67 00:03:45,640 --> 00:03:47,850 San Francisco, joka on täydellinen minulle. 68 00:03:47,850 --> 00:03:53,354 Tai ehkä siellä lennon välillä Miami kautta Denver se on paljon halvempaa. 69 00:03:53,354 --> 00:03:54,270 Joten minulla on vielä mennä. 70 00:03:54,270 --> 00:03:58,200 Ja minulla on vielä tarkasteltava kaikkia näitä kaupungit että en ole tutkittu vielä. 71 00:03:58,200 --> 00:04:04,220 Minun on tyhjentävästi tarkistaa kaikki mahdollisuuksia että saisin. 72 00:04:04,220 --> 00:04:09,610 >> Joten New York, ehkä saan lento Nashville, ja Nashville 73 00:04:09,610 --> 00:04:10,336 Austin. 74 00:04:10,336 --> 00:04:11,460 Ja sitten tiedän, missä olen. 75 00:04:11,460 --> 00:04:14,252 Ja sitten tiedän Austin, voin lentää Phoenix, ja Phoenix 76 00:04:14,252 --> 00:04:14,960 San Francisco. 77 00:04:14,960 --> 00:04:18,240 78 00:04:18,240 --> 00:04:22,830 Jos Lennän ensin Miami, vaikka, Ehkä saan lennon välillä Miami 79 00:04:22,830 --> 00:04:25,080 Nashville, tai Miami Austin. 80 00:04:25,080 --> 00:04:27,950 81 00:04:27,950 --> 00:04:30,860 >> Ja nyt olen yrittänyt kaikki mahdollisuuksia. 82 00:04:30,860 --> 00:04:36,310 Olen rakentanut tämän kuvaaja, joka näyttää minulle kaikki mahdolliset reitit 83 00:04:36,310 --> 00:04:37,790 että voisin ottaa. 84 00:04:37,790 --> 00:04:40,510 85 00:04:40,510 --> 00:04:43,640 Kun me edustamme näitä erilaisia ​​ongelmia, 86 00:04:43,640 --> 00:04:47,870 emme aio edustamaan nimenomaisesti mukaan tätä kuvaajaa, 87 00:04:47,870 --> 00:04:51,590 koska kuvaaja ei edusta historian missä olemme menneet. 88 00:04:51,590 --> 00:04:55,260 Tietäen, että lensin Phoenix San Francisco 89 00:04:55,260 --> 00:05:01,690 ei kerro minulle, tulin kautta Nashville, tai kautta Denver, kautta tai Miami. 90 00:05:01,690 --> 00:05:06,430 >> Joten mitä teen sen sijaan on Otan tämän saman ongelman, 91 00:05:06,430 --> 00:05:09,140 ja minä edustaa sitä kuin puu. 92 00:05:09,140 --> 00:05:14,300 Ja juureen puu, on top, laitan paikka, että aloitin, 93 00:05:14,300 --> 00:05:16,590 Boston. 94 00:05:16,590 --> 00:05:19,310 Ja Boston, minä katson kaikki mahdolliset paikat 95 00:05:19,310 --> 00:05:20,380 että voin matkustaa. 96 00:05:20,380 --> 00:05:25,480 No, tässä tapauksessa, minulla oli kolme, Chicago, New Yorkissa, ja Miami. 97 00:05:25,480 --> 00:05:29,850 Ja sitten minä tutkia jokaisen nämä lapset puussa. 98 00:05:29,850 --> 00:05:32,690 >> Chicago, olen nähnyt että minulla oli kaksi lentoa. 99 00:05:32,690 --> 00:05:35,940 Voisin lentää suoraan San Francisco tai Denver. 100 00:05:35,940 --> 00:05:37,740 Nyt San Francisco, se on minun tavoite. 101 00:05:37,740 --> 00:05:39,790 Se on minun määränpää. 102 00:05:39,790 --> 00:05:42,220 Se tulee olemaan lehtiä tämän puun. 103 00:05:42,220 --> 00:05:45,340 Eli en aio koskaan mennä jonnekin jälkeen San Francisco. 104 00:05:45,340 --> 00:05:47,850 105 00:05:47,850 --> 00:05:50,340 Denver, vaikka, Voin lentää Denver 106 00:05:50,340 --> 00:05:54,220 Austin, Austin Phoenix, ja Phoenix San Francisco. 107 00:05:54,220 --> 00:05:56,050 Ja nyt taas, olen saavuttanut lehtiä. 108 00:05:56,050 --> 00:05:59,470 109 00:05:59,470 --> 00:06:03,980 >> Voisin palaa seuraavaan kaupunki, joka en ole täysin tutkittu. 110 00:06:03,980 --> 00:06:07,440 Se olisi New York, mennä takaisin ylös minun puu, 111 00:06:07,440 --> 00:06:09,160 tulla alas New Yorkiin. 112 00:06:09,160 --> 00:06:12,700 New York, voin lentää Nashville, Nashville Austin, 113 00:06:12,700 --> 00:06:17,290 Austin Phoenix, ja Phoenix-San Francisco. 114 00:06:17,290 --> 00:06:20,170 Ja lopuksi, yksi kaupunki I ole katsonut vielä, Miami. 115 00:06:20,170 --> 00:06:24,600 >> No, Miamista sanoin minulla oli kaksi mahdollisuuksia, Nashville tai Austin. 116 00:06:24,600 --> 00:06:28,810 Jos Lennän Nashville, hyvin sitten lennän Nashville, Austin, Phoenix, 117 00:06:28,810 --> 00:06:29,640 San Francisco. 118 00:06:29,640 --> 00:06:33,600 Jos Lennän Austin, lennän Austin, Phoenix, San Francisco. 119 00:06:33,600 --> 00:06:36,340 Ja nyt minulla on puu. 120 00:06:36,340 --> 00:06:37,230 Se on täydellinen puu. 121 00:06:37,230 --> 00:06:41,890 Se on kaikki mahdollisuudet ja kaikki polut että voisin ottaa. 122 00:06:41,890 --> 00:06:44,310 Eli jos minä alkavat puun juuri yläreunassa 123 00:06:44,310 --> 00:06:47,860 ja menen alas yksi lehdet, se kertoo minulle ei vain 124 00:06:47,860 --> 00:06:50,480 minne olen menossa päätyvät, San Francisco, 125 00:06:50,480 --> 00:06:53,670 mutta se kertoo minulle reitti, joka Minun täytyy ottaa sinne. 126 00:06:53,670 --> 00:06:56,400 127 00:06:56,400 --> 00:06:59,690 >> Nyt, mikä näistä on paras? 128 00:06:59,690 --> 00:07:02,430 No, ei mitään tästä ongelma vielä kertoo minulle 129 00:07:02,430 --> 00:07:04,710 mikä näistä on paras ratkaisu. 130 00:07:04,710 --> 00:07:09,270 Ehkä välitän eniten kuinka paljon aikaa olen ilmassa, 131 00:07:09,270 --> 00:07:12,350 tai etäisyys, että lennän. 132 00:07:12,350 --> 00:07:16,410 Siinä tapauksessa, Chicago San Francisco voisi olla lyhin määrä 133 00:07:16,410 --> 00:07:18,910 mailia ilmassa. 134 00:07:18,910 --> 00:07:20,860 >> Ehkä välitän kustannuksia. 135 00:07:20,860 --> 00:07:23,680 Ja me kaikki tiedämme suorat lennot ovat yleensä kalliimpia. 136 00:07:23,680 --> 00:07:26,610 Joten ehkä jos otan tämän eräänlainen taaksepäin reitti 137 00:07:26,610 --> 00:07:30,650 kautta Miami, Nashville, Austin, Phoenix, ehkä sitten 138 00:07:30,650 --> 00:07:34,070 Saan halvemmalla. 139 00:07:34,070 --> 00:07:36,440 Mutta voisin optimoida tahansa kriteerit, jotka välitän. 140 00:07:36,440 --> 00:07:39,790 Kenellä paras lento Wi-Fi, tai jotka 141 00:07:39,790 --> 00:07:43,110 lentoasemilla on parasta ruokaa saatavilla. 142 00:07:43,110 --> 00:07:47,280 Ja jokainen näistä ehkä anna minulle toinen ratkaisu 143 00:07:47,280 --> 00:07:49,215 että näen olevan paras. 144 00:07:49,215 --> 00:07:51,990 145 00:07:51,990 --> 00:07:54,400 >> Tällaisia ​​ongelmia, minne olemme menossa 146 00:07:54,400 --> 00:07:58,480 rakentaa tämä puu mahdollisuuksia, ja sitten 147 00:07:58,480 --> 00:08:02,100 näyttää jokaisen näistä yksittäisiä polkuja, ja tutkia 148 00:08:02,100 --> 00:08:05,270 joka näistä täytä kriteerit meille, 149 00:08:05,270 --> 00:08:08,790 aiomme soittaa nämä haku ongelmia. 150 00:08:08,790 --> 00:08:11,280 Ja meillä on paljon algoritmit, joista osa 151 00:08:11,280 --> 00:08:15,270 olemme nähneet jo, mennä ja tutkia näitä puita. 152 00:08:15,270 --> 00:08:19,270 Voisimme tehdä sen tavalla, jota en vain teki, syvyys-ensimmäinen haku, 153 00:08:19,270 --> 00:08:22,900 menee alas kuin voimme, kunnes me osuma lehtiä, ja sitten tulee takaisin ylös, 154 00:08:22,900 --> 00:08:24,787 ja menee takaisin alas. 155 00:08:24,787 --> 00:08:26,870 Tai voimme tehdä mitä nimeltään leveys-ensin hakua. 156 00:08:26,870 --> 00:08:29,675 Voisimme laajentaa kaiken huipulla, ja sitten 157 00:08:29,675 --> 00:08:31,550 kaikki yksi rivi alla, että ja sitten 158 00:08:31,550 --> 00:08:35,240 kaikki yhden rivin alla että. 159 00:08:35,240 --> 00:08:41,250 Ne hakupuita ovat olennaisia ​​AI. 160 00:08:41,250 --> 00:08:46,570 Mutta ne eivät aivan saada se koko ajan oikeassa. 161 00:08:46,570 --> 00:08:51,600 Itse asiassa paljon tapauksia että me välitä, 162 00:08:51,600 --> 00:08:54,430 haluamme rakentaa puu, mutta emme oikeastaan 163 00:08:54,430 --> 00:08:57,140 saada tehdä kaikki päätökset. 164 00:08:57,140 --> 00:09:00,940 >> Näitä tilanteita kutsutaan kontradiktorisen haku, joka tunnetaan myös nimellä 165 00:09:00,940 --> 00:09:05,390 kuten miten kirjoittaa pelin pelaaminen järjestelmät ja saat maksaa sen. 166 00:09:05,390 --> 00:09:07,940 Mutta nämä ovat erilaisia Järjestelmien jossa I 167 00:09:07,940 --> 00:09:12,920 saattaa saada valita, milloin menen Boston, mikä kaupunki menen seuraavaksi. 168 00:09:12,920 --> 00:09:19,990 Mutta sen jälkeen, joku muu voi saada tehdä päätöksen siitä, missä minä lentää. 169 00:09:19,990 --> 00:09:24,040 Joten rakentaa nämä erilaisia ​​rakenteita, olemme 170 00:09:24,040 --> 00:09:28,510 täytyy ottaa hieman erilainen lähestymistapa sen. 171 00:09:28,510 --> 00:09:31,060 Emme aio pystyä vain etsiä puu 172 00:09:31,060 --> 00:09:35,000 enää, koska emme ole yksi, joka on hallinnassa 173 00:09:35,000 --> 00:09:38,180 kunkin tällaisen päätöksen pistettä. 174 00:09:38,180 --> 00:09:42,590 >> Joten kuvitella yksinkertainen peli kuin Ristinolla. 175 00:09:42,590 --> 00:09:46,730 Voisin aloittaa täysin tyhjä board. 176 00:09:46,730 --> 00:09:49,580 Ja Ristinolla, X saa pelata ensin. 177 00:09:49,580 --> 00:09:53,890 Ja niin voisin ajatella kaikki mahdollista siirtoa että X voisi tehdä. 178 00:09:53,890 --> 00:09:57,420 Ja jos olen yksi soitto X, hienoa. 179 00:09:57,420 --> 00:10:01,020 Minulla on yhdeksän mahdollista liikkuu, että voin tehdä. 180 00:10:01,020 --> 00:10:05,000 Voisin laittaa X tahansa näistä yhdeksän kantoja. 181 00:10:05,000 --> 00:10:10,710 >> Ja sitten kunkin näistä, minä voisi kuvitella, mitä tapahtuu seuraavaksi. 182 00:10:10,710 --> 00:10:14,130 No, tässä tapauksessa, muut pelaaja saisi vuorollaan. 183 00:10:14,130 --> 00:10:15,660 O saisi vuorollaan. 184 00:10:15,660 --> 00:10:19,510 Ja kunkin näistä on olisi kahdeksan eri paikoissa 185 00:10:19,510 --> 00:10:22,980 että O voisivat sijoittaa niiden merkki. 186 00:10:22,980 --> 00:10:25,790 >> Sanotaan päätin, että olin aikoo laittaa X keskustassa. 187 00:10:25,790 --> 00:10:28,810 Että aina tuntuu hyvä avaussiirto. 188 00:10:28,810 --> 00:10:34,870 Voisin katsoa alla, että kahdeksan mahdollista siirtoa että O tekee. 189 00:10:34,870 --> 00:10:37,320 Nyt, jos pelaan X, joka on ihana. 190 00:10:37,320 --> 00:10:41,740 Saan valita, mihin minä mennä, yksi keskellä. 191 00:10:41,740 --> 00:10:45,000 Mutta nyt O saa valita. 192 00:10:45,000 --> 00:10:48,750 Ja minulla ei ole valvontaa yli kyseisen päätöksen. 193 00:10:48,750 --> 00:10:51,670 >> Mutta kunkin näistä mahdollista hallituksissa, 194 00:10:51,670 --> 00:10:54,020 siellä on sitten toinen joukko mahdollisuuksia. 195 00:10:54,020 --> 00:10:56,700 Kun se tulee olla Minun vuoroni jälleen, olisin 196 00:10:56,700 --> 00:11:01,500 saat valita ja sanoa, hyvin, jos O siirtyy, hyvin, 197 00:11:01,500 --> 00:11:06,110 keskimmäinen paikalla vasemmalle, sitten Minulla on joukko mahdollisuuksia 198 00:11:06,110 --> 00:11:09,740 jossa voin ottaa minun seuraava siirto. 199 00:11:09,740 --> 00:11:14,140 Noista, voisin harkita kaikkia mahdollisuuksista niiden alle. 200 00:11:14,140 --> 00:11:18,030 Ja sitten O saisi valita joukossa. 201 00:11:18,030 --> 00:11:22,290 >> Ja voisin pitää rakentaa tämän puu, kunnes sain siihen pisteeseen 202 00:11:22,290 --> 00:11:26,960 joissa joko joku voittaa game-- se 203 00:11:26,960 --> 00:11:31,070 Täytyy pitää lehtiä node-- tai lauta on aivan täynnä 204 00:11:31,070 --> 00:11:32,704 ja kukaan ei ole voittanut. 205 00:11:32,704 --> 00:11:34,370 Ja joka on myös olemaan lehtisolmu. 206 00:11:34,370 --> 00:11:35,411 Se tulee olemaan solmio. 207 00:11:35,411 --> 00:11:37,820 208 00:11:37,820 --> 00:11:41,680 >> Mutta hankala juttu tämä on jos tämä olisi vain tavallinen haku 209 00:11:41,680 --> 00:11:44,269 ongelma, olisin pystyä sanoa, hyvin, X pitäisi mennä täällä. 210 00:11:44,269 --> 00:11:45,560 Ja O pitäisi mennä tapa tuolla. 211 00:11:45,560 --> 00:11:46,770 Ja niin X pitäisi mennä tänne. 212 00:11:46,770 --> 00:11:48,269 Ja sitten O pitäisi mennä tapa tuolla. 213 00:11:48,269 --> 00:11:51,860 Ja sitten X voi saada kolme peräkkäin, ja voitan. 214 00:11:51,860 --> 00:11:54,870 Ja peli olisi ohi viidessä liikkuu, kolme minulle, 215 00:11:54,870 --> 00:11:57,710 kaksi minun vastustaja. 216 00:11:57,710 --> 00:12:01,300 Mutta en aina päästä valita että. 217 00:12:01,300 --> 00:12:03,720 >> Joten sen sijaan, mitä olemme täytyy tehdä 218 00:12:03,720 --> 00:12:06,270 on aiomme olla on uusi strategia. 219 00:12:06,270 --> 00:12:09,350 Ja strategia, peli-pelissä algoritmit käyttävät usein 220 00:12:09,350 --> 00:12:12,000 on mitä kutsutaan minimax. 221 00:12:12,000 --> 00:12:15,500 Keskeinen ajatus minimax on, että olemme 222 00:12:15,500 --> 00:12:21,365 vilkastumassa liikkua joka antaa vastustaja pahin mahdollinen joukko 223 00:12:21,365 --> 00:12:22,790 liikkuu, että he voivat tehdä. 224 00:12:22,790 --> 00:12:25,570 225 00:12:25,570 --> 00:12:28,870 Se ei tee minulle mitään hyvää valita liikkua missä 226 00:12:28,870 --> 00:12:31,952 Voisin voittaa jälkeen että, koska minun vastustaja ei ole 227 00:12:31,952 --> 00:12:33,160 aio antaa minulle mahdollisuuden. 228 00:12:33,160 --> 00:12:37,770 He aikovat valita joitakin kauhea lopputulos minulle. 229 00:12:37,770 --> 00:12:42,010 Joten aion tehdä liikkua joka pakottaa vastustajani 230 00:12:42,010 --> 00:12:45,760 tehdä jotain parempi minulle. 231 00:12:45,760 --> 00:12:46,260 Selvä. 232 00:12:46,260 --> 00:12:48,410 Katsotaanpa, miten se pelaa. 233 00:12:48,410 --> 00:12:51,640 Joten tässä on meidän algoritmi pseudokoodilla. 234 00:12:51,640 --> 00:12:54,450 Aiomme tuottaa koko pelin puu. 235 00:12:54,450 --> 00:12:56,757 Aiomme rakentaa koko rakenne. 236 00:12:56,757 --> 00:12:57,840 Ja sitten mennään läpi. 237 00:12:57,840 --> 00:13:02,100 Ja alareunassa kullakin päätesolmuja, kussakin lehdet, 238 00:13:02,100 --> 00:13:07,850 me arvioida, kuinka arvokasta on, että minulle? 239 00:13:07,850 --> 00:13:11,690 Ja aiomme arvo asioita, ovat hyvä minulle olevan positiivinen. 240 00:13:11,690 --> 00:13:14,460 Asioita, jotka eivät ole hyvä minulle on vähemmän positiivinen, tai nolla, 241 00:13:14,460 --> 00:13:16,480 tai jopa negatiivinen. 242 00:13:16,480 --> 00:13:19,240 >> Joten Ristinolla, ehkä voitto on minulle hyvä. 243 00:13:19,240 --> 00:13:20,290 Se on yksi. 244 00:13:20,290 --> 00:13:22,400 Ja tie on nolla. 245 00:13:22,400 --> 00:13:26,230 Ja jotain, joka on tappio minulle, ehkä se negatiivinen. 246 00:13:26,230 --> 00:13:29,620 Tärkeää on, että parempi se on minulle, korkeammat pisteet 247 00:13:29,620 --> 00:13:32,160 se saa. 248 00:13:32,160 --> 00:13:36,690 Noista mahdollisuuksiin pohja, sitten me suodattaa ylöspäin. 249 00:13:36,690 --> 00:13:40,650 Ja kun se on minun mahdollisuus valita keskuudessa joukko vaihtoehtoja, 250 00:13:40,650 --> 00:13:44,460 Minä valita yksi, joka on sai korkeimmat pisteet. 251 00:13:44,460 --> 00:13:47,200 >> Ja aina kun se on minun vastustajat puolestaan ​​valita, 252 00:13:47,200 --> 00:13:52,350 Minä olettaa, että he aikovat valita yksi alin pistemäärä. 253 00:13:52,350 --> 00:13:56,090 Ja jos en tee tätä koko matkan jopa puun latvaan, 254 00:13:56,090 --> 00:14:03,150 Minä olen valinnut polku, joka antaa minulle paras tulos, että voin saada, 255 00:14:03,150 --> 00:14:09,110 olettaen että vastustajani tekee kaikki oikein liikkuu. 256 00:14:09,110 --> 00:14:11,940 >> Selvä, joten katsotaanpa tämä toiminnassa ensin. 257 00:14:11,940 --> 00:14:14,980 Ja sitten me oikeastaan katso koodia. 258 00:14:14,980 --> 00:14:16,780 Joten kuvitella Olen tämän iso puu. 259 00:14:16,780 --> 00:14:18,280 Ja nyt en pelaa Ristinolla. 260 00:14:18,280 --> 00:14:20,405 Halusin antaa sinulle jotain hieman rikkaampi. 261 00:14:20,405 --> 00:14:23,560 Joten minulla joitakin peli, jossa olemassa monia eri tulokset 262 00:14:23,560 --> 00:14:26,390 että voisin olla lopussa. 263 00:14:26,390 --> 00:14:27,980 Ja niin minä rakentaa tämä täydellinen puu. 264 00:14:27,980 --> 00:14:29,070 Ja saan liikkua ensin. 265 00:14:29,070 --> 00:14:31,290 Olen juureen puun. 266 00:14:31,290 --> 00:14:36,150 >> Ja saan valita that-- niin saan maksimoida poikki ensimmäinen solmu. 267 00:14:36,150 --> 00:14:38,410 Ja sitten minun vastustaja saa mennä. 268 00:14:38,410 --> 00:14:41,910 Ja sitten saan mennä kerran. 269 00:14:41,910 --> 00:14:46,830 Niin alas alareunassa, minulla on joukko mahdollisuuksia, että voin valita, 270 00:14:46,830 --> 00:14:50,570 eri pääte valtioiden peli. 271 00:14:50,570 --> 00:14:54,980 Jos olen alas että äärivasemmiston yläkulmassa, 272 00:14:54,980 --> 00:14:58,867 ja näen, että minulla valinta välillä kahdeksan, seitsemän, ja kaksi, 273 00:14:58,867 --> 00:15:00,450 No, olen se, joka saa valita. 274 00:15:00,450 --> 00:15:02,910 Joten aion valita paras yksi niistä. 275 00:15:02,910 --> 00:15:05,650 Aion valita kahdeksan. 276 00:15:05,650 --> 00:15:10,090 >> Joten tiedän, että jos olen koskaan saada alas että kohta, 277 00:15:10,090 --> 00:15:13,890 Minä voi saada, että kahdeksan pistettä. 278 00:15:13,890 --> 00:15:17,410 Jos minä päätyvät seuraavan pisteen yli, seuraava solmu yli, 279 00:15:17,410 --> 00:15:20,760 yhdeksän, yksi tai kuusi, hyvin, olen aikoo valita paras niistä. 280 00:15:20,760 --> 00:15:21,950 Minä valita yhdeksän. 281 00:15:21,950 --> 00:15:24,880 Jos minulla on mahdollisuus valita kaksi ja neljä, ja yksi, 282 00:15:24,880 --> 00:15:28,240 Minä valita neljä, korkein. 283 00:15:28,240 --> 00:15:31,990 >> Nyt, jos katson tasolla yläpuolella, vastustajani 284 00:15:31,990 --> 00:15:34,440 on yksi saa tehdä tämä valinta. 285 00:15:34,440 --> 00:15:37,040 Joten minun vastustaja saa valita, tehdä Haluan antaa hänelle 286 00:15:37,040 --> 00:15:39,250 asia, joka tulee saada hänet kahdeksan pistettä, 287 00:15:39,250 --> 00:15:41,916 tai voin antaa hänelle asia, joka on aikoo antaa hänelle yhdeksän pistettä, 288 00:15:41,916 --> 00:15:45,240 tai asia, joka tulee antaa hänelle neljä pistettä? 289 00:15:45,240 --> 00:15:49,130 Ja minun vastustaja, joka rationaalinen, on menossa 290 00:15:49,130 --> 00:15:53,470 valita vähintään näiden, aikoo valita neljä. 291 00:15:53,470 --> 00:15:56,020 >> Ja voin tehdä tämän läpi koko puun. 292 00:15:56,020 --> 00:15:59,110 En voi mennä alas, että keskellä asettaa kolme. 293 00:15:59,110 --> 00:16:01,517 Ja voin valita yksi, kolme ja viisi. 294 00:16:01,517 --> 00:16:02,350 Ja saan valita. 295 00:16:02,350 --> 00:16:03,810 Joten valitsen viisi. 296 00:16:03,810 --> 00:16:05,340 Voin valita kolme, yhdeksän tai kaksi. 297 00:16:05,340 --> 00:16:07,570 Saan valita, niin valitsen yhdeksän. 298 00:16:07,570 --> 00:16:09,290 Kuusi, viisi, tai kaksi, valitsen. 299 00:16:09,290 --> 00:16:11,539 Saan valita kuusi. 300 00:16:11,539 --> 00:16:13,080 Yläpuolella, että kuka saa valita? 301 00:16:13,080 --> 00:16:16,280 302 00:16:16,280 --> 00:16:18,140 Kuka saa valita? 303 00:16:18,140 --> 00:16:20,000 Muut kaveri, minun vastustaja. 304 00:16:20,000 --> 00:16:22,583 Joten he valitsevat viisi, yhdeksän, tai kuusi, joista yksi? 305 00:16:22,583 --> 00:16:23,410 >> Yleisö: viisi. 306 00:16:23,410 --> 00:16:25,250 >> SPEAKER: He valitsevat viisi. 307 00:16:25,250 --> 00:16:27,400 He saavat valita pienin. 308 00:16:27,400 --> 00:16:29,690 Ja sitten viimeinen, valita yksi, kaksi tai kolme. 309 00:16:29,690 --> 00:16:31,720 Saan valita, niin valitsen kolme. 310 00:16:31,720 --> 00:16:34,370 Yhdeksän, seitsemän tai kaksi, valitsen yhdeksän. 311 00:16:34,370 --> 00:16:37,070 Ja 11, kuusi tai neljä, valitsen 11. 312 00:16:37,070 --> 00:16:41,190 Vastustajani valitsee sitten kolme, yhdeksän, tai 11, valitsee minimiin. 313 00:16:41,190 --> 00:16:43,290 Hän antaa minulle kolme. 314 00:16:43,290 --> 00:16:47,780 Ja sitten lopulta yläreunassa puu, saan valita uudelleen. 315 00:16:47,780 --> 00:16:51,190 Ja saan valita neljä, viisi tai kolme. 316 00:16:51,190 --> 00:16:52,270 Joten otan viisi. 317 00:16:52,270 --> 00:16:55,070 318 00:16:55,070 --> 00:17:00,891 >> Jos sain kontrolloida kaikkea, olisin polkua, joka johti 11. 319 00:17:00,891 --> 00:17:02,390 Mutta en saa tehdä tämä valinta. 320 00:17:02,390 --> 00:17:04,220 Jos menen tätä tietä. 321 00:17:04,220 --> 00:17:10,710 Vastustajani pakottaa minut valinta, joka johtaa kolme. 322 00:17:10,710 --> 00:17:14,530 Joten paras että voin tehdä on ottaa että keski haara, 323 00:17:14,530 --> 00:17:19,859 jotta valinta olisi se lopulta menossa johtaa minut viisi pistettä. 324 00:17:19,859 --> 00:17:23,230 Sitähän minimax tekee. 325 00:17:23,230 --> 00:17:23,807 >> Selvä. 326 00:17:23,807 --> 00:17:24,890 Katsotaanpa katsomaan, että. 327 00:17:24,890 --> 00:17:27,480 328 00:17:27,480 --> 00:17:32,330 Joten täällä CS50 IDE on ohjelma, joka 329 00:17:32,330 --> 00:17:36,540 toteuttaa minimax pelata Ristinolla. 330 00:17:36,540 --> 00:17:40,100 Aiomme rakentaa ylös edustus. 331 00:17:40,100 --> 00:17:44,390 Aiomme olla kaksi opponent-- tai kaksi pelaajaa, meidän tietokone 332 00:17:44,390 --> 00:17:46,090 soitin ja ihmisen pelaaja. 333 00:17:46,090 --> 00:17:48,980 334 00:17:48,980 --> 00:17:53,090 Pelaaja numero yksi pelaavat O. Se tulee olemaan koneen pelaaja. 335 00:17:53,090 --> 00:17:55,747 He saavat liikkua toiseen. 336 00:17:55,747 --> 00:17:57,830 Ja toinen pelaaja, meidän ihmisen pelaaja, on X. 337 00:17:57,830 --> 00:17:59,880 >> Ja tehdä elämäni vähän yksinkertainen, aion 338 00:17:59,880 --> 00:18:03,060 merkitä, että pelaaja kielteinen. 339 00:18:03,060 --> 00:18:05,026 Joten voin vain kertoa negatiivisen yksi vaihtaa 340 00:18:05,026 --> 00:18:06,400 välillä yksi pelaaja ja muut. 341 00:18:06,400 --> 00:18:09,030 342 00:18:09,030 --> 00:18:12,250 Selvä, joten katsotaanpa katsomaan mitä me todella aiomme tehdä. 343 00:18:12,250 --> 00:18:15,840 Aiomme määritellä meidän aluksella. 344 00:18:15,840 --> 00:18:19,060 Se tulee olemaan hyvin, aiomme jotta se voi olla kolme kolme, 345 00:18:19,060 --> 00:18:21,580 tai voimme jopa pelata viisi viisi tai seitsemän 346 00:18:21,580 --> 00:18:28,870 seitsemän Ristinolla jos olisit kuten, joka perustuu joitakin ulottuvuus D. 347 00:18:28,870 --> 00:18:31,260 >> Ja meillä on pari auttaja toimintoja 348 00:18:31,260 --> 00:18:34,360 että teemme asioita, kuten alustaa screen-- tai anteeksi, 349 00:18:34,360 --> 00:18:38,900 alustaa meidän muuttujat, tyhjennä näyttö, piirtää hallituksen ruudulla, 350 00:18:38,900 --> 00:18:41,060 joka tarkistaa hallitus onko vai ei 351 00:18:41,060 --> 00:18:44,520 siellä on voittaja, joka jäsentää kautta komentoriviltä, 352 00:18:44,520 --> 00:18:50,670 vain auttaa, joka lukee tulo, ja yksi toiminto nimeltään minimax. 353 00:18:50,670 --> 00:18:52,746 Ja se on yksi me välittävät eniten. 354 00:18:52,746 --> 00:18:54,120 Mutta Katsotaanpa ensin tärkein. 355 00:18:54,120 --> 00:18:57,490 356 00:18:57,490 --> 00:18:58,510 >> Mitä me teemme? 357 00:18:58,510 --> 00:19:00,570 No, me aiomme jäsentää meidän komentoriviltä, 358 00:19:00,570 --> 00:19:04,300 juuri lukenut ja katso, mitä ulottuvuus aluksella haluaisimme olla. 359 00:19:04,300 --> 00:19:07,330 Me alustaa meidän aluksella. 360 00:19:07,330 --> 00:19:10,360 Ja sitten me anna yksi iso villi silmukka, toistuvasti 361 00:19:10,360 --> 00:19:16,630 hyväksyä liikkuu kunnes peli on voitti, tai ei ole siirtyy vasemmalle. 362 00:19:16,630 --> 00:19:20,560 Joka kerta käymme läpi, että silmukka, me tyhjentää näytön. 363 00:19:20,560 --> 00:19:23,290 Me kiinnittää lauta ruudulle. 364 00:19:23,290 --> 00:19:28,750 Ja me olemme tietoisesti tavallaan Abstrahoimalla nämä pois aliohjelmina, 365 00:19:28,750 --> 00:19:32,030 jotta meidän ei tarvitse huolehtia liikaa yksityiskohdista, miten ne tapahtuvat. 366 00:19:32,030 --> 00:19:33,480 >> Sinulla on koodi myöhemmin tänään. 367 00:19:33,480 --> 00:19:37,970 Ja jos haluat käydä läpi ja selvittää, näet ne kaikki. 368 00:19:37,970 --> 00:19:39,890 Mutta me piirtää hallituksen ruudulla. 369 00:19:39,890 --> 00:19:43,620 Ja sitten me tarkistaa ja katso, meillä on voittaja? 370 00:19:43,620 --> 00:19:46,290 Onko joku voitti tämän pelin? 371 00:19:46,290 --> 00:19:49,260 Jos heillä on, me tulostaa ulos voitto viesti. 372 00:19:49,260 --> 00:19:51,680 Ja me lopettaa pelin. 373 00:19:51,680 --> 00:19:54,510 >> Otamme myös tarkistaa ja onko siellä solmio. 374 00:19:54,510 --> 00:19:56,620 Se tulee olemaan helppo nähdä, jos siellä solmio. 375 00:19:56,620 --> 00:20:00,700 Se tarkoittaa, että kaikki tilat ovat täynnä, mutta ei ole ollut voittaja vielä. 376 00:20:00,700 --> 00:20:03,580 Voimme julistaa solmio ja tehdä. 377 00:20:03,580 --> 00:20:10,530 Sitten todellinen meat-- jos se kone pelaaja, 378 00:20:10,530 --> 00:20:14,120 me sallia kone pelaaja etsiä 379 00:20:14,120 --> 00:20:19,500 kautta käyttämällä tätä Minimax algoritmia, löytää parhaan tilanteen, että se voi. 380 00:20:19,500 --> 00:20:22,310 Ja sitten me laitamme että liikkua ylös. 381 00:20:22,310 --> 00:20:27,640 >> Muuten, jos se on ihmisen pelaaja, me lukenut joitakin panosta ihmisen. 382 00:20:27,640 --> 00:20:30,800 Ja sitten onko se ihmisen soitin tai koneen pelaaja, 383 00:20:30,800 --> 00:20:32,800 teemme pari vähän bittiä virheentarkistus, 384 00:20:32,800 --> 00:20:36,910 varmista, että se pysyy rajoissa ja todelliset mitat hallituksen 385 00:20:36,910 --> 00:20:40,040 että meillä on, varmista että avaruus on tyhjä, 386 00:20:40,040 --> 00:20:43,570 ettei kenenkään laittaa pala siellä jo. 387 00:20:43,570 --> 00:20:45,810 Ja sitten me vain laittaa pala pöydällä, 388 00:20:45,810 --> 00:20:51,550 muuttaa soittimen seuraavaan kerrokseen, ja increment kuinka moni liikkuu tapahtunut. 389 00:20:51,550 --> 00:20:54,090 >> Se on tärkein silmukka meidän Ristinolla peli. 390 00:20:54,090 --> 00:20:57,000 391 00:20:57,000 --> 00:21:02,340 Minimax sitten, on täsmälleen algoritmi, joka me ennen. 392 00:21:02,340 --> 00:21:04,710 Ainoa säätö että olemme tehneet niin, että me 393 00:21:04,710 --> 00:21:07,290 voi pelata suurempi ulotteinen levyt on olemme 394 00:21:07,290 --> 00:21:11,070 pidetään tätä ylimääräistä parametri nimeltä syvyys. 395 00:21:11,070 --> 00:21:14,870 Ja syvyys vain sanoo, jos olen hakuja alaspäin kautta että puu 396 00:21:14,870 --> 00:21:19,022 ja saan niin pitkälle yli jonkin verran syvyyttä 397 00:21:19,022 --> 00:21:20,730 että en vain halua mennä pidemmälle, 398 00:21:20,730 --> 00:21:25,630 Aion lopettaa ja juuri arvioida hallituksen tässä vaiheessa. 399 00:21:25,630 --> 00:21:27,310 Tarkistan ja onko siellä voittaja. 400 00:21:27,310 --> 00:21:29,240 Jos on voittaja, palaan niihin. 401 00:21:29,240 --> 00:21:31,720 Muuten, menen läpi silmukka. 402 00:21:31,720 --> 00:21:34,380 Ja minä sanon, kaikille mahdollisia paikkoja 403 00:21:34,380 --> 00:21:38,080 että voisin mahdollisesti ottaa niin minun liikkua, minä 404 00:21:38,080 --> 00:21:43,760 rakentaa hypoteettinen aluksella, joka sisältää minun siirtyä että aluksella, 405 00:21:43,760 --> 00:21:45,960 ja sitten rekursiivisesti kutsuu minimax. 406 00:21:45,960 --> 00:21:49,360 407 00:21:49,360 --> 00:21:53,900 >> Jos se on minun liikkua, saan löytää joka sai suurimman pisteet. 408 00:21:53,900 --> 00:21:58,710 Jos se on minun vastustajan liikkua, löydämme joka sai vähintään pisteet. 409 00:21:58,710 --> 00:22:02,240 Ja kaikki muu on vain kirjanpito. 410 00:22:02,240 --> 00:22:04,789 Selvä, joten katsotaanpa tämä aikavälillä. 411 00:22:04,789 --> 00:22:06,830 Oikeastaan, ehkä voimme saada pari vapaaehtoisia 412 00:22:06,830 --> 00:22:09,930 keksiä ja pelata Ristinolla. 413 00:22:09,930 --> 00:22:12,780 [Äänetön] yksi, ja yksi enemmän, kaksi, tuolla. 414 00:22:12,780 --> 00:22:13,550 Tule ylös. 415 00:22:13,550 --> 00:22:19,290 416 00:22:19,290 --> 00:22:23,650 >> Joten mene eteenpäin ja käynnistä tämä täysin. 417 00:22:23,650 --> 00:22:24,150 Joten, hei. 418 00:22:24,150 --> 00:22:24,920 >> Yleisö: Hei. 419 00:22:24,920 --> 00:22:25,420 >> SPEAKER: Mikä on nimesi? 420 00:22:25,420 --> 00:22:26,086 >> Yleisö: Gorav. 421 00:22:26,086 --> 00:22:26,840 SPEAKER: Gorav. 422 00:22:26,840 --> 00:22:27,800 >> Yleisö: Olen Layla. 423 00:22:27,800 --> 00:22:29,490 >> SPEAKER: Ja Layla, ja Layla, anteeksi. 424 00:22:29,490 --> 00:22:30,384 Tule ylös. 425 00:22:30,384 --> 00:22:32,050 Gorav, me aiomme saada sinut mennä ensin. 426 00:22:32,050 --> 00:22:37,710 Ja aion pyytää sinua ei hirveän hyvä Ristinolla soitin. 427 00:22:37,710 --> 00:22:40,130 OK, joten kaikki paine on pois sinua. 428 00:22:40,130 --> 00:22:44,660 Katsotaanpa, kuitenkin, että kone pelaaja voi todella tehdä jotain älykästä. 429 00:22:44,660 --> 00:22:45,310 Joten mene eteenpäin. 430 00:22:45,310 --> 00:22:49,830 Olet menossa kirjoittaa johon koordinoida haluat laittaa X. 431 00:22:49,830 --> 00:22:55,170 A0, OK, ja kone on mennyt heti ja laittaa jälkensä A1. 432 00:22:55,170 --> 00:22:56,640 >> Laita O taululle. 433 00:22:56,640 --> 00:22:58,970 Okei, nyt mennä eteenpäin. 434 00:22:58,970 --> 00:23:00,193 Minne haluaisit mennä? 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 Meidän kone pelaaja on ottanut keskimmäinen neliö, estänyt sinut. 438 00:23:08,430 --> 00:23:10,320 Joten se oli hyvä, fiksu asia se tehdä. 439 00:23:10,320 --> 00:23:13,430 440 00:23:13,430 --> 00:23:14,250 Olet estänyt sen. 441 00:23:14,250 --> 00:23:15,210 Se on erinomainen. 442 00:23:15,210 --> 00:23:16,390 Se vie nurkassa. 443 00:23:16,390 --> 00:23:23,890 444 00:23:23,890 --> 00:23:30,430 >> Ja se tulee pakottaa sinut ottaa viimeinen tila, B0. 445 00:23:30,430 --> 00:23:32,220 Ja peli päättyy tasan. 446 00:23:32,220 --> 00:23:35,030 Mutta se pelataan kohtuullinen peli sinua vastaan, eikö? 447 00:23:35,030 --> 00:23:36,956 Selvä, kiitos paljon, Gorav. 448 00:23:36,956 --> 00:23:40,860 >> [SUOSIONOSOITUKSET] 449 00:23:40,860 --> 00:23:44,723 >> Hyvä on, Layla, menemme up peli täällä. 450 00:23:44,723 --> 00:23:46,940 >> Yleisö: Hienoa. 451 00:23:46,940 --> 00:23:49,950 >> SPEAKER: Me aiomme antaa te neljä neljä Ristinolla. 452 00:23:49,950 --> 00:23:54,760 Nyt neljä neljä, sinulla on voittaa neljä peräkkäin, ei kolme peräkkäin. 453 00:23:54,760 --> 00:23:56,135 Ja se on kokonaan sinun. 454 00:23:56,135 --> 00:24:02,180 455 00:24:02,180 --> 00:24:04,420 Joten Layla otti D1. 456 00:24:04,420 --> 00:24:11,730 Olemme nyt menossa seuraamaan meidän tietokone pelaaja täällä. 457 00:24:11,730 --> 00:24:16,910 Kolme kolme Ristinolla on sellainen asia, että on helppo meille kaikille. 458 00:24:16,910 --> 00:24:21,960 Mutta se on silti mukava nähdä tietokone pelaaja tekee fiksu liikkuu. 459 00:24:21,960 --> 00:24:23,725 Neljä neljä saa olla hieman hankalampaa. 460 00:24:23,725 --> 00:24:42,960 461 00:24:42,960 --> 00:24:44,230 >> Hyvin tehty. 462 00:24:44,230 --> 00:24:46,210 Selvä, joten Layla n viimeisteli. 463 00:24:46,210 --> 00:24:48,270 Niin, ja meidän olisi pitänyt päättyä siellä. 464 00:24:48,270 --> 00:24:51,870 Mutta katsotaanpa vielä yhden täällä. 465 00:24:51,870 --> 00:24:53,480 Joten Layla, kiitos. 466 00:24:53,480 --> 00:24:55,112 Hyvin tehty. 467 00:24:55,112 --> 00:24:57,517 >> [SUOSIONOSOITUKSET] 468 00:24:57,517 --> 00:25:00,410 469 00:25:00,410 --> 00:25:04,750 >> Joten meidän Ristinolla pelaaja menee läpi ja löytää paikkoja, 470 00:25:04,750 --> 00:25:07,040 ratkaisee ne tämän Minimax. 471 00:25:07,040 --> 00:25:08,990 Ja minulla oli syvyysasetusta siitä, että niin, että se 472 00:25:08,990 --> 00:25:11,010 ei juosta liian nopeasti, joka on luultavasti miksi 473 00:25:11,010 --> 00:25:16,790 Layla voinut mennä hienosti eteenpäin kuten hän teki, ja teki erittäin hyvin. 474 00:25:16,790 --> 00:25:20,450 Mutta nämä järjestelmät että vain läpi ja raa'alla voimalla 475 00:25:20,450 --> 00:25:23,870 mennä syvemmälle, ja syvemmälle, ja syvemmälle, ja pitää löytää ratkaisu 476 00:25:23,870 --> 00:25:29,890 että he tarvitsevat, tuollaiset järjestelmät ovat varsin onnistunut näissä, hyvin, 477 00:25:29,890 --> 00:25:32,700 standardi lautapelejä. 478 00:25:32,700 --> 00:25:37,060 >> Ja itse asiassa, jos katsomme kolme kolmen Ristinolla peli, 479 00:25:37,060 --> 00:25:40,040 tämä on periaatteessa ratkaistu ongelma. 480 00:25:40,040 --> 00:25:45,430 Ja tämä on hieno kaavio Randall Munroe klo XKCD, 481 00:25:45,430 --> 00:25:52,130 näyttää jotka liikkuvat sinun pitäisi ottaa, koska vastustajan liikkeitä. 482 00:25:52,130 --> 00:25:56,420 Tämä on jotain, että voisimme helposti määrittää etuajassa. 483 00:25:56,420 --> 00:26:00,180 Mutta mitä tapahtuu, kun saamme enemmän monimutkaisia ​​pelejä, monimutkaisemman pelejä, 484 00:26:00,180 --> 00:26:05,690 jossa on isompi levyt, lisää mahdollisuuksia, syvempi strategia? 485 00:26:05,690 --> 00:26:09,660 >> Osoittautuu, että tämä brute force etsivät edelleen 486 00:26:09,660 --> 00:26:14,150 ei kohtuullisen hyvin, paitsi kun saat siihen pisteeseen 487 00:26:14,150 --> 00:26:19,230 jos tämä puu on niin suuri että et voi edustaa kaikkea. 488 00:26:19,230 --> 00:26:22,370 489 00:26:22,370 --> 00:26:28,280 Kun et voi laskea koko puu, kun ei voi mennä eteenpäin ja työntää 490 00:26:28,280 --> 00:26:32,204 itsesi siihen pisteeseen, jossa olet saanut koko puu muistissa, 491 00:26:32,204 --> 00:26:34,370 vai voit saada sen muistiin ja se vain 492 00:26:34,370 --> 00:26:39,200 vie aivan liian pitkä etsiä se, sinun täytyy tehdä jotain älykkäämpiä. 493 00:26:39,200 --> 00:26:42,620 494 00:26:42,620 --> 00:26:46,450 >> Voidakseen tehdä niin, te täytyy tehdä kaksi asiaa. 495 00:26:46,450 --> 00:26:49,030 Ensinnäkin, sinun täytyy löytää tapa rajoittaa syvyys. 496 00:26:49,030 --> 00:26:50,370 No, se on OK. 497 00:26:50,370 --> 00:26:55,740 Voimme löytää kivoja, minimiin ja sanoa, et voi vain mennä niin syvälle. 498 00:26:55,740 --> 00:27:00,890 Mutta kun teet näin, se tarkoittaa, että näitä osittain puutteellisia levyt. 499 00:27:00,890 --> 00:27:04,770 Ja sinun täytyy valita, tehdä pidän tämä osittain puutteellisia aluksella, 500 00:27:04,770 --> 00:27:08,600 tai tämä osittain puutteellisia hallitus? 501 00:27:08,600 --> 00:27:11,910 >> Ja meidän neljä neljä Ristinolla peli, 502 00:27:11,910 --> 00:27:15,240 meidän tietokone pelaaja sai alas pohjaan ja se sanoi, 503 00:27:15,240 --> 00:27:16,800 Minulla kaksi eri levyt. 504 00:27:16,800 --> 00:27:17,940 Kumpikaan on win. 505 00:27:17,940 --> 00:27:19,120 Kumpikaan on tappio. 506 00:27:19,120 --> 00:27:22,070 Kumpikaan on tie. 507 00:27:22,070 --> 00:27:24,100 Miten valita ne? 508 00:27:24,100 --> 00:27:26,200 Ja se ei ole fiksu tapa tehdä se. 509 00:27:26,200 --> 00:27:28,910 510 00:27:28,910 --> 00:27:32,850 >> Näemme tällaista arviointi tapahtuu koko ajan 511 00:27:32,850 --> 00:27:35,290 kun pääsemme monimutkaisempia pelejä. 512 00:27:35,290 --> 00:27:37,600 Shakki on loistava esimerkki. 513 00:27:37,600 --> 00:27:41,550 Shakki, meillä on ensimmäinen Kaikkien, suurempi aluksella. 514 00:27:41,550 --> 00:27:43,370 Meillä on paljon enemmän kappaletta. 515 00:27:43,370 --> 00:27:47,930 Ja paikannus nämä kappaleet ja siten, että nämä kappaleet liikkuvat 516 00:27:47,930 --> 00:27:50,370 on ratkaisevan tärkeää. 517 00:27:50,370 --> 00:27:53,700 Joten jos haluan käyttää minimax, Minun täytyy voitava määritellä 518 00:27:53,700 --> 00:27:58,240 ja sanoa, tämä hallitus, jossa kukaan ei ole voittanut tai menettänyt vielä, 519 00:27:58,240 --> 00:28:04,310 on jotenkin parempi kuin tämä muut aluksella, jossa kukaan ei ole voittanut tai kadonnut. 520 00:28:04,310 --> 00:28:06,740 >> Voit tehdä, että voisin tehdä asioita, kuten voisin vain 521 00:28:06,740 --> 00:28:10,787 laskea kuinka monta kappaletta minulla on ja kuinka monta kappaletta sinulla on? 522 00:28:10,787 --> 00:28:12,870 Tai voisin antaa eri kappaletta eri kohdissa. 523 00:28:12,870 --> 00:28:14,420 Minun kuningatar kannattaa 20 pistettä. 524 00:28:14,420 --> 00:28:16,500 Sinun sotilas on arvoltaan yhden pisteen. 525 00:28:16,500 --> 00:28:18,920 Kuka on enemmän pisteitä yhteensä? 526 00:28:18,920 --> 00:28:22,300 Tai voisin harkita asioita, kuten kenellä on parempi paikkansa hallituksessa? 527 00:28:22,300 --> 00:28:26,820 Kenen vuoro on ensi, mitään, että voin 528 00:28:26,820 --> 00:28:31,220 ei arvioida tarkemmin joka näistä mahdollisuuksista 529 00:28:31,220 --> 00:28:34,660 on parempi ilman tyhjentävästi harkitsee 530 00:28:34,660 --> 00:28:36,565 jokaista liikettä, joka voisi tulla sen jälkeen. 531 00:28:36,565 --> 00:28:39,740 532 00:28:39,740 --> 00:28:45,130 >> Nyt tehdä tätä työtä, yksi niistä asioista, jotka on 533 00:28:45,130 --> 00:28:48,680 tulossa todella tärkeä meille ei ole vain liikkuvat suoraan 534 00:28:48,680 --> 00:28:53,720 alas tiettyyn syvyyteen raja, mutta voi sanoa, 535 00:28:53,720 --> 00:28:59,380 yksi näistä ajatuksista, että olen on on niin huono, että se on 536 00:28:59,380 --> 00:29:02,280 ei harkitsemisen arvoinen kaikki mahdolliset keinot 537 00:29:02,280 --> 00:29:06,680 että asiat voivat mennä huonompaan suuntaan. 538 00:29:06,680 --> 00:29:12,760 Voit tehdä, että me lisäämme osaksi minimax periaate kutsutaan alph-beeta. 539 00:29:12,760 --> 00:29:16,340 Ja alfa-beeta sanoo, jos sinulla on huono idea, 540 00:29:16,340 --> 00:29:22,840 älä tuhlaa aikaa yrittää selvittää tarkasti, kuinka huono se on. 541 00:29:22,840 --> 00:29:24,990 >> Joten tässä mitä aiomme tehdä. 542 00:29:24,990 --> 00:29:28,620 Aiomme ottaa samaan periaatteita, joita meillä oli ennen, 543 00:29:28,620 --> 00:29:32,200 sama minimax tyyppi haku, vain olemme 544 00:29:32,200 --> 00:29:37,570 menossa seurata, paitsi oloarvojen, että meillä on, mutta me 545 00:29:37,570 --> 00:29:41,440 seurata mahdollisimman arvo, että voisin saada, 546 00:29:41,440 --> 00:29:45,700 ja pahin mahdollinen lopputulos Voisin olla. 547 00:29:45,700 --> 00:29:50,470 Ja aina pahin mahdollinen asia etsii todennäköistä, 548 00:29:50,470 --> 00:29:52,694 Minä luopua että osa puusta. 549 00:29:52,694 --> 00:29:54,610 Ja en edes vaivaudu katsomalla sitä enää. 550 00:29:54,610 --> 00:29:57,680 551 00:29:57,680 --> 00:30:02,600 >> Selvä, joten kuvitella että aloitamme tällä samalla tarkka peli puu. 552 00:30:02,600 --> 00:30:05,200 Ja nyt aiomme mennä alas, kaikki alas 553 00:30:05,200 --> 00:30:07,200 kyseiseen vasemmassa alakulmassa. 554 00:30:07,200 --> 00:30:11,180 Ja että vasemmassa alakulmassa, me näyttää ja arvioimme tämän hallituksen. 555 00:30:11,180 --> 00:30:15,700 Ehkä se on neljä neljän Ristinolla aluksella, tai ehkä se on shakkilaudalla. 556 00:30:15,700 --> 00:30:18,620 Mutta katsomme sitä, ja arvioimme se, ja saamme arvo kahdeksan. 557 00:30:18,620 --> 00:30:22,290 558 00:30:22,290 --> 00:30:28,030 >> Siinä vaiheessa, me tiedämme, että aiomme saada ainakin 559 00:30:28,030 --> 00:30:32,380 kahdeksan pistettä tästä pohjasta päätöksestä. 560 00:30:32,380 --> 00:30:36,620 Sillä ei ole väliä mitä muut kaksi ovat, että seitsemän ja että kaksi. 561 00:30:36,620 --> 00:30:38,580 Ne voisivat olla mitään arvoja he halusivat olla. 562 00:30:38,580 --> 00:30:41,279 Aiomme saada aikaa vähintään kahdeksan pistettä. 563 00:30:41,279 --> 00:30:43,070 Hyvä on, mutta voisimme mennä eteenpäin ja tarkistaa. 564 00:30:43,070 --> 00:30:45,080 Ehkä yksi niistä on parempi kuin kahdeksan. 565 00:30:45,080 --> 00:30:46,000 >> Katsomme seitsemän. 566 00:30:46,000 --> 00:30:46,910 Onko se parempi kuin kahdeksan? 567 00:30:46,910 --> 00:30:48,680 No, joka ei muutu Mielestämme lainkaan. 568 00:30:48,680 --> 00:30:49,460 Katsomme kaksi. 569 00:30:49,460 --> 00:30:50,543 Onko se parempi kuin kahdeksan? 570 00:30:50,543 --> 00:30:52,580 No, joka ei muutu Mielestämme lainkaan. 571 00:30:52,580 --> 00:30:55,480 Joten nyt me tiedämme, olemme loppuun kaikki mahdollisuudet siellä. 572 00:30:55,480 --> 00:30:58,330 Emme tule saamaan mitään parempaa kuin kahdeksan. 573 00:30:58,330 --> 00:31:01,310 Aiomme saada täsmälleen kahdeksan. 574 00:31:01,310 --> 00:31:03,825 >> Ja niin me muuttaa että solmu ja sanoa, että on nyt varmuus. 575 00:31:03,825 --> 00:31:07,010 576 00:31:07,010 --> 00:31:10,270 Me siirtyä yhden tason yläpuolella. 577 00:31:10,270 --> 00:31:13,820 Ja nyt me tiedämme jotain siitä minimointi tasolla. 578 00:31:13,820 --> 00:31:18,560 Tiedämme, että emme koskaan tule saamaan yli kahdeksan pistettä jos menemme alas 579 00:31:18,560 --> 00:31:20,910 siihen suuntaan. 580 00:31:20,910 --> 00:31:22,980 Sillä vaikka ne muut kaksi haaraa osoittautua 581 00:31:22,980 --> 00:31:26,170 mahtavia ja kannattaa tuhansia pistettä kustakin, 582 00:31:26,170 --> 00:31:31,666 vastustaja antaa meille minimi, ja antaa meille kahdeksan. 583 00:31:31,666 --> 00:31:32,790 Hyvä, hyvin, katsotaanpa. 584 00:31:32,790 --> 00:31:35,190 Me jatkaa tätä tietä. 585 00:31:35,190 --> 00:31:38,490 Menemme alas, että keski vasemmalla. 586 00:31:38,490 --> 00:31:40,560 Odotamme alas ja näemme siellä yhdeksän. 587 00:31:40,560 --> 00:31:45,590 Tiedämme, että aiomme saada vähintään yhdeksän pistettä menemällä alas 588 00:31:45,590 --> 00:31:47,720 että keski tie. 589 00:31:47,720 --> 00:31:52,110 Ja tässä vaiheessa voimme vain keskeyttää. 590 00:31:52,110 --> 00:31:56,910 Ja voimme sanoa, katso, minä tietää yläpuolella, 591 00:31:56,910 --> 00:32:01,160 Aion saada enintään kahdeksan pisteitä menossa tähän suuntaan. 592 00:32:01,160 --> 00:32:05,670 Mutta jos menin keskelle polku sijasta vasemmalle polku, 593 00:32:05,670 --> 00:32:08,980 Haluan saada vähintään yhdeksän pistettä. 594 00:32:08,980 --> 00:32:13,590 >> Vastustajani ei koskaan tule anna minun mennä alas, että keskitietä. 595 00:32:13,590 --> 00:32:14,650 He saavat valita. 596 00:32:14,650 --> 00:32:18,140 Ja he aikovat valita polku vasemmalle kohti kahdeksan, 597 00:32:18,140 --> 00:32:23,650 pikemminkin kuin keskeltä kohti mitä ainakin yhdeksän pistettä. 598 00:32:23,650 --> 00:32:25,334 Niin siinä vaiheessa, minä lopetan. 599 00:32:25,334 --> 00:32:26,500 Ja minä sanon, tiedätkö mitä? 600 00:32:26,500 --> 00:32:29,990 Minulla ei tarvitse etsiä enemmän alas tähän suuntaan. 601 00:32:29,990 --> 00:32:32,270 Koska olen koskaan päästä sinne. 602 00:32:32,270 --> 00:32:36,660 >> Voin ohittaa että yksi, ja voin ohittaa että kuusi, 603 00:32:36,660 --> 00:32:39,720 koska se ei koskaan tule tapahtumaan. 604 00:32:39,720 --> 00:32:42,470 Joten menen alas ja minä harkita seuraavaksi mahdollisuutta. 605 00:32:42,470 --> 00:32:44,830 Menen sinne ja sanon, näen kaksi. 606 00:32:44,830 --> 00:32:47,125 Tiedän jos saan tänne, olen menossa ainakin kaksi. 607 00:32:47,125 --> 00:32:49,810 608 00:32:49,810 --> 00:32:50,470 OK. 609 00:32:50,470 --> 00:32:51,520 En jatka. 610 00:32:51,520 --> 00:32:52,440 Näen neljä. 611 00:32:52,440 --> 00:32:54,920 Tiedän, että olen menossa saada vähintään neljä. 612 00:32:54,920 --> 00:32:57,200 Siellä on vielä paljon välillä neljä ja kahdeksan, vaikka. 613 00:32:57,200 --> 00:32:58,454 Joten en jatka. 614 00:32:58,454 --> 00:32:59,870 Odotan alas ja näen siellä on yksi. 615 00:32:59,870 --> 00:33:01,614 Hyvä on, tiedän jos Menen tätä tietä, 616 00:33:01,614 --> 00:33:03,280 Aion olla mahdollisuus valita neljä. 617 00:33:03,280 --> 00:33:06,540 618 00:33:06,540 --> 00:33:08,980 Mitä minun vastustaja aikoo tehdä? 619 00:33:08,980 --> 00:33:12,310 Välillä jotain, joka antaa minulle kahdeksan, mikä antaa minulle neljä, 620 00:33:12,310 --> 00:33:14,730 ja jotain, antaa minulle ainakin yhdeksän, 621 00:33:14,730 --> 00:33:17,550 hyvin, hän aikoo antaa minulle neljä. 622 00:33:17,550 --> 00:33:20,110 Ja tiedän nyt hyvin alkuun, aion 623 00:33:20,110 --> 00:33:23,145 voitava saada vähintään neljä pistettä tästä pelistä. 624 00:33:23,145 --> 00:33:27,030 625 00:33:27,030 --> 00:33:30,900 >> Koko ajatus alfa-beeta on katkaista osiin puun niin 626 00:33:30,900 --> 00:33:32,530 että en katso niitä enää. 627 00:33:32,530 --> 00:33:35,964 Mutta se näyttää vielä olen ollut katsot paljon puu. 628 00:33:35,964 --> 00:33:36,880 Pidetään menossa alaspäin. 629 00:33:36,880 --> 00:33:38,305 Menemme alas seuraavaan nyt. 630 00:33:38,305 --> 00:33:39,680 Alas alareunassa, saan yhden. 631 00:33:39,680 --> 00:33:41,030 Tiedän, että olen menossa saada ainakin yksi. 632 00:33:41,030 --> 00:33:41,690 En jatka etsimistä. 633 00:33:41,690 --> 00:33:42,625 >> Minusta kolme. 634 00:33:42,625 --> 00:33:44,250 Tiedän, että olen menossa saada vähintään kolme. 635 00:33:44,250 --> 00:33:44,840 En jatka. 636 00:33:44,840 --> 00:33:45,660 Minusta viisi. 637 00:33:45,660 --> 00:33:49,760 Tiedän, että olen menossa saada viisi jos saan alas tätä tietä. 638 00:33:49,760 --> 00:33:52,580 Ja tiedän myös sitten että minun vastustaja, jos en 639 00:33:52,580 --> 00:33:55,510 valita keskellä kolme isoa valintoja, 640 00:33:55,510 --> 00:34:01,440 hän aikoo antaa minulle jotain, joka on viisi tai vähemmän. 641 00:34:01,440 --> 00:34:02,150 >> OK. 642 00:34:02,150 --> 00:34:03,400 Voin jatkaa siellä. 643 00:34:03,400 --> 00:34:06,470 Voin katsoa alas ja minä voi sanoa, mitä olen menossa 644 00:34:06,470 --> 00:34:08,239 saada jos menen alas keskitietä? 645 00:34:08,239 --> 00:34:09,909 Aion saada, hyvin, kolme siellä. 646 00:34:09,909 --> 00:34:12,080 Aion saada jotain se on ainakin kolme. 647 00:34:12,080 --> 00:34:16,030 Vielä asioita välillä kolme ja viisi, joten en jatka etsimistä. 648 00:34:16,030 --> 00:34:20,203 Voi, yhdeksän, minä ehdottomasti ottaa että yli kolme. 649 00:34:20,203 --> 00:34:22,744 Aion saada vähintään yhdeksän jos menen alas että keskitietä. 650 00:34:22,744 --> 00:34:25,530 651 00:34:25,530 --> 00:34:31,010 >> Nyt minun vastustaja pysähtyy ja sanoo, katso, ei ole mitään järkeä enää. 652 00:34:31,010 --> 00:34:33,669 Tiedän, että minun minimointi vastustaja, hän 653 00:34:33,669 --> 00:34:36,210 aio antaa minulle asia, joka on vähemmän kuin tai yhtä suuri kuin viisi, 654 00:34:36,210 --> 00:34:39,030 eikä asia, joka on suurempi tai yhtä suuri kuin yhdeksän. 655 00:34:39,030 --> 00:34:39,530 Lopetan. 656 00:34:39,530 --> 00:34:40,779 En katso enää tuohon. 657 00:34:40,779 --> 00:34:43,280 En jatka. 658 00:34:43,280 --> 00:34:44,850 >> Olen halveksia tämä. 659 00:34:44,850 --> 00:34:46,370 Pohjaan, saan kuusi. 660 00:34:46,370 --> 00:34:50,040 Tiedän, että olen menossa saada vähintään kuusi. 661 00:34:50,040 --> 00:34:53,130 Ja mitä voin tehdä? 662 00:34:53,130 --> 00:34:54,877 Voin lopettaa. 663 00:34:54,877 --> 00:34:57,460 Koska siellä valita jotain, joka on vähintään kuusi 664 00:34:57,460 --> 00:34:59,250 ja jotain, joka on vähemmän kuin viisi, hän 665 00:34:59,250 --> 00:35:02,570 aio antaa minulle asia se on vähemmän kuin viisi. 666 00:35:02,570 --> 00:35:04,779 Ja nyt tiedän aion saada juuri tämä valinta. 667 00:35:04,779 --> 00:35:06,195 Aion saada että viisi valinta. 668 00:35:06,195 --> 00:35:08,980 669 00:35:08,980 --> 00:35:10,010 >> Menen takaisin ylös. 670 00:35:10,010 --> 00:35:11,450 Joka olen menossa valita jotain 671 00:35:11,450 --> 00:35:14,449 joka on suurempi tai yhtä suuri kuin neljä, tai jotain, joka on yhtä kuin viisi? 672 00:35:14,449 --> 00:35:17,140 Aion tehdä jotain se on vähintään viisi. 673 00:35:17,140 --> 00:35:20,490 Menen alas viime polku, kaikki alas pohjaan. 674 00:35:20,490 --> 00:35:21,260 Siellä on yksi. 675 00:35:21,260 --> 00:35:23,410 OK, ainakin aion saada yhden pisteen. 676 00:35:23,410 --> 00:35:24,427 En jatka. 677 00:35:24,427 --> 00:35:25,760 Kaksi, oi, se on parempi kuin yksi. 678 00:35:25,760 --> 00:35:27,100 Aion saada vähintään kaksi. 679 00:35:27,100 --> 00:35:28,610 Minusta kolme. 680 00:35:28,610 --> 00:35:31,450 Tiedän, että olen menossa kolme. 681 00:35:31,450 --> 00:35:34,690 >> Ja pisteen yläpuolella, vastustajani on menossa 682 00:35:34,690 --> 00:35:38,540 antaa minulle jotain, joka on vähemmän kuin tai yhtä suuri kuin kolme. 683 00:35:38,540 --> 00:35:40,940 Ja nyt voin lopettaa. 684 00:35:40,940 --> 00:35:46,290 Koska valita minulle on voi saada viisi ja vastustajani 685 00:35:46,290 --> 00:35:52,290 antaa minulle jotain vähemmän kuin kolme, Olen aina menossa ottamaan että viisi. 686 00:35:52,290 --> 00:35:56,810 Joten en arvioi, että alaosassa puun ollenkaan. 687 00:35:56,810 --> 00:35:59,470 >> Nyt tämä voi tuntua pieniä. 688 00:35:59,470 --> 00:36:03,630 Mutta kun vähän bittiä aritmeettinen, suurempi ja pienempi kuin, 689 00:36:03,630 --> 00:36:10,640 voi leikata pois koko osat tämä eksponentiaalisesti kasvava puu, 690 00:36:10,640 --> 00:36:14,280 joka johtaa valtavan Säästöistä, säästöt 691 00:36:14,280 --> 00:36:17,630 jotka ovat tarpeeksi suuria, että minä voit aloittaa pelaamisen kilpailukykyisesti 692 00:36:17,630 --> 00:36:21,330 klo monimutkaisempia pelejä. 693 00:36:21,330 --> 00:36:27,030 >> Hyvä on, jos katsomme koko ja monimutkaisuus erilaisia ​​pelejä, 694 00:36:27,030 --> 00:36:29,470 Ristinolla oli meidän helppo esimerkki. 695 00:36:29,470 --> 00:36:32,150 Meillä pieni lauta, kolme kolme. 696 00:36:32,150 --> 00:36:36,030 Saamme korkeintaan keskimäärin noin neljä eri vaihtoehtoa 697 00:36:36,030 --> 00:36:38,440 kun käymme läpi pelin. 698 00:36:38,440 --> 00:36:42,720 Meillä on jonnekin noin 10 Viides mahdollinen eri lehtiä. 699 00:36:42,720 --> 00:36:45,200 Ja rakentaa Ristinolla soitin, hyvin, me vain teimme sen. 700 00:36:45,200 --> 00:36:47,460 Se on helppoa. 701 00:36:47,460 --> 00:36:49,890 >> Jos menemme jopa jotain enemmän monimutkainen, kuten Connect Four. 702 00:36:49,890 --> 00:36:53,170 Muistatko tämän peli, jossa pudotat pikku tokens? 703 00:36:53,170 --> 00:36:58,490 Se on kuusi seitsemän aluksella, ei niin paljon isompi, edelleen 704 00:36:58,490 --> 00:37:00,770 on suunnilleen sama haaroitus tekijä kuten Ristinolla. 705 00:37:00,770 --> 00:37:05,410 Olen noin neljä vaihtoehtoa jossa voin laittaa asiat. 706 00:37:05,410 --> 00:37:10,760 Mutta nyt, minulla on paljon enemmän johtaa, 10 21. valtaa. 707 00:37:10,760 --> 00:37:14,440 Se on jotain, joka on helppo riitä, että ratkaisemme sen heti. 708 00:37:14,440 --> 00:37:17,560 >> Nappuloita, enemmän complex-- sinua sai kahdeksan kahdeksan aluksella. 709 00:37:17,560 --> 00:37:20,570 Olet vain puolet milloin tahansa, vaikka. 710 00:37:20,570 --> 00:37:24,930 Sinulla haarautuvan tekijä, joka on noin 2,8. 711 00:37:24,930 --> 00:37:28,160 No, meillä pari liikkuu voit ottaa. 712 00:37:28,160 --> 00:37:33,870 Sinulla noin 10 31. lehdet, suurempi, ja suurempi, ja suurempia tiloja. 713 00:37:33,870 --> 00:37:37,340 Koska minulla on etsiä ne suurempia ja suurempia tiloja, 714 00:37:37,340 --> 00:37:42,220 silloin asiat kuten alfa-beeta ja että voimme leikata pois koko oksat 715 00:37:42,220 --> 00:37:44,420 tulee olennainen. 716 00:37:44,420 --> 00:37:47,440 >> Nyt, Tammi oli helppoa vuonna 1992. 717 00:37:47,440 --> 00:37:51,400 Tietokoneohjelma nimeltään Chinook voittaa maailman nappuloita 718 00:37:51,400 --> 00:37:53,590 mestari, Marion Tinsley. 719 00:37:53,590 --> 00:37:57,260 Ja sen jälkeen, ei ihmisjohtajan pelaajalla on 720 00:37:57,260 --> 00:38:02,290 pystynyt voittamaan paras laskennallisen systeemibiologian. 721 00:38:02,290 --> 00:38:06,570 Jos tarkastelemme jotain shakki, nyt taas, meillä on kahdeksan kahdeksan aluksella. 722 00:38:06,570 --> 00:38:09,870 Mutta meillä on paljon monimutkaisempi kappaletta, paljon monimutkaisia ​​liikkeitä. 723 00:38:09,870 --> 00:38:14,610 Meillä haarautumiskerroin noin 35, 35 mahdollista siirtoa keskimäärin 724 00:38:14,610 --> 00:38:20,030 että voin ottaa, ja valtio tilaa, lehtien lukumäärä 725 00:38:20,030 --> 00:38:28,950 joka on kasvanut 10 123. valtaa, valtavan määrän mahdollisuuksia. 726 00:38:28,950 --> 00:38:35,570 >> Jopa vielä, nykyaikaiset prosessorit pystyvät tekemään tämän menestyksekkäästi. 727 00:38:35,570 --> 00:38:43,900 Vuonna 1995 ja sen jälkeen vuonna 1997, tietokone ohjelma nimeltä Deep Blue rakennettu IBM 728 00:38:43,900 --> 00:38:49,601 että sai pitkän jättiläinen supertietokoneen lyödä nykyinen maailmanmestari, 729 00:38:49,601 --> 00:38:50,225 Garri Kasparov. 730 00:38:50,225 --> 00:38:54,000 731 00:38:54,000 --> 00:38:56,650 Tämä oli käännekohta. 732 00:38:56,650 --> 00:39:00,620 Tänään, kuitenkin, että sama käsittely teho istuu MacBook. 733 00:39:00,620 --> 00:39:04,180 734 00:39:04,180 --> 00:39:06,440 >> Käsittelyn nopeus pitää saada nopeammin ja nopeammin. 735 00:39:06,440 --> 00:39:09,500 Voimme arvioida enemmän ja enemmän levyt nopeammin ja nopeammin. 736 00:39:09,500 --> 00:39:14,550 Mutta vielä tärkeämpää, olemme parempi arviointi toiminnot ja parempi karsimisesta 737 00:39:14,550 --> 00:39:15,460 menetelmiä. 738 00:39:15,460 --> 00:39:19,560 Jotta voimme etsiä tilaa lisää monimutkaisesti. 739 00:39:19,560 --> 00:39:22,350 Suurin Hallituksen pelejä, että voimme ajatella, 740 00:39:22,350 --> 00:39:26,310 jotain Go, joka on sai 19 19 aluksella, 741 00:39:26,310 --> 00:39:32,490 nyt yhtäkkiä, olemme ohi pisteen jossa laskennallinen järjestelmät voivat voittaa. 742 00:39:32,490 --> 00:39:34,530 Ei ole laskennallinen järjestelmä siellä 743 00:39:34,530 --> 00:39:38,880 joka voi voittaa ammatillinen Go pelaaja. 744 00:39:38,880 --> 00:39:45,000 Paras järjestelmät tänään listalla kyse eräänlainen hyvä amatööri tasolla. 745 00:39:45,000 --> 00:39:49,285 Joten siellä on vielä melko vähän ulos siellä, että et voi saada vielä. 746 00:39:49,285 --> 00:39:51,840 747 00:39:51,840 --> 00:39:55,360 >> Hyvä, nämä perinteisiä lautapelejä, 748 00:39:55,360 --> 00:39:58,560 tällaisia ​​järjestelmiä, joissa me rakentaa tämän minimax, onko se sai 749 00:39:58,560 --> 00:40:06,300 alfa-beeta- tai ei, nämä algoritmit koska on olemassa tiettyjä rajoituksia. 750 00:40:06,300 --> 00:40:08,520 Meillä on täydellinen tietoa maailmasta. 751 00:40:08,520 --> 00:40:11,690 Tiedämme missä kaikki palaset ovat. 752 00:40:11,690 --> 00:40:13,570 Maailma on staattinen. 753 00:40:13,570 --> 00:40:16,220 Kukaan ei pääse liikkumaan kappaletta ympäri kun olen 754 00:40:16,220 --> 00:40:20,640 istuu siellä ajattelu, kun minun vuoroni. 755 00:40:20,640 --> 00:40:23,140 On toimintatilaa, joka on diskreetti. 756 00:40:23,140 --> 00:40:26,900 Voin laittaa pelinappula täällä, tai voin laittaa pelinappula tässä. 757 00:40:26,900 --> 00:40:30,520 En saa laittaa sotilas linjan välillä kaksi ruutua. 758 00:40:30,520 --> 00:40:34,430 759 00:40:34,430 --> 00:40:36,520 >> Ja lopuksi, toimien deterministisiä. 760 00:40:36,520 --> 00:40:39,790 Tiedän, että jos sanon, torni Knight kolme, 761 00:40:39,790 --> 00:40:44,660 minun torni on menossa päätyä ritari kolme, kunhan se on voimassa liikkua. 762 00:40:44,660 --> 00:40:47,830 Ei ole epävarmuutta siitä. 763 00:40:47,830 --> 00:40:52,490 Nyt, kun menen enemmän erilaisia ​​pelejä, 764 00:40:52,490 --> 00:40:55,960 meillä on rikkoa näistä oletuksista. 765 00:40:55,960 --> 00:41:00,020 >> Mitä jos menen jotain kuten klassinen videopelit? 766 00:41:00,020 --> 00:41:04,180 Tässä valikoima video pelejä Atari 2600. 767 00:41:04,180 --> 00:41:05,180 Mitä minulla on siellä? 768 00:41:05,180 --> 00:41:08,440 Minulla Frogger, Space Hyökkääjät, Pitfall, ja Pac-Man. 769 00:41:08,440 --> 00:41:11,290 770 00:41:11,290 --> 00:41:14,840 Millaisia ​​ympäristöjä minulla on täällä nyt? 771 00:41:14,840 --> 00:41:16,900 Mikä näistä oletuksista minun täytyy rikkoa? 772 00:41:16,900 --> 00:41:19,410 773 00:41:19,410 --> 00:41:21,570 >> No, se riippuu pelistä. 774 00:41:21,570 --> 00:41:28,170 Voisin pelata shakki 2600, ja se olisi aivan kuin se oli ennen. 775 00:41:28,170 --> 00:41:33,020 Useimpien näistä järjestelmistä, siellä täydellinen tietoa maailmasta. 776 00:41:33,020 --> 00:41:36,300 On täysin deterministinen toimia. 777 00:41:36,300 --> 00:41:38,330 Mutta yleensä, maailman ei enää staattisia. 778 00:41:38,330 --> 00:41:41,970 Eli kun istun siellä odottaa, jotain liikkuu. 779 00:41:41,970 --> 00:41:44,320 Aaveet ovat tulossa hakemaan minua. 780 00:41:44,320 --> 00:41:46,570 Skorpioni seuraa minua alla. 781 00:41:46,570 --> 00:41:48,880 Space Invaders ovat tulossa lähemmäs ja lähemmäs. 782 00:41:48,880 --> 00:41:54,020 783 00:41:54,020 --> 00:41:55,510 Kuinka hyvin voimme tehdä näitä? 784 00:41:55,510 --> 00:41:58,640 785 00:41:58,640 --> 00:42:02,790 >> Muutama vuosi sitten, Google oli projektin nimeltään 786 00:42:02,790 --> 00:42:12,030 DeepMind, jossa he koulutettu tietokone ohjelma pelata Atari 2600 pelejä. 787 00:42:12,030 --> 00:42:16,120 Ja jos luulet tämä ei ole vakava liiketoiminta, tulokset niiden tutkimuksen 788 00:42:16,120 --> 00:42:19,920 julkaistiin Nature, joten lähes yhtä hyvä julkaisu 789 00:42:19,920 --> 00:42:22,500 kuin voit mahdollisesti saada. 790 00:42:22,500 --> 00:42:24,340 Ja tässä miten hyvin he esiintyivät. 791 00:42:24,340 --> 00:42:29,220 >> Heillä on algoritmi, joka istui ja katseli vain näytön tuloa. 792 00:42:29,220 --> 00:42:34,080 Se sai mitään ohjeita lainkaan noin pelisäännöt. 793 00:42:34,080 --> 00:42:42,610 Ja se piti selvittää, perustanut pisteet, miten hyvin se oli tekemässä. 794 00:42:42,610 --> 00:42:46,560 Tämä oli järjestelmä, joka käyttää jotain nimeltään vahvistaminen oppiminen. 795 00:42:46,560 --> 00:42:48,380 Eli, se katsoi sen pisteet. 796 00:42:48,380 --> 00:42:51,620 Ja jos se sai hyvät pisteet, se sanoi, Haluan muistaa nuo asiat. 797 00:42:51,620 --> 00:42:53,310 Ja minun pitäisi tehdä niitä uudestaan. 798 00:42:53,310 --> 00:42:56,450 Ja jos se sai huonon sijoituksen, se sanoi, Minun ei pitäisi tehdä niitä asioita uudelleen. 799 00:42:56,450 --> 00:42:59,750 800 00:42:59,750 --> 00:43:03,430 >> Tämä on suorituskyvyn näistä koulutettu järjestelmien 801 00:43:03,430 --> 00:43:07,490 saa pelata muutaman tunnin jokaista peliä, 802 00:43:07,490 --> 00:43:12,490 verrattiin ammatillinen pelaajille. 803 00:43:12,490 --> 00:43:19,670 Joten kaikki pelejä, jotka ovat vasemmalle puolelle tätä linjaa, 804 00:43:19,670 --> 00:43:25,920 Tämä itse koulutettu tietokoneohjelma päihitti ammatillinen pelaajille. 805 00:43:25,920 --> 00:43:29,690 Ja kaiken oikeus, ammatillinen pelaajat 806 00:43:29,690 --> 00:43:30,920 olivat edelleen paras. 807 00:43:30,920 --> 00:43:34,040 808 00:43:34,040 --> 00:43:36,850 Jotain, joka tiesi mitään sääntöjä, että 809 00:43:36,850 --> 00:43:43,020 tiennyt mitään rakennetta pelejä, tämä on vaikuttava suorituskyky. 810 00:43:43,020 --> 00:43:45,660 Ja tämä on mitä pystymme tekemään tänään. 811 00:43:45,660 --> 00:43:50,239 >> OK, te sanotte, mutta jos me ajatella AI peleissä, 812 00:43:50,239 --> 00:43:52,530 normaalisti ajattelemme asioita, joita voimme todella 813 00:43:52,530 --> 00:43:54,180 istua alas ja pelata. 814 00:43:54,180 --> 00:43:58,760 Jos istun ja pelaan StarCraft, tai pelaan Ilmainen seula, 815 00:43:58,760 --> 00:44:01,870 tietokone vastustaja on jolla on määräysvalta Zerg, 816 00:44:01,870 --> 00:44:06,770 tai ohjaamalla muita sivilisaation. 817 00:44:06,770 --> 00:44:11,920 Miten nämä pelaajat itse löytää siirtonsa? 818 00:44:11,920 --> 00:44:18,810 >> No, nämä pelit ovat rakenteeltaan paljon samalla tavalla kuin meidän lautapelejä, 819 00:44:18,810 --> 00:44:22,250 nämä pelit, että me will kollektiivisesti soittaa neljä X pelejä, 820 00:44:22,250 --> 00:44:26,040 tutkia, expand-- unohtaa niitä. 821 00:44:26,040 --> 00:44:26,980 Mitä he ovat? 822 00:44:26,980 --> 00:44:32,150 Tutki, laajentaa, ja sammuttaa, Mielestäni on viimeinen. 823 00:44:32,150 --> 00:44:36,060 Mutta ne ovat pohjimmiltaan etsintä ja valloittaa pelejä. 824 00:44:36,060 --> 00:44:41,020 Tyypillisesti tietokone vastustaja siellä on rajoitetusti tietoa. 825 00:44:41,020 --> 00:44:45,486 He eivät tiedä tarkalleen, mitä takana tapahtuu, että sumu sodan. 826 00:44:45,486 --> 00:44:47,735 He eivät saa nähdä, mitä sinulla on inventaario. 827 00:44:47,735 --> 00:44:50,240 828 00:44:50,240 --> 00:44:52,800 >> On ympäristössä, joka on dynaaminen. 829 00:44:52,800 --> 00:44:56,180 Kaikki muuttuu koko ajan. 830 00:44:56,180 --> 00:45:00,290 Et saa istua ja odota ottaa liikkua. 831 00:45:00,290 --> 00:45:02,810 Mutta useimmat asiat ovat edelleen erillisiä. 832 00:45:02,810 --> 00:45:04,200 Minun täytyy laittaa kaupungin täällä. 833 00:45:04,200 --> 00:45:06,750 Tai minun täytyy laittaa kotikaupungissani täällä. 834 00:45:06,750 --> 00:45:08,950 Ja kaikki on deterministinen. 835 00:45:08,950 --> 00:45:14,660 Kun sanon, siirrän yksikkö täällä, minun yksikkö liikkuu täällä, ellei esteenä yhtäkkiä 836 00:45:14,660 --> 00:45:17,700 tulee pelata. 837 00:45:17,700 --> 00:45:21,610 Nyt, se ei ole kaikki tietokoneen pelejä, jotka ovat siellä tänään. 838 00:45:21,610 --> 00:45:27,320 >> Jos menen ja pelaan ensimmäinen henkilö tyyppi peli, jotain Thief tai Fallout 839 00:45:27,320 --> 00:45:33,350 tai Skyrim, tai halo, nyt Minulla on tietokone vastustajat 840 00:45:33,350 --> 00:45:37,860 jotka ovat siellä, jotka ovat hyvin erilainen tilanne. 841 00:45:37,860 --> 00:45:40,020 Heillä on jälleen rajoitetusti tietoa. 842 00:45:40,020 --> 00:45:43,420 He vain voi nähdä tietyt näkökenttä. 843 00:45:43,420 --> 00:45:45,180 Ympäristö on edelleen dynaaminen. 844 00:45:45,180 --> 00:45:48,280 Asiat muuttuvat koko ajan. 845 00:45:48,280 --> 00:45:52,300 >> Mutta nyt minulla on paljon enemmän jatkuvia toimia tilaa. 846 00:45:52,300 --> 00:45:57,170 Voin olla vain kurkistaa hieman ulos oviaukosta. 847 00:45:57,170 --> 00:46:00,650 Ja joitakin pelejä, minun toimet ovat stokastisia. 848 00:46:00,650 --> 00:46:04,590 Saan yrittää hypätä yli että seinä, mutta minulla on mahdollisuus epäonnistua. 849 00:46:04,590 --> 00:46:08,280 850 00:46:08,280 --> 00:46:14,550 Tämäntyyppiset pelit lähestyvät ja lähempänä erilaisia ​​ohjaimia 851 00:46:14,550 --> 00:46:17,330 että rakennamme robotiikka. 852 00:46:17,330 --> 00:46:21,050 >> Robotiikka, meidän on oletettava, että meillä on vain vähän tietoa. 853 00:46:21,050 --> 00:46:23,070 Meillä on anturit, jotka kertovat maailmasta. 854 00:46:23,070 --> 00:46:25,860 Meillä on aina muuttuvassa, dynaamisessa ympäristössä. 855 00:46:25,860 --> 00:46:30,440 Meillä on maailma, jossa tila on jatkuvaa, eikä erillisiä. 856 00:46:30,440 --> 00:46:36,260 Ja tekomme, kun yritämme heille, on mahdollisuus epäonnistua. 857 00:46:36,260 --> 00:46:40,960 Ja itse asiassa, moderni peli säätimet oman Halo vastustaja, 858 00:46:40,960 --> 00:46:48,690 tai niille Yhteyshenkilö Skyrim, pohjimmiltaan tavallista pienempiä robotiikka arkkitehtuurit. 859 00:46:48,690 --> 00:46:50,380 >> He aistivat maailman. 860 00:46:50,380 --> 00:46:52,910 Ne rakentaa malli maailman. 861 00:46:52,910 --> 00:46:57,950 He Laske perustuu joukko tavoitteet, jotka he haluaisivat saavuttaa. 862 00:46:57,950 --> 00:47:03,110 He suunnittelevat perustuvat kanteet mitä he tietävät. 863 00:47:03,110 --> 00:47:07,940 Ja ne ovat täsmälleen samanlaisia Järjestelmien että rakennamme robotiikka. 864 00:47:07,940 --> 00:47:11,420 Joten nämä arkkitehtuurit, jotta tuoda tämän takaisin yhteen, 865 00:47:11,420 --> 00:47:14,500 ovat usein aivan sama. 866 00:47:14,500 --> 00:47:16,340 >> Joten jos voimme nähdä, että. 867 00:47:16,340 --> 00:47:19,210 Mennään takaisin meidän Ristinolla esimerkki. 868 00:47:19,210 --> 00:47:22,690 Ja minä aion kysyä pari minun post-docs keksiä ja auttamaan minua. 869 00:47:22,690 --> 00:47:26,970 Joten Chen Ming, ja Alessandro, ja Olivier, jos te voisi keksiä. 870 00:47:26,970 --> 00:47:32,080 871 00:47:32,080 --> 00:47:35,440 Ja aion pitää pari vapaaehtoisten 872 00:47:35,440 --> 00:47:37,590 >> OK, minä näin käsi ylös oikealle siellä keskellä. 873 00:47:37,590 --> 00:47:39,965 Otan yhden, joku edelleen takana ehkä. 874 00:47:39,965 --> 00:47:40,881 Okei, tuolla. 875 00:47:40,881 --> 00:47:41,490 Tule ylös. 876 00:47:41,490 --> 00:47:44,190 877 00:47:44,190 --> 00:47:45,335 Selvä. 878 00:47:45,335 --> 00:47:49,490 Joten ottakaamme että kansi alas. 879 00:47:49,490 --> 00:48:03,700 Ja jos kaverit tulevat heti takaisin täällä minulle, fantastinen. 880 00:48:03,700 --> 00:48:06,580 >> Joten tämä on robotti nimeltään Baxter. 881 00:48:06,580 --> 00:48:10,880 Ja Baxter on robotti, joka on kaupallinen foorumi, jonka tarkoituksena 882 00:48:10,880 --> 00:48:13,030 niminen yhtiö Rethink. 883 00:48:13,030 --> 00:48:16,580 Ja tämä robotti on suunniteltu pienimuotoista valmistus. 884 00:48:16,580 --> 00:48:19,265 Mutta tänään emme aio käyttää sitä pelata Ristinolla. 885 00:48:19,265 --> 00:48:21,930 886 00:48:21,930 --> 00:48:27,150 Nyt, tämä robotti on myös jotain se on melko ainutlaatuinen. 887 00:48:27,150 --> 00:48:32,950 Koska jos en seisoisi tahansa lähellä standardi tehtaan automaatio 888 00:48:32,950 --> 00:48:39,580 järjestelmä, olisin erittäin vakava vaarassa loukkaantua. 889 00:48:39,580 --> 00:48:45,600 >> Baxter, kuitenkin, on suunniteltu suhteellisen turvallista vuorovaikutuksessa. 890 00:48:45,600 --> 00:48:48,680 Ja niin minä voi työntää tämän robotti. 891 00:48:48,680 --> 00:48:52,350 Ja näet se on vähän bittinen joustava kuin se liikkuu. 892 00:48:52,350 --> 00:48:57,250 Ja voin asemoida sitä jossa Haluaisin sen mennä. 893 00:48:57,250 --> 00:49:03,410 Nyt normaalissa robottijärjestelmän, meillä olisi joukko nivelten täällä 894 00:49:03,410 --> 00:49:07,970 että olisi suoraan vastaa asentoon komentoja. 895 00:49:07,970 --> 00:49:13,180 Ja he eivät välttämättä välitä jos ne liikkuvat läpi ulkoilmaan, 896 00:49:13,180 --> 00:49:15,555 tai jos ne liikkuvat läpi minun rintakehä. 897 00:49:15,555 --> 00:49:18,410 898 00:49:18,410 --> 00:49:19,120 >> OK. 899 00:49:19,120 --> 00:49:22,090 Ja tyypillisesti, jos olisit täällä teollisen järjestelmän, 900 00:49:22,090 --> 00:49:23,400 menisit läheskään sitä. 901 00:49:23,400 --> 00:49:26,280 Olisi keltainen turvallisuus nauha kaikki sen ympärillä. 902 00:49:26,280 --> 00:49:28,310 Tämä järjestelmä on hieman erilainen muotoilu 903 00:49:28,310 --> 00:49:32,130 olla ystävällisempi ja helpompi ihmisten vuorovaikutuksessa, 904 00:49:32,130 --> 00:49:36,380 että kussakin yhteinen, siellä keväällä. 905 00:49:36,380 --> 00:49:39,110 Ja eivätkä hallitse tarkan sijainnin, 906 00:49:39,110 --> 00:49:43,110 me ohjata tietyn määrän vääntömomentti, tietty määrä voimaa, 907 00:49:43,110 --> 00:49:45,874 että haluaisimme olla, että kevät. 908 00:49:45,874 --> 00:49:47,790 Hyvä on, joten haluaisin otamme Vapaaehtoiset. 909 00:49:47,790 --> 00:49:48,540 Hei mikä nimesi on? 910 00:49:48,540 --> 00:49:49,010 >> Yleisö: Louis. 911 00:49:49,010 --> 00:49:49,635 >> SPEAKER: Louis. 912 00:49:49,635 --> 00:49:50,490 Mukava nähdä sinua. 913 00:49:50,490 --> 00:49:50,990 Ja? 914 00:49:50,990 --> 00:49:51,610 >> Yleisö: David. 915 00:49:51,610 --> 00:49:51,960 >> SPEAKER: David. 916 00:49:51,960 --> 00:49:52,550 Kiva tavata. 917 00:49:52,550 --> 00:49:54,508 Jos kaverit odottaa täällä toista, 918 00:49:54,508 --> 00:49:56,420 Aion antaa teille mahdollisuus tehdä tämä. 919 00:49:56,420 --> 00:50:00,610 Joten tämä robotti, jos keksitte ja jos painat sitä kevyesti, 920 00:50:00,610 --> 00:50:03,780 aiot nähdä, että se liikkuu vähän. 921 00:50:03,780 --> 00:50:06,349 Ja jos napata se oikea tässä ranteessa vain 922 00:50:06,349 --> 00:50:09,390 yläpuolella, jossa nämä painikkeet ovat, se näyttää sinun pitäisi napata painikkeet, 923 00:50:09,390 --> 00:50:13,100 mutta napata oikea yläpuolella Siksi sinun pystyä hyvin varovasti manipuloida sitä 924 00:50:13,100 --> 00:50:14,545 avaruudessa. 925 00:50:14,545 --> 00:50:15,920 Louis, haluat antaa sille yrittää? 926 00:50:15,920 --> 00:50:19,465 Joten antaa sille vain vähän push aloittaa. 927 00:50:19,465 --> 00:50:23,190 Ja sitten jos laitat sormet oikeassa ja pitää kiinni siitä, 928 00:50:23,190 --> 00:50:24,807 koska se siirtyy sinulle sitten. 929 00:50:24,807 --> 00:50:27,824 930 00:50:27,824 --> 00:50:29,365 Selvä, haluat antaa sille yrittää? 931 00:50:29,365 --> 00:50:29,980 Tule ylös. 932 00:50:29,980 --> 00:50:32,300 Joten antaa se vain lempeä push siellä aloittaa. 933 00:50:32,300 --> 00:50:33,820 Voit tuntea, millaista se on. 934 00:50:33,820 --> 00:50:40,060 Ja sitten jos napata sen oikeassa, voit liikkumaan noin. 935 00:50:40,060 --> 00:50:41,280 >> OK. 936 00:50:41,280 --> 00:50:47,360 Niin tyypillisesti tällainen robotti olisi käytetään pienessä mittakaavassa valmistukseen. 937 00:50:47,360 --> 00:50:50,980 Ja aion siirtää tätä käsivarteen vain alas pois tieltä hieman täällä. 938 00:50:50,980 --> 00:50:55,750 Mutta tänään, aiomme käyttää Sama Ristinolla pelaa järjestelmä 939 00:50:55,750 --> 00:50:59,520 perustuvat minimax että rakensimme aiemmin. 940 00:50:59,520 --> 00:51:00,549 OK? 941 00:51:00,549 --> 00:51:02,340 Joten, te ovat kukin menossa pelaamaan peliä. 942 00:51:02,340 --> 00:51:04,210 Louis, aiot olla ensimmäinen. 943 00:51:04,210 --> 00:51:05,920 Haluan vain pitää tänne toista. 944 00:51:05,920 --> 00:51:10,949 Aion olla seisot oikeus täällä, vain niin jokainen voi nähdä sinua. 945 00:51:10,949 --> 00:51:11,990 Oletteko perustaa täällä? 946 00:51:11,990 --> 00:51:13,120 >> ROBOT: Tervetuloa. 947 00:51:13,120 --> 00:51:15,910 Pelataan Ristinolla. 948 00:51:15,910 --> 00:51:20,860 Älä ymmärrä tunnuksen ennen Sanon, että se on sinun vuorosi. 949 00:51:20,860 --> 00:51:22,050 Aloitan pelin. 950 00:51:22,050 --> 00:51:27,900 951 00:51:27,900 --> 00:51:28,750 Se on minun vuoroni. 952 00:51:28,750 --> 00:51:47,002 953 00:51:47,002 --> 00:51:50,210 SPEAKER: Nyt, jos voisit ottaa yhden nappulat ja mennä eteenpäin ja aseta se. 954 00:51:50,210 --> 00:51:51,446 ROBOT: Se on sinun vuorosi. 955 00:51:51,446 --> 00:51:53,430 [NAURU] 956 00:51:53,430 --> 00:51:54,836 Se on minun vuoroni. 957 00:51:54,836 --> 00:51:56,820 [NAURU] 958 00:51:56,820 --> 00:52:12,196 959 00:52:12,196 --> 00:52:15,680 [NAURU] 960 00:52:15,680 --> 00:52:16,570 On sinun vuorosi. 961 00:52:16,570 --> 00:52:21,397 962 00:52:21,397 --> 00:52:23,688 SPEAKER: Ihmiskunta on teihin täällä, Louis. 963 00:52:23,688 --> 00:52:27,440 964 00:52:27,440 --> 00:52:28,350 >> ROBOT: Se on minun vuoroni. 965 00:52:28,350 --> 00:52:44,810 966 00:52:44,810 --> 00:52:47,015 >> SPEAKER: Niin Baxter onnistuneesti estetty täällä. 967 00:52:47,015 --> 00:52:49,670 968 00:52:49,670 --> 00:52:52,480 >> ROBOT: Se on sinun vuorosi. 969 00:52:52,480 --> 00:52:53,360 Se on minun vuoroni. 970 00:52:53,360 --> 00:53:14,730 971 00:53:14,730 --> 00:53:16,810 On sinun vuorosi. 972 00:53:16,810 --> 00:53:17,760 Se on minun vuoroni. 973 00:53:17,760 --> 00:53:21,330 974 00:53:21,330 --> 00:53:23,830 SPEAKER: Ja me ilmoitamme Baxter loppuun pois sen viimeisen siirron täällä. 975 00:53:23,830 --> 00:53:36,622 976 00:53:36,622 --> 00:53:39,090 >> [NAURU] 977 00:53:39,090 --> 00:53:40,480 >> ROBOT: Se on solmio. 978 00:53:40,480 --> 00:53:42,030 Aion voittaa ensi kerralla. 979 00:53:42,030 --> 00:53:43,365 >> [NAURU] 980 00:53:43,365 --> 00:53:45,210 >> SPEAKER: Hyvä, Kiitoksia, Louis. 981 00:53:45,210 --> 00:53:46,094 Kiitos. 982 00:53:46,094 --> 00:53:46,980 Voit mennä tällä tavalla. 983 00:53:46,980 --> 00:53:49,759 >> ROBOT: aloitan pelin. 984 00:53:49,759 --> 00:53:51,800 SPEAKER: Joten selitän sinulle yksi pieni 985 00:53:51,800 --> 00:53:55,410 hieman ennen saamme rematch täältä. 986 00:53:55,410 --> 00:53:57,200 Mitä tapahtuu? 987 00:53:57,200 --> 00:53:59,430 Joten robotti on kamera ylös tänne. 988 00:53:59,430 --> 00:54:01,330 Ja se etsii alas hallitus. 989 00:54:01,330 --> 00:54:04,470 Ja se näkee onko se sai punaisen O tai sininen 990 00:54:04,470 --> 00:54:10,450 ja valkoinen X. Koska nämä saavat saatettu aluksella, joka on pohjimmiltaan sama tulo 991 00:54:10,450 --> 00:54:13,890 että olisimme lukeminen sisään meidän tietorakenne meidän näytössä. 992 00:54:13,890 --> 00:54:17,290 Se on käynnissä samaan minimax algoritmi olla 993 00:54:17,290 --> 00:54:21,010 löytää mistä aseta hyvä merkki. 994 00:54:21,010 --> 00:54:24,820 >> Ja sitten annamme komento noin jossa haluamme merkki sijoitetaan. 995 00:54:24,820 --> 00:54:26,120 Varsi on muuttamassa pois. 996 00:54:26,120 --> 00:54:31,750 Se käyttää tyhjiö tarttuja soveltaa jotkut imu että puinen pala, 997 00:54:31,750 --> 00:54:35,240 noutaa sen, siirrä sitä oikealle paikka, ja vapauta sitten imu 998 00:54:35,240 --> 00:54:36,950 ja pudota se. 999 00:54:36,950 --> 00:54:38,990 Selvä, olemme menossa antaa se yksi laukaus 1000 00:54:38,990 --> 00:54:40,930 hieman älykkäämpi pelaaja täällä. 1001 00:54:40,930 --> 00:54:42,290 Oletko valmis? 1002 00:54:42,290 --> 00:54:46,150 Hyvä on, jos haluat seistä asti täällä ja antaa a-- osoittautua tällä tavalla 1003 00:54:46,150 --> 00:54:47,955 joten voit nähdä kaikki. 1004 00:54:47,955 --> 00:54:48,830 Ja sitten [kuultavissa]. 1005 00:54:48,830 --> 00:54:49,330 >> ROBOT: Se on minun vuoroni. 1006 00:54:49,330 --> 00:54:50,455 >> SPEAKER: Baxter alkaa. 1007 00:54:50,455 --> 00:55:10,750 1008 00:55:10,750 --> 00:55:11,730 On sinun vuorosi. 1009 00:55:11,730 --> 00:55:16,490 1010 00:55:16,490 --> 00:55:17,520 Se on minun vuoroni. 1011 00:55:17,520 --> 00:55:38,740 1012 00:55:38,740 --> 00:55:39,690 On sinun vuorosi. 1013 00:55:39,690 --> 00:55:46,330 1014 00:55:46,330 --> 00:55:47,165 Se on minun vuoroni. 1015 00:55:47,165 --> 00:56:01,252 1016 00:56:01,252 --> 00:56:06,192 >> [NAURU] 1017 00:56:06,192 --> 00:56:08,542 >> SPEAKER: [WHISPERING] Vain anna hänen mennä eteenpäin ja voittaa. 1018 00:56:08,542 --> 00:56:09,500 ROBOT: Se on sinun vuorosi. 1019 00:56:09,500 --> 00:56:15,099 1020 00:56:15,099 --> 00:56:15,890 SPEAKER: Ei se mitään. 1021 00:56:15,890 --> 00:56:20,390 1022 00:56:20,390 --> 00:56:21,360 >> ROBOT: Se on minun vuoroni. 1023 00:56:21,360 --> 00:56:24,825 1024 00:56:24,825 --> 00:56:26,805 >> [NAURU] 1025 00:56:26,805 --> 00:56:42,650 1026 00:56:42,650 --> 00:56:43,510 >> Minä voitan. 1027 00:56:43,510 --> 00:56:45,620 >> [NAURU] 1028 00:56:45,620 --> 00:56:46,595 >> Aloitan pelin. 1029 00:56:46,595 --> 00:56:48,261 >> SPEAKER: Selvä, kiitos paljon. 1030 00:56:48,261 --> 00:56:50,180 1031 00:56:50,180 --> 00:56:55,590 Hyvä, mielestäni meillä aika yksi erinomainen Ristinolla soitin, 1032 00:56:55,590 --> 00:57:00,490 joku, joka voi laittaa tämä asia ottelu, joka tietää, mitä he tekevät. 1033 00:57:00,490 --> 00:57:03,010 >> [NAURU] 1034 00:57:03,010 --> 00:57:05,560 >> Kuka tulee olemaan meidän mestari täällä? 1035 00:57:05,560 --> 00:57:08,110 Hyvä, ystävillesi vapaaehtoisesti sinua. 1036 00:57:08,110 --> 00:57:11,190 Se riittää minulle. 1037 00:57:11,190 --> 00:57:12,194 Kerro minulle nimesi uudelleen. 1038 00:57:12,194 --> 00:57:12,860 Yleisö: Tamir. 1039 00:57:12,860 --> 00:57:14,193 SPEAKER: Tamir, kiva nähdä sinua. 1040 00:57:14,193 --> 00:57:19,270 Hyvä on, jälleen, aiomme laittaa sinut asti täällä, jotta jokainen voi nähdä sinua. 1041 00:57:19,270 --> 00:57:22,070 Olet meidän edustaja tässä ottelussa nyt. 1042 00:57:22,070 --> 00:57:24,540 Baxter on yksi ja oh ja oh. 1043 00:57:24,540 --> 00:57:26,300 Tai pahoillani, oh ja yksi. 1044 00:57:26,300 --> 00:57:27,490 Ja se on jopa sinua täällä. 1045 00:57:27,490 --> 00:57:29,340 Baxter saavat liikkua ensin, vaikka. 1046 00:57:29,340 --> 00:57:30,435 Niin. 1047 00:57:30,435 --> 00:57:31,310 ROBOT: Se on minun vuoroni. 1048 00:57:31,310 --> 00:57:45,226 1049 00:57:45,226 --> 00:57:48,208 >> [NAURU] 1050 00:57:48,208 --> 00:57:52,720 1051 00:57:52,720 --> 00:57:55,780 >> On sinun vuorosi. 1052 00:57:55,780 --> 00:57:56,845 Se on minun vuoroni. 1053 00:57:56,845 --> 00:58:18,130 1054 00:58:18,130 --> 00:58:18,965 On sinun vuorosi. 1055 00:58:18,965 --> 00:58:28,751 1056 00:58:28,751 --> 00:58:30,248 Se on minun vuoroni. 1057 00:58:30,248 --> 00:58:51,210 1058 00:58:51,210 --> 00:58:52,160 On sinun vuorosi. 1059 00:58:52,160 --> 00:59:00,854 1060 00:59:00,854 --> 00:59:03,365 >> [NAURU] 1061 00:59:03,365 --> 00:59:04,240 ROBOT: Se on minun vuoroni. 1062 00:59:04,240 --> 00:59:06,930 SPEAKER: Se on paljon vaikeampaa, kun seisot täällä, ihmiset. 1063 00:59:06,930 --> 00:59:19,400 1064 00:59:19,400 --> 00:59:21,840 [NAURU] 1065 00:59:21,840 --> 00:59:26,730 1066 00:59:26,730 --> 00:59:29,054 ROBOT: Te ihmiset ovat niin helppoja voittaa. 1067 00:59:29,054 --> 00:59:30,803 [Naurua ja suosionosoituksia] 1068 00:59:30,803 --> 00:59:31,886 SPEAKER: Kiitos paljon. 1069 00:59:31,886 --> 00:59:34,692 ROBOT: voitan. 1070 00:59:34,692 --> 00:59:35,400 Aloitan pelin. 1071 00:59:35,400 --> 00:59:39,500 >> SPEAKER: Selvä, joten kiitos erittäin paljon Olivier, ja Alessandro, 1072 00:59:39,500 --> 00:59:41,616 ja Chen Ming. 1073 00:59:41,616 --> 00:59:45,600 >> [SUOSIONOSOITUKSET] 1074 00:59:45,600 --> 00:59:47,040 >> Haluan tehdä yhden asian. 1075 00:59:47,040 --> 00:59:51,630 Joten Baxter on hyvin pääty tähän, huijatuksi. 1076 00:59:51,630 --> 00:59:54,160 1077 00:59:54,160 --> 00:59:56,310 Ja se oli odottamaton. 1078 00:59:56,310 --> 01:00:00,440 Yksi upeista asioita AI on, että me 1079 01:00:00,440 --> 01:00:05,070 tehdä työtä AI, jotta voimme rakentaa todella mielenkiintoinen ja älykäs 1080 01:00:05,070 --> 01:00:06,930 laitteita. 1081 01:00:06,930 --> 01:00:10,130 Mutta teemme myös työtä AI koska se kertoo meille jotain 1082 01:00:10,130 --> 01:00:13,940 miten ihmiset ovat älykkäitä. 1083 01:00:13,940 --> 01:00:17,280 >> Yksi suosikki tutkimuksissa minun lab on 1084 01:00:17,280 --> 01:00:23,660 katsot mitä tapahtuu, kun koneet yllättäen huijata. 1085 01:00:23,660 --> 01:00:27,070 Teimme alun perin ei kanssa Baxter pelissä Ristinolla, 1086 01:00:27,070 --> 01:00:30,340 mutta pienempi robotti nimeltään Nao, joka pelasi kivi-paperi-sakset. 1087 01:00:30,340 --> 01:00:33,010 1088 01:00:33,010 --> 01:00:35,800 Ja joskus jälkeen pelaa paljon ja paljon 1089 01:00:35,800 --> 01:00:41,580 tylsää kivi-paperi-sakset pelit, robotti voisi heittää ele, 1090 01:00:41,580 --> 01:00:48,616 menettää, ja sitten yhtäkkiä muuttaa sen ele ja sanoa, voitan. 1091 01:00:48,616 --> 01:00:50,480 >> [NAURU] 1092 01:00:50,480 --> 01:00:56,090 >> Nyt, joskus olisimme myös robotti, kuten ohjaus, heittää ele, 1093 01:00:56,090 --> 01:01:01,270 voittaa, ja muuttaa sen ele menettää, heittää ottelu, 1094 01:01:01,270 --> 01:01:04,070 huijata jotta menettää. 1095 01:01:04,070 --> 01:01:07,540 Ja että ei ole läheskään yhtä vakuuttava. 1096 01:01:07,540 --> 01:01:09,890 Robotti, joka huijareita saadakseen ihmiset 1097 01:01:09,890 --> 01:01:14,660 vastata, jos se on hakemaan heidät, kuin se 1098 01:01:14,660 --> 01:01:17,690 pyrkii aktiivisesti niiden tuhoamista. 1099 01:01:17,690 --> 01:01:19,210 >> [NAURU] 1100 01:01:19,210 --> 01:01:20,990 >> Siitä tulee agentti. 1101 01:01:20,990 --> 01:01:21,840 Se on kuin ihminen. 1102 01:01:21,840 --> 01:01:23,970 Se on usko ja tarkoitus. 1103 01:01:23,970 --> 01:01:27,470 Ja se ei ole hyvä tarkoitus. 1104 01:01:27,470 --> 01:01:33,790 Ja robotti, joka heittää peli on juuri toimintahäiriö. 1105 01:01:33,790 --> 01:01:36,990 Se on vain viallisen laitteen. 1106 01:01:36,990 --> 01:01:41,405 Näytän teille pari esimerkkiä Kyseisen muutamasta osallistujista. 1107 01:01:41,405 --> 01:01:43,990 1108 01:01:43,990 --> 01:01:45,600 Joten tässä on huijaaminen jotta menettää. 1109 01:01:45,600 --> 01:01:46,266 >> [VIDEOTOISTOSTA] 1110 01:01:46,266 --> 01:01:47,010 - [Kuultavissa] voittaa. 1111 01:01:47,010 --> 01:01:49,550 Pelataan. 1112 01:01:49,550 --> 01:01:50,538 >> -Odota mitä? 1113 01:01:50,538 --> 01:01:54,490 1114 01:01:54,490 --> 01:01:55,352 >> - [Kuultavissa] voittaa. 1115 01:01:55,352 --> 01:01:58,280 Pelataan. 1116 01:01:58,280 --> 01:01:59,400 >> [Kuultavissa] voittaa. 1117 01:01:59,400 --> 01:02:02,290 Pelataan. 1118 01:02:02,290 --> 01:02:05,490 >> SPEAKER: Ja tässä huijaa voittaa. 1119 01:02:05,490 --> 01:02:06,438 >> -Kyllä, Voitan. 1120 01:02:06,438 --> 01:02:07,394 Pelataan. 1121 01:02:07,394 --> 01:02:08,828 >> -Voit Tehdä sitä. 1122 01:02:08,828 --> 01:02:10,740 >> [NAURU] 1123 01:02:10,740 --> 01:02:12,174 1124 01:02:12,174 --> 01:02:13,979 >> -Kyllä, Voitan. 1125 01:02:13,979 --> 01:02:14,520 -Sinä Huijatuksi. 1126 01:02:14,520 --> 01:02:17,990 1127 01:02:17,990 --> 01:02:20,010 Huijasit nyt. 1128 01:02:20,010 --> 01:02:21,140 >> -Kyllä, Voitan. 1129 01:02:21,140 --> 01:02:22,940 >> Hei, sinä huijari. 1130 01:02:22,940 --> 01:02:26,670 Huijaat, Super huijata. 1131 01:02:26,670 --> 01:02:27,650 >> [Lopeta toisto] 1132 01:02:27,650 --> 01:02:31,130 >> SPEAKER: Nämä eri reaktiot nopeasti 1133 01:02:31,130 --> 01:02:34,890 muuttaa käsityksemme laitteen. 1134 01:02:34,890 --> 01:02:36,780 Tarkoittaako tämä, että me tietoisesti rakentaa 1135 01:02:36,780 --> 01:02:40,370 koneita, jotka huijata koska se on paras engineering, että voimme tehdä? 1136 01:02:40,370 --> 01:02:44,680 Ei, mutta se kertoo meille jotain todella mielenkiintoinen ihmisistä. 1137 01:02:44,680 --> 01:02:49,710 Tämä asia, että huijareita sinua ja varastaa voitto, joka on 1138 01:02:49,710 --> 01:02:53,660 jotain, joka on elossa, se on animoida, joka on hakemaan sinut. 1139 01:02:53,660 --> 01:02:54,680 Se on henkinen tila. 1140 01:02:54,680 --> 01:02:55,400 Se on usko. 1141 01:02:55,400 --> 01:02:57,170 Se on tarkoitus. 1142 01:02:57,170 --> 01:03:01,540 >> Tämä asia, että kädet peli sinulle, että ei ole. 1143 01:03:01,540 --> 01:03:04,670 Se on vain huonosti. 1144 01:03:04,670 --> 01:03:08,900 Tämä on monella tapaa miksi se on helppo heittää pelin lasten kanssa. 1145 01:03:08,900 --> 01:03:12,050 Mutta jos yrität huijata niitä ja tavallaan väittävät voitto 1146 01:03:12,050 --> 01:03:15,200 kun tiedät, vain lyhentää peli, he sinut kiinni heti. 1147 01:03:15,200 --> 01:03:19,040 1148 01:03:19,040 --> 01:03:23,140 Tällaisia ​​vaikutuksia näemme tulossa ulos AI, 1149 01:03:23,140 --> 01:03:26,490 he opettavat meille paljon itsestämme. 1150 01:03:26,490 --> 01:03:28,076 >> Okei, se on siinä tänään. 1151 01:03:28,076 --> 01:03:30,450 Kiitoksia David ja Harvardin tuotanto joukkue 1152 01:03:30,450 --> 01:03:32,350 varten tulossa alas. 1153 01:03:32,350 --> 01:03:33,820 >> [SUOSIONOSOITUKSET] 1154 01:03:33,820 --> 01:03:36,760 1155 01:03:36,760 --> 01:03:41,840 >> Nähdään varten tietokilpailu yhden, ja sitten yksi viime luento. 1156 01:03:41,840 --> 01:03:43,025 Hyvää päivän jatkoa. 1157 01:03:43,025 --> 01:03:44,965 >> [SUOSIONOSOITUKSET] 1158 01:03:44,965 --> 01:03:48,360 1159 01:03:48,360 --> 01:03:51,825 >> [Musiikkia] 1160 01:03:51,825 --> 01:03:54,950 DAVID J MALAN: No, me luultavasti ottaa käyttöön jonkinlainen salauksen, 1161 01:03:54,950 --> 01:03:55,450 oikea? 1162 01:03:55,450 --> 01:03:58,650 Koska silloin otsikot nämä HTTP-pyynnöt ovat 1163 01:03:58,650 --> 01:04:01,530 salattu niin, että kuka tahansa yrittää haistella liikennettä 1164 01:04:01,530 --> 01:04:03,400 ei todella voi nähdä niitä. 1165 01:04:03,400 --> 01:04:05,254 Joten mikä on ratkaisu tähän ongelmaan? 1166 01:04:05,254 --> 01:04:07,920 No, meidän on todella käyttöön salaus kaavaan, 1167 01:04:07,920 --> 01:04:11,010 niin että kun kyseinen henkilö on lähettämään tietoa B, 1168 01:04:11,010 --> 01:04:12,390 voimme turvallisesti send-- 1169 01:04:12,390 --> 01:04:14,590 >> [NAURU] 1170 01:04:14,590 --> 01:04:19,530 >> Tiedot siten, että vastustaja ei voi itse asiassa nähdä sen.