As I decided to quietly teach a python, but I got into the wilds of CS188.1x Artificial Intelligence

Hi Habr, or introduction

I'll tell you a little background.

As once again, I was tired of picking up the next controller, the circuit and the pcb, and I decided that I was depressed by the average salary of an ordinary electronics engineer in the market - I want to be a programmer again.
')
I can not say that I was already a programmer, but I got an education 3 years ago in the specialty “Information Systems and Technologies” in Voenmech. And fate brought in electronic circuit engineers in the days of uni. Previously, frequent business trips to facilities were being saved (while young and single — interesting), and the last year was all completely boring.
Reading Habr, chose to myself Python.

These first second recent articles helped determine how and what to start.

Actually, on the recommendation and began in early September with the study: Mark Lutz. Learning Python, 4th edition. Clenching his teeth and clenching into a fist all that squeezed - on the remainder of motivation, read up to the 803rd page, doing all the exercises along the way. In the middle of the PLO I finally twisted. The book is good, but dreary - no strength.

I just didn’t want to quit, and then I tried Google’s python class. Wow, how cool it turned out to solve the final puzzle! Two evenings flew in an instant.

Then I realized that it was probably not the best option to press through a book. And he remembered that he had seen a post about courses in Western universities. I used to stop the knowledge of spoken English, but after all I understood Nick Parlante!

It is said - done, and here I am already enrolled in two courses. About the first already written here , about the second - here . And the fact that in one python 2.7, in another 3.2 is also better, I thought. After the meticulous Lutz, the first 2 weeks of both courses were snapped like nuts. Special thanks to the progress bar for motivation. And clicking on the links he was found - CS188.1x: Artificial Intelligence . What do they write?

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)

Cool! I will remember matan, I will train my little python for the time being, and nothing that the course has been going for the 2nd week.

First encounter with reality

I'll tell you about the course in more detail. The introductory lecture made a very favorable impression. Pleasant talking (and most importantly, not bearded!) Uncle, well-designed slides (later I learned that a separate designer worked on the pictures). Lectures are recorded from a real audience, students' reactions are heard (mostly laughter). They told what they mean by AI today, what has changed since the 50s, showed videos from Google machines, as well as their robot, which neatly folds shirts and T-shirts. Hmm, in my university, the transfer of knowledge about AI began and ended with a story about a Turing test.



Minus for me is the inability to download video with subtitles to yourself locally.

Lectures are good, but practice? Aha in the first week we have (Optional) Math Self Diagnostic, (Optional) Python Refresher.
Here is an example of a question from the Math section:

You can play three cards (marked 1 through 10). You can win if your card is a 10 or if your card is odd.
How many winning hands are there?
What is your chance of winning?

Actually, a higher technical education whispers: “Somewhere this has already happened ...” With the help of Wikipedia, mathematics was remembered. In the python refresher was peeked, but the confidence in my abilities, which settled after Lutz and two courses, gave vent to laziness, and I didn’t do the task, deciding to move on to week two.

Search and trees

With the concept of graphs and the disclosure of the search tree was introduced to the university. Therefore, I expected that it would be boring. But shown by the teacher yellow old Pacman kept interest. Depth First, Breadth First, Uniform Cost, Greedy, A * (with heuristic) Search - all this was consistently explained, and as an example served as Pacman, merrily running through the maze for points in accordance with the search algorithm. And not a single line of code in the lectures. I like it.

On the same day homework was mastered with lectures — graphs and general questions about bugs in the maze
But the further tab project 1 plunged into a stupor. Download the archive (more details here , thanks to Nbooo ), run under python 2.7 pacman.py - play (you can also run with the -h key for help). Now write your functions in the search.py ​​module, your pacman should find food in the corner of the maze. This is how it looks.



How so, because how to write it we were not taught. But since I took it. Work put aside. On the first day, several Depth First Search implementations were written, and Packman regularly began to get to the food. But they were ruthlessly removed, it turned out the number of branches opened by the search and the optimality of the path is strictly controlled. Your functions and methods are tested automatically after downloading the source texts to the server. Once again, erasing the code page, threw his sword and took up shouting. The leaves of the paper were covered with trees, pacmen and the labyrinth. Colleagues electronics engineers considered it their duty to grin, passing by. As a result, the implementation was found. Who wants to learn - it is worth torment yourself. From those who are with python and algorithms, I will be glad to hear comments on the case.



The implementation of Breadth First Search, in my opinion, was already a little more beautiful.



Then, Uniform Cost Search and A * Search were relatively easy to implement (with Euclidean distance to food as a heuristic function)



In the second part of project 1, students were asked to modify search problems in the searchAgents.py module by adapting the methods of the child classes. If earlier there was one Pac-man and one meal, then now there is one Pac-man and food in 4 corners, which need to be followed along the optimal path. And also come up with a heuristic-function for A * Search, which aims to reduce the costs of opening the branches of the search tree (the rating system is as follows: 1 point for expanding fewer than 1600 nodes . 1 point for expanding fewer than 1200 nodes.).

Project 1 has ended with a solution to the problem of optimally eating a multitude of points in the maze.



As a result, I spent almost 3 working days on solving these problems; well, there was some lull at work. It was interesting to break my head and hopefully useful in the future.

I want to finish with the funniest words of the teacher in one of the lectures:

Anything you want to do, NP-hard. Sorry, this is an AI class. Everything is hard.
I hope the review helped a little someone. The course (or just solve problems) I advise all beginners to get acquainted with python, and I myself am looking forward to the project 2.

upd. part 2