Course Navigation

 Course Home Page

Robot Lab Wiki

WeeklyReactions

Final Project

Tim Ambrogi

It seems to me, then, that this closely models real life game-playing. Using this structure, one could craft an interesting simulation of a person skilled at other games, who is trying to learn a new game. All that would be needed is a learning algorithm (or GA) that would alter the Static Evaluator. The Game State is like the box you buy in a store that contains the pieces and the board itself. The Move Generator represents what happens when you have the rules of the game explained to you. So one would define a movement rule set (Move Generator), and a player who uses minimax (or any other general-purpose algorithm), and then see the player slowly become better and better at deciding which moves are better in the long run.

* NOTE: The Game class is simply the game event loop/etc...

Larry Bomback

Last week's comment by Ananya regarding games with 3 or more players made me start to think about games for one player. What type of search would it employ? Would the minimax algorithm dissappear? I thought about one of the classic games for one person, the Peg Solitaire Jumping Game, also known as "The Great Thirteen." It's the one where you have a board of pegs and one space empty. By jumping over pegs you try to end up with as few pegs left on the board at the point where you can't jump anymore. Obviously minimax is not a factor here and the search I think probably involves iterative deepening, since we don't really know anything about cost or distance to the goal. Now in the more complicated game of card solotaire, I believe minimax is also not a factor, but the search probably is different because we do know a lot more about cost. For example, a typical situation that we find ourselves in during a game of solitaire would be, "do we put the 2 of clubs over the ace of clubs or under the red 3?" Cost is a factor here. Once we place the 2 over the ace, we can never get it back. We're assuming that we won't have to use it again. But if we put the black 2 under the red 3, we sacrifice distance/time to the goal. So perhaps if a computer was to play card solitaire, it would employ an optimal search.

Jackie Chew

Catherine Chiu

Over the past week or so, I have been trying to figure out what the strategy behind Konane might be. The only experience that I have had with the game is seeing it played once in class and playing it once myself. I have to say that the time that I did play it, I was totally clueless as to what move I should make and which moves would be the most beneficial. The audience that was watching my match questioned on whether a stategy might be to focus on isolating one piece or whether it was to take away as many pieces as possible. Unfortunately, I haven't had the privilage of playing checkers, but could the strategies be similar?

I found a site that seems like it would be helpful. It's a Konane game that uses a minimax algorithm made by someone from Swat. There are three modes: two humans can play, a human can play against the computer, or the computer can play against each other. You can also set the depth of the minimax. Check it out! www.cs.swarthmore.edu/~meeden/konane/carlisle/Konane.html

Jason Coleman

It's funny, because when I played the Konane game Catherine linked to, I tried some of the things I thought were strategy. I tried to keep my edge pieces on the edge (thinking that they are good because they can't be jumped (as much)). I tried to get my pieces into situations where I could jump their piece but they couldn't jump mine. Anyway, I lost! I only played once, but I was trying and I lost. While everyone else it seems played random and won. Jamie might have a point. Maybe I should write my Konane game to play randomly.

About logic and true and false stuff: It seems that a lot of the time we would say "That's not necessarily true..." we point to some factor that hasn't been considered yet. And once you factor in this factor, you can once again say, "Well, if you count factor x, it is false." But then you have situations where it is helpfully to think of things in shades of gray... it's helpful to say "Well, if you count factor x, it is false, but it is closer to being true than say if factor x where equal to y, bla bla." It seems to me that these shades of gray could be integrated into the notion of including more parameters... I need to think this through:

y is true. x is true if y is true, so x is true. BUT x is false if you also consider z, which is false. For values of y and z: (T T) means x is T. (T F) means x is false. (F F) means x is false. Isn't (T F) "closer" to being true than (F F).

My point is that, you could refrase "(T F) is closer to being true" as "(T F), AND if z were T, is true" You could use these if's as parameters themselves in determining truth.

I'm getting lost in my argument... I don't know what the point of this is anymore...

Ian Harrison

On the subject of logic, I was wondering if everything actually could be classified as true or false, assuming you did the classification on a basic enough level and that everything classified was already well defined. Saying that the “economy is doing well” is unclassifiable as true or false depends on not having a single definition of what it means for the economy to do well. If you could take the various data that make up the economy (stock market, interest rates, jobless rates, consumer spending and so on), and then break those data down into the components that are used to make it, you could arrive at a level where everything was either true or false, and from this build back up to answer the initial question. For every person x in the United States, x has a job. That’s a true or false question. Through absurdly long logical sentences, you could then determine the jobless rate, and whether it was currently too high for the economy to be doing well (false), or good enough for the economy to be doing well (true). This does require figuring out how all the different factors that make up the economy interact to affect how well the economy does, but once the relationships are translated into logical forms, they could be used. All that is required to start with is a definition of what it means for the economy to do well in terms of it’s components. Of course, it’d take a whole lot of work to accomplish this, so if someone else wants to try it.

