Course Navigation

 Course Home Page

Robot Lab Wiki

WeeklyReactions

Week 9

Timothy Ambrogi

The problem of, given any image, counting the number of people in the image, is quite complex. By setting up a neural net of sufficient complexity, and by providing a versatile enough data set, a computer scientist could program software to perform a task that he would not have the slightest clue how to code if he had to use a standard procedural algorithm. They might manage it, but only after a far longer period of time. Also, they would probably have to go through the learning process on their own before coding it.

Computers can, theoretically, learn certain things faster than humans, just as they can calculate things faster. I guess what I'm saying is that these "AI" techniques seem like algorithm calculators that, like calculators, give solutions without outlining the processes clearly.

Lawrence Bomback

I found a webpage where you can download a version of Konane to play on your PC. The URL is www.zillions-of-games.com/games/konane.html Unfortunately though you have to pay for the program that actually runs the games. I wasn't able to find any other websites that allowed you to download a version of Konane for your PC, and I also couldn't find any website that allowed you to play a against an online computer. However, there are an abundance of sites that allow you download a palmOS or pocketPC version of the game. So, if you have a palm pilot or some other PDA you can get a nice compact version of the game.

I'm excited to see how these programs will turn out. I played one of the palm versions of the game and I discovered something very interesting about it. I thought I was losing terribly, constantly getting double jumped by the computer. It was the first time I had ever played and I knew I was going to be bad at it. As the board gradually lost pieces, I realized that I had fewer pieces left than my computer opponent due to the frequent double jumps. I assumed I was going to lose because in most board games, such as chess or checkers, when you have less pieces to play with, your chances of winning become that much smaller. But in this game, it sometimes works to your advantage, because of the fact that unlike chess or checkers, you're not necessarily trying to rid the board of your opponent's pieces or corner a particular piece. All you want to do is not be the person who can't make a move. As a result, I feel there's a lot more luck needed in this game than in chess or checkers. The skill obviously has to be there too, but when I was playing, I just made moves totally at random and was still able to win. It had to do with the fact though that my moves were done pretty close to each other. I didn't realize it conciously, but by the end, I had a cluster of pieces next to each other, preventing the computer from jumping over any of them.

Jacqueline Chew

I was looking online for possible final project topics and came across some interesting information regarding early AI. I found that traditional AI developed out of attempts to crack enemy codes in WWII. It attempted to capture human intelligence by simply following incredible lists of pre-programmed rules. This early strategy had many limitations because it is doubtful that such a program is displaying any form of "intelligence."

I find it intersting that AI was initailly being developed for purposes of military defense becasue the field has evolved and expanded in so many ways. While, of course, AI is still being used and developed for purposes such as military defense, it is becoming increasing used for matters of convenience and even entertainment. For my final paper, I'm considering researching "AI meets Music." That is, the development of "musical intelligence." I came across a lot of very interesting projects and developments in using musical intelligence in interpreting or even composing music.

Catherine Chiu

Jason Coleman

It's so sad that we can't find a version of Konane for the computer. I see a link to what must have been a Bryn Mawr student's version, but it's dead. Well... I'll have to break out my Visor Handspring and play the palm version. After this assignment, I can make a webpage to host the versions we make for this class so no one will go Konaneless ever again.

I played a couple games of chess this weekend with my brother, and of course I was thinking about game playing algorithms the entire time. Mostly I was thinking about how humans play chess as opposed to computers... this is especially important I think for our Konane game because we will only be able to look three ply deep, which for a game like Konane isn't very much. I'm also scared by Larry's statement that he can beat the Palm version playing randomly. I wonder what kind of algorithm the Palm version uses... hopefully a very poor one... or else the human players in our tourniment will kick butt.

So back to chess this weekend. I noticed that I had general "game plans" or strategies when I was playing. I know how pieces work together, how I can cover my attacking queen with a bishop or rook to get a checkmate. Considering our Konane programs will only be able to search three ply, meaning they wont really be able to tell which move leads to a win... and it seems like a heuristic for Konane will be hard to make a good one, I need to figure out what the Konane equivelents of strategy are, and try to program these into the algorithm. This will probably be implimented in the heuristic to recognize favorable patterns of pieces... like maybe having your own pieces in clumps to big to jump over is a good thing... bla bla. Okay... I have to get my hands on a Konane game so I can figure out some more strategies...

