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

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

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

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

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

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

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

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

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

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

Секрет!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Комбінації

рекурсія

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

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

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

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

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

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

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

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

графи

графи

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

графи

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

графи

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

графи

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

графи

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