Как я решил потихоньку учить питон, а попал в дебри CS188.1x Artificial Intelligence

Привет Хабр, или введение

Расскажу свою небольшую предысторию.

Как то в очередной раз надоело ковырять очередной контроллер, схему и pcb, и удрученный средней по рынку зарплатой рядового электронщика решил — хочу опять в программисты.

Не могу сказать, что я уже был в программистах, но образование получил 3 года назад по специальности «Информационные системы и технологии» в Военмехе. А судьба занесла в схемотехники-электронщики еще во времена универа. Раньше спасали частые командировки на объекты (пока молод и холост — интересно), а последний год все окончательно надоело.
Читая Хабр, выбрал себе Python.

Эти первая вторая недавние статьи помогли определится как и что начинать.

Собственно, по рекомендации и начал в начале сентября с изучения: Марк Лутц. Изучаем Python, 4-е издание. Стиснув зубы и сжав в кулак все что сжималось — на остатке мотивации дочитал до 803-й страницы, сделав попутно все упражнения. На середине ООП меня скрючило окончательно. Книга хороша, но муторна — нет сил.

Просто бросать не хотелось, и дальше попробовал курс Google’s python class. Ух, как же классно оказалось решить финальную задачку! Два вечера пролетели за мгновенье.

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

Сказано — сделано, и вот я уже записан на два курса. Про первый уже писали тут, про второй — тут. А то, что в одном python 2.7, в другом 3.2 — еще и лучше, подумалось мне. После дотошного Лутца первые 2 недели обоих курсов щелкнулись как орешки. Отдельное спасибо progress bar за мотивацию. И кликая по ссылкам был найден он — CS188.1x: Artificial Intelligence. Что пишут?

PREREQUISITES

• Programming
  
  1. Object-Oriented Programming
  2. Recursion
  3. Python or the ability to learn Python quickly (short referesher provided)
• Data Structures
  
  1. Lists vs. Sets (Arrays, Hashtables)
  2. Queuing (Stacks, Queues, Priority Queues)
  3. Trees vs. Graphs (Traversal, Backpointers)
• Math
  
  1. Probability, Random Variables, and Expectations (Discrete)
  2. Basic Asymptotic Complexity (Big-O)
  3. Basic Counting (Combinations and Permutations)

Классно! Вспомню матан, потренирую своего маленького пока еще питона, и ничего что курс идет уже 2ю неделю.

Полная программа курса

Introduction to AI

• Overview
• Agents: Perception, Decisions, and Actuation

Search and Planning

• Uninformed Search (Depth-First, Breadth-First, Uniform-Cost)
• Informed Search (A*, Greedy Search)
• Heuristics and Optimality

Constraint Satisfaction Problems

• Backtracking Search
• Constraint Propagation (Forward Checking, Arc Consistency)
• Exploiting Graph Structure

Game Trees and Decision Theory

• Decision Theory
  Preferences, Rationality, and Utilities
  Maximum Expected Utility

• Game Trees and Tree-Structured Computation
  Minimax, Expectimax, Combinations
  Evaluation Functions and Approximations
  Alpha-Beta Pruning

Markov Decision Processes (MDPs)

• Policies, Rewards, and Values
• Value Iteration
• Policy Iteration

Reinforcement Learning (RL)

• TD/Q Learning
• Exploration
• Approximation

Conclusion and Wrap-Up
No Lecture, Final Exam Week

Первое столкновение с действительностью

Расскажу про курс подробнее. Вводная лекция произвела очень благоприятное впечатление. Приятно говорящий (а главное, не бородатый!) дядька, хорошо оформленные слайды (потом узнал, что над картинками трудился отдельный дизайнер). Лекции записаны из реальной аудитории, слышно реакцию студентов (в основном смех). Рассказали, что понимают под AI сегодня, что изменилось с 50-х годов, показали видео из машин Google, а также своего робота, который аккуратно складывает рубашки и футболки. Мда, в моем ВУЗе передача знаний про AI началась и закончилась рассказом о тесте Тьюринга.



Минус для меня — это невозможность скачать видео с субтитрами себе локально.