Ian Harrison

Given enough computational power and time, the minimax algorithm would produce a perfect gameplaying computer. However, I’m not so sure that, as it is, minimax actually constitutes something resembling human intelligence. When Deep Blue beat Gary Kasparov, it wasn’t a sign that the computer was smarter than Kasparov. In fact, Kasparov’s losing had more to do with the fact that he wasn’t allowed to play against the improved version of Deep Blue before the match in which lost, while Deep Blue had a database of every one of Kasparov’s matches. More recently, Vladimr Kramnik played to draw against a chess computer called Deep Fritz, one that is supposedly a much better player than Deep Blue was. The difference in this match was that Kramnik was allowed to play against Deep Fritz for one month before the match. Because the branching factor in chess is so great, as the match approaches it’s midpoint intelligently creative play stands a very good chance of beating sheer computational power. Computation leaves the computer exposed to horizon problems, where it can be lured into a position that may look really good even 8 ply down, but opens up some sort of weakness beyond that ply, and creating this sort of weakness is what chess grandmasters specialize at. A vastly experienced human player is better able to force lines of play that will eventually favor him, even if they don’t appear to in the short term. Part of this involves knowing how the opponent will react to certain moves, knowledge Kasparov was denied by the IBM research team.

The Japanese game of Go also presents a problem for the minimax algorithm. In Go, the branching factor is so great, approaching 300 moves per board position, that the work done to search a Go tree n moves ahead is 10 times greater than searching a chess tree n moves ahead. Additionally, evaluation of a given board state is extremely complicated. There aren’t any clear cut evaluation principles, as in chess where one can use the number and type of pieces each side as left as a good indicator of a board state’s value. Most Go programs can’t even beat amateur human Go players. In game playing, when the search tree is large enough, humans are doing much more than simple min-max evaluations.

Nicholas Kerr

I was looking online for ideas for a final project. I want to program robots to compete in a couple of predetermined competitions. I found some interesting ideas for games at www.firstlegoleague.org/sitemod/design/layouts/default/index.asp?pid=7540 If anyone is interested in competing with us in these games for a final project, we’d be glad to include you. Since some of these games may require some more complex decision making than our plain old prioritized subsumption architecture, I was trying to think of ways to use a minimax search algorithm within my IC code for the robot. I am not sure if we have the sophistication to create a practical situation in which the robot would need such a search, nor a heuristic that could be used to define the algorithm, but I think the implementation of such a minimax search within robot code would be a big step in our attempt to make our robots look as though they are “thinking” or “learning.” It is hard for me to think of a complex situation that would need decision making that could actually be accomplished with our simple physical robotics technology. What about a situation in which a robot had the capability to follow a black tape strip on the ground: This robot would try to get back and forth between “bases” at each end of the tape strip as many times as possible, while another robot would be programmed to bump the strip following robot off track (this bump robot would probably just be equipped with a simple maze solving algorithm, and thus just bump randomly anything it hit). If the strip following robot was hit, it would have traverse a binary tree of tactical options to decide whether to stray from the tape strip to try to get around the other robot (and which specific way to stray), or to continue following the strip and hope to avoid the other robot moves). If anyone has any ideas, I would be glad to hear them.

Ananya Misra

One thing I learned from the robot labs is that the physical design of a robot is important. Of course, that seems obvious. But I mean that small design details played a larger role than I'd expected in the robot's performance. For example, the placement of light sensors and the programming of light threshold values had almost equal influence on the final behavior. Similarly, when the robot followed a wall, its success at corners or sharp turns depended partly on its length and the placement of the bend sensor. We could have modified the program to behave differently during these situations, but then the wall following behavior may not have been considered as emergent. I wonder how far the design can vary for a given program to work.

