Into AI- Week 1
This is the second week working through the Udacity AIND and diving into Artificial Intelligence. It has been focused on implementing four key concepts: MiniMax algorithm, Alpha-Beta Pruning, Iterative Deepening, and developing my own heuristics.
Reviewing Concepts
I started this week reviewing basic concepts from Udacity Intro to AI course. It was useful to review types of problems (fully vs partially observable, deterministic vs stochastic, discrete vs continuos, benign vs adversarial). After that, I reviewed problem solving and search problems techniques. It helped me to review the common tree search functions like DFS, BFS, and A*.
As I mentioned last week, I’ve been working in an AI that can play Isolation. Just to give an overview, there is a board and two players. That makes this problem more complex than sudoku because of the adversarial component. In adversarial games, you assume that the opponent is going to try to minimize your score while you’ll try to maximize your score.
Now, in the game, you can move your piece to any empty square. You can move as a knight in chess (but you can also play it using the movements of a queen, or any rules you define). Once you move your piece, you remove the square from the game, so now nobody can go to that space.
There are many approaches when working in playing agents. MIT Open CourseWare has a nice way of introducing to this concepts. As you can probably guess, using a lot of if-then rules (like some people do to solve Tic Tac Toe) can’t be used when there are too many possibilities. So, what can we do? We can look ahead and evaluate which is the best movement. This is still not a good solution because of a big branching factor. What do I mean by this? When you have many possibilities, you need to test all of them, and then test the possibilities of the possibilities. Let’s say that there are 25 places (in a 5x5 board). The branching factor can be huge! In this point the only thing we can do is look ahead, and evaluate, but just as far as possible: here we have MiniMax.
MiniMax, AlphaBeta, and more
As mentioned, AI can’t search far enough into the tree to solve the problem. This is called Horizon Effect. So, we need a clever way of handling so many possibilities. I won’t dive too much into how this algorithms work, but I’ll give a general overview of why they are too useful for adversarial games. Even if this a specific example with 2 players and no probabilities (not stochastic) involved, this algorithms can easily adapt to add more players, and add a luck component (for example, Poker).
Minimax looks in the tree, and returns a suggested movement and a score for that movement. As mentioned before, we may not be always capable of getting to the end of the tree. This is why we use Iterative Deepening, which will traverse the tree as far as possible until the time runs out. It would not make sense to have a game agent that takes days to play. This gets a complexity of O(b^d), with b being the branching factor and d the depth. This isn’t too bad for being a game. But there’s a clever way of making this better, it is called Alpha Beta pruning, which is nicely covered in the Berkeley CS 188 demo.
The algorithm will go the deepest it can in the tree. What happens when the time is up? Well, it will run an evaluation function. An evaluation function is based in a heuristic. This was the hardest part of the problem. The idea is to receive a state of the game, and give a numeric value to it. The highest the value, the best the state of the game. It is hard to find a good heuristic that is flexible enough to work in most of the cases.
Once I got the heuristics, I followed a testing tournament in which my game agent plays different types of agents. Overall, I got good heuristics that normally get to win the game. It depends a little on hardware, but it wins from 60% to 85% of the times.
Conclusions and next steps
I’ve talked with many people that are worried about starting to learn AI. My first suggestion is to make your Python skills stronger. Second suggestion, start! I know AI sounds really scaring, but it is easier than it sounds. You can take the free course at Udacity: Intro to Artificial Intelligence.
I’ll keep working in improving my agent, and start doing some research on Deep Blue, AlphaGo, Min/Max approximation, and other papers. I may also begin building something with Tensor Flow.
Have a nice week and see you soon!
