1354_lecture0_ver2 HarvardUniversity CS50_AI101 20 — Transcript

Full transcript

1. 0:04[музика]
2. 0:23Вітаю на вступній лекції до курсу вступ
3. 0:24до штучного інтелекту з паython мене
4. 0:26звати Брайан ю в цьому курсі ми
5. 0:28дослідимо ідеї техніки та алгоритми які
6. 0:31є основою штучного
7. 0:33інтелекту штучний інтелект охоплює
8. 0:35широкий спектр типів технології щоразу
9. 0:38коли ви бачите як комп'ютер робить щось
10. 0:40Що здається розумним чи раціональним
11. 0:42наприклад розпізнає обличчя на фото або
12. 0:44грає в гру краще ніж людина або здатен
13. 0:47розуміти людську мову коли ми
14. 0:49розмовляємо з телефоном Він розуміє що
15. 0:51ми маємо на увазі і може відповісти це
16. 0:55приклади штучного інтелекту в цьому
17. 0:57курсі дослідимо ідеї що роблять можливим
18. 0:59іс вання штучного
19. 1:01інтелекту почнемо розмову з пошуку
20. 1:04проблема полягає в тому що у нас є
21. 1:06штучний інтелект і ми хочемо щоби він
22. 1:08міг шукати рішення проблеми і неважливо
23. 1:11що це за проблема чи пошук маршруту від
24. 1:13точки А до точки Б чи спроба зрозуміти
25. 1:15як грати у Хрестики нулики з'ясовуючи
26. 1:17який рух треба зробити потім ми
27. 1:19розглянемо
28. 1:20знання в ідеалі Ми хочемо щоби штучний
29. 1:23інтелект міг знати інформацію
30. 1:25представляти її і що важливіше мати
31. 1:28можливість робити висновки на основі
32. 1:30цієї
33. 1:31інформації умійте використовувати відому
34. 1:34йому інформацію робити додаткові
35. 1:36висновки тож поговоримо про те як
36. 1:38штучний інтелект можна запрограмувати
37. 1:40для цього потім ми розглянемо тему
38. 1:42невизначеності що відбувається якщо
39. 1:44комп'ютер не впевнений у факті або
40. 1:46впевнений лише з певною
41. 1:49ймовірністю ми поговоримо про ідеї що
42. 1:51лежать в основі ймовірності і про те як
43. 1:54комп'ютери можуть працювати з
44. 1:55невизначеними подіями щоби також трохи
45. 1:58більше знатися на цьому після цього
46. 2:00звернемо увагу на оптимізацію цея
47. 2:02проблема пов'язана з тим що комп'ютер
48. 2:04намагається оптимізувати проблему для
49. 2:06досягнення цілі особливо в ситуації коли
50. 2:08він може вирішити завдання кількома
51. 2:10способами але ми шукаємо найкращий або
52. 2:13потенційно найкращий спосіб якщо це
53. 2:15взагалі можливо потім ми розглянемо
54. 2:17машини навчання або навчання загалом
55. 2:19коли ми маємо доступ до даних комп'ютери
56. 2:21можна запрограмувати так щоб вони
57. 2:22навчалися за допомого даних і досвіду
58. 2:25були здатні виконувати завдання дедалі
59. 2:27краще на основі ширшого доступу до даних
60. 2:30щоб наприклад папка вхідні в електронній
61. 2:32пошті якимось чином знала які листи
62. 2:34хороші а які спам це Приклади того як
63. 2:36комп'ютери можуть навчатися на минулих
64. 2:38досвіді та
65. 2:39даних також Розглянемо як комп'ютери
66. 2:42беруть натхнення з людського інтелекту
67. 2:45дивлячись на структуру людського мозку
68. 2:47та як нейронні мережі можуть бути
69. 2:49комп'ютерним аналогом такої
70. 2:51ідеї і як використовуючи переваги
71. 2:54комп'ютерної програми певного типу ми
72. 2:56можемо написати нейронні мережі здатні
73. 2:58ефективно виконувати завдання і нарешті
74. 3:01звернемо увагу на мову не на мову
75. 3:03програмування А на людські мови і
76. 3:06розглянемо які проблеми виникають коли
77. 3:08комп'ютер намагається зрозуміти природну
78. 3:10мову і на те як насправді може працювати
79. 3:13обробка природної мови яка відбувається
80. 3:16в сучасному штучному інтелекті
81. 3:19сьогоднішня розмова почнеться з пошуку
82. 3:21це спроба зрозуміти що робити коли є
83. 3:23якась ситуація у якій перебуває
84. 3:25комп'ютер і якесь середовище в якому так
85. 3:28би мовити є агент і ми би хотіли щоб цей
86. 3:31Агент міг шукати вирішення
87. 3:34завдання ці завдання можуть мати
88. 3:36будь-яку кількість форматів одним із
89. 3:38прикладів можуть бути п'ятнашки ви
90. 3:41напевне знаєте цю головоломку треба
91. 3:43вишикувати числа по порядку переміщаючи
92. 3:46плиточки це приклад того що можна
93. 3:48назвати завданням пошуку п'ятнашки вже
94. 3:51переплутані Нам потрібен спосіб знайти
95. 3:53послідовність ходів щоби повернути
96. 3:55головоломку до початкового
97. 3:58стану є схожі завдання які можна
98. 4:01сформулювати іншими способами наприклад
99. 4:04знайти шлях у лабіринті Це ще один
100. 4:06приклад завдання пошуку ви починаєте в
101. 4:09одному місці У вас є ціль Куди ви
102. 4:11намагаєтеся потрапити і вам потрібно
103. 4:13визначити правильну послідовність дій
104. 4:15які приведуть вас від початкового стану
105. 4:17до цілі це все трохи абстрактно Та коли
106. 4:20ми говоримо про проходження лабіринту ви
107. 4:22можете перекласти це на реальний світ
108. 4:25порівнявши наприклад з маршрутом у
109. 4:26дорозі ви коли-небудь замислювались як
110. 4:29Google Maps може визначити який для вас
111. 4:31найкращий спосіб дістатися з точки А в
112. 4:33точку б де В який час повернути залежно
113. 4:36від трафіку часто це певний алгоритм
114. 4:38пошуку У вас є штучний інтелект який
115. 4:40намагається дістатися від початкової
116. 4:42позиції до цілі виконуючи певну
117. 4:44послідовність дій розпочнемо нашу
118. 4:46розмову з роздумів про ці типи завдань
119. 4:48пошуку і про те що потрібно для
120. 4:50вирішення такого завдання пошуку щоби
121. 4:52штучний інтелект міг знайти хороше
122. 4:53рішення для цього нам потрібно вивчити
123. 4:56термінологію дещо ви вже чули від мене
124. 4:58та спершу поговоримо про агента Агент -
125. 5:01це сутність яка сприймає своє середовище
126. 5:03вона здатна сприймати речі навколо себе
127. 5:05та певним чином впливати на середовище
128. 5:08Якщо говорити про маршрут поїздки
129. 5:10агентом може виступати автомобіль який
130. 5:12намагається з'ясувати які дії потрібно
131. 5:15виконати щоби прибути на місце Якщо
132. 5:17говорити про п'ятнашки агентом може бути
133. 5:19штучний інтелект або людина яка
134. 5:21намагається розв'язати головоломку
135. 5:23намагаючи з'ясувати які плитки потрібно
136. 5:27перемістити далі ми вводимо поняття
137. 5:29стану стан - це конфігурація агента і
138. 5:32його
139. 5:34середовища наприклад у п'ятнашках
140. 5:36будь-який стан може бути будь-яким з цих
141. 5:39трьох стан - це лише конфігурація
142. 5:41плиточок кожен із цих станів різний і
143. 5:43вимагатиме дещо іншого рішення у кожному
144. 5:46з них потрібна буде інша послідовність
145. 5:48дій щоби дістатися від початкового стану
146. 5:51до цілі куди ми намагаємося
147. 5:54потрапити початковий стан що це
148. 5:57початковий стан - це стан з якого
149. 5:59починає Агент це один із таких станів з
150. 6:02якого ми можемо почати це стане
151. 6:04відправною точкою для нашого алгоритму
152. 6:06пошуку Ми почнемо з цього початкового
153. 6:09стану а потім почнемо міркувати про
154. 6:11нього думати про те які дії ми можемо
155. 6:13застосувати до цього початкового стану
156. 6:16щоб з'ясувати як дістатися від початку
157. 6:18до кінця від початкової позиції до цілі
158. 6:21як ми прокладаємо шлях від початкової
159. 6:23позиції до цілі Це залежить від дій дії
160. 6:26- це лише вибір який ми можемо зробити в
161. 6:28будь-якому у конкретному стані ми будемо
162. 6:31намагатися формалізувати ці ідеї трохи
163. 6:33точніше щоб ми могли запрограмувати їх
164. 6:36математично ця тема буде повторюватися І
165. 6:39ми можемо точніше визначити дії як
166. 6:41функцію ми визначимо функцію actions із
167. 6:45параметром S DS буде певним станом який
168. 6:48існує всередині
169. 6:50середовища actions S візьме стан як
170. 6:53параметр і повернеться у вигляді
171. 6:55результату набору всіх дій які можна
172. 6:58виконати в цьому стані
173. 7:00деякі дії можливі лише Для певних станів
174. 7:04незабаром ми побачимо
175. 7:05приклади у випадку з п'ятнашками це як
176. 7:09правило чотири можливі дії які ми можемо
177. 7:11виконувати більшу частину часу ми можемо
178. 7:14пересунути плитку вправо вліво
179. 7:16пересунути вгору або вниз і лише ці дії
180. 7:19будуть нам
181. 7:22доступні якимось чином штучному
182. 7:25інтелекту програмі потрібне кодування
183. 7:28стану яке часто має бути в числовому
184. 7:30форматі і кодування дій але також
185. 7:33потрібне кодування зв'язку між тим як
186. 7:35стани та дії співвідносяться між собою
187. 7:38для того щоб це зробити введемо в
188. 7:40штучний інтелект модель переходу яка
189. 7:43описуватиме який стан Ми отримаємо після
190. 7:46виконання певної дії в іншому
191. 7:48стані ми можемо бути трохи більш точними
192. 7:51щодо цього визначаючи цю модель переходи
193. 7:53трохи більш формальною як функцію це
194. 7:56буде
195. 7:56функція яка цього разу матиме два
196. 7:59параметри перший параметр S - це стан
197. 8:03другий параметр a - це
198. 8:05дія функція повертає стан який ми
199. 8:08отримаємо після виконання дії
200. 8:11a у стані
201. 8:13S подивімося на приклад і точніше
202. 8:16побачимо що це означає ось стан на
203. 8:19прикладі п'ятнашок А ось приклад дії
204. 8:22ковзання плитки
205. 8:24вправо що станеться якщо ми передамо ці
206. 8:27параметри функції зал
207. 8:30функція result приймає цю дошку цей стан
208. 8:32як перший параметр і приймає дію як
209. 8:35другий параметр я візуалізую приклад щоб
210. 8:38ви бачили що таке стан і що таке дія у
211. 8:41комп'ютері ви можете представити одну з
212. 8:43дій як число Або якщо ви знайомі з
213. 8:46переліками inams які дозволяють
214. 8:48перераховувати кілька можливостей це
215. 8:50може бути щось подібне а стан може бути
216. 8:52представлений у вигляді масиву або
217. 8:54двовимірного масиву цих чисел але я все
218. 8:57візуалізую щоб ви могли це побачити коли
219. 9:00ми приймаємо цей стан і цю дію передаємо
220. 9:03їх функції result результатом є новий
221. 9:05стан стан який ми отримаємо після того
222. 9:08як беремо плитку і пересуваємо її вправо
223. 9:11це стан який ми отримаємо в результаті
224. 9:13якби ми мали іншу дію та інший стан і
225. 9:16передали їх функції result то отримали б
226. 9:18іншу відповідь Отже функція result має
227. 9:22дбати про те як прийняти стан виконати
228. 9:24дію та отримати результати це і буде
229. 9:27наша модель переходу яка описує як
230. 9:29пов'язані стани та дії Якщо ми візьмемо
231. 9:32цю модель переходу і подумаємо про неї
232. 9:35Загалом у масштабах усього завдання ми
233. 9:37зможемо сформувати простір станів Це
234. 9:40набір усіх станів які можна отримати з
235. 9:42початкового стану за допомогою будь-якої
236. 9:44послідовності дії виконуючи нуль одну
237. 9:47дві або більше дій щоб ми могли
238. 9:49намалювати приблизно таку діаграму тут
239. 9:52кожен стан представлено ігровою дошкою є
240. 9:55стрілки які з'єднують стан з іншим
241. 9:58станом який можна отримати з цього стану
242. 10:00простір станів набагато більший ніж те
243. 10:02що ви бачите Це просто один фрагмент
244. 10:04простору станів Загалом у багатьох
245. 10:06завданнях пошуку Незалежно від того чи
246. 10:08це п'ятнашки чи пошук маршруту чи щось
247. 10:11інше простір станів матиме приблизно
248. 10:13Такий вигляд є окремі стани та стрілки
249. 10:16які їх
250. 10:18з'єднують часто для простоти ми будемо
251. 10:20спрощувати все це до вигляду графа тобто
252. 10:23певної послідовності вузлів і ребер які
253. 10:26з'єднують вузли ви можете вважати це
254. 10:29абстрактним поданням тієї самої
255. 10:31ідеї кожен з цих кругів або вузлів
256. 10:34представлятиме Один зі станів усередині
257. 10:36проблеми а стрілки представляють дії які
258. 10:40ми можемо виконувати в будь-якому
259. 10:41конкретному стані переходячи з одного
260. 10:44конкретного стану в
261. 10:47інший Отже тепер у нас є ідея вузлів які
262. 10:51представляють стани дій які можуть
263. 10:53перевести нас з одного стану в інший і
264. 10:56моделі переходу яка визначає що
265. 10:58відбувається після виконання певної дії
266. 11:00з'ясуємо наступний крок як ми дізнаємося
267. 11:03коли штучний інтелект закінчив вирішення
268. 11:05завдання йому потрібен спосіб дізнатися
269. 11:08що він досяг цілі коли він її досяг далі
270. 11:11у штучному інтелекті потрібно закодувати
271. 11:13перевірку цілі тобто якийсь спосіб
272. 11:16визначити чи є певний стан цільовим Якщо
273. 11:19говорити про маршрут це легко якщо ви
274. 11:21перебуваєте в стані який відповідає тому
275. 11:24що користувач ввів як Пункт призначення
276. 11:26то ви знаєте що ви перебуваєте в
277. 11:28цільовому
278. 11:30у п'ятнашках можна перевірити чи
279. 11:32розташовані числа в порядку зростання
280. 11:34але штучному інтелекту потрібен спосіб
281. 11:36кодування того чи є стан у якому він
282. 11:38перебуває
283. 11:39ціллю деякі завдання можуть мати одну
284. 11:42ціль наприклад Лабіринт у якому є одна
285. 11:44початкова позиція і одна кінцева у
286. 11:46складніших завданнях можливе існування
287. 11:48кількох цілей а отже і кілька способів
288. 11:50вирішення завдання нам може бути байдуже
289. 11:53яку з них знайде комп'ютер Головне щоб
290. 11:55знайшов однак інколи комп'ютер дбає не
291. 11:58лише про про те щоб знайти ціль а й про
292. 12:00те щоб знайти ціль ефективною чи з
293. 12:03низькою ціною саме тому останнім
294. 12:05терміном який ми використовуємо для
295. 12:07визначення завдання пошуку Є вартість
296. 12:10шляху можете уявити що у випадку пошуку
297. 12:13маршруту було б дуже неприємно Якби я
298. 12:15сказав що хочу проїхати з точки А у
299. 12:17точку б а маршрут який намалювала Google
300. 12:20карта був довгим із багатьма поворотами
301. 12:22і мені знадобилося значно більше часу
302. 12:26саме з цієї причини коли ми формулюємо
303. 12:28завдання пошуку ми часто надаємо кожному
304. 12:31шляхові певну числову вартість якесь
305. 12:33число яке говорить нам наскільки дорого
306. 12:36обійдеться цей конкретний варіант
307. 12:38вкажіть штучному інтелекту Що замість
308. 12:40того щоби шукати будь-який спосіб
309. 12:42дістатися від початкового стану до цілі
310. 12:45Ми хотіли би знайти такий Який мінімізує
311. 12:48вартість шляху або менш дорогий або
312. 12:50займає менше часу або мінімізує якесь
313. 12:53інше числове значення ми можемо
314. 12:56представити це графічно якщо подивимося
315. 12:58на граф І уявимо що кожна стрілка кожна
316. 13:01дія які ми можемо виконувати для
317. 13:03переходу з одного стану в інший має
318. 13:05якесь число пов'язане з нею це число і є
319. 13:08вартістю шляху цієї конкретної дії
320. 13:11вартість будь-якої конкретної дії може
321. 13:12бути дорожчою ніж вартість іншої дії
322. 13:15хоча це можливо лише в деяких завданнях
323. 13:18в інших завданнях ми можемо спростити
324. 13:19схему і припустити що вартість будь-якої
325. 13:22дії однакова це наприклад стосується
326. 13:24п'ятнашок де немає значення рухаюся я
327. 13:27праворуч чи ліворуч має значення лише
328. 13:29загальна кількість кроків які я маю
329. 13:31зробити щоби дістатися з пункту А у
330. 13:34пункт б і кожен крок має однакову
331. 13:36вартість можемо припустити що ця
332. 13:38вартість стала наприклад одиниця це
333. 13:41формує основу для того що ми можемо
334. 13:43вважати завданням пошуку завдання пошуку
335. 13:46має певний початковий стан місце з якого
336. 13:49ми починаємо певну дію або кількість дій
337. 13:51які ми можемо виконати і модель
338. 13:53переходу- спосіб визначення того що
339. 13:56відбувається коли ми переходимо з одного
340. 13:58стану і і виконуємо одну дію в
341. 14:00результаті якої отримаємо інший стан
342. 14:03крім того потрібна перевірка цілі щоби
343. 14:06дізнатися досягли ми цілі чи ні і
344. 14:08функція вартості шляху яка повідомляє
345. 14:11нам дотримуючись певної послідовності
346. 14:13дій наскільки дорогий цей шлях яка його
347. 14:16вартість з точки зору грошей часу чи
348. 14:18інших ресурсів використання яких ми
349. 14:21намагаємося мінімізувати мета полягає в
350. 14:23тому щоби знайти рішення рішенням у
351. 14:26цьому випадку буде послідовність дій
352. 14:28якій переведуть нас із початкового стану
353. 14:30До цільового стану вделі Ми хотіли би
354. 14:33знайти не будь-яке рішення а оптимальне
355. 14:36рішення яке має найнижчу вартість шляху
356. 14:39серед усіх можливих рішень у деяких
357. 14:41випадках може бути кілька оптимальних
358. 14:43рішень але оптимальне рішення означає що
359. 14:45ми не могли би зробити краще з точки
360. 14:48зору пошуку рішення Отже ми визначили
361. 14:51завдання тепер потрібно з'ясувати як ми
362. 14:54вирішимо це завдання
363. 14:56пошуку для того щоб зробити це ви мабуть
364. 14:59уявити що комп'ютеру потрібно буде
365. 15:01надати купу даних що стосуються завдання
366. 15:04йому потрібні дані про те де ми в
367. 15:06завданні можливо доведеться розглядати
368. 15:08кілька різних варіантів одночасно часто
369. 15:11Коли ми намагаємося об'єднати купу даних
370. 15:13пов'язаних зі станом ми робимо це за
371. 15:15допомогою структури даних яку називаємо
372. 15:18вузлом вузол - це структура даних яка
373. 15:21відстежує безліч різних значень зокрема
374. 15:24у випадку завдання пошуку вона
375. 15:25відстежуватиме ці чотири значення кожен
376. 15:28вузол відстежуватиме стан у якому ми
377. 15:31перебуваємо і кожен вузол також буде
378. 15:33стежити за батьком батько - Це
379. 15:36попередній стан або вузол який ми
380. 15:38використовували для переходу до
381. 15:40поточного стану це буде важливо бо Як
382. 15:43тільки ми досягнемо цільового вузла як
383. 15:45тільки підійдемо до кінця ми захочемо
384. 15:48знати яку послідовність дій ми
385. 15:50використали щоби досягти цілі а
386. 15:52дізнаємося ми це дивлячись на цих
387. 15:54батьків щоби відстежити що привело нас
388. 15:57до цілі до цього стану до попереднього
389. 15:59стану і так далі повертаючись назад до
390. 16:02початку ми знатимемо всю послідовність
391. 16:04дій які нам потрібні щоб пройти від
392. 16:07початку до кінця вузол відстежуватиме
393. 16:10які дії ми виконали щоб перейти від
394. 16:12батьківського стану До поточного вузол
395. 16:14також відстежуватиме вартість шляху
396. 16:17інакше кажучи він відстежуватиме число
397. 16:19яке Показує скільки часу знадобиться
398. 16:22щоби перейти від початкового стану До
399. 16:24поточного стану ми побачимо чому це
400. 16:27важливо коли будемо говорити про
401. 16:28оптимізації які ми можемо зробити з
402. 16:31точки зору завдань
403. 16:32пошуку Отже це структура даних яку ми
404. 16:35будемо використовувати для вирішення
405. 16:37завдання а тепер поговоримо про підхід
406. 16:39як розпочати вирішення завдання Ми
407. 16:41почнемо з одного конкретного стану
408. 16:43просто будемо його досліджувати інтуїція
409. 16:46вам підкаже що в нас є кілька варіантів
410. 16:48розвитку подій ми будемо вивчати всі
411. 16:50варіанти і Як тільки ми вивчимо їх то
412. 16:53побачимо що ще більше варіантів стануть
413. 16:55доступними ми розглянемо всі доступні
414. 16:58варіанти що будуть зберігатися в одній
415. 17:00структурі даних яку ми назвемо межею
416. 17:04межа представлятиме все що ми могли би
417. 17:06дослідити далі але ще не дослідили Отже
418. 17:09розпочинаємо наш підхід з алгоритму
419. 17:11пошуку почнемо з межі яка містить лише
420. 17:14один стан межа містить початковий стан
421. 17:17тому що на початку це єдиний стан про
422. 17:19який ми знаємо це єдиний стан який
423. 17:27існує тим пошуку фактично буде циклом ми
424. 17:30будемо повторювати процес знову і знову
425. 17:33і
426. 17:34знову що ми зробимо зпершу якщо межа
427. 17:38порожня то рішення немає можна
428. 17:41повідомити що немає можливості досягнути
429. 17:43цілі таке можливо є певні типи завдань
430. 17:46які штучний інтелект може Дослідити і
431. 17:48зрозуміти що немає способу вирішити це
432. 17:50завдання це теж корисна інформація якщо
433. 17:53межа буде порожньою це означає що
434. 17:56досліджувати нема чого і що ми не
435. 17:58знайшли рішення рішення немає нема чого
436. 18:02досліджувати інакше ми видаілимо вузол
437. 18:05із межі зараз на початку межа містить
438. 18:08лише один вузол що представляє
439. 18:10початковий стан але з часом межа Може
440. 18:14розростатися вона Може містити кілька
441. 18:16станів тому тут ми просто видалимо один
442. 18:19вузол з межі якщо цей вузол є ціллю тоді
443. 18:23ми знайшли рішення тому видаляємо вузол
444. 18:26з межі і запитуємо себе це ціль а робимо
445. 18:30це застосовуючи перевірку цілі про яку
446. 18:32ми говорили раніше запитуючи чи ми на
447. 18:35місці призначення або чи всі числа в
448. 18:37п'ятнашках стоять по порядку Отже якщо
449. 18:41вузол містить ціль ми знайшли рішення
450. 18:44мити досягнуто інакше нам потрібно буде
451. 18:47розширити вузол це термін у штучному
452. 18:49інтелекті він означає переглянути всіх
453. 18:52сусідів цього вузла інакше кажучи
454. 18:55розглянемо всі можливі дії які я міг би
455. 18:57виконати зі стану який представляє цей
456. 19:00вузол і до яких вузлів я міг би
457. 19:02дістатися візьмемо всі ці вузли наступні
458. 19:05вузли до яких я можу дістатися з цього
459. 19:08поточного і додамо їх до межі а потім
460. 19:11повторимо процес на дуже загальному
461. 19:13рівні ідея полягає в тому що ми
462. 19:15починаємо з межі яка містить початковий
463. 19:18стан постійно видаляємо вузол з межі
464. 19:21Дивлячись куди можемо дістатися далі і
465. 19:24додаємо ці вузли до межі повторюючи про
466. 19:26це знову і знову доки або не видалимо
467. 19:29вузол з межі бо він міститиме ціль Тобто
468. 19:32ми вирішили завдання або не зіткнемося
469. 19:34із ситуацією коли межа порожня тобто
470. 19:37рішення немає спробуємо взяти псевдокод
471. 19:40і застосувати його на практиці
472. 19:41розглянувши приклад завдання пошуку це
473. 19:44зразок графа a з'єднується з B за
474. 19:46допомогою цієї дії B з'єднується з
475. 19:49вузлами c і D C з і D з F Я хотів би
476. 19:53щоби штучний інтелект знайшов шлях від a
477. 19:56до і ми хочемо дістатися від цього
478. 19:58початкового стану До цього цільового
479. 20:00стану як ми це зробимо почнемо з межі
480. 20:03яка містить початковий стан червоне поле
481. 20:06буде межею вона спочатку міститиме лише
482. 20:08a початковий стан з якого ми почнемо і
483. 20:11повторимо процес якщо межа порожня
484. 20:14рішення немає це не наш варіант бо межа
485. 20:16не порожня тож видалимо вузол із межі як
486. 20:20такий що слід розглянути наступним на
487. 20:22межі є лише один вузол видалимо його з
488. 20:25межі тепер Ей початковий вузол це вузол
489. 20:28який ми зараз розглядаємо переходимо до
490. 20:31наступного кроку запитуємо себе цей
491. 20:33вузол є ціллю ні е не ціль ціль і тому
492. 20:38не повертаємо рішення замість цього
493. 20:41переходимо до останнього кроку
494. 20:43розширюємо вузол і додаємо отримані
495. 20:45вузли до межі що це означає це означає
496. 20:48взяти стан a і подумати куди ми можемо
497. 20:51потрапити після a є єдиний маршрут B Ось
498. 20:55що ми отримаємо коли розгорнемо A ми
499. 20:58знайдемо бій додаємо бій до межі тепер
500. 21:01бій на межі А ми повторюємо процес межа
501. 21:04непорожня Отже прибираємо бі з межі бій
502. 21:07став вузлом який ми розглядаємо
503. 21:09запитуємо бі - це ціль ні значить
504. 21:13розширяємо бій і додаємо отримані вузли
505. 21:15до межі Що станеться коли ми розширимо B
506. 21:18тобто до яких вузлів ми можемо дістатися
507. 21:20з B можемо дістатися до c і D додаємо c
508. 21:23і D до межі тепер на межі два вузли c і
509. 21:26D повторюємо про це видаляємо вузол межі
510. 21:29поки що робимо це довільно спершу
511. 21:32видаливши сі пізніше побачимо що вибір
512. 21:34вузла який треба видалити з межі - Це
513. 21:36важлива частина алгоритму Але зараз я
514. 21:39довільно видаляю сі тому що це не ціль
515. 21:42додаю і до межі тоді скажімо Я видаляю і
516. 21:45з межі Я дивлюся на стан і це цільовий
517. 21:48стан так тому що я намагаюся знайти шлях
518. 21:51від Е до і тому Я повернув би ціль це і
519. 21:55буде рішенням я можу повернути рішення Я
520. 21:58знайшов шлях від a до
521. 22:00і Отже це загальна ідея загальний підхід
522. 22:04цього алгоритму пошуку виконувати кроки
523. 22:06постійно видаляючи вузли з межі поки ми
524. 22:09не знайдемо рішення наступне запитання
525. 22:11яке виникає Логічно що може піти не так
526. 22:15які потенційні проблеми в такому підході
527. 22:18наведу вам один приклад проблеми яка
528. 22:20може виникнути уявіть цей самий граф але
529. 22:23з однією
530. 22:24зміною зміна полягає в тому що замість
531. 22:28від a до B Ми також маємо стрілку від B
532. 22:31до a Тобто можна рухатися в обох
533. 22:33напрямках це реальна ситуація у
534. 22:35п'ятнашках Де я можу пересунути плитку
535. 22:37праворуч а потім можу пересунути її
536. 22:39ліворуч щоби Повернутися у вихідне
537. 22:42положення ось яку ідею символізують Ці
538. 22:44дві стрілки я можу потрапити з одного
539. 22:47стану в інший а потім повернутися це
540. 22:50реальна ситуація в багатьох завданнях
541. 22:52пошуку що станеться якщо я спробую
542. 22:54застосувати той самий підхід зараз почну
543. 22:57з A як і раніше видаляю a з межі потім
544. 23:01подумаю куди я можу потрапити з a після
545. 23:03a я можу вибрати тільки B тому B
546. 23:05переходить до межі далі розглянемо B
547. 23:08тільки B лишилося на межі куди я можу
548. 23:11потрапити з B раніше це були лише c і D
549. 23:14але тепер завдяки зворотній стрілці є a
550. 23:17c або D Отже усі три AC c і D Усі вони
551. 23:22йдуть на межу це місця куди я можу
552. 23:25потрапити збій Я знімаю одне з межі
553. 23:27можливо мені не пощастить і я виберу a
554. 23:30Тепер я знову Думаю куди я можу
555. 23:32потрапити з a Ну я можу потрапити в B
556. 23:34тепер ми бачимо проблему якщо я
557. 23:37необережний то я йду з a у B потім
558. 23:40повертаюся до a потім знову до B я можу
559. 23:43перебувати в цьому нескінченному циклі
560. 23:45де ніколи не досягну прогресу бо я
561. 23:48постійно ходитиму між двома станами чи є
562. 23:51рішення потрібен спосіб вирішення
563. 23:53завдання Цей спосіб полягає в тому щоб
564. 23:55якимось чином стежити за тим що ми вже
565. 23:58дослідили логіка така якщо ми вже
566. 24:01дослідили стан немає причин повертатися
567. 24:03до нього після того як ми дослідили стан
568. 24:06не повертайтесь до нього не додавайте
569. 24:08його до межі Отже ось кращий спосіб
570. 24:11підійти до такого роду завдання пошуку
571. 24:13він буде дуже схожим лише з парою
572. 24:15модифікацій почнемо з межі яка містить
573. 24:18початковий стан те саме що і раніше але
574. 24:22тепер почнемо з іншої структури даних
575. 24:25яка буде просто набором вузлів які ми
576. 24:27вже дослідили який стане ми дослідили
577. 24:30Спочатку він порожній У нас є порожній
578. 24:33досліджений набір тепер повторюємо якщо
579. 24:36межа порожня рішення немає те саме щой
580. 24:38раніше видаляємо вузол із межі і
581. 24:41Перевіряємо чи це цільовий стан
582. 24:44повертаємо рішення Поки що все так само
583. 24:46але тепер Ми додамо вузол до
584. 24:49дослідженого стану якщо станеться так що
585. 24:51ми видалимо вузол з межі і це не ціль Ми
586. 24:54додамо його до дослідженого набору щоб
587. 24:57ми знали що ми його вже дослідили не
588. 24:59потрібно повертатися до нього знову Якщо
589. 25:01це станеться пізніше на останньому кроці
590. 25:04ми розширяємо вузол і додаємо отримані
591. 25:06вузли до межі ми завжди додаємо отримані
592. 25:09вузли до межі але цього разу будемо
593. 25:12розумнішими додамо до межі вузли тільки
594. 25:14якщо вони ще не на межі і якщо вони ще
595. 25:17не в дослідженому наборі Тобто ми
596. 25:19перевіримо як межу так і досліджений
597. 25:23набір переконаємося що вузла немає ні
598. 25:25там ні там і поки це не Так Ми
599. 25:28продовжимо і додамо до межі але не
600. 25:30інакше тобто цей переглянутий підхід
601. 25:33зрештою допоможе переконатися що ми не
602. 25:36переходимо туди-сюди між двома вузлами
603. 25:39єдиний момент про який я змовчав - це
604. 25:41цей крок видалення вузла з межі раніше я
605. 25:44вибирав довільно видалимо цей вузол і
606. 25:46все але виявилося що насправді дуже
607. 25:49важливо те як ми вирішуємо структурувати
608. 25:52межу як ми додаємо та видаляємо вузли
609. 25:55межа - це структура даних потрібно
610. 25:58вибрати у якому порядку ми будемо
611. 26:00видаляти елементи однією з найпростіших
612. 26:02структур даних для додавання та
613. 26:05видалення елементів є стек стек - це
614. 26:07структура даних яка працює за принципом
615. 26:10останнім прийшов першим вийшов це
616. 26:12означає що Останнє що я додам до межі
617. 26:15буде першим що я видаляю з межі Отже
618. 26:18останнім елементом який увійде в стек
619. 26:20або в цьому випадку в межу буде вузол
620. 26:23який я досліджую подивімося що станеться
621. 26:26якщо я сую стековий підхід до чогось на
622. 26:29зразок цього завдання знаходження шляху
623. 26:32від a до І що станеться ми знову почнемо
624. 26:35з a спершу розглянемо a Зверніть увагу
625. 26:39що цього разу ми додали a до
626. 26:41дослідженого набору a уже досліджений у
627. 26:45нас є структура даних яка це відстежує з
628. 26:48a ми можемо дістатися до B що ми можемо
629. 26:51зробити з b дослідимо b з нього ми
630. 26:54можемо дістатися до c і D додамо C потім
631. 26:57ді тож тепер коли ми досліджуємо вузол
632. 27:01ми розглядатимемо межу як стек останнім
633. 27:04увійшов першим вийшов D увійшов останнім
634. 27:07Тому дослідимо далі його Куди ми можемо
635. 27:10потрапити з D можемо дістатися до F
636. 27:13ставимо F на межу оскільки межа - це
637. 27:15стек F - це останній елемент у стеку
638. 27:18тобто далі ми досліджуємо F досліджуємо
639. 27:21F куди ми можемо дістатися з F нікуди
640. 27:24тому до межі нічого не додається який
641. 27:26останній елемент ми додали до межі тепер
642. 27:29це C тому що це єдиний вузол у межі
643. 27:32дослідимо його і C ми можемо дістатися
644. 27:35до і і переходить до
645. 27:38межі досліджуємо і і - це рішення ми
646. 27:43розв'язали
647. 27:44завдання коли ми розглядаємо межу як
648. 27:47стек структуру даних останнім прийшов
649. 27:50першим вийшов це результат який ми
650. 27:52отримаємо ми переходимо від a до B df а
651. 27:55потім повертаємося і йдемо до с а потім
652. 27:58до і важливо отримати візуальне уявлення
653. 28:01того як працює алгоритм ми зайшли дуже
654. 28:04глибоко в дерево пошуку аж до самого дна
655. 28:07де потрапили в глухий кут і повернули
656. 28:09назад і дослідили інший маршрут який
657. 28:12раніше не пробували це глибоке
658. 28:14проникнення в ідею дерева пошуку Таким
659. 28:16чином алгоритм закінчує роботу коли ми
660. 28:19використовуємо стек ми називаємо цю
661. 28:22версію алгоритму пошуком у глибину пошук
662. 28:24у глибину - це алгоритм пошуку де ми
663. 28:26завжди дос найглибший вузол у межі ми
664. 28:29заглиблюємося в дерево пошуку А якщо
665. 28:31потрапляємо в глухий кут повертаємось і
666. 28:34пробуємо щось інше пошук у глибину - це
667. 28:37лише один із можливих варіантів пошуку
668. 28:40виявляється існує ще один алгоритм під
669. 28:42назвою пошук ширину який поводиться
670. 28:44подібно до пошуку в глибину з однією
671. 28:47відмінністю замість того щоби
672. 28:49досліджувати найглибший вузол у дереві
673. 28:51пошуку як це робить пошук у глибину
674. 28:53пошук у ширину завжди досліджуватиме
675. 28:55найближчий вузол у межі що це означає що
676. 28:59замість використання пошуку в глибину
677. 29:00або deps First search dfs який досліджує
678. 29:04останній елемент доданий до межі пошуку
679. 29:07у ширину або breads First search bfs
680. 29:11натомість буде використовувати чергу
681. 29:13черга - це тип даних першим прийшов
682. 29:15першим вийшов у черзі перше що ми
683. 29:18додаємо до межі буде першим що ми
684. 29:20досліджуємо елементи утворюють лінію або
685. 29:22чергу у якій що раніше ви прибуваєте на
686. 29:25межу То раніше вас досліджують
687. 29:27що це означає те саме завдання пошуку
688. 29:30шляху від a до і починаємо з A як і
689. 29:33раніше досліджуємо a куди ми можемо
690. 29:35дістатися з a до B так само як і раніше
691. 29:39від B як і раніше до c і D C і D
692. 29:42додаються до межі однак цього разу ми
693. 29:46додали C перед D тому спочатку дослідимо
694. 29:49C досліджуємо куди ми можемо потрапити з
695. 29:52с до і і додається до межі але оскільки
696. 29:56ді було досліджено раніше за і ми
697. 29:59розглянемо D
698. 30:01першим досліджуємо D куди можна
699. 30:04дістатися з D до F і тільки тоді можемо
700. 30:07перейти до і Отже що зробив пошук в
701. 30:11ширину або bfs ми почали тут перевірили
702. 30:14c і D а потім перейшли до і по суті ми
703. 30:18перевірили все на відстані однієї
704. 30:21стрілки від початкового стану потім на
705. 30:24відстані двох Стрілок І лише потім усе
706. 30:26на відстані трьох Стрілок на відміну від
707. 30:28пошуку в глибину який просто заходив
708. 30:31якомога глибше в дерево пошуку поки не
709. 30:33потрапляв у глихий кут а потім
710. 30:35повертався Отже це два різні алгоритми
711. 30:38пошуку які ми можемо застосувати щоб
712. 30:41вирішити завдання подивимося як це
713. 30:43працюватиме на практиці наприклад із
714. 30:45проходженням лабіринту порожні клітини
715. 30:47представляють місця куди може
716. 30:49пересуватися Агент затемнені сіри
717. 30:51клітини представляють стіни через які
718. 30:54Агент не може пройти Агент штучний
719. 30:56інтелект спробує знайти спосіб пройти з
720. 30:58позиції a у позицію
721. 31:00B за допомогою певної послідовності дій
722. 31:04ліворуч праворуч Вгору та вниз що в
723. 31:07цьому випадку дасть пошук у глибину
724. 31:10пошук у глибину проходитиме лише одним
725. 31:12шляхом якщо він дійде до розвилки де він
726. 31:15має кілька варіантів то спочатку вибере
727. 31:17якийсь один переваг немає І продовжить
728. 31:20іти цим шляхом поки не потрапить у
729. 31:22глухий кут з глухого кута пошук у
730. 31:25глибину повертається до останньої точки
731. 31:27прийняття рішення і перевіряє інший шлях
732. 31:30повністю вичерпавши весь цей шлях і
733. 31:33зрозумівши що цілі тут немає Він звертає
734. 31:36свою увагу на цей шлях іде якомога
735. 31:39глибше потрапляє в глухий кут
736. 31:41повертається назад перевіряє інший шлях
737. 31:44продовжує йти якомога глибше одним
738. 31:46конкретним шляхом А коли я розумію що це
739. 31:49теж глухий кут повертається назад і
740. 31:52зрештою знаходить шлях до цілі можливо
741. 31:55вам пощастило Можливо ви раніше зробили
742. 31:57інший вибір але зрештою Саме так
743. 31:59працюватиме пошук у глибину він ітиме
744. 32:02одним шляхом поки не потрапить у глухий
745. 32:05кут а потім повернеться і шукатиме інше
746. 32:07рішення ви слушно можете запитати чи
747. 32:10завжди цей алгоритм працюватиме чи
748. 32:12завжди він дійсно і знайдей спосіб
749. 32:14дістатися від початкового стану до цілі
750. 32:16Виявляється що поки Лабіринт обмежений
751. 32:19поки ми маємо кінцеву кількість
752. 32:21просторів де ми можемо подорожувати тоді
753. 32:24так пошук у глибину допоможе знайти
754. 32:26рішення а бо зрештою Він дослідить усе
755. 32:29якщо Лабіринт нескінченний і існує
756. 32:31нескінченний простір станів який дійсно
757. 32:33існує в певних типах завдань тоді це
758. 32:36інша історія але поки Лабіринт має
759. 32:38кінцеву кількість квадратів Ми
760. 32:40збираємося знайти рішення наступне
761. 32:42запитання чи буде це рішення хорошим Чи
762. 32:44це оптимальне рішення яке ми можемо
763. 32:46знайти відповідь Не обов'язково
764. 32:48розглянемо інший приклад у цьому
765. 32:50лабіринті ми знову намагаємося знайти
766. 32:53шлях від a до B ви вже помітили що тут є
767. 32:56кілька можливих рішень можна піти цим
768. 32:58шляхом або піднятися вгору щоб пройти
769. 33:00від a до B Якщо нам пощастить пошук у
770. 33:03глибину вибере цей шлях і дійде до Бій
771. 33:07але немає жодної причини чому пошук у
772. 33:09глибину вибирав би підйом у гору спершу
773. 33:12це довільна точка прийняття рішення
774. 33:14оскільки обидва будуть додані до межі
775. 33:17Якщо нам не пощастить пошук і глибину
776. 33:20Може спочатку вибрати цей шлях тому що
777. 33:23це випадковий вибір Він буде
778. 33:25досліджувати досліджувати досліджува
779. 33:27і зрештою знайде ціль цей конкретний
780. 33:30шлях хоча бу в кращий шлях було більш
781. 33:33оптимальне рішення з меншою кількістю
782. 33:35кроків ми припускаємо що вимірюємо
783. 33:37вартість рішення на основі кількості
784. 33:39кроків Таким чином Якщо нам не пощастить
785. 33:42пошук у глибину може закінчитися
786. 33:44знаходженням не найкращого рішення хоча
787. 33:46краще буде доступне Отже Це dfs пошук у
788. 33:50глибину як щодо bfs або пошуку в ширину
789. 33:53Як би він спрацював у цій ситуації
790. 33:56візуально алгорит матиме зовсім інший
791. 33:58вигляд з точки зору того як bfs
792. 34:00досліджує оскільки bfs спочатку дивиться
793. 34:02на ближчі вузли ідея полягає в тому що
794. 34:05bfs спочатку розглядатиме всі вузли які
795. 34:08розташовані на одинарній відстані від
796. 34:10початкового стану оцей і оцей наприклад
797. 34:13які розташовані поруч із початковим
798. 34:15станом потім він дослідить вузли
799. 34:17розташовані на подвійній відстані потім
800. 34:19дослідить вузли розташовані на потрійній
801. 34:21відстані цей стан і цей У той час як
802. 34:24пошук у глибину вибрав один шлях і йшов
803. 34:27ним пошук у ширину використовує варіант
804. 34:30дослідження всіх можливих шляхів ніби
805. 34:32одночасно перескакуючи між ними
806. 34:34Досліджуючи глибше і глибше кожен але
807. 34:37обов'язково спершу Досліджуючи найближчі
808. 34:39до початкового стану продовжуємо
809. 34:42дотримуватися цієї моделі Досліджуючи на
810. 34:44відстані чотирьох кроків п'яти кроків
811. 34:47потім шести кроків поки зрештою не
812. 34:49досягнемо
813. 34:51цілі у цьому випадку правда що нам
814. 34:54довелося досліджувати деякі стани які
815. 34:56зрештою нікуди не привели але шлях який
816. 34:59ми знайшли до цілі був оптимальним це
817. 35:02найкоротший шлях яким ми могли пройти що
818. 35:05ж може статися у більшому лабіринті
819. 35:07подивімося як пошук у ширину спрацює в
820. 35:10цьому лабіринті спочатку пошук у ширину
821. 35:12стежитиме за
822. 35:14станами Доки не досягне точки прийняття
823. 35:17рішення іти ліворуч чи праворуч якщо dфs
824. 35:20вибрав би один і продовжував би йти ним
825. 35:23поки не зайшов у глухий кут bfs
826. 35:26досліджувати обидва шляхи він дослідить
827. 35:29цей вузол потім цей потім цей потім цей
828. 35:31і так далі І коли дійде до точки
829. 35:34прийняття рішення замість того щоб
830. 35:36вибрати ліворуч чи праворуч досліджувати
831. 35:39цей шлях він знову досліджуватиме обидва
832. 35:41переключаючись між ними буде
833. 35:43досліджувати тут Потім можливо тут і тут
834. 35:46і так далі І буде повільно пробиратися
835. 35:49ви це Бачите далі І далі Коли ми дійдемо
836. 35:51до цієї точки прийняття рішення будемо
837. 35:54досліджувати і вгору і вниз поки з
838. 35:56рештою не досягнемо цілі Ви помітите що
839. 36:00пошук у ширину справді знайшов шлях від
840. 36:03a до B ідучи конкретним шляхом Але для
841. 36:06цього потрібно було дослідити багато
842. 36:08станів тому ми бачимо певний компроміс
843. 36:11між ДФС і bfs у dfs можуть бути випадки
844. 36:15з економією пам'яті порівняно з підходом
845. 36:18спершу в ширину де в цьому випадку пошук
846. 36:20у ширину має досліджувати багато станів
847. 36:23Але можливо так буде не завжди тепер
848. 36:27звернімо увагу на код подивімося на код
849. 36:30який ми могли б написати щоб реалізувати
850. 36:32Щось на кшталт пошуку в глибину або
851. 36:34пошуку в ширину в контексті проходження
852. 36:38лабіринту я За терміналом
853. 36:41у.pie подано реалізацію тієї самої ідеї
854. 36:45проходження
855. 36:46лабіринту я визначив клас під назвою
856. 36:49node Який у цьому випадку відстежую стан
857. 36:52батьківський стан тобто стан перед
858. 36:54станом і дію тут ми не відстежуємо
859. 36:58вартість шляху Оскільки ми можемо
860. 36:59обчислити вартість шляху після того як
861. 37:02знайдемо шлях від початкового стану до
862. 37:04цілі на додачу до цього я визначив клас
863. 37:07під назвою stack fronteer якщо ви не
864. 37:10знайомі з класами то використання класів
865. 37:12- це спосіб створення об'єктів у пайthні
866. 37:15це має пряме відношення до
867. 37:17об'єктноорієнтованого програмування де
868. 37:19ідея полягає в тому що створюється
869. 37:21об'єкт у якому зберігаються всі дані
870. 37:24межі до складу об'єкта входять функції
871. 37:28інша назва методи які можна
872. 37:30використовувати для маніпулювання
873. 37:32об'єктом я прокоментую код якщо ви не
874. 37:35знайомі з синтаксисом спочатку йде
875. 37:37функція яка створює об'єкт frontteer
876. 37:40тобто межу дані в якому будуть подані у
877. 37:43вигляді списку спочатку межа
878. 37:45представлена порожнім списком у межі
879. 37:47нічого немає у мене є функція Add яка
880. 37:50додає щось до межі додаючи це в кінець
881. 37:52списку є функція яка перевіряє чи
882. 37:55містить межа певни стан у мене є порожня
883. 37:58функція яка перевіряє чи межа порожня
884. 38:00якщо межа порожня це означає що довжина
885. 38:03межі дорівнює нулю ще в мене є функція
886. 38:05видалення чогось із межі я не можу
887. 38:08нічого видалити з межі якщо межа порожня
888. 38:10тому я спочатку перевіряю це але в
889. 38:12іншому випадку якщо межа не порожня
890. 38:14пам'ятайте що я реалізую цю межу як стек
891. 38:18структуру даних останнім прийшов першим
892. 38:20вийшов це означає що останнім що Я додаю
893. 38:23до межі інакше кажучи останнім у списку
894. 38:26є при Мет який я маю видалити з межі ви
895. 38:30побачите що я видалив останній пункт зі
896. 38:32списку якщо ви введете індекс -1 у
897. 38:36список пайthна Ви отримаєте останній
898. 38:38елемент у списку оскільки нуль - це
899. 38:40перший елемент індекс -ну1 переходить до
900. 38:42останнього елемента у
901. 38:44списку це noe вузл оновлюємо frontр тут
902. 38:49у рядку номер 28 Щоби сказати Видаліть
903. 38:52вузол який ви щойно видалили з межі і
904. 38:55повертаємо E я результат цей клас
905. 38:57ефективно реалізує ідею межі це дає мені
906. 39:00спосіб додати щось до межі та спосіб
907. 39:03видаілити щось із межі як
908. 39:06стеку Також я реалізував альтернативну
909. 39:09версію того що називається
910. 39:12qfronteer цей клас який ви бачите в
911. 39:15дужках успадкований від steк frontр
912. 39:17тобто він виконуватиме ті самі дії що і
913. 39:20к fronter за винятком того що спосіб
914. 39:23видалення вузла з межі буде дещо іншим
915. 39:26замість видалення з кінця списку як це
916. 39:28було б у стеку Ми видалимо спочатку
917. 39:31списку
918. 39:32self.fronteer0 дасть мені перший доданий
919. 39:35вузол на межі Саме цей ми повернемо у
920. 39:38випадку черги
921. 39:40Q Тут у мене визначення класу mazee він
922. 39:44впорається із процесом взяття
923. 39:46послідовності текстового файлу схожого
924. 39:49на лабіринт і з'ясування як його пройти
925. 39:53візьмемо за вхідні дані текстовий файл
926. 39:55maze1
927. 39:57txt тут є решітки які представляють
928. 39:59стіни літера a що представляє початкову
929. 40:02позицію і Літера B що представляє
930. 40:04кінцеву позицію ви можете переглянути
931. 40:07код для аналізу цього текстового файлу
932. 40:09це не так цікаво більш цікава тут
933. 40:12функція solve яка з'ясовує як дістатися
934. 40:15з точки
935. 40:16A до точки B тут ми бачимо реалізацію
936. 40:21тієї самої ідеї яку бачили мить тому ми
937. 40:24будемо стежити за тим скільки станів ми
938. 40:27дослідили щоб повідомити ці дані пізніше
939. 40:29але я починаю з вузла який представляє
940. 40:32початковий стан Я починаю з межі у цьому
941. 40:35випадку стек frнр Враховуючи те що я
942. 40:37розглядаю межу Як стек ви можете уявити
943. 40:40що алгоритм який я тут використовую є
944. 40:43пошуком у глибину оскільки він
945. 40:44використовує стек як структуру
946. 40:48даних спочатку ця межа міститиме
947. 40:51початковий
948. 40:53стан ми ініціалізуємо expр який спочатку
949. 40:57порожній ми нічого не досліджували і ось
950. 41:01наш цикл це поняття повторення чогось
951. 41:04Спочатку ми перевіряємо чи межа порожня
952. 41:07викликаючи функцію empt реалізацію якої
953. 41:10ми бачили хвилину тому якщо межа справді
954. 41:12порожня ми підемо далі та викличемо
955. 41:15виняток або помилку пайтона щоб сказати
956. 41:18Вибачте рішення немає інакше ми видалимо
957. 41:22вузол з межі наприклад викликавши
958. 41:24fronterкра remove та оновивши кількість
959. 41:27станів які ми дослідили Оскільки ми
960. 41:29дослідили один додатковий стан кажемо що
961. 41:32selfкраn explored + дорівнює одиниця
962. 41:36додає одиницю до кількості досліджених
963. 41:38станів після того як ми видалимо вузол з
964. 41:40межі наступним кроком буде перевірка чи
965. 41:43досягли ми цілі тобто перевірка цілі у
966. 41:46випадку з лабіринтом ціль проста Я
967. 41:48перевіряю чи стан вузла відповідає цілі
968. 41:51Спочатку коли я налаштував Лабіринт я
969. 41:53встановлював це значення під назвою goл
970. 41:56ціль яке є властивістю лабіринту щоби
971. 41:59перевірити чи справді вузол є ціллю якщо
972. 42:02це ціль тоді я хочу повернутися назад і
973. 42:05з'ясувати які дії Я виконав для
974. 42:08досягнення цілі Як це зробити Ми
975. 42:10пам'ятаємо що кожен вузол зберігає свого
976. 42:13батька вузол який був перед ним і який
977. 42:15ми використовували щоб дістатися до
978. 42:18цього вузла а також дію використану для
979. 42:21того щоб туди потрапити Тож я можу
980. 42:23створити цикл в якому постійно
981. 42:25переглядаю батька кожного вузла
982. 42:27відстежую всіх батьків і які дії я
983. 42:30зробив щоб дістатися від батька до
984. 42:32поточного вузла Таким чином цикл буде
985. 42:34повторювати процес перегляду всіх
986. 42:36батьківських вузлів доки ми не
987. 42:38повернемося до початкового стану який
988. 42:40немає батька
989. 42:42деноdeкраpent дорівнюватиме NAN роблячи
990. 42:45це я буду створювати список усіх дій які
991. 42:48я виконую і список усіх комірок які є
992. 42:50частиною розв'язку але робитиму це у
993. 42:53зворотньому порядку Бо коли я роблю це
994. 42:55повертаючись від цілі до початкового
995. 42:58стану я будую послідовність дій від цілі
996. 43:00до початкового стану проте я хочу
997. 43:02змінити порядок на зворотні щоб отримати
998. 43:05послідовність дій від початкового стану
999. 43:07до цілі це і буде розв'язком це все
1000. 43:09можливо якщо Поточний стан відповідає
1001. 43:11цілі інакше Якщо це не ціль тоді я додам
1002. 43:15цей стан до дослідженого набору Щоби
1003. 43:17сказати що я дослідив цей стан і не
1004. 43:19треба повертатися до нього якщо я
1005. 43:21натраплю на нього в майбутньому логіка
1006. 43:23тут реалізує ідею додавання сусідів до
1007. 43:26межі Подивіться на всіх сусідів я
1008. 43:28реалізував функцію під назвою neighbor
1009. 43:30для кожного сусіда Я перевіряю чи стан
1010. 43:32уже на межі чи стан уже в дослідженому
1011. 43:35наборі Якщо його немає ні там ні там
1012. 43:37тоді я додам новий дочірній вузол до
1013. 43:40межі ви бачите чимало синтаксису але
1014. 43:42головне не в тому щоб розуміти всі його
1015. 43:45нюанси Хоча не соромтеся придивитися до
1016. 43:47цього файлу самостійно щоби зрозуміти як
1017. 43:50він працює головне побачити як це
1018. 43:52реалізує той самий псевдокод ту саму
1019. 43:55ідею яку ми описали хвилину тому на
1020. 43:57екрані коли розглядали кроки які ми
1021. 43:59могли б виконати щоб вирішити завдання
1022. 44:02пошуку тепер подивімося на це в дії я
1023. 44:04запущу maze.p на Maze
1024. 44:081txt ми побачимо який вигляд мав
1025. 44:11Лабіринт спочатку А внизу Лабіринт після
1026. 44:13розв'язку завдання для цього нам
1027. 44:15потрібно було дослідити 11 станів і ми
1028. 44:19знайшли шлях від a до
1029. 44:21B у цій програмі Я також згенерував
1030. 44:24графічне подання я відкрию файл Maze png
1031. 44:28що створюється цією програмою Він
1032. 44:30показує що темний колір - це стіна
1033. 44:32червоний- початковий стан зелений ціль
1034. 44:35жовтий шлях ми знайшли шлях від
1035. 44:38початкового стану до
1036. 44:40цілі тепер подивімося на складніший
1037. 44:42Лабіринт щоб побачити що може
1038. 44:45статися я відкрию файл Maze
1039. 44:472txt Як бачите це значно більший
1040. 44:50Лабіринт Ми намагаємося знайти шлях з
1041. 44:53пункту a у пункт B але тепер ви знаєте
1042. 44:56що пошук у глибину може не досягти цілі
1043. 44:59з першої спроби можливо доведеться йти
1044. 45:01одним шляхом потім повертатися і
1045. 45:03досліджувати щось інше спробуємо
1046. 45:07запустимо python ma.p Maze 2txt цього
1047. 45:11разу інший лабіринт і тепер пошук у
1048. 45:14глибину може знайти розв'язок зірочками
1049. 45:17вказано шлях від a до B і ми можемо це
1050. 45:20побачити відкривши
1051. 45:22Лабіринт ось такий він жовтим кольором
1052. 45:25ділено шлях від початкового стану до
1053. 45:28цілі але скільки станів ми маємо
1054. 45:30дослідити перш ніж знайти цей
1055. 45:34шлях Пригадайте що у програмі я
1056. 45:37відстежував кількість станів які ми
1057. 45:39дослідили на цей момент повертаюся до
1058. 45:41термінала щоб вирішити це завдання нам
1059. 45:44довелося дослідити 399 різних
1060. 45:49станів якщо я вношу одну невелику
1061. 45:51модифікацію в програму та повідомляю
1062. 45:54програмі в кінці коли ми виводи димо
1063. 45:56зображення Я додаю аргумент під назвою
1064. 45:59Show explor Я встановлюю Show explor як
1065. 46:02такий що дорівнює тру і повторно запущу
1066. 46:05програму pythonmaz.pie і Maze 2 потім
1067. 46:08відкрию лабіринт і ви побачите що
1068. 46:10червоним виділені всі стани які мали
1069. 46:13бути досліджені щоби дістатися від
1070. 46:15початкового стану до цілі пошук у
1071. 46:17глибину або dfs не відразу знайшов шлях
1072. 46:20до цілі Він вирішив спочатку дослідити
1073. 46:22цей напрямок і коли він його досліджував
1074. 46:25йому довелось пройти всі можливі шляхи
1075. 46:27аж до самого кінця навіть цей довгий і
1076. 46:30звивестий щоб усвідомити що це глухий
1077. 46:33кут і програмі довелося повернутися
1078. 46:35потім піти в цьому напрямку тут
1079. 46:37пощастило що не вибрав цей шлях але не
1080. 46:40пощастило тут Під час дослідження цього
1081. 46:42напрямку дослідження купи непотрібних
1082. 46:45станів і потім Аналогічно Під час
1083. 46:47дослідження всієї цієї верхньої частини
1084. 46:49чого взагалі не потрібно було робити
1085. 46:52Отже загалом пошук у глибину насправді
1086. 46:54не працює оптимально він досліджує
1087. 46:56більше станів ніж потрібно він знаходить
1088. 46:59оптимальне рішення найкращий шлях до
1089. 47:01цілі але кількість станів які довелося
1090. 47:03дослідити до цього кількість кроків які
1091. 47:06довелося зробити була набагато більшою
1092. 47:09порівняємо як пошук у ширину або bfs
1093. 47:12працював би в цьому лабіринті щоби це
1094. 47:14зробити достатньо внести невелику зміну
1095. 47:16алгоритм для dfs і bfs однаковий за
1096. 47:19винятком того яку структуру даних ми
1097. 47:22використовуємо для представлення межі у
1098. 47:25dfs використовував Ек fronteer останнім
1099. 47:28прийшов першим вийшов тоді як у bfs я
1100. 47:31використаю Q fronteer першим прийшов
1101. 47:34першим вийшов те що я першим додам до
1102. 47:37межі я першим і видалю повернусь до
1103. 47:41термінала повторно запущу програму в
1104. 47:43тому самому лабіринті і тепер ви
1105. 47:45побачите що кількість станів які
1106. 47:47потрібно було дослідити лише 77 а під
1107. 47:50час пошуку в глибину було досліджено
1108. 47:52майже 400 і ми бачимо чому ми бачимо що
1109. 47:55сталось відкриваємо Ma png і поглянемо
1110. 47:59жовтим виділено розв'язок який було
1111. 48:01знайдено пошуком у ширину це до речі той
1112. 48:04самий розв'язок який було знайдено
1113. 48:05пошуком у глибину вони обидва знаходять
1114. 48:08найкращий розв'язок але бачите білі
1115. 48:11недосліджені клітини щоб знайти шлях до
1116. 48:14цілі пошуку в ширину довелося дослідити
1117. 48:16набагато менше станів пошиук у ширину
1118. 48:18працює Трохи поверхневіше він досліджує
1119. 48:21вузли близькі до початкового стану без
1120. 48:23дослідження того що розташова надалі
1121. 48:26Отже якщо ціль не дуже далеко пошуку
1122. 48:29ширини може діяти досить ефективно в
1123. 48:31подібному
1124. 48:33лабіринті у цьому випадку і bfs і dfs
1125. 48:37знайшли однаковий розв'язок але так
1126. 48:39буває не завжди погляньмо на ще один
1127. 48:42приклад
1128. 48:443
1129. 48:46txt у May 3 txt Зверніть увагу що тут є
1130. 48:50кілька шляхів якими ви можете дістатися
1131. 48:53від a до B це відносно на великий
1132. 48:56Лабіринт якщо я вимкну Show explor щоб
1133. 49:00ми побачили тільки розв'язок Я
1134. 49:02використовую bfs пошук у ширину щоби
1135. 49:06вирішити May
1136. 49:073xt ми знайшли розв'язок Я відкриваю
1137. 49:11Лабіринт ось наш розв'язок він
1138. 49:13оптимальний лише за Чотири кроки ми
1139. 49:16можемо дійти від початкового стану до
1140. 49:20цілі але що станеться якщо замість цього
1141. 49:23ми спробуємо використати пошук у глибину
1142. 49:26або dfs знову ж таки я повернувся до Q
1143. 49:29fronteer що означає використання пошуку
1144. 49:32в ширину зміню його на stack fronteer
1145. 49:34тобто тепер ми будемо використовувати
1146. 49:36пошук у
1147. 49:38глибину запускаю
1148. 49:41pythonm.p Тепер ви побачите що ми
1149. 49:43знаходимо розв'язок але він не
1150. 49:46оптимальний це те що знаходить наш
1151. 49:48алгоритм можливо пошук у глибину знайшов
1152. 49:51би цей розв'язок Можливо але не
1153. 49:53гарантовано що якщо нам просто не
1154. 49:55пощастить якщо ми виберемо цей стан
1155. 49:58замість того стану То пошук у глибину
1156. 50:00може знайти довший шлях щоб дістатися
1157. 50:02від початкового стану до цілі ми бачимо
1158. 50:06певні компроміси коли пошук у глибину
1159. 50:08може не знайти оптимального розв'язку На
1160. 50:11цьому етапі здається що пошук у ширину
1161. 50:13це досить добре чи це найкраще що ми
1162. 50:15можемо зробити якщо він знайде
1163. 50:17оптимальний розв'язок нам Не доведеться
1164. 50:19турбуватися про ситуацію коли ми можемо
1165. 50:21знайти довший шлях до розв'язку ніж той
1166. 50:24який насправді існує
1167. 50:26там де ціль далеко від початкового стану
1168. 50:28і потрібно зробити багато кроків щоб
1169. 50:30дістатися від початкового стану до цілі
1170. 50:32алгоритм bfс дослідив майже весь графік
1171. 50:35пройшов майже весь Лабіринт щоби знайти
1172. 50:37шлях від початкового стану до цілі Ми би
1173. 50:41хотіли щоб алгоритм був розумнішим але
1174. 50:44що в цьому випадку означає розумніший
1175. 50:46алгоритм погляньмо де пошук у ширину міг
1176. 50:49би прийняти інше рішення та врахуємо
1177. 50:51також людську інтуїцію в цьому процесі
1178. 50:55на на приклад що такого іншого може
1179. 50:58зробити людина проходячи Лабіринт
1180. 51:01порівняно з діями які б вирішив зробити
1181. 51:07bfs Перше рішення яке bfs прийняв було б
1182. 51:11тут коли він зробив п'ять кроків і
1183. 51:13опинився на розвилці він може піти
1184. 51:16ліворуч або праворуч у перших кількох
1185. 51:19кроках не було вибору з кожного цього
1186. 51:22стану можна було виконати лише одну дію
1187. 51:25тому алгоритм пошуку зробив єдине що міг
1188. 51:27зробити будь-який алгоритм пошуку
1189. 51:29продовжив переходи з одного стану в
1190. 51:32інший але ця точка прийняття рішення вже
1191. 51:35цікавіша пошук у глибину той самий
1192. 51:38перший алгоритм пошуку який ми
1193. 51:40розглядали вирішив сказати виберемо один
1194. 51:43шлях і пройдемо його до кінця перевіримо
1195. 51:46чи має який-небудь цей шлях ціль А якщо
1196. 51:49ні то спробуємо інший шлях пошук у
1197. 51:52ширину використовував альтернативний
1198. 51:54підхід спочатку досліди предмети які
1199. 51:56ближчі які поблизу Він дивився ліворуч і
1200. 51:59праворуч знову ліворуч і праворуч
1201. 52:01чергуючи варіанти в Надії знайти щось
1202. 52:03поблизу А що може зробити людина
1203. 52:06Опинившись у подібній ситуації йти
1204. 52:08ліворуч або праворуч людина може
1205. 52:10візуально побачити що вона намагається
1206. 52:12дістатися до стану бій який високо там і
1207. 52:16поворот праворуч здається ближчим до
1208. 52:18цілі рух праворуч має бути кращим ніж
1209. 52:20ліворуч тому що так швидше дістатися до
1210. 52:23цілі я зроблю кілька щень я роблю
1211. 52:26припущення що ми можемо представити цю
1212. 52:28сітку як двовимірну сітку де я знаю
1213. 52:31координати всього a має координати 00 B
1214. 52:35якісь інші координати і я знаю На яких
1215. 52:38координатах я зараз я можу розрахувати
1216. 52:42що йти сюди це ближче до цілі але це
1217. 52:45може бути розумним припущенням лише для
1218. 52:48деяких завдань пошуку поки що Припустимо
1219. 52:51що я знаю свої поточні координати і знаю
1220. 52:54координати ці цілі до якої намагаються
1221. 52:56дістатися у цій ситуації Я хотів би щоб
1222. 52:59алгоритм був розумнішим і знав що я
1223. 53:02повинен просуватися до цілі а проходити
1224. 53:05Лабіринт знаючи координати цілі це
1225. 53:08зазвичай чудовий спосіб Хоча і не завжди
1226. 53:11Тому тут ми встановлюємо відмінність між
1227. 53:14двома різними типами алгоритмів пошуку
1228. 53:17неінформованим пошуком та інформованим
1229. 53:22пошуком алгоритми неінформованого пошуку
1230. 53:25це такі алгоритми як dfs і bfs це
1231. 53:28стратегії пошуку які не використовують
1232. 53:31жодних специфічних знань для розв'язку
1233. 53:34завдання dfs і bfs було байдуже до
1234. 53:37структури лабіринту чи до нього самого
1235. 53:40як такого вони просто дивляться на
1236. 53:42доступні дії та вибирають зпоміж них і
1237. 53:45немає значення Чи це Лабіринт чи інша
1238. 53:48проблема розв'язок або спосіб яким
1239. 53:51намагаються вирішити проблему буде
1240. 53:53однаковим за Зараз ми розглянемо
1241. 53:56вдосконалений варіант неінформованого
1242. 53:58пошуку ми розглянемо інформований пошук
1243. 54:01інформований пошук - це стратегії пошуку
1244. 54:04які використовують знання специфічні для
1245. 54:06завдання щоби знайти кращий розв'язок у
1246. 54:10випадку з лабіринтом конкретне знання
1247. 54:12про завдання схоже на щось таке якщо я
1248. 54:14збираюся побудувати квадрат географічно
1249. 54:17ближче до цілі це краще ніж перебувати в
1250. 54:20квадраті який географічно далі І це те
1251. 54:23що ми можемо дізнатися ше поміркувавши
1252. 54:26над цією проблемою та міркуючи про те
1253. 54:28які знання можуть бути корисними для
1254. 54:31нашого агента зі штучним інтелектом
1255. 54:33Існує кілька різних типів інформованого
1256. 54:36пошуку по-перше ми розглянемо певний тип
1257. 54:39алгоритму пошуку який називається
1258. 54:41евристичним пошуком за першим найкращим
1259. 54:43збігом евристичний пошук або gbfs - це
1260. 54:47алгоритм пошуку який замість розширення
1261. 54:50найглибшого вузла як dfs або найближчого
1262. 54:53вузла як bfs за завжди розширює вузол
1263. 54:56який На його думку є найближчим до
1264. 54:59цілі алгоритм пошуку не знатиме напевно
1265. 55:02Чи це ближче до цілі бо Якби ми знали що
1266. 55:05ближче до цілі то вже мали б рішення
1267. 55:09знаючи що ближче до цілі Ми би просто
1268. 55:12пішли від початкової позиції до
1269. 55:15рішення Але якщо ми не знаємо рішення
1270. 55:17тобто не знаємо точно що ближче до цілі
1271. 55:21можемо оцінити те що ближче до цілі
1272. 55:24інакше це відомо як евристика спосіб
1273. 55:27оцінити ближче ми до цілі чи ні Ми
1274. 55:30зробимо це за допомогою евристичної
1275. 55:32функції яку стандартно називають H відn
1276. 55:35Вона приймає стан вхідних даних і
1277. 55:38повертає оцінку того наскільки ми
1278. 55:40близькі до цілі якою ж може бути
1279. 55:42евристична функція для алгоритму
1280. 55:45проходження лабіринту Отже ми проходимо
1281. 55:47алгоритм якою буде евристика Вона має
1282. 55:50відповісти на запитання яка клітинка
1283. 55:52краща C чи D якій із них я б віддав
1284. 55:56перевагу шукаючи шлях до
1285. 55:59цілі людина поглянула б і сказала знаєте
1286. 56:03ді здається
1287. 56:05краще навіть якщо лабіринт заплутаний і
1288. 56:08ви не подумали про всі стіни ді напевне
1289. 56:11краще але чому Бо якщо не зважати на
1290. 56:14стіни удамо на мить що стін не існує
1291. 56:17полегшимо собі завдання так би мовити
1292. 56:19так от дій якщо взяти до уваги
1293. 56:21координати ближче до цілі від клітини
1294. 56:24дій до цілі значно менше кроків
1295. 56:26порівняно із с навіть якщо ігнорувати
1296. 56:28стіни якщо ви знаєте координати XY точки
1297. 56:32С і координати XY цілі а також знаєте
1298. 56:35координати XY точки D ви можете
1299. 56:37обчислити що ді просто географічно без
1300. 56:40урахування стін краща Ми збираємося
1301. 56:43використовувати евристичну функцію яка
1302. 56:45називається манхетенська відстань це
1303. 56:48конкретний тип евристики де евристика -
1304. 56:50це кількість квадратів по вертикалі та
1305. 56:52горизонталі ліворуч або правоч поруч не
1306. 56:55можна йти по діагоналі тобто тільки
1307. 56:57вгору тільки вправо тільки вліво тільки
1308. 57:00вниз скільки кроків треба зробити щоби
1309. 57:02дійти до цілі від кожної клітинки
1310. 57:05виявилося що ді набагато ближча кроків
1311. 57:08менше Потрібно зробити лише шість кроків
1312. 57:10щоби досягти цілі знову ж таки ігноруємо
1313. 57:13стіни ми полегшили собі завдання нас
1314. 57:16хвилює лише оцінка того наскільки ми
1315. 57:18далеко це можна обчислити віднявши
1316. 57:20значення одне від одного і значення y
1317. 57:23одне від одного і ми можемо оцінити що
1318. 57:25dі ближче до цілі ніж с тепер у нас є
1319. 57:28підхід є спосіб вибрати Який вузол
1320. 57:30видалити з межі на кожному етапі
1321. 57:33алгоритму ми будемо видаляти вузол із
1322. 57:35межі ми будемо досліджувати вузол якщо
1323. 57:37він має найменше значення для цієї
1324. 57:39евристичної функції якщо він має
1325. 57:41найменшу манхетенську відстань до цілі
1326. 57:45Як це працює на практиці я спершу
1327. 57:47позначу Лабіринт числами які
1328. 57:49представляють значення евристичної
1329. 57:50функції значення манхетенської відстані
1330. 57:53від будь-якої з цих клітинок
1331. 57:55відстань від цієї клітинки до цілі один
1332. 57:58крок від цієї два кроки
1333. 58:00тричотири тут п'ять кроків одна клітинка
1334. 58:03праворуч і чотири вгору звідси
1335. 58:06манхетенська відстань дорівнює двом
1336. 58:09крокам географічно ми лише за два
1337. 58:11квадрати від цілі хоча в реальності
1338. 58:14доведеться йти довшим шляхом але ми ще
1339. 58:16не знаємо цього евристика - це простий
1340. 58:19спосіб оцінити наскільки ми далеко від
1341. 58:21цілі може наша евристика надто
1342. 58:23оптомістична вона вважає що ми За два
1343. 58:26кроки від цілі тоді як У реальності якщо
1344. 58:28взяти до уваги стіни їх може бути більше
1345. 58:31важливо те що евристика не гарантує
1346. 58:34скільки кроків буде зроблено
1347. 58:37це оцінка це спроба наближення і справді
1348. 58:41здається що квадрати які ніби ближче до
1349. 58:43цілі мають менш значення для евристичної
1350. 58:46функції ніж квадрати розташовані
1351. 58:50далі Отже що може зробити цей алгоритм
1352. 58:53використовуючи чний пошук знову ж таки
1353. 58:56для цих перших п'яти кроків немає
1354. 58:58особливого вибору починаємо з
1355. 59:00початкового стану a досліджуємо п'ять
1356. 59:03станів і тепер точка прийняття рішення
1357. 59:06треба вибрати куди йти ліворуч чи
1358. 59:08праворуч раніше dfs і bfs вибирали
1359. 59:11довільно бо це залежало від того в якому
1360. 59:14порядку ви розміщуєте два вузли на межі
1361. 59:16ми не вказували в якому порядку
1362. 59:18розміщувати лише порядок в якому
1363. 59:20видаляти тут ми можемо подивитися на 13
1364. 59:23і 11 сказати що цей квадрат розташований
1365. 59:27на відстані 11 кроків від цілі згідно з
1366. 59:29нашою евристикою А цей за нашою оцінкою
1367. 59:32на відстані 13
1368. 59:34кроків Отже між цими двома варіантами я
1369. 59:37би радше обрав 11 я волію бути за 11
1370. 59:41кроків від цілі тому піду праворуч ми
1371. 59:44можемо прийняти обґрунтоване рішення
1372. 59:46оскільки знаємо дещо Більше про це
1373. 59:48завдання йдемо далі 10 9 8 і ми між
1374. 59:53двома сімками ми не можемо дізнатися
1375. 59:55нічого конкретного тому вибираємо
1376. 59:57довільно Можливо ми оеремо неправильно
1377. 1:00:00Але це не страшно далі ми можемо вибрати
1378. 1:00:03цю Сімку Ідемо
1379. 1:00:05СШ робимо цей вибір навіть якщо він
1380. 1:00:08збільшує значення евристичної функції
1381. 1:00:10але тепер ми маємо іншу точку прийняття
1382. 1:00:12рішення між шісткою і вісімкою згадаємо
1383. 1:00:1513 але вона набагато вища між шісткою
1384. 1:00:19вісімкою і 13кою шість має найменше
1385. 1:00:22значення тому ми радше оберемо її ми
1386. 1:00:25можемо прийняти обґрунтоване рішення що
1387. 1:00:27рухатися праворуч краще ніж униз Ідемо
1388. 1:00:30сюди п'ять знову точка прийняття рішення
1389. 1:00:34ми Приймаємо рішення яке можливо і не
1390. 1:00:36хочемо приймати але немає способу його
1391. 1:00:38обійти бачимо четвірку і шістку четвірка
1392. 1:00:41ближче до цілі Вона веде вгору а ціль
1393. 1:00:44угорі і вибираємо Шлях який зрештою
1394. 1:00:46приводить нас у глухий кут але це
1395. 1:00:49нормально бо ми можемо спробувати шістку
1396. 1:00:51і підемо цим шляхом який зрештою приведе
1397. 1:00:53нас до цілі
1398. 1:00:55Ось як евристичний пошук може підійти до
1399. 1:00:58цієї проблеми Коли у нас є вибір між
1400. 1:01:00кількома вузлами які ми можемо дослідити
1401. 1:01:03ми дослідимо вузол який має найменше
1402. 1:01:05значення H від N евристичної функції яка
1403. 1:01:09оцінює як далеко я маю
1404. 1:01:12пройти так сталося що в цьому випадку ми
1405. 1:01:15маємо кращу кількість досліджених станів
1406. 1:01:17порівняно із bfs bfs дослідив би всю цю
1407. 1:01:21ділянку і всю цю ділянку але ми змогли
1408. 1:01:24уникнути цього скориставшись евристикою
1409. 1:01:27знанням про те наскільки ми близькі до
1410. 1:01:29цілі або про оцінку цієї
1411. 1:01:33ідеї це явно краще То може завжди
1412. 1:01:37вибиратимемо цей алгоритм а не наприклад
1413. 1:01:39пошук у ширину можливо однак слід узяти
1414. 1:01:42до уваги те що нам потрібно придумати
1415. 1:01:45хорошу евристику наскільки хороша
1416. 1:01:47евристика настільки хороший алгоритм
1417. 1:01:49проте розробити хорошу евристику не так
1418. 1:01:52і
1419. 1:01:53легко начим м ще варто подумати як і у
1420. 1:01:56випадку з попередніми двома алгоритмами
1421. 1:01:58чи цей алгоритм оптимальний чи завжди
1422. 1:02:01він знайде найкоротший шлях від
1423. 1:02:03початкового стану до
1424. 1:02:05цілі щоби відповісти на це питання на
1425. 1:02:08мить поглянемо на цей приклад Ми
1426. 1:02:10намагаємося дістатися від a до B Я
1427. 1:02:13позначив кожну клітинку манхетенською
1428. 1:02:16відстанню від цілі тобто кількістю
1429. 1:02:18квадратів угору і праворуч які вам
1430. 1:02:20потрібно пройти щоби дістатися від цього
1431. 1:02:23квадрата до цілі
1432. 1:02:24подумаємо чи жадібний пошук який завжди
1433. 1:02:28вибирає найменше число знайде оптимальне
1434. 1:02:32рішення яке найкоротше рішення і чи
1435. 1:02:35знайде його цей алгоритм важливо
1436. 1:02:38розуміти що тут точка прийняття
1437. 1:02:41рішення за нашою оцінкою ми за 12 кроків
1438. 1:02:45від цілі У нас є два вибори можемо піти
1439. 1:02:49ліворуч і будемо на відстані 13 кроків
1440. 1:02:51від цілі або вгору 11 кроків від цілі
1441. 1:02:54розглянувши Ці дві позиції жадібний
1442. 1:02:57пошук скаже що 11 краще за 13 Таким
1443. 1:03:01чином жадібний пошук знайде отакий шлях
1444. 1:03:04до
1445. 1:03:06цілі та виявляється що цей шлях не
1446. 1:03:09оптимальний є спосіб дістатися до цілі
1447. 1:03:12за меншу кількість кроків цей шлях
1448. 1:03:15складався з меншої кількості кроків хоча
1449. 1:03:18в цій точці прийняття рішення довелося
1450. 1:03:20вибрати гірший варіант із двох або те що
1451. 1:03:23ми оцінили як гірший варіант базуючись
1452. 1:03:26на евристиці ось що маємо на увазі під
1453. 1:03:29жадібним алгоритмом це найкраще рішення
1454. 1:03:31локально на цьому етапі прийняття
1455. 1:03:34рішення здається що краще перейти сюди
1456. 1:03:36ніж до
1457. 1:03:3713 але загалом це не обов'язково
1458. 1:03:40оптимальне алгоритм може знайти рішення
1459. 1:03:43однак може існувати і краще рішення
1460. 1:03:45треба якось знайти рішення нам
1461. 1:03:47подобається ідея евристики тобто
1462. 1:03:49можливість оцінити шлях відстань між
1463. 1:03:52нами та ціллю це допомагає прийняти
1464. 1:03:54краще рішення і уникнути перегляду
1465. 1:03:56всього простору станів але ми хотіли би
1466. 1:03:59змінити алгоритм щоби досягнути
1467. 1:04:01оптимальності щоби він був
1468. 1:04:04оптимальним як це зробити до чого тут
1469. 1:04:07інтуїція погляньмо на це
1470. 1:04:11завдання у цьому лабіринті евристичний
1471. 1:04:14пошук знайшов рішення отакий довгий шлях
1472. 1:04:18чому це неоптимальне рішення так з першу
1473. 1:04:21числа евристики дійшли до дуже низького
1474. 1:04:23значення але потім почали зростати 8 9
1475. 1:04:2710 11 аж до 12 у цьому випадку як ми
1476. 1:04:30можемо вдосконалити цей алгоритм ми
1477. 1:04:33розуміємо що якщо проходити весь
1478. 1:04:35алгоритм цим шляхом ми зрештою дійдемо
1479. 1:04:38до 12ти доведеться зробити от стільки
1480. 1:04:41кроків ніхто не знає скільки точно
1481. 1:04:43кроків просто щоб дістатися до 12 але
1482. 1:04:47натомість як альтернатива ми могли би
1483. 1:04:49зробити набагато менши кроків лише шість
1484. 1:04:52і опинитися на 13ти Так 13 більше за 12
1485. 1:04:56здається що це погано Проте це шлях із
1486. 1:04:59меншою кількістю кроків лише шість
1487. 1:05:01кроків щоби дістатися до 13 і набагато
1488. 1:05:04більше щоби дістатися до 12 і хоча
1489. 1:05:07жадібний пошук каже 12 краще ніж 13
1490. 1:05:10вибере 12 ми можемо діяти розумніше
1491. 1:05:13краще я буду там де евристично здається
1492. 1:05:16що потрібно більше часу проте можна
1493. 1:05:19дістатися туди набагато швидше Ми
1494. 1:05:21збираємося закодувати цю загальну ідею в
1495. 1:05:24формальний алгоритм відомий як пошук
1496. 1:05:26езірочка Він вирішить це завдання не
1497. 1:05:29просто розглядаючи евристику а також
1498. 1:05:31враховуючи Скільки часу знадобилося нам
1499. 1:05:34щоби дістатися до будь-якого конкретного
1500. 1:05:37стану відмінність у тому що при
1501. 1:05:39евристичному пошуку в будь-якому стані
1502. 1:05:41Мене хвилює лише оціночна відстань
1503. 1:05:43евристична цінність між мною та ціллю
1504. 1:05:47пошук езірочка враховуватиме дві частини
1505. 1:05:50інформації буде взято до уваги те як
1506. 1:05:53далеко я цілі а також як далеко Мені
1507. 1:05:56довелося пройти щоби потрапити сюди бо
1508. 1:05:59це теж актуально Отже ми шукатимемо
1509. 1:06:02алгоритми розгортаючи вузол із найменшим
1510. 1:06:05значенням g відn + h віn h відn - це та
1511. 1:06:09сама евристика про яку ми вже говорили
1512. 1:06:12яка змінюватиметься залежно від завдання
1513. 1:06:14а gvdn - це вартість досягнення вузла
1514. 1:06:17Скільки кроків потрібно було зробити
1515. 1:06:19щоби досягти поточного
1516. 1:06:22стану як цей алгоритм пошуку працює в
1517. 1:06:25реальності подивімося Знову той самий
1518. 1:06:28лабіринт і знову я позначив манхетенську
1519. 1:06:31відстань це значення є значенням H від N
1520. 1:06:34евристичною оцінкою того наскільки кожен
1521. 1:06:36квадрат віддалений від
1522. 1:06:39цілі коли ми починаємо досліджувати
1523. 1:06:42стани нам важливе не лише евристичне
1524. 1:06:44значення а й gvdн кількість кроків які
1525. 1:06:47довелося зробити щоби потрапити туди
1526. 1:06:50Мені потрібна сума цих двох чисел Як це
1527. 1:06:52працює перший хід один крок оцінка Я за
1528. 1:06:5616 кроків від
1529. 1:06:59цілі загальне значення дорівнює
1530. 1:07:0217 роблю ще один крок Тепер я зробив два
1531. 1:07:06кроки оцінюю відстань від цілі у 15
1532. 1:07:08кроків знову ж таки загальне значення 17
1533. 1:07:11я зробив Три кроки оцінюю відстань від
1534. 1:07:14цілі у 14 кроків і так далі І так далі
1535. 1:07:17Чотири кроки оцінка 13 п'ять кроків
1536. 1:07:20оцінка 12 А ось тепер точка прийняття
1537. 1:07:22рішення я можу бути на відстані шести
1538. 1:07:25кроків від початку з евристикою 13 із
1539. 1:07:27загальною оцінкою 19 або я можу бути на
1540. 1:07:31відстані шести кроків від початку з
1541. 1:07:33евристикою 11 із загальною оцінкою 17
1542. 1:07:36між 19 і 17 я би вибрав 17 6 + 11 поки
1543. 1:07:41що нічим не відрізняється від того що ми
1544. 1:07:44бачили раніше ми вибираємо цей варіант
1545. 1:07:46оскільки він видається кращим Я
1546. 1:07:48продовжую йти цим шляхом але саме тут
1547. 1:07:51усе стає
1548. 1:07:52інакше тепер тепер я можу бути на
1549. 1:07:54відстані 15 кроків від початку із
1550. 1:07:57орієнтовною дистанцією 6 15 + 6 =
1551. 1:08:0221 як альтернатива я можу бути за шість
1552. 1:08:05кроків від початку це було п'ять кроків
1553. 1:08:07Отже цешість із загальним оціненим
1554. 1:08:10значенням 13 6 + 13 = 19 тут ми б
1555. 1:08:15оцінили g відn + h відn як 19 6 + 13
1556. 1:08:20тоді як тут ми б отримали 15 + 6 або 21
1557. 1:08:24інтуїція така 19 менше за 21 йдемо сюди
1558. 1:08:29але я волів би зробити менше кроків щоби
1559. 1:08:31дістатися до 13 ніж зробити 15 кроків і
1560. 1:08:35опинитися на шістці Оскільки тут
1561. 1:08:37доведеться зробити більше кроків можливо
1562. 1:08:40цей шлях
1563. 1:08:41кращий тому дослідимо його робимо ще
1564. 1:08:45один крок це 7+ 14 = 21 між цими двома
1565. 1:08:51ніби рівність ми все одно можемо слідити
1566. 1:08:54цей Але після цього коли евристичні
1567. 1:08:56значення цих чисел почнуть збільшуватися
1568. 1:08:59а ці евристичні значення почнуть
1569. 1:09:02зменшуватися ви побачите що ми фактично
1570. 1:09:04продовжимо досліджувати цей шлях Можете
1571. 1:09:07порахувати і побачити що в кожній точці
1572. 1:09:10прийняття рішення пошук е зірочка
1573. 1:09:12зробить вибір на основі Суми того
1574. 1:09:15скільки кроків мені знадобилося щоб
1575. 1:09:17дістатися до поточної позиції і як
1576. 1:09:19далеко я від цілі Отже хоча нам і
1577. 1:09:22довелося досліджувати деякі з цих станів
1578. 1:09:24остаточне рішення яке ми знайшли було по
1579. 1:09:26суті оптимальним таки знайшовся
1580. 1:09:28найшвидший спосіб дістатися від
1581. 1:09:30початкового стану до цілі Виявляється що
1582. 1:09:32пошук зірочка - це оптимальний алгоритм
1583. 1:09:35але за певних умов умови H вn моя
1584. 1:09:38евристика має бути
1585. 1:09:40прийнятною що означає прийнятність
1586. 1:09:42евристики евристика прийнятна якщо вона
1587. 1:09:45ніколи не переоцінює справжню вартість
1588. 1:09:48кожну подію завжди потрібно або точно
1589. 1:09:50визначити або її потрібно недооцінити ми
1590. 1:09:53бачили попередній приклад де евристичне
1591. 1:09:55значення було набагато меншим за
1592. 1:09:57фактичну вартість це нормально але
1593. 1:09:59ніколи не слід переоцінювати евристичні
1594. 1:10:03значення ніколи не слід думати що я далі
1595. 1:10:05від цілі ніж
1596. 1:10:07насправді щоби зробити твердження
1597. 1:10:10сильнішим H від N також має бути
1598. 1:10:13послідовною Що це означає математично це
1599. 1:10:16означає що для кожного вузла який ми
1600. 1:10:19називатимемо N І наступного вузла який я
1601. 1:10:22називатиму nш
1602. 1:10:24з вартістю кроку C евристичне значення N
1603. 1:10:27має бути меншим або дорівнювати
1604. 1:10:29евристичному значенню n' плюс вартість
1605. 1:10:33висловимо цю математичну формулу словами
1606. 1:10:35якщо я зараз у цьому стані евристичне
1607. 1:10:38значення від мене до цілі не має бути
1608. 1:10:40більшим ніж евристичне значення мого
1609. 1:10:43наступника наступного місця куди я міг
1610. 1:10:45би піти плюс вартість кроку таким чином
1611. 1:10:48це лише перевірка того що моя евристика
1612. 1:10:51відповідає всім крокам які я можу
1613. 1:10:53зробити поки це правда пошук езірочка
1614. 1:10:56знайде оптимальне рішення і Саме тут
1615. 1:10:58інколи може виникнути велика частина
1616. 1:11:00викликів у завданнях пошуку пошук
1617. 1:11:03езірочка - це відомий алгоритм і ви
1618. 1:11:06можете написати код досить легко а от
1619. 1:11:08вибір евристики може бути цікавим
1620. 1:11:10викликом що краще евристика то краще я
1621. 1:11:14зможу вирішити завдання і то менше
1622. 1:11:16станів мені доведеться
1623. 1:11:18досліджувати Мені потрібно переконатися
1624. 1:11:21що евристика задовольняє ці конкретні
1625. 1:11:26обмеження Отже це лише деякі приклади
1626. 1:11:28алгоритмів пошуку які можуть працювати
1627. 1:11:31їх звісно набагато більше наприклад
1628. 1:11:33пошук езірочка має тенденцію
1629. 1:11:35використовувати багато пам'яті тому
1630. 1:11:38існують альтернативні підходи які
1631. 1:11:40використовують менше пам'яті Ніж ця
1632. 1:11:42версія пошуку езірочка існують інші
1633. 1:11:45алгоритми пошуку оптимізовані для інших
1634. 1:11:48випадків поки що ми розглядали алгоритми
1635. 1:11:51пошуку з одним агентом я намагаюся
1636. 1:11:54вирішити
1637. 1:11:56завдання Я намагаюся пройти Лабіринт я
1638. 1:12:00намагаюся скласти п'ятнашки я намагаюся
1639. 1:12:03знайти маршрут з пункту a в пункт B
1640. 1:12:06однак іноді в пошукових ситуаціях ми
1641. 1:12:08потрапляємо в змагальну ситуацію де я
1642. 1:12:11агент намагаюся приймати розумні рішення
1643. 1:12:14а проти мене так би мовити бореться
1644. 1:12:16хтось інший який має протилежну ціль
1645. 1:12:19хтось інший який хоче щоб я зазнав
1646. 1:12:22невдачі уявити це можна знову ж таки на
1647. 1:12:25прикладі гри Хрестики нулики де є ігрове
1648. 1:12:28поле 3хтри квадрати у яких по черзі
1649. 1:12:31треба ставити хрестик або Нулик ціль
1650. 1:12:34полягає в тому щоби виставити три
1651. 1:12:35хрестики в лінію або три нулики
1652. 1:12:38комп'ютери добре грають в ігри вони
1653. 1:12:41легко можуть впоратися зі складними
1654. 1:12:43іграми Не кажучи вже про Хрестики нулики
1655. 1:12:47можете собі уявити яким буде розумне
1656. 1:12:49рішення в цій грі Перший гравець ставить
1657. 1:12:52хрестик по всередині другий Нулик угорі
1658. 1:12:55яким буде розумний хід для хрестика куди
1659. 1:12:58би ви його поставили є кілька варіантів
1660. 1:13:01але якщо штучний інтелект грає
1661. 1:13:03оптимально тоді він має поставити
1662. 1:13:06хрестик угорі праворуч Нулик у цій
1663. 1:13:08ситуації має ціль протилежну хрестику
1664. 1:13:11хрестик намагається виграти гру
1665. 1:13:13заповнивши діагональ а в нулика
1666. 1:13:15протилежна ціль завадити цьому тому
1667. 1:13:18Нулик стане тут щоби заблокувати хрестик
1668. 1:13:21але тепер хрестик може зробити хитрий
1669. 1:13:24хід він може стати тут і тепер у
1670. 1:13:27хрестика є два можливі шляхи виграти гру
1671. 1:13:29хрестик може виграти закривши центральну
1672. 1:13:31горизонталь або хрестик може виграти
1673. 1:13:34закривши праву вертикаль і вже неважливо
1674. 1:13:36де Нулик зробить наступний крок може
1675. 1:13:39стати тут блокуючи горизонтальний ряд
1676. 1:13:41але тоді хрестик виграє гру заповнивши
1677. 1:13:44праву вертикаль для того щоб комп'ютер
1678. 1:13:46міг вирішити це завдання у нього є
1679. 1:13:48безліч даних це завдання за своєю суттю
1680. 1:13:51схоже на ті які ми розглядали раніше є
1681. 1:13:54дії є певний стан дошки є певний перехід
1682. 1:13:57від однієї дії до наступної але
1683. 1:14:00відмінність полягає в тому що це тепер
1684. 1:14:02не просто класичне завдання пошуку А
1685. 1:14:04завдання змагального пошуку Я граю за
1686. 1:14:07хрестик і намагаюся знайти найкращі ходи
1687. 1:14:10але знаю що є супротивник який
1688. 1:14:12намагається зупинити мене Отже Нам
1689. 1:14:15потрібен алгоритм який впорається із цим
1690. 1:14:18змагальним пошуком розглянемо алгоритм
1691. 1:14:21мінімаксу який дуже добре працює для
1692. 1:14:23подібних Ігор де є два гравці він може
1693. 1:14:26працювати і в інших типах Ігор але зараз
1694. 1:14:28ми розглянемо ігри де я роблю хід потім
1695. 1:14:32суперник робить хід я намагаюся виграти
1696. 1:14:35і суперник намагається виграти інакше
1697. 1:14:38кажучи суперник змушує мене
1698. 1:14:41програти що потрібно щоби цей алгоритм
1699. 1:14:43працював щоразу коли ми намагаємося
1700. 1:14:46перекласти людську концепцію гри
1701. 1:14:48Перемоги та поразки на комп'ютер Ми
1702. 1:14:51хочемо перекласти її так щоб комп
1703. 1:14:53комютер її зрозумів комп'ютер насправді
1704. 1:14:55розуміє лише числа ми хочемо якимось
1705. 1:14:58чином перевести гру в Хрестики нулики у
1706. 1:15:01щось числове у те що комп'ютер
1707. 1:15:04розуміє зазвичай комп'ютер не розуміє
1708. 1:15:07поняття виграш чи програш але він
1709. 1:15:09розуміє концепцію більшого та меншого що
1710. 1:15:12ми можемо зробити узяти кожен із
1711. 1:15:15можливих шляхів якими може йти гра в
1712. 1:15:17Хрестики нулики і призначити значення чи
1713. 1:15:20корисність кожному з цих можливих
1714. 1:15:22способів
1715. 1:15:23у хрестиках-нуликах як і в багатьох
1716. 1:15:25типах Ігор є три можливі результати
1717. 1:15:28результати Нулик виграє хрестик виграє
1718. 1:15:31або нічия тобто виграє Перший гравець
1719. 1:15:34виграє другий гравець або нічия
1720. 1:15:36присвоємо кожному з цих можливих
1721. 1:15:38результатів різні значення ситуація
1722. 1:15:41Нулик виграє матиме значення -ну1 нічия
1723. 1:15:45матиме значення нуль і хрестик виграє
1724. 1:15:49матиме значення один ми присвоїли числа
1725. 1:15:52кожному з трьох можли
1726. 1:15:53результатів ще у нас є два гравці
1727. 1:15:57гравець хрестик і гравець
1728. 1:15:59Нулик ми підемо далі і назвемо гравця
1729. 1:16:02хрестик гравцем Макс а гравця Нулик
1730. 1:16:04гравцем
1731. 1:16:06міні навіщо тому що в міні максному
1732. 1:16:09алгоритмі гравець Макс яким у цьому
1733. 1:16:12випадку є хрестик прагне максимізувати
1734. 1:16:15рахунок це можливі варіанти рахунку -10
1735. 1:16:18і о хрестик хоче максимізувати рахунок
1736. 1:16:21якщо це взагалі можливо хрестик хотів би
1737. 1:16:24таку ситуацію коли він виграє гру і
1738. 1:16:26отримає одиницю Але якщо це неможливо
1739. 1:16:29Якщо хрестику потрібно вибрати між цими
1740. 1:16:32двома варіантами -1 означає перемогу
1741. 1:16:34нулика нуль означає нічию хрестик воліє
1742. 1:16:38щоби ніхто не виграв йому краще нуль ніж
1743. 1:16:40-нус1 тобто перемога нулика Таким чином
1744. 1:16:43поняття виграшу та програшу було зведено
1745. 1:16:46математично до простої спроби
1746. 1:16:48максимізувати рахунок гравець хрестик
1747. 1:16:51завжди хоче щоби рахунок був більший з
1748. 1:16:53іншого боку гравець міні у цьому випадку
1749. 1:16:56Нулик прагне мінімізувати рахунок
1750. 1:16:59гравець Нулик хоче щоби рахунок був
1751. 1:17:01якомога меншим ми взяли гру Хрестики
1752. 1:17:04нулики і перетворили її на щось
1753. 1:17:06математичне на щось таке де хрестик
1754. 1:17:09намагається максимізувати рахунок а
1755. 1:17:11Нулик
1756. 1:17:12мінімізувати розглянемо всі частини гри
1757. 1:17:15які нам потрібні для закодування її в
1758. 1:17:18штучний інтелект щоби штучний інтелект
1759. 1:17:20міг грати у Хрестики нулики для гри нам
1760. 1:17:23знадобиться ще дещо деякий початковий
1761. 1:17:26стан який ми в цьому випадку назвемо s0
1762. 1:17:29з нього починається гра це незаповнене
1763. 1:17:32поле для хрестиківнуликів нам також
1764. 1:17:34знадобиться функція під назвою Player
1765. 1:17:36Вона прийматиме за вхідні дані стан тут
1766. 1:17:39представлений S а результатом функції
1767. 1:17:41playр буде черга якого гравця потрібно
1768. 1:17:45дати комп'ютеру поле для гри в Хрестики
1769. 1:17:47на улики і запустити його через функцію
1770. 1:17:50яка повідомляє чия черга
1771. 1:17:54нам знадобиться уявлення про дії які ми
1772. 1:17:57можемо Виконати за мить побачимо
1773. 1:17:59приклади нам потрібно уявлення про
1774. 1:18:02модель переходу як і раніше Якщо у мене
1775. 1:18:04є стан і я роблю дію Мені потрібно знати
1776. 1:18:07до чого це приведе потрібен спосіб
1777. 1:18:09дізнатися коли гра закінчилася це
1778. 1:18:12еквівалентно перевірці цілі але мені
1779. 1:18:14потрібна завершальна перевірка якийсь
1780. 1:18:17спосіб перевірити чи стан завершальний
1781. 1:18:20тобто чи закінчилася гра у класичній грі
1782. 1:18:24в хрестикинуликий завершальний стан
1783. 1:18:25означає що або хтось виставив три знаки
1784. 1:18:28вряд або всі квадрати заповнені будь-яка
1785. 1:18:31з цих умов означає завершальний стан у
1786. 1:18:34шахах це може бути мат або ситуація у
1787. 1:18:36якій мат неможливий це буде завершальний
1788. 1:18:38стан і нарешті нам знадобиться функція
1789. 1:18:41корисності функція яка приймає стан і
1790. 1:18:43дає нам числове значення для
1791. 1:18:45завершального стану Скажімо так Якщо
1792. 1:18:47виграє хрестик значення буде один якщо
1793. 1:18:50Нулик мінус1дин якщо нічия тоді нуль
1794. 1:18:54розглянемо по черзі кожен із них
1795. 1:18:56початковий стан ми можемо представити як
1796. 1:18:58порожнє поле для грив Хрестики нулики з
1797. 1:19:01цього починаємо це місце з якого ми
1798. 1:19:04починаємо пошук я представлятиму все
1799. 1:19:07візуально ви можете уявити що це масив
1800. 1:19:09або двовимірний масив усіх можливих
1801. 1:19:13квадратів нам потрібна функція playр яка
1802. 1:19:16приймає стан і повідомляє чия черга
1803. 1:19:19Припустимо що перший хід робить хрестик
1804. 1:19:22якщо ігрове поле порожняє тоді функція
1805. 1:19:24playр повертає хрестик якщо поле уже з
1806. 1:19:26хрестиком тоді функція playр повертає
1807. 1:19:29нуль
1808. 1:19:30функція Player приймає ігрове поле і
1809. 1:19:33повідомляє чия
1810. 1:19:35черга далі розглянемо функцію actions
1811. 1:19:39функція actions подібно до класичного
1812. 1:19:41пошуку приймає стан і дає нам набір усіх
1813. 1:19:43можливих дій які ми можемо виконати в
1814. 1:19:46цьому
1815. 1:19:47стані уявімо що настала черга нулика
1816. 1:19:51робити хід Що станеться коли ми
1817. 1:19:54передаємо його функції actions функція
1818. 1:19:57actions с приймає цей стан гри як вхідні
1819. 1:20:00дані а результатом буде набір можливих
1820. 1:20:02дій набір хід у верхній лівий кут або в
1821. 1:20:06нижній квадрат посередині це два можливі
1822. 1:20:09варіанти дій коли починаю з цього
1823. 1:20:10конкретного
1824. 1:20:13стану як і раніше коли ми додаємо стани
1825. 1:20:16та дії нам потрібна модель переходу щоби
1826. 1:20:19повідомити який новий стан Ми отримаємо
1827. 1:20:22коли виконаємо дію в цьому стані
1828. 1:20:25визначаємо це за допомогою функції
1829. 1:20:27result яка приймає стан як вхідні дані а
1830. 1:20:30також дію коли застосовуємо функцію
1831. 1:20:33result до цього стану ставлячи Нулик у
1832. 1:20:35верхній лівий кут новий стан який ми
1833. 1:20:37отримаємо - це результуючи стан де Нулик
1834. 1:20:40у верхньому лівому куті Це здається
1835. 1:20:42очевидним для тих хто вміє грати в
1836. 1:20:44Хрестики нулики Логічно що поставивши
1837. 1:20:46Нулик у верхній лівий кут Ви отримаєте
1838. 1:20:48таке поле але всю цю інформацію потрібно
1839. 1:20:51закодувати в штучний інтелект Він не
1840. 1:20:53знає як грати в Хрестики нулики доки ви
1841. 1:20:55не скажете йому як працюють правила гри
1842. 1:20:58ця функція дозволяє повідомити штучному
1843. 1:21:00інтелекту як ця гра працює і як дії
1844. 1:21:03впливають на результат гри штучний
1845. 1:21:05інтелект має знати як працює гра і коли
1846. 1:21:08гру закінчено визначивши функцію
1847. 1:21:11terminнаal яка приймає як вхідні дані
1848. 1:21:14стан S якщо ми беремо гру яка ще не
1849. 1:21:17закінчилася передаємо її функції terміal
1850. 1:21:20результат буде хибним гру не закін але
1851. 1:21:23якщо взяти гру яка закінчилася або
1852. 1:21:25хрестик заповнив діагональ передамо це
1853. 1:21:28функції terminal тоді результат буде
1854. 1:21:30істиним тому що гру
1855. 1:21:32закінчено Нарешті ми розповіли штучному
1856. 1:21:35інтелекту як працює гра які рухи можна
1857. 1:21:37робити І що відбувається коли ви їх
1858. 1:21:40робите повідомили йому коли гра
1859. 1:21:43закінчиться тепер потрібно повідомити
1860. 1:21:46йому значення кожного з цих станів ми
1861. 1:21:48робимо це визначаючи функцію tility яка
1862. 1:21:51приймає стан S і повідомляє нам рахунок
1863. 1:21:54або корисність цього стану ще раз якщо
1864. 1:21:58хрестик виграє utility дорівнює один
1865. 1:22:01коли Нулик виграє utility дорівнює
1866. 1:22:05-1 штучний інтелект має знати корисність
1867. 1:22:08кожного завершального стану коли гру
1868. 1:22:10буде закінчено покажу вам отаке поле де
1869. 1:22:13гру закінчено і я прошу штучний інтелект
1870. 1:22:16сказати яке значення має цей
1871. 1:22:19стан він може це зробити значення стану
1872. 1:22:22один але все цікавіше якщо гру ще не
1873. 1:22:25закінчено уявімо таке ігрове поле ми
1874. 1:22:28всередині гри черга нулику зробити хід
1875. 1:22:32це можна обчислити за допомогою функції
1876. 1:22:35Player Player S передаємо стану
1877. 1:22:37відповідь Нулик Ось як ми знаємо чий хід
1878. 1:22:41яке значення цього поля і які дії має
1879. 1:22:44зробити Нулик тут треба зробити
1880. 1:22:47розрахунки і саме тут на допомогу
1881. 1:22:49приходить мінімаксний алгоритм
1882. 1:22:51пам'ятайте що що хрестик намагається
1883. 1:22:53максимізувати рахунок а Нулик
1884. 1:22:55мінімізувати рахунок Нулик хотів би
1885. 1:22:58мінімізувати загальне значення яке ми
1886. 1:23:00отримуємо в кінці гри оскільки гру ще не
1887. 1:23:04закінчено ми не знаємо значення ігрового
1888. 1:23:07поля потрібно зробити розрахунки щоби це
1889. 1:23:11зрозуміти як же зробити ці розрахунки
1890. 1:23:14для цього Розглянемо як і в класичні
1891. 1:23:17ситуації пошуку які дії можуть відбутися
1892. 1:23:19далі І до яких станів вони
1893. 1:23:23ведуть у цій позиції є лише два відкриті
1894. 1:23:26квадрати тобто є лише два відкриті місця
1895. 1:23:29куди Нулик може зробити хід або у
1896. 1:23:33верхній лівий кут або внизу
1897. 1:23:37посередині мінімаксний не знає одразу
1898. 1:23:40який із цих ходів буде кращим тому він
1899. 1:23:43розглядатиме обидва але зараз ми
1900. 1:23:46потрапляємо в таку саму ситуацію тепер у
1901. 1:23:48мене є ще два незакінчені ігрові поля що
1902. 1:23:51далі і саме в цьому сенсі ми будемо
1903. 1:23:54називати мінімаксний алгоритм
1904. 1:23:56рекурсивним він повторить той самий
1905. 1:23:58процес але тепер розглядатиме його з
1906. 1:24:01протилежної точки зору ніби я гравець
1907. 1:24:04Нулик збираюся Поставити себе на місце
1908. 1:24:07суперника гравця хрестик і буду думати
1909. 1:24:10що зробив би мій суперник Якби він був у
1910. 1:24:13цій позиції що зробив би гравець хрестик
1911. 1:24:17у цій позиції І що сталося б інший
1912. 1:24:20гравець мій суперник гравець хрестик
1913. 1:24:23намагається максимізувати рахунок тоді
1914. 1:24:25як я гравець Нулик намагаюся
1915. 1:24:28мінімізувати рахунок хрестик намагається
1916. 1:24:31отримати максимально можливе значення що
1917. 1:24:33ж буде у цій позиції на полі хрестик має
1918. 1:24:36лише один вибір заповнити центральну
1919. 1:24:39вертикаль ми знаємо що це поле На якому
1920. 1:24:42хрестик виграє має значення один якщо
1921. 1:24:45хрестик виграє значення цього ігрового
1922. 1:24:47поля дорівнюватиме одиниці якщо цей стан
1923. 1:24:51може привести лише до цього стану якщо
1924. 1:24:54це єдиний можливий варіант і цей стан
1925. 1:24:56має значення один тоді максимально
1926. 1:24:58можливе значення яке гравець хрестик
1927. 1:25:00може отримати з цього ігрового поля
1928. 1:25:03також дорівнює одиниці звідси ми можемо
1929. 1:25:06закінчити гру зі значенням один тому
1930. 1:25:08поле також має значення
1931. 1:25:10один тепер розглянемо це поле що буде
1932. 1:25:14хрестик має зробити хід єдиний варіант
1933. 1:25:16ходу верхній лівий кут хрестик іде Туди
1934. 1:25:19і в цій грі ніхто не виграє ні в кого
1935. 1:25:21немає ліній тобто значення цього
1936. 1:25:23ігрового поля дорівнює нулю за тією
1937. 1:25:26самою логікою якщо з цієї позиції поля
1938. 1:25:29єдине місце куди ми можемо потрапити це
1939. 1:25:32поле із значенням нуль тоді цей стан
1940. 1:25:34також має значення нуль і ось тепер
1941. 1:25:36вибір спроба мінімізувати я як гравець
1942. 1:25:39Нулик тепер знаю що якщо я походжу у
1943. 1:25:42верхній лівий кут це закінчиться грою зі
1944. 1:25:46значенням один це ми припускаємо що всі
1945. 1:25:49грають оптимально А якщо я натомість
1946. 1:25:52виберу нижній ряд це приведе до появи
1947. 1:25:55ігрового поля зі значенням нуль У мене
1948. 1:25:57два варіанти один і нуль потрібно
1949. 1:25:59вибрати як гравець міні я би вибрав
1950. 1:26:02варіант із мінімальним значенням щоразу
1951. 1:26:05коли гравець має кілька варіантів
1952. 1:26:07гравець міні вибере варіант із найменшим
1953. 1:26:09значенням а гравець Макс із найбільшим
1954. 1:26:12значенням між одиницею і нулем нуль
1955. 1:26:15менший тобто я краще виберу нічию ніж
1956. 1:26:18програю це ігрове поле Скажімо так також
1957. 1:26:21має значе нуль бо якщо я граю оптимально
1958. 1:26:24Я виберу цю розвилку я поставлю Нулик
1959. 1:26:27тут щоби заблокувати хрестикурят хрестик
1960. 1:26:30стане у верхньому лівому куті і гра
1961. 1:26:32закінчиться в нічию це логіка
1962. 1:26:34мінімаксного алгоритму розглянути всі
1963. 1:26:37варіанти які можна зробити усі дії які
1964. 1:26:39можна зробити а потім Поставити себе на
1965. 1:26:42місце суперника я вирішую який хід
1966. 1:26:44зробити Зараз враковуючи який хід
1967. 1:26:47зробить мій суперник потім для цього я
1968. 1:26:50обмірковую який хід я зробив би після
1969. 1:26:52цього І так далі І так далі поки не
1970. 1:26:55дійду до кінця гри до одного з
1971. 1:26:57завершальних станів ця точка прийняття
1972. 1:26:59рішення коли я як гравець Нулик
1973. 1:27:01намагаюся вирішити щодо чого приймати
1974. 1:27:04рішення могла бути лише частиною логіки
1975. 1:27:07яку гравець хрестик мій суперник
1976. 1:27:09використовував захід переді мною це може
1977. 1:27:12бути частиною якогось більшого дерева де
1978. 1:27:15хрестик намагається зробити крок у цій
1979. 1:27:17ситуації йому потрібно прийняти рішення
1980. 1:27:19вибираючи між трьома варіантами що далі
1981. 1:27:22ми від кінця гри то глибшим буде дерево
1982. 1:27:25тому що кожен його рівень відповідатиме
1983. 1:27:28одному ходу чи дії які я роблю одному
1984. 1:27:31ходу чи дії які суперник робить щоби
1985. 1:27:34вирішити що станеться і Виявляється що
1986. 1:27:37якщо я гравець хрестик у цій позиції і
1987. 1:27:40якщо я рекурсивно виконую логіку то бачу
1988. 1:27:43що в мене є три варіанти один з яких
1989. 1:27:45веде до значення нуль якщо я походжу
1990. 1:27:47сюди і якщо всі гратимуть оптимально
1991. 1:27:50буде нічия якщо я походжу сюди Нулик
1992. 1:27:53виграє а Я програю граючи оптимально або
1993. 1:27:56сюди де я гравець хрестик можу виграти
1994. 1:27:58між результатом нуль -1 і О я би вибрав
1995. 1:28:02поле зі значенням один тому що це
1996. 1:28:04максимальне значення яке я можу отримати
1997. 1:28:06Отже це поле також матиме максимальне
1998. 1:28:08значення один це дерево може стати дуже
1999. 1:28:11глибоким особливо коли у грі стає дедалі
2000. 1:28:13більше ходів Ця логіка працює не лише
2001. 1:28:16для хрестиківнуликів але й для будь-якої
2002. 1:28:19з ігор Де я роблю хід суперник робить
2003. 1:28:22хід і ми
2004. 1:28:23змагаємося можна спростити цю діаграму
2005. 1:28:26до ось такої діаграми це абстрактна
2006. 1:28:28версія мінімаксного дерева з усіма
2007. 1:28:31станами я не показую вам поле для
2008. 1:28:33Хрестиків нуликів це репрезентація
2009. 1:28:36якоїсь загальної гри чи то Хрестиків
2010. 1:28:39нуликів чи то якоїсь
2011. 1:28:41іншої Зелена стрілка спрямована вгору
2012. 1:28:44означає стан
2013. 1:28:45максимізації Я хочу щоби рахунок був
2014. 1:28:48якомога більшим а червоні стрілки
2015. 1:28:51спрямовані в низ це стани мінімізації де
2016. 1:28:53гравець міні намагається зробити рахунок
2017. 1:28:56якомога меншим уявіть у цій ситуації що
2018. 1:28:59я гравець який максимізує і я маю три
2019. 1:29:03варіанти один вибір дає мені рахунок пть
2020. 1:29:06балів інший рахунок три і ще один
2021. 1:29:08рахунок дев'ять між цими трьома
2022. 1:29:11варіантами мій найкращий варіант вибрати
2023. 1:29:13дев'ятку оцінку яка максимізує мої
2024. 1:29:16можливості зпоміж усіх трьох варіантів
2025. 1:29:19тому я можу дати цьому стану знач де
2026. 1:29:22тому що серед трьох варіантів це
2027. 1:29:24найкращий
2028. 1:29:27вибір це моє рішення Уявіть що до кінця
2029. 1:29:31гри один хід і виникне логічне запитання
2030. 1:29:34Що може зробити мій суперник за два ходи
2031. 1:29:36до кінця
2032. 1:29:38партії мій суперник гравець міні він
2033. 1:29:41намагається зробити рахунок якомога
2034. 1:29:43меншим Уявіть що сталося би якби йому
2035. 1:29:46довелося вибирати один вибір веде нас до
2036. 1:29:49цього стану де я гравець Макс збираюся
2037. 1:29:52вибрати дев'ять найбільший рахунок один
2038. 1:29:55веде до цього стану де я гравець Макс
2039. 1:29:58вибрав би вісім тому що це був би
2040. 1:30:00найбільший рахунок тепер гравець міні
2041. 1:30:04змушений вибирати між дев'яткою і
2042. 1:30:06вісімкою він вибере найменший рахунок
2043. 1:30:09тобто вісім Ось так цей процес
2044. 1:30:12розгортатиметься але гравець міні у
2045. 1:30:15цьому випадку розглядає обидва свої
2046. 1:30:17варіанти а потім усі варіанти які
2047. 1:30:19стануть можливими в результаті Отже це
2048. 1:30:22загальна картина мінімаксного алгоритму
2049. 1:30:24спробуємо формалізувати його за
2050. 1:30:27допомогою псевдокоду Отже що саме
2051. 1:30:30відбувається в мінімаксному алгоритмі
2052. 1:30:32враховуючи стан S нам потрібно вирішити
2053. 1:30:35що має статися гравець Макс якщо це Його
2054. 1:30:37черга вибере дію a у actions від S
2055. 1:30:41нагадаю що actions - це функція яка
2056. 1:30:44приймає стан і повертає всі мої можливі
2057. 1:30:46дії вона повідомляє мені про всі можливі
2058. 1:30:50рухи
2059. 1:30:53гравець Макс збирається вибрати дію a у
2060. 1:30:56наборі дій яка дає мені найвище значення
2061. 1:30:59minanvue result від S і
2062. 1:31:03a що це означає що я хочу вибрати
2063. 1:31:07варіант Який дасть найвищий рахунок з
2064. 1:31:09усіх дій
2065. 1:31:11a але яким буде цей рахунок щоб
2066. 1:31:14обчислити це мені потрібно знати що мій
2067. 1:31:16суперник гравець міні збирається робити
2068. 1:31:19якщо він хоче мінімізувати значення
2069. 1:31:21стану який виник яким буде значення
2070. 1:31:24стану після того як я виконаю цю дію І
2071. 1:31:27що станеться коли гравець міні спробує
2072. 1:31:29мінімізувати значення цього стану я
2073. 1:31:32розгляну це для всіх можливих варіантів
2074. 1:31:34І після того виберу дію A яка має
2075. 1:31:37найвище
2076. 1:31:39значення подібним чином гравецьміні
2077. 1:31:42зробить те саме але обернено він також
2078. 1:31:45розгляне Які можливі дії він може
2079. 1:31:47виконати під час свого ходу і вибере дію
2080. 1:31:50a що має наймен ше можливе значення з
2081. 1:31:53усіх варіантів а звідки він знає яке
2082. 1:31:56найменше можливе значення з усіх
2083. 1:31:57варіантів він розгляне те що збирається
2084. 1:32:00зробити гравець Макс який результат
2085. 1:32:02застосування цієї дії до поточного стану
2086. 1:32:06яке значення розрахував би гравець Макс
2087. 1:32:08для цього конкретного
2088. 1:32:11стану кожен приймає рішення оцінюючи що
2089. 1:32:14може зробити
2090. 1:32:17суперник тепер звернімо увагу на функції
2091. 1:32:20maxv і meanue Як ви обчислюєте значення
2092. 1:32:24стану коли намагаєтеся максимізувати
2093. 1:32:27його значення або мінімізувати його
2094. 1:32:29значення якщо ви можете це зробити тоді
2095. 1:32:33ми маємо повну реалізацію мінімаксного
2096. 1:32:36алгоритму спробуємо реалізувати функцію
2097. 1:32:38Max value яка приймає стан і повертає
2098. 1:32:41значення цього стану якщо я намагаюся
2099. 1:32:44максимізувати його
2100. 1:32:47значення Спершу я перевірю чи
2101. 1:32:49закінчилася гра якщо так інакше кажучи
2102. 1:32:52якщо стан є завершальним тоді все легко
2103. 1:32:56У мене є функція utility яка повідомляє
2104. 1:32:59вартість поля якщо гра закінчилася Я
2105. 1:33:02перевіряю виграв хрестик виграв Нулик
2106. 1:33:05нічия функція tilліity просто знає
2107. 1:33:08значення стану складніше якщо гра не
2108. 1:33:10закінчилася тоді мені потрібно міркувати
2109. 1:33:13рекурсивно про те що суперник зробить
2110. 1:33:15під час наступного ходу потім я обчислюю
2111. 1:33:18значення цього стану і хочу щоб воно
2112. 1:33:20було якомога
2113. 1:33:22вищим я відстежуватиму це значення у
2114. 1:33:25змінні V якщо я хочу щоби значення було
2115. 1:33:28якомога вищим Мені потрібно надати в
2116. 1:33:30початкове значення Спочатку я встановлю
2117. 1:33:33його якомога нижчим бо ще не знаю які
2118. 1:33:35варіанти мені доступні нехай V дорівнює
2119. 1:33:38від'ємний нескінченності це дивно але
2120. 1:33:41ідея в тому що я визначаю початкове
2121. 1:33:43значення якомого нижчим тому що
2122. 1:33:45розглядаючи свої дії Я завжди
2123. 1:33:47намагатимуся зробити краще ніж V А при V
2124. 1:33:51дорів від'ємній нескінченності Я завжди
2125. 1:33:54можу зробити
2126. 1:33:56краще я обмірковую свої дії це буде
2127. 1:33:59різновид циклу де для кожної дії в
2128. 1:34:02actions від
2129. 1:34:03State Нагадую що actions - це функція
2130. 1:34:06яка приймає мій стан і надає мені всі
2131. 1:34:08можливі дії які я можу використовувати в
2132. 1:34:10цьому стані кожну з цих дій треба
2133. 1:34:13порівняти з
2134. 1:34:15в тому V буде
2135. 1:34:18дорівнювати максимуму V та результату
2136. 1:34:22цього виразу що це за вираз Спочатку це
2137. 1:34:25отримання результату виконання дії та
2138. 1:34:27стану а потім отримання мінімального
2139. 1:34:30значення цього результату інакше кажучи
2140. 1:34:33я хочу з'ясувати з цього стану що
2141. 1:34:36найкраще може зробити гравець міні бо
2142. 1:34:39він намагається мінімізувати рахунок
2143. 1:34:41яким би не був результат мінімального
2144. 1:34:43значення цього стану порівняйте його з
2145. 1:34:46поточним найкращим значенням і виберіть
2146. 1:34:48максимальне оскільки я намагаюся
2147. 1:34:51максимізувати значення Коротше кажучи що
2148. 1:34:54роблять ці три рядки коду переглядають
2149. 1:34:57усі мої можливі дії і запитують як
2150. 1:34:59максимізувати рахунок Враховуючи те що
2151. 1:35:01мій суперник збирається зробити після
2152. 1:35:04цього циклу я можу повернути в і це
2153. 1:35:07тепер значення цього конкретного стану а
2154. 1:35:09для гравця міні усе прямо протилежне та
2155. 1:35:12сама логіка тільки обернено щоб
2156. 1:35:15обчислити мінімальне значення стану
2157. 1:35:17спочатку Перевіряємо чи це завершальний
2158. 1:35:19стан Якщо так повер
2159. 1:35:22інакше ми будемо намагатися мінімізувати
2160. 1:35:25значення стану враховуючи всі можливі
2161. 1:35:27дії тому мені потрібне початкове
2162. 1:35:29значення для V що дорівнює
2163. 1:35:31нескінченності бо я знаю що завжди можна
2164. 1:35:33отримати щось менше за нескінченність
2165. 1:35:36установивши в що дорівнює нескінченності
2166. 1:35:40я гарантував що перша дія яку я знайду
2167. 1:35:42буде меншою за це значення в потім я
2168. 1:35:46роблю те саме переглядаю всі мої можливі
2169. 1:35:48дії і для кожного результату який ми
2170. 1:35:50можемо отримати коли гравець maxс
2171. 1:35:52приймає рішення візьмемо мінімум цього
2172. 1:35:55та поточного значення V після того як
2173. 1:35:58усе зроблено я отримую найменше можливе
2174. 1:36:01значення V яке потім повертає
2175. 1:36:03користувачеві по суті це псевдокод для
2176. 1:36:06мінімаксного алгоритму Ми беремо гру та
2177. 1:36:09визначаємо який найкращий хід зробити
2178. 1:36:12рекурсивно використовуючи функції Max
2179. 1:36:14value Та minan value де Max value
2180. 1:36:17викликає minanvue minan value викликає
2181. 1:36:20Max value туди і назад доки ми не
2182. 1:36:22досягнемо завершального стану в якому
2183. 1:36:25наш алгоритм може повернути тиліity
2184. 1:36:27цього конкретного стану можете уявити що
2185. 1:36:30цей процес буде тривалим особливо коли
2186. 1:36:33ігри будуть складнішими та довшими коли
2187. 1:36:36Ми додамо більше ходів і більше можливих
2188. 1:36:38варіантів виникає питання Яку
2189. 1:36:40оптимізацію ми можемо виконати Як це
2190. 1:36:43можна зробити краще щоби використовувати
2191. 1:36:45менше місця або витрачати менше часу на
2192. 1:36:48вирішення завдання розглянемо кілька
2193. 1:36:50можливих оп ці але для початку
2194. 1:36:52поговоримо про цей приклад це знову
2195. 1:36:54стрілки спрямовані вгору і вниз уявімо
2196. 1:36:57що я зараз гравець Макс ця Зелена
2197. 1:37:00Стрілка я намагаюся зробити рахунок
2198. 1:37:02якомога вищим це легка гра де всього два
2199. 1:37:05виходи я роблю хід один із цих трьох
2200. 1:37:08Потім мій суперник робить хід один із
2201. 1:37:10цих трьох Що залежить від мого ходу у
2202. 1:37:13результаті Ми отримаємо значення
2203. 1:37:15подивимося на порядок в якому я виконую
2204. 1:37:18обчислення і з'ясуємо Чи можу я якось
2205. 1:37:21омізувати процес обчислення розглядатиму
2206. 1:37:23ці стани по- оддному Я починаю тут зліва
2207. 1:37:28я буду думати що гравець міні мій
2208. 1:37:30суперник спробує зробити тут гравець
2209. 1:37:32міні розгляне всі три можливі дії та
2210. 1:37:35оцінить їх значення тому що це
2211. 1:37:37завершальні стани які означають кінець
2212. 1:37:40гри він побачить цей вузол має значення
2213. 1:37:42чотири цей ві цей пть і гравець міні
2214. 1:37:45скаже між цими трьома варіантами 4 ві і
2215. 1:37:495 я візьму найменший чоти тепер цей стан
2216. 1:37:53має
2217. 1:37:53значеннячотири тоді я як гравець Макс
2218. 1:37:57кажу якщо я візьму цю дію вона матиме
2219. 1:38:00значення чотири це найкраще що я можу
2220. 1:38:03зробити бо гравець міні намагається
2221. 1:38:05мінімізувати рахунок А якщо я виберу цей
2222. 1:38:08варіант дослідимо що зробить гравець
2223. 1:38:11міні якщо я виберу цю дію гравець міні
2224. 1:38:13скаже які є три варіанти гравець міні
2225. 1:38:17має варіанти дет і с три найменше серед
2226. 1:38:20них тобто цей стан має значення три я як
2227. 1:38:24гравець Макс дослідив два із трьох своїх
2228. 1:38:27варіантів і знаю що один із них
2229. 1:38:28гарантуватиме мені рахунокчотири а інший
2230. 1:38:31гарантуватиме рахунок
2231. 1:38:34три Тепер я розглядаю свій третій
2232. 1:38:37варіант що тут
2233. 1:38:39відбувається така сама логіка гравець
2234. 1:38:41міні розглядатиме і три стани 2 4 іш
2235. 1:38:45найменший з них- два тому він вибирає
2236. 1:38:48його тепер я як гравець Макс обчи числив
2237. 1:38:51усю інформацію дивлячись на два шари
2238. 1:38:53вглиб вибираючи між чотиритри і два Я
2239. 1:38:57вибрав би чотири тому що в цій ситуації
2240. 1:39:00якщо суперник гратиме оптимально він
2241. 1:39:02спробує привести мене до четвірки але це
2242. 1:39:05найкраще що я можу зробити я не можу
2243. 1:39:08гарантувати Вищий бал бо якщо я виберу
2244. 1:39:11будь-який із цих двох варіантів то можу
2245. 1:39:13отримати три або два але тут є дев'ять
2246. 1:39:16це найвищий рахунок зпоміж усіх в мене
2247. 1:39:19може виникнути Спокуса вибрати трійку
2248. 1:39:21можливо варто вибрати її бо тут я міг би
2249. 1:39:24отримати дев'ять але якщо гравець міні
2250. 1:39:26грає розумно і вибирає найкращі ходи
2251. 1:39:29зпоміж усіх можливих я можу лишитися з
2252. 1:39:31трійкою замість того щоби граючи
2253. 1:39:33оптимально гарантувати собі
2254. 1:39:35четвірку це не впливає на логіку якою я
2255. 1:39:38б користувався як гравець міні maкс
2256. 1:39:40намагаючись максимізувати свій рахунок
2257. 1:39:42із цього вузла Та мені знадобилося
2258. 1:39:45чимало обчислень щоби це зрозуміти
2259. 1:39:47довелося розглянути всі вузли щоби
2260. 1:39:50зробити такий висновк і це у простій грі
2261. 1:39:52де в мене і суперника є по три варіанти
2262. 1:39:55і гра закінчується Отже я хотів би
2263. 1:39:57придумати якусь оптимізацію можливо мені
2264. 1:40:00не потрібно робити Всі ці розрахунки щоб
2265. 1:40:02дійти висновку що дія ліворуч - це
2266. 1:40:05найкращий для мене
2267. 1:40:07варіант спробуємо ще раз і спробуємо
2268. 1:40:10діяти трохи
2269. 1:40:11розумніше починаю так само не знаю що
2270. 1:40:15робити спочатку тому просто розглядаю
2271. 1:40:18один із варіантів і думаю що може
2272. 1:40:21зробити гравець міні Він має три
2273. 1:40:23варіанти 48 і5 зпоміж них міні вибирає
2274. 1:40:27найкращі для себечотири бо хоче
2275. 1:40:30мінімізувати
2276. 1:40:31рахунок Тепер я гравець Макс розгляну
2277. 1:40:34свій другий варіант зробивши хід тут і
2278. 1:40:37подумавши що суперник зробив би у
2279. 1:40:40відповідь що робитиме гравець міні Він
2280. 1:40:43збирається з цього стану розглянути свої
2281. 1:40:45варіанти - це варіант 3 це варіант і
2282. 1:40:50якщо я в цьому початковому стані виконую
2283. 1:40:52всі ці обчислення То коли бачу три це
2284. 1:40:55має негайно стати для мене червоним
2285. 1:40:57прапорцем Бо коли я бачу три у цьому
2286. 1:41:00стані Я знаю що значення цього стану
2287. 1:41:02становитиме щонайбільше
2288. 1:41:05три це буде три або менше за три Хоча я
2289. 1:41:08ще навіть не дивився на останню дію чи
2290. 1:41:11подальші дії якщо тут можна було б їх
2291. 1:41:14виконати звідки я це знаю я знаю що
2292. 1:41:17гравець міні намагається мінімізувати
2293. 1:41:19мій рахунок якщо він бачить три тут тоді
2294. 1:41:22тут може бути не трійка тільки якщо ця
2295. 1:41:25дія яку я ще не перевірив менша за
2296. 1:41:27трійку а це означає що це значення не
2297. 1:41:30може бути більшим за трійку бо гравець
2298. 1:41:32міні уже може гарантувати три і він
2299. 1:41:35намагається мінімізувати
2300. 1:41:37рахунок про що це мені говорить Це
2301. 1:41:40говорить мені якщо я виберу цю дію мій
2302. 1:41:43рахунок Буде три або навіть менше за три
2303. 1:41:45якщо мені не пощастить але я вже знаю що
2304. 1:41:49ця дія гарантує чотири і оскільки я знаю
2305. 1:41:52що ця дія гарантує чотири А ця дія
2306. 1:41:55означає що я не зможу заробити більше
2307. 1:41:58ніж три то якщо я намагаюся
2308. 1:42:00максимізувати рахунок нема потреби
2309. 1:42:02розглядати цей трикутник тут не може
2310. 1:42:04бути жодного значення жодного числа яке
2311. 1:42:07змінило би мій вибір між цими двома
2312. 1:42:09варіантами Я завжди оберу цей шлях який
2313. 1:42:12приносить мені чотири на відміну від
2314. 1:42:14цього шляху де найкращою для мене буде
2315. 1:42:16трійка якщо суперник грає оптимально і
2316. 1:42:19це також буде справедливо для всіх
2317. 1:42:21майбутніх станів що гравець міні може
2318. 1:42:23зробити тут якщо я бачу що цей стан
2319. 1:42:25дорівнює двійці то я знаю що цей стан
2320. 1:42:27дорівнює що найбільше двом бо єдиний
2321. 1:42:30спосіб завдяки якому це значення може
2322. 1:42:32бути чимось іншим ніж два це якщо один
2323. 1:42:35із цих двох станів що залишились менше
2324. 1:42:37за два то гравець міні вибере це
2325. 1:42:39натомість Отже навіть не переглядаючи
2326. 1:42:42стани що залишились я як гравець Макс
2327. 1:42:45може знати що шлях ліворуч буде кращим
2328. 1:42:47ніж будь-який шлях праворуч тому що цей
2329. 1:42:50не може бути кращим за три А цей не може
2330. 1:42:53бути кращим за два Отже чотири в цьому
2331. 1:42:57випадку найкращий варіант тепер я можу
2332. 1:43:00сказати що цей стан має значення чотири
2333. 1:43:03щоби виконати такий тип розрахунків я
2334. 1:43:05звертав увагу на математику весь час
2335. 1:43:08відстежував що я можу зробити найкраще
2336. 1:43:11що я можу зробити
2337. 1:43:13найгірше якщо я вже знаю що можу
2338. 1:43:16отримати чотири а в цьому стані я можу
2339. 1:43:18отримати максимум три мені не причин
2340. 1:43:21його
2341. 1:43:22розглядати я можу ефективно обрізати цю
2342. 1:43:25гілку і все що під нею саме з цієї
2343. 1:43:28причини оптимізація мінімаксного
2344. 1:43:31алгоритму називається Альфа Бета
2345. 1:43:34відсіченням Альфа та бета означають два
2346. 1:43:36значення які вам доведеться відстежувати
2347. 1:43:38найкраще і найгірше що ви можете зробити
2348. 1:43:42відсічення полягає в тому що якщо у мене
2349. 1:43:44є глибоке дерево пошуку я міг би
2350. 1:43:46здійснити пошук у ньому ефективніше якщо
2351. 1:43:49мені не потрібно перебирати все якщо я
2352. 1:43:52можу видалити деякі вузли щоб
2353. 1:43:54оптимізувати процес перегляду всього
2354. 1:43:56простору пошуку альфабета відсічення
2355. 1:43:58може заощадити нам багато часу під час
2356. 1:44:01пошуку зробивши його ефективнішим але
2357. 1:44:04навіть так не все чудово оскільки ігри
2358. 1:44:07стають складнішими Хрестики нулики - це
2359. 1:44:09відносно проста гра ми можемо розумно
2360. 1:44:12поставити запитання скільки всього існує
2361. 1:44:15можливих ігор у Хрестики нулики
2362. 1:44:18подумайте про це спробуйте оцінити скіль
2363. 1:44:20скільки ходів є в будь-якій конкретній
2364. 1:44:22точці скільки ходів може тривати гра
2365. 1:44:25виявляється існує приблизно 255 000
2366. 1:44:28можливих ігор у Хрестики
2367. 1:44:30нулики порівняйте Це зі складнішою грою
2368. 1:44:34наприклад шахами більше фігур більше
2369. 1:44:37ходів довше грати скільки всього може
2370. 1:44:40бути можливих шахових партій Виявляється
2371. 1:44:43що Після чотирьох ходів білими і
2372. 1:44:46чотирьох ходів чорними існує
2373. 1:44:48288 млрдв можливих шахових
2374. 1:44:52партій лише після чотирьох ходів кожного
2375. 1:44:55гравця А якщо ви візьмете шахові партії
2376. 1:44:58загалом і те скільки можливих шахових
2377. 1:45:00партій може існувати Ви отримаєте понад
2378. 1:45:0310 у степені 29 000 набагато більше
2379. 1:45:06шахових партій ніж Можна було б
2380. 1:45:08розглянути це велике завдання для
2381. 1:45:11мінімаксного алгоритму тому що він
2382. 1:45:13починає з початкового стану розглядає
2383. 1:45:16всі можливі дії та всі можливі дії після
2384. 1:45:18них Доки не дійде до кінця
2385. 1:45:22гри це буде проблемою якщо комп'ютеру
2386. 1:45:25доведеться переглядати стільки станів А
2387. 1:45:27це набагато більше ніж будь-який
2388. 1:45:29комп'ютер міг би зробити за розумний
2389. 1:45:31проміжок часу як же вирішити це завдання
2390. 1:45:35замість того щоб переглядати всі стани
2391. 1:45:37що абсолютно неможливо для комп'ютера
2392. 1:45:39потрібен кращий підхід цей кращий підхід
2393. 1:45:41набуває форми мінімаксного алгоритму з
2394. 1:45:44обмеженням глибини зазвичай мінімаксний
2395. 1:45:46алгоритм не обмежений за глибиною Ми
2396. 1:45:49продовжуємо шар за шаром хід за ходом
2397. 1:45:52Доки не дійдемо до кінця гри мінімаксний
2398. 1:45:55алгоритм з обмеженням глибини після
2399. 1:45:57певної кількості ходів може 10ти чи 12ти
2400. 1:46:00зупиниться і не розглядатиме додаткові
2401. 1:46:03ходи тому що буде обчислювально важко
2402. 1:46:06розглянути всі можливі
2403. 1:46:11варіанти але що робити після 10 12 ходів
2404. 1:46:15у глибину якщо гра ще не закінчиться
2405. 1:46:18мінімаксу потрібен спосіб призначення
2406. 1:46:20рахунок цьому ігровому полю або стану
2407. 1:46:23гри щоби визначити його поточне значення
2408. 1:46:26це легко зробити якщо гра
2409. 1:46:28закінчилася але не так легко якщо гра ще
2410. 1:46:31триває для цього потрібно додати одну
2411. 1:46:34додаткову особливість до мінімаксного
2412. 1:46:36алгоритму з обмеженням глибини яка
2413. 1:46:38називається оцінювальною функцією
2414. 1:46:41це функція яка оцінює очікувану
2415. 1:46:43корисність гри із заданого стану у такій
2416. 1:46:47грі як шахи якщо ви уявите що значення
2417. 1:46:49гри один означає перемогу білих міну1
2418. 1:46:52перемогу чорних нуль нічию тоді ви
2419. 1:46:55можете уявити що рахунок
2420. 1:46:570,8 означає що виграють радше білі хоча
2421. 1:47:00звісно це
2422. 1:47:02негарантовано оцінювальна функція
2423. 1:47:04оцінить наскільки хорошим є стан гри
2424. 1:47:07якість оцінювальної функції визначатиме
2425. 1:47:09наскільки якісно працює штучний інтелект
2426. 1:47:12що краще штучний інтелект оцінює
2427. 1:47:14наскільки хороший чи поганий певний стан
2428. 1:47:16гри то краще він зможе зіграти якщо
2429. 1:47:19оцінювальна функці не така хороша як
2430. 1:47:21оцінка очікуваної корисності тоді все
2431. 1:47:24буде набагато складніше ви можете уявити
2432. 1:47:27спробу придумати ці оцінювальні функції
2433. 1:47:29у шахах Ви можете написати оцінювальну
2434. 1:47:32функцію на основі того скільки фігур є у
2435. 1:47:34вас скільки у супротивника оскільки
2436. 1:47:37кожна з них має значення у оцінювальній
2437. 1:47:40функції ймовірно все це має бути
2438. 1:47:42складніше ніж зараз щоб розглянути інші
2439. 1:47:45можливі ситуації які також можуть
2440. 1:47:47виникнути у мінімаксному алгоритмі є
2441. 1:47:49багато інших варіантів які додають
2442. 1:47:52особливості щоб допомогти йому працювати
2443. 1:47:54краще в таких масштабах і складних з
2444. 1:47:57точки зору обчислень ситуаціях де ми не
2445. 1:47:59можемо дослідити всі можливі ходи Тому
2446. 1:48:01нам потрібно з'ясувати як
2447. 1:48:03використовувати оцінювальні функції та
2448. 1:48:05інші техніки щоб мати можливість краще
2449. 1:48:07грати в ці ігри це був погляд на
2450. 1:48:10різновид змагального пошуку завдання
2451. 1:48:12пошуку коли ми маємо ситуації де я
2452. 1:48:14намагаюся грати проти суперника ці
2453. 1:48:17завдання пошуку виявляються у штучному
2454. 1:48:19інтелекті сьогодні Ми багато говорили
2455. 1:48:21про класичні завдання пошуку як от пошук
2456. 1:48:24маршруту але щоразу коли штучний
2457. 1:48:27інтелект намагається прийняти рішення на
2458. 1:48:29зразок того що мені робити зараз щоби
2459. 1:48:31зробити щось раціональне або розумне або
2460. 1:48:34спробувати зіграти в гру і з'ясувати
2461. 1:48:36який хід зробити такі алгоритми можуть
2462. 1:48:39стати у пригоді для хрестиків-нуликів
2463. 1:48:42рішення досить просте бо це маленька гра
2464. 1:48:44xkcd створив відомий веб-комікс у якому
2465. 1:48:48він розкаже який оптимальний хід зроби
2466. 1:48:50бити незалежно від того як походить
2467. 1:48:52суперник такий тип речей неможливий для
2468. 1:48:55більшої гри як от шашки чи шахи шахи
2469. 1:48:58абсолютно не піддаються обчисленню і
2470. 1:49:00більшість комп'ютерів не можуть
2471. 1:49:02дослідити всі можливі стани Тому нам
2472. 1:49:04потрібно щоби штучний інтелект був
2473. 1:49:06набагато розумнішим у вирішенні цих
2474. 1:49:09завдань і в тому як він шукатиме рішення
2475. 1:49:12Опинившись у цьому середовище Отже Це
2476. 1:49:15пошук і штучний інтелект Наступного разу
2477. 1:49:18розглянемо знання і подумаємо як штучний
2478. 1:49:21інтелект здатний знати інформацію думати
2479. 1:49:24про неї та робити висновки і все це з
2480. 1:49:27огляду на штучний інтелект і принципи що
2481. 1:49:29лежать в його основі до
2482. 1:49:36зустрічі