Огляд курсу "Python та штучний інтелект"

задачі, де потрібні інтелектуальні рішення

задачі, де потрібні інтелектуальні рішення

• логічні задачки
• пазли
• математичні задачки
• стратегії в іграх
• симуляція інтелекту

мова, яку розуміє комп'ютер

мова, яку розуміє комп'ютер

З мовами все не так просто

як працює вгадування персонажа

як працює вгадування персонажа

як працює вгадування персонажа

як працює вгадування персонажа

• табличку не обов'язково заповнювати вручну
• нехай юзери заповнюють цю табличку
• але так, щоб вони самі про це не знали

як працює вгадування персонажа

Секрет!

• задаємо 10 питань, які ділять Y/N варіанти пополам
• в цей момент ми вже знаємо персонажа
• але задаємо ще 10 незв'язаних питань юзеру, щоб заповнити пропуски в табличці

передбачення точки зустрічі

передбачення точки зустрічі

Слідування (крива погоні)

передбачення точки зустрічі

Математична модель

передбачення точки зустрічі

Програмний код для розрахунку точки зустрічі та напрямку вильоту ракети ППО

еволюційні (генетичні) алгоритми

еволюційні (генетичні) алгоритми

Ідея: робимо симуляції агентів з різними параметрами (так званий ДНК). Спочатку їх ДНК випадкові, вони рухаються по рандому.

еволюційні (генетичні) алгоритми

Ідея: ті агенти, які краще всього рухаються (найближче до цілі), схрещуємо їх ДНК та створюємо новий набір агентів (нова популяція).

еволюційні (генетичні) алгоритми

Ідея: якщо повторити так багато разів, то в результаті залишаться агенти з ДНК, яка допомагає їм "виживати", тобто, виконувати поставлену задачу.

перебір ходів

перебір ходів

Будуємо дерево всіх можливих ходів, якщо це можливо. Чим глибше і ширше дерево –- тим більше випадків можна розглянути.

перебір ходів

Кожній ігровій позиції присвоюємо ціну. Ціна може складатись з вартості фігур, розміщень фігур та інших параметрів, головне щоб вийшло одне число –- додатнє або від'ємне.

алгоритм Мінімакс

алгоритм Мінімакс

• будуємо дерево, враховуючи не тільки свої ходи, а й ходи суперника
• проставляємо ціну позицій на всіх листках цього дерева (останньому рівні)

алгоритм Мінімакс

• починаючи на листках, заповнюємо всі інші ціни позицій
• принцип мінімакс: якщо наш хід, то максимізуємо виграш, якщо хід противника –- то мінімізуємо виграш. Це буде означати "вибираємо найкращий хід з найгірших"

симуляція гри

симуляція гри

Нам потрібне якесь середовище, де наш штучний інтелект буде працювати.

Це може бути реальний робот (Arduino, RaspberryPi), але їх може бути довго і дорого будувати.

симуляція гри

А ще роботи повільні, і тестувати ваш алгоритм на роботах займе багато часу.

Набагато швидше робити програмні симуляції. Щоб всі тести були на комп'ютерів, без фізичних роботів.

симуляція гри

Кожна комп'ютерна гра –- це міні-симуляція маленького світу, з своїми правилами та своїм штучним інтелектом.

комбінаторика

комбінаторика

Правило добутку

комбінаторика

Перестановки

комбінаторика

Комбінації

рекурсія

рекурсія

пошук шляху в прямокутній сітці

пошук шляху в прямокутній сітці

Кількість можливих шляхів

пошук шляху в прямокутній сітці

Манхеттенська та Евклідова відстані

пошук шляху в прямокутній сітці

Мінімальна манхеттенська відстань в сітці з перешкодами

пошук шляху в прямокутній сітці

Пошук шляху на дошці (починаючи з кінця, в порядку зменшення чисел)

графи

графи

графи

Graphviz –- мова для малювання графів (якщо немає ручки та листочка).

графи

Графи бувають різні

графи

Представлення графа: список ребер

графи

Представлення графа: список вершин та їх сусідів

графи

Представлення графа: матриця суміжності

пошук мінімального шляху в графі