1 00:00:00,000 --> 00:00:01,924 >> [Грає музика] 2 00:00:01,924 --> 00:00:10,600 3 00:00:10,600 --> 00:00:13,280 >> СЛУХАЛИ: Ласкаво просимо, кожен. 4 00:00:13,280 --> 00:00:15,440 Це CS50. 5 00:00:15,440 --> 00:00:21,040 І сьогодні, у нас є багато цікаві речі, щоб говорити про. 6 00:00:21,040 --> 00:00:25,500 По-перше, хоча, я повинен нагадати Ви з декількох адміністративних речей. 7 00:00:25,500 --> 00:00:30,160 На цьому тижні вікторини одним, середа або секції Yale 8 00:00:30,160 --> 00:00:32,940 по вівторках і четвергах, в четвер. 9 00:00:32,940 --> 00:00:38,170 Є відгуки вікторини сьогодні в Єльському університеті, 5:30 до 7:00. 10 00:00:38,170 --> 00:00:40,030 У Гарварді, вони записали одне вчора. 11 00:00:40,030 --> 00:00:43,000 І кожен може подивитися, що в Інтернеті. 12 00:00:43,000 --> 00:00:49,406 >> Крім того, на цьому тижні або на початку наступного тижня, у нас є наш останній CS50 лекцію. 13 00:00:49,406 --> 00:00:51,450 [Стогін] я знаю. 14 00:00:51,450 --> 00:00:54,140 Він прийшов так швидко. 15 00:00:54,140 --> 00:00:57,820 Yale студенти матимуть живий лекції тут, в юридичній школі 16 00:00:57,820 --> 00:00:59,920 Глядацька зала в п'ятницю. 17 00:00:59,920 --> 00:01:01,140 Там буде торт. 18 00:01:01,140 --> 00:01:05,570 Студентів Гарварда матиме Остання лекція в Сандерс в понеділок. 19 00:01:05,570 --> 00:01:08,050 Там також буде торт. 20 00:01:08,050 --> 00:01:14,000 >> Крім того, на цьому тижні в п'ятницю, для тих, з вас, хто приходять в Нью-Хейвен, 21 00:01:14,000 --> 00:01:15,740 у нас є CS50 Expo. 22 00:01:15,740 --> 00:01:18,850 У нас є більш ніж 30 зареєстровано різні групи 23 00:01:18,850 --> 00:01:22,530 щоб показати вам все, від автономних парусних, 24 00:01:22,530 --> 00:01:27,170 до систем, які розпізнають цифрові портрети, на комп'ютер 25 00:01:27,170 --> 00:01:32,100 музикою і комп'ютером виробництва музики. 26 00:01:32,100 --> 00:01:33,610 Тому, будь ласка, приєднуйтесь до нас. 27 00:01:33,610 --> 00:01:36,460 Я думаю, що це буде прекрасний час. 28 00:01:36,460 --> 00:01:40,320 >> Сьогодні, однак, ми отримуємо продовжувати говорити про AI, 29 00:01:40,320 --> 00:01:43,150 про штучний інтелект. 30 00:01:43,150 --> 00:01:46,070 І одна з речей, які ми збираємося, щоб дістатися до сьогодні 31 00:01:46,070 --> 00:01:51,750 ідея про те, як використовувати AI вирішувати проблеми. 32 00:01:51,750 --> 00:01:54,690 Тепер, як завжди, давайте почнемо з чого-небудь простого. 33 00:01:54,690 --> 00:01:57,120 І ми збираємося, щоб почати з простої ідеї. 34 00:01:57,120 --> 00:01:59,920 І це за допомогою пошуку. 35 00:01:59,920 --> 00:02:06,990 >> Отже, уявіть, на хвилину, що я є завдання, яке мені потрібно виконувати. 36 00:02:06,990 --> 00:02:11,970 І я б хотів, щоб це завдання автоматизована деяким програмного забезпечення агента. 37 00:02:11,970 --> 00:02:17,100 Уявіть собі, що я намагаюся забронювати набір авіарейси зі, скажімо, Бостон 38 00:02:17,100 --> 00:02:20,040 в Сан-Франциско. 39 00:02:20,040 --> 00:02:24,230 Я міг би пройти і я міг би використовувати один з чудового онлайн-пошуку 40 00:02:24,230 --> 00:02:28,790 інструменти, які збирається зробити в основному той же процес, що ми 41 00:02:28,790 --> 00:02:30,030 збирається йти до сьогоднішнього дня. 42 00:02:30,030 --> 00:02:34,100 Але якщо у вас не було, що інструмент, що б ви зробили? 43 00:02:34,100 --> 00:02:37,570 >> Ну, ви могли б виглядати і побачити і сказати, що я в Бостоні. 44 00:02:37,570 --> 00:02:41,520 Які рейси доступні для мене? 45 00:02:41,520 --> 00:02:44,390 Тепер, можливо, я три можливі рейси з Бостона 46 00:02:44,390 --> 00:02:47,180 який буде відповідати часу коли мені потрібно піти. 47 00:02:47,180 --> 00:02:48,830 Я міг би летіти в Чикаго. 48 00:02:48,830 --> 00:02:50,130 Або я міг би літати в Майамі. 49 00:02:50,130 --> 00:02:53,340 Або я міг би літати в Нью-Йорк. 50 00:02:53,340 --> 00:02:56,980 Я міг би потім подивитися один від одне з тих міст призначення 51 00:02:56,980 --> 00:03:00,650 і думати про яких місцях Я міг би досягти 52 00:03:00,650 --> 00:03:03,020 від кожного з цих окремих міст. 53 00:03:03,020 --> 00:03:07,390 >> Так, може бути, з Чикаго, я можу отримати прямий рейс в Сан-Франциско. 54 00:03:07,390 --> 00:03:09,550 Це відмінно. 55 00:03:09,550 --> 00:03:12,360 Або я міг би отримати рейс в Денвері. 56 00:03:12,360 --> 00:03:16,970 Тепер, може бути, що політ в Сан-Франциско є ідеальним рішенням для мене, 57 00:03:16,970 --> 00:03:19,530 але, можливо, немає. 58 00:03:19,530 --> 00:03:22,180 Може бути, я шукаю щось що це трохи дешевше 59 00:03:22,180 --> 00:03:24,920 або трохи краще для мого графіка. 60 00:03:24,920 --> 00:03:29,197 І тому я міг дивитися на те, що інші Можливості можуть бути там. 61 00:03:29,197 --> 00:03:30,280 Так що я міг дивитися в Денвері. 62 00:03:30,280 --> 00:03:33,870 І з Денвера, ну, може бути, Я можу отримати політ у Остін. 63 00:03:33,870 --> 00:03:37,080 І з Остіна, може бути, я можу отримати Політ в Фінікс, з Фінікса і 64 00:03:37,080 --> 00:03:40,190 в Сан-Франциско. 65 00:03:40,190 --> 00:03:42,730 Тепер, я ще цього не зробили. 66 00:03:42,730 --> 00:03:45,640 Тому що, може бути, є Прямий рейс з Нью-Йорка 67 00:03:45,640 --> 00:03:47,850 в Сан-Франциско, який ідеально підходить для мене. 68 00:03:47,850 --> 00:03:53,354 Або, може бути, є політ з Майамі через Денвер, що це набагато дешевше. 69 00:03:53,354 --> 00:03:54,270 Так що я досі йти. 70 00:03:54,270 --> 00:03:58,200 І я досі дивлюся на всіх тих, міста, які я ще не вивчені. 71 00:03:58,200 --> 00:04:04,220 Я повинен вичерпно перевірити всі можливості, які я міг би мати. 72 00:04:04,220 --> 00:04:09,610 >> Так з Нью-Йорка, може бути, я можу отримати Політ в Нешвіллі, і з Нешвілла 73 00:04:09,610 --> 00:04:10,336 Остін. 74 00:04:10,336 --> 00:04:11,460 І тоді я знаю, де я перебуваю. 75 00:04:11,460 --> 00:04:14,252 І тоді я знаю, з Остіна, я можу летіти в Фінікс, з Фінікса і 76 00:04:14,252 --> 00:04:14,960 в Сан-Франциско. 77 00:04:14,960 --> 00:04:18,240 78 00:04:18,240 --> 00:04:22,830 Якщо я літаю першого Майамі, хоча, може бути, я можу отримати рейс з Майамі 79 00:04:22,830 --> 00:04:25,080 в Нешвілл, або з Майамі в Остіні. 80 00:04:25,080 --> 00:04:27,950 81 00:04:27,950 --> 00:04:30,860 >> А тепер я спробував все можливостей. 82 00:04:30,860 --> 00:04:36,310 Я побудував цей графік, показує мені всі можливі маршрути 83 00:04:36,310 --> 00:04:37,790 що я міг би бути в змозі прийняти. 84 00:04:37,790 --> 00:04:40,510 85 00:04:40,510 --> 00:04:43,640 Коли ми представляємо ці види проблем, 86 00:04:43,640 --> 00:04:47,870 ми не збираємося представляти їм явно, як цього графіка, 87 00:04:47,870 --> 00:04:51,590 бо граф не уявляють історія, де ми пішли. 88 00:04:51,590 --> 00:04:55,260 Знаючи, що я вилетів з Фенікс в Сан-Франциско 89 00:04:55,260 --> 00:05:01,690 не скажите мені, чи прийшла я за допомогою Нешвілл, або через Денвер, або через Майамі. 90 00:05:01,690 --> 00:05:06,430 >> Так що я буду робити, натомість Я візьму цей ж проблеми, 91 00:05:06,430 --> 00:05:09,140 і я буду представляти його у вигляді дерева. 92 00:05:09,140 --> 00:05:14,300 І в корені дерева, на зверху, я покладу місце, що я почав, 93 00:05:14,300 --> 00:05:16,590 Бостон. 94 00:05:16,590 --> 00:05:19,310 І з Бостона, я буду дивитися на всі можливі місця 95 00:05:19,310 --> 00:05:20,380 що я можу поїхати в. 96 00:05:20,380 --> 00:05:25,480 Ну, в цьому випадку, у мене було три, Чикаго, Нью-Йорк, і Майамі. 97 00:05:25,480 --> 00:05:29,850 І тоді я буду досліджувати кожен з ці діти в дереві. 98 00:05:29,850 --> 00:05:32,690 >> З Чикаго, я бачив що я мав два рейси. 99 00:05:32,690 --> 00:05:35,940 Я міг би літати безпосередньо Сан - Франциско або Денвера. 100 00:05:35,940 --> 00:05:37,740 Тепер Сан-Франциско, це моя мета. 101 00:05:37,740 --> 00:05:39,790 Це моя призначення. 102 00:05:39,790 --> 00:05:42,220 Це збирається бути лист цього дерева. 103 00:05:42,220 --> 00:05:45,340 Тобто, я ніколи не буду йти десь після Сан-Франциско. 104 00:05:45,340 --> 00:05:47,850 105 00:05:47,850 --> 00:05:50,340 З Денвера, хоча, Я можу літати з Денвера 106 00:05:50,340 --> 00:05:54,220 Остін, з Остіна в Фінікс, і з Фенікса в Сан-Франциско. 107 00:05:54,220 --> 00:05:56,050 І тепер знову, я досяг лист. 108 00:05:56,050 --> 00:05:59,470 109 00:05:59,470 --> 00:06:03,980 >> Я міг би повернутися на наступний місто, яке я не повністю вивчені. 110 00:06:03,980 --> 00:06:07,440 Це було б в Нью-Йорку, перейдіть назад до вершини мого дерева, 111 00:06:07,440 --> 00:06:09,160 спуститися в Нью-Йорку. 112 00:06:09,160 --> 00:06:12,700 З Нью-Йорка, я можу летіти в Нешвілл, з Нешвілла в Остіні, 113 00:06:12,700 --> 00:06:17,290 з Остіна в Фінікс, і з Фенікса в Сан-Франциско. 114 00:06:17,290 --> 00:06:20,170 І, нарешті, місто, яке я не дивився на все ж, Майамі. 115 00:06:20,170 --> 00:06:24,600 >> Ну, з Майамі я сказав, було два Можливості, Нешвілл або Остін. 116 00:06:24,600 --> 00:06:28,810 Якщо я літаю в Нешвіллі, а потім я літаю з Нешвілла, в Остін, в Фенікс, 117 00:06:28,810 --> 00:06:29,640 в Сан-Франциско. 118 00:06:29,640 --> 00:06:33,600 Якщо я літаю в Остіні, я літаю Остін, в Фінікс, Сан-Франциско. 119 00:06:33,600 --> 00:06:36,340 І тепер у мене є дерево. 120 00:06:36,340 --> 00:06:37,230 Це повне дерево. 121 00:06:37,230 --> 00:06:41,890 Це всі можливості і всі шляхи, що я міг би прийняти. 122 00:06:41,890 --> 00:06:44,310 Тобто, якщо я почну на корінь дерева у верхній 123 00:06:44,310 --> 00:06:47,860 і я йду до однієї з листя, він каже мені, не тільки 124 00:06:47,860 --> 00:06:50,480 де я збираюся зрештою, Сан-Франциско, 125 00:06:50,480 --> 00:06:53,670 але він каже мені, що маршрут Мені потрібно, щоб дістатися там. 126 00:06:53,670 --> 00:06:56,400 127 00:06:56,400 --> 00:06:59,690 >> Тепер, що один з них краще? 128 00:06:59,690 --> 00:07:02,430 Ну, нічого про це Проблема ще говорить мені, 129 00:07:02,430 --> 00:07:04,710 який з них є кращим рішенням. 130 00:07:04,710 --> 00:07:09,270 Може бути, я все одно найбільше скільки разів я в повітрі, 131 00:07:09,270 --> 00:07:12,350 або відстань, що я лечу. 132 00:07:12,350 --> 00:07:16,410 У цьому випадку, Чикаго Сан Франциско може бути короткий номер 133 00:07:16,410 --> 00:07:18,910 миль в повітрі. 134 00:07:18,910 --> 00:07:20,860 >> Може бути, я дбаю про вартість. 135 00:07:20,860 --> 00:07:23,680 І всі ми знаємо прямі рейси як правило, дорожче. 136 00:07:23,680 --> 00:07:26,610 Так, може бути, якщо я візьму це вигляд зворотного маршрутом 137 00:07:26,610 --> 00:07:30,650 через Майамі, Нешвіллі, Остін, Фінікс, може бути, тоді 138 00:07:30,650 --> 00:07:34,070 Я отримати більш низьку ціну. 139 00:07:34,070 --> 00:07:36,440 Але я міг би оптимізувати на будь-якому Критерії, які я дбаю. 140 00:07:36,440 --> 00:07:39,790 Хто отримав кращий в Політ Wi-Fi, або які 141 00:07:39,790 --> 00:07:43,110 аеропорти мають найкраща їжа доступна. 142 00:07:43,110 --> 00:07:47,280 І кожен з тих, хто може дати мені інше рішення 143 00:07:47,280 --> 00:07:49,215 що я бачу як кращий. 144 00:07:49,215 --> 00:07:51,990 145 00:07:51,990 --> 00:07:54,400 >> Ці види проблем куди ми йдемо 146 00:07:54,400 --> 00:07:58,480 побудувати цю дерево Можливості, а потім 147 00:07:58,480 --> 00:08:02,100 подивитися на кожен з тих, окремі доріжки, і вивчити 148 00:08:02,100 --> 00:08:05,270 які з цих виконує критерієм для нас, 149 00:08:05,270 --> 00:08:08,790 ми збираємося називати ці проблеми пошуку. 150 00:08:08,790 --> 00:08:11,280 І у нас є багато Алгоритми, деякі з яких 151 00:08:11,280 --> 00:08:15,270 ми вже бачили, щоб піти і досліджувати ці дерева. 152 00:08:15,270 --> 00:08:19,270 Ми могли б зробити це таким чином, що я тільки що зробили, в глибину пошуку, 153 00:08:19,270 --> 00:08:22,900 спускаючись, наскільки ми можемо поки ми хіт лист, а потім повертатися вгору, 154 00:08:22,900 --> 00:08:24,787 і збирається назад вниз. 155 00:08:24,787 --> 00:08:26,870 Або ми могли б робити те, що називається пошук в ширину. 156 00:08:26,870 --> 00:08:29,675 Ми могли б розширити всі у верхній частині, а потім 157 00:08:29,675 --> 00:08:31,550 все одна лінія під цим, і потім 158 00:08:31,550 --> 00:08:35,240 все одна лінія під цим. 159 00:08:35,240 --> 00:08:41,250 Ці дерева пошуку є основоположними для ШІ. 160 00:08:41,250 --> 00:08:46,570 Але вони не зовсім розумію це право весь час. 161 00:08:46,570 --> 00:08:51,600 Насправді, у багатьох випадків що ми дійсно дбаємо про, 162 00:08:51,600 --> 00:08:54,430 ми хочемо побудувати дерево, але ми насправді не 163 00:08:54,430 --> 00:08:57,140 отримати, щоб всі рішення. 164 00:08:57,140 --> 00:09:00,940 >> Це ситуації, звані змагальності пошук, також відомий 165 00:09:00,940 --> 00:09:05,390 про те, як написати гру грати системи і платять за це. 166 00:09:05,390 --> 00:09:07,940 Але ці види систем, де я 167 00:09:07,940 --> 00:09:12,920 може отримати, щоб вибрати, коли я йду від Бостон, яке місто я йду до наступного. 168 00:09:12,920 --> 00:09:19,990 Але після цього, хтось може отримати прийняти рішення про те, де я літаю. 169 00:09:19,990 --> 00:09:24,040 Таким чином, щоб побудувати ці види структури, ми 170 00:09:24,040 --> 00:09:28,510 доведеться прийняти трохи Інший підхід до неї. 171 00:09:28,510 --> 00:09:31,060 Ми не збираємося бути в змозі просто шукати по дереву 172 00:09:31,060 --> 00:09:35,000 більше, тому що ми не той, який контролює 173 00:09:35,000 --> 00:09:38,180 кожного з цих точок прийняття рішень. 174 00:09:38,180 --> 00:09:42,590 >> Отже, давайте уявимо собі простий ігри, як хрестики-нулики. 175 00:09:42,590 --> 00:09:46,730 Я міг би почати з повністю порожній борту. 176 00:09:46,730 --> 00:09:49,580 І в хрестики-нулики, Х добирається, щоб грати в першу чергу. 177 00:09:49,580 --> 00:09:53,890 І так я міг думати про все можливі ходи, які могли б зробити Х. 178 00:09:53,890 --> 00:09:57,420 І якщо я один гри Х, це здорово. 179 00:09:57,420 --> 00:10:01,020 У мене є дев'ять можливе рухається, що я можу зробити. 180 00:10:01,020 --> 00:10:05,000 Я міг би покласти X в одному з цих дев'яти позицій. 181 00:10:05,000 --> 00:10:10,710 >> А потім з кожної з них, я міг собі уявити, що станеться далі. 182 00:10:10,710 --> 00:10:14,130 Ну, в цьому випадку, інший Гравець отримає зайняти чергу. 183 00:10:14,130 --> 00:10:15,660 Про отримали б зайняти чергу. 184 00:10:15,660 --> 00:10:19,510 І від кожного з них, є буде вісім різних місць 185 00:10:19,510 --> 00:10:22,980 що О може поставити їх маркер. 186 00:10:22,980 --> 00:10:25,790 >> Скажімо, я вирішив, що я був збирається покласти X в центрі. 187 00:10:25,790 --> 00:10:28,810 Це завжди здається хороший відкриття хід. 188 00:10:28,810 --> 00:10:34,870 Я міг дивитися на під того, восьмій можливих кроків, які робить. Про 189 00:10:34,870 --> 00:10:37,320 Тепер, якщо я граю X, це чудово. 190 00:10:37,320 --> 00:10:41,740 Я отримую вибрати, який я йти, один в середині. 191 00:10:41,740 --> 00:10:45,000 Але тепер Про отримує, щоб вибрати. 192 00:10:45,000 --> 00:10:48,750 І я не мають контролю протягом цього рішення. 193 00:10:48,750 --> 00:10:51,670 >> Але з кожною з них можливі позиції дошка, 194 00:10:51,670 --> 00:10:54,020 є інший безліч можливостей. 195 00:10:54,020 --> 00:10:56,700 Коли справа доходить до бути моя черга знову, я б 196 00:10:56,700 --> 00:11:01,500 отримати, щоб забрати і сказати, ну, якщо Про переходить в, ну, 197 00:11:01,500 --> 00:11:06,110 середній пляма на лівій, а потім У мене є набір можливостей 198 00:11:06,110 --> 00:11:09,740 де я можу взяти мій наступний крок. 199 00:11:09,740 --> 00:11:14,140 З них, я міг розглянути всі можливості під ними. 200 00:11:14,140 --> 00:11:18,030 А потім виведення отримаєте вибрати серед тих ,. 201 00:11:18,030 --> 00:11:22,290 >> І я міг би продовжувати будувати цей дерево не, поки я потрапив в точку, 202 00:11:22,290 --> 00:11:26,960 де або хтось виграє game-- Це 203 00:11:26,960 --> 00:11:31,070 має бути розглянутий лист node-- або плата повністю заповнений 204 00:11:31,070 --> 00:11:32,704 і ніхто не виграв. 205 00:11:32,704 --> 00:11:34,370 І це також буде кінцевий вузол. 206 00:11:34,370 --> 00:11:35,411 Це збирається бути краватку. 207 00:11:35,411 --> 00:11:37,820 208 00:11:37,820 --> 00:11:41,680 >> Але хитра річ з цим якби це було просто черговий пошук 209 00:11:41,680 --> 00:11:44,269 проблема, я був би в змозі скажімо, ну, X повинен йти тут. 210 00:11:44,269 --> 00:11:45,560 І Про повинні йти шлях там. 211 00:11:45,560 --> 00:11:46,770 І тоді Х повинні йти сюди. 212 00:11:46,770 --> 00:11:48,269 А потім виводу повинні йти шлях там. 213 00:11:48,269 --> 00:11:51,860 І тоді Х може одержати три в рядку, і я виграю. 214 00:11:51,860 --> 00:11:54,870 І гра буде закінчена в п'яти ходів, три для мене, 215 00:11:54,870 --> 00:11:57,710 два для мого опонента. 216 00:11:57,710 --> 00:12:01,300 Але я не завжди можете вибрати, що. 217 00:12:01,300 --> 00:12:03,720 >> Таким чином, замість, того, що ми доведеться робити 218 00:12:03,720 --> 00:12:06,270 що ми будемо мати мати нову стратегію. 219 00:12:06,270 --> 00:12:09,350 І стратегія, що ігрові алгоритми часто використовують 220 00:12:09,350 --> 00:12:12,000 це те, що називається мінімаксної. 221 00:12:12,000 --> 00:12:15,500 Центральна ідея мінімаксний, що ми 222 00:12:15,500 --> 00:12:21,365 збирається забрати крок, який дає наш опонент найгірший набір 223 00:12:21,365 --> 00:12:22,790 ходів, що вони можуть зробити. 224 00:12:22,790 --> 00:12:25,570 225 00:12:25,570 --> 00:12:28,870 Це не робить мені нічого хорошого вибрати крок де 226 00:12:28,870 --> 00:12:31,952 Я міг би бути в змозі виграти після що, тому що мій суперник не 227 00:12:31,952 --> 00:12:33,160 збирається дати мені цей шанс. 228 00:12:33,160 --> 00:12:37,770 Вони збираються вибрати деякі жахливо результат для мене. 229 00:12:37,770 --> 00:12:42,010 Так що я збираюся зробити рухатися, що змушує мого опонента 230 00:12:42,010 --> 00:12:45,760 зробити щось краще для мене. 231 00:12:45,760 --> 00:12:46,260 Добре. 232 00:12:46,260 --> 00:12:48,410 Давайте подивимося, як це втрачає значення. 233 00:12:48,410 --> 00:12:51,640 Так от наш алгоритм псевдокоді. 234 00:12:51,640 --> 00:12:54,450 Ми збираємося, щоб генерувати все дерево гри. 235 00:12:54,450 --> 00:12:56,757 Ми збираємося побудувати вся структура. 236 00:12:56,757 --> 00:12:57,840 І тоді ми будемо йти до кінця. 237 00:12:57,840 --> 00:13:02,100 І в самому низу на кожній з термінальними вузлами, в кожному з листя, 238 00:13:02,100 --> 00:13:07,850 ми оцінити, як цінно те, що зі мною? 239 00:13:07,850 --> 00:13:11,690 І ми збираємося вартості речей, які добре для мене, як бути позитивним. 240 00:13:11,690 --> 00:13:14,460 Речі, які не дуже добре для мене буде менше позитивним або дорівнює нулю, 241 00:13:14,460 --> 00:13:16,480 або навіть негативним. 242 00:13:16,480 --> 00:13:19,240 >> Таким чином, в хрестики-нулики, може бути, перемога для мене це добре. 243 00:13:19,240 --> 00:13:20,290 Ось один. 244 00:13:20,290 --> 00:13:22,400 І краватка нулю. 245 00:13:22,400 --> 00:13:26,230 І те, що це втрата для мені, може бути, це негативний. 246 00:13:26,230 --> 00:13:29,620 Все, що має значення в тому, що краще це для мене, тим вище оцінка 247 00:13:29,620 --> 00:13:32,160 він отримує. 248 00:13:32,160 --> 00:13:36,690 Від цих можливостей на знизу, тоді ми будемо фільтрувати вгору. 249 00:13:36,690 --> 00:13:40,650 І коли це мій шанс вибрати серед безлічі альтернатив, 250 00:13:40,650 --> 00:13:44,460 Я виберу той, який отримав найвищий бал. 251 00:13:44,460 --> 00:13:47,200 >> І всякий раз, коли це моя Противники чергу вибирати, 252 00:13:47,200 --> 00:13:52,350 Я припускаю, що вони збираються вибрати один з найнижчим рахунком. 253 00:13:52,350 --> 00:13:56,090 І якщо я зроблю це весь шлях до верхньої частини дерева, 254 00:13:56,090 --> 00:14:03,150 Я вибрав шлях, який дає мені найкращий результат, що я можу отримати, 255 00:14:03,150 --> 00:14:09,110 припускаючи, що мій опонент робить все правильні кроки. 256 00:14:09,110 --> 00:14:11,940 >> Гаразд, так що давайте подивимося це дія першого. 257 00:14:11,940 --> 00:14:14,980 І тоді ми будемо насправді подивитися на код для нього. 258 00:14:14,980 --> 00:14:16,780 Отже, уявіть, у мене є цей великий дерево. 259 00:14:16,780 --> 00:14:18,280 А тепер я не граю в хрестики-нулики. 260 00:14:18,280 --> 00:14:20,405 Я хотів, щоб дати вам щось трохи багатшими. 261 00:14:20,405 --> 00:14:23,560 Так що я отримав деяку гру, де є багато різних забиває 262 00:14:23,560 --> 00:14:26,390 що я міг би в кінці. 263 00:14:26,390 --> 00:14:27,980 І тому я побудувати це повне дерево. 264 00:14:27,980 --> 00:14:29,070 І я отримую перший хід. 265 00:14:29,070 --> 00:14:31,290 Я в корені дерева. 266 00:14:31,290 --> 00:14:36,150 >> І я отримую вибрати that-- так що я отримую максимально по цій першого вузла. 267 00:14:36,150 --> 00:14:38,410 І тоді мій опонент отримує йти. 268 00:14:38,410 --> 00:14:41,910 І тоді я йти ще раз. 269 00:14:41,910 --> 00:14:46,830 Так на дні, у мене є набір Можливості, які я можу вибрати з, 270 00:14:46,830 --> 00:14:50,570 різні термінальні стани гри. 271 00:14:50,570 --> 00:14:54,980 Якщо я вниз, що далеко лівому кутку, 272 00:14:54,980 --> 00:14:58,867 і я бачу, що у мене є вибір між восьмій, сім, і два, 273 00:14:58,867 --> 00:15:00,450 ну, я той, який отримує на вибір. 274 00:15:00,450 --> 00:15:02,910 Так що я збираюся вибрати одним з кращих з них. 275 00:15:02,910 --> 00:15:05,650 Я збираюся вибрати восьмій. 276 00:15:05,650 --> 00:15:10,090 >> Так що я знаю, що якщо я коли-небудь приступимо до цієї точки, 277 00:15:10,090 --> 00:15:13,890 Я буду в змозі отримати що вісім очок. 278 00:15:13,890 --> 00:15:17,410 Якщо я в кінцевому підсумку в наступній точці більше, наступний вузол протягом, 279 00:15:17,410 --> 00:15:20,760 дев'ятій, один, або шість, ну, я збирається вибрати кращий з них. 280 00:15:20,760 --> 00:15:21,950 Я виберу дев'ятій. 281 00:15:21,950 --> 00:15:24,880 Якщо у мене є вибір між два, а чотири, і один, 282 00:15:24,880 --> 00:15:28,240 Я виберу чотирьох, найвищий. 283 00:15:28,240 --> 00:15:31,990 >> Тепер, якщо я дивлюся на рівні вище, що, мій опонент 284 00:15:31,990 --> 00:15:34,440 це один отримує, щоб зробити цей вибір. 285 00:15:34,440 --> 00:15:37,040 Так що мій противник отримує вибрати, я хочу, щоб дати йому 286 00:15:37,040 --> 00:15:39,250 Те, що відбувається щоб отримати його вісім очок, 287 00:15:39,250 --> 00:15:41,916 або я даю йому річ, яка збираюся дати йому дев'ять очок, 288 00:15:41,916 --> 00:15:45,240 або річ, яка відбувається щоб дати йому чотири очки? 289 00:15:45,240 --> 00:15:49,130 І мій опонент, будучи раціональним, буде 290 00:15:49,130 --> 00:15:53,470 вибрати мінімум тим, буде вибрати чотири. 291 00:15:53,470 --> 00:15:56,020 >> І я можу це зробити через весь дерева. 292 00:15:56,020 --> 00:15:59,110 Я можу спуститися до того, що середній набір з трьох. 293 00:15:59,110 --> 00:16:01,517 І я можу вибрати між один, три, п'ять. 294 00:16:01,517 --> 00:16:02,350 І я отримую, щоб вибрати. 295 00:16:02,350 --> 00:16:03,810 Так що я вибрати п'ять. 296 00:16:03,810 --> 00:16:05,340 Я можу вибрати три, дев'ять, або два. 297 00:16:05,340 --> 00:16:07,570 Я отримую вибрати, так що я вибрати дев'ять. 298 00:16:07,570 --> 00:16:09,290 Шість, п'ять, або два, я вибираю. 299 00:16:09,290 --> 00:16:11,539 Я отримую вибрати шість. 300 00:16:11,539 --> 00:16:13,080 Рівень вище того, хто отримує, щоб вибрати? 301 00:16:13,080 --> 00:16:16,280 302 00:16:16,280 --> 00:16:18,140 Хто отримує вибрати? 303 00:16:18,140 --> 00:16:20,000 Інший хлопець, мій опонент. 304 00:16:20,000 --> 00:16:22,583 Так вони вибирають п'ять, дев'ятій, або шість, то які? 305 00:16:22,583 --> 00:16:23,410 >> Аудиторія: п'ять. 306 00:16:23,410 --> 00:16:25,250 >> СЛУХАЛИ: Вони вибирають п'ять. 307 00:16:25,250 --> 00:16:27,400 Вони отримують, щоб вибрати мінімум. 308 00:16:27,400 --> 00:16:29,690 І тоді останній, вибрати один, два, або три. 309 00:16:29,690 --> 00:16:31,720 Я отримую вибрати, так що я вибрати три. 310 00:16:31,720 --> 00:16:34,370 Дев'ять, сім, або два, я вибираю дев'ятій. 311 00:16:34,370 --> 00:16:37,070 І 11, шість або чотири, я вибираю 11. 312 00:16:37,070 --> 00:16:41,190 Мій опонент добирає три, дев'яти або 11, вибирає мінімальне. 313 00:16:41,190 --> 00:16:43,290 Він дає мені три. 314 00:16:43,290 --> 00:16:47,780 І, нарешті у верхній частині дерево, я отримую, щоб вибрати знову. 315 00:16:47,780 --> 00:16:51,190 І я отримую вибирати між чотири, п'ять, або три. 316 00:16:51,190 --> 00:16:52,270 Отже, я беру на п'ять. 317 00:16:52,270 --> 00:16:55,070 318 00:16:55,070 --> 00:17:00,891 >> Якби я отримав все контролювати, я б встати на шлях, який привів до 11. 319 00:17:00,891 --> 00:17:02,390 Але я не отримую, щоб зробити цей вибір. 320 00:17:02,390 --> 00:17:04,220 Якщо я йду цим шляхом. 321 00:17:04,220 --> 00:17:10,710 Мій опонент змусить мене в вибір, який призводить до трьох. 322 00:17:10,710 --> 00:17:14,530 Таким чином, найкраще, що я можу зробити, це прийняти, що середній філія, 323 00:17:14,530 --> 00:17:19,859 зробити цей вибір, що в кінцевому рахунку збирається привести мене до п'яти очок. 324 00:17:19,859 --> 00:17:23,230 Це те, що робить минимакса. 325 00:17:23,230 --> 00:17:23,807 >> Добре. 326 00:17:23,807 --> 00:17:24,890 Давайте поглянемо на це. 327 00:17:24,890 --> 00:17:27,480 328 00:17:27,480 --> 00:17:32,330 Так от в CS50 IDE це програма, яка 329 00:17:32,330 --> 00:17:36,540 реалізує минимакса грати в хрестики-нулики. 330 00:17:36,540 --> 00:17:40,100 Ми збираємося побудувати до вистави. 331 00:17:40,100 --> 00:17:44,390 Ми збираємося мати два opponent-- або двох гравців, наш комп'ютер 332 00:17:44,390 --> 00:17:46,090 плеєр і програвач людини. 333 00:17:46,090 --> 00:17:48,980 334 00:17:48,980 --> 00:17:53,090 Номер гравця один буде грати О. Це буде машина гравець. 335 00:17:53,090 --> 00:17:55,747 Вони отримують, щоб перемістити секунду. 336 00:17:55,747 --> 00:17:57,830 І інший гравець, наш людина-плеєр, буде X. 337 00:17:57,830 --> 00:17:59,880 >> І зробити моє життя трохи просто, я йду 338 00:17:59,880 --> 00:18:03,060 маркувати, що гравець негативний. 339 00:18:03,060 --> 00:18:05,026 Так що я можу просто помножити на мінус одиницю, щоб поміняти 340 00:18:05,026 --> 00:18:06,400 між одним гравцем і іншим. 341 00:18:06,400 --> 00:18:09,030 342 00:18:09,030 --> 00:18:12,250 Гаразд, так що давайте поглянемо на те, що ми насправді збирається робити. 343 00:18:12,250 --> 00:18:15,840 Ми збираємося, щоб визначити наша порада. 344 00:18:15,840 --> 00:18:19,060 Це буде добре, ми збираємося щоб вона могла бути три на три, 345 00:18:19,060 --> 00:18:21,580 або ми можемо навіть грати п'ять на п'ять чи сім 346 00:18:21,580 --> 00:18:28,870 на сім хрестики-нулики, якщо ви хочете як, грунтуючись на якийсь розмірності D. 347 00:18:28,870 --> 00:18:31,260 >> І ми будемо мати пару з допоміжних функцій 348 00:18:31,260 --> 00:18:34,360 що буде робити речі, як ініціалізувати screen-- або вибачте, 349 00:18:34,360 --> 00:18:38,900 ініціалізувати наші змінні, зніміть екраном, намалювати дошку на екрані, 350 00:18:38,900 --> 00:18:41,060 який перевіряє дошка щоб побачити або НЕ 351 00:18:41,060 --> 00:18:44,520 є переможець, який розбирає за допомогою командного рядка, 352 00:18:44,520 --> 00:18:50,670 просто, щоб допомогти, той, який зчитує вхід, і одна функція називається мінімаксної. 353 00:18:50,670 --> 00:18:52,746 І це один ми дбаємо найбільше. 354 00:18:52,746 --> 00:18:54,120 Але давайте спочатку подивимося на основний. 355 00:18:54,120 --> 00:18:57,490 356 00:18:57,490 --> 00:18:58,510 >> Що ми робимо? 357 00:18:58,510 --> 00:19:00,570 Ну, ми збираємося розібрати нашу командний рядок, 358 00:19:00,570 --> 00:19:04,300 щойно прочитав і подивитися, що Розмір плати, ми хотіли б мати. 359 00:19:04,300 --> 00:19:07,330 Ми ініціалізувати плату. 360 00:19:07,330 --> 00:19:10,360 І тоді ми будемо вводити одне великий дикий цикл, неодноразово 361 00:19:10,360 --> 00:19:16,630 прийняти кроки, поки гра не виграв, або немає ніяких переміщається вліво. 362 00:19:16,630 --> 00:19:20,560 Кожен раз, коли ми йдемо через це цикл, ми очистити екран. 363 00:19:20,560 --> 00:19:23,290 Ми будемо малювати дошка на екрані. 364 00:19:23,290 --> 00:19:28,750 І ми навмисно роду абстрагуючись від них у вигляді підпрограм, 365 00:19:28,750 --> 00:19:32,030 так, що ми не повинні надто турбуватися про подробиці, як вони відбуваються. 366 00:19:32,030 --> 00:19:33,480 >> Ви будете мати код пізніше сьогодні. 367 00:19:33,480 --> 00:19:37,970 І якщо ви хочете, щоб дивитися через і з'ясувати це, ви можете побачити їх усі. 368 00:19:37,970 --> 00:19:39,890 Але ми будемо малювати дошку на екрані. 369 00:19:39,890 --> 00:19:43,620 І тоді ми будемо перевіряти і см, у нас є переможець? 370 00:19:43,620 --> 00:19:46,290 Хтось виграв цю гру? 371 00:19:46,290 --> 00:19:49,260 Якщо у них є, ми роздрукувати з повідомлення перемога. 372 00:19:49,260 --> 00:19:51,680 І ми будемо закінчити гру. 373 00:19:51,680 --> 00:19:54,510 >> Ми також перевірити і побачити, якщо є краватка. 374 00:19:54,510 --> 00:19:56,620 Це буде легко побачити, якщо є краватка. 375 00:19:56,620 --> 00:20:00,700 Це означає, що всі простори повні, але не був переможцем ще. 376 00:20:00,700 --> 00:20:03,580 Ми можемо оголосити краватку і зробити. 377 00:20:03,580 --> 00:20:10,530 Тоді реальна meat-- якщо це машина плеєр, 378 00:20:10,530 --> 00:20:14,120 ми допустити, що машина плеєр для пошуку 379 00:20:14,120 --> 00:20:19,500 шляхом використання цього алгоритму мінімаксного, знайти кращий хід, що він може. 380 00:20:19,500 --> 00:20:22,310 І тоді ми будемо покласти, що рухатися вгору. 381 00:20:22,310 --> 00:20:27,640 >> В іншому випадку, якщо це людина-плеєр, ми читатимемо деякі матеріали з людини. 382 00:20:27,640 --> 00:20:30,800 А потім будь то людина гравець чи машина плеєр, 383 00:20:30,800 --> 00:20:32,800 ми зробимо пару трохи біти перевірки помилок, 384 00:20:32,800 --> 00:20:36,910 переконайтеся, що він залишається в межах кордонів з фактичних розмірів плати 385 00:20:36,910 --> 00:20:40,040 що у нас є, переконайтеся, що що цей простір порожньо, 386 00:20:40,040 --> 00:20:43,570 що ніхто поставимо шматок там вже. 387 00:20:43,570 --> 00:20:45,810 І тоді ми будемо просто покласти шматок на борту, 388 00:20:45,810 --> 00:20:51,550 змінити гравця на наступний рівень, і збільшити скільки ходів сталося. 389 00:20:51,550 --> 00:20:54,090 >> Це основний цикл для наш хрестики-нулики гра. 390 00:20:54,090 --> 00:20:57,000 391 00:20:57,000 --> 00:21:02,340 Мінімакс, то, точно алгоритм, який ми раніше. 392 00:21:02,340 --> 00:21:04,710 Єдине, що регулювання ми зробили так, що ми 393 00:21:04,710 --> 00:21:07,290 може грати більш мірних плат ми в 394 00:21:07,290 --> 00:21:11,070 зберегти цей додатковий параметр, званий глибина. 395 00:21:11,070 --> 00:21:14,870 І глибина просто каже, якщо я пошук вниз через цього дерева 396 00:21:14,870 --> 00:21:19,022 і я так далеко вниз за деякій глибині рівня 397 00:21:19,022 --> 00:21:20,730 що я просто не хочу, щоб йти далі, 398 00:21:20,730 --> 00:21:25,630 Я збираюся зупинитися і просто оцінити дошка в цій точці. 399 00:21:25,630 --> 00:21:27,310 Я перевірити і подивитися, якщо є переможець. 400 00:21:27,310 --> 00:21:29,240 Якщо є переможець, я їх повернути. 401 00:21:29,240 --> 00:21:31,720 В іншому випадку, я піду через петлю. 402 00:21:31,720 --> 00:21:34,380 І я скажу, для всіх можливі місця 403 00:21:34,380 --> 00:21:38,080 що я міг, можливо, взяти в якості мого переїзду, я 404 00:21:38,080 --> 00:21:43,760 побудувати гіпотетичну рада, яка включає в себе свій хід на цьому борту, 405 00:21:43,760 --> 00:21:45,960 а потім рекурсивно викликає минимакса. 406 00:21:45,960 --> 00:21:49,360 407 00:21:49,360 --> 00:21:53,900 >> Якщо це мій крок, я отримую, щоб знайти той, який отримав найбільшу кількість балів. 408 00:21:53,900 --> 00:21:58,710 Якщо цей рух мого опонента, ми знаходимо той, який отримав мінімальний бал. 409 00:21:58,710 --> 00:22:02,240 І все інше просто облік. 410 00:22:02,240 --> 00:22:04,789 Гаразд, так що давайте подивимося цей пробіг. 411 00:22:04,789 --> 00:22:06,830 Насправді, може бути, ми можемо отримати пару добровольців 412 00:22:06,830 --> 00:22:09,930 прийти і грати в хрестики-нулики. 413 00:22:09,930 --> 00:22:12,780 [Нерозбірливо] одним, і один Більш того, два, прямо там. 414 00:22:12,780 --> 00:22:13,550 Давай до. 415 00:22:13,550 --> 00:22:19,290 416 00:22:19,290 --> 00:22:23,650 >> Так що давайте йти вперед і перезавантажити це повністю. 417 00:22:23,650 --> 00:22:24,150 Так, привіт. 418 00:22:24,150 --> 00:22:24,920 >> АУДИТОРІЯ: Привіт. 419 00:22:24,920 --> 00:22:25,420 >> СЛУХАЛИ: Ваше ім'я? 420 00:22:25,420 --> 00:22:26,086 >> АУДИТОРІЯ: Gorav. 421 00:22:26,086 --> 00:22:26,840 СЛУХАЛИ: Gorav. 422 00:22:26,840 --> 00:22:27,800 >> АУДИТОРІЯ: Я Лейла. 423 00:22:27,800 --> 00:22:29,490 >> СЛУХАЛИ: І Лейла, Лейла і, вибачте. 424 00:22:29,490 --> 00:22:30,384 Давай до. 425 00:22:30,384 --> 00:22:32,050 Gorav, ми збираємося, щоб ви йдете в першу чергу. 426 00:22:32,050 --> 00:22:37,710 І я попрошу вас бути не жахливо добре хрестики-нулики гравець. 427 00:22:37,710 --> 00:22:40,130 ОК, так що весь тиск на вас. 428 00:22:40,130 --> 00:22:44,660 Давайте подивимося, однак, що наша машина Гравець може зробити щось розумний. 429 00:22:44,660 --> 00:22:45,310 Так що вперед. 430 00:22:45,310 --> 00:22:49,830 Ви збираєтеся ввести в які координують Ви хотіли б поставити хрестик у. 431 00:22:49,830 --> 00:22:55,170 А0, ОК, і машина пішла відразу і поставити свій слід в А1. 432 00:22:55,170 --> 00:22:56,640 >> Поставте O на борту. 433 00:22:56,640 --> 00:22:58,970 Гаразд, тепер йди вперед. 434 00:22:58,970 --> 00:23:00,193 Де б ви хотіли поїхати? 435 00:23:00,193 --> 00:23:03,510 436 00:23:03,510 --> 00:23:05,090 С2. 437 00:23:05,090 --> 00:23:08,430 Наша машина гравець прийняв середній квадрат, заблокував вас. 438 00:23:08,430 --> 00:23:10,320 Так що це було добре, розумна річ для того, щоб зробити. 439 00:23:10,320 --> 00:23:13,430 440 00:23:13,430 --> 00:23:14,250 Ви заблокували. 441 00:23:14,250 --> 00:23:15,210 Це відмінно. 442 00:23:15,210 --> 00:23:16,390 Це подає кутовий там. 443 00:23:16,390 --> 00:23:23,890 444 00:23:23,890 --> 00:23:30,430 >> І це відбувається, щоб змусити вас взяти один останній простору, B0. 445 00:23:30,430 --> 00:23:32,220 І гра закінчується внічию. 446 00:23:32,220 --> 00:23:35,030 Але він грав розумний Гра проти вас, чи не так? 447 00:23:35,030 --> 00:23:36,956 Гаразд, спасибі дуже багато, Gorav. 448 00:23:36,956 --> 00:23:40,860 >> [Оплески] 449 00:23:40,860 --> 00:23:44,723 >> Гаразд, Лейла, ми збираємося до гри на вас тут. 450 00:23:44,723 --> 00:23:46,940 >> АУДИТОРІЯ: О, здорово. 451 00:23:46,940 --> 00:23:49,950 >> СПІКЕР: Ми збираємося дати Ви Чотири на чотири хрестики-нулики. 452 00:23:49,950 --> 00:23:54,760 Тепер, в чотири на чотири, у вас є, щоб виграти з чотирма поспіль, а не три в ряд. 453 00:23:54,760 --> 00:23:56,135 І це все твоє. 454 00:23:56,135 --> 00:24:02,180 455 00:24:02,180 --> 00:24:04,420 Так Лейла взяла D1. 456 00:24:04,420 --> 00:24:11,730 Тепер ми збираємося слідувати наш комп'ютер гравець тут. 457 00:24:11,730 --> 00:24:16,910 Три на три Tic-Tac-Toe є свого роду речі, які легко для всіх нас. 458 00:24:16,910 --> 00:24:21,960 Але це все одно приємно бачити комп'ютерного гравця робить правильні ходи. 459 00:24:21,960 --> 00:24:23,725 Чотири на чотири отримує бути трохи складніше. 460 00:24:23,725 --> 00:24:42,960 461 00:24:42,960 --> 00:24:44,230 >> Красиво зроблено. 462 00:24:44,230 --> 00:24:46,210 Гаразд, так Лейла закінчив с. 463 00:24:46,210 --> 00:24:48,270 О, і ми повинні закінчилися там. 464 00:24:48,270 --> 00:24:51,870 Але давайте зробимо ще один тут. 465 00:24:51,870 --> 00:24:53,480 Так Layla, спасибі. 466 00:24:53,480 --> 00:24:55,112 Красиво зроблено. 467 00:24:55,112 --> 00:24:57,517 >> [Оплески] 468 00:24:57,517 --> 00:25:00,410 469 00:25:00,410 --> 00:25:04,750 >> Таким чином, наша гра в хрестики-нулики гравець йде через і знаходить місця, 470 00:25:04,750 --> 00:25:07,040 вирішує їх за допомогою цієї минимакса. 471 00:25:07,040 --> 00:25:08,990 І я був настройку глибини на які так, щоб він 472 00:25:08,990 --> 00:25:11,010 не працюватиме занадто швидко, тому, напевно, 473 00:25:11,010 --> 00:25:16,790 Лейла була в змозі піти вперед красиво як вона, і зробив дуже добре. 474 00:25:16,790 --> 00:25:20,450 Але ці системи, що тільки пройти і перебір 475 00:25:20,450 --> 00:25:23,870 глибше, і глибше, і глибше, і продовжують знаходити рішення 476 00:25:23,870 --> 00:25:29,890 що їм потрібно, ці види систем досить успішно ці, ну, 477 00:25:29,890 --> 00:25:32,700 стандартні настільні ігри. 478 00:25:32,700 --> 00:25:37,060 >> І справді, якщо ми подивимося на три на три хрестики-нулики ігри, 479 00:25:37,060 --> 00:25:40,040 це в основному вирішена проблема. 480 00:25:40,040 --> 00:25:45,430 І це чудовий схема від Randall Манро в XKCD, 481 00:25:45,430 --> 00:25:52,130 показ, що переміщуються ви повинні прийняти, враховуючи рухається вашого супротивника. 482 00:25:52,130 --> 00:25:56,420 Це те, що ми могли б легко визначити заздалегідь. 483 00:25:56,420 --> 00:26:00,180 Але те, що відбувається, коли ми отримуємо більш складні ігри, більш складних ігор, 484 00:26:00,180 --> 00:26:05,690 де Є великі дошки, більш Можливості, глибше стратегія? 485 00:26:05,690 --> 00:26:09,660 >> Виявляється, що це перебір пошуку ще 486 00:26:09,660 --> 00:26:14,150 робить досить добре, за винятком того, коли ви дійдете до точки, 487 00:26:14,150 --> 00:26:19,230 де це дерево настільки великий що ви не можете уявити все це. 488 00:26:19,230 --> 00:26:22,370 489 00:26:22,370 --> 00:26:28,280 Якщо ви не можете обчислити все дерево, якщо ви не можете йти вперед і поштовх 490 00:26:28,280 --> 00:26:32,204 самі до точки, де ви отримав все дерево в пам'яті, 491 00:26:32,204 --> 00:26:34,370 або ви можете отримати його в пам'яті, і це буде тільки 492 00:26:34,370 --> 00:26:39,200 прийняти вас занадто довго, щоб шукати через це, у вас є щось робити розумніше. 493 00:26:39,200 --> 00:26:42,620 494 00:26:42,620 --> 00:26:46,450 >> Для того, щоб зробити це, вам потрібно зробити дві речі. 495 00:26:46,450 --> 00:26:49,030 По-перше, ви повинні знайти деякі спосіб обмеження глибину. 496 00:26:49,030 --> 00:26:50,370 Ну, це нормально. 497 00:26:50,370 --> 00:26:55,740 Ми можемо знайти хороший, мінімум і сказати, ви можете йти тільки так глибоко. 498 00:26:55,740 --> 00:27:00,890 Але коли ви це зробите, це означає, що вам ці частково неповні дошка. 499 00:27:00,890 --> 00:27:04,770 І ви повинні вибрати, я люблю це частково неповним дошка, 500 00:27:04,770 --> 00:27:08,600 або це частково неповну панель? 501 00:27:08,600 --> 00:27:11,910 >> А на наших чотирьох по чотирьох хрестики-нулики гра, 502 00:27:11,910 --> 00:27:15,240 наш комп'ютер гравець отримав вниз на дно і він сказав, 503 00:27:15,240 --> 00:27:16,800 У мене є два різних плат. 504 00:27:16,800 --> 00:27:17,940 Жоден виграш. 505 00:27:17,940 --> 00:27:19,120 Жоден збиток. 506 00:27:19,120 --> 00:27:22,070 Жоден краватку. 507 00:27:22,070 --> 00:27:24,100 Як вибрати між ними? 508 00:27:24,100 --> 00:27:26,200 І це не є розумний спосіб зробити це. 509 00:27:26,200 --> 00:27:28,910 510 00:27:28,910 --> 00:27:32,850 >> Ми бачимо, цей вид оцінка відбуваються весь час 511 00:27:32,850 --> 00:27:35,290 як ми отримуємо в більш складних іграх. 512 00:27:35,290 --> 00:27:37,600 Шахи є відмінним прикладом. 513 00:27:37,600 --> 00:27:41,550 У шахах, ми, по-перше за все, більше плата. 514 00:27:41,550 --> 00:27:43,370 У нас є набагато більше штук. 515 00:27:43,370 --> 00:27:47,930 І позиціонування цих частин і те, як ці шматочки рухатися 516 00:27:47,930 --> 00:27:50,370 є критично важливим. 517 00:27:50,370 --> 00:27:53,700 Так що, якщо я хочу використовувати минимакса, Мені потрібно, щоб мати можливість вказати 518 00:27:53,700 --> 00:27:58,240 і говорити, що це дошка, де ніхто не виграв чи програв ще, 519 00:27:58,240 --> 00:28:04,310 якось краще, ніж це інше дошка, де ніхто не виграв або програв. 520 00:28:04,310 --> 00:28:06,740 >> Щоб зробити це, я міг би зробити речі, як я міг би просто 521 00:28:06,740 --> 00:28:10,787 підрахувати, скільки штук у мене є і скільки штук у вас є? 522 00:28:10,787 --> 00:28:12,870 Або я міг би дати різні шт різні точки. 523 00:28:12,870 --> 00:28:14,420 Моя королева коштує 20 очок. 524 00:28:14,420 --> 00:28:16,500 Ваш пішак стоїть одне очко. 525 00:28:16,500 --> 00:28:18,920 Хто має спільної більше очок? 526 00:28:18,920 --> 00:28:22,300 Або я міг би розглянути речі, як, хто отримав кращу позицію дошка? 527 00:28:22,300 --> 00:28:26,820 Чия чергу це поруч, все, що я можу 528 00:28:26,820 --> 00:28:31,220 зробити, щоб оцінити більш точно які з цих можливостей 529 00:28:31,220 --> 00:28:34,660 краще без вичерпно розглядає 530 00:28:34,660 --> 00:28:36,565 кожен крок, який може прийти після цього. 531 00:28:36,565 --> 00:28:39,740 532 00:28:39,740 --> 00:28:45,130 >> Тепер, щоб зробити цю роботу, одна з речей, що це 533 00:28:45,130 --> 00:28:48,680 стане дійсно важливо для нас не просто переміщення прямо 534 00:28:48,680 --> 00:28:53,720 до певній глибині межа, але, будучи в змозі говорити, 535 00:28:53,720 --> 00:28:59,380 один з цих ідей, які я є так погано, що це 536 00:28:59,380 --> 00:29:02,280 не варто розглядати всі з можливих шляхів 537 00:29:02,280 --> 00:29:06,680 щось може піти від поганого до гіршого. 538 00:29:06,680 --> 00:29:12,760 Щоб зробити це, ми додамо в минимакса принцип називається Альф-бета. 539 00:29:12,760 --> 00:29:16,340 І альфа-бета говорить, якщо у вас є погана ідея, 540 00:29:16,340 --> 00:29:22,840 не витрачайте свій час, намагаючись з'ясувати, як саме це погано. 541 00:29:22,840 --> 00:29:24,990 >> Отже, ось що ми збираємося зробити. 542 00:29:24,990 --> 00:29:28,620 Ми збираємося взяти те ж саме принципи, які ми раніше, 543 00:29:28,620 --> 00:29:32,200 те ж саме минимакса типу пошуку, тільки ми 544 00:29:32,200 --> 00:29:37,570 збирається відстежувати не тільки з фактичні значення, що у нас є, але ми 545 00:29:37,570 --> 00:29:41,440 відслідковувати найкращим Значення, яке я міг би отримати, 546 00:29:41,440 --> 00:29:45,700 і найгірший Результатом я міг би. 547 00:29:45,700 --> 00:29:50,470 І в будь-який час найгірший що шукає, швидше за все, 548 00:29:50,470 --> 00:29:52,694 Я відмовитися від цієї частини дерева. 549 00:29:52,694 --> 00:29:54,610 І я навіть не буду дивлячись на нього більше. 550 00:29:54,610 --> 00:29:57,680 551 00:29:57,680 --> 00:30:02,600 >> Гаразд, так що уявіть, що ми починаємо з цією ж точної гри дерева. 552 00:30:02,600 --> 00:30:05,200 І тепер ми збираємося піти знову, весь шлях вниз 553 00:30:05,200 --> 00:30:07,200 до того лівому нижньому кутку. 554 00:30:07,200 --> 00:30:11,180 І в цьому лівий нижній кут, ми дивитися і оцінювати цю дошку. 555 00:30:11,180 --> 00:30:15,700 Може бути, це чотири на чотири хрестики-нулики дошка, чи, може бути, це шахівниця. 556 00:30:15,700 --> 00:30:18,620 Але ми дивимося на нього, і ми оцінюємо це, і ми отримуємо значення з восьми. 557 00:30:18,620 --> 00:30:22,290 558 00:30:22,290 --> 00:30:28,030 >> У той момент, ми знаємо, що ми збираємося, щоб отримати принаймні, 559 00:30:28,030 --> 00:30:32,380 вісім очок від цієї нижньої рішення. 560 00:30:32,380 --> 00:30:36,620 Це не має значення, що інший два, що сім, і що два. 561 00:30:36,620 --> 00:30:38,580 Вони можуть бути будь-які значення вони хотіли б бути. 562 00:30:38,580 --> 00:30:41,279 Ми збираємося, щоб отримати на Менше вісім очок. 563 00:30:41,279 --> 00:30:43,070 Все правильно, але ми могли йти вперед і перевірити. 564 00:30:43,070 --> 00:30:45,080 Можливо, один з них краще, ніж восьмій. 565 00:30:45,080 --> 00:30:46,000 >> Ми дивимося на сім. 566 00:30:46,000 --> 00:30:46,910 Це краще, ніж восьмеро? 567 00:30:46,910 --> 00:30:48,680 Ні, це не змінює наша думка взагалі. 568 00:30:48,680 --> 00:30:49,460 Ми дивимося на два. 569 00:30:49,460 --> 00:30:50,543 Це краще, ніж восьмеро? 570 00:30:50,543 --> 00:30:52,580 Ні, це не змінює наша думка взагалі. 571 00:30:52,580 --> 00:30:55,480 Так що тепер ми знаємо, ми вичерпали всі можливості там. 572 00:30:55,480 --> 00:30:58,330 Ми не збираємося, щоб отримати що-небудь краще, ніж восьмій. 573 00:30:58,330 --> 00:31:01,310 Ми збираємося, щоб отримати саме восьмій. 574 00:31:01,310 --> 00:31:03,825 >> І так ми змінюємо вузол і скажемо, що в даний час є визначеність. 575 00:31:03,825 --> 00:31:07,010 576 00:31:07,010 --> 00:31:10,270 Ми піднімаємося на один рівень вище, що. 577 00:31:10,270 --> 00:31:13,820 І тепер ми знаємо, щось про те, що рівень мінімізації. 578 00:31:13,820 --> 00:31:18,560 Ми знаємо, що ми ніколи не збираємося, щоб отримати більш ніж у вісім очок, якщо ми йдемо вниз 579 00:31:18,560 --> 00:31:20,910 що напрямок. 580 00:31:20,910 --> 00:31:22,980 Бо навіть якщо ті два інших галузей виявляються 581 00:31:22,980 --> 00:31:26,170 бути фантастичним, і варто тисячі точок кожен, 582 00:31:26,170 --> 00:31:31,666 наш противник буде дати нам мінімум, а дати нам восьмій. 583 00:31:31,666 --> 00:31:32,790 Гаразд, добре, давайте подивимося. 584 00:31:32,790 --> 00:31:35,190 Ми будемо тримати спускаючись по цьому шляху. 585 00:31:35,190 --> 00:31:38,490 Ми спускаємося до цієї середині зліва. 586 00:31:38,490 --> 00:31:40,560 Ми дивляться, і ми бачимо, що є дев'ять. 587 00:31:40,560 --> 00:31:45,590 Ми знаємо, що ми збираємося, щоб отримати принаймні, дев'ять очок, спускаючись 588 00:31:45,590 --> 00:31:47,720 що середній шлях. 589 00:31:47,720 --> 00:31:52,110 І в цей момент, ми можемо просто призупинити. 590 00:31:52,110 --> 00:31:56,910 І ми можемо сказати, подивіться, я знати на рівні вище, 591 00:31:56,910 --> 00:32:01,160 Я збираюся отримати не більше восьми вказує, спускаючись цей напрямок. 592 00:32:01,160 --> 00:32:05,670 Але якби я пішов вниз середина Шлях замість лівого шляху, 593 00:32:05,670 --> 00:32:08,980 Я хотів би отримати, принаймні дев'ять очок. 594 00:32:08,980 --> 00:32:13,590 >> Мій опонент ніколи не буде дозвольте мені йти цим середній шлях. 595 00:32:13,590 --> 00:32:14,650 Вони отримують, щоб вибрати. 596 00:32:14,650 --> 00:32:18,140 І вони збираються вибрати Шлях до наліво до восьми, 597 00:32:18,140 --> 00:32:23,650 а не вниз до середини те, що, принаймні дев'ять очок. 598 00:32:23,650 --> 00:32:25,334 Таким чином, на той момент, я зупинюся. 599 00:32:25,334 --> 00:32:26,500 І я скажу, ви знаєте, що? 600 00:32:26,500 --> 00:32:29,990 Я не повинні дивитися більш вниз в цьому напрямку. 601 00:32:29,990 --> 00:32:32,270 Тому що я ніколи не буду туди потрапити. 602 00:32:32,270 --> 00:32:36,660 >> Я можу перестрибнути, що один, і я можу пропустити, що шість, 603 00:32:36,660 --> 00:32:39,720 тому що ніколи не трапиться. 604 00:32:39,720 --> 00:32:42,470 Так що я піду і я розглянути наступний можливість. 605 00:32:42,470 --> 00:32:44,830 Я йду туди, і я кажу, я бачу два. 606 00:32:44,830 --> 00:32:47,125 Я знаю, якщо я отримую тут, я збирається отримати принаймні два. 607 00:32:47,125 --> 00:32:49,810 608 00:32:49,810 --> 00:32:50,470 ДОБРЕ. 609 00:32:50,470 --> 00:32:51,520 Я продовжувати. 610 00:32:51,520 --> 00:32:52,440 Я бачу чотири. 611 00:32:52,440 --> 00:32:54,920 Я знаю, що я збираюся отримати принаймні чотири. 612 00:32:54,920 --> 00:32:57,200 Там ще багато між чотирьох і вісьмох, хоча. 613 00:32:57,200 --> 00:32:58,454 Так що я продовжувати. 614 00:32:58,454 --> 00:32:59,870 Я дивлюся вниз і бачу там один. 615 00:32:59,870 --> 00:33:01,614 Гаразд, я знаю, якщо Я йду цим шляхом, 616 00:33:01,614 --> 00:33:03,280 Я збираюся бути в змозі вибрати чотири. 617 00:33:03,280 --> 00:33:06,540 618 00:33:06,540 --> 00:33:08,980 Що мій опонент збирається зробити? 619 00:33:08,980 --> 00:33:12,310 Між чогось, що дає мені восьмій, те, що дає було мені чотири, 620 00:33:12,310 --> 00:33:14,730 і те, що дає мені принаймні, дев'ять, 621 00:33:14,730 --> 00:33:17,550 добре, що він збирається дати мені чотири. 622 00:33:17,550 --> 00:33:20,110 І тепер я знаю, на дуже зверху, я збираюся 623 00:33:20,110 --> 00:33:23,145 щоб бути в змозі отримати принаймні чотири бали з цієї гри. 624 00:33:23,145 --> 00:33:27,030 625 00:33:27,030 --> 00:33:30,900 >> Загалом ідея альфа-бета це відрізати частини з дерева, так 626 00:33:30,900 --> 00:33:32,530 що я не дивлюся на них більше. 627 00:33:32,530 --> 00:33:35,964 Але вона як і раніше виглядає як я був дивлячись на багато дерева. 628 00:33:35,964 --> 00:33:36,880 Давайте продовжувати йти вниз. 629 00:33:36,880 --> 00:33:38,305 Ми підемо вниз наступний підприємством. 630 00:33:38,305 --> 00:33:39,680 Вниз на дні, я вважаю, один. 631 00:33:39,680 --> 00:33:41,030 Я знаю, що я збираюся отримати принаймні один. 632 00:33:41,030 --> 00:33:41,690 Я продовжую дивитися. 633 00:33:41,690 --> 00:33:42,625 >> Я знаходжу зо три. 634 00:33:42,625 --> 00:33:44,250 Я знаю, що я збираюся отримати принаймні три. 635 00:33:44,250 --> 00:33:44,840 Я продовжувати. 636 00:33:44,840 --> 00:33:45,660 Я знаходжу п'ять. 637 00:33:45,660 --> 00:33:49,760 Я знаю, що я збираюся отримати п'ять якщо я спускаюся по цьому шляху. 638 00:33:49,760 --> 00:33:52,580 І я також знаю, то що мій опонент, якщо я 639 00:33:52,580 --> 00:33:55,510 вибрати середину втричі великі вибори, 640 00:33:55,510 --> 00:34:01,440 він збирається дати мені те, що це п'ять або менше. 641 00:34:01,440 --> 00:34:02,150 >> ДОБРЕ. 642 00:34:02,150 --> 00:34:03,400 Я можу продовжувати їсти. 643 00:34:03,400 --> 00:34:06,470 Я можу подивитися вниз, і я можу сказати, що я збираюся 644 00:34:06,470 --> 00:34:08,239 щоб отримати, якщо я йду вниз по середині шляху? 645 00:34:08,239 --> 00:34:09,909 Я йду, щоб отримати, ну, три там. 646 00:34:09,909 --> 00:34:12,080 Я збираюся отримати щось це принаймні три. 647 00:34:12,080 --> 00:34:16,030 Там як і раніше, що між три і п'ять, так що я продовжую дивитися. 648 00:34:16,030 --> 00:34:20,203 Про, дев'ять, я буду виразно вважати, що протягом трьох років. 649 00:34:20,203 --> 00:34:22,744 Я йду, щоб отримати принаймні дев`ять якщо я йду вниз, що середній шлях. 650 00:34:22,744 --> 00:34:25,530 651 00:34:25,530 --> 00:34:31,010 >> Тепер мій опонент зупиняється і каже, дивіться, немає ніякого сенсу більше. 652 00:34:31,010 --> 00:34:33,669 Я знаю, що мій мінімізація противник, він 653 00:34:33,669 --> 00:34:36,210 збираюся дати мені річ, яка менше або дорівнює п'яти, 654 00:34:36,210 --> 00:34:39,030 а не річ, яка більше або дорівнює дев'яти. 655 00:34:39,030 --> 00:34:39,530 Я зупиняюся. 656 00:34:39,530 --> 00:34:40,779 Я не дивлюся більше на це. 657 00:34:40,779 --> 00:34:43,280 Я продовжувати. 658 00:34:43,280 --> 00:34:44,850 >> Я дивлюся вниз на цьому. 659 00:34:44,850 --> 00:34:46,370 Аж до дна, я знаходжу шість. 660 00:34:46,370 --> 00:34:50,040 Я знаю, що я збираюся отримати принаймні шість. 661 00:34:50,040 --> 00:34:53,130 А що я можу зробити? 662 00:34:53,130 --> 00:34:54,877 Я можу зупинити. 663 00:34:54,877 --> 00:34:57,460 Тому що вибір між те, що, принаймні шість 664 00:34:57,460 --> 00:34:59,250 і те, що це менше, ніж п'ять, він 665 00:34:59,250 --> 00:35:02,570 збирається дати мені річ це менше, ніж п'ять. 666 00:35:02,570 --> 00:35:04,779 І тепер я знаю, що я збираюся щоб отримати саме такий вибір. 667 00:35:04,779 --> 00:35:06,195 Я йду, щоб отримати що п'ять вибір. 668 00:35:06,195 --> 00:35:08,980 669 00:35:08,980 --> 00:35:10,010 >> Я повертаюся на вершину. 670 00:35:10,010 --> 00:35:11,450 Який я буду вибрати між чимось 671 00:35:11,450 --> 00:35:14,449 це більше або дорівнює чотирьом, або щось, що це дорівнює п'яти? 672 00:35:14,449 --> 00:35:17,140 Я збираюся взяти щось це, щонайменше п'ять. 673 00:35:17,140 --> 00:35:20,490 Я спускаюся в останню путь, все аж до дна. 674 00:35:20,490 --> 00:35:21,260 Там це одне. 675 00:35:21,260 --> 00:35:23,410 ОК, принаймні, я йду, щоб отримати одне очко. 676 00:35:23,410 --> 00:35:24,427 Я продовжувати. 677 00:35:24,427 --> 00:35:25,760 По-друге, про, це краще, ніж один. 678 00:35:25,760 --> 00:35:27,100 Я йду, щоб отримати принаймні два. 679 00:35:27,100 --> 00:35:28,610 Я знаходжу зо три. 680 00:35:28,610 --> 00:35:31,450 Я знаю, що я збираюся одержати три. 681 00:35:31,450 --> 00:35:34,690 >> І вище, що точка, мій опонент збирається 682 00:35:34,690 --> 00:35:38,540 щоб дати мені що-небудь менше або дорівнює трьом. 683 00:35:38,540 --> 00:35:40,940 І тепер я можу зупинитися. 684 00:35:40,940 --> 00:35:46,290 Тому що у вибір між мною бути можливість отримати п'ять і мій опонент 685 00:35:46,290 --> 00:35:52,290 даючи мені щось менше, ніж три, Я завжди буду вважати, що п'ять. 686 00:35:52,290 --> 00:35:56,810 Так що я не оцінити, що Нижня частина дерева взагалі. 687 00:35:56,810 --> 00:35:59,470 >> Тепер, це може здатися незначним. 688 00:35:59,470 --> 00:36:03,630 Але, коли маленькі шматочки арифметики, більше, але менше, 689 00:36:03,630 --> 00:36:10,640 може відрізати цілі частини це зростає в геометричній прогресії дерево, 690 00:36:10,640 --> 00:36:14,280 що призводить до величезних кількість заощаджень, накопичень 691 00:36:14,280 --> 00:36:17,630 які є достатньо великими, що я можете почати грати на конкурсній основі 692 00:36:17,630 --> 00:36:21,330 в більш складних іграх. 693 00:36:21,330 --> 00:36:27,030 >> Гаразд, якщо ми подивимося на розмір і складність різних ігор, 694 00:36:27,030 --> 00:36:29,470 хрестики-нулики був наш простий приклад. 695 00:36:29,470 --> 00:36:32,150 У нас є невеликий рада, три на три. 696 00:36:32,150 --> 00:36:36,030 Ми отримуємо, в кращому випадку, в середньому близько чотирьох різних варіантів 697 00:36:36,030 --> 00:36:38,440 як ми йдемо через гру. 698 00:36:38,440 --> 00:36:42,720 У нас є десь близько 10 до п'ятий можливі різні листя. 699 00:36:42,720 --> 00:36:45,200 І будівництво в хрестики-нулики плеєр, добре, ми просто зробили це. 700 00:36:45,200 --> 00:36:47,460 Це легко. 701 00:36:47,460 --> 00:36:49,890 >> Якщо ми йдемо до чогось більш Комплекс, як Connect Four. 702 00:36:49,890 --> 00:36:53,170 Ви пам'ятаєте цю гру де упаду маленькі жетони в? 703 00:36:53,170 --> 00:36:58,490 Це шість сьомій дошка, не те, що набагато більше, як і раніше 704 00:36:58,490 --> 00:37:00,770 має приблизно такий же розгалуження фактор, як хрестики-нулики. 705 00:37:00,770 --> 00:37:05,410 У мене є близько чотирьох вибір де я можу покласти речі в. 706 00:37:05,410 --> 00:37:10,760 Але тепер, я отримав набагато більше, призводить, з 10 по 21 сили. 707 00:37:10,760 --> 00:37:14,440 Це те, що легко Досить того, що ми вирішити відразу. 708 00:37:14,440 --> 00:37:17,560 >> Шашки, більш complex-- вас дістав вісім на вісім борту. 709 00:37:17,560 --> 00:37:20,570 Ти тільки на половину їх у будь-який час, хоча. 710 00:37:20,570 --> 00:37:24,930 У вас є розгалуження Коефіцієнт це близько 2,8. 711 00:37:24,930 --> 00:37:28,160 Ну, у нас є кілька рухається ви можете взяти. 712 00:37:28,160 --> 00:37:33,870 Ви отримали від 10 до 31-листя, великі і більш великі, і більші простору. 713 00:37:33,870 --> 00:37:37,340 Як я повинен шукати через ці все більше і більше простору, 714 00:37:37,340 --> 00:37:42,220 що, коли речі, як альфа-бета і можливість відрізати всі гілки 715 00:37:42,220 --> 00:37:44,420 стає необхідним. 716 00:37:44,420 --> 00:37:47,440 >> Тепер, шашки було досить легко в 1992 році. 717 00:37:47,440 --> 00:37:51,400 Комп'ютерна програма називається Чинук побити світовий шашки 718 00:37:51,400 --> 00:37:53,590 Чемпіон, Маріон Тінслі. 719 00:37:53,590 --> 00:37:57,260 І з тих пір, немає людина майстер гравець 720 00:37:57,260 --> 00:38:02,290 вдалося побити кращий обчислювальні системи. 721 00:38:02,290 --> 00:38:06,570 Якщо ми подивимося на те, як шахи, тепер знову, у нас є вісім на вісім борту. 722 00:38:06,570 --> 00:38:09,870 Але у нас є набагато більш складним, штук, набагато більш складні рухи. 723 00:38:09,870 --> 00:38:14,610 У нас є коефіцієнта розгалуження близько 35, 35 можливих ходів в середньому 724 00:38:14,610 --> 00:38:20,030 що я можу взяти, і стан простір, кількість листя 725 00:38:20,030 --> 00:38:28,950 який виріс до 10 в сто двадцять третій влади, Величезні номери можливостей. 726 00:38:28,950 --> 00:38:35,570 >> Навіть досі, сучасні процесори в змозі зробити це успішно. 727 00:38:35,570 --> 00:38:43,900 У 1995 році, а потім в 1997 році, комп'ютер Програма називається Deep Blue від IBM побудована 728 00:38:43,900 --> 00:38:49,601 який біг на гігантському суперкомп'ютері бити поточний чемпіон світу, 729 00:38:49,601 --> 00:38:50,225 Гаррі Каспаров. 730 00:38:50,225 --> 00:38:54,000 731 00:38:54,000 --> 00:38:56,650 Це був переломний момент. 732 00:38:56,650 --> 00:39:00,620 Сьогодні, однак, що ж обробка Потужність сидить на моїй MacBook. 733 00:39:00,620 --> 00:39:04,180 734 00:39:04,180 --> 00:39:06,440 >> Швидкість обробки зберігає отримувати швидше і швидше. 735 00:39:06,440 --> 00:39:09,500 Ми можемо оцінити все більш і більш Дошки швидше і швидше. 736 00:39:09,500 --> 00:39:14,550 Але що ще більш важливо, ми повинні краще Функції оцінки і краще обрізка 737 00:39:14,550 --> 00:39:15,460 методи. 738 00:39:15,460 --> 00:39:19,560 Таким чином, ми можемо шукати простір складніше. 739 00:39:19,560 --> 00:39:22,350 Найбільша ради ігри, які ми можемо думати про, 740 00:39:22,350 --> 00:39:26,310 щось на зразок Go це отримав 19 по 19 дошка, 741 00:39:26,310 --> 00:39:32,490 раптом, ми пройшли точку де обчислювальні системи можуть виграти. 742 00:39:32,490 --> 00:39:34,530 Там немає обчислювальна Система там 743 00:39:34,530 --> 00:39:38,880 що може побити професійний гравець Перейти. 744 00:39:38,880 --> 00:39:45,000 Кращий систем сьогодні Оцінка його про свого роду хорошим любительському рівні. 745 00:39:45,000 --> 00:39:49,285 Так що все ще трохи з там, що ви не можете дістатися до ще. 746 00:39:49,285 --> 00:39:51,840 747 00:39:51,840 --> 00:39:55,360 >> Гаразд, це традиційні настільні ігри, 748 00:39:55,360 --> 00:39:58,560 Ці види систем, де ми побудувати цю минимакса, будь він отримав 749 00:39:58,560 --> 00:40:06,300 альфа-бета чи ні, ці алгоритми працюють тому що є певні обмеження. 750 00:40:06,300 --> 00:40:08,520 Ми маємо досконалу інформацію про навколишній світ. 751 00:40:08,520 --> 00:40:11,690 Ми знаємо, де всі частини. 752 00:40:11,690 --> 00:40:13,570 Світ є статичним. 753 00:40:13,570 --> 00:40:16,220 Ніхто не отримує, щоб перемістити штук навколо, поки я 754 00:40:16,220 --> 00:40:20,640 сидячи там, думаючи, приймаючи моя черга. 755 00:40:20,640 --> 00:40:23,140 Там в простір дія, яка дискретно. 756 00:40:23,140 --> 00:40:26,900 Я можу поставити свою пішака тут, або я можу поставити свою пішака тут. 757 00:40:26,900 --> 00:40:30,520 Я не дозволив поставити свою пішака на лінія між двома квадратами. 758 00:40:30,520 --> 00:40:34,430 759 00:40:34,430 --> 00:40:36,520 >> І, нарешті, дії детерміновані. 760 00:40:36,520 --> 00:40:39,790 Я знаю, що якщо я кажу, Човен із конем зо три, 761 00:40:39,790 --> 00:40:44,660 моя тура буде в кінцевому підсумку на лицаря зо три, поки це діє хід. 762 00:40:44,660 --> 00:40:47,830 Там немає невизначеності про це. 763 00:40:47,830 --> 00:40:52,490 Тепер, як я йду до більш різні види ігор, 764 00:40:52,490 --> 00:40:55,960 ми повинні розірвати ці припущення. 765 00:40:55,960 --> 00:41:00,020 >> Що робити, якщо я йду в той як класичних відеоігор? 766 00:41:00,020 --> 00:41:04,180 Ось вибір відео ігри від Atari 2600. 767 00:41:04,180 --> 00:41:05,180 Що я маю там? 768 00:41:05,180 --> 00:41:08,440 Я отримав Frogger, простір Загарбників, Пастка, і Pac-Man. 769 00:41:08,440 --> 00:41:11,290 770 00:41:11,290 --> 00:41:14,840 Які середовищ у мене тут зараз? 771 00:41:14,840 --> 00:41:16,900 Який з цих припущень я повинен зламати? 772 00:41:16,900 --> 00:41:19,410 773 00:41:19,410 --> 00:41:21,570 >> Ну, це залежить від гри. 774 00:41:21,570 --> 00:41:28,170 Я міг би грати в шахи на 2600, і це було б так само, як це було раніше. 775 00:41:28,170 --> 00:41:33,020 Для більшості з цих систем, є повне знання про світ. 776 00:41:33,020 --> 00:41:36,300 Там абсолютно детерміновані дії. 777 00:41:36,300 --> 00:41:38,330 Але, як правило, у світі більше не статичні. 778 00:41:38,330 --> 00:41:41,970 Тобто, в той час як я сидів там очікування, щось рухається. 779 00:41:41,970 --> 00:41:44,320 Привиди приходять, щоб отримати мене. 780 00:41:44,320 --> 00:41:46,570 Скорпіон буде після мене внизу. 781 00:41:46,570 --> 00:41:48,880 Космічні загарбники ближче і ближче. 782 00:41:48,880 --> 00:41:54,020 783 00:41:54,020 --> 00:41:55,510 Наскільки добре ми можемо зробити проти них? 784 00:41:55,510 --> 00:41:58,640 785 00:41:58,640 --> 00:42:02,790 >> Кілька років тому, Google що проект під назвою 786 00:42:02,790 --> 00:42:12,030 DeepMind, де вони тренувалися комп'ютер програма, грати в Atari 2600 ігор. 787 00:42:12,030 --> 00:42:16,120 І якщо ви думаєте, що це не серйозно бізнес, результати їх дослідження 788 00:42:16,120 --> 00:42:19,920 були опубліковані в Nature, так майже так само добре, публікація 789 00:42:19,920 --> 00:42:22,500 як ви можете, можливо, отримати. 790 00:42:22,500 --> 00:42:24,340 А ось наскільки добре вони виконуються. 791 00:42:24,340 --> 00:42:29,220 >> Вони є алгоритм, який сидів і дивився тільки входи екрана. 792 00:42:29,220 --> 00:42:34,080 Це не отримав ніяких інструкцій взагалі про правила гри. 793 00:42:34,080 --> 00:42:42,610 І він повинен був з'ясувати, на основі його оцінки, наскільки добре вона робить. 794 00:42:42,610 --> 00:42:46,560 Це була система, яка використовується щось називається навчання з підкріпленням. 795 00:42:46,560 --> 00:42:48,380 Тобто, це дивилося на його рахунок. 796 00:42:48,380 --> 00:42:51,620 А якщо він отримав гарні оцінки, сказав він, Я повинен пам'ятати ці речі. 797 00:42:51,620 --> 00:42:53,310 І я повинен робити тим знову. 798 00:42:53,310 --> 00:42:56,450 А якщо він отримав погану оцінку, він сказав, Я не повинен робити ці речі знову. 799 00:42:56,450 --> 00:42:59,750 800 00:42:59,750 --> 00:43:03,430 >> Це виконання з тих підготовлених систем 801 00:43:03,430 --> 00:43:07,490 дозволено грати для Кілька годин на кожній грі, 802 00:43:07,490 --> 00:43:12,490 в порівнянні з професійними геймерами. 803 00:43:12,490 --> 00:43:19,670 Таким чином, для всіх ігор, які з лівого боку від цієї лінії, 804 00:43:19,670 --> 00:43:25,920 це само-навчання комп'ютерної програми перевершили професійних геймерів. 805 00:43:25,920 --> 00:43:29,690 І все до Правильно, професійні геймери 806 00:43:29,690 --> 00:43:30,920 ще краще. 807 00:43:30,920 --> 00:43:34,040 808 00:43:34,040 --> 00:43:36,850 Для чогось, що знав нічого про правила, які 809 00:43:36,850 --> 00:43:43,020 нічого не знав про структуру гри, це вражаючі результати. 810 00:43:43,020 --> 00:43:45,660 І це те, що ми можемо зробити сьогодні. 811 00:43:45,660 --> 00:43:50,239 >> ОК, ви говорите, але якщо ми думати про AI в іграх, 812 00:43:50,239 --> 00:43:52,530 Зазвичай ми думаємо про Те, що ми дійсно можемо 813 00:43:52,530 --> 00:43:54,180 сісти і грати проти нього. 814 00:43:54,180 --> 00:43:58,760 Якщо я сідаю і граю StarCraft, або я грати безкоштовно сито, 815 00:43:58,760 --> 00:44:01,870 комп'ютер опонент людина, керуючий зергов, 816 00:44:01,870 --> 00:44:06,770 або управління іншим цивілізації. 817 00:44:06,770 --> 00:44:11,920 Як ті гравці насправді знайти свої ходи? 818 00:44:11,920 --> 00:44:18,810 >> Ну, ці ігри структуровані майже таким же способом, як наші настільні ігри, 819 00:44:18,810 --> 00:44:22,250 ці ігри, які ми разом називають чотири X ігри, 820 00:44:22,250 --> 00:44:26,040 дослідити, expand-- забути ті. 821 00:44:26,040 --> 00:44:26,980 Хто вони? 822 00:44:26,980 --> 00:44:32,150 Дослідіть, розширювати і згасити, Я думаю, що це останній. 823 00:44:32,150 --> 00:44:36,060 Але вони в основному з розвідки і володарюй гри. 824 00:44:36,060 --> 00:44:41,020 Як правило, комп'ютерний противник тобто має обмежену інформацію. 825 00:44:41,020 --> 00:44:45,486 Вони не знають, саме те, що відбувається за цього туману війни. 826 00:44:45,486 --> 00:44:47,735 Вони не отримують, щоб побачити, що у вас є у вашому інвентарі. 827 00:44:47,735 --> 00:44:50,240 828 00:44:50,240 --> 00:44:52,800 >> Там у середу, що є динамічним. 829 00:44:52,800 --> 00:44:56,180 Все змінюється весь час. 830 00:44:56,180 --> 00:45:00,290 Ви не можете сидіти і чекати, щоб взяти ваш хід. 831 00:45:00,290 --> 00:45:02,810 Але більшість речей все ще дискретним. 832 00:45:02,810 --> 00:45:04,200 Я повинен покласти моє місто тут. 833 00:45:04,200 --> 00:45:06,750 Або я повинен поставити своє місто тут. 834 00:45:06,750 --> 00:45:08,950 І все детерміновано. 835 00:45:08,950 --> 00:45:14,660 Коли я кажу, поворушити блок тут, мій блок НЕ рухається тут, якщо перешкода раптом 836 00:45:14,660 --> 00:45:17,700 вступає в гру. 837 00:45:17,700 --> 00:45:21,610 Тепер, це ще не всі комп'ютерні ігри, які там сьогодні. 838 00:45:21,610 --> 00:45:27,320 >> Якщо я йду, і я граю перший тип особи гра, щось на зразок Thief або Fallout 839 00:45:27,320 --> 00:45:33,350 або Скайрім, або гало, в даний час У мене є комп'ютерних супротивників 840 00:45:33,350 --> 00:45:37,860 які там є, що дуже різні ситуації. 841 00:45:37,860 --> 00:45:40,020 Вони мають, знову ж, обмежену інформацію. 842 00:45:40,020 --> 00:45:43,420 Вони тільки можуть побачити якесь поле зору. 843 00:45:43,420 --> 00:45:45,180 Захист навколишнього середовища є ще динамічним. 844 00:45:45,180 --> 00:45:48,280 Речі весь час змінюються. 845 00:45:48,280 --> 00:45:52,300 >> Але тепер у мене є набагато більш безперервне простір дії. 846 00:45:52,300 --> 00:45:57,170 Я можу бути тільки визирав трохи з дверного отвору. 847 00:45:57,170 --> 00:46:00,650 А деякі ігри, мій дії стохастичною. 848 00:46:00,650 --> 00:46:04,590 Я отримую, щоб спробувати перестрибнути через цю стіну, але я отримав шанс поломки. 849 00:46:04,590 --> 00:46:08,280 850 00:46:08,280 --> 00:46:14,550 Ці типи ігор стають ближчими і ближче до видів контролерів 851 00:46:14,550 --> 00:46:17,330 що ми будуємо у робототехніці. 852 00:46:17,330 --> 00:46:21,050 >> У робототехніці, ми повинні припустити, що у нас є обмежена інформація. 853 00:46:21,050 --> 00:46:23,070 У нас є датчики, які розповісти про світ. 854 00:46:23,070 --> 00:46:25,860 У нас є завжди змінюється, динамічна середу. 855 00:46:25,860 --> 00:46:30,440 У нас є світ, в якому є місце безперервною, а не дискретною. 856 00:46:30,440 --> 00:46:36,260 І наші дії, коли ми намагаємося їм, є шанс поломки. 857 00:46:36,260 --> 00:46:40,960 І справді, сучасна гра Контролери для вашого Halo противника, 858 00:46:40,960 --> 00:46:48,690 або для тих НПС в Skyrim, в основному запустити невеликі архітектур робототехніки. 859 00:46:48,690 --> 00:46:50,380 >> Вони відчувають світ. 860 00:46:50,380 --> 00:46:52,910 Вони будують модель світу. 861 00:46:52,910 --> 00:46:57,950 Вони обчислити на основі набору цілі, які вони хотіли б досягти. 862 00:46:57,950 --> 00:47:03,110 Вони планують дії, засновані на те, що вони знають. 863 00:47:03,110 --> 00:47:07,940 А ті, рівно ті ж самі види систем, які ми будуємо у робототехніці. 864 00:47:07,940 --> 00:47:11,420 Таким чином, ці архітектури, щоб довести цю назад разом, 865 00:47:11,420 --> 00:47:14,500 часто вельми те ж саме. 866 00:47:14,500 --> 00:47:16,340 >> Отже, давайте подивимося, якщо ми можемо бачити, що. 867 00:47:16,340 --> 00:47:19,210 Давайте повернемося до нашого хрестики-нулики приклад. 868 00:47:19,210 --> 00:47:22,690 І я збираюся поставити кілька моїх пост-документи, щоб прийти і допомогти мені. 869 00:47:22,690 --> 00:47:26,970 Так Чень Мін, і Алессандро, і Олів'є, якщо ви, хлопці б придумати. 870 00:47:26,970 --> 00:47:32,080 871 00:47:32,080 --> 00:47:35,440 І я буду потребувати пара добровольців 872 00:47:35,440 --> 00:47:37,590 >> ОК, я побачив руку право там в середині. 873 00:47:37,590 --> 00:47:39,965 Дозвольте мені взяти ще один, хтось далі в спині може бути. 874 00:47:39,965 --> 00:47:40,881 Гаразд, там. 875 00:47:40,881 --> 00:47:41,490 Давай до. 876 00:47:41,490 --> 00:47:44,190 877 00:47:44,190 --> 00:47:45,335 Добре. 878 00:47:45,335 --> 00:47:49,490 Так що давайте вважати, що кришку вниз. 879 00:47:49,490 --> 00:48:03,700 І якщо ви, хлопці, прийде прямо тому тут для мене, фантастика. 880 00:48:03,700 --> 00:48:06,580 >> Так що це робот називається Бакстер. 881 00:48:06,580 --> 00:48:10,880 І Бакстер це робот, який це комерційна платформа, призначена 882 00:48:10,880 --> 00:48:13,030 компанією під назвою Переосмислення. 883 00:48:13,030 --> 00:48:16,580 І цей робот призначений для малого виробництва. 884 00:48:16,580 --> 00:48:19,265 Але сьогодні ми збираємося використовувати його, щоб грати в хрестики-нулики. 885 00:48:19,265 --> 00:48:21,930 886 00:48:21,930 --> 00:48:27,150 Тепер, цей робот є також те, це відносно унікальним. 887 00:48:27,150 --> 00:48:32,950 Тому що, якщо я де-небудь стояли близько до стандартної заводської автоматизації 888 00:48:32,950 --> 00:48:39,580 Система, я б у дуже важкому Небезпека поранення. 889 00:48:39,580 --> 00:48:45,600 >> Бакстер, однак, призначений для відносно безпечно взаємодіяти. 890 00:48:45,600 --> 00:48:48,680 І тому я можу натиснути на цього робота. 891 00:48:48,680 --> 00:48:52,350 І ви можете бачити, що це трохи трохи гнучкими, як вона рухається навколо. 892 00:48:52,350 --> 00:48:57,250 І я можу змінити його де я хотів би, щоб це пішло. 893 00:48:57,250 --> 00:49:03,410 В даний час в нормальному роботизованої системи, ми б мати набір суглобів тут 894 00:49:03,410 --> 00:49:07,970 який був би безпосередньо відповідає на команди позиції. 895 00:49:07,970 --> 00:49:13,180 І вони не піклуються обов'язково якщо вони рухалися через відкритому повітрі, 896 00:49:13,180 --> 00:49:15,555 або якщо вони рухалися через мій грудної клітки. 897 00:49:15,555 --> 00:49:18,410 898 00:49:18,410 --> 00:49:19,120 >> ДОБРЕ. 899 00:49:19,120 --> 00:49:22,090 І, як правило, якщо ви були тут з виробничої системи, 900 00:49:22,090 --> 00:49:23,400 ви ніколи нікуди поруч з ним. 901 00:49:23,400 --> 00:49:26,280 Там буде жовтий Безпека стрічка навколо нього. 902 00:49:26,280 --> 00:49:28,310 Ця система має трохи інший дизайн 903 00:49:28,310 --> 00:49:32,130 бути дружелюбніше і простіше для людей, щоб взаємодіяти, 904 00:49:32,130 --> 00:49:36,380 в тому, що в кожному суглобі, є джерело. 905 00:49:36,380 --> 00:49:39,110 І замість того, контроль точна позиція, 906 00:49:39,110 --> 00:49:43,110 ми контролюємо певну кількість крутний момент, певну кількість сили, 907 00:49:43,110 --> 00:49:45,874 що ми хотіли б бути на цій навесні. 908 00:49:45,874 --> 00:49:47,790 Гаразд, так що давайте мені прийняти наші волонтери тут. 909 00:49:47,790 --> 00:49:48,540 Привіт, як тебе звати? 910 00:49:48,540 --> 00:49:49,010 >> АУДИТОРІЯ: Луї. 911 00:49:49,010 --> 00:49:49,635 >> СЛУХАЛИ: Луї. 912 00:49:49,635 --> 00:49:50,490 Приємно бачити вас. 913 00:49:50,490 --> 00:49:50,990 І що ж? 914 00:49:50,990 --> 00:49:51,610 >> АУДИТОРІЯ: Девід. 915 00:49:51,610 --> 00:49:51,960 >> СПІКЕР: Девід. 916 00:49:51,960 --> 00:49:52,550 Приємно познайомитись. 917 00:49:52,550 --> 00:49:54,508 Якщо ви, хлопці, буде чекати тут на секунду, 918 00:49:54,508 --> 00:49:56,420 Я збираюся дати вам шанс зробити це. 919 00:49:56,420 --> 00:50:00,610 Так що це робот, якщо ви придумали і якщо ви злегка натисніть на нього, 920 00:50:00,610 --> 00:50:03,780 Ви побачите, що вона рухається небагато. 921 00:50:03,780 --> 00:50:06,349 І якщо ви берете його прямо тут, на зап'ясті просто 922 00:50:06,349 --> 00:50:09,390 вище, де ці кнопки, це Схоже, що ви повинні захопити кнопки, 923 00:50:09,390 --> 00:50:13,100 але захопити прямо над ним, а не, ви зможе дуже м'яко маніпулювати 924 00:50:13,100 --> 00:50:14,545 в просторі. 925 00:50:14,545 --> 00:50:15,920 Луїс, ви хочете, щоб дати йому спробувати? 926 00:50:15,920 --> 00:50:19,465 Так дайте його трохи натиснути, щоб почати с. 927 00:50:19,465 --> 00:50:23,190 І потім, якщо ви поклали пальці тут і утримати його, 928 00:50:23,190 --> 00:50:24,807 тому що він буде рухатися для Вас тоді. 929 00:50:24,807 --> 00:50:27,824 930 00:50:27,824 --> 00:50:29,365 Гаразд, ви хочете, щоб дати йому спробувати? 931 00:50:29,365 --> 00:50:29,980 Давай до. 932 00:50:29,980 --> 00:50:32,300 Так дайте його просто ніжний натисніть там, щоб почати. 933 00:50:32,300 --> 00:50:33,820 Ви можете відчути, що це таке. 934 00:50:33,820 --> 00:50:40,060 І потім, якщо ви берете його прямо там, Ви зможете маневрувати в межах. 935 00:50:40,060 --> 00:50:41,280 >> ДОБРЕ. 936 00:50:41,280 --> 00:50:47,360 Так, як правило, цей вид робота буде використовувати при малих виробничих масштабах. 937 00:50:47,360 --> 00:50:50,980 І я збираюся перемістити цю руку тільки вниз у бік трохи тут. 938 00:50:50,980 --> 00:50:55,750 Але сьогодні, ми збираємося використовувати ж хрестики-нулики грати система 939 00:50:55,750 --> 00:50:59,520 на основі минимакса, що ми раніше побудованих. 940 00:50:59,520 --> 00:51:00,549 ДОБРЕ? 941 00:51:00,549 --> 00:51:02,340 Так, ви, хлопці, кожен збирається грати в гру. 942 00:51:02,340 --> 00:51:04,210 Луїс, ви збираєтеся бути першим. 943 00:51:04,210 --> 00:51:05,920 Дозвольте мені провести тут на секунду. 944 00:51:05,920 --> 00:51:10,949 Я збираюся, щоб ви стояти прямо тут, просто так що кожен може бачити Вас. 945 00:51:10,949 --> 00:51:11,990 Ви, хлопці створили тут? 946 00:51:11,990 --> 00:51:13,120 >> РОБОТ: Прошу. 947 00:51:13,120 --> 00:51:15,910 Давайте грати в хрестики-нулики. 948 00:51:15,910 --> 00:51:20,860 Не збагнути ваш маркер, перш ніж Я кажу, що це ваша черга. 949 00:51:20,860 --> 00:51:22,050 Я почати гру. 950 00:51:22,050 --> 00:51:27,900 951 00:51:27,900 --> 00:51:28,750 Це моя черга. 952 00:51:28,750 --> 00:51:47,002 953 00:51:47,002 --> 00:51:50,210 СЛУХАЛИ: Тепер, якщо ви могли б взяти один з Ваші частин і йти вперед і помістити його. 954 00:51:50,210 --> 00:51:51,446 РОБОТ: Це ваша черга. 955 00:51:51,446 --> 00:51:53,430 [Сміх] 956 00:51:53,430 --> 00:51:54,836 Це моя черга. 957 00:51:54,836 --> 00:51:56,820 [Сміх] 958 00:51:56,820 --> 00:52:12,196 959 00:52:12,196 --> 00:52:15,680 [Сміх] 960 00:52:15,680 --> 00:52:16,570 Це ваша черга. 961 00:52:16,570 --> 00:52:21,397 962 00:52:21,397 --> 00:52:23,688 СПІКЕР: людський гонка розраховує на вас тут, Луї. 963 00:52:23,688 --> 00:52:27,440 964 00:52:27,440 --> 00:52:28,350 >> РОБОТ: Це моя черга. 965 00:52:28,350 --> 00:52:44,810 966 00:52:44,810 --> 00:52:47,015 >> СЛУХАЛИ: Так Бакстер успішно блокована тут. 967 00:52:47,015 --> 00:52:49,670 968 00:52:49,670 --> 00:52:52,480 >> РОБОТ: Це ваша черга. 969 00:52:52,480 --> 00:52:53,360 Це моя черга. 970 00:52:53,360 --> 00:53:14,730 971 00:53:14,730 --> 00:53:16,810 Це ваша черга. 972 00:53:16,810 --> 00:53:17,760 Це моя черга. 973 00:53:17,760 --> 00:53:21,330 974 00:53:21,330 --> 00:53:23,830 СЛУХАЛИ: І ми дамо Бакстер закінчити свій останній крок тут. 975 00:53:23,830 --> 00:53:36,622 976 00:53:36,622 --> 00:53:39,090 >> [Сміх] 977 00:53:39,090 --> 00:53:40,480 >> РОБОТ: Це краватку. 978 00:53:40,480 --> 00:53:42,030 Я виграю в наступний раз. 979 00:53:42,030 --> 00:53:43,365 >> [Сміх] 980 00:53:43,365 --> 00:53:45,210 >> СЛУХАЛИ: Гаразд, спасибі дуже багато, Луї. 981 00:53:45,210 --> 00:53:46,094 Дякую. 982 00:53:46,094 --> 00:53:46,980 Ви можете йти по цьому шляху. 983 00:53:46,980 --> 00:53:49,759 >> РОБОТ: я починаю гру. 984 00:53:49,759 --> 00:53:51,800 СЛУХАЛИ: Отже, дозвольте мені пояснити, Вам ще один маленький 985 00:53:51,800 --> 00:53:55,410 трохи, перш ніж ми отримаємо нашу реванш тут. 986 00:53:55,410 --> 00:53:57,200 Що саме відбувається? 987 00:53:57,200 --> 00:53:59,430 Таким чином, робот має камери нагорі тут. 988 00:53:59,430 --> 00:54:01,330 І це, дивлячись на дошку. 989 00:54:01,330 --> 00:54:04,470 І це чи бачить він отримав червону O або синій 990 00:54:04,470 --> 00:54:10,450 і білий X. Як ті об'єкти поміщаються на дошка, це в основному те ж саме вхід 991 00:54:10,450 --> 00:54:13,890 що ми прочитали б у від наша структура даних з нашого екрану. 992 00:54:13,890 --> 00:54:17,290 Це працює той же Алгоритм минимакса бути 993 00:54:17,290 --> 00:54:21,010 змозі знайти, де розмістити хорошу фішку. 994 00:54:21,010 --> 00:54:24,820 >> І тоді ми даємо команду про де ми хотіли б маркер повинен бути поміщений. 995 00:54:24,820 --> 00:54:26,120 Рука рухається з. 996 00:54:26,120 --> 00:54:31,750 Це за допомогою вакуумного захвату, щоб застосувати деякі всмоктування в цій шматка дерева, 997 00:54:31,750 --> 00:54:35,240 забрати його, перемістіть його вправо пляма, а потім відпустіть всмоктування 998 00:54:35,240 --> 00:54:36,950 і помістіть його. 999 00:54:36,950 --> 00:54:38,990 Гаразд, ми збираємося щоб дати йому ще один постріл 1000 00:54:38,990 --> 00:54:40,930 з трохи розумніші гравця тут. 1001 00:54:40,930 --> 00:54:42,290 Ви готові? 1002 00:54:42,290 --> 00:54:46,150 Гаразд, якби ви стояти прямо тут і дати a-- перетворити цей шлях 1003 00:54:46,150 --> 00:54:47,955 так що ви можете бачити всіх. 1004 00:54:47,955 --> 00:54:48,830 І тоді [нерозбірливо]. 1005 00:54:48,830 --> 00:54:49,330 >> РОБОТ: Це моя черга. 1006 00:54:49,330 --> 00:54:50,455 >> СЛУХАЛИ: Бакстер почне. 1007 00:54:50,455 --> 00:55:10,750 1008 00:55:10,750 --> 00:55:11,730 Це ваша черга. 1009 00:55:11,730 --> 00:55:16,490 1010 00:55:16,490 --> 00:55:17,520 Це моя черга. 1011 00:55:17,520 --> 00:55:38,740 1012 00:55:38,740 --> 00:55:39,690 Це ваша черга. 1013 00:55:39,690 --> 00:55:46,330 1014 00:55:46,330 --> 00:55:47,165 Це моя черга. 1015 00:55:47,165 --> 00:56:01,252 1016 00:56:01,252 --> 00:56:06,192 >> [Сміх] 1017 00:56:06,192 --> 00:56:08,542 >> СЛУХАЛИ: [шепітних] Просто нехай йти вперед і перемагати. 1018 00:56:08,542 --> 00:56:09,500 РОБОТ: Це ваша черга. 1019 00:56:09,500 --> 00:56:15,099 1020 00:56:15,099 --> 00:56:15,890 СЛУХАЛИ: Це нормально. 1021 00:56:15,890 --> 00:56:20,390 1022 00:56:20,390 --> 00:56:21,360 >> РОБОТ: Це моя черга. 1023 00:56:21,360 --> 00:56:24,825 1024 00:56:24,825 --> 00:56:26,805 >> [Сміх] 1025 00:56:26,805 --> 00:56:42,650 1026 00:56:42,650 --> 00:56:43,510 >> Я виграв. 1027 00:56:43,510 --> 00:56:45,620 >> [Сміх] 1028 00:56:45,620 --> 00:56:46,595 >> Я почати гру. 1029 00:56:46,595 --> 00:56:48,261 >> СЛУХАЛИ: Гаразд, спасибі дуже багато. 1030 00:56:48,261 --> 00:56:50,180 1031 00:56:50,180 --> 00:56:55,590 Гаразд, я думаю, що ми отримали час для ще один відмінний хрестики-нулики плеєр, 1032 00:56:55,590 --> 00:57:00,490 хто може покласти цю річ збігаються, хто знає, що вони роблять. 1033 00:57:00,490 --> 00:57:03,010 >> [Сміх] 1034 00:57:03,010 --> 00:57:05,560 >> Хто буде наш чемпіон тут? 1035 00:57:05,560 --> 00:57:08,110 Гаразд, ваші друзі добровільно вас. 1036 00:57:08,110 --> 00:57:11,190 Це досить добре для мене. 1037 00:57:11,190 --> 00:57:12,194 Скажи мені своє ім'я, знов. 1038 00:57:12,194 --> 00:57:12,860 АУДИТОРІЯ: Тамір. 1039 00:57:12,860 --> 00:57:14,193 СЛУХАЛИ: Тамір, приємно тебе бачити. 1040 00:57:14,193 --> 00:57:19,270 Гаразд, раз ми збираємося поставити вас прямо тут, так що кожен може бачити Вас. 1041 00:57:19,270 --> 00:57:22,070 Ви наш представник в цьому матчі зараз. 1042 00:57:22,070 --> 00:57:24,540 Бакстер є одним і про і о. 1043 00:57:24,540 --> 00:57:26,300 Або вибачте, один і один, о. 1044 00:57:26,300 --> 00:57:27,490 І це до вас тут. 1045 00:57:27,490 --> 00:57:29,340 Бакстер отримаєте для переміщення по-перше, хоча. 1046 00:57:29,340 --> 00:57:30,435 Так. 1047 00:57:30,435 --> 00:57:31,310 РОБОТ: Це моя черга. 1048 00:57:31,310 --> 00:57:45,226 1049 00:57:45,226 --> 00:57:48,208 >> [Сміх] 1050 00:57:48,208 --> 00:57:52,720 1051 00:57:52,720 --> 00:57:55,780 >> Це ваша черга. 1052 00:57:55,780 --> 00:57:56,845 Це моя черга. 1053 00:57:56,845 --> 00:58:18,130 1054 00:58:18,130 --> 00:58:18,965 Це ваша черга. 1055 00:58:18,965 --> 00:58:28,751 1056 00:58:28,751 --> 00:58:30,248 Це моя черга. 1057 00:58:30,248 --> 00:58:51,210 1058 00:58:51,210 --> 00:58:52,160 Це ваша черга. 1059 00:58:52,160 --> 00:59:00,854 1060 00:59:00,854 --> 00:59:03,365 >> [Сміх] 1061 00:59:03,365 --> 00:59:04,240 РОБОТ: Це моя черга. 1062 00:59:04,240 --> 00:59:06,930 СПІКЕР: Це набагато складніше, коли Ви стоїте тут, хлопці. 1063 00:59:06,930 --> 00:59:19,400 1064 00:59:19,400 --> 00:59:21,840 [Сміх] 1065 00:59:21,840 --> 00:59:26,730 1066 00:59:26,730 --> 00:59:29,054 РОБОТ: Ви люди так легко перемогти. 1067 00:59:29,054 --> 00:59:30,803 [Сміх і оплески] 1068 00:59:30,803 --> 00:59:31,886 СЛУХАЛИ: Спасибі дуже багато. 1069 00:59:31,886 --> 00:59:34,692 РОБОТ: я виграю. 1070 00:59:34,692 --> 00:59:35,400 Я почати гру. 1071 00:59:35,400 --> 00:59:39,500 >> Доповідач: Гаразд, спасибі дуже багато Олів'є, і Алессандро, 1072 00:59:39,500 --> 00:59:41,616 і Чень Мін. 1073 00:59:41,616 --> 00:59:45,600 >> [Оплески] 1074 00:59:45,600 --> 00:59:47,040 >> Я хочу, щоб в останній момент. 1075 00:59:47,040 --> 00:59:51,630 Так Бакстер в дуже закінчується, обдурили. 1076 00:59:51,630 --> 00:59:54,160 1077 00:59:54,160 --> 00:59:56,310 І це було несподівано. 1078 00:59:56,310 --> 01:00:00,440 Один з фантастичні речі, про ШІ, що ми 1079 01:00:00,440 --> 01:00:05,070 зробити роботу в AI, так що ми можемо побудувати дійсно цікавий і розумний 1080 01:00:05,070 --> 01:00:06,930 пристрою. 1081 01:00:06,930 --> 01:00:10,130 Але ми також робимо роботу в AI тому що він говорить нам дещо 1082 01:00:10,130 --> 01:00:13,940 про те, як люди розумні. 1083 01:00:13,940 --> 01:00:17,280 >> Один з улюблених Дослідження, проведені в моїй лабораторії є 1084 01:00:17,280 --> 01:00:23,660 дивлячись на те, що відбувається, коли машини несподівано обдурити. 1085 01:00:23,660 --> 01:00:27,070 Ми зробили це спочатку ні з Бакстер грає в хрестики-нулики, 1086 01:00:27,070 --> 01:00:30,340 але з меншим робота на ім'я Нао, який грав рок-ножиці-папір. 1087 01:00:30,340 --> 01:00:33,010 1088 01:00:33,010 --> 01:00:35,800 А іноді після грати багато і багато 1089 01:00:35,800 --> 01:00:41,580 нудних рок-ножиці-папір ігри, робот буде кидати жест, 1090 01:00:41,580 --> 01:00:48,616 втратити, а потім раптом змінити його жест і сказати, я виграю. 1091 01:00:48,616 --> 01:00:50,480 >> [Сміх] 1092 01:00:50,480 --> 01:00:56,090 >> Тепер, іноді ми також робота, тільки в якості контролю, кинути жест, 1093 01:00:56,090 --> 01:01:01,270 виграти, і змінити його жест втратити, кинути сірник, 1094 01:01:01,270 --> 01:01:04,070 чит для того, щоб втратити. 1095 01:01:04,070 --> 01:01:07,540 І це далеко не переконливими. 1096 01:01:07,540 --> 01:01:09,890 Робот, який обдурює для того, щоб виграти людей 1097 01:01:09,890 --> 01:01:14,660 відповісти на, як якщо б це , Щоб отримати їх, як це 1098 01:01:14,660 --> 01:01:17,690 активно шукає їх руйнування. 1099 01:01:17,690 --> 01:01:19,210 >> [Сміх] 1100 01:01:19,210 --> 01:01:20,990 >> Вона стає агентом. 1101 01:01:20,990 --> 01:01:21,840 Це як людина. 1102 01:01:21,840 --> 01:01:23,970 Він має віру і намір. 1103 01:01:23,970 --> 01:01:27,470 І це не добрий намір. 1104 01:01:27,470 --> 01:01:33,790 І робот, який кидає гра просто неправильно. 1105 01:01:33,790 --> 01:01:36,990 Це просто розбите пристрій. 1106 01:01:36,990 --> 01:01:41,405 Дозвольте мені показати вам пару прикладів того, що від деяких з наших учасників. 1107 01:01:41,405 --> 01:01:43,990 1108 01:01:43,990 --> 01:01:45,600 Так от обман, щоб втратити. 1109 01:01:45,600 --> 01:01:46,266 >> [ВІДТВОРЕННЯ ВІДЕО] 1110 01:01:46,266 --> 01:01:47,010 - [Нерозбірливо] виграти. 1111 01:01:47,010 --> 01:01:49,550 Давай грати. 1112 01:01:49,550 --> 01:01:50,538 >> -Чекати, що? 1113 01:01:50,538 --> 01:01:54,490 1114 01:01:54,490 --> 01:01:55,352 >> - [Нерозбірливо] виграти. 1115 01:01:55,352 --> 01:01:58,280 Давай грати. 1116 01:01:58,280 --> 01:01:59,400 >> [Нерозбірливо] виграти. 1117 01:01:59,400 --> 01:02:02,290 Давай грати. 1118 01:02:02,290 --> 01:02:05,490 >> СЛУХАЛИ: І ось обман, щоб виграти. 1119 01:02:05,490 --> 01:02:06,438 >> Так, я виграю. 1120 01:02:06,438 --> 01:02:07,394 Давай грати. 1121 01:02:07,394 --> 01:02:08,828 >> -Ви Не можете цього зробити. 1122 01:02:08,828 --> 01:02:10,740 >> [Сміх] 1123 01:02:10,740 --> 01:02:12,174 1124 01:02:12,174 --> 01:02:13,979 >> Так, я виграю. 1125 01:02:13,979 --> 01:02:14,520 -Ви Обдурили. 1126 01:02:14,520 --> 01:02:17,990 1127 01:02:17,990 --> 01:02:20,010 Тепер ви обдурили. 1128 01:02:20,010 --> 01:02:21,140 >> Так, я виграю. 1129 01:02:21,140 --> 01:02:22,940 >> Гей, ви шахрай. 1130 01:02:22,940 --> 01:02:26,670 Ви обманюєте, супер чит. 1131 01:02:26,670 --> 01:02:27,650 >> [КІНЕЦЬ ПЕРЕГЛЯДУ] 1132 01:02:27,650 --> 01:02:31,130 >> СЛУХАЛИ: Такі різні Реакції швидко 1133 01:02:31,130 --> 01:02:34,890 змінити наше сприйняття пристрою. 1134 01:02:34,890 --> 01:02:36,780 Чи означає це, що ми свідомо будувати 1135 01:02:36,780 --> 01:02:40,370 машини, які обманюють, бо це кращий інженерно що ми можемо зробити? 1136 01:02:40,370 --> 01:02:44,680 Ні, але це говорить нам дещо дійсно цікаво про людей. 1137 01:02:44,680 --> 01:02:49,710 Це річ, яка обманює вас і краде ваша перемога, це 1138 01:02:49,710 --> 01:02:53,660 те, що живий, що це анімації, це, щоб отримати Вас. 1139 01:02:53,660 --> 01:02:54,680 Він має психічний стан. 1140 01:02:54,680 --> 01:02:55,400 Він має віру. 1141 01:02:55,400 --> 01:02:57,170 Він має намір. 1142 01:02:57,170 --> 01:03:01,540 >> Це річ, яка вручає гра для вас, це не так. 1143 01:03:01,540 --> 01:03:04,670 Ось тільки зі збоями. 1144 01:03:04,670 --> 01:03:08,900 Це багато в чому, чому це легко кинути гру з дітьми. 1145 01:03:08,900 --> 01:03:12,050 Але якщо ви спробуєте обдурити їх і начебто претендувати на перемогу 1146 01:03:12,050 --> 01:03:15,200 коли ви знаєте, просто, щоб скоротити гра, вони зловлять вас відразу. 1147 01:03:15,200 --> 01:03:19,040 1148 01:03:19,040 --> 01:03:23,140 Ці види ефектів, ми бачимо, виходить з AI, 1149 01:03:23,140 --> 01:03:26,490 вони вчать нас багато чому про себе. 1150 01:03:26,490 --> 01:03:28,076 >> Гаразд, це все на сьогодні. 1151 01:03:28,076 --> 01:03:30,450 Велике спасибі Давиду і знімальна група Гарвардського 1152 01:03:30,450 --> 01:03:32,350 для спускається. 1153 01:03:32,350 --> 01:03:33,820 >> [Оплески] 1154 01:03:33,820 --> 01:03:36,760 1155 01:03:36,760 --> 01:03:41,840 >> Ми будемо бачити Вас на одному вікторини, а потім протягом однієї останньої лекції. 1156 01:03:41,840 --> 01:03:43,025 Гарного дня. 1157 01:03:43,025 --> 01:03:44,965 >> [Оплески] 1158 01:03:44,965 --> 01:03:48,360 1159 01:03:48,360 --> 01:03:51,825 >> [Грає музика] 1160 01:03:51,825 --> 01:03:54,950 Девід Дж Малан: Ну, ми, ймовірно, повинні ввести якийсь шифрування, 1161 01:03:54,950 --> 01:03:55,450 вірно? 1162 01:03:55,450 --> 01:03:58,650 Бо тоді заголовках ці HTTP запити будуть 1163 01:03:58,650 --> 01:04:01,530 омлет так, що хто- намагаючись обнюхати трафіку 1164 01:04:01,530 --> 01:04:03,400 насправді не в змозі бачити їх. 1165 01:04:03,400 --> 01:04:05,254 Так що вирішення цієї проблеми? 1166 01:04:05,254 --> 01:04:07,920 Ну, ми повинні фактично ввести Шифрування в формулу, 1167 01:04:07,920 --> 01:04:11,010 так що, коли ця людина передачі даних від А до Б, 1168 01:04:11,010 --> 01:04:12,390 ми можемо надійно send-- 1169 01:04:12,390 --> 01:04:14,590 >> [Сміх] 1170 01:04:14,590 --> 01:04:19,530 >> Інформація таким чином, що супротивник не може, насправді, побачити його.