The algorithms for 2-person 0-sum perfect knowledge games have been interesting. Only, it's a little amusing how many adjectives are required before the "games" for these techniques to work...though it's also cool that they'll work for any such game. But if some of those adjectives were changed--if the game had more players, or was a guessing game like Master Mind or Battleship--I'd like to know how the algorithms would change.

James Racanelli

What if we were to have a bunch of robots play tag for the final project. We could do it with some subsumption style works and a dual mode on-off switch type deal. Basically the robot has two modes, it and not it. When the robot is in it mode, it follows moving objects. Larry mentioned in week seven’s wiki that there was a robot Seymour that used subsumption to do this. We don’t have the capabilities to make something that complicated, but we could make a cheaper version which might do the trick. If the robot in it mode hits another robot with its bump sensors, then the it mode robot goes into flee mode, and somehow the robot who got tagged goes into it mode. When in flee mode, a robot just tries to avoid all objects, especially moving ones. One main problem with this is that we couldn’t put the robots in a closed arena because if the hit a wall then they wouldn’t think that they were it anymore and the robots would all just be going berserk. Perhaps there is a way to distinguish between moving objects and not moving objects. I’m not sure if it would work, but it would take a lot of infrared sensors and it would be awesome, so I want to try it. Just imagine a bunch of robots running around going berserk playing tag. If that is not intelligent then I don’t know what is.

Juan Ramos

The Minimax algorithm we discussed in class last week looks like a very efficient way of making a game program where the computer can be really challenging. I was talking about this with Jason last Friday, and we thought that a game that uses Minimax, or any other sort of search algorithm, has a good chance to defeat the human opponent even with a small ply. I played a simulated version of tic-tac-toe on this page: www.tcnj.edu/~games/tic/ , and I mostly played to draws against the computer (with 2-ply and 4-ply), and was only able to win in 2-ply when the human starts. Of course, maybe I'm just bad at tic tac toe, but I think this page gives a nice example of how a simple program that runs on a minimax algorithm can be difficult to defeat (there's also a program on the page that cheats its way to a guaranteed win). With a more complex game like Checkers or Konane, I imagine that the computer player will have a more difficult time guaranteeing a win, although it will still pose a challenging opponent.

There's one doubt I thought of in regard to Deep Blue's algorithms. Was its implementation mostly based on statistics and an archive of Kasparov's moves, or was the program more dependent on some sort of a minimax algorithm? I don't think it was a matter of either minimax or statistics, but I can't remember which one Deep Blue depended on the most.

Matthew Rushton

I'm really excited about the Konane game programming competition. I think it will be really fun to implement one of the algorithms we have learned about in a competitive setting. There was one particular game playing element/idea that I wanted to mention. I had heard when watching a TV special on Deep Blue that in one respect Kasporov did have an edge on Deep Blue and that was with creativity, or insight. Apparently in chess and I assume other more complex games there is almost an undefinable property that a machine could never (at least presently) possess. Maybe others of you know something of this but it would be interesting to learn more about. I believe Kasparov did beat Deep Blue once (it was a best of 7) and tie twice, so perhaps there is something to this. How else could one beat a computer that essentially makes the best (or near best) move every time? It would seem at best you could only get a draw. I know Kasporov also changed his style of play in the later games to try and trick the computer, which in a way is kind of too bad because perhaps he was not quite as good of a player when he did this. It would be interesting to see if the outcome of the game would have been different if Kasporov had thought he was just playing against what he thought was a human. In all likelihood it would have been the same, but there could have been some psychological effects.

Tina Tan

I’m looking forward to playing in the Konane tournament. I haven’t played the game yet, but it seems a lot different from any other games I encountered. It seems harder to think ahead and for me, it seems even harder to just picture how a winning pattern at the end would look like. One thing that I’ve been thinking about is how humans use games as means of entertainment. I agree with Matthew’s comment of how humans would always have creativity and insight, but I also think that humans play for different reasons than computer opponents. I’m not sure if the enjoyment of playing a game makes someone play better than a computer but I think it gives an advantage when people play against another person. Computers have one purpose only and that is to play to win. Of course, I like the idea of computer players yet the idea seems ironic when you think about the general purpose of games for humans and how computers don’t share that.