CS372: Artificial Intelligence (Fall 1998)

Week 6 & 7: Responses

Readings



Diana Applegate

This week, we looked at searches - Nilsson's chapter 8 dealt specifically with uninformed searches, including depth-first and breadth-first. I really don't have much to comment about regarding this chapter...it seemed relatively straightforward. I'm sure that more questions will arise in my head as we begin to apply these searches in our upcoming programming project.

However, I do have an interesting story of sorts to share that indirectly relates to our class discussion. When talking about the Hawaiian checkers game, or games like chess, tic-tac-toe, etc., we mentioned that, as programmers, our job was to try to help the agent make the most intelligent move at any given point in the game. In other words, we have to assume that the agent always wants to make a move that's in its best interest. This may seem like an extremely obvious claim that isn't even worth repeating. However, in philosophy, this idea is known as the Intentional Stance, and is seen as having noteworthy predictive power. Right after lecture on Thursday, I had to finish up some last-minute reading for my Philosophy of Cognitive Science class. And it just so happens that we're reading Daniel Dennett's The Intentional Stance. The Intentional Stance says that we assume that other agents, or human beings, whatever the case may be, will act how they "ought" to act. This translates into acting in one's own best interest. This, of course, isn't an assumption that we usually make consciously, but is a very powerful and important one nonetheless. The subject of intentionality is quite a controversial one in both the realms of philosophy and AI, and I can't really go into it fully here...but for those of you that are interested in this sort of thing, do check it out.

Moravec's chapter 3 brought out some interesting points. It was neat to see how he described such environments/systems that we now call "virtual reality" or VR. His discussion of the magic glasses was only the beginning as far as that goes...I spent part of my summer at UPenn's Institute for Research in Cognitive Science and got to see some of the VR experiments in progress over there, including their Interactive Jack project. I got to see a demo of a VR glove in action. I also saw a demo where a student was actually wearing a "VR suit" with wires/nodes/sensors mounted just about everywhere imaginable. These wires were then connected to a computer, and the student's movements were quite accurately modeled by the figure on the computer screen. What I found to be most interesting were the numerous "reall-life" applications of VR. There are some great websites detailing this research, but the URLs allude me at the moment. I'll post the links on Group 4's webpage as soon as I can dig them up. In addition, Moravec made mention of a navigation system that could be implemented in cars to aid the lost. I just recently saw a car commercial (forgive me for not remembering the make of the car) that had exactly this built-in. The system had iconic representations of streets, landmarks, gas stations, etc. and was able to help out the lost driver in a number of ways. Well, that's about all I have to say for this week...I'm looking forward to learning how to implement the Minimax algorithm in our next programming project, which will be a challenge for sure.



Jocelyn Arcari


The diagrams of the 8-Puzzle were helpful in trying to separate the differences between depth-first searches and breadth-first searches. If we had a really large problem which could not be represented by explicit graphs, though, which is the optimal search method. Is it always the A* search method? Is there a good way to keep all of these straight in my head? The text reading is a bit dry with regards to these search methods... I was also wondering if we would see an example of an adversarial search -- perhaps in lab on Monday as demonstrated by one of the robots in the film?

The background given in Moravec's chapter 3 on programming and how some computer languages developed over time was interesting. The amount of time it took to run one program at a time, find an error, print out the program and have a programmer labor over it until mistakes were found would be so inconvenient compared with the speed we are able to write programs now. If we had to practice this batch mode of computer operation today, advances would be so much slower. Time-share systems are definitely an important discovery.

I found the other portions of Chapter 3 in the Moravec to be extremely exciting. Again, Moravec makes a claim about computers that in 1/2 a century, a robot will exist which has reasoning abilities "astonishingly better than a human's." If some of the technology discussed in this chapter is developed, it would open the doors to a whole new realm of exciting products. I do not know how well magic glasses or gloves have been developed, yet. I know some cars have a map-system in it to help the driver on trips, but if there were a system as detailed as the one described in the book to help someone arrive at a friend's house, I would definitely buy it. The other example of "walking through" the blueprints of a person's house was an incredible idea. Does anything like this exist today?? All of the short stories of people interacting w/ their programs were great. I'd like to know to what extent any of these have been successfully accomplished.

