1 00:00:00,000 --> 00:00:01,924 >> [MUZYKI] 2 00:00:01,924 --> 00:00:10,600 3 00:00:10,600 --> 00:00:13,280 >> GŁOŚNIK: Witamy z powrotem, wszyscy. 4 00:00:13,280 --> 00:00:15,440 To CS50. 5 00:00:15,440 --> 00:00:21,040 A dzisiaj mamy dużo Interesujące rzeczy do omówienia. 6 00:00:21,040 --> 00:00:25,500 Najpierw jednak muszę przypomnieć Ci kilka rzeczy administracyjnych. 7 00:00:25,500 --> 00:00:30,160 Ten tydzień jest quiz, jeden, środa lub sekcji Yale 8 00:00:30,160 --> 00:00:32,940 we wtorki i czwartki, w czwartek. 9 00:00:32,940 --> 00:00:38,170 Istnieją opinie quizów dzisiaj w Yale, 5:30 do 7:00. 10 00:00:38,170 --> 00:00:40,030 Na Harvardzie, nagrali jeden wczoraj. 11 00:00:40,030 --> 00:00:43,000 I każdy może oglądać ten online. 12 00:00:43,000 --> 00:00:49,406 >> Również w tym tygodniu lub na początku przyszłego tygodnia, mamy nasz ostatni wykład CS50. 13 00:00:49,406 --> 00:00:51,450 [Wzdycha] Wiem. 14 00:00:51,450 --> 00:00:54,140 To przyszło tak szybko. 15 00:00:54,140 --> 00:00:57,820 Studenci Yale będzie miał na żywo wykład tu w szkole prawniczej 16 00:00:57,820 --> 00:00:59,920 Widownia w piątek. 17 00:00:59,920 --> 00:01:01,140 Będzie tort. 18 00:01:01,140 --> 00:01:05,570 Studenci Harvardu będzie miał Ostatni wykład w Sandersa w poniedziałek. 19 00:01:05,570 --> 00:01:08,050 Będzie też tort. 20 00:01:08,050 --> 00:01:14,000 >> Również w tym tygodniu w piątek, dla tych, z Was, którzy przybywają do New Haven, 21 00:01:14,000 --> 00:01:15,740 mamy Expo CS50. 22 00:01:15,740 --> 00:01:18,850 Mamy ponad 30 różne grupy zarejestrowany 23 00:01:18,850 --> 00:01:22,530 pokazać wszystko z autonomicznych łodzi, 24 00:01:22,530 --> 00:01:27,170 do systemów, które uznają portrety cyfrowe, do komputera 25 00:01:27,170 --> 00:01:32,100 muzyka i produkcji muzyki komputerowej. 26 00:01:32,100 --> 00:01:33,610 Więc proszę do nas dołączyć. 27 00:01:33,610 --> 00:01:36,460 Myślę, że to będzie świetny czas. 28 00:01:36,460 --> 00:01:40,320 >> Dziś, choć mamy do nadal mówić o AI, 29 00:01:40,320 --> 00:01:43,150 o sztucznej inteligencji. 30 00:01:43,150 --> 00:01:46,070 A jedną z rzeczy, które mamy zamiar dostać się do dziś 31 00:01:46,070 --> 00:01:51,750 jest pomysł, jak użyć AI do rozwiązywania problemów. 32 00:01:51,750 --> 00:01:54,690 Teraz, jak zawsze, zacznijmy od czegoś prostego. 33 00:01:54,690 --> 00:01:57,120 I mamy zamiar zacząć z prostego pomysłu. 34 00:01:57,120 --> 00:01:59,920 I to przy użyciu wyszukiwania. 35 00:01:59,920 --> 00:02:06,990 >> Więc wyobraź sobie przez chwilę, że mają zadania, które trzeba wykonać. 36 00:02:06,990 --> 00:02:11,970 I chciałbym mieć to zadanie zautomatyzowany przez jakiegoś agenta oprogramowania. 37 00:02:11,970 --> 00:02:17,100 Wyobraź sobie, że staram się zarezerwować zestaw lotów z, powiedzmy, Boston 38 00:02:17,100 --> 00:02:20,040 do San Francisco. 39 00:02:20,040 --> 00:02:24,230 Mogłem przejść i można używać Jedną z najlepszych wyszukiwania online 40 00:02:24,230 --> 00:02:28,790 narzędzia, które zrobi w zasadzie ten sam proces, że jesteśmy 41 00:02:28,790 --> 00:02:30,030 będzie chodzić do dzisiaj. 42 00:02:30,030 --> 00:02:34,100 Ale jeśli nie masz, że Narzędzie, co byś zrobił? 43 00:02:34,100 --> 00:02:37,570 >> Cóż, można patrzeć i zobaczyć i powiedzieć, że jestem w Bostonie. 44 00:02:37,570 --> 00:02:41,520 Co loty są dostępne do mnie? 45 00:02:41,520 --> 00:02:44,390 Teraz, być może mam trzy Możliwe loty spośród Bostonie 46 00:02:44,390 --> 00:02:47,180 które będą pasowały do ​​czasu kiedy muszę odejść. 47 00:02:47,180 --> 00:02:48,830 Mogę lecieć do Chicago. 48 00:02:48,830 --> 00:02:50,130 Albo mógłbym polecieć do Miami. 49 00:02:50,130 --> 00:02:53,340 Albo mógłbym polecieć do Nowego Jorku. 50 00:02:53,340 --> 00:02:56,980 Mógłbym to nie patrzeć od siebie jednym z tych miast docelowych 51 00:02:56,980 --> 00:03:00,650 i zastanowić się, co lokalizacje Mógłbym osiągnąć 52 00:03:00,650 --> 00:03:03,020 z każdego z tych poszczególnych miast. 53 00:03:03,020 --> 00:03:07,390 >> Więc może z Chicago, mogę bezpośredni lot do San Francisco. 54 00:03:07,390 --> 00:03:09,550 To doskonała. 55 00:03:09,550 --> 00:03:12,360 Czy mogę dostać lot do Denver. 56 00:03:12,360 --> 00:03:16,970 Teraz, być może, że lot do San Francisco jest idealnym rozwiązaniem dla mnie, 57 00:03:16,970 --> 00:03:19,530 ale może nie. 58 00:03:19,530 --> 00:03:22,180 Może szukam czegoś to trochę tańsze 59 00:03:22,180 --> 00:03:24,920 lub nieco lepsze dla mojego harmonogramu. 60 00:03:24,920 --> 00:03:29,197 A więc mogłem patrzeć na to, co inne możliwości może być tam. 61 00:03:29,197 --> 00:03:30,280 Więc mogłem patrzeć na Denver. 62 00:03:30,280 --> 00:03:33,870 A z Denver, no, może Mogę lot do Austin. 63 00:03:33,870 --> 00:03:37,080 A z Austin, może uda mi się dostać Lot do Phoenix, a z Phoenix 64 00:03:37,080 --> 00:03:40,190 do San Francisco. 65 00:03:40,190 --> 00:03:42,730 Teraz, nie mam jeszcze zrobić. 66 00:03:42,730 --> 00:03:45,640 Bo może istnieje bezpośredni lot z Nowego Jorku 67 00:03:45,640 --> 00:03:47,850 San Francisco, który jest idealny dla mnie. 68 00:03:47,850 --> 00:03:53,354 A może jest to lot z Miami przez Denver to dużo tańsze. 69 00:03:53,354 --> 00:03:54,270 Więc mam jeszcze do zrobienia. 70 00:03:54,270 --> 00:03:58,200 I mam jeszcze patrzeć na tych wszystkich, miasta, że ​​nie zostały jeszcze zbadane. 71 00:03:58,200 --> 00:04:04,220 Muszę wyczerpująco sprawdzić wszystkie możliwości, że mogę mieć. 72 00:04:04,220 --> 00:04:09,610 >> Więc z Nowego Jorku, może uda mi się dostać lot do Nashville, a od Nashville 73 00:04:09,610 --> 00:04:10,336 do Austin. 74 00:04:10,336 --> 00:04:11,460 I wtedy wiem, gdzie jestem. 75 00:04:11,460 --> 00:04:14,252 I wtedy wiem, że z Austin, mogę lecieć do Phoenix, a z Phoenix 76 00:04:14,252 --> 00:04:14,960 do San Francisco. 77 00:04:14,960 --> 00:04:18,240 78 00:04:18,240 --> 00:04:22,830 Jeśli lecę pierwszy Miami, choć, może uda mi się lot z Miami 79 00:04:22,830 --> 00:04:25,080 do Nashville, lub z Miami do Austin. 80 00:04:25,080 --> 00:04:27,950 81 00:04:27,950 --> 00:04:30,860 >> A teraz Próbowałem wszystkich z możliwości. 82 00:04:30,860 --> 00:04:36,310 Mam zbudowany ten wykres, że mi pokazuje wszystkich możliwych tras 83 00:04:36,310 --> 00:04:37,790 że mogę być w stanie podjąć. 84 00:04:37,790 --> 00:04:40,510 85 00:04:40,510 --> 00:04:43,640 Kiedy stanowią one rodzaje problemów, 86 00:04:43,640 --> 00:04:47,870 nie idziemy do reprezentowania im wyraźnie, jak tego wykresu, 87 00:04:47,870 --> 00:04:51,590 bo to wykres nie przedstawia historia, gdzie zaszliśmy. 88 00:04:51,590 --> 00:04:55,260 Wiedząc, że przyleciał z Phoenix do San Francisco 89 00:04:55,260 --> 00:05:01,690 nie mów mi, czy ja przyszedłem poprzez Nashville, lub przez Denver, lub przez Miami. 90 00:05:01,690 --> 00:05:06,430 >> Więc co zrobię, a nie jest Wezmę ten sam problem, 91 00:05:06,430 --> 00:05:09,140 a ja reprezentuje ją jako drzewo. 92 00:05:09,140 --> 00:05:14,300 A u korzeni drzewa, u góry, włożę miejsce, które zacząłem, 93 00:05:14,300 --> 00:05:16,590 Boston. 94 00:05:16,590 --> 00:05:19,310 A z Bostonu, będę patrzeć na wszystkich możliwych lokalizacji 95 00:05:19,310 --> 00:05:20,380 że mogę podróżować do. 96 00:05:20,380 --> 00:05:25,480 No cóż, w tym przypadku, miałem trzy, Chicago, Nowym Jorku i Miami. 97 00:05:25,480 --> 00:05:29,850 A potem będę odkrywać każdego te dzieci w drzewie. 98 00:05:29,850 --> 00:05:32,690 >> Z Chicago, widziałem że miałem dwa loty. 99 00:05:32,690 --> 00:05:35,940 Mogę latać bezpośrednio do San Francisco lub Denver. 100 00:05:35,940 --> 00:05:37,740 Teraz w San Francisco, to jest mój cel. 101 00:05:37,740 --> 00:05:39,790 To jest moim celem. 102 00:05:39,790 --> 00:05:42,220 To będzie liści tego drzewa. 103 00:05:42,220 --> 00:05:45,340 Oznacza to, że nigdy nie pójdę gdzieś po San Francisco. 104 00:05:45,340 --> 00:05:47,850 105 00:05:47,850 --> 00:05:50,340 Z Denver, choć, Mogę latać z Denver 106 00:05:50,340 --> 00:05:54,220 Austin, Austin do Phoenix, oraz z Phoenix do San Francisco. 107 00:05:54,220 --> 00:05:56,050 A teraz znowu mam osiągnęła liść. 108 00:05:56,050 --> 00:05:59,470 109 00:05:59,470 --> 00:06:03,980 >> Mogłem wrócić do następnego miasto, że nie w pełni zbadane. 110 00:06:03,980 --> 00:06:07,440 To byłoby Nowy Jork, przejdź z powrotem na górę mojego drzewa, 111 00:06:07,440 --> 00:06:09,160 sprowadzają się do Nowego Jorku. 112 00:06:09,160 --> 00:06:12,700 Z Nowego Jorku, mogę latać do Nashville, z Nashville do Austin, 113 00:06:12,700 --> 00:06:17,290 z Austin do Phoenix, i z Phoenix do San Francisco. 114 00:06:17,290 --> 00:06:20,170 I w końcu, jedno miasto ja nie spojrzał na jeszcze, Miami. 115 00:06:20,170 --> 00:06:24,600 >> Cóż, z Miami powiedziałem miałem dwa możliwości, Nashville i Austin. 116 00:06:24,600 --> 00:06:28,810 Jeśli lecę do Nashville, a potem lecę z Nashville, do Austin, do Phoenix, 117 00:06:28,810 --> 00:06:29,640 do San Francisco. 118 00:06:29,640 --> 00:06:33,600 Jeśli lecę do Austin, lecę Austin, do Phoenix, San Francisco. 119 00:06:33,600 --> 00:06:36,340 A teraz mam w drzewo. 120 00:06:36,340 --> 00:06:37,230 Jest to pełne drzewo. 121 00:06:37,230 --> 00:06:41,890 To wszystko z możliwości i wszystkie drogi, że mogę podjąć. 122 00:06:41,890 --> 00:06:44,310 Oznacza to, że jeśli zacznę u korzeniem drzewa na górze 123 00:06:44,310 --> 00:06:47,860 i idę do jednego z pozostawia, to mówi mi, nie tylko 124 00:06:47,860 --> 00:06:50,480 gdzie mam zamiar kończy się, San Francisco, 125 00:06:50,480 --> 00:06:53,670 ale mówi mi drogę, która Muszę wziąć się tam dostać. 126 00:06:53,670 --> 00:06:56,400 127 00:06:56,400 --> 00:06:59,690 >> Teraz, który z nich jest najlepszy? 128 00:06:59,690 --> 00:07:02,430 Cóż, nic na ten temat Problem jednak mówi mi, 129 00:07:02,430 --> 00:07:04,710 który z nich jest najlepszym rozwiązaniem. 130 00:07:04,710 --> 00:07:09,270 Może zależy mi najbardziej o ile czasu jestem w powietrzu, 131 00:07:09,270 --> 00:07:12,350 lub odległość, że lecę. 132 00:07:12,350 --> 00:07:16,410 W tym przypadku, z Chicago do San Francisco może być najkrótszy numer 133 00:07:16,410 --> 00:07:18,910 mil w powietrzu. 134 00:07:18,910 --> 00:07:20,860 >> Może dbam o kosztach. 135 00:07:20,860 --> 00:07:23,680 A wszyscy wiemy, loty bezpośrednie są zwykle droższe. 136 00:07:23,680 --> 00:07:26,610 Więc może jeśli wezmę to rodzaj wstecznej trasie 137 00:07:26,610 --> 00:07:30,650 przez Miami, Nashville, Austin, Phoenix, może wtedy 138 00:07:30,650 --> 00:07:34,070 Uzyskać niższą cenę. 139 00:07:34,070 --> 00:07:36,440 Ale mogę zoptymalizować na żadnym Kryteria, że ​​mi zależy. 140 00:07:36,440 --> 00:07:39,790 Kto ma najlepszy w Lot Wi-Fi, lub które 141 00:07:39,790 --> 00:07:43,110 lotniska mają najlepsze jedzenie dostępne. 142 00:07:43,110 --> 00:07:47,280 I każdy z tych może daj mi inne rozwiązanie 143 00:07:47,280 --> 00:07:49,215 że widzę jako najlepsze. 144 00:07:49,215 --> 00:07:51,990 145 00:07:51,990 --> 00:07:54,400 >> Tego rodzaju problemy, gdzie jedziemy 146 00:07:54,400 --> 00:07:58,480 budować tę drzewo możliwości, a następnie 147 00:07:58,480 --> 00:08:02,100 patrzeć na każdy z tych Poszczególne ścieżki, i zbadać 148 00:08:02,100 --> 00:08:05,270 które z tych spełnia kryterium do nas, 149 00:08:05,270 --> 00:08:08,790 mamy zamiar zadzwonić te problemy wyszukiwania. 150 00:08:08,790 --> 00:08:11,280 I mamy dużo algorytm, z których niektóre 151 00:08:11,280 --> 00:08:15,270 widzieliśmy już, aby przejść i zbadać te drzewa. 152 00:08:15,270 --> 00:08:19,270 Możemy zrobić to w ten sposób, że ja po prostu tak, jak przeszukiwanie w głąb, 153 00:08:19,270 --> 00:08:22,900 dzieje się tak daleko, jak to możliwe, dopóki nie uderzył w skrzydło, a następnie wraca do góry, 154 00:08:22,900 --> 00:08:24,787 i będzie z powrotem w dół. 155 00:08:24,787 --> 00:08:26,870 Albo możemy zrobić to, co nazywa przeszukiwanie wszerz. 156 00:08:26,870 --> 00:08:29,675 Możemy poszerzyć wszystko w górę, a następnie 157 00:08:29,675 --> 00:08:31,550 wszystko jedna linia pod nim, a następnie 158 00:08:31,550 --> 00:08:35,240 wszystko pod spodem, że jedna linia. 159 00:08:35,240 --> 00:08:41,250 Wyszukiwarka te drzewa mają fundamentalne znaczenie dla AI. 160 00:08:41,250 --> 00:08:46,570 Ale nie dość się to prawo cały czas. 161 00:08:46,570 --> 00:08:51,600 W istocie, w wielu przypadkach że naprawdę obchodzi, 162 00:08:51,600 --> 00:08:54,430 chcemy zbudować drzewo, ale w rzeczywistości nie 163 00:08:54,430 --> 00:08:57,140 się, aby wszystkie decyzje. 164 00:08:57,140 --> 00:09:00,940 >> Są to sytuacje, zwane kontradyktoryjności wyszukiwarka, znany także 165 00:09:00,940 --> 00:09:05,390 a jak napisać grę grę systemy i dostać za to pieniądze. 166 00:09:05,390 --> 00:09:07,940 Ale są to rodzaje systemów, gdzie 167 00:09:07,940 --> 00:09:12,920 może dostać się do wyboru, kiedy idę z Boston, które miasto idę dalej. 168 00:09:12,920 --> 00:09:19,990 Ale po tym, ktoś inny może dostać do podjęcia decyzji o tym, gdzie lecę. 169 00:09:19,990 --> 00:09:24,040 Więc zbudować nich Struktury rodzaju, jesteśmy 170 00:09:24,040 --> 00:09:28,510 będzie musiał podjąć lekko Inne podejście do niego. 171 00:09:28,510 --> 00:09:31,060 Nie będziemy w stanie wystarczy poszukać przez drzewo 172 00:09:31,060 --> 00:09:35,000 więcej, bo nie jesteśmy jedna to w kontroli 173 00:09:35,000 --> 00:09:38,180 każdego z tych punktów decyzyjnych. 174 00:09:38,180 --> 00:09:42,590 >> Więc wyobraźmy sobie proste gra jak Kółko i krzyżyk. 175 00:09:42,590 --> 00:09:46,730 Mógłbym zacząć z zupełnie puste płyty. 176 00:09:46,730 --> 00:09:49,580 A w Kółko i krzyżyk, X dostaje do gry w pierwszej kolejności. 177 00:09:49,580 --> 00:09:53,890 A więc mogłem myśleć o wszystkim możliwe ruchy, które mogłyby spowodować X. 178 00:09:53,890 --> 00:09:57,420 A jeśli jestem jedynym gry X, to świetnie. 179 00:09:57,420 --> 00:10:01,020 Mam dziewięć możliwych porusza się, że mogę to zrobić. 180 00:10:01,020 --> 00:10:05,000 I może umieścić znak X w jednego z tych dziewięciu pozycjach. 181 00:10:05,000 --> 00:10:10,710 >> Po czym z każdego z nich, I można sobie wyobrazić, co będzie dalej. 182 00:10:10,710 --> 00:10:14,130 Również w tym przypadku druga Gracz dostanie się skręcić. 183 00:10:14,130 --> 00:10:15,660 O dostanie się skręcić. 184 00:10:15,660 --> 00:10:19,510 Oraz każdy z nich, nie będzie osiem różnych miejsc 185 00:10:19,510 --> 00:10:22,980 które mogłyby stawiać ich O znacznik. 186 00:10:22,980 --> 00:10:25,790 >> Powiedzmy, że postanowiłem, że jestem zamiar umieścić znak X w centrum. 187 00:10:25,790 --> 00:10:28,810 To zawsze wydaje się dobry ruch otwierania. 188 00:10:28,810 --> 00:10:34,870 Mogłem patrzeć pod tym, osiem możliwe ruchy, że O producentów. 189 00:10:34,870 --> 00:10:37,320 Teraz, gdy gram w X, to wspaniale. 190 00:10:37,320 --> 00:10:41,740 Mogę wybrać jeden I przejść do, jeden w środku. 191 00:10:41,740 --> 00:10:45,000 Ale teraz O dostaje do wyboru. 192 00:10:45,000 --> 00:10:48,750 I nie mają kontroli nad tą decyzją. 193 00:10:48,750 --> 00:10:51,670 >> Ale z każdego z tych możliwe pozycje planszowe, 194 00:10:51,670 --> 00:10:54,020 nie ma wtedy inny szereg możliwości. 195 00:10:54,020 --> 00:10:56,700 Gdy chodzi się Moja kolej ponownie, chciałbym 196 00:10:56,700 --> 00:11:01,500 się wybrać i powiedzieć, dobrze, jeśli wy przenosi się do, dobrze, 197 00:11:01,500 --> 00:11:06,110 środkowe miejsce na lewej stronie, a następnie Mam zbiór możliwości 198 00:11:06,110 --> 00:11:09,740 gdzie mogę wziąć mój następny ruch. 199 00:11:09,740 --> 00:11:14,140 Od tych, mogę rozważyć wszystkie możliwości pod nimi. 200 00:11:14,140 --> 00:11:18,030 A następnie O dostanie do wyboru spośród tych. 201 00:11:18,030 --> 00:11:22,290 >> I mogłem utrzymać budowy tego Drzewo się, aż dotarłem do punktu 202 00:11:22,290 --> 00:11:26,960 gdzie albo ktoś wygrywa game--, który jest 203 00:11:26,960 --> 00:11:31,070 ale powinna być traktowana jako liść node-- lub płyta jest pełny 204 00:11:31,070 --> 00:11:32,704 i nikt nie wygrał. 205 00:11:32,704 --> 00:11:34,370 I to też będzie węzeł liści. 206 00:11:34,370 --> 00:11:35,411 Że będzie remis. 207 00:11:35,411 --> 00:11:37,820 208 00:11:37,820 --> 00:11:41,680 >> Ale trudne rzeczy z tym jest gdyby to było po prostu zwykła wyszukiwarka 209 00:11:41,680 --> 00:11:44,269 Problem, że będę w stanie powiedzmy, dobrze, X powinny tu. 210 00:11:44,269 --> 00:11:45,560 I O powinny iść droga tam. 211 00:11:45,560 --> 00:11:46,770 A następnie X powinny iść tutaj. 212 00:11:46,770 --> 00:11:48,269 A następnie O powinny iść droga tam. 213 00:11:48,269 --> 00:11:51,860 A następnie X może uzyskać trzy z rzędu, i wygram. 214 00:11:51,860 --> 00:11:54,870 A gra się skończy w pięciu ruchów, trzy dla mnie, 215 00:11:54,870 --> 00:11:57,710 dwa dla mojego przeciwnika. 216 00:11:57,710 --> 00:12:01,300 Ale nie zawsze się do wyboru tego. 217 00:12:01,300 --> 00:12:03,720 >> Więc zamiast tego, co mamy będzie musiał zrobić 218 00:12:03,720 --> 00:12:06,270 jest, że będziemy mieć mieć nową strategię. 219 00:12:06,270 --> 00:12:09,350 I strategii, które Algorytmy-playing game często używają 220 00:12:09,350 --> 00:12:12,000 jest to, co nazywa się minimax. 221 00:12:12,000 --> 00:12:15,500 Główną ideą minimax jest to, że jesteśmy 222 00:12:15,500 --> 00:12:21,365 zamiar wybrać ruch, który daje nasz przeciwnik najgorszy możliwy zestaw 223 00:12:21,365 --> 00:12:22,790 ruchów, które mogą zrobić. 224 00:12:22,790 --> 00:12:25,570 225 00:12:25,570 --> 00:12:28,870 Nie robi mi jakieś dobre aby wybrać ruch gdzie 226 00:12:28,870 --> 00:12:31,952 Mogę być w stanie wygrać po , to dlatego, że mój przeciwnik nie jest 227 00:12:31,952 --> 00:12:33,160 zamiar dać mi szansę. 228 00:12:33,160 --> 00:12:37,770 Zamierzają wybrać niektóre straszny wynik dla mnie. 229 00:12:37,770 --> 00:12:42,010 Więc mam zamiar zrobić przenieść, że zmusza mojego przeciwnika 230 00:12:42,010 --> 00:12:45,760 zrobić coś lepszego dla mnie. 231 00:12:45,760 --> 00:12:46,260 W porządku. 232 00:12:46,260 --> 00:12:48,410 Zobaczmy, jak to rozegra. 233 00:12:48,410 --> 00:12:51,640 Więc tutaj jest nasz algorytm w pseudokodzie. 234 00:12:51,640 --> 00:12:54,450 Jedziemy do generowania całe drzewo gry. 235 00:12:54,450 --> 00:12:56,757 Zamierzamy budować cała konstrukcja. 236 00:12:56,757 --> 00:12:57,840 A potem będziemy przejść. 237 00:12:57,840 --> 00:13:02,100 A na samym dole w każdej z węzły końcowe, w każdym z liści, 238 00:13:02,100 --> 00:13:07,850 oszacujemy jak cenne jest to, że do mnie? 239 00:13:07,850 --> 00:13:11,690 I jedziemy do rzeczy, wartości, które są dobre dla mnie, jako pozytywne. 240 00:13:11,690 --> 00:13:14,460 Rzeczy, które nie są dla mnie dobre będzie mniej pozytywne, lub zero, 241 00:13:14,460 --> 00:13:16,480 lub nawet ujemna. 242 00:13:16,480 --> 00:13:19,240 >> Tak więc w Kółko i krzyżyk, może zwycięstwo jest dla mnie dobre. 243 00:13:19,240 --> 00:13:20,290 To jest jeden. 244 00:13:20,290 --> 00:13:22,400 I krawat jest zero. 245 00:13:22,400 --> 00:13:26,230 I coś, że to strata dla ja, może to jest negatywny. 246 00:13:26,230 --> 00:13:29,620 Ważne jest to, że lepiej to jest dla mnie, tym wyższy wynik 247 00:13:29,620 --> 00:13:32,160 odbiera. 248 00:13:32,160 --> 00:13:36,690 Z tych możliwości Na dolny, a następnie będziemy filtrować górę. 249 00:13:36,690 --> 00:13:40,650 A kiedy to moja szansa, aby wybrać Wśród zbioru alternatyw, 250 00:13:40,650 --> 00:13:44,460 Wybiorę ten, który jest uzyskała najwyższą ocenę. 251 00:13:44,460 --> 00:13:47,200 >> A gdy to jest mój Przeciwnicy włączyć do wyboru, 252 00:13:47,200 --> 00:13:52,350 Będę zakładać, że oni będą wybrać jedną z najmniejszą liczbą punktów. 253 00:13:52,350 --> 00:13:56,090 I jeśli mogę to zrobić na drodze do wierzchu drzewa 254 00:13:56,090 --> 00:14:03,150 Ja wybrałem drogę, która daje mnie najlepszy wynik, który może uzyskać, 255 00:14:03,150 --> 00:14:09,110 zakładając, że mój przeciwnik sprawia, że ​​wszystkie odpowiednie ruchy. 256 00:14:09,110 --> 00:14:11,940 >> W porządku, więc zobaczymy to w pierwszej akcji. 257 00:14:11,940 --> 00:14:14,980 A potem będziemy rzeczywiście spojrzeć na kod dla niego. 258 00:14:14,980 --> 00:14:16,780 Więc wyobraź sobie, mam to wielkie drzewo. 259 00:14:16,780 --> 00:14:18,280 A teraz nie gram Kółko i krzyżyk. 260 00:14:18,280 --> 00:14:20,405 Chciałem ci dać coś trochę bogatszy. 261 00:14:20,405 --> 00:14:23,560 Więc mam trochę gra, gdzie istnieje wiele różnych wyniki 262 00:14:23,560 --> 00:14:26,390 że mogę mieć na końcu. 263 00:14:26,390 --> 00:14:27,980 I tak zbudować to kompletne drzewo. 264 00:14:27,980 --> 00:14:29,070 A ja się przenieść pierwszy. 265 00:14:29,070 --> 00:14:31,290 Jestem u korzeni drzewa. 266 00:14:31,290 --> 00:14:36,150 >> I mam do wyboru that-- więc mogę zmaksymalizować poprzek pierwszego węzła. 267 00:14:36,150 --> 00:14:38,410 I wtedy mój przeciwnik dostaje iść. 268 00:14:38,410 --> 00:14:41,910 A potem mam iść jeszcze raz. 269 00:14:41,910 --> 00:14:46,830 Więc się na dole, mam zestaw możliwości, że mogę wybierać, 270 00:14:46,830 --> 00:14:50,570 różne stany końcowe gry. 271 00:14:50,570 --> 00:14:54,980 Jeśli jestem w które lewej rogu, 272 00:14:54,980 --> 00:14:58,867 i widzę, że mam do wyboru pomiędzy osiem, a siedem, a dwa, 273 00:14:58,867 --> 00:15:00,450 Cóż, jestem tym, który dostaje do wyboru. 274 00:15:00,450 --> 00:15:02,910 Więc mam zamiar wybrać najlepszy z nich. 275 00:15:02,910 --> 00:15:05,650 Mam zamiar wybrać osiem. 276 00:15:05,650 --> 00:15:10,090 >> Więc wiem, że jeśli kiedykolwiek dostać się do tego punktu, 277 00:15:10,090 --> 00:15:13,890 Będę w stanie dostać się, że osiem punktów. 278 00:15:13,890 --> 00:15:17,410 Jeśli skończę w następnym punkcie powyżej, w ciągu następnego węzła, 279 00:15:17,410 --> 00:15:20,760 dziewięć, jeden, lub sześć, dobrze, jestem zamiar wybrać najlepszy z nich. 280 00:15:20,760 --> 00:15:21,950 Wybiorę dziewięciu. 281 00:15:21,950 --> 00:15:24,880 Jeśli mam do wyboru dwa, cztery, jeden, 282 00:15:24,880 --> 00:15:28,240 Wybiorę cztery, najwyżej. 283 00:15:28,240 --> 00:15:31,990 >> Teraz, gdy patrzę na poziomie powyżej, że mój przeciwnik 284 00:15:31,990 --> 00:15:34,440 to dostaje do wyboru. 285 00:15:34,440 --> 00:15:37,040 Więc mój przeciwnik dostaje wybrać, czy chcę, aby dać mu 286 00:15:37,040 --> 00:15:39,250 tym, co się dzieje aby mu osiem punktów, 287 00:15:39,250 --> 00:15:41,916 czy mogę dać mu coś, co jest zamiar dać mu dziewięć punktów, 288 00:15:41,916 --> 00:15:45,240 lub tym, co się dzieje dać mu czterech punktów? 289 00:15:45,240 --> 00:15:49,130 I mój przeciwnik, jest racjonalne, będzie 290 00:15:49,130 --> 00:15:53,470 do wyboru minimum te, będzie wybrać cztery. 291 00:15:53,470 --> 00:15:56,020 >> I mogę to zrobić przez całego drzewa. 292 00:15:56,020 --> 00:15:59,110 Mogę iść do środkowy zestaw trzech. 293 00:15:59,110 --> 00:16:01,517 I mogę wybierać między jeden, trzy i pięć. 294 00:16:01,517 --> 00:16:02,350 I mam do wyboru. 295 00:16:02,350 --> 00:16:03,810 Więc wybrać pięć. 296 00:16:03,810 --> 00:16:05,340 Mogę wybrać trzy, dziewięć, lub dwa. 297 00:16:05,340 --> 00:16:07,570 Mam do wyboru, więc wybrać dziewięć. 298 00:16:07,570 --> 00:16:09,290 Sześć, pięć, czy dwa, wybieram. 299 00:16:09,290 --> 00:16:11,539 Mam do wyboru sześć. 300 00:16:11,539 --> 00:16:13,080 Poziom wyżej, że, który dostaje do wyboru? 301 00:16:13,080 --> 00:16:16,280 302 00:16:16,280 --> 00:16:18,140 Kto dostanie do wyboru? 303 00:16:18,140 --> 00:16:20,000 Drugi facet, mój przeciwnik. 304 00:16:20,000 --> 00:16:22,583 Więc wybrać pięć, dziewięć lub sześć, które? 305 00:16:22,583 --> 00:16:23,410 >> PUBLICZNOŚCI: Pięć. 306 00:16:23,410 --> 00:16:25,250 >> GŁOŚNIK: Oni wybrać pięć. 307 00:16:25,250 --> 00:16:27,400 Oni się wybrać minimum. 308 00:16:27,400 --> 00:16:29,690 A następnie ostatni, wybrać jeden, dwa lub trzy. 309 00:16:29,690 --> 00:16:31,720 Mam do wyboru, więc wybrać trzy. 310 00:16:31,720 --> 00:16:34,370 Dziewięć, siedem, lub dwa, wybrać dziewięć. 311 00:16:34,370 --> 00:16:37,070 I 11, sześć lub cztery, wybrać 11. 312 00:16:37,070 --> 00:16:41,190 Mój przeciwnik wybiera trzy, dziewięciu lub 11, wybiera minimum. 313 00:16:41,190 --> 00:16:43,290 On daje mi trzy. 314 00:16:43,290 --> 00:16:47,780 A na koniec na górze drzewo, mogę wybrać ponownie. 315 00:16:47,780 --> 00:16:51,190 I mam do wyboru między cztery, pięć lub trzy. 316 00:16:51,190 --> 00:16:52,270 Więc biorę pięć. 317 00:16:52,270 --> 00:16:55,070 318 00:16:55,070 --> 00:17:00,891 >> Jeśli mam kontrolować wszystko, ja bym na drogę, która doprowadziła do 11. 319 00:17:00,891 --> 00:17:02,390 Ale ja nie rozumiem na taki wybór. 320 00:17:02,390 --> 00:17:04,220 Jeśli pójdę tą drogą. 321 00:17:04,220 --> 00:17:10,710 Mój przeciwnik zmusi mnie do Wybór, który prowadzi do trzech. 322 00:17:10,710 --> 00:17:14,530 Tak więc najlepsze, co mogę zrobić, to do podjęcia tego środkowy oddział, 323 00:17:14,530 --> 00:17:19,859 dokonać tego wyboru, który jest w końcu będzie prowadzić mnie do pięciu punktów. 324 00:17:19,859 --> 00:17:23,230 To, co robi minimax. 325 00:17:23,230 --> 00:17:23,807 >> W porządku. 326 00:17:23,807 --> 00:17:24,890 Rzućmy okiem na to. 327 00:17:24,890 --> 00:17:27,480 328 00:17:27,480 --> 00:17:32,330 Więc tutaj w CS50 IDE to program, który 329 00:17:32,330 --> 00:17:36,540 realizuje minimax do gry Kółko i krzyżyk. 330 00:17:36,540 --> 00:17:40,100 Zamierzamy budować do reprezentacji. 331 00:17:40,100 --> 00:17:44,390 Mamy zamiar mieć dwa opponent-- lub dwóch graczy, nasz komputer 332 00:17:44,390 --> 00:17:46,090 Odtwarzacz i osoba grająca. 333 00:17:46,090 --> 00:17:48,980 334 00:17:48,980 --> 00:17:53,090 Numer jeden gracz będzie grał O. To będzie gracz maszyna. 335 00:17:53,090 --> 00:17:55,747 Oni się przenieść sekund. 336 00:17:55,747 --> 00:17:57,830 A drugi gracz, nasze Odtwarzacz ludzka, będą X. 337 00:17:57,830 --> 00:17:59,880 >> I aby moje życie trochę proste, zamierzam 338 00:17:59,880 --> 00:18:03,060 na etykiecie, że negatywny jednego gracza. 339 00:18:03,060 --> 00:18:05,026 Więc może po prostu pomnożyć poprzez negatywny zamienić 340 00:18:05,026 --> 00:18:06,400 między jednym a drugim graczem. 341 00:18:06,400 --> 00:18:09,030 342 00:18:09,030 --> 00:18:12,250 W porządku, więc rzućmy okiem na co my właściwie zrobić. 343 00:18:12,250 --> 00:18:15,840 Jedziemy zdefiniować naszą płytę. 344 00:18:15,840 --> 00:18:19,060 To będzie dobrze, będziemy aby mogła ona być trójkami, 345 00:18:19,060 --> 00:18:21,580 lub możemy nawet grać pięć przez pięć lub siedem 346 00:18:21,580 --> 00:18:28,870 przez siedem Kółko i krzyżyk Gdybyś jak, na podstawie jakiegoś wymiaru D. 347 00:18:28,870 --> 00:18:31,260 >> A my mamy parę funkcji pomocniczych 348 00:18:31,260 --> 00:18:34,360 że będziemy robić takie rzeczy jak zainicjować screen-- lub przykro, 349 00:18:34,360 --> 00:18:38,900 zainicjować nasze zmienne, wyczyść Ekran, wyciągnąć płytę na ekranie, 350 00:18:38,900 --> 00:18:41,060 jeden, który sprawdza pokładzie aby zobaczyć, czy nie 351 00:18:41,060 --> 00:18:44,520 tam jest zwycięzca, który analizuje za pomocą wiersza polecenia, 352 00:18:44,520 --> 00:18:50,670 po prostu pomóc, to taki, który czyta w wejście i jedna funkcja nazywa się minimax. 353 00:18:50,670 --> 00:18:52,746 I to jest jeden my najbardziej zależy. 354 00:18:52,746 --> 00:18:54,120 Ale spójrzmy najpierw na główną. 355 00:18:54,120 --> 00:18:57,490 356 00:18:57,490 --> 00:18:58,510 >> Co robimy? 357 00:18:58,510 --> 00:19:00,570 Cóż, będziemy analizować naszą linię poleceń, 358 00:19:00,570 --> 00:19:04,300 wystarczy przeczytać i zobaczyć, co Płyta wymiar chcielibyśmy mieć. 359 00:19:04,300 --> 00:19:07,330 Będziemy inicjować naszą płytę. 360 00:19:07,330 --> 00:19:10,360 A potem będziemy wprowadzić jeden duże dzikie pętli, wielokrotnie 361 00:19:10,360 --> 00:19:16,630 akceptuje ruchy, aż gra się wygrał, czy nie ma już żadnych ruchów. 362 00:19:16,630 --> 00:19:20,560 Za każdym razem idziemy przez które pętli, będziemy wyczyścić ekran. 363 00:19:20,560 --> 00:19:23,290 Będziemy rysować płytę na ekranie. 364 00:19:23,290 --> 00:19:28,750 A my świadomie rodzaju abstrahując nich z dala, jak podprogramów, 365 00:19:28,750 --> 00:19:32,030 tak, że nie musisz martwić się zbyt wiele o szczegółach, jak się stało. 366 00:19:32,030 --> 00:19:33,480 >> Będziesz miał później dzisiaj kod. 367 00:19:33,480 --> 00:19:37,970 A jeśli chcesz przejrzeć i dowiedzieć się, można zobaczyć je wszystkie. 368 00:19:37,970 --> 00:19:39,890 Ale będziemy rysować płyty na ekranie. 369 00:19:39,890 --> 00:19:43,620 A potem będziemy sprawdzać i zobaczyć, czy mamy zwycięzcę? 370 00:19:43,620 --> 00:19:46,290 Czy ktoś wygrał tę grę? 371 00:19:46,290 --> 00:19:49,260 Jeśli tak, będziemy drukować z wiadomości zwycięstwa. 372 00:19:49,260 --> 00:19:51,680 A my zakończyć grę. 373 00:19:51,680 --> 00:19:54,510 >> Będziemy również sprawdzić i sprawdzić, czy jest remis. 374 00:19:54,510 --> 00:19:56,620 To będzie łatwe, aby zobaczyć, czy jest remis. 375 00:19:56,620 --> 00:20:00,700 Oznacza to, że wszystkie miejsca są zajęte, ale nie było jeszcze zwycięzcą. 376 00:20:00,700 --> 00:20:03,580 Możemy zadeklarować krawat i zrobienia. 377 00:20:03,580 --> 00:20:10,530 Wtedy prawdziwa meat-- jeśli to gracz maszyna, 378 00:20:10,530 --> 00:20:14,120 my to pozwolić Odtwarzacz maszyna do wyszukiwania 379 00:20:14,120 --> 00:20:19,500 poprzez zastosowanie tego algorytmu minimax, aby znaleźć najlepszy ruch, który może to zrobić. 380 00:20:19,500 --> 00:20:22,310 A potem kładziemy pojedynek w górę. 381 00:20:22,310 --> 00:20:27,640 >> W przeciwnym razie, jeśli jest to osoba grająca, będziemy czytać jakieś wejście od człowieka. 382 00:20:27,640 --> 00:20:30,800 A potem, czy to ludzkie graczy lub gracz maszyna, 383 00:20:30,800 --> 00:20:32,800 zrobimy kilka mało bity kontroli błędów, 384 00:20:32,800 --> 00:20:36,910 upewnić się, że pozostaje w granicach rzeczywistych wymiarów tablicy 385 00:20:36,910 --> 00:20:40,040 że mamy, upewnij się, że przestrzeń jest pusta, 386 00:20:40,040 --> 00:20:43,570 że nikt nie jest umieścić Kawałek tam już. 387 00:20:43,570 --> 00:20:45,810 A potem po prostu umieścić kawałek na płycie, 388 00:20:45,810 --> 00:20:51,550 zmienić odtwarzacz do następnej warstwy, a zwiększyć liczbę porusza się stało. 389 00:20:51,550 --> 00:20:54,090 >> To główny pętli na nasza gra tic-tac-toe. 390 00:20:54,090 --> 00:20:57,000 391 00:20:57,000 --> 00:21:02,340 Minimax, to jest dokładnie to, algorytm, że my wcześniej. 392 00:21:02,340 --> 00:21:04,710 Jedynym regulacji, które zrobiliśmy tak, że 393 00:21:04,710 --> 00:21:07,290 może odgrywać większa płyty wymiarowe to mamy 394 00:21:07,290 --> 00:21:11,070 przechowywane ten dodatkowy parametr zwany głębokość. 395 00:21:11,070 --> 00:21:14,870 I głębokość tylko mówi, czy jestem wyszukiwanie w dół przez tego drzewa 396 00:21:14,870 --> 00:21:19,022 a ja się tak daleko w dół poza pewnej głębokości poziomu 397 00:21:19,022 --> 00:21:20,730 że po prostu nie chcą iść dalej, 398 00:21:20,730 --> 00:21:25,630 Mam zamiar się zatrzymać i po prostu ocenić płytę w tym punkcie. 399 00:21:25,630 --> 00:21:27,310 Będę sprawdzić i zobaczyć, czy jest zwycięzcą. 400 00:21:27,310 --> 00:21:29,240 Jeśli jest zwycięzcą, ja ich zwrotu. 401 00:21:29,240 --> 00:21:31,720 W przeciwnym razie, pójdę przez pętlę. 402 00:21:31,720 --> 00:21:34,380 I powiem, dla wszystkich możliwe lokalizacje 403 00:21:34,380 --> 00:21:38,080 że mogłem być może podjąć jak mój ruch, będę 404 00:21:38,080 --> 00:21:43,760 zbudować hipotetyczny zarząd, który obejmuje mój ruch na tej płycie, 405 00:21:43,760 --> 00:21:45,960 a następnie rekurencyjnie wywołuje Minimax. 406 00:21:45,960 --> 00:21:49,360 407 00:21:49,360 --> 00:21:53,900 >> Jeśli jest to mój ruch, mogę znaleźć taki, który ma największy wynik. 408 00:21:53,900 --> 00:21:58,710 Jeśli jest to posunięcie mojego przeciwnika, znajdziemy ten, który ma minimalny wynik. 409 00:21:58,710 --> 00:22:02,240 A wszystko inne jest tylko rekord prowadzenie. 410 00:22:02,240 --> 00:22:04,789 W porządku, więc zobaczymy ten bieg. 411 00:22:04,789 --> 00:22:06,830 Faktycznie, może się da dostać kilka wolontariuszy 412 00:22:06,830 --> 00:22:09,930 przyjść i grać Kółko i krzyżyk. 413 00:22:09,930 --> 00:22:12,780 [Niesłyszalne] jednym, a jeden więcej, dwa, właśnie tam. 414 00:22:12,780 --> 00:22:13,550 Chodź na górę. 415 00:22:13,550 --> 00:22:19,290 416 00:22:19,290 --> 00:22:23,650 >> Więc idź naprzód i ponownie uruchomić ten całkowicie. 417 00:22:23,650 --> 00:22:24,150 Tak, cześć. 418 00:22:24,150 --> 00:22:24,920 >> PUBLICZNOŚCI: Cześć. 419 00:22:24,920 --> 00:22:25,420 >> GŁOŚNIK: Jak masz na imię? 420 00:22:25,420 --> 00:22:26,086 >> PUBLICZNOŚCI: Gorav. 421 00:22:26,086 --> 00:22:26,840 GŁOŚNIK: Gorav. 422 00:22:26,840 --> 00:22:27,800 >> PUBLICZNOŚCI: Jestem Layla. 423 00:22:27,800 --> 00:22:29,490 >> GŁOŚNIK: A Layla i Layla, przepraszam. 424 00:22:29,490 --> 00:22:30,384 Chodź na górę. 425 00:22:30,384 --> 00:22:32,050 Gorav, będziemy mieć ty pierwszy. 426 00:22:32,050 --> 00:22:37,710 I mam zamiar zapytać się nie strasznie dobry gracz tic-tac-toe. 427 00:22:37,710 --> 00:22:40,130 OK, więc wszystko ciśnienie jest wyłączony na Ciebie. 428 00:22:40,130 --> 00:22:44,660 Zobaczmy jednak, że nasza maszyna Gracz może rzeczywiście zrobić coś inteligentnego. 429 00:22:44,660 --> 00:22:45,310 Więc idź naprzód. 430 00:22:45,310 --> 00:22:49,830 Masz zamiar wpisać które koordynują chcesz umieścić X w. 431 00:22:49,830 --> 00:22:55,170 A0, OK, a maszyna poszła i od razu umieścić swoje piętno na A1. 432 00:22:55,170 --> 00:22:56,640 >> Umieść O na płycie. 433 00:22:56,640 --> 00:22:58,970 W porządku, teraz iść do przodu. 434 00:22:58,970 --> 00:23:00,193 Gdzie chciałbyś pójść? 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 Nasz zawodnik maszyny podjęła środkowy kwadrat, zablokował Cię. 438 00:23:08,430 --> 00:23:10,320 Tak, że był dobry, mądrą rzeczą na to zrobić. 439 00:23:10,320 --> 00:23:13,430 440 00:23:13,430 --> 00:23:14,250 Masz zablokowane go. 441 00:23:14,250 --> 00:23:15,210 To doskonała. 442 00:23:15,210 --> 00:23:16,390 To wykonuje rzut rożny tam. 443 00:23:16,390 --> 00:23:23,890 444 00:23:23,890 --> 00:23:30,430 >> I to będzie zmuszać do wziąć ostatnia przestrzeń, B0. 445 00:23:30,430 --> 00:23:32,220 A gra kończy się remisem. 446 00:23:32,220 --> 00:23:35,030 Ale grał rozsądny Gra przeciwko tobie, prawda? 447 00:23:35,030 --> 00:23:36,956 Dobrze, dziękuję bardzo, Gorav. 448 00:23:36,956 --> 00:23:40,860 >> [OKLASKI] 449 00:23:40,860 --> 00:23:44,723 >> Dobrze, Layla, jedziemy się gry na Ciebie tutaj. 450 00:23:44,723 --> 00:23:46,940 >> PUBLICZNOŚCI: Och, to świetnie. 451 00:23:46,940 --> 00:23:49,950 >> GŁOŚNIK: Mamy zamiar dać masz cztery czterech Kółko i krzyżyk. 452 00:23:49,950 --> 00:23:54,760 Teraz, cztery koła, trzeba wygrać z czterech z rzędu, a nie trzy w rzędzie. 453 00:23:54,760 --> 00:23:56,135 I to wszystko jest twoje. 454 00:23:56,135 --> 00:24:02,180 455 00:24:02,180 --> 00:24:04,420 Więc Layla wziął D1. 456 00:24:04,420 --> 00:24:11,730 Jesteśmy teraz będzie przestrzegać nasz komputer odtwarzacz tutaj. 457 00:24:11,730 --> 00:24:16,910 Trzy po trzy Kółko i krzyżyk jest rodzaj rzeczy, że jest to łatwe dla nas wszystkich. 458 00:24:16,910 --> 00:24:21,960 Ale to i tak miło zobaczyć Gracz komputerowy podejmowania mądrych posunięć. 459 00:24:21,960 --> 00:24:23,725 Cztery czterech dostaje być trochę trudniejsze. 460 00:24:23,725 --> 00:24:42,960 461 00:24:42,960 --> 00:24:44,230 >> Ładnie wykonane. 462 00:24:44,230 --> 00:24:46,210 W porządku, więc Layla pod wykończone. 463 00:24:46,210 --> 00:24:48,270 Aha, i nie powinno się skończyć. 464 00:24:48,270 --> 00:24:51,870 Ale zróbmy jeszcze tutaj. 465 00:24:51,870 --> 00:24:53,480 Więc Layla, dziękuję. 466 00:24:53,480 --> 00:24:55,112 Ładnie wykonane. 467 00:24:55,112 --> 00:24:57,517 >> [OKLASKI] 468 00:24:57,517 --> 00:25:00,410 469 00:25:00,410 --> 00:25:04,750 >> Tak więc nasz zawodnik tic-tac-toe idzie przez i znajduje pozycje, 470 00:25:04,750 --> 00:25:07,040 rozwiązuje je za pomocą tego Minimax. 471 00:25:07,040 --> 00:25:08,990 A ja miałem ustawienie głębokości na tym tak, że 472 00:25:08,990 --> 00:25:11,010 nie byłoby to zbyt szybko, pewnie dlatego 473 00:25:11,010 --> 00:25:16,790 Layla była w stanie go ładnie do przodu jak ona, i zrobił bardzo dobrze. 474 00:25:16,790 --> 00:25:20,450 Ale te systemy, które po prostu przejść i brute force 475 00:25:20,450 --> 00:25:23,870 głębiej i głębiej i głębiej, i zachować znalezienia rozwiązania 476 00:25:23,870 --> 00:25:29,890 że trzeba te rodzaje systemów są bardzo skuteczne w nich dobrze, 477 00:25:29,890 --> 00:25:32,700 standardowe gry planszowe. 478 00:25:32,700 --> 00:25:37,060 >> I rzeczywiście, gdy patrzymy na trzy przez trzy Kółko i krzyżyk gra, 479 00:25:37,060 --> 00:25:40,040 to jest po prostu rozwiązać problemu. 480 00:25:40,040 --> 00:25:45,430 I to jest wspaniałe schemat Randall Munroe co z xkcd, 481 00:25:45,430 --> 00:25:52,130 pokazano które poruszają zalecana podjąć, biorąc pod uwagę ruchy przeciwnika. 482 00:25:52,130 --> 00:25:56,420 To jest coś, co się dało łatwo określić z wyprzedzeniem. 483 00:25:56,420 --> 00:26:00,180 Ale co się stanie, jak dostać się do bardziej bardziej złożone gry, skomplikowanych gier, 484 00:26:00,180 --> 00:26:05,690 gdzie istnieje większe płyty, bardziej możliwości, głębiej strategia? 485 00:26:05,690 --> 00:26:09,660 >> Okazuje się, że to brute force szukając wciąż 486 00:26:09,660 --> 00:26:14,150 nie dość dobrze, z wyjątkiem kiedy dojdziesz do punktu, 487 00:26:14,150 --> 00:26:19,230 w przypadku, gdy drzewo jest tak duża, że nie może reprezentować wszystko. 488 00:26:19,230 --> 00:26:22,370 489 00:26:22,370 --> 00:26:28,280 Kiedy nie można obliczyć całe drzewo, gdy nie możesz iść do przodu i Push 490 00:26:28,280 --> 00:26:32,204 się do punktu, gdzie ty zdobyć całe drzewo w pamięci, 491 00:26:32,204 --> 00:26:34,370 czy można go dostać w pamięci i będzie po prostu 492 00:26:34,370 --> 00:26:39,200 zabierze Cię zbyt długo, aby przeszukać to, co musisz zrobić coś inteligentniejszego. 493 00:26:39,200 --> 00:26:42,620 494 00:26:42,620 --> 00:26:46,450 >> Aby to zrobić, musisz zrobić dwie rzeczy. 495 00:26:46,450 --> 00:26:49,030 Po pierwsze, trzeba znaleźć jakiś sposób ograniczając głębokość. 496 00:26:49,030 --> 00:26:50,370 Cóż, to jest OK. 497 00:26:50,370 --> 00:26:55,740 Możemy znaleźć jakieś fajne, niezbędne minimum i powiedzieć, można tylko iść tak głęboko. 498 00:26:55,740 --> 00:27:00,890 Ale gdy to zrobisz, to znaczy ci mają te częściowo niekompletne deski. 499 00:27:00,890 --> 00:27:04,770 I masz do wyboru, lubię to częściowo niepełne wyżywienie, 500 00:27:04,770 --> 00:27:08,600 Ten częściowo niekompletne lub wyżywienie? 501 00:27:08,600 --> 00:27:11,910 >> A w naszych czterech przez cztery gra tic-tac-toe, 502 00:27:11,910 --> 00:27:15,240 nasz gracz komputerowy zsiadł na dół i powiedział, 503 00:27:15,240 --> 00:27:16,800 Mam dwie różne płyty. 504 00:27:16,800 --> 00:27:17,940 Żaden z nich nie jest zwycięstwo. 505 00:27:17,940 --> 00:27:19,120 Żaden z nich nie jest strata. 506 00:27:19,120 --> 00:27:22,070 Ani jeden remis. 507 00:27:22,070 --> 00:27:24,100 Jak wybrać między nimi? 508 00:27:24,100 --> 00:27:26,200 I nie mają inteligentny sposób na osiągnięcie tego. 509 00:27:26,200 --> 00:27:28,910 510 00:27:28,910 --> 00:27:32,850 >> Widzimy tego rodzaju Ocena zdarzają się cały czas 511 00:27:32,850 --> 00:27:35,290 jak dostać się do bardziej skomplikowanych gier. 512 00:27:35,290 --> 00:27:37,600 Szachy to świetny przykład. 513 00:27:37,600 --> 00:27:41,550 W szachy, musimy najpierw wszystkim, większy pokładzie. 514 00:27:41,550 --> 00:27:43,370 Mamy znacznie więcej kawałków. 515 00:27:43,370 --> 00:27:47,930 I rozmieszczenie tych elementów i sposób, że te kawałki przenieść 516 00:27:47,930 --> 00:27:50,370 ma zasadnicze znaczenie. 517 00:27:50,370 --> 00:27:53,700 Więc jeśli chcę korzystać Minimax, Muszę być w stanie określić, 518 00:27:53,700 --> 00:27:58,240 i powiedzieć, to forum, gdzie nikt nie wygrywa się lub przegrywa jeszcze, 519 00:27:58,240 --> 00:28:04,310 jest w jakiś sposób lepszy niż ten drugi wyżywienie, gdzie nikt nie wygrywa się lub przegrywa. 520 00:28:04,310 --> 00:28:06,740 >> Aby to zrobić, mogę zrobić rzeczy takie jak I może po prostu 521 00:28:06,740 --> 00:28:10,787 policzyć, ile sztuk mam i ile sztuk masz? 522 00:28:10,787 --> 00:28:12,870 Albo może dać różne szt różne punkty. 523 00:28:12,870 --> 00:28:14,420 Moja królowa jest warte 20 punktów. 524 00:28:14,420 --> 00:28:16,500 Twój pionek jest wart jeden punkt. 525 00:28:16,500 --> 00:28:18,920 Kto ma więcej punktów w sumie? 526 00:28:18,920 --> 00:28:22,300 Albo mógłbym rozważyć takie rzeczy jak, kto ma lepszą pozycję wyżywienie? 527 00:28:22,300 --> 00:28:26,820 Którego tura jest obok, wszystko, co się da 528 00:28:26,820 --> 00:28:31,220 należy ocenić dokładniej która z tych możliwości 529 00:28:31,220 --> 00:28:34,660 jest lepiej bez wyczerpująco rozważa 530 00:28:34,660 --> 00:28:36,565 każdy ruch, który może przyjść później. 531 00:28:36,565 --> 00:28:39,740 532 00:28:39,740 --> 00:28:45,130 >> Teraz do tej pracy, jedna z rzeczy, która jest 533 00:28:45,130 --> 00:28:48,680 stanie się naprawdę ważne dla nas nie tylko w ruchu prosto 534 00:28:48,680 --> 00:28:53,720 do określonej głębokości limitu, ale jest w stanie powiedzieć, 535 00:28:53,720 --> 00:28:59,380 jeden z tych pomysłów, które mam mają się tak źle, że jest to 536 00:28:59,380 --> 00:29:02,280 nie warto zastanowić się, wszystkie możliwe sposoby 537 00:29:02,280 --> 00:29:06,680 że rzeczy mogą iść coraz gorzej. 538 00:29:06,680 --> 00:29:12,760 Aby to zrobić, dodamy do minimax zasada zwana alf-beta. 539 00:29:12,760 --> 00:29:16,340 I alfa-beta, mówi, jeśli masz zły pomysł, 540 00:29:16,340 --> 00:29:22,840 nie trać czasu na próby dowiedzieć się dokładnie, jak źle jest. 541 00:29:22,840 --> 00:29:24,990 >> Więc tutaj jest to, co mamy zamiar zrobić. 542 00:29:24,990 --> 00:29:28,620 Zamierzamy podjąć takie same Zasady, które mieliśmy wcześniej, 543 00:29:28,620 --> 00:29:32,200 tego samego typu minimax poszukiwań, tylko my jesteśmy 544 00:29:32,200 --> 00:29:37,570 będzie śledzić nie tylko z Rzeczywiste wartości, które posiadamy, ale będziesz 545 00:29:37,570 --> 00:29:41,440 śledzić najlepsze możliwe Wartość że mogę dostać, 546 00:29:41,440 --> 00:29:45,700 a najgorsze możliwe Wynik mogłem. 547 00:29:45,700 --> 00:29:50,470 I za każdym razem, najgorsze możliwe rzeczą szuka prawdopodobne, 548 00:29:50,470 --> 00:29:52,694 Będę zrezygnować z części drzewa. 549 00:29:52,694 --> 00:29:54,610 A ja nawet nie przeszkadza patrząc na to już. 550 00:29:54,610 --> 00:29:57,680 551 00:29:57,680 --> 00:30:02,600 >> W porządku, więc sobie wyobrazić, że możemy zacząć z tego samego drzewa dokładnym gry. 552 00:30:02,600 --> 00:30:05,200 A teraz mamy zamiar iść znowu w dół, w dół 553 00:30:05,200 --> 00:30:07,200 do tego w lewym dolnym rogu. 554 00:30:07,200 --> 00:30:11,180 I w tym dolnym lewym rogu, mamy wyglądać i oceniamy ten dział. 555 00:30:11,180 --> 00:30:15,700 Może to cztery czterech Kółko i krzyżyk wyżywienie, a może to szachownicy. 556 00:30:15,700 --> 00:30:18,620 Ale spójrz na to, i oceniamy Opisz i otrzymujemy wartość ośmiu. 557 00:30:18,620 --> 00:30:22,290 558 00:30:22,290 --> 00:30:28,030 >> W tym momencie wiemy, że mamy zamiar uzyskać co najmniej 559 00:30:28,030 --> 00:30:32,380 osiem punktów z tej dolnej decyzji. 560 00:30:32,380 --> 00:30:36,620 Nie ma znaczenia, co druga dwa to, że siedem i dwa. 561 00:30:36,620 --> 00:30:38,580 Mogą być dowolne wartości chcieli być. 562 00:30:38,580 --> 00:30:41,279 Mamy zamiar dostać się na najmniej osiem punktów. 563 00:30:41,279 --> 00:30:43,070 W porządku, ale mogliśmy iść dalej i sprawdzić. 564 00:30:43,070 --> 00:30:45,080 Może któryś z nich jest lepszy niż osiem. 565 00:30:45,080 --> 00:30:46,000 >> Patrzymy na siedmiu. 566 00:30:46,000 --> 00:30:46,910 Czy to jest lepsze niż osiem? 567 00:30:46,910 --> 00:30:48,680 Nie, to nie zmienia Naszym zdaniem w ogóle. 568 00:30:48,680 --> 00:30:49,460 Patrzymy na dwóch. 569 00:30:49,460 --> 00:30:50,543 Czy to jest lepsze niż osiem? 570 00:30:50,543 --> 00:30:52,580 Nie, to nie zmienia Naszym zdaniem w ogóle. 571 00:30:52,580 --> 00:30:55,480 Więc teraz wiemy, że wyczerpane zostały wszystkie tam możliwości. 572 00:30:55,480 --> 00:30:58,330 Nie dostaniesz nic lepszego niż osiem. 573 00:30:58,330 --> 00:31:01,310 Jedziemy, aby uzyskać dokładnie osiem. 574 00:31:01,310 --> 00:31:03,825 >> I tak możemy zmienić ten węzeł i powiedzmy, że jest już pewne. 575 00:31:03,825 --> 00:31:07,010 576 00:31:07,010 --> 00:31:10,270 Idziemy w górę o jeden poziom wyżej, że. 577 00:31:10,270 --> 00:31:13,820 A teraz coś wiemy o tym poziomie minimalizacji. 578 00:31:13,820 --> 00:31:18,560 Wiemy, że nigdy nie dostaniesz więcej niż osiem punktów, jeśli idziemy w dół 579 00:31:18,560 --> 00:31:20,910 że kierunek. 580 00:31:20,910 --> 00:31:22,980 Bo nawet jeśli ci Pozostałe dwie gałęzie okazują 581 00:31:22,980 --> 00:31:26,170 być fantastyczne i warto tysiące punktów każda, 582 00:31:26,170 --> 00:31:31,666 nasz przeciwnik da nam Minimalna, i daje nam osiem. 583 00:31:31,666 --> 00:31:32,790 Dobrze, dobrze, zobaczmy. 584 00:31:32,790 --> 00:31:35,190 Będziemy iść dalej tą drogą. 585 00:31:35,190 --> 00:31:38,490 Schodzimy do tej środku po lewej stronie. 586 00:31:38,490 --> 00:31:40,560 Patrzymy w dół i widzimy tam jest dziewięć. 587 00:31:40,560 --> 00:31:45,590 Wiemy, że mamy zamiar się co najmniej dziewięć punktów przez schodząc 588 00:31:45,590 --> 00:31:47,720 że środkowa droga. 589 00:31:47,720 --> 00:31:52,110 I w tym momencie, możemy po prostu wstrzymać. 590 00:31:52,110 --> 00:31:56,910 I można powiedzieć, słuchaj, wiedzieć na poziomie powyżej, 591 00:31:56,910 --> 00:32:01,160 Mam zamiar się nie więcej niż osiem wskazuje, przechodząc w dół w tym kierunku. 592 00:32:01,160 --> 00:32:05,670 Ale gdybym poszedł na środku ścieżka zamiast lewej ścieżce 593 00:32:05,670 --> 00:32:08,980 Chciałbym uzyskać co najmniej dziewięć punktów. 594 00:32:08,980 --> 00:32:13,590 >> Mój przeciwnik nie będzie pozwól mi iść tą drogę pośrednią. 595 00:32:13,590 --> 00:32:14,650 Oni się wybrać. 596 00:32:14,650 --> 00:32:18,140 I zamierzamy wybrać Droga w lewo w kierunku ośmiu, 597 00:32:18,140 --> 00:32:23,650 a nie na środku kierunku co jest co najmniej dziewięć punktów. 598 00:32:23,650 --> 00:32:25,334 Więc w tym momencie, ja zatrzymać. 599 00:32:25,334 --> 00:32:26,500 I powiem, że wiesz, co? 600 00:32:26,500 --> 00:32:29,990 I nie trzeba szukać więcej w tym kierunku. 601 00:32:29,990 --> 00:32:32,270 Bo nigdy nie zamierzam się tam dostać. 602 00:32:32,270 --> 00:32:36,660 >> Mogę pominąć tego jednego, i mogę przejść nad tym sześciu, 603 00:32:36,660 --> 00:32:39,720 dlatego, że nigdy nie zdarzy. 604 00:32:39,720 --> 00:32:42,470 Więc pójdę na dół i będę rozważyć kolejną możliwość. 605 00:32:42,470 --> 00:32:44,830 Idę tam i mówię, widzę dwa. 606 00:32:44,830 --> 00:32:47,125 Wiem, czy mogę tu jestem dostanie co najmniej dwa. 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 I wracamy. 610 00:32:51,520 --> 00:32:52,440 Widzę cztery. 611 00:32:52,440 --> 00:32:54,920 Wiem, że będzie się co najmniej cztery. 612 00:32:54,920 --> 00:32:57,200 Jest jeszcze wiele między cztery i osiem lat, choć. 613 00:32:57,200 --> 00:32:58,454 Więc dalej. 614 00:32:58,454 --> 00:32:59,870 Patrzę i widzę, jest jedna. 615 00:32:59,870 --> 00:33:01,614 W porządku, wiem, jeśli Ja się na to rozwiązanie, 616 00:33:01,614 --> 00:33:03,280 Mam zamiar być w stanie wybrać cztery. 617 00:33:03,280 --> 00:33:06,540 618 00:33:06,540 --> 00:33:08,980 Co mój przeciwnik zrobi? 619 00:33:08,980 --> 00:33:12,310 Między czymś, co daje mi osiem, coś, co daje mi cztery, 620 00:33:12,310 --> 00:33:14,730 i coś, daje mi co najmniej dziewięć, 621 00:33:14,730 --> 00:33:17,550 dobrze, że zamierza dać mi cztery. 622 00:33:17,550 --> 00:33:20,110 I wiem, że teraz u bardzo góry, idę 623 00:33:20,110 --> 00:33:23,145 aby być w stanie uzyskać co najmniej czterech punktów na tej grze. 624 00:33:23,145 --> 00:33:27,030 625 00:33:27,030 --> 00:33:30,900 >> Cała idea alfa-beta jest odcięcie częściom drzewa tak 626 00:33:30,900 --> 00:33:32,530 że nie patrzę na nich więcej. 627 00:33:32,530 --> 00:33:35,964 Ale to wciąż wygląda jak byłem patrząc na dużym drzewie. 628 00:33:35,964 --> 00:33:36,880 Trzymajmy spada. 629 00:33:36,880 --> 00:33:38,305 Pójdziemy w dół następny teraz. 630 00:33:38,305 --> 00:33:39,680 Na dole, mogę znaleźć jednego. 631 00:33:39,680 --> 00:33:41,030 Wiem, że będzie się co najmniej jeden. 632 00:33:41,030 --> 00:33:41,690 Ciągle szuka. 633 00:33:41,690 --> 00:33:42,625 >> I znaleźć trzy. 634 00:33:42,625 --> 00:33:44,250 Wiem, że będzie się co najmniej trzy. 635 00:33:44,250 --> 00:33:44,840 I wracamy. 636 00:33:44,840 --> 00:33:45,660 I znaleźć pięć. 637 00:33:45,660 --> 00:33:49,760 Wiem, że dostanie pięć jeśli dostanę w tej ścieżce. 638 00:33:49,760 --> 00:33:52,580 I wiem też, czym że mój przeciwnik, jeśli I 639 00:33:52,580 --> 00:33:55,510 wybrać środek trzy duże możliwości wyboru, 640 00:33:55,510 --> 00:34:01,440 on będzie mi dać coś, co jest pięć lub mniej. 641 00:34:01,440 --> 00:34:02,150 >> OK. 642 00:34:02,150 --> 00:34:03,400 Mogę iść dalej istnieje. 643 00:34:03,400 --> 00:34:06,470 Mogę spojrzeć w dół, a ja Można powiedzieć, co mam 644 00:34:06,470 --> 00:34:08,239 dostać, jeśli pójdę na dół środku drogi? 645 00:34:08,239 --> 00:34:09,909 Mam zamiar się dobrze, trzy nie. 646 00:34:09,909 --> 00:34:12,080 Mam zamiar coś to co najmniej trzy. 647 00:34:12,080 --> 00:34:16,030 Jest jeszcze rzeczy, między trzy i pięć lat, więc szukać dalej. 648 00:34:16,030 --> 00:34:20,203 Och, dziewięć, będę na pewno się, że w ciągu trzech. 649 00:34:20,203 --> 00:34:22,744 Mam zamiar uzyskać co najmniej dziewięć jeśli iść tą drogę pośrednią. 650 00:34:22,744 --> 00:34:25,530 651 00:34:25,530 --> 00:34:31,010 >> Teraz mój przeciwnik zatrzymuje się i mówi: patrzeć, nie ma sensu już. 652 00:34:31,010 --> 00:34:33,669 Wiem, że mój minimalizacja przeciwnik, jest 653 00:34:33,669 --> 00:34:36,210 zamiar dać mi coś, co jest mniejsza lub równa pięć, 654 00:34:36,210 --> 00:34:39,030 a nie rzecz, która większy niż lub równy dziewięciu. 655 00:34:39,030 --> 00:34:39,530 Ja zatrzymuję. 656 00:34:39,530 --> 00:34:40,779 Nie patrzę na to bardziej. 657 00:34:40,779 --> 00:34:43,280 I wracamy. 658 00:34:43,280 --> 00:34:44,850 >> Patrzę na ten jeden. 659 00:34:44,850 --> 00:34:46,370 Do dołu, znajdę sześć. 660 00:34:46,370 --> 00:34:50,040 Wiem, że będzie się co najmniej sześć. 661 00:34:50,040 --> 00:34:53,130 I co mogę zrobić? 662 00:34:53,130 --> 00:34:54,877 Mogę przestać. 663 00:34:54,877 --> 00:34:57,460 Ponieważ nie jest to wybór pomiędzy coś, co jest co najmniej sześć 664 00:34:57,460 --> 00:34:59,250 i coś, co jest mniej niż pięć, on 665 00:34:59,250 --> 00:35:02,570 da mi rzeczy to mniej niż pięć. 666 00:35:02,570 --> 00:35:04,779 I teraz wiem, że będę aby uzyskać dokładnie taki wybór. 667 00:35:04,779 --> 00:35:06,195 Zamierzam się, że pięć wyboru. 668 00:35:06,195 --> 00:35:08,980 669 00:35:08,980 --> 00:35:10,010 >> Wracam do góry. 670 00:35:10,010 --> 00:35:11,450 Które mam zamiar wybrać coś 671 00:35:11,450 --> 00:35:14,449 to jest większa niż lub równa cztery, lub coś, co jest równa pięć? 672 00:35:14,449 --> 00:35:17,140 Mam zamiar wziąć coś to jest co najmniej pięć. 673 00:35:17,140 --> 00:35:20,490 Idę w dół ostatnią drogę, wszystko aż do dna. 674 00:35:20,490 --> 00:35:21,260 Tam jest jedna. 675 00:35:21,260 --> 00:35:23,410 OK, przynajmniej mam zamiar dostać jeden punkt. 676 00:35:23,410 --> 00:35:24,427 I wracamy. 677 00:35:24,427 --> 00:35:25,760 Dwa, och, to nie jedna. 678 00:35:25,760 --> 00:35:27,100 Mam zamiar dostać co najmniej dwa. 679 00:35:27,100 --> 00:35:28,610 I znaleźć trzy. 680 00:35:28,610 --> 00:35:31,450 Wiem, że będzie się trzy. 681 00:35:31,450 --> 00:35:34,690 >> I punkt wyżej, że, mój przeciwnik będzie 682 00:35:34,690 --> 00:35:38,540 dać mi coś, co jest mniejsza lub równa trzy. 683 00:35:38,540 --> 00:35:40,940 A teraz mogę przestać. 684 00:35:40,940 --> 00:35:46,290 Ponieważ w wybór między mną jest w stanie uzyskać pięć i mojego przeciwnika 685 00:35:46,290 --> 00:35:52,290 daje mi coś mniej niż trzy, Ja zawsze zajmie to pięć. 686 00:35:52,290 --> 00:35:56,810 Więc nie ocenia, że Dolna część drzewa w ogóle. 687 00:35:56,810 --> 00:35:59,470 >> Teraz może się to wydawać niewielkie. 688 00:35:59,470 --> 00:36:03,630 Ale kiedy małe kawałki arytmetyki, większe i mniejsze niż 689 00:36:03,630 --> 00:36:10,640 może odciąć całe części Drzewo to rośnie w postępie geometrycznym, 690 00:36:10,640 --> 00:36:14,280 która prowadzi do ogromnego kwota oszczędności, oszczędności 691 00:36:14,280 --> 00:36:17,630 które są na tyle duże, że może zacząć grać konkurencyjnie 692 00:36:17,630 --> 00:36:21,330 przy bardziej skomplikowanych gier. 693 00:36:21,330 --> 00:36:27,030 >> Dobrze, jeśli spojrzymy na wielkość i złożoność różnych gier, 694 00:36:27,030 --> 00:36:29,470 Kółko i krzyżyk był nasz prosty przykład. 695 00:36:29,470 --> 00:36:32,150 Mamy małą deskę, trzy przez trzy. 696 00:36:32,150 --> 00:36:36,030 Dostajemy co najwyżej średnio około czterech różnych wyborów 697 00:36:36,030 --> 00:36:38,440 jak przejść grę. 698 00:36:38,440 --> 00:36:42,720 Mamy gdzieś około 10 do piąty możliwe różne liście. 699 00:36:42,720 --> 00:36:45,200 I budowanie Kółko i krzyżyk Gracz, dobrze, po prostu to zrobił. 700 00:36:45,200 --> 00:36:47,460 To łatwe. 701 00:36:47,460 --> 00:36:49,890 >> Jeśli idziemy do czegoś więcej skomplikowane, jak Connect Four. 702 00:36:49,890 --> 00:36:53,170 Pamiętasz to gra, w której upadłego małe żetony w? 703 00:36:53,170 --> 00:36:58,490 Jest to sześć na siedem wyżywienie, nie, że znacznie większy, wciąż 704 00:36:58,490 --> 00:37:00,770 ma w przybliżeniu ten sam rozgałęzienia czynnikiem Kółko i krzyżyk. 705 00:37:00,770 --> 00:37:05,410 Mam około czterech wyborów gdzie mogę umieścić rzeczy w. 706 00:37:05,410 --> 00:37:10,760 Ale teraz, mam dużo więcej prowadzi, 10 do 21 potęgi. 707 00:37:10,760 --> 00:37:14,440 To jest coś, co jest proste wystarczy, że go rozwiązać od razu. 708 00:37:14,440 --> 00:37:17,560 >> Warcaby, bardziej complex-- was dostał osiem przez osiem pokładzie. 709 00:37:17,560 --> 00:37:20,570 Jesteś tylko w połowie je w każdej chwili, choć. 710 00:37:20,570 --> 00:37:24,930 Masz rozgałęzienia Czynnikiem, który jest około 2,8. 711 00:37:24,930 --> 00:37:28,160 Cóż, mamy kilka porusza można wziąć. 712 00:37:28,160 --> 00:37:33,870 Masz około 10 do 31 liści, większe i większe, i większe przestrzenie. 713 00:37:33,870 --> 00:37:37,340 Jak mam przeszukiwać te coraz większe przestrzenie, 714 00:37:37,340 --> 00:37:42,220 wtedy takie rzeczy jak alfa-beta i jest w stanie odciąć całe oddziały 715 00:37:42,220 --> 00:37:44,420 staje się niezbędne. 716 00:37:44,420 --> 00:37:47,440 >> Teraz, warcaby było dość łatwe w 1992 roku. 717 00:37:47,440 --> 00:37:51,400 Program komputerowy o nazwie Chinook pokonać warcaby świata 718 00:37:51,400 --> 00:37:53,590 mistrz, Marion Tinsley. 719 00:37:53,590 --> 00:37:57,260 I od tego czasu nie ma Mistrz ma ludzki gracz 720 00:37:57,260 --> 00:38:02,290 w stanie pokonać najlepszych systemy obliczeniowe. 721 00:38:02,290 --> 00:38:06,570 Jeśli spojrzymy na coś takiego jak szachy, teraz znowu mamy osiem przez osiem pokładzie. 722 00:38:06,570 --> 00:38:09,870 Mamy jednak dużo bardziej skomplikowana sztuk, znacznie bardziej skomplikowane ruchy. 723 00:38:09,870 --> 00:38:14,610 Mamy współczynnik rozgałęzienia o 35, 35 możliwe ruchy na średniej 724 00:38:14,610 --> 00:38:20,030 że mogę wziąć, a stan Przestrzeń, liczba liści 725 00:38:20,030 --> 00:38:28,950 która jest uprawiana do 10 do 123. władzy, ogromna liczba możliwości. 726 00:38:28,950 --> 00:38:35,570 >> Nawet jeszcze, nowoczesne procesory są w stanie to zrobić skutecznie. 727 00:38:35,570 --> 00:38:43,900 W 1995 roku, a następnie w 1997 roku, komputerem Program o nazwie Deep Blue zbudowany przez IBM 728 00:38:43,900 --> 00:38:49,601 które prowadził na gigantycznym superkomputer pokonać aktualnego mistrza świata, 729 00:38:49,601 --> 00:38:50,225 Garri Kasparow. 730 00:38:50,225 --> 00:38:54,000 731 00:38:54,000 --> 00:38:56,650 To był punkt zwrotny. 732 00:38:56,650 --> 00:39:00,620 Dziś jednak, że sama obróbka Moc siedzi na moim MacBooku. 733 00:39:00,620 --> 00:39:04,180 734 00:39:04,180 --> 00:39:06,440 >> Szybkość przetwarzania utrzymuje coraz szybciej i szybciej. 735 00:39:06,440 --> 00:39:09,500 Możemy ocenić bardziej Płyty szybciej i szybciej. 736 00:39:09,500 --> 00:39:14,550 Ale co ważniejsze, mamy lepsze funkcje oceny i lepiej przycinanie 737 00:39:14,550 --> 00:39:15,460 metody. 738 00:39:15,460 --> 00:39:19,560 Więc możemy przeszukać Przestrzeń bardziej kompleksowo. 739 00:39:19,560 --> 00:39:22,350 Największy na pokładzie gry, które możemy myśleć, 740 00:39:22,350 --> 00:39:26,310 coś Go to dostał 19 przez 19 planszę, 741 00:39:26,310 --> 00:39:32,490 teraz nagle, że jesteśmy poza punkt gdzie systemy obliczeniowe mogą wygrać. 742 00:39:32,490 --> 00:39:34,530 Nie ma obliczeniowa System tam 743 00:39:34,530 --> 00:39:38,880 że może pokonać profesjonalnego odtwarzacza Go. 744 00:39:38,880 --> 00:39:45,000 Najlepsze systemy dziś Ranking go o rodzaj dobrym poziomie amatorskim. 745 00:39:45,000 --> 00:39:49,285 Tak więc jest jeszcze trochę się tam, że nie można się jeszcze. 746 00:39:49,285 --> 00:39:51,840 747 00:39:51,840 --> 00:39:55,360 >> W porządku, to tradycyjne gry planszowe, 748 00:39:55,360 --> 00:39:58,560 Te rodzaje systemów, w których budować ten Minimax, czy to ma 749 00:39:58,560 --> 00:40:06,300 alfa-beta lub nie, algorytmy te pracują ponieważ istnieją pewne ograniczenia. 750 00:40:06,300 --> 00:40:08,520 Mamy doskonałą informację o świecie. 751 00:40:08,520 --> 00:40:11,690 Wiemy, gdzie wszystkie elementy są. 752 00:40:11,690 --> 00:40:13,570 Świat jest statyczna. 753 00:40:13,570 --> 00:40:16,220 Nikt nie robi, aby przesunąć kawałki wokół, a ja jestem 754 00:40:16,220 --> 00:40:20,640 siedzi tam myśląc, biorąc moja kolej. 755 00:40:20,640 --> 00:40:23,140 Jest takie miejsce akcji to dyskretny. 756 00:40:23,140 --> 00:40:26,900 Mogę umieścić tutaj mój pionek, czy mogę umieścić tutaj mój pionek. 757 00:40:26,900 --> 00:40:30,520 Nie wolno mi umieścić mój pionek na linia między dwoma kwadratami. 758 00:40:30,520 --> 00:40:34,430 759 00:40:34,430 --> 00:40:36,520 >> I wreszcie działania są deterministyczne. 760 00:40:36,520 --> 00:40:39,790 Wiem, że jeśli powiem, gawron do rycerza trzech, 761 00:40:39,790 --> 00:40:44,660 moja wieża ma skończyć się w rycerza trzy, tak długo, jak jest to ważny pojedynek. 762 00:40:44,660 --> 00:40:47,830 Nie ma wątpliwości o tym. 763 00:40:47,830 --> 00:40:52,490 Teraz, jak idę do więcej różne rodzaje gier, 764 00:40:52,490 --> 00:40:55,960 Musimy przełamać te założenia. 765 00:40:55,960 --> 00:41:00,020 >> Co, jeśli pójdę do czegoś jak klasycznych gier wideo? 766 00:41:00,020 --> 00:41:04,180 Oto wybór wideo gry z Atari 2600. 767 00:41:04,180 --> 00:41:05,180 Czego mam się tam? 768 00:41:05,180 --> 00:41:08,440 Mam Frogger, przestrzeń Invaders, Pułapka, i Pac-Man. 769 00:41:08,440 --> 00:41:11,290 770 00:41:11,290 --> 00:41:14,840 Jakie rodzaje środowisk mam tu teraz? 771 00:41:14,840 --> 00:41:16,900 Które z tych założeń muszę złamać? 772 00:41:16,900 --> 00:41:19,410 773 00:41:19,410 --> 00:41:21,570 >> Cóż, to zależy od gry. 774 00:41:21,570 --> 00:41:28,170 Mogłem grać w szachy na 2600, a to będzie tak jak to było wcześniej. 775 00:41:28,170 --> 00:41:33,020 Dla większości z tych systemów nie jest kompletną wiedzę o świecie. 776 00:41:33,020 --> 00:41:36,300 Jest całkowicie deterministyczne działania. 777 00:41:36,300 --> 00:41:38,330 Ale zwykle, na świecie już nie statyczne. 778 00:41:38,330 --> 00:41:41,970 Oznacza to, że podczas gdy ja siedzę tam czeka, coś się porusza. 779 00:41:41,970 --> 00:41:44,320 Duchy przychodzą po mnie. 780 00:41:44,320 --> 00:41:46,570 Skorpion jest po mnie pod spodem. 781 00:41:46,570 --> 00:41:48,880 Przez najeźdźcami z kosmosu coraz bliżej. 782 00:41:48,880 --> 00:41:54,020 783 00:41:54,020 --> 00:41:55,510 Jak dobrze możemy zrobić wobec nich? 784 00:41:55,510 --> 00:41:58,640 785 00:41:58,640 --> 00:42:02,790 >> Kilka lat temu, Google był projekt o nazwie 786 00:42:02,790 --> 00:42:12,030 DeepMind, gdzie szkoleni komputera Program do gry Atari 2600 gier. 787 00:42:12,030 --> 00:42:16,120 A jeśli uważasz, że to nie jest poważna biznesowych, wyniki ich badań 788 00:42:16,120 --> 00:42:19,920 zostały opublikowane w Nature, więc po prostu tak dobre, publikacja 789 00:42:19,920 --> 00:42:22,500 jak można ewentualnie dostać. 790 00:42:22,500 --> 00:42:24,340 A oto, jak dobrze wykonana. 791 00:42:24,340 --> 00:42:29,220 >> Mają algorytm, który siedział i patrzył tylko wejść na ekranie. 792 00:42:29,220 --> 00:42:34,080 To ma żadnych instrukcji w ogóle o zasadach gry. 793 00:42:34,080 --> 00:42:42,610 A to miał dowiedzieć się, oparła swoją ocenę, jak dobrze to robi. 794 00:42:42,610 --> 00:42:46,560 Był to system, który stosuje się coś nazywa uczenie zbrojenia. 795 00:42:46,560 --> 00:42:48,380 To znaczy, że spojrzał na jego wynik. 796 00:42:48,380 --> 00:42:51,620 A jeśli to ma dobrą ocenę, to powiedział, Należy Pamiętam te rzeczy. 797 00:42:51,620 --> 00:42:53,310 I zrobić te ponownie. 798 00:42:53,310 --> 00:42:56,450 A jeśli to ma niską ocenę, to powiedział, Nie powinienem znowu robić te rzeczy. 799 00:42:56,450 --> 00:42:59,750 800 00:42:59,750 --> 00:43:03,430 >> Jest to wydajność z tych przeszkolonych systemów 801 00:43:03,430 --> 00:43:07,490 mogą grać dla Kilka godzin w każdej grze, 802 00:43:07,490 --> 00:43:12,490 porównywana z profesjonalnych graczy. 803 00:43:12,490 --> 00:43:19,670 Więc dla wszystkich gier, które są Po lewej stronie tej linii, 804 00:43:19,670 --> 00:43:25,920 Ten samouk program komputerowy przewyższyła profesjonalnych graczy. 805 00:43:25,920 --> 00:43:29,690 A za wszystko do prawo, profesjonalni gracze 806 00:43:29,690 --> 00:43:30,920 wciąż najlepszy. 807 00:43:30,920 --> 00:43:34,040 808 00:43:34,040 --> 00:43:36,850 Czegoś, co wiedział nic na temat zasad, które 809 00:43:36,850 --> 00:43:43,020 nic nie wiedział o strukturze gry, jest to imponująca wydajność. 810 00:43:43,020 --> 00:43:45,660 I to jest to, co jesteśmy w stanie zrobić dzisiaj. 811 00:43:45,660 --> 00:43:50,239 >> OK, można powiedzieć, ale jeśli myśleć o AI w grach, 812 00:43:50,239 --> 00:43:52,530 Zwykle myślimy o Rzeczy, które możemy w rzeczywistości 813 00:43:52,530 --> 00:43:54,180 usiąść i grać przeciwko. 814 00:43:54,180 --> 00:43:58,760 Jeśli siadam i gram StarCraft lub Gram Sito darmowe, 815 00:43:58,760 --> 00:44:01,870 przeciwnik komputerowy jest Osoba kontrolowanie Zergów, 816 00:44:01,870 --> 00:44:06,770 lub kontrolowania innych cywilizacji. 817 00:44:06,770 --> 00:44:11,920 Jak ci gracze rzeczywiście znaleźć swoje ruchy? 818 00:44:11,920 --> 00:44:18,810 >> Cóż, te gry są tak skonstruowane, taki sam sposób jak nasze gry planszowe, 819 00:44:18,810 --> 00:44:22,250 te gry, które będziemy zbiorczo nazywamy cztery gry X, 820 00:44:22,250 --> 00:44:26,040 zbadać, expand-- zapomnieć o nich. 821 00:44:26,040 --> 00:44:26,980 Czym oni są? 822 00:44:26,980 --> 00:44:32,150 Przeglądaj, poszerzyć i gaszenia, Myślę, że jest ostatni. 823 00:44:32,150 --> 00:44:36,060 Ale one są w zasadzie poszukiwania i przejęcie gry. 824 00:44:36,060 --> 00:44:41,020 Zazwyczaj przeciwnik komputerowy nie ma ograniczone informacje. 825 00:44:41,020 --> 00:44:45,486 Nie wiem dokładnie, co to dzieje się za tym mgle wojny. 826 00:44:45,486 --> 00:44:47,735 Oni nie dostać się do zobaczyć, co masz w ekwipunku. 827 00:44:47,735 --> 00:44:50,240 828 00:44:50,240 --> 00:44:52,800 >> Jest to środowisko, które jest dynamiczne. 829 00:44:52,800 --> 00:44:56,180 Wszystko zmienia się przez cały czas. 830 00:44:56,180 --> 00:45:00,290 Nie siedzieć i doczekać, aby wziąć swój ruch. 831 00:45:00,290 --> 00:45:02,810 Ale większość rzeczy nadal są dyskretne. 832 00:45:02,810 --> 00:45:04,200 I umieścić moje miasto tutaj. 833 00:45:04,200 --> 00:45:06,750 Albo mam umieścić moje miasto tutaj. 834 00:45:06,750 --> 00:45:08,950 I wszystko jest deterministyczny. 835 00:45:08,950 --> 00:45:14,660 Kiedy mówię, przenieść jednostkę tutaj, mój zespół porusza się tu, chyba że przeszkody nagle 836 00:45:14,660 --> 00:45:17,700 wchodzi w grę. 837 00:45:17,700 --> 00:45:21,610 Teraz, to nie wszystko komputerowy gry, które są tam dzisiaj. 838 00:45:21,610 --> 00:45:27,320 >> Jeśli pójdę i gram w pierwszej osobie rodzaju gry, coś jak złodziej lub Fallout 839 00:45:27,320 --> 00:45:33,350 lub Skyrim lub Halo, teraz Mam przeciwników komputerowych 840 00:45:33,350 --> 00:45:37,860 że to, że obecnie nie ma bardzo inna sytuacja. 841 00:45:37,860 --> 00:45:40,020 Mają znowu ograniczone informacje. 842 00:45:40,020 --> 00:45:43,420 Tylko oni mogą zobaczyć pewne pole widzenia. 843 00:45:43,420 --> 00:45:45,180 Środowisko jest wciąż dynamiczne. 844 00:45:45,180 --> 00:45:48,280 Coś się zmienia cały czas. 845 00:45:48,280 --> 00:45:52,300 >> Ale teraz mam o wiele więcej ciągła przestrzeń działania. 846 00:45:52,300 --> 00:45:57,170 I można tylko zerkając trochę na drzwiach. 847 00:45:57,170 --> 00:46:00,650 I kilka gier, moje działania są stochastyczne. 848 00:46:00,650 --> 00:46:04,590 Mogę spróbować przeskoczyć tej ścianie, ale mam szansę niepowodzeniem. 849 00:46:04,590 --> 00:46:08,280 850 00:46:08,280 --> 00:46:14,550 Tego typu gry są coraz bliżej bliżej rodzaju regulatory 851 00:46:14,550 --> 00:46:17,330 że budujemy w robotyce. 852 00:46:17,330 --> 00:46:21,050 >> W robotyki, musimy założyć, że mamy ograniczone informacje. 853 00:46:21,050 --> 00:46:23,070 Mamy czujniki powiedz nam o świecie. 854 00:46:23,070 --> 00:46:25,860 Mamy zawsze zmieniający się, dynamiczne środowisko. 855 00:46:25,860 --> 00:46:30,440 Mamy świat, w którym przestrzeń jest ciągła, niż dyskretne. 856 00:46:30,440 --> 00:46:36,260 I nasze działania, gdy staramy je, mają szansę niepowodzeniem. 857 00:46:36,260 --> 00:46:40,960 A w rzeczywistości, nowoczesne gry Sterowniki dla przeciwnika Halo, 858 00:46:40,960 --> 00:46:48,690 lub dla tych NPC w Skyrim, w zasadzie uruchomić małe architektur robotyki. 859 00:46:48,690 --> 00:46:50,380 >> Czują świat. 860 00:46:50,380 --> 00:46:52,910 Budują model świata. 861 00:46:52,910 --> 00:46:57,950 Oni obliczyć na podstawie zestawu cele, które chcieliby osiągnąć. 862 00:46:57,950 --> 00:47:03,110 Planują działań w oparciu na to, co wiedzą. 863 00:47:03,110 --> 00:47:07,940 A to są dokładnie te same rodzaje systemów, które budujemy w robotyce. 864 00:47:07,940 --> 00:47:11,420 Zatem te architektury, do przynieść to z powrotem razem, 865 00:47:11,420 --> 00:47:14,500 są często takie same. 866 00:47:14,500 --> 00:47:16,340 >> Zobaczmy więc, jeśli widzimy, że. 867 00:47:16,340 --> 00:47:19,210 Wróćmy do naszego Przykładem tic-tac-toe. 868 00:47:19,210 --> 00:47:22,690 I mam zamiar zadać kilka moich post-docs, aby przyjść i pomóc mi. 869 00:47:22,690 --> 00:47:26,970 Więc Chen Ming i Alessandro i Olivier, jeśli faceci przyjdzie się. 870 00:47:26,970 --> 00:47:32,080 871 00:47:32,080 --> 00:47:35,440 A ja będę potrzebował para wolontariuszy 872 00:47:35,440 --> 00:47:37,590 >> OK, widziałem ręki się prawo tam w środku. 873 00:47:37,590 --> 00:47:39,965 Pozwól mi wziąć jeszcze jedno, ktoś dodatkowo z tyłu może. 874 00:47:39,965 --> 00:47:40,881 Dobrze, tam. 875 00:47:40,881 --> 00:47:41,490 Chodź na górę. 876 00:47:41,490 --> 00:47:44,190 877 00:47:44,190 --> 00:47:45,335 W porządku. 878 00:47:45,335 --> 00:47:49,490 Więc weźmy tę pokrywę w dół. 879 00:47:49,490 --> 00:48:03,700 A jeśli faceci przyjdzie w prawo z powrotem tutaj dla mnie fantastyczne. 880 00:48:03,700 --> 00:48:06,580 >> Więc to jest robotem o nazwie Baxter. 881 00:48:06,580 --> 00:48:10,880 Baxter jest robotem, który jest platforma handlowa, zaprojektowane 882 00:48:10,880 --> 00:48:13,030 przez firmy o nazwie Rethink. 883 00:48:13,030 --> 00:48:16,580 Oraz robot jest przeznaczony do produkcji na małą skalę. 884 00:48:16,580 --> 00:48:19,265 Ale dziś mamy zamiar używać go do gry Kółko i krzyżyk. 885 00:48:19,265 --> 00:48:21,930 886 00:48:21,930 --> 00:48:27,150 Teraz, ten robot jest również coś to relatywnie wyjątkowa. 887 00:48:27,150 --> 00:48:32,950 Bo jeśli stały wszędzie blisko standardowej automatyki przemysłowej 888 00:48:32,950 --> 00:48:39,580 System, byłbym w samym grobie niebezpieczeństwo zranienia. 889 00:48:39,580 --> 00:48:45,600 >> Baxter, jest jednak przeznaczone do stosunkowo bezpieczne do interakcji z. 890 00:48:45,600 --> 00:48:48,680 A więc mogę naciskać na tej robocie. 891 00:48:48,680 --> 00:48:52,350 I widać, że to trochę nieco elastyczny, jak porusza się wokół. 892 00:48:52,350 --> 00:48:57,250 I mogę go zmienić położenie gdzie chciałbym to przejść. 893 00:48:57,250 --> 00:49:03,410 Teraz w normalnym układzie zautomatyzowanych mielibyśmy komplet złączy tutaj 894 00:49:03,410 --> 00:49:07,970 który bezpośrednio reagowanie na polecenia pozycji. 895 00:49:07,970 --> 00:49:13,180 I nie koniecznie dbać jeśli się poruszały przez wolnym powietrzu 896 00:49:13,180 --> 00:49:15,555 lub jeśli się poruszały przez moją klatkę piersiową. 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 I zazwyczaj, jeśli były Obok systemu przemysłowego 900 00:49:22,090 --> 00:49:23,400 chcesz iść nigdzie w pobliżu niego. 901 00:49:23,400 --> 00:49:26,280 Nie będzie żółta Taśma bezpieczeństwa wokół niego. 902 00:49:26,280 --> 00:49:28,310 Ten system ma nieco inna konstrukcja 903 00:49:28,310 --> 00:49:32,130 aby być bardziej przyjazny i łatwiejszy ludzi do interakcji z, 904 00:49:32,130 --> 00:49:36,380 tym, że w każdym połączeniu, nie ma wiosny. 905 00:49:36,380 --> 00:49:39,110 I zamiast sterowania dokładną pozycję, 906 00:49:39,110 --> 00:49:43,110 kontrolować pewną Moment, pewna ilość siły, 907 00:49:43,110 --> 00:49:45,874 że chcemy być na tej wiosny. 908 00:49:45,874 --> 00:49:47,790 W porządku, więc niech mnie ma tu naszych wolontariuszy. 909 00:49:47,790 --> 00:49:48,540 Cześć jak masz na imię? 910 00:49:48,540 --> 00:49:49,010 >> PUBLICZNOŚCI: Louis. 911 00:49:49,010 --> 00:49:49,635 >> GŁOŚNIK: Louis. 912 00:49:49,635 --> 00:49:50,490 Miło Cię widzieć. 913 00:49:50,490 --> 00:49:50,990 I? 914 00:49:50,990 --> 00:49:51,610 >> PUBLICZNOŚCI: David. 915 00:49:51,610 --> 00:49:51,960 >> Prelegent: David. 916 00:49:51,960 --> 00:49:52,550 Miło cię poznać. 917 00:49:52,550 --> 00:49:54,508 Jeśli faceci będą czekać tu na chwilę, 918 00:49:54,508 --> 00:49:56,420 Mam zamiar dać ci szansa, aby to zrobić. 919 00:49:56,420 --> 00:50:00,610 Więc ten robot, jeśli pojawią się i jeśli delikatnie naciskać na nią, 920 00:50:00,610 --> 00:50:03,780 masz zamiar zobaczyć, że porusza się trochę. 921 00:50:03,780 --> 00:50:06,349 A jeśli chwycić go w prawo tutaj na nadgarstku tak 922 00:50:06,349 --> 00:50:09,390 powyżej, gdzie te przyciski są, to Wygląda na to, należy chwycić przycisków, 923 00:50:09,390 --> 00:50:13,100 ale chwycić tuż nad nim, a nie, będziesz w stanie bardzo delikatnie manipulować 924 00:50:13,100 --> 00:50:14,545 w przestrzeni. 925 00:50:14,545 --> 00:50:15,920 Louis, chcesz spróbować? 926 00:50:15,920 --> 00:50:19,465 Więc dać go tylko trochę naciskać na początek. 927 00:50:19,465 --> 00:50:23,190 A potem, jeśli wkładać palców tam i trzymać się tego, 928 00:50:23,190 --> 00:50:24,807 ponieważ będzie to przenieść na ciebie czasu. 929 00:50:24,807 --> 00:50:27,824 930 00:50:27,824 --> 00:50:29,365 Dobra, chcesz spróbować? 931 00:50:29,365 --> 00:50:29,980 Chodź na górę. 932 00:50:29,980 --> 00:50:32,300 Więc daj to tylko delikatne wcisnąć tam rozpocząć. 933 00:50:32,300 --> 00:50:33,820 Możesz poczuć, jak to jest. 934 00:50:33,820 --> 00:50:40,060 A potem, jeśli złapał go właśnie tam, będziesz w stanie manewrować na około. 935 00:50:40,060 --> 00:50:41,280 >> OK. 936 00:50:41,280 --> 00:50:47,360 Więc zwykle, tego rodzaju robot będzie zostać wykorzystane do produkcji na małą skalę. 937 00:50:47,360 --> 00:50:50,980 I mam zamiar przenieść tę rękę tak dół z drogi trochę tutaj. 938 00:50:50,980 --> 00:50:55,750 Ale dziś mamy zamiar użyć sam system gry Kółko i krzyżyk 939 00:50:55,750 --> 00:50:59,520 na podstawie minimax, że zbudowane wcześniej. 940 00:50:59,520 --> 00:51:00,549 OK? 941 00:51:00,549 --> 00:51:02,340 Tak, jesteście siebie zamiar zagrać. 942 00:51:02,340 --> 00:51:04,210 Louis, masz zamiar być pierwszy. 943 00:51:04,210 --> 00:51:05,920 Pozwól mi tylko trzymać się tutaj na chwilę. 944 00:51:05,920 --> 00:51:10,949 Będę miał stanąć w prawo tutaj, tak każdy może cię zobaczyć. 945 00:51:10,949 --> 00:51:11,990 Czy wy założyć tutaj? 946 00:51:11,990 --> 00:51:13,120 >> ROBOT: Witamy. 947 00:51:13,120 --> 00:51:15,910 Zagrajmy w Kółko i krzyżyk. 948 00:51:15,910 --> 00:51:20,860 Nie podnoś token przed Muszę powiedzieć, że to jest twoja kolej. 949 00:51:20,860 --> 00:51:22,050 I rozpocząć grę. 950 00:51:22,050 --> 00:51:27,900 951 00:51:27,900 --> 00:51:28,750 To jest moja kolej. 952 00:51:28,750 --> 00:51:47,002 953 00:51:47,002 --> 00:51:50,210 GŁOŚNIK: Teraz, jeśli można przyjąć jedną z Twoje kawałki i iść do przodu i umieścić go. 954 00:51:50,210 --> 00:51:51,446 ROBOT: To jest twoja kolej. 955 00:51:51,446 --> 00:51:53,430 [ŚMIECH] 956 00:51:53,430 --> 00:51:54,836 To jest moja kolej. 957 00:51:54,836 --> 00:51:56,820 [ŚMIECH] 958 00:51:56,820 --> 00:52:12,196 959 00:52:12,196 --> 00:52:15,680 [ŚMIECH] 960 00:52:15,680 --> 00:52:16,570 Twoja kolej. 961 00:52:16,570 --> 00:52:21,397 962 00:52:21,397 --> 00:52:23,688 GŁOŚNIK: Rasa ludzka jest liczy na was tutaj, Louis. 963 00:52:23,688 --> 00:52:27,440 964 00:52:27,440 --> 00:52:28,350 >> ROBOT: To jest moja kolej. 965 00:52:28,350 --> 00:52:44,810 966 00:52:44,810 --> 00:52:47,015 >> GŁOŚNIK: Tak Baxter skutecznie zablokowane tutaj. 967 00:52:47,015 --> 00:52:49,670 968 00:52:49,670 --> 00:52:52,480 >> ROBOT: To jest twoja kolej. 969 00:52:52,480 --> 00:52:53,360 To jest moja kolej. 970 00:52:53,360 --> 00:53:14,730 971 00:53:14,730 --> 00:53:16,810 Twoja kolej. 972 00:53:16,810 --> 00:53:17,760 To jest moja kolej. 973 00:53:17,760 --> 00:53:21,330 974 00:53:21,330 --> 00:53:23,830 GŁOŚNIK: A my poinformujemy Baxter zakończyć się jego ostatni ruch tutaj. 975 00:53:23,830 --> 00:53:36,622 976 00:53:36,622 --> 00:53:39,090 >> [ŚMIECH] 977 00:53:39,090 --> 00:53:40,480 >> ROBOT: To remis. 978 00:53:40,480 --> 00:53:42,030 Wygram następnym razem. 979 00:53:42,030 --> 00:53:43,365 >> [ŚMIECH] 980 00:53:43,365 --> 00:53:45,210 >> GŁOŚNIK: Wszystko w porządku, Dziękuję bardzo, Louis. 981 00:53:45,210 --> 00:53:46,094 Dziękuję. 982 00:53:46,094 --> 00:53:46,980 Możesz iść tą drogą. 983 00:53:46,980 --> 00:53:49,759 >> ROBOT: I rozpocząć grę. 984 00:53:49,759 --> 00:53:51,800 GŁOŚNIK: Więc pozwól mi wyjaśnić do was jeszcze jedno małe 985 00:53:51,800 --> 00:53:55,410 nieco, zanim się nasz rewanż tutaj. 986 00:53:55,410 --> 00:53:57,200 Co dokładnie się dzieje? 987 00:53:57,200 --> 00:53:59,430 Więc robot ma tu kamery się szczyt. 988 00:53:59,430 --> 00:54:01,330 I to patrząc na pokładzie. 989 00:54:01,330 --> 00:54:04,470 I to zobaczyć, czy to dostał czerwoną O lub niebieski 990 00:54:04,470 --> 00:54:10,450 i biały X. Jak ci się umieścić na Płyta, która jest w zasadzie takie samo wejście 991 00:54:10,450 --> 00:54:13,890 że będziemy czytać z nasza struktura danych z naszego ekranu. 992 00:54:13,890 --> 00:54:17,290 To działa tak samo Algorytm minimax się 993 00:54:17,290 --> 00:54:21,010 w stanie dowiedzieć się, gdzie miejsce dobre token. 994 00:54:21,010 --> 00:54:24,820 >> A potem dajemy polecenie o gdzie chcielibyśmy token być umieszczone. 995 00:54:24,820 --> 00:54:26,120 Ramię porusza się. 996 00:54:26,120 --> 00:54:31,750 To użycie chwytaka podciśnieniowego do zastosowania niektóre ssania do tego drewnianego elementu, 997 00:54:31,750 --> 00:54:35,240 go podnieść, przenieść go w prawo miejscu, a następnie zwolnij ssania 998 00:54:35,240 --> 00:54:36,950 i upuść go. 999 00:54:36,950 --> 00:54:38,990 Dobra, jedziemy dać mu jeszcze jeden strzał 1000 00:54:38,990 --> 00:54:40,930 z nieco mądrzejszego odtwarzacza tutaj. 1001 00:54:40,930 --> 00:54:42,290 Jesteś gotowy? 1002 00:54:42,290 --> 00:54:46,150 Dobrze, jeśli chcesz stanąć w prawo tutaj i dać A-- okazać się w ten sposób 1003 00:54:46,150 --> 00:54:47,955 więc można zobaczyć wszyscy. 1004 00:54:47,955 --> 00:54:48,830 A następnie [niesłyszalne]. 1005 00:54:48,830 --> 00:54:49,330 >> ROBOT: To jest moja kolej. 1006 00:54:49,330 --> 00:54:50,455 >> GŁOŚNIK: Baxter rozpocznie. 1007 00:54:50,455 --> 00:55:10,750 1008 00:55:10,750 --> 00:55:11,730 Twoja kolej. 1009 00:55:11,730 --> 00:55:16,490 1010 00:55:16,490 --> 00:55:17,520 To jest moja kolej. 1011 00:55:17,520 --> 00:55:38,740 1012 00:55:38,740 --> 00:55:39,690 Twoja kolej. 1013 00:55:39,690 --> 00:55:46,330 1014 00:55:46,330 --> 00:55:47,165 To jest moja kolej. 1015 00:55:47,165 --> 00:56:01,252 1016 00:56:01,252 --> 00:56:06,192 >> [ŚMIECH] 1017 00:56:06,192 --> 00:56:08,542 >> GŁOŚNIK: [WHISPERING] Tylko niech śmiało i wygrać. 1018 00:56:08,542 --> 00:56:09,500 ROBOT: To jest twoja kolej. 1019 00:56:09,500 --> 00:56:15,099 1020 00:56:15,099 --> 00:56:15,890 GŁOŚNIK: To jest OK. 1021 00:56:15,890 --> 00:56:20,390 1022 00:56:20,390 --> 00:56:21,360 >> ROBOT: To jest moja kolej. 1023 00:56:21,360 --> 00:56:24,825 1024 00:56:24,825 --> 00:56:26,805 >> [ŚMIECH] 1025 00:56:26,805 --> 00:56:42,650 1026 00:56:42,650 --> 00:56:43,510 >> Wygrałem. 1027 00:56:43,510 --> 00:56:45,620 >> [ŚMIECH] 1028 00:56:45,620 --> 00:56:46,595 >> I rozpocząć grę. 1029 00:56:46,595 --> 00:56:48,261 >> GŁOŚNIK: Dobrze, dziękuję bardzo. 1030 00:56:48,261 --> 00:56:50,180 1031 00:56:50,180 --> 00:56:55,590 Dobrze, myślę, że mamy czas na jeszcze jeden doskonały odtwarzacz tic-tac-toe, 1032 00:56:55,590 --> 00:57:00,490 ktoś, kto może umieścić tę rzecz w celu mecz, który wie, co robi. 1033 00:57:00,490 --> 00:57:03,010 >> [ŚMIECH] 1034 00:57:03,010 --> 00:57:05,560 >> Kto będzie naszym mistrzem tutaj? 1035 00:57:05,560 --> 00:57:08,110 Dobrze, twoi przyjaciele ochotnika ciebie. 1036 00:57:08,110 --> 00:57:11,190 To mi wystarczy. 1037 00:57:11,190 --> 00:57:12,194 Powiedz mi swoje imię ponownie. 1038 00:57:12,194 --> 00:57:12,860 PUBLICZNOŚCI: Tamir. 1039 00:57:12,860 --> 00:57:14,193 GŁOŚNIK: Tamir, miło cię widzieć. 1040 00:57:14,193 --> 00:57:19,270 Dobra, znowu, będziemy do was aż tutaj, więc każdy może cię widzieć. 1041 00:57:19,270 --> 00:57:22,070 Jesteś naszym przedstawicielem Dotychczas w tym meczu. 1042 00:57:22,070 --> 00:57:24,540 Baxter jest jeden i och och. 1043 00:57:24,540 --> 00:57:26,300 Albo przepraszam, jeden no i jeden. 1044 00:57:26,300 --> 00:57:27,490 I to jest do was tutaj. 1045 00:57:27,490 --> 00:57:29,340 Baxter będzie się poruszać po pierwsze, choć. 1046 00:57:29,340 --> 00:57:30,435 Więc. 1047 00:57:30,435 --> 00:57:31,310 ROBOT: To jest moja kolej. 1048 00:57:31,310 --> 00:57:45,226 1049 00:57:45,226 --> 00:57:48,208 >> [ŚMIECH] 1050 00:57:48,208 --> 00:57:52,720 1051 00:57:52,720 --> 00:57:55,780 >> Twoja kolej. 1052 00:57:55,780 --> 00:57:56,845 To jest moja kolej. 1053 00:57:56,845 --> 00:58:18,130 1054 00:58:18,130 --> 00:58:18,965 Twoja kolej. 1055 00:58:18,965 --> 00:58:28,751 1056 00:58:28,751 --> 00:58:30,248 To jest moja kolej. 1057 00:58:30,248 --> 00:58:51,210 1058 00:58:51,210 --> 00:58:52,160 Twoja kolej. 1059 00:58:52,160 --> 00:59:00,854 1060 00:59:00,854 --> 00:59:03,365 >> [ŚMIECH] 1061 00:59:03,365 --> 00:59:04,240 ROBOT: To jest moja kolej. 1062 00:59:04,240 --> 00:59:06,930 GŁOŚNIK: Jest to o wiele trudniejsze, gdy stoisz tu, ludzie. 1063 00:59:06,930 --> 00:59:19,400 1064 00:59:19,400 --> 00:59:21,840 [ŚMIECH] 1065 00:59:21,840 --> 00:59:26,730 1066 00:59:26,730 --> 00:59:29,054 ROBOT: Wy, ludzie są tak łatwe do pokonania. 1067 00:59:29,054 --> 00:59:30,803 [Śmiech i oklaski] 1068 00:59:30,803 --> 00:59:31,886 GŁOŚNIK: Dziękuję bardzo. 1069 00:59:31,886 --> 00:59:34,692 ROBOT: wygram. 1070 00:59:34,692 --> 00:59:35,400 I rozpocząć grę. 1071 00:59:35,400 --> 00:59:39,500 >> Prelegent: Dobra, dziękuję bardzo wiele do Oliviera, i Alessandro, 1072 00:59:39,500 --> 00:59:41,616 i Chen Ming. 1073 00:59:41,616 --> 00:59:45,600 >> [OKLASKI] 1074 00:59:45,600 --> 00:59:47,040 >> Chcę, aby ostatni punkt. 1075 00:59:47,040 --> 00:59:51,630 Więc Baxter na samym kończy, oszukany. 1076 00:59:51,630 --> 00:59:54,160 1077 00:59:54,160 --> 00:59:56,310 I to było nieoczekiwane. 1078 00:59:56,310 --> 01:00:00,440 Jednym z fantastyczny rzeczy o AI jest to, że 1079 01:00:00,440 --> 01:00:05,070 wykonywać pracę w AI, tak że możemy budować naprawdę ciekawy i inteligentny 1080 01:00:05,070 --> 01:00:06,930 pomysłowość. 1081 01:00:06,930 --> 01:00:10,130 Ale również wykonywać pracę w AI ponieważ mówi nam coś 1082 01:00:10,130 --> 01:00:13,940 o tym, jak ludzie są inteligentni. 1083 01:00:13,940 --> 01:00:17,280 >> Jednym z ulubionych badania z moim laboratorium jest 1084 01:00:17,280 --> 01:00:23,660 patrząc na to, co się dzieje, gdy Maszyny niespodziewanie oszukiwać. 1085 01:00:23,660 --> 01:00:27,070 Zrobiliśmy to pierwotnie nie z Baxter gry Kółko i krzyżyk, 1086 01:00:27,070 --> 01:00:30,340 ale z mniejszym robota o nazwie Nao, który grał Papier, kamień, nożyce. 1087 01:00:30,340 --> 01:00:33,010 1088 01:00:33,010 --> 01:00:35,800 A czasem po grać dużo, dużo 1089 01:00:35,800 --> 01:00:41,580 nudne Papier, kamień, nożyce gry, robot rzucał gest, 1090 01:00:41,580 --> 01:00:48,616 stracić, a potem nagle zmienić jego gest i powiedzieć, że wygram. 1091 01:00:48,616 --> 01:00:50,480 >> [ŚMIECH] 1092 01:00:50,480 --> 01:00:56,090 >> Teraz, czasami chcielibyśmy mieć robota, tylko jako kontrola, rzucać gest, 1093 01:00:56,090 --> 01:01:01,270 wygrać, i zmienić jego gest stracić, rzucić zapałkę, 1094 01:01:01,270 --> 01:01:04,070 oszukiwać, aby stracić. 1095 01:01:04,070 --> 01:01:07,540 I to nie jest tak atrakcyjne. 1096 01:01:07,540 --> 01:01:09,890 Robot, który oszukuje Aby wygrać ludzi 1097 01:01:09,890 --> 01:01:14,660 reagować dalej, jeśli jest się do nich dostać, jak to 1098 01:01:14,660 --> 01:01:17,690 aktywnie poszukuje ich zniszczenie. 1099 01:01:17,690 --> 01:01:19,210 >> [ŚMIECH] 1100 01:01:19,210 --> 01:01:20,990 >> To staje się agentem. 1101 01:01:20,990 --> 01:01:21,840 To jest jak człowiek. 1102 01:01:21,840 --> 01:01:23,970 Ma przekonanie i zamiar. 1103 01:01:23,970 --> 01:01:27,470 I to nie jest dobre intencje. 1104 01:01:27,470 --> 01:01:33,790 I robot, który rzuca Gra jest po prostu uszkodzony. 1105 01:01:33,790 --> 01:01:36,990 To jest po prostu zepsute urządzenie. 1106 01:01:36,990 --> 01:01:41,405 Pokażę wam kilka przykładów stanowi, że od kilku naszych uczestników. 1107 01:01:41,405 --> 01:01:43,990 1108 01:01:43,990 --> 01:01:45,600 Tak tu jest oszustwo w celu utraty. 1109 01:01:45,600 --> 01:01:46,266 >> [ODTWARZANIE] 1110 01:01:46,266 --> 01:01:47,010 - [Niesłyszalne] wygrać. 1111 01:01:47,010 --> 01:01:49,550 Zagrajmy. 1112 01:01:49,550 --> 01:01:50,538 >> -Czekaj, co? 1113 01:01:50,538 --> 01:01:54,490 1114 01:01:54,490 --> 01:01:55,352 >> - [Niesłyszalne] wygrać. 1115 01:01:55,352 --> 01:01:58,280 Zagrajmy. 1116 01:01:58,280 --> 01:01:59,400 >> [Niesłyszalne] wygrać. 1117 01:01:59,400 --> 01:02:02,290 Zagrajmy. 1118 01:02:02,290 --> 01:02:05,490 >> GŁOŚNIK: I tu oszukuje, aby wygrać. 1119 01:02:05,490 --> 01:02:06,438 >> -Tak, Wygram. 1120 01:02:06,438 --> 01:02:07,394 Zagrajmy. 1121 01:02:07,394 --> 01:02:08,828 >> -Nie Mogę tego zrobić. 1122 01:02:08,828 --> 01:02:10,740 >> [ŚMIECH] 1123 01:02:10,740 --> 01:02:12,174 1124 01:02:12,174 --> 01:02:13,979 >> -Tak, Wygram. 1125 01:02:13,979 --> 01:02:14,520 -Oszukałeś. 1126 01:02:14,520 --> 01:02:17,990 1127 01:02:17,990 --> 01:02:20,010 Oszukałeś teraz. 1128 01:02:20,010 --> 01:02:21,140 >> -Tak, Wygram. 1129 01:02:21,140 --> 01:02:22,940 >> Hej, jesteś oszustem. 1130 01:02:22,940 --> 01:02:26,670 Oszukiwać, super oszukiwać. 1131 01:02:26,670 --> 01:02:27,650 >> [Zakończyć odtwarzanie] 1132 01:02:27,650 --> 01:02:31,130 >> GŁOŚNIK: Są różne Reakcje gwałtownie 1133 01:02:31,130 --> 01:02:34,890 zmienić nasze postrzeganie urządzenia. 1134 01:02:34,890 --> 01:02:36,780 Czy to oznacza, że świadomie budować 1135 01:02:36,780 --> 01:02:40,370 maszyny, które oszukują, ponieważ to najlepsza technika, co możemy zrobić? 1136 01:02:40,370 --> 01:02:44,680 Nie, ale to mówi nam coś mnie naprawdę interesuje ludzi. 1137 01:02:44,680 --> 01:02:49,710 To rzecz, która oszukuje ciebie i kradnie twoje zwycięstwo, to 1138 01:02:49,710 --> 01:02:53,660 coś, co żyje, to animować, to cię dopaść. 1139 01:02:53,660 --> 01:02:54,680 Ma stan psychiczny. 1140 01:02:54,680 --> 01:02:55,400 Ma przekonanie. 1141 01:02:55,400 --> 01:02:57,170 Ma zamiar. 1142 01:02:57,170 --> 01:03:01,540 >> To coś, że ręce gra dla Ciebie, to nie. 1143 01:03:01,540 --> 01:03:04,670 To jest po prostu uszkodzony. 1144 01:03:04,670 --> 01:03:08,900 To jest na wiele sposobów, dlatego jest łatwo rzucać gry z dziećmi. 1145 01:03:08,900 --> 01:03:12,050 Ale jeśli spróbujesz je oszukać i rodzaj twierdzą zwycięstwo 1146 01:03:12,050 --> 01:03:15,200 gdy wiesz, po prostu skrócić Gra, to cię złapią od razu. 1147 01:03:15,200 --> 01:03:19,040 1148 01:03:19,040 --> 01:03:23,140 Te rodzaje efektów, które widzimy wychodzi z AI, 1149 01:03:23,140 --> 01:03:26,490 uczą nam wiele o nas samych. 1150 01:03:26,490 --> 01:03:28,076 >> W porządku, to wszystko na dzisiaj. 1151 01:03:28,076 --> 01:03:30,450 Dziękuję bardzo do Dawida i ekipa produkcyjna Harvard 1152 01:03:30,450 --> 01:03:32,350 dla schodzili. 1153 01:03:32,350 --> 01:03:33,820 >> [OKLASKI] 1154 01:03:33,820 --> 01:03:36,760 1155 01:03:36,760 --> 01:03:41,840 >> Zobaczymy się w quizie jednym, a następnie na ostatni wykład. 1156 01:03:41,840 --> 01:03:43,025 Mieć świetny dzień. 1157 01:03:43,025 --> 01:03:44,965 >> [OKLASKI] 1158 01:03:44,965 --> 01:03:48,360 1159 01:03:48,360 --> 01:03:51,825 >> [MUZYKI] 1160 01:03:51,825 --> 01:03:54,950 DAVID J MALAN: Cóż, prawdopodobnie trzeba wprowadzenie pewnego rodzaju szyfrowania, 1161 01:03:54,950 --> 01:03:55,450 dobrze? 1162 01:03:55,450 --> 01:03:58,650 Bo wtedy nagłówkach te żądania HTTP będzie 1163 01:03:58,650 --> 01:04:01,530 jajecznica, aby każdy, próbuje powąchać ruchu 1164 01:04:01,530 --> 01:04:03,400 Nie rzeczywiście będzie w stanie je zobaczyć. 1165 01:04:03,400 --> 01:04:05,254 Więc co to jest rozwiązanie tego problemu? 1166 01:04:05,254 --> 01:04:07,920 Cóż, musimy właściwie przedstawić szyfrowanie do wzoru, 1167 01:04:07,920 --> 01:04:11,010 tak, że gdy osoba transmisji danych z punktu A do B, 1168 01:04:11,010 --> 01:04:12,390 możemy bezpiecznie send-- 1169 01:04:12,390 --> 01:04:14,590 >> [ŚMIECH] 1170 01:04:14,590 --> 01:04:19,530 >> Informacje, w taki sposób, że Przeciwnik nie może, w rzeczywistości, to widzę.