Similarly, aren’t all digital computers, at their core, just really complex true/false systems? Which means, essentially, that all of the AI constructs we’ve examined for digital computers are no more than really complex logic systems. Like the economy model, they are too complex to be written practically by hand, but that doesn’t change the fact that in the end, it’s all either 1 or 0. Does this mean that the same limits that apply to logic systems also manifest themselves in all other forms of AI programming?

Nick Kerr

I am excited to explore uses of logic we have been studying in AI. Like Ian, I was wondering the whole time during thursday's class why it was that everything couldn't be classified as true or false. Often in CS we represent true/false options in binary with a 0 or 1. Deepak explained that some decisions are based on a logic tables with more possibilities than just true or false, which are represented by numbers between 0 and infinity or negative infinity and infinity. I don't see how anything in the real world could be rated objectively without use of a binary system of choices as a subrating. Maybe Ian and I are making the mistake of confusing the way we think about logic in the real world with an implementation style used in programming computers. A similar example to this type of confusion might be thinking that there is no such thing as a four dimensional vector (since we have only three dimensions in the real world), even though we have used higher dimensional vectors a number of times in our fitness assessments for genetic algorithms and other places. I'm basically confused on the issue. I think it would be interesting to see a true false table induced from a logic system with a larger set of statement evaluators than just true/false. The table would get complicated quickly and it would be hard to create in a well defined manner. Just kidding.

Ananya Misra

Larry's comment is interesting...not just because it refers to mine from last week, but because the peg-solitaire game was actually one of my final project ideas. It would have used 32 pegs rather than 13, though, and I was planning to implement one of the search algorithms we did before we moved on to two-person games, like A* or iterative deepening. I ended up not choosing that project because I thought it might be boring to watch a computer play the game--it's not exactly exciting to watch even another person playing it! It may have felt more worthwhile if the computer came up with different solutions using a genetic algorithm or neural net.

Jamie Racanelli

So, I was talking to this girl, and she claims in some weird state somewhere there is some sciency and or farmy place where people stand in line to play tic tac toe against a chicken. I mean come one, what's that all about. But apparently, the idea is that you get a whole heap load of money if you can beat the chicken, not just draw, and no one has beaten the chicken in like ten years. What do we think about this chicken people? I am assuming that the chicken gets to go first, but still. My thought was that maybe the chicken was a robot and it was using a minimax algorithm. But then it wouldn't be a chicken. So if it is really a chicken, then I don't know what it could be doing other than playing randomly. Granted, it is easy to get a draw in tic tac toe, but come on people, it's just a chicken. I was thinking of this story because everyone was talking about how they could be computer konane games pretty consistently while just playing randomly. Maybe there is more to this random game playing technique than we think. Why else would you so often beat a computer that is following some system particular to the game? Perhaps in certain games looking to much into the game (too many moves ahead) is a bad idea. That is, maybe in certain games like konane, moves that look really good three moves down turn out to be the worst kind of moves one move later. I played a lot of othello this weekend and it seemed like a game that might work that way. It's not, and that's why computers are better at playing it, but I hope you get the idea.

Juan Ramos

I tried out the Konane game Catherine posted in her link, and I have to say I found myself in the same situation as Larry last week. I was playing without really thinking seriously about my moves (except that this time, I was allowed to do double jumps!) In the end, I still won even after I thought the computer was giving me a trashing. This makes me wonder if the evaluation functions we create for our own Konane games will be able to return results that make the computer a challenging opponent. Hopefully, our algorithms will be challenging enough that we'll have to rely more on strategy than luck to win games.

The next time I played (with a depth of 6), I did double jumps every chance I got, and this time I lost. This seems to go with what was said in class in that double jumping may not always be the best option. However, I think that never double jumping (or triple-jumping, etc.) is not a good solution. I think a mixture of both would be a better approach, and make the computer pick accordingly from which move returns a better value after checking it with the evaluation function.

Matt Rushton

I thought the stuff on logic programming we talked about on Thursday was pretty interesting. I can definitely imagine situations where it would be particularly useful, like say in word problem solving. I do get a little hesitant though in using it in the real world, because of all the gray areas that any sort of logical statement may encompass. However by restricting the tasks and responsibilities of a robot using logic, I feel like it could be capable of some pretty interesting things. I don't know if you could classify behavior like this as learning (ie. Fido is a dog. Dogs have four legs. Thus Fido has four legs), but it is pretty close. I think you could certainly argue either way. On one hand the programmer never explicitly told the computer that Fido has four legs, but on the other hand he did say all dogs have four legs. Again I think you could make a pretty convincing argument either way.

Tina Tan