Finally, in lab, it seemed that many groups had difficulties in getting the robots to respond as we hoped they would. The second week and the chance to re-work a specific area of our program is a welcome assignment and hopefully, the second try will be better. I look forward to viewing the clips of different robots in lab tomorrow. I am excited to see more of what has already been accomplished.



David Costello

In the book Mind Children, Moravec states that all digital computer after ENIAC incorporates machine language. Programming environments (like C) translate code written by the user into this machine language so that the computer can implement algorithms. What I don't understand is why we can't have the programming language be the machine language so that we can skip the compiling step? One other question I have concerning Mind Children has to do with the author's statement that it is not yet possible to embody true general language understanding in a program. Since this was written in 1988, I was wondering if there had been any progress in this field?

I just have a couple of questions from last weekís lectures. When you were describing the adversarial search algorithm, you made the assumption that there were 2 agents with perfect information playing in a zero-sum game. Is the definition of perfect information similar to the economic definition? Also, is a zero-sum game a situation where you either win everything or lose everything or am I thinking of another type of game? Besides those little questions I pretty much understand the search algorithms as well as pruning the tree of branches which do not need to be searched.



Sonia Dubielzig





Ben Flynn

This whole business about game trees has rekindled my childhood aspirations of one day writing a computer game that was halfway decent. I have for some time wanted to write an update to the Electronic Arts classic, Lords of Conquest, but have yet to do so. LOC is Risk-like in nature and was based on a board game. Although much more complex than TicTacToe, I can see how the game could be reduced to game tree. Later in the game, the complexity of look ahead might become too large for it to be an effect agent on its own accord, so it would take some thinking as to how to simply the search algorithm.

In discussing TicTacToe, I also had the idea that two computer opponents, under the guidance of a referee, could learn how to play TicTacToe from scratch using the neural nets we talked about recently. If we were to keep track of all the state transitions and then to back-propogate a weight adjustment through them at the end of a game, we might be able to create a scene like that at the end of Wargames, when the Big Whopper is deciding how it can win a nuclear war. I think that would be rather exciting, especially without the risk of nuclear holocaust. Those are thoughts for this week. See you this evening at the movie.



Emily Greenfest

I just have two little things to comment on this week. One is just a small pet peeve that I feel like sharing, especially because I believe many people share my frustration. It is about the programming assignment. Having started it, I realize that the main goal of the assignment is to implement the static evaluation heuristic (the tree and minimax being secondary as hopefully we (the programmers) are familiar with trees and minimax is actually a rather simply algorithm). However, I just wish to state quickly that I believe that to be slightly ... trying (implementing the heuristic) ... not because the coding will be difficult but because it involves learning to play the game well enough to determine what consitutes a "good" move. It may be (I've not really fooled around w/the playing of the game quite yet) that that is a simple problem, but then again, I've played chess for 15 years now, and I'm still never exactly sure (well almost never) what is a good move. And if you asked me to quanitfy one, I do not think I could. But, according to some, checkers is a simpler game .... so how does Konane rate against good old western checkers?

That being said, I also have a little something I want to bring up about the class in general. So far, we've seen little that I would call intelligence -- but I think that is because of my perspective. I have shared my robots and seen someone comment on their behavior, emotions, or thinking skills, but I know better. So, here's my questions: do we call a "computer" intelligent when we (the creator/programmer) find it to be intelligent or when the casual observer is convinced that it is intelligent? In other words, perhaps it a more appropriate version of the turing test would be to have the computer be matched against its creator -- if it can convice someone who knows without a doubt that it is a machine that it is intelligent perhaps i might be convinced.

I guess, my point is that I see a lot of outgrowths of AI that are helpfule in some field or another -- e.g. complexity studies, machine learning algorithms, gas, searches, etc. -- but little that makes me the programmer feel as if real progress toward modeling intelligence is being made. But then again, perhaps I have the wrong perspective on the goal of AI.



Ayishih Hakim





Ada Hogan

In the implicit state space graphs, how long is the new state "remembered" after an action has been performed? Is it stored until a goal is attained?

I was also trying to decide whether uninformed or heuristicprocesses would be more useful; but it seems that each process really replies to what kind of information is available. I think that if we want to consider these as decision makers and learners, a search that does not depend on additional information to run in its world might be closer to human learning. It seems, however, that the breadth first search would be fairly slow since it applies all operators to the start node, and then all operators to successors of the start node - not necessarily recognizing the most efficient path. I might wonder, too, what is more time consuming: simply trying to find the goal node, or trying to establish the most efficient path that would lead to the goal node. In the breadth first search of the 8 puzzle, what keeps the blank from moving back to a position it already held?; are the moves held in the memory until the goal node is attained?

Chapter 10:

I gathered from the reading that most of the problems associated with search based planning stemmed from physical changes in the environment. How accurate is it really to forsee the actions through probablilty distribution? We've already established that planning out every move on some searches would be too large a task, requiring too much memory.

How can we, then, effectively theorize which action might be initiated? It seems like we have to make a lot of assumptions for these architectures to work ( the computation time mustn't be too long; the agent must be in a benign environment; the agent must take accurate information, etc... ) This seems like a lot: even if agents are accomplishing certain tasks, it's being done in an unreal world.

About hierarchical searches: are the steps of the "macro-operators" completely random? If the islands that form the base of the metalevel supergraph are random, won't it run into paths that are non-optimal, like the breadth first search? The question of time and effectiveness keeps reappearing in all these searches; I thought that the limited horizon research responded to the restrictions of the previous searches, but then it might be much slower since it is constantly re-evaluating it surroundings.

I think it's interesting that progress in AI is so often measured by an agent's actions in a game such as chess or checkers; again, it makes me wonder what kind of "intelligence" is being sought after. The search techniques are mathmatical. Are we defining human intelligence, or reasoning, in this way as well?

Again, I liked Morevec's historical approach to his writing; it was interesting to consider the evolution of computers and programming as a progression twards a human/ robot partnership. I think it's surprising that with all of the effort to make computers user friendly, that programming languages are still hardly accessible to every user. It's true thast in other ways the computer is much more user friendly- the laptop takes up a lot less place in my room than the ENIAC would. But even if money and time is being put into researching magic gloves and glasses, I have a hard time imagining these devices really integrated into our lives in the next fifty years. In the 1980's there were cars that would "speak" to you (your door is ajar...) but even that is far from being a common characteristic in automobiles.



Peter Ingebretson

The minimax algorithm is a specific form of the general procedure for playing games:

1) What move should I make?

2) What moves can I make?

