Course Navigation

 Course Home Page

Robot Lab Wiki

WeeklyReactions

Final Project

Tim Ambrogi

1. Random play still manages to win against minimax every once in a while (with my static evaluation).
2. Double jumps aren't always good moves, but they are good if the only other option is the ub-jump.
3. My 3-ply search is very slow. * It is a good rule-of-thumb to wait as long as you can before making a jump that is not in dispute.
4. The static evaluation function for Konane is far from trivial.

On the topic of the last point, I think this is a perfect time to implement GA/LA in AI. Here we have a problem for which the algorithm is unknown, and which we find it hard to systematize. However, we *also* know that there are best moves in some situations. Therefore, there must be a static evaluation function that will satisfy our needs, and GA/LA will approximate this function with minimal investment in the actual game, and also with minimal human experiencial bias (such as the human who assumes outright that double jumps should be taken as soon as they appear).

As for the 3-ply being slow, I hope that alpha-beta pruning will remedy this slowdown somewhat. I'll guess know by class tomorrow!

Larry Bomback

I'm thinking about the upcoming Konane tournament. I wonder if we made a version of the game that played it completeley randomly and then matched it up against a version that ran on a very well-thought out static evaluation function. If the random version consistently beat the "thinking" version, would the average onlooker call the random program more intelligent? Would we call it more intelligent?

On an entirely different note, I had a question concerning logic and I was wondering how a computer handles so-called "leading questions," a favorite of lawyers. A great example of a leading question is, "Has your brother gotten out of prison yet?" If you say yes (true) or no (false) you're screwed. Leading questions do this because we instinctively always assume that the presupposition portion (the given portion) of the statement is true. In this case, the presupposition is that "your brother is/was in prison." A computer using propositional logic would answer "false" because that is the default "I don't know" or "can't be determined" value. This seems to be a big flaw in the language, since by answering false the computer has essentially admitted to something that isn't true. Are there languages that have an explicit "can't be determined" value as opposed to simply a default "false?"

Jackie Chew

I have been working on my paper about artificial intelligence used in music composition and interpretation and come across a lot of fun stuff. I hadn't realized just how much research has been done in this area. Most of the research however, has been pretty recent. It seems that many of the projects have been started within the past 4 or 5 years. In any case, there has been a lot of progress made. I came across a program that allows you to simply put in specific preferences regarding style of music, or a particular type of tempo, and it composes some pretty well-developed music. I'm currently taking a music theory class in which i'm learning to compose melodies and such, so i realize that it isn't just somethign that you can just throw together. There are generic chord progression, and such, that one can follow in music composition, but in order to make something that sounds good or catchy, you can't just follow a set of rules. Because of the creativity and musical sense i have learned to be required of good music composition, i am impressed with some of programs that have been written so far.

Catherine Chiu

Like everyone else, I have been working on my program a lot lately as well. Still puzzled as to what a good strategy would be, but I do think that it would be interesting if we took Larry's suggestion of having a random program play against the minimax program. My guess would be that the random program's winning percentage would be no more than half since there is no weight to moves that would end the game in the random program's favor.

I am excited to see everyone's final projects and see what problems they may have encounted and the steps that they took to fix the problem.

Jason Coleman

I went to the Complex Systems/Emergence talk last Friday, and it was interesting. It got me thinking: we're always talking about simple individual behaviors that lead to complex group behaviors... our Robots were programmed simply, but they could do interesting, possibly intelligent, things.

I think it would be useful to talk about the opposite occurance: where something programmed very complicated leads to a very simple behavior. Does this even happen... I'm trying to think of an example.

It seems that when this happens, it's either an underestimation of how difficult the displayed behavior is (as in: "Why that program JUST lifts up boxes and places them on top of other ones." but we know this is a difficult problem) or there is an overestimation in the difficulty of the problem (and resultant complexity of the answer)... this would happen if say a random Konane player is the best player (not likely)... or if you programmed a stock picker and all it did was choose to invest in GE stock. If this is the correct answer to ensurably make the most money, you could just have made you program output: "Buy GE stock", and it would have been easier to code.

I can't just now come up with an example where complex programming results in a fairly simple behavior that couldn't have been programmed in a simpilar way... meaning the complex programming is NEEDED to get the simple behavior... If complex programming is NEEDED to get the resultant behavior, then that behavior is kind of "by definition" complex... until someone finds a simpilar way to do it. There's a paradox at the bottom of this argument... and it seems that you can't complicate simple things... if they had to be complicated, they wouldn't be simple...

Maybe it isn't so useful to consider the opposite of emmergence.

Ian Harrison

I don't think that a completely random konane player would fare all that well in the long run against any konane player using a minimax evaluation function, merely because the random player would have no idea how to finish off a game. That is, it could be a single move away from winning, and not make the correct move. A program that searchs 3 ply, however, can win the game six moves away from the actual final move once it sees a line of play that results in victory no matter what move the opponent makes, random or not. Though I haven't tried it yet, I think a game between a random player and minimax player would look fairly even right up until end, at which point the minimax player would demolish the random player. Lawyers aren't supposed to ask leading questions. That's what objections are for. If the computer being asked the question about the brother getting out of prison actually understood the question, I imagine it would return an indeterminate truth value. If the computer understands that in order to get our of prison, you must be in prison in the first place (which is pretty simple to represent in a language like prolog), then it might notice that it has no fact representing the brother being in prison. Hence the question would appear nonsensical to the logic system, so it wouldn't return a true or false value unless it was set to default to one of those answers for questions it had no other answer for. There are various methods in first order logic and predicate calculus that were devised to keep track of changes through time such as the ones that are often the subject of leading questions.

