Course Navigation

 Course Home Page

Robot Lab Wiki

WeeklyReactions

Final Project

Tim Ambrogi

Larry Bomback

Since we have spoken a lot about Deep Blue on this WIKI board, I thought this link might be of interest to many of you. It's an article about two new computers that IBM is currently creating that will rival the human brain in terms of processing speed, memory, and storage: www.timesonline.co.uk/article/0,,3-485578,00.html

The first computer, ASCI Purple, is able to do 100,000,000,000 (one hundred thousand billion) calculations per second, which is apparantely how fast our brains process. The other computer, Blue Gene/L is 3.6 times as fast as ASCI Purple. Both will be used by the US Government. ASCI Purple will be able to simulate nuclear tests, while Blue Gene/L will be used to map stars in three dimensions, analyse earthquakers, and aid in oil exploration.

Despite all these capabilities, the computers cannot exhibit artificial intelligence on their own and it's likely that we're never going to be able to build a machine that is intelligent on its own accord without any programs running through it. Still, these computers, which will make their debut in 2004, are so fast that they will probably be able to run programs that exist today but can't be run on current computer speeds.

Jackie Chew

In researching for my AI meets music paper, I have come across an interesting sore topic that exists in all areas of AI research. Many people feel extremely threatened by advances made in AI. Specifically, there is a lot of opposition to computers composing orignal music, and computers that can compose music in the same style of a famous human composer. It seems that people are bothered by this because, to say that a program can produce aesthetically pleasing music, or music that is nearly indistinguishable from that of a real composer, shatters our ideals that a composer's heart and soul, emotions, and struggles are necessary elements in creating music.

I'm not sure that i agree with this entirely. To some extent, i believe that what makes a piece of music "good" is being able to feel what the composer had been feeling, or to understand what emotional state the composer had been under when writing the music with the dynamics and phrasing that he or she did. On the other hand, i have heard examples of computer generated music, and it is... well.. not bad. I do not feel threatened by AI in music because i know that human musicians aren't going ot stop composing just because a machine can do it too. I don't tink it will ever come to that.

Catherine Chiu

I am curious to see what other static evaluations other people may have used in their programs or if they have any additions to their algorithms. Is anyone going to start placing bets on who is going to win the tournement tomorrow? Hopefully, the matches won't take too long so that everyone can stay to the end.

Jason Coleman

Without Alpha-Beta Pruning, my program takes about 5-10 minutes for each move on ply 3. On ply 2, it's cut down to about 5-15 seconds, and on ply 1 it's pretty much instantaneous (duh). So my program is slow too.

About evaluation functions... I thought about a lot of different ones... like about keeping pieces in the corner where you can jump the other player but he can't jump you, and about being in positions where you can jump a player but he can't jump you... all of these seem to be isomorphic to the test where you compare your number of jumps with the opponents number of jumps... The only differences I make is that I weight the number of moves the opponent has, and randomly choose from moves with the same evaluation... so my static evaluation is:

# of possible moves I could make - 2 x # of possible moves the opponent could make

the factor on the opponents moves makes it so that the AI will favor states where the opponent has less moves, even if it means he himself will have less moves... it seems that having 3 moves vs. 1 move is better than 4 moves vs. 2 moves, ect... I was thinking about maybe turning that around if you had fewer moves than your opponent... so it would rather have 2 moves vs. 4 moves than 1 move vs. 3...

Ian Harrison

Like everyone else's, my program runs very slowly during the middle of game when using a 3 ply search. Part of my problem is that the data structures I used are fairly ineffecient. They make the program more readable, and easier to modify, but require a lot more processor work. Since these structures are manipulated at every node on the search tree, the increase in the number of moves that need to be evaluated that results from using a 3 ply search compounds the effect the data structure ineffeciency has on the overall run time of the program. I've also found that, at least in my program, the outcome of the game seems to be determined mainly in the end game. Often, the player who appears to be winning suddenly finds themselves getting beaten (at least this is what keeps happening to me when I play the computer, and it seems to happen to the computer when it plays itself). I'm unsure what results in this dramatic swing, but it seems to be that playing what looks like a winning strategy during the earlier phases of the game actually leaves ones pieces in a bad position for the end game.

Nick Kerr

