Into AI — Week 0
This has been an immersive week into Artificial Intelligence. This week I started working on the Udacity AIND, which meant a fast paced dive into AI right away. I also started to learn how to create new Amazon Alexa’s skills, and got two of them certified by now. It has been a great week!
Intro
My week started going to Udacity’s office in Mountain View and being part of two conferences about AI: the first one was about its medical applications, while the second one was an overview of the many applications it has in all the fields. Contrasting to web development, which has been the field that in which I’ve focused for almost three years, AI has the power to directly revolutionise different industries. Artificial Intelligence is changing the farming, financial, transportation, and health industries. Self-driving cars may be the thing we hear more about, but there are hundreds (or thousands) of places where AI is starting to be used to solve daily problems. Going to Udacity’s office was fun, even if it meant a trip of almost 2 hours from Berkeley. In addition, last week, Ashwin Ram, the Senior Manager of AI Science for Alexa, came to give a great and interesting talk about how Alexa was created and how it works.
Last year I read about many applications of AI: movie writing, creating songs, using machine learning to dress up customers, and even designing better AI software. I mean, when we are able to identify rare diseases with a simple picture, or improve cancer detection (and before any normal medical device can), you know that we are at another level. Reading all this made me really curious of how all of this works. So here I am.
Solving Sudoku with Constraint Propagation
A bunch on concepts have been thrown to me this week: AlphaBeta pruning, quiescent search, MiniMax algorithm, and many more. Solving a Sudoku optimally is a hard thing to achieve. Being the first project, it was a simple, deterministic and benign (no opponent) problem.
The key to solve this problem was good information representation (dictionaries!), and adding correct ways of handling the different constraints. Constraint propagation was like telling the rules to the computer: if there is only one choice to put the number, well, put it there; if you already put it a 2 in a row, well, now you can’t put a 2 in any other box in the same row (or column), so eliminate that from the dictionary. This was enough to solve the sudoku, but the problem was extended with diagonal sudoku (just more cells to check as peers), and naked twins optimization, which helped reducing the problem even more. After this, you only had to iterate between the different constraints until you got to a solution. Even if this isn’t exactly fully AI, it was a nice way to get into some of the basic concepts.
Game Playing using Search and Optimization
The next section was a deep dive into AI. The project here is to make an agent that wins in the isolation game. Probably you’ve heard about AIs that win in chess or in Go. You might I ask: “Why do we care to solve games?” In this kind of games, there is an opponent. This means that there will be uncertainty, making it hard to solve, so we can’t do the same that we did for the Sudoku. For example,Chess has a branching factor of 35, and an average game has 100 moves, so it would be 35^100. You know, big numbers.
When trying to solve this kind of problems, you create trees in which every node is a state. A state represents all the information needed to solve the problem. It might seem simple, but the problem itself gets very complicated because of the branching factor in the tree. The first thing that can be done is create an opening book, which is a list of suggested moves for the first turn(s). Then, MiniMax algorithm can be used. It has a pretty high complexity O(b^d) (where b is the branching factor and d is the depth), but I think it works in a really clever way. In one level of the tree the agent tries to maximize the result, while, in the next level, the adversarial agent (or human player) tries to minimize your result. Even if this is clever, it could take some years (1.2 million years being positive) to solve. So, MiniMax was not enough.
Different concepts need to be used for this problem to be solved. Quiescent search, iterative deepening and a good evaluation function are the keys to this. Iterative deepening is a clever way that will go as further as it can in the tree and give you the best potential move. This is useful because it will do shallow searches at the beginning but deeper searches in the end, when the branching factor is not as big. A good evaluation functions works as an heuristic to know if the solution is going on the right way. It is more complex than that, but I won’t get into further details. Lastly, another important concept was Alpha-Beta Pruning. It allows to cut certain parts of the tree and give the same good result than MiniMax.
Solving games seems like a really complex thing to do. Lots of things need to be considered. What if there are multiple players? What would happen if the game is a more complex one?
The cool thing about working on this project is that you get an overall sense of how AI works. I’m still curious about how training computers to do things work (machine learning), but I also want to go further into this. For now, the next path is to code the isolation game AI.
Conclusions and next steps
I’ve learned a lot of new things this week. Getting introduced to a completely foreign field to me has been great. I get a little scared of having to get all this theory into practical solutions, but I know that my skills are getting developed really, really fast.
As for now, I’m going to pause the working on this project specifically and will dive into a review by checking two courses: Design of Computer Programs, being taught by Peter Norvig, who is also the guy that wrote the leading book in AI; the other course is Intro to Artificial Intelligence, who is taught by Norvig and Sebastian Thrun, who is, well, just great. He has done too many things to mention it here.
Udacity community is, like always, great. It’s great to talk with the people in the Slack group, and you always meet different people.
See you next week!
