Melagagir

Now that we’ve talked about how to “score” a board, we can talk about the min-max algorithm. Now if we didn’t want the AI to look very far ahead, it could just pick the move that scored the highest amongst the its possible moves. That is, it could pick the “max” as the move to make.

To look further ahead, though, the AI  has to anticipate the opponent’s move. To do that, the AI looks at the opponent’s possible responses to its move, and assumes that the opponent will choose the lowest scoring move. The lowest scoring move is the AI’s opponent’s best move, that is, the worst one for the AI. This is the “min” move. The AI’s opponent makes “min” moves, the AI wants “max” moves.

This will make more sense as we examine this diagram:

Now if the AI is only looking at the next possible move, it’d probably choose the move that leads to B, since it has the highest score. But, if the AI’s opponent chooses the move that leads to F, our choices (N, O) are less than ideal. If it happens to make a mistake and choose G, our choices are still not the highest scoring moves for us on the bottom level (the leaf nodes).

We could have the AI look at the highest scoring node on the bottom level and choose the move that leads to that move. For example, M is the highest in the diagram, so the AI could choose A. But…if the opponet chooses D in response, we’re left with sub-optimal moves again. So the AI must consider the “min” as well as the max. With this diagram, the best move for the AI to make is C, because we predict the opponent will choose I, and in response, we can choose U, which is almost as high scoring as M, but more likely to be reachable if our opponent makes an intelligent choice.

With this technique, the “intelligence” of the AI becomes dependent on how quickly it can compute the boards, and how deeply it can look before it runs out of time. Since (as we discussed earlier) the trees can get immensely large in the mid-game, we have to find a way to achieve the same search…but with less computation. We’ll examine how in the next installment.

Before we can talk about how to make searching the state-tree more efficient, we have to talk about how “rate” the states in terms of their usefulness to our goal of winning.

First, there is a routine that just adds up the value of a board. For discussion, we’ll call it a “utility function” (my textbook called it that!). The utility function scores positive points for elements that favor the AI, and negative points that favor the AI’s opponent. With Othello, the “obvious” (but wrong, as it turned out) thing to do is the score 1 pt for each square has the AI’s color in it, and -1 for the each of the opponent’s, and 0 for the rest. So boards where I have a majority of the pieces will score higher, and boards that my opponent has the majority will score lower.

There’s a problem with this, however. Strategically, if you play by selecting the move that produces the most flipped pieces at the time, it is likely you’ll lose, because a skilled player will trap you into making moves that favor them. It turns out that control of the game rests on three things: 1) If you have very few pieces of your color on the board, your opponent’s options become very limited…you can control the opponent this way in the early/mid game. 2) Playing to obtain the corners is critical, because the corners can’t be flipped. 3) Similarly, the sides have a bit of power, with an exception: 3) It turns out the spaces immediately adjacent to the corner are “bad” places to play, because they set up the opponent to take the corner.

Some of this I learned through experimentation, some I learned through reading about othello strategies, othello-AI strategies, and the like.

So in the end, I had the corners worth a large number, the spaces adjacent to the corner worth negative, particularly the one diagonally adjacent, since playing there pretty much guaranteed the corner to the opponent. The sides I gave a little bit of points to, the rest were worth 1 pt, except the starting four squares, which were worth zero (they get flipped nearly every time, so they’re strategically valueless).

Armed with this idea of a utility function, we can talk about the base-algorithm I used in the next installment.

In a passing comment recently, I mentioned writing an AI to play othello in my AI course. Regabyr expressed some curiousity on how my AI worked, so I thought I’d talk about it here.

Let me cover the background for the assignment first. The software engineering class had a group project to write a network playable Othello game which had a client capable of executing a Python scripted AI. The AI class then had a individual “Final Project” to write an AI to play Othello.

I learned a great deal in the course, which of course, I don’t want to cover all of it, but I’ll give enough explanation for the technique I used to make sense.

First of all, consider the game of Othello itself. It has two players, who take turns. Each turn produces a new arrangement of pieces on the board, a situation we could call “the state” of the board.