3) What would the results of those moves be?

4) What moves could my opponent make if I did this?

5) What would be their best move (my worst move)?

5b) I.e. What move should they make?

This procedure, when recursed infinitely, guarantees that a player who can force a win or a draw will; it makes sure a player will make the best move possible to them. The minimax algorithm comes from the impossibility of recursing this process infinitly. A heuristic on a state is just an approximation of the function h(s) = { +inf if the current player has won, -inf if they have lost}. Since it is a pretty good approximation to a perfect algorithm, it seems that it should be unbeatable.

This is why it seems strange to me that people can beat computers at games (although the number of games solved by computers is increasing). What skill do people have, what algorithm, that enables them to play a game such as chess or go at a high level? I don't know, but I think it has something to do with the way that the minimax algorithm limits itself to examinations of only specific moves and pieces, and isn't concerned with patterns on the board. I don't know how a better algorithm would look, but I think that one must exist.




Sarah Klaum

I found chapter 10 in the text fairly straight forward. The few comments and questions I have are as follows: Island-Driven Search--is this just a very general description given before elaborating on it in the section on hierarchical search? I found this slightly confusing. It brought to mind the configuration spaces (with robots--I am not sure I am using the proper term here) that we discused in briefly in class, but I am inclined to assume there is no connection between these two concepts.

The topics of learning heuristic and evaluation functions (the latter covered in chapter 12) proved interesting, although I once again found myself floudering somewhere in the middle of the applicable equations. For now I am satisfied to have gleaned a general understanding from the text of the process, and I am intrigued.

Two-agent games and adversarial search is what I find most exciting among this material. I think the minimax and alpha-beta procedures are easily comprehended, and yet at the same time they are quite clever. I would like to see the topic of games of chance covered, if only briefly, in class. The example of Backgammon and the dice throw is informative, yet I was only able to abstract so much from the description in class, and I feel a bit more clarification would be welcome.

As usual, I enjoyed Moravec. His scenarios were entertaining, yet I found myself questioning his approach. The symbiosis he protrayed is not unique; that is, others have envisioned similar scenarios for the future. What I mull over most with such projections is the question of how far removed we will become from the reality of our surroundings and regular human-to-human interaction if we are constantly presented with computer models, psuedo-human interactions, and map on which to base our actions?



