Поиск и игровой ИИ: A* и минимакс на Python

Суть простыми словами

Классический ИИ решает задачи, перебирая возможные состояния. A* находит самый дешёвый путь, складывая уже пройденную стоимость с оценкой оставшейся, а минимакс выбирает ходы в играх двух игроков, предполагая, что соперник играет хорошо.

Найдите кратчайший путь на сетке поиском A* и выберите лучший ход в игре с помощью минимакса.

Главные идеи

A* находит лучший путь, если оценка (эвристика) никогда не превышает реальную стоимость.
Минимакс обходит дерево игры до заданной глубины или до конца партии.
Альфа-бета отсечение пропускает ветви, которые не могут изменить решение.
Генетические алгоритмы ищут иначе: они развивают популяцию вариантов решения.

Когда это использовать?

Понять, что происходит внутри нейронных сетей и библиотек ИИ.
Разобраться в идее до того, как реализовать её в соответствующих задачах.
Подготовиться к курсам по машинному обучению, собеседованиям и проектам.

Посмотрите в действии

Нажмите Запуск, чтобы посмотреть, как A* исследует сетку; щёлкайте по клеткам, чтобы ставить или убирать стены. В дереве игры щёлкните по листу, чтобы изменить его оценку.

Пример кода

Запустить код →

main.py

import heapq

# A* finds the cheapest path using cost so far + a guess of the cost left.
grid = ["S..#",
        ".#..",
        "...G"]
start, goal = (0, 0), (2, 3)
guess = lambda r, c: abs(r - goal[0]) + abs(c - goal[1])   # Manhattan distance

frontier = [(guess(*start), 0, start, [start])]
seen = set()
while frontier:
    _, cost, (r, c), path = heapq.heappop(frontier)
    if (r, c) == goal:
        print("path:", path, "cost:", cost)
        break
    if (r, c) in seen:
        continue
    seen.add((r, c))
    for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < 3 and 0 <= nc < 4 and grid[nr][nc] != "#":
            heapq.heappush(frontier, (cost + 1 + guess(nr, nc), cost + 1, (nr, nc), path + [(nr, nc)]))

# Minimax: the maximizer assumes the opponent always picks the worst for it.
def minimax(node, maximizing):
    if isinstance(node, int):
        return node
    values = [minimax(child, not maximizing) for child in node]
    return max(values) if maximizing else min(values)

tree = [[3, 5], [2, 9], [0, 7]]   # our move, then the opponent's reply
print("best guaranteed score:", minimax(tree, True))

Ожидаемый результат

path: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 3), (2, 3)] cost: 5
best guaranteed score: 3

Как это работает

Очередь с приоритетом всегда раскрывает клетку с наименьшей суммой «стоимость + оценка», где оценка - манхэттенское расстояние до цели, поэтому A* доходит до G за 5 шагов в обход стен. minimax() берёт максимум на нашем ходу и минимум на ходу соперника; первый ход гарантирует 3 - лучший из трёх худших вариантов.

Измените значения и запустите программу в онлайн-компиляторе Python CodeUtility без локальной установки Python.

Практические задания

Изменяйте входные данные и проверяйте граничные случаи перед работой с большими наборами.

Измените входные данные или веса и предскажите результат до запуска.
Выводите промежуточные значения, чтобы проследить каждый шаг вычислений.
Решите задачи по ссылкам ниже, чтобы самостоятельно реализовать идею.

Запустить в Python IDE →

Попрактикуйтесь на задаче

Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.

Все задачи