Which leads us to one of the ways we can approach the problem with a computer program. We have our program build a “tree diagram”. We start with the current state of the board as our starting point (the first state). Then each branch from the starting state is one of the possible moves for the current player, each leading to a new state. For example, at the beginning of the game, the 1st player (always black discs) has four possible moves. After the black makes his first move, white always has three moves. In fact, the state tree looks something like this:

So the program could examine this tree, examing every possible state, until it reaches the bottom of the tree (the point where both players can’t play any longer, and someone has won). Then it could pick the move that led down the path to the best chance for the AI to win. Except…there is a problem.

It turns out the state tree is really really large! You can’t see it in the diagram above, but with the very next move the tree’s width starts expanding with each layer dramatically. For example, the next layer in the diagram above would have 56 boxes…and every box takes a while to compute.

In other words, we need to find a way to make it more efficient…but we’ll have to figure that out in a future post.

A friend of mine started a new business recently, and even more recently open a physical location for it. So I attended his grand opening today.

Art, once a database programmer, has turned to photography as his current career. To expand his options, he opened a physical location in downtown Columbia. In addition to his own photography he is renting out the studios (yes, plural) to any photographer that needs to use them.

The space is awesome. He found a large place on Columbia’s primary “downtown” street, Broadway. He’s divided the main large space into three studios, one of which if necessary could been ‘curtained’ off to create a fourth.

The main studio is large enough (and has entrance to the outside) so that if you desired, you could pull a car into it and get pictures taken with the car, of the car, etc. Or some other large item.

Or the large studio could be setup with a ’set’, if wanted to some shots with a particular setting in mind. Awesome stuff.

If you’re a photographer in the Columbia, MO area, and interested in renting: Su Casa Studio

If you want Art’s services as a photographer: ArtSmith Photography

In any case, tip your hats toward a new entrepreneur!

After today, I have one more week of classes, then finals week. I’ve positioned myself well in the majority of classes, so there’s little uncertainity at this point. I love going into a final knowing things like “Hm. to keep my A, I need 69% on this test…”

Addendum: As of today, you can ’subscribe’ to this blog, either via your user control panel (if you’ve registered), or by putting your e-mail  on the right and clicking the button.

Now you might think that I know christmas-time is here because, well, its december, or perhaps because it is cold outside, or perhaps my neighbors musical christmas lights display is playing, but no, there is a far better indicator than that.

Angry-mama drivers. I can almost set my calendar by it. Dec 1 rolls around, and wham! The most aggressive (and apparently most incompetent) drivers descend on the roads. I know from experience that at first I’ll see one or two; and then as the month progresses, the roads will be crawling with them as that deadline of Dec 25 approaches. Getting from point A to point B is never as frightening as it is during the holidays.

Some woman tried to run me down yesterday in her big ol’ SUV monstrosity, me in my ford; my offense? Slowing down to make my turn safely. I have a few choice words for her…which I won’t print here.

Message Ends.

I don’t even know how to title this. The husband of one of Melalvai’s coworkers died Friday. At the age of 31. Thirty-one.

We don’t know the means, other than ‘peacefully at home’, but Melalvai mentioned to me that he had several of the risk factors (weight, smoking, etc.) that’d lead me to believe it was heart disease related.

It boggles the mind though. five years younger than I; some number nearing 30 years younger than my parents, and just …gone, early.

I don’t know. At least should make one stop and think for a moment.

I didn’t know either of them very well, having only met them at work social events.

Everyone keep his wife, parents, and siblings in mind this week.

http://www.columbiatribune.com/2008/Nov/20081123Obit003.asp

Family and I decided to struggle for world domination this weekend. Here’s a snapshot from the Gunpowder Era:

Ten and fifteen minutes agone, Xylia set out on a quest. She sought out the terrible monster that resided in the lair of a giant.

She traveled across the long sandy desert, up the tall mountain with its shelf-shaped rocks, to the Giant’s abode.

The Giant’s door was too large for her to open; but she knocked upon the door most carefully. The Giant, believing it was his daughter’s delicate touch, opened the door.

 As soon as the door was open a small piece, Xylia slipped quickly inside and hid beyond the Giant’s reach and waited.

Later, while the Giant slept, Xylia went to the Giant’s dungeon in the far corner of his abode.