Maralee LaBarge

Well, unfortunately we skipped a part in the book that I was really looking forward to and went into a less interesting part for me. The discussion of search algorithms and graphs smacks just a little too much of Discrete Math which road I walked down awhile ago and have been trying to avoid as much as possible ever since (though Minimax is a decent algorithm).

What we missed was Robot Vision which is one subject I've never learned enough about to say I know all that much about it, but the idea fascinates. Seeing, in its way, is so easy for human beings. We take it completely for granted. I mean, there really is no other sense that we rely on more to tell us about our environment, to navigate new situations. Not to say that not having eyesight somehow renders someone unable to function, but its a serious debilitation. And so far, robots have been sightless, so we have to really suck the other sensors for all their worth.

Will we ever be going back to the chapter on vision? Or at least have some kind of discussion about how vision works in animals and why it's so difficult to create a vision system for robots? Or techniques for vision? I was really looking forward to going over that.

Unfortunately, since we bypassed vision, I'm a bit at a loss for something to say about graph-searching. Anyone who chugged through Chapter 9 saw that we were entering the realm of proofs and theroems. There's a reason why Alice went to Wonderland and not DiscreteMathLand.

Okay, so that's not fair to those who find that interesting. I just don't belong to that group, which leads to wonder how our own brains process similar kinds of problems. We know that we make a sort of graph or tree in our head when it comes to game playing of this kind. Staring at the eight-puzzle, I immediately started pushing blocks around in my head and when one idea didn't seem to be working, I would back out to where I thought I had a good path to a solution and start again. Well, this eight-puzzle was trivial, but it seems to me that the better we are at a game, the more likely we are to use heuristic searching, better and better heuristics as we become more and more skilled. Sometimes when we have no idea how to play a particular game, we do a blind search where we start trying different options--but then we DEVELOP a heuristic search as we start figuring things out. And the longer we play, the more perfected that heuristic becomes. The reason games are still interesting is that it is STILL a heuristic, no matter how well-developed, and it doesn't guarantee a right answer. If we know how to beat a puzzle, then we won't bother.

So this is leading to a connection between some of the learning systems (neural nets and whatnot) and the graph-searching algorithms we've been studying. Rather than make the human come up with a decent heuristic and programming a robot to execute that algorithm, what if we could give a robot certain skills and methods for exploring games and the ability to use the results of those methods for building an algorithm, and then improving that algorithm. I mean, there's always genetic programming, but that's not what I'm talking about. GP and GA's just generate a bunch of ideas and then and through some speedy natural selection and a touch of randomness, come up with an optimal solution. What if we could teach a robot how to teach itself heuristics? Then we probably wouldn't study all these theorems and proofs, except to see if a robot developed the same kind of ideas we did.

Or if it came up with something different--and better.


David Rothstein