Лекции хорошо, а практика? Ага на первой неделе имеем (Optional) Math Self Diagnostic, (Optional) Python Refresher.
Приведу здесь пример вопроса из раздела Math:

You are playing a solitaire game in which you are dealt three cards without replacement from a simplified deck of 10 cards (marked 1 through 10). You win if one of your cards is a 10 or if all of your cards are odd.
How many winning hands are there if different orders are different hands?
What is your chance of winning?

Собственно высшее техническое образование шепчет: «Где-то это уже было...» С помощью википедии математика вспомнилась. В python refresher было заглянул, но уверенность в своих силах, которая поселилась после Лутца и двух курсов, дала волю лени, и делать задачку я не стал, решив перейти к недели второй.

Поиск и деревья

С понятием графов и раскрытием поискового дерева был ознакомлен в ВУЗе. Поэтому ожидал, что будет скучновато. Но показанный преподавателем желтый старина Пэкмен удержал интерес. Depth First, Breadth First, Uniform Cost, Greedy, A*(with heuristic) Search — все это последовательно объяснялось, а в качестве примера служил Пэкмен, весело бегающий по лабиринту за точками в соответствии с алгоритмом поиска. И ни строчки кода в лекциях. Мне понравилось.

В тот же день с лекциями была осилена домашняя работа — графы и общие вопросы про жуков в лабиринте
А вот дальнейшая вкладка project 1 повергла в ступор. Скачайте архив (подробнее тут, спасибо Nbooo), запустите под python 2.7 pacman.py — поиграйте (можно запустить также с ключем -h для help). А теперь пишите свои функции в модуле search.py, ваш пэкмен должен найти еду в углу лабиринта. Вот так это выглядит.



Как же так, ведь как это написать нас не учили. Но раз уж взялся. Работа отставлена в сторону. В первый день было написано несколько кривых реализаций Depth First Search, пэкмен регулярно начал добираться до еды. Но они безжалостно удалялись, оказалось количество вскрытых поиском ветвей и оптимальность пути жестко контролируется. Тестируются ваши функции и методы автоматически, после загрузки исходных текстов на сервер. В очередной раз стерев страницу кода, бросил свой меч и взялся за орало. Листочки бумаги покрывались деревьями, рисунками пэкмена и лабиринта. Коллеги-электронщики считали своим долгом ухмыльнуться, проходя мимо. В итоге реализация была найдена. Кто хочет поучится — стоит помучаться самостоятельно. От тех кто на ты с питоном и алгоритмами, буду рад услышать замечания по делу.

Код

Думаю тут все понятно, util.Stack() и utilQueue() — фактически списки, обернутые в классы для удобства учащихся, с методами push и pop, FIFO и LIFO соответственно:

def depthFirstSearch(problem):
    """
    Search the deepest nodes in the search tree first

    Your search algorithm needs to return a list of actions that reaches
    the goal.  Make sure to implement a graph search algorithm

    To get started, you might want to try some of these simple commands to
    understand the search problem that is being passed in:

    print "Start:", problem.getStartState()
    >>> Start: (4, 3)
    print "Is the start a goal?", problem.isGoalState(problem.getStartState())
    >>> Is the start a goal? False
    print "Start's successors:", problem.getSuccessors(problem.getStartState())
    >>> Start's successors: [((4, 4), 'North', 1), ((4, 2), 'South', 1), ((5, 3), 'East', 1), ((3, 3), 'West', 1)]
    """
    def fromXYtoXY(coord1, coord2):
        '''
        tuple(int,int), tuple(int,int) -> str
        Takes near coord1 coord2 tuples, returns string way, or error
        sample for tinyMaze:
        >>>fromXYtoXY((5,5),(4,5))
        >>>'West'

        >>>fromXYtoXY((1,3),(2,3))
        >>>'East'
        '''
        if coord1[0]==coord2[0]:
            if coord1[1]-coord2[1]==1:
                return 'South'
            else:
                return 'North'
        elif coord1[1]==coord2[1]:
            if coord1[0]-coord2[0]==1:
                return 'West'
            else:
                return 'East'
        else:
            return ('Path not found from %s to %s' % (coord1, coord2))

    Fringe = util.Stack()
    currState=problem.getStartState()
    Fringe.push([currState])
    while True:
        currState=Fringe.pop()
        if problem.isGoalState(currState[-1]):
            listWays=[]
            fromState=currState[0]       # формируем выходной список с путями
            for state in currState[1:]:  # ex: ['South', 'West']
                listWays.append(fromXYtoXY(fromState,state))
                fromState=state
            return listWays
            break
        for State, Way, Price in problem.getSuccessors(currState[-1]):
            if not State in currState:
                nextPath=currState[:]
                nextPath.append(State)
                Fringe.push(nextPath)