Nick Kerr

I decided to express my thoughts in the form of a poem this week:

'O Konane

you play me so

your secret is in static evaluation though

between the move generator and board initializer

the darkest evening of the year'

There was once a small green duck

whose existence was based upon luck

he loved summer rain

but konane was pain

he played the game worse than a truck

his 3-ply search is worse than yanni

speed that thing up

we homymo'fic wassup'

alpha-beta that stinkin salami

reduce complex programs with detergents

that code is too tough

i'm callin' your bluff

you got way too many recursions

I could have done better with muffins

the "new guy" is a fluke

you 90210 luke

your ninja just taps on the buttons

are they better? Or worse? That's heuristics.

a respectable guy

excels at AI

when his response is encoded in cryptics

Ananya Misra

This is not something we discussed in class last week, but it came up in another class and the presenter said the idea was used in AI, so I wondered how. She referred to it as "people games" and described it as follows: Three people have lunch together and get spinach stuck in their teeth. Each one laughs at the others' teeth, until one of them finally deduces that her own teeth are also in the same condition. (In the sense of a "game", we could say the person who realizes this first is the winner.) The reasoning goes something like, "If my teeth are clean, my two friends are laughing at each other. Eventually one of them (A) should wonder what the other one (B) is laughing at. B is obviously not laughing at me (if I'm right about my teeth), so A should figure out that B is laughing at him, and should therefore shut up. But both these people are still laughing, which means there's something wrong with my teeth. Aaaaa!"

Apparently, similar reasoning techniques are used in some AI applications. It seems like a sort of proof by contradiction, basically, but does anyone know of more specific uses?

Returning to class: I was thinking of logic systems in terms of their being abstract. One could possibly find that the same fairly complicated logic mapped perfectly into two seemingly different worlds. (Lots of adverbs in that sentence.) This would be easy for simple logics, but if they were complicated enough, wouldn't it be a great way to find similarities (ie an isomorphism) between the two worlds? Which implies that logics could help us better understand apparently different systems. Except that who would think of the generating the appropriate mapping to begin with, without already knowing whatever the logic might verify?

Jamie Racanelli

Have you ever been playing video games with a lot of people in one room, when all of a sudden the "new guy" steps up, takes the controller, and beats everyone. It seems to be a pretty common theme in head-to-head video game situations, especially if they are combat style. Often times if someone just comes up and hits a lot of buttons really fast they can beat players who know how to do all the moves and have strategies. This happens becasue sometimes strategies aren't as sophisticated, as correct, or as complete as one thinks. They give you a purpose and show that you know some ins and outs of the game, but they won't make you a ninja master, neccessarily.

I'm wondering about this becasue I thought that perhaps we are not thinking about all this randomness business in the right way. Maybe it's not that random can be better than certain strategies or whatever. Maybe it is just the case that in order to make a really sucessful strategy in KOnane, you have to get really complicated. So most strategies thought up by common folk are not developed enough to guarantee sucess. Perhpas up to a certain point randomness is just as good as strategy. I mean after all, Tim did say that the static evaluation function is not trivial. Right.

Juan Ramos

On Larry's question about whether there are logic programs that default to "I don't know", my final project deals with some of those issues. Granted, SNePS is not a pure logic system, but it is based off on propositional logic.

The prepositional logic we've seen in class only has the values True and False, which, as Larry says, lends itself to certain kinds of problems in situations such as leading questions. SNePS allows for the case where the result would be "I don't know." Take for example a system that knows "Mary is human", "John is human", "Peter is human", "Richard is human", "Peter is the parent of John", and "John is the parent of Richard". Suppose I input rules that determine the relationship between parents and grandparents. Then if I ask the system "Is Peter the parent of Richard?", depending on the rules that I gave it, the system might be able to conlcude "False", and give a proof as to why the assertion is false. If I ask "Is Mary the parent of Richard", the system should answer "True" and provide a proof. The idea is that the system behaves like the theorems and proofs we've seen in logic, but with the added bonus that it can prove false statements. If there are no proofs, then the system answers "I don't know". Going with Ian's explanation, this "I don't know" value could serve as the default. If the system were more complex, it could point out that such a question might not even make sense from a logical perspective.

Matt Rushton

I have been working on my Konane game quite a bit recently as well. Everything is coming along fine but I am still unsure of what the static evaluation function should be. I completely agree with Tim in that this would be the perfect place to use a genetic algorithm. Clearly there are good and bad moves, it's just not readily apparent what they are statically. I think it's great that people are talking about randomness, not only in moves but essentially in determining the winner as well. Konane however is not a game of chance, there is absolutely no "luck" involved. Of course you could get "lucky" and make a good move you didn't know was good but this is a far different kind of luck than say getting dealt a great hand in a card game. Who knows if the winner of the tournament will be "lucky" in this sense or if they will indeed have a superior static evaluation function. It will be interesting to see what the winner does differently than others.

I've been doing a bit of research toward my final project as well. Specifically I've been monitoring the espn.com expert football analysists. Between the eight of them their win percentage varies from .569 to .653. Interestingly I have noted that there have been weeks when a couple analysists will be even below .500 for that week's picks. For example one guy was only 4-9-1 for week 10, which is pretty bad. Hopefully my program will be a biy better than this. Getting a picker over .700 could be pretty impossible, especially in football where crazy stuff can and does happen.

Tina Tan