CS 372 (Artificial Intelligence) Fall 2004
Week8 (Due 10/25) Reactions & Thoughts
Ioana Butoi
MINIMAX looks pretty easy and intuitive. At least it looks like that in the case of Tic-Tac-Toe. In this case there are not very many moves and the strategies for winning are very simple. But when there is a larger board, things get more complicated. I wonder how effective the MINIMAX algorithm is in that case, since we cannot look too much ahead given the computation restrictions. Also given the fact that the board situation is more complicated, how good of a static evaluator can we write. The outcome depends almost only on the static evaluator.
How can we avoid symmetric moves? On a small board that is easy, but when the board increases that seems harder. Also as the game goes on, the situation on the board gets more and more complicated, so it is harder to look for symmetries. It is also true that as we evolve the number of possible moves decreases.
I don’t quite understand what a quiescent position is. Do you have to go even further that the max depth to make sure you are not too off track? How does that help the overall suggestion of a move?
Andrew Cantino
I have often wondered how game-playing AIs work. I knew that they had to do with some sort of search algorithm, but I'm pleasantly surprised to find out how simple the MINIMAX search is – even with the alpha-beta pruning, it's conceptually not very hard to understand. Granted, the static evaluation function compartmentalizes what in some games must be an incredibly complicated algorithm, but, still, the search itself is simple and tractable. II wonder about the static evaluation function – are there some games where it is nearly impossible to come up with a good one? It seems like the static evaluation function itself might often need to be some sort of search. I'm looking forward to trying to write my own game-playing program.For the final project, would something relating to computer vision be acceptable? I'd love to try to apply my computer vision experiences to actual robots. It seems like a robot could be trained to follow a person wearing a certain pattern of clothes. This sounds like a good challenge to me.
Audrey Flattes
When reading over my notes and the text. I find myself really confused about these added techniques. I think I have almost got it, but the Alpha-Beta pruning has still got me more than a little confused. When thinking about this class right now, I'm very interested, learning the different ways to search and semi-understanding them shows me the many different ways to solve a problem. However, I am still uncertain about how I will know which to use and when, but I'm hoping that will become more clear as we actually implement the different searches.Christina Florio
Now that I feel that I have a good handle on the gaming algorithm, I was thinking about how to write a program that gives the user multiple games to play. Using the same algorithm for each game, I assume you would have to write a "fitness function" specific to each game. But how complicated can that get? For example, in chess there are different rules depending on the playing piece, so would that result in a fitness function for each of those pieces and then a global fitness function? It all seems a bit overwhelming just thinking about the coding necessary to make this work, but it also seems very interesting. It requires that we breakdown everything, moves and rules, to a simple algorithm or function, but at the same time never forgetting the complicated overall structure. While just thinking about the difficulty of putting all of this together, having a program that would allow a user to choose from a multitude of games would be a great accomplishment considering my current knowledge of gaming algorithms.
Kathleen Maffei
I was thinking about games of chance and how they would be handled by MIN-MAX search algorithm. I know that each whole dice roll would be included as a layer of the game, with each result as a branch. And I know that we’re to assume that the opponent will roll the best possible result. The problem is that in most games I can think of, determining the best result isn’t so easy. There are complex rules and the current game situation often determines the value of each dice roll (or card deal).
For example, in Parcheesi if you roll doubles and if all your pieces have left home, then you get to move pieces 14 spaces in increments based on the tops and bottoms of the dice (i.e. double 5s means you can move 5, 5, 2, and 2) and you get to roll again, but a third roll of doubles in a row is bad. A roll may be exactly the number of spaces a piece needs to move to jump an opponent’s piece or to land it on a safe space, or it may place it in jeopardy. The value of a roll, in other words, depends on a good deal of board evaluation.
It occurred to me that if one were to implement such a game, the evaluator function would have to be terribly complex. It seems to me that it would make much more sense to store evaluations for each node rather than re-evaluate any node during a game (trading memory for speed). If the evaluations are being stored, then it only makes sense that it could serve two more purposes: as a way of sorting the successors to allow for efficient alpha-beta pruning, and also to help eliminate duplicate situations in the same search tree. In this way, there would be a great increase in efficiency to help make up for the complexity of the evaluator function. Unfortunately, this would take a lot of memory.
Sara McCullough
I also really admire the simplicity and functionality of the minimax algorithm and the alpha-beta pruning. They are obviously great game playing or programming strategies. The fact that chess-playing machines can beat even the world's best players is truly impressive. However, I find that I am somewhat losing touch with the aspect of Artificial Intelligence here. It just doesn't seem to me that the computerized chess players are portraying a human-like intelligence. An understanding I have of AI is that it is an effort to understand human intelligence and re-create that in machines. The chess-playing programs seem more like high-end programming. The chess programs in particular are successful because of a computer's ability to explore huge numbers of potential future moves by both players and then apply a relatively simple evaluation function to the search results. Wouldn't it be more of a challenge relative to the field of AI to attempt to write a program that could play a game like Go? It just seems that much more contemplation of concepts is involved in Go than in chess. I would think that programming a Go-playing machine would be much more of a profound problem in AI than programming a chess-playing machine, but the situation seems to me to be just the opposite.Ben Root
I just played Go the other night and it is hard. I can imagine why computers have so much trouble playing at a level better than an amateur person. At any given time there are a ton of moves which could be made so the branching factor of the search tree is much higher than chess or checkers, and as the game progresses the number of available moves doesn’t really decrease that much either.Static evaluation is what really is interesting to me. While minimax is a pretty clear search algorithm, e() is where the creativity and hard work comes in. I usually think of good board game players as knowing which moves are better than others. It is no small feat to design algorithms which discern good board positions from bad, and I think it will be fun to attempt to strip a game like checkers down to its most essential components. I can imagine that after this I will be a better checkers player.
After programming the robot wall-following behavior I understand what you meant about “simulators are doomed to succeed.” Mostly the sensor data that I got from the robot was very anomalous. Using the Khepera, each sensor gave different values to obstacles at the same distance away. In the end I decided to make each sensor into a Boolean value (e.g. "I see something" or "I don’t see anything") and this worked and allowed the robot to stay close enough to the walls.
Sandeep Singh
I think it should go without saying, as pretty much everyone has pointed out, that the evaluation function is both the heart of the program and will prove to be the most complex. After reading the book and consulting a few other resources, I think I finally understand how the mini-max algorithm works. Player MIN’s object is to minimize the possible outcomes for MAX, while MAX will try to select the more beneficial move that has the highest possible outcomes. Although I have never played Go, I’ve read enough to understand that while the probability that two Go games are played exactly the same is infinitesimally minute, the possibility of moves becomes more predictable as the game progresses. Consequently, it’s pretty obvious to see that a search tree for such a game would have an insanely large branching factor. I found this interesting site (http://www.wordiq.com/definition/Computer_Go) that makes mention of different concepts behind computer Go. As I had speculated earlier, the site states that although Go can be represented mathematically relatively easily, the numerous amount of possible moves makes such an algorithm and approach very complicated. What caught my eye on this page is that it says that neural networks and genetic algorithms are at the forefront of approaches in Go sims. Despite the fact that they would ‘bypass’ the problem with the high branching factor, I strongly feel that programming the neural net for a Go game would in itself be a difficult challenge. This other website (http://satirist.org/learn-game/systems/go-net.html) talks about a Go neural net that was developed at the Salk Institute. The developers found that training against experienced Go players was much faster and efficient than self-play training. This network used two layer back propagation to learn and study hundreds of thousands of training games. This whole idea of game playing AI agents and adversarial search is something that’s very appealing and interesting to me and is something I definitely want to look into meticulously.
Darby Thompson
Everyone seems to be so hung up on the evaluation function, and I tend to agree that it's a pretty complex problem. The minimax algorithm itself is a fantastic compact gaming algorithm, however the evaluation function and expand method are going to be the complex modules. As we saw on the TICTACTOE program, the option which leaves you with the highest probability of winning can easily be cutoff/ignored using an evaluation function which is imprecise. The 'perfect' evaluation function would have to take into account the entire tree and calculate the probability of a win/draw at all the leaves and then propogate the probability backwards up the branches. If this were possible (as it is in an easy game like tictactoe), then we would have an unbeatable game. I like Kathys suggestion that we associate a stored evaluation function with each node/state. It would make sense to have some kind of hash table with states and the eval function, taking up more storage, but decreasing CPU time at each play. What if we ran the calculations on a huge cluster before the game play and stored the values? If that's still too much, how about assuming our opponent will play the best move and therefore trim the tree at every opponent's node - having a branching factor of 1?
Writing the expand function must also be pretty complex for a game like chess... you're dealing with a matrix, yes, but with different pieces which each have different rules of moves. Is it possible to boil all these down to simple matrix operations to see if a move is valid? I guess it would depend on your representation of the different pieces.
Since I am absolutely terrible at games like Chess and can't see a good move when it hits me over the head, it's a bit daunting to think of coming up with the eval function or even implementing the known strategies.