Реализация Breadth First Search, по-моему, вышла уже немного красивее.

Код

def breadthFirstSearch(problem):
    """
    Search the shallowest nodes in the search tree first.
    """
    fringe=util.Queue()
    visitedNodes=[]
    fringe.push([problem.getStartState(),[]]) # сохраним стартовые координаты + нулевой путь

    while not fringe.isEmpty(): #пока в очереди есть чтото
        currNode = fringe.pop() #берем последний
        if currNode[0] not in visitedNodes: #если не было посещено
            visitedNodes.append(currNode[0])   #добавим
            for State, Way, Price in problem.getSuccessors(currNode[0]):
                path=currNode[1][:] #сделаем путь для дочерней ветки
                path.append(Way)
                if problem.isGoalState(State):
                    return path
                else:
                    fringe.push([State, path])

Потом были уже относительно легко реализованы Uniform Cost Search и A* Search (с Евклидовым расстоянием до еды в качестве heuristic-функции)

Код

def uniformCostSearch(problem):
    "Search the node of least total cost first. "
    fringe=util.PriorityQueue()
    visitedNodes=[]
    fringe.push([problem.getStartState(),[],0],0)
    while not fringe.isEmpty():
        currNode = fringe.pop()
        if problem.isGoalState(currNode[0]):
            return currNode[1]
        if currNode[0] not in visitedNodes: #если не было посещено
            visitedNodes.append(currNode[0])   #добавим
            for State, Way, Price in problem.getSuccessors(currNode[0]):
                path=currNode[1][:] #сделаем путь к дочерней ветке
                totalCost=currNode[2]+Price
                path.append(Way)
                fringe.push([State, path, totalCost],totalCost)

def aStarSearch(problem, heuristic=nullHeuristic):
    "Search the node that has the lowest combined cost and heuristic first."
    "*** YOUR CODE HERE ***"
    fringe=util.PriorityQueue()
    visitedNodes=[]
    fringe.push([problem.getStartState(),[],0],0)
    while not fringe.isEmpty():
        currNode = fringe.pop()
        if problem.isGoalState(currNode[0]):
            print 'Success!!', currNode[1]
            return currNode[1]
        if currNode[0] not in visitedNodes: #если не было посещено
            visitedNodes.append(currNode[0])   #добавим
            for State, Way, Price in problem.getSuccessors(currNode[0]):
                #print 'succ', State, Way, Price
                path=currNode[1][:] #сделаем путь к дочерней ветке
                totalCost=currNode[2]+Price
                path.append(Way)
                fringe.push([State, path, totalCost],totalCost+heuristic(State,problem))

Во второй части project 1 учащимся предлагалось видоизменить проблемы поиска в модуле searchAgents.py, адаптировав методы дочерних классов. Если раньше был один Пэкмен и одна еда, то теперь один Пэкмен и еда в 4-х углах, пройтись по которым нужно по оптимальному пути. А также придумать heuristic-функцию для A* Search, который призван сократить затраты на раскрытие ветвей дерева поиска (система оценки следующая: inconsistent heuristics will get no credit. 1 point for any non-trivial consistent heuristic. 1 point for expanding fewer than 1600 nodes. 1 point for expanding fewer than 1200 nodes.).

Закончился project 1 решением проблемы оптимального поедания множества точек в лабиринте.



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

Закончить хочу шутливыми словами преподавателя в одной из лекций:

Anything you want to do, NP-hard. Sorry, this is an AI class. Everything is hard.
Надеюсь, обзор немного помог кому-то. Курс (или просто порешать задачи) советую всем начинающим знакомится с python, а сам с нетерпением жду project 2.

upd. часть 2