There, she fought the ferocious beast and nearly didn’t survive. Her battle lasted for twenty and ten minutes, and after a ferocious mauling, finally the creature yielded and Xylia was able to rest.

This coming monday, my “junior” year of college begins. I’ll be studying artificial intelligence, discrete mathematics, automata theory, and logic.

Automata and AI will likely be the toughest classes, they’re complex subjects taught by a brilliant professor who moves fast and likes to push students if he can. They’re also the most interesting classes, although it’d be difficult to describe why in a limited number of words. If you’re reading my blog later in the semester, you’ll likely hear about them some more, both good and bad.

f.

Fourteen years as of today.

Not much more can be said.

I took the basic ethics survey course this last spring. It made a fast pass over three of the main methods of determining whether an action is ethical. I found it interesting and useful, I found myself looking at some choices through each of the method’s lenses, testing my own belief about what the right choice should be.

I feel there is a lack in these philosophies and I don’t have reason to believe that their relatives or derivatives address this lack: It is one thing to know what the moral choice is, and quite another to successfully implement it. They seem to fail to address the very real issue that the reason we’re thinking about this at all is we’re faced with the very real limitations of flesh and bone, we know that our emotions can mis-guide us, and so we write these moral philosophies in hopes of producing a guiding principle that will work despite our feelings.

 Just because we have a guiding moral principle doesn’t mean the feelings go away, though. So the real question becomes, having determined the moral choice, how do we “crack the whip” over our heads and demand that this lump of meat do the right thing?

When I started writing this, I didn’t have any useful answers. I have one now, but only one. I think we need more than one, but maybe this is all we have. Love. For me, at least, feeling love and caring for others gives me all the strength I need. The right action becomes the easier path when we have examined the wrong action for its impact on others. The wrong action is only appealing because it appears easier. Once examined for the ripples that will go out from a wrong action, the wrong action becomes a terrible gauntlet, and the right action becomes something beautiful and irresistable.

I confess. My first measure of whether an action is right or wrong, is an examination of the source of my motivations. In my view, even if an action is analyzed and found to be the right action, it is still the wrong action if the impetus derives from anger, hate, or even indifference. No matter how right the action is; if it comes from a place of darkness in your psyche, it will be overshadowed by that darkness. The converse is true as well…an apparently wrong action may very well be the right one, if it truly comes from love and caring.

A simple example of this comes from people around me. I have friends that greet each other with profanity; a custom I’m not terribly comfortable with, my upbringing says that such behavior is wrong, that is that using such language is hateful. But when these friends use that language with each other, and it is right because its coming from their love and concern for each other. Took me a while to wrap my head around that idea.

I’m sure we can all think of examples of “nice” things, that are in fact, quite nasty. We’ve all had the experience of someone saying things that if you looked at them without the tones and emphasis, you’d think they were nice things…but the velvet is actually there to hide the dagger.

Love,

Feaelin

I know this story is already a month old, but I had to comment on it. I only recently heard this story and went looking on the web for it. The following article sums up the event:

http://nbcsports.msnbc.com/id/24392612/

These two ladies deserve a great deal of admiration! Acts like theirs is what I think of when I think about honor. 

Mallory Holtman and Liz Wallace, you just made my list of heroes.

My college has an ethics course that all undergraduate students are required to take. I was concerned that the class would be a miserable experience; as a mandatory course, you get a fair number of people that don’t want to be there, and the instructor could easily take the same attitude (in response to indifference of the students).

I am pleased to discover that my concerns were unfounded. One thing that helps that you cannot take the course until you have junior standing which improves the quality of the students in terms of age/maturity and academic commitment.

The instructor makes the real difference though. He has an easy and clear way of presenting the material in the lecture. I have no difficulty identifying pertinent information that needs recorded in my notes and as appropiate he slows to allow us to get our notes without missing any of the material. He does a good job of focusing on understanding the concepts an ideas, rather than the class being a recitiation of terms and definitions.

He also creates an atmosphere that makes it easy for discussion. Some professors consciously invite discussion or participation by asking questions; but this guy somehow projects a feeling that makes (me at least, and I think others) comfortable speaking about our own points or questions.