My static evaluator also just returns the difference in the number of moves the computer has and the number of moves the human has, with one minor modification. I will be interested to hear from people in class tomorrow who used more inventive methods of static evaluation. I'm also wondering if anyone was able to incoporate any good trash talking algorithms. I saw jamie working on something of the sort, but I am not sure how far he got with it.

I wonder why depth six is so slow. I mean sure we're talking 4-6 million static evaluations here, but I thought computers were supposed to be fast these days. The slowness of our algorithms makes me really confused as to how they program the commercial board game opponent simulators on the market today. They must either have ridiculously programs or must use much more intelligent programming style. Either way, I have found myself much less interested in things like computer chess after completing this project. Computer opponents just don't seem that intertesting after you have programmed one yourself. Maybe I'll take up reading instead.

Ananya Misra

Then a dark secret was revealed. Realizing that I'd forgotten to keep track of the number of cutoffs, I re-read the cutoff section of my code and noticed that for both alpha and beta cuts I had been returning beta. Huh? (Exactly; that should not make sense unless you've been blinking at the algorithm recently.) So why did the moves still match? Either my sample inputs were strange or alpha was always equal to beta during the cutoffs. Or both, or something else.

Anyway, it's interesting that a logic-based system includes so much more than my intuitive idea of logic. The amount of knowledge and its representation seem at least as important as the rules of inference.

Jamie Racanelli

My program has turned into the devil, I think. I got it working and it was finishing games at depth 4 no problem and everything seemed in order. Then, when I tried to run depth 6 games, my computer went beserk. IT seems as if 4 ply runs even take longer now. I know that wouldn't make any sense unless I changed code, but I don't think that I made any changes. Also, my program is really similar to the other peoples' that I have seen, but mine is counting about ten times as many static evaluations per game. My play game function is recursive rather than being a loop, which may be causing the problems. But yikes.

On another note, I am still not convinced that we couldn't implement a very simple logic system on the computers we use in class. If we only gave a few rules, it seems like we could build something to use inference and be able to answer simple questions. I guess that if it were at all possible, the systems we could build would have to be terribly uninteresting. But I'm still interested.

Juan Ramos

While looking at the results my (buggy) program was returning, I've noticed something interesting that can vary the average branching factor substantially. Suppose the player picks moves relatively evenly; that is, is equally likely to move pieces on one side of the board than on the other. Here, the branching factor can grow quite high, up to about fourteen or fifteen. This means about two hundred twenty four total nodes divided by fifteen expanded nodes (and this is just depth 2!). However, if the player sticks to moving pieces on one section of the board only, the branching factor goes down to about seven or eight. Here, the total nodes would be about seventy two vs. a total of about nine expanded nodes. Whichever choice is made, the resulting average seems to hold for the majority of the game, save for the very beginning and near the end, where the branching factor drops back to six or below.

I'm also curious to know what the static evaluation functions are for other people. Mine consisted of calculating the number of moves the computer had available to it at the depth bound, and then sending that value back up to minimax and alpha-beta.

Matt Rushton

Like everyone else I'm seeming to have extreme slow-down on higher depths. It's gotten to the point where it's taking in excess of an hour to play a game, and this is using alpha-beta pruning. I think for the tournament I'll stick to depth three, or perhaps four at the most. I too am not using the most efficient code and this surely is part of the problem, though I also feel like I wouldn't be getting much of an increase even if I changed a lot of it. I think the tourney tomorrow is going to be a good time, especially with all the trash talking I've been hearing about. All I can say is, bring it. Anyway I found the most effective static evaluator to be just the simple "my moves - your moves". Using this it always seems to be able to beat a random player, so I think that theory clearly is incorrect, especially in end game situations. Good luck and see everyone in class tomorrow.

Tina Tan

The article that Larry posted made me think back to the first question that was asked on the first day of class: what is artificial intelligence? While reading the beginning of the article, I immediately thought, these computers are not really showing any intelligent behavior, and sure enough, the fifth paragraph begins with this statement. I remember now that during that first class, I said artificial intelligence is when a machine can mimic human behavior. Obviously these new computers are basically replicating human brain capacity yet no signs of thought. Back then, I didn’t realize how little I knew about A.I. It is still hard for me to explain to my friends that certain machines or gadgets aren’t displaying artificial intelligence. From the article, it seems like there are numerous applications for these computers but another reason I couldn’t consider them as advancements in A.I. was because it wasn’t clear how these computers were providing any insight into how the human mind functioned.