About me
I’m currently taking a 3-semester break from my 8-year software development career to pursue an MS in Computer Science with a focus on AI at the Georgia Institute of Technology.
This online portfolio is a supplement to my professional resume. It does not delve into great detail regarding topics specific to artificial intelligence, although links to online resources are provided. The code excerpts and brief project summaries are intended to show that AI techniques can be simple to implement and solve concrete, real-world problems.
- Interested in knowing about algorithms beyond quicksort and binary search?
- Need pseudo-text for a website but don’t want to use Lorem Ipsum?
- Want to know which products might appeal to a customer based on survey data, if there is no exact fit?
Read on!
Foundation: Reading and Assignments
In the course, we completed 8 assignments on the foundations of AI, covering numerous algorithms applicable to a wide range of search, constraint satisfaction and language analysis.
1. Reading: AI: A Modern Approach by Russel & Norvig, Chapter 3. Algorithms: Dijkstra, A*, bi-directional A* and path-finding using landmarks. Applications: route-planning, games, graph search.
2. Reading: AIMA Chapter 5. Algorithms: Minimax Search, Alpha-Beta pruning, Constraint Satisfaction. Applications: games, puzzles.
3. Reading: AIMA Chapters 7-9. Algorithms: proof resolution, knowledge engineering, forward & backward chaining. Applications: planning, proofs, rule-based systems.
4. Reading: AIMA Chapters 13-14. Algorithms: Bayesian networks, Markov chain Monte Carlo, Gibbs Sampling. Applications: reasoning under uncertainty, approximate inference.
5. Reading: handout. Algorithms: Hidden Markov Models, Viterbi, Forward-backward. Applications: music, language and text classification.
6. Reading: AIMA Chapters 22-23. Algorithms: N-gram language models, Laplace smoothing, back-off smoothing, syntactic analysis. Applications: Language identification, speech recognition, machine translation.
7. Reading: AIMA Chapters 17-18. Algorithms: Markov Decision Processes, k-d trees, entropy. Applications: decision problems with noisy data, learning from data.
8. ‘Reading: handout. Algorithms: Markov Logic Networks, factor graphs. Applications: probabilistic reasoning.
Because my only previous exposure to AI at the university level was a single semester of Knowledge-Based AI, many of the techniques covered in these assignments were new to me. The opportunity to survey the breadth of current AI techniques over the course of the semester proved invaluable. Some exercises such as Bayesian Networks were largely a review of my previous professional work; others in particular those involving factor graphs and Hidden Markov models were more challenging.
Skills: Mini-projects
There were three mini-projects in which I chose to research a problem that was supposed to be relevant to my your future career. For each of these three projects, I proposed a solution, implemented it, and described it in a mini-conference paper.
My favorite Project
My favorite mini-project of the three was on the topic of Computer Go. Go is a 4,000 year-old board game in which two players take turns placing white or black stones on a grid of intersecting lines (9×9, 13×13 or 19×19) with the aim of surrounding the most territory. Although the rules of capture and scoring are very simple, it remains one of the unsolved ‘grand challenges’ of AI due to the enormous number of possible games and board positions. Unlike checkers or chess, Go is one of the few simple board games where even the best computer programs cannot challenge human professionals – yet.
Problem Addressed
The game of Go is a conundrum in the field of artificial intelligence. The number of rules and types of pieces are smaller than those of chess or even checkers, games which have both seen the successful application of various AI tree search, pruning and heuristic techniques. However, computer agents for go are currently unable to compete with strong amateur players on the full-sized board or regularly defeat professional players on even the smallest board. This is because several aspects of Go make traditional tree search techniques impracticable for Go. These elements include the huge branching factor of the board, the percentage of potential moves which are legal and the non-monotonic count of pieces on the board. We chose to focus on this problem as it has remained unsolved since the first computer Go agent was devised by Albert Zobrist in 1970 1?. In particular, we focus on solving games on small sized boards, where the branching factor is more manageable. In this paper, we developed a tree search algorithm to play go, which we test against the state-of-the-art Monte-Carlo algorithms.
Related Work
We chose to focus on this problem as it has remained unsolved since the first computer Go agent was devised by Albert Zobrist in 1970 . In particular, we focus on solving games on small sized boards, where the branching factor is more manageable. In this paper, we develop a tree search algorithm to play go, which we test against the state-of-the-art Monte-Carlo algorithms. Despite the challenges faced by classical approaches, the field of computer Go has seen dramatic advances since the use of Monte-Carlo techniques to evaluate the best next move was first proposed in 2006. This approach for computer Go has several weaknesses, however. For example, it is always possible in a Monte-Carlo simulation, which relies on random sampling, that a clear best move is simply not contemplated. It follows from this that these agents can fail to pick the best sequence of play especially when the order of moves is important, which is quite often the case in Go. Furthermore, each position is represented individually, and Monte-Carlo agents make no attempt to represent relations between related positions. This means that these approaches are entirely depended on a random sampling to explore the gamespace.
Some researchers have partially mitigated these weaknesses with hybrid algorithms, such as UCT-RAVE , which “forms an online generalization between related positions, using the average outcome of each move…combining this rapid but biased estimate of a move’s value with the slower but unbiased Monte-Carlo estimate”. However, even UCT-RAVE, like the basic Monte Carlo method it is based on, is not exhaustive and can be shown to overlook an optimal play if the random sampling is poor.
Approach
We use established algorithms to develop four autonomous Go playing agents: Random, Minimax, Alpha-Beta and Monte Carlo. These agents are pitted against each other using the online match making service “KGS Go.” This service allows people from around the world to play Go against one another over the internet. Our players log onto the Go server with a screen name just like a person would, enter a game, and start playing. (As an aside, this could be interesting to set up as a Turing test, since the server provides a human opponent no indication that he or she is playing against a computer.) We test the tree-search algorithm’s effectiveness versus Monte-Carlo by having them play a series of 10 games against one another on 7 by 7 board.
Results
We focused on the matches between the Alpha-Beta player and the Monte-Carlo player. This is because minimax is strictly worse than Alpha-Beta since it is slower, and the random opponent did not win any games, unsurprisingly.
Qualitatively, we found that Alpha-Beta will make tactically solid defensive formations, visible as the diamond shapes in the upper portion of this screenshot. Monte-Carlo tends to explore more of the board and is quicker to play the center, but fails to develop solid defensive structures.
Quantitatively, we show the results of our ten game series below.
What I learned
At a basic level, this project served to confirm my understanding of the relative merits of tree search and Monte Carlo methods. We were not at all surprised that the provably optimal Alpha-Beta search outperformed the stochastic Monte Carlo method for this constrained exercise. However, it was instructive to see that by looking only 3 moves ahead (for each player), the agent could constructive basic defense structures with no a priori knowledge of Go strategy.
Writing the proposal and having it critically evaluated by my peers was very educational. I had participated in independent research as a high school student and undergraduate, but had not written a project proposal in almost a decade until taking this course. Consequently, my initial effort was found lacking in persuasive qualities and clarity of focus. I am glad to have had the opportunity to revise the project proprosals and resulting papers, and feel confident that I now think more critically about the effectiveness of my writing. While I intend to return to the software development industry after graduation, I know that the ability to express oneself clearly is just as valuable in business as academia.
Why This Was My Favorite Project
This project was fulfilling on a personal level because it was my first complete effort to write a game-playing AI, and it was amazing to see the occasional opponent connect and play against this program as we gathered data for the evaluation. Finally, this project had ramifications for my study beyond the duration of this course because it inspired me to continue studying computer Go and tackle the more ambitious aim of developing a competitive Go agent for my MS Project during the fall 2012 semester.
For more information regarding any of the mini-projects for this course, see the complete reports:
Project 1 “Tree Search vs. Monte-Carlo in Go for Small Boards” with Stephen Motter
Project 2 “A Bayesian Approach to Collaborative Dish Selection” with Daniel Kohlsdorf
Project 3 “Predicting Stock Trends Using Natural Language Processing of Headlines” with Rowland O’Flaherty
Final Comments
In the course of completing CS6601 in the Spring of 2012, I
- was able to master search algorithms beyond those taught in undergraduate courses.
- gained a greater appreciation of Machine Learning techniques which can help make sense of vast amounts of data “in the cloud”.
- planned, implemented and presented several software projects on 2-3 week development cycles.
Apart from these concrete results, the continual practice of research-planning-implementation-presentation has enhanced my ability to reason critically and work as part of a team. As a result, I am now more prepared to complete my graduate studies and apply these lessons in my professional career.