I should say this isn’t a “contemporary ethics” course. It doesn’t try to take current social/moral concerns and talk about them. Instead, it is (an introduction, really) to methods for making moral choices. The professor says that there are in general only three methods. We are going to look at one representative philosopher for each method: John Stuart Mill (Mill’s brand of Consquentialism: Utilitarianism), Immanuel Kant (Kantism, Deontology), and Aristotle (Virtue Ethics).

Since the subject material interests me and the class has a excellent instructor, I fully expect to enjoy the class and you can expect more blog posts about the class.

This is a long and possibly uninteresting story, but it is an important one to me, so you have to read it anyway.

The first time I attempted a bachelor’s degree, I went to college immediately after high school, Fall of 1991. I ended the semester with a GPA of 0.71 (4 point scale). That’s not a typo, that’s what you get if you have two 3-credit D’s, two 3-credit F’s and a 2-credit C. (Interm Algebra, American Government, Latin I, English Comp, and Fitness for Living, respectively)

I won’t explain in detail why that happened, but I will mention the important part: My education, the degree, and thereby the classes, didn’t matter to me. There is a lesson there, but it’d be a distraction from my story, so we’ll move on.

A 0.71 GPA is an automatic academic suspension. So the following semester, I was suspended from taking classes at all. But that summer, I made an attempt to repair the damage: I re-took intermediate Algebra (as a summer evening class, no less, it met only once a week!) and replaced my prior grade of D with a B. CGPA: 1.14.

Then in the fall, I took a 1 credit course ”Intro to Library Science” I honestly don’t recall why, other than to pad my GPA a little further. CGPA: 1.20.

Then I took a “full load” in the spring of 1993: Pre-Calculus (5), English Composition (3), American Government (3), Electronics Survey (3). Not precisely a success: respectively: D, C, C, N. CGPA: 1.60. And another academic suspension.

Then I retook Latin I (Fall 1994) and got an A. Awesome, that raised my CGPA to 2.20. Which completely removed me from academic suspension and probation entirely. Finally, something good!

I followed up in the Spring of ‘95 with Latin II and got a B. CGPA: 2.30. The following fall (1995, Nelalvai is 2-3 months old!), I attempt Latin III, but withdraw (safely, so a grade of N). Final CGPA from the entire four-year fiasco: 2.30 (w/replacements).

Meanwhile, while my academics went up and down repeatedly, I started working at Best Buy in the summer of 1993. At the time, it was a significant increase for my income. I worked there a year before getting a position in a tech support department in the city government. The pay and hours were better and during the two years I worked there, I gave up on the degree entirely, and focused my attention on bringing a paycheck home. A big factor was simply I liked having an income and having a wife and daughter played a significant role in that point of view.

The position at the city government put enough experience (2.5 years!) under my belt I was able to get a salaried position in a department of a large university, where I worked for seven and a half years.

Then we made a mistake. My wife completed her doctorate in Biology in May 2003. For her to do her post-doctoral work, we needed to move to another city. All a good thing, significant achievements for her career. But we mistakenly thought we could make the move without lining up a job for me first. We had the idea that as a computer tech, there is always a position available. It didn’t work out that way. The nation was in the throes of the recession that is still being felt today, the market became very competitive and for a guy with experience, but lacking a degree, it became very challenging to obtain work.

I ended up either being unemployed or working near-minimum wage jobs the whole year. Yes, only a year. Because then we bailed out of the situation (our hindsight says we should have bailed sooner). The city we were living in had an incredibly higher cost of living than we had previously experienced, and we were rapidly racking up an unmanageable debt.

So we fled back to the town we moved from. Melalvai was able to get a post-doc position through her contacts in Biology, I acquired a part-time (but only 1 year) job at my old employer and started getting ourselves back on our feet.

I went from the part-time job at the university to a sales position at a movie rental chain, and got fed up with evil business practices and “palace politics” of the job. Combine that with an especially uncomfortable job interview (in an attempt to find something better):

I came to the realization that I would be stuck in crappy jobs forever if I didn’t get a degree.

We’re almost to the present, but not quite. The job interview made my decision. I started looking seriously at what it would take to put me through school: Financial Aid, etc.