I found the discussion of game-playing search algorithms which we began on Thursday to be very interesting, since it is something that I have a bit of experience with. For my final project in CS 105 at Haverford last year, I wrote a program to play tic-tac-toe. The algorithm I used actually wound up being somewhat similar to the minimax procedure (although I didn't know it at the time). The main difference was that mine did not make use of static evaluation functions per se -- instead, it simply searched the entire game tree until it reached every terminating node, and returned "win", "lose" or "tie" from that point. The advantage to my program was that it was absolutely guaranteed never to lose, but the disadvantage, of course, was that my algorithm would not have been practically feasible for a more complicated game than tic-tac-toe.

Actually, my original plan for the tic-tac-toe program was to try to model the system as a collection of rows, columns and diagonals that each had a certain number of X's and O's in them. That wound up being too complicated, but if I knew then what I know now about static evaluations, I think I would have been able to program it rather easily. I probably would have chosen a slightly more complicated static evaluation function than we discussed in class -- instead of just counting open lines of attack, I would also have given extra weight to the situation where, for example, a row had two X's and no O's. This static evaluation function would probably make the program stronger against inexperienced human players, because it would be more likely to aim for strong offensive positions and thus take advantage of any human mistakes.

This brings up a point raised in Nilsson about how the minimax procedure always assumes the other player is as good as the computer, which eliminates some potentially good strategies. This is definitely the case with tic-tac-toe. I don't feel like going into the details, but I know there is a series of moves that can be used in tic-tac-toe that will often beat a player who has never seen it before, because in order to avoid losing against it, it is necessary to move in one of the side squares rather early in the game, when most people will intuitively assume that it is best to move in one of the corners. I think it would be interesting to see a computer program that was able to discover this series of moves and realize that it is an effective offensive strategy -- the algorithms we have discussed so far really have no way of doing this.

I was also very interested in the idea of having game-playing programs learn by changing their static evaluation functions, which was mentioned briefly in Nilsson. It seems that in most cases this could be done simply by using a single TLU, and not an entire neural network as Nilsson speaks of. For example, for the tic-tac-toe static evaluation function we discussed in class, the inputs would be (1) the number of open lines of attack for the computer and (2) the number of open lines of attack for the opponent, and each input would be given a weight that is allowed to change based on the program's performance. If this doesn't wind up being too complicated, I might be interested in trying to implement some form of learning for our upcoming project involving Hawaiian checkers. Among many other things, this could allow a computer to adapt to a particular player and therefore learn to pursue strategies that might lead that player to make mistakes (is that how Deep Blue beat Kasparov?).



Frank Rusch


Currently, computers can't assess their environment without an abstract representation of reality that we design for them. We give them this abstraction (or at least the instructions on how to build it), then they are set to the task of searching the structure for possible courses of action. The ability to swiftly traverse these state-space graphs gives a computer a broad vision of the possibilities (within the narrow confines of the abstract environment) that enables it to be logically competitive with humans. I think this area of AI has some interesting possibilities. Reducing the time complexity of search algorithms will enable computers to consider increasingly complex systems in reasonable amounts of time. I am curious about ways in which we could generalize the world, so that robots could build search trees based on the environment they're currently in. I think idea of template functions in C++ might be useful for this. We could make a general tree structure, with the nature of the nodes themselves being variable dependent on the situation. These different nodes could also be designed to flag different functions, depending on what is necessary.

In the example in chapter 9, a heuristic function is used to determine how close a particular state is to being the goal state. My main question about this is-- will a computer head down a path that is initially close to the goal, when what is really needed is that the computer diverge from the goal first, in order to get around to the goal? Consider the robot lab where the computer had to work around a U-shaped wall to get to the light. If the robot had had a temperature sensor to detect the light, in would head straight into the U and hit the wall. To really get to the goal, it has to work away from the goal for a little while, move around the obstacle, and then continue to the goal.

In worlds that change, making plans is more difficult. By the time a robot constructs a plan to move north, its path may be blocked. Even if it completes its move, the robot may not be exactly in the state it thought it would be in. Also, when a human is in danger, they can and usually do act immediately. A robot in danger might be destroyed while still in the process of analyzing its possible moves. An island-driven search is used to isolate key nodes that are connected to desireable courses. Does this take into account the constancy and availability of a node? For example, a paved road is more likely to be clear and traversable than a gravel path. This method (and realted methods) seem to reduce the problem to a series of mini-goals which would be helpful to reach in order to get to the final goal.




Edina Sarajlic

The lectures and readings in the past two weeks have answered many questions that came up after the first introduction of planning agents. Now I understand more about the capabilities and performance of search methods for large and incomplete state spaces. Some of the search optimization problems do not seem as computationally intractable as I initially thought.

I found the explanations in the book very thorough, both for the case of heuristic and approximate search methods. One thing that was not very clear to me was the hierarchical search. How are these different search level defined? The way I understood it is the following: the metalevel search forms a basic outline, a plan of general actions that need to be taken, to get to goal node. The base-level search then finds paths between the states in the metalevel search graph, to get the complete path. What I am confused about is how the nodes in the metalevel search are expanded? Do we need to form two separate node-expanding functions, or do we use the same one as for the base-level search?

Nilsson briefly mentions another approach to performing approximate searches, namely probabilistic methods. I was just wandering how often these are used in solving practical problems and whether we will get to cover some of them in class.

The section on minmax procedure was very interesting, especially the alpha-beta optimization procedure. It would have liked to learn more about search methods used in state spaces of games involving chance. Nilsson describes how the minmax method can be expanded to include a random input with a small discrete set of possible values. I guess this would not work well for large sets, because the search tree size grows as an exponential of the branching factor. Is there any other method this could be handled? (I guess this relates to my earlier question on probabilistic search methods above.) Would it be possible to incorporate a simple probability distribution function into a minmax procedure?





Jim Speer

Jim Speer Last week's material got me thinking just how artificial AI is, especially with reference to the game playing procedures outlined in chapter 12. When the computer thinks out its best move it "considers" in a way that seems very alien to me, and very different than a human's method of decision making might be. The computer must picture every possibility, evaluate its likelihood of success, and discard those scenarios that do not maximize the desired outcome. If humans had to think this way they might have to picture themselves in every possible undesirable situation before deciding not to proceed into them. If humans had such speedy search of possibilities one might argue that we would be more efficient, but at the expense of creativity. There's nothing creative involved in speedily choosing between known quantities. A human presented with a complex problem or game might attempt to do things which are less than fully logical, but for unrelated reasons, and at least has the chance of pioneering a new method. The artificial intelligence is still stuck in its own rules, no matter how adept it becomes at navigating its own chances.


Ben Sprecher

This week's readings and lecture have been quite enjoyable. Although I found Nilson's descriptions of some of the search algorithms (Hierarchical search, for example) a little confusing, I found many of the underlying concepts intuitive. For example, the idea of using a neural net to learn a static evaluation function occured to me while I was reading chapter 10, so it was neat to see it mentioned in chapter 12.

Reading so much about search has gotten me quite excited about programming our Hawiian Checker games. Something I would like to do, although I don't know if I'll have enough time, is to program several different search systems, and have several different systems of restrictions (per-move time limit, per-game time limit, depth limit). Then, I could have the computer play itself using two different algorithms and see which algorithm performs better given the restrictions under which it is playing. I'd also like to implement a neural-net based static evaluation function, and I have been trying to figure out how to implement a neural net player. I would have to train it against a player using a proven search strategy, and I'd have to figure out a reward/punishment scheme that would allow the net to adjust its weights after each move, not just after each game. Although the training will probably take quite a while, once trained the net should be able to perform much faster than the search algorithms, since it will not have to do any evaluation or tree generation during game time; in essence, it will be able to evaluate positions of the game wholistically and make moves which better its position, rather than necessarily lead it on the most direct path to the goal. I would imagine that it would still lose to the algorithm against which it trained, but if there were some time limit imposed it would decrease the power of the search algorithm while leaving the performance of the neural net unaffected, since it will have a much faster response.

In any case, I doubt I'll have the time to implement my full wish list, but it will be fun seeing what I can do.



Emily Sweeney-Samuelson

It's been an interesting couple of weeks. Reading the historical information in Moravec's Symbiosis chapter was very good for my sense of perspective; the early undertakings he described in the field seem like huge undertakings! I can't imagine building or maintaining one of those, or even using one, really. The interface was so different between people and those computers. The movement away from pure machine language makes sense for the field, but it was a classic case of conservatism, such as happen all the time in many fields, to protest that change. I hadn't thought about that protestation before, but it was very natural. The idea of symbiosis, with his italicized narratives that make the idea easy to grasp and imagine, frightens me. If something like that happens, even if not in my lifetime as he predicts, I think it will take away from humans' truly personal, unique communication, and their creativity. It has wonderful benefits, also, like the great educational system he described, but the bad effects will come about first, and it seems like there would have to be long intermediate periods of work and experimentation while these negative effects are spreading, before the benefits would appear. It's sobering to think that such a science-fiction-like situation could come true, when you consider some possible effects.

I like learning so much about searching; it's been a very interesting topic for me in computer science courses. The variations in ways of searching and the precision and planning involved is amazing to someone like me, who looks for things very randomly (and usually without success) or, when solving problems which a computer could solve with search algorithms, doesn't usually think of the problem in that light. I feel a little uncertain about the selection of the heuristic function - is this an important skill for us? If so, some clarification would help.

The sense/plan/act architecture, with all its variations, seems very practical, and a good way to thoroughly deal with present machine limitations when finding a good path. Learning heuristic functions are intriguing -- are we going to deal with those?

I am excited about dealing with games. I have never programmed a game before, but I have been curious about it. The search-tree methods of programming games that we have discussed make me wish I could do that in my head. Playing games used to seem so much more random, because I only have so much brain facility; very often, I just have to guess fairly randomly when playing complicated games. But breaking them down, the procedures for playing and even for ensuring a win can be so simple. I am looking forward to Project #1.



Tim Waring

In Chapter 3, Morovec outlines a nice future of computing story, with fully integrated imesrive worlds and interactive mutli-user environments. He doesn't directly predict how long it will take before this sort of thing exists, but he assumes we are arriving at that stage in computation, or will be soon. I love the picture he paints. however i don't think it's going to be that cozy and easy anytime soon. First of all we need gigahertz computers to run most of the stuff he talks about, and they are 5 years down the line. Once at that stage, OSes and programs will be written and implemented entirely in life-like 3D. But then a network standard protocol must be hammered out.

A truly prohibitive problem is that of the hard ware, and "magic glasses" and Magic suit he talks about. There are 3d vision goggles ont he market right now, and they are getting better and cheaper, however, we are very far away from the sunglasses-sized version, with an embedded camera or two. very far indeed. also the magic suit is a little rediculous. even the military, (commonly understood to be a good 5-10 years ahead of commercial computing hardware) doesn't have a comforatble suit that can apply variable amounts of pressure to any part of the body in real time, and translate the bodies moves into motions for the virtual body in the program. this technology isn't even worth dreaming about right now. we are still working on simple immersive environments.

enough of morvec.

i read chapters 8 and 9 over break, and they aren't as exciting as chpt 10 anyway. Chapter 10 starts with the sense-plan-act cycle. I have become really fond of the idea of sense-plan-act, and i feel that it is related in spirit to island search, limited horizon search, and having rewards instead of goals.

The spirit of these searches, or behavior cycles is that an agent might not have the computational power, or time, or luxury to find the "goal" state before it must act. This field is the one that contains the programs that must someday govern mobile autonomous robots of all kinds. Island search makes sense to break up the task into a bunch of large but manageable steps. Limited horizon makes sense in a similar way. Real Time A* (RTA*) seems even more intutive because it almost has a short term memory and must remember what it did last time in this situation.

Finally Rewards instead of goals is a much more sensible way to look at the way the world really works. People don't plan an "end-state" or goal node, that upon reaching it they will stop all searching. That's not the way it works. It's more realistic to set up short term goals and rewards and have the AI search from island to island of these. I also beleive that a true AI must be able to build it's own heyristic. The learning outlined in chapter 10 needs all heuristics programmed in, and then weighted, and learning being the adjusting of those wieghts. i like that idea, but the AI should build the heuristics (or pick them out of a really large general area) itself.



Sarah Waziruddin


This weeks readings were very challenging. How much detail do we need to know about each search? The concept of the A* search is still not clear. A concrete example would help.

What is a monotone function? This was mentioned in the book in the section discussing limited horizontal search.

Nilsson mentioned implementing random actions in agents. Our group used this in our labs to get out of a corner.

Moravec proved to be entertaining as usual. I really liked the history of computers that he presented. Moravec said that for a computer understand English commands, it would require common sense and broad knowledge of the world. (p. 83) AI could change the way programming is done by creating an intelligent agent. If this agent is created, there would be no need for programming languages.





Leslie Zavisca

As hard as it was to deal with the fact that Fall Break is over and done with, I forced myself to sit down and complete the readings for this response. I have to admit that I didn't enjoy it all that much. Overall, the different search methods are ones that I have been abstractly familiar with but just never had names or algorithms for. The concepts are all pretty straight forward and relatively easily understood. The only challenge is getting used to the notation, as opposed to the everyday descriptions of what's going on. I am taking discreet math along with this course and it's nice to see some of its applications so early on. The section most interesting to me was that on limited-horizon search because this method seems to be most similar to the way that humans learn to successfully strategize when playing games more difficult that tic-tac-toe. All of the reading on two agent games focused on perfect information settings. I would like to know about non-perfect information games like scrabble(where, for example, a player can count the number of R's left on the board and in their hand to 'expectimate' what letter the next player will or will not build on) or spades(four-agent, scary), where each move means the information is one step closer to being perfect.

The last lab meeting was the most enjoyable one yet for me. I really enjoyed the fact that we were all given the exact same assignment to complete and still all of the robots were so different from each other and implemented so many different methods and designs. Until the last meeting, they've been pretty much the same and executed probably almost identical code. Now that there are so many more variations, and even idiosyncrasies, I would be interested in seeing all six of them at some point. I really enjoyed the diversity and the fact that we all learned from other groups' ideas. I am making our improvements for next week's lab.


Back to CS372 Course Materials