I had a certain amount of loyal feeling to the university that employed me; I had had a good run of years of employment there. Also, it was a major university and would look decent on my resume. I examined their enrollment requirements, and the main relevant one was a 2.0 GPA minimum. Since I had brought my GPA up to 2.3 via replacing grades (back during the 4 year fiasco!), I figured there would be no problems.

I was wrong, as you can see above. It turns out the university had the most draconian method of calculating your GPA for purposes of admission. If you had taken a class twice, they counted BOTH grades in calculating your GPA. So instead of them saying I had 23 hours with a 2.30, they said I had 35 hours with a 1.686 (because they were including those F’s and D’s I had replaced with B’s and C’s). Despite it being a decade since I was in school, they rejected my application. I still have many choice words for this kind of bureaucratic nonsense…[1]

So applied at a local private college instead. THEY were able to calculate (its disturbing that a major institution isn’t capable of doing math…) my GPA correctly, and so despite them having the same minimum GPA, I met the 2.0 requirement with my correctly calculated 2.3 GPA. As it turns out, it may have been a better choice anyway. They are a smaller instution, with small class sizes, which means greater support from the instructors and a much more personal feel. I never feel like the support staff or faculty do not care about the students (a feeling I often got working at the university).

Today is the first day of my fifth semester at the private college. Every course (43 credit hours!) I’ve taken so far, I’ve gotten an A in. Obviously, I’m quite proud of this! And have some desire to give the university the bird: “See? I was a good risk. Your loss, not mine!” or something to that effect. CGPA at the private institution is 4.0. If I include the 4-year fiasco, my overall CGPA is: 3.41 (calculated the correct way). Calculated the way the state university did it, I have: 2.96. Ha!

I wanted to talk about how school is going now, but I also wanted the foundation of what my past situation was and at least an inkling of how much completing the degree matters to me written out first.

 [1] I should add here that at the same time, they were bureaucratically screwing with my wife’s grant money, but that is an entirely different story.

I had the extraordinary priviledge of attending a lecture given by Jane Yolen this evening. The lecture was titled Stories Are More…And Less…Than We Think. A wonderful and interesting lecture on the “hidden morals” in fairy tales and the origins of those fairy tales, as well as interesting anecdotes about those that craft(ed) them.

As I listened to hear talk discuss some of the original versions of fairy tales and the differences between versions not just across time, but country to country (The Little Gum Baby…), I got to thinking how much fun it would be to read stories in that fashion, not really by author or series, but more by the links of retelling, similarity of purpose or agenda. Studying history through fiction, perhaps. Not sure how to describe it, of course.

Then I remembered my first passion: Computer Science. I was brought back down to earth, in a sense, remembering that while I might enjoy stories for a while, I have a passion for programming/computer science. That of course led me to ask the question: “Is there a way to combine the two?”

Commercial worth watching

http://www.flixxy.com/wilkinson-shaver.htm

I love the fight scene references, I saw references to films I’ve not seen in decades.

I’m kicking back in my living room, listening to my daughter and wife play trumpet and clarinet together.

It is a completely amazing thing for me. They both pick up their instruments and music comes out. In between songs, they communicate briefly about the music and how to play, while I listen in (baffled) wonderment at the very technical language employed.

Part of my wonder may stem from not being able to play an instrument myself and alongside that, there is something exceedingly cool about your daughter having skills that you don’t or exceed yours.

A Youtube video worth watching:

http://www.youtube.com/watch?v=ngRq82c8Baw

I think Nelalvai has covered the “Darkside” of our camping trip thoroughly enough that I’ll simply link to her blog entry:

http://www.kemenel.org/nelalvai/journal/?p=5

 There was a great deal of inappropiate language, loud enough for the whole campground to hear. And not  just regular dialogue punctuated by profanity (which is pretty common), but loud and boisterous discussions of a nature not appropiate for families. Or anyone else in some cases. Their racist talk was especially inappropiate (and no, I don’t see any reason to repeating it).

Their behavior underscores why I have such a strong dislike for profanity (and yes, I engage in it myself, just more often than I prefer), I /feel/ that most profanity I hear is of a hateful nature, which is never appropiate.