Melagagir

Software Rebuild. A phrase I have mixed feelings about. On one hand, it can be very effective at eliminating many problems that a machine has by the virtue of clearing out the chaff that accumulates on an active machine.

On the other hand, in an ideal world, we’d tackle each problem that the machine has, identify it precisely, affect a solution and document how we identified the problem and what steps we took to solve it…and add that to the collective knowledge.

Some problems are fairly elusive (particularly intermittent ones), hard to trace, and even if you narrow it down, sometimes hard to resolve. In short, the ideal practice I described is time-consuming, frustrating, and frequently fails (leading to a rebuild anyway).

I’ve done many software rebuilds on machines, with many flavors of windows, a few Linux boxes, and a few Macs. (The many vs. few doesn’t really reflect on the OSs in question, it merely reflects the percentage of machines running the respective OSs. Our network, for example is 3 windows, 2 Linux, 0 Mac at this time…).

So we have a machine whom we’ll call Lapis. It is need of a software rebuild, which will hopefully clear up the numerous problems we’re having with it.

The first step is always, always, always, … to backup the current machine. As entirely as possible. Fortunately, I have a great software application for generating images of hard drives or systems. Acronis TrueImage produces an image of a hard drive, that can be later restored to the drive, extracted if you want, or browsed as if it was a folder on the your hard drive (this last requires Acronis to be installed on the system in question). Great stuff.

The image of Lapis is 35GB. Not bad, considering the size of many modern systems. But…to wipe the drive, I have to have that backup on some other system or drive. There, the pain arrives. Lapis has difficulty communicating with our File-server. So I can’t just copy the 35GB file to the fileserver.

The easiest route would have been a external hard drive…which I don’t have and of course, I don’t want to spend the money. Then I remembered: I have a 80GB SATA drive on a shelf, that came out of another machine when its HDD was upgraded. Voila! The solution. We mount the drive as a second drive on Lapis, copy the image to the drive, mount the drive in the file-server, copy the file from the drive to the file-server. Presto! We have the backup image on the 80GB drive and on the file-server. Briefly, we browse the image file on the file server, opening some individual files from the image to make sure it is a good copy (ideally, I’d do a verification against the original drive…network issue, alas). And we’re in business.

Course, we’ve jumped through all of these hoops, and we haven’t even wiped the drive yet. joy.

I said in my previous blog entry that I’d be working on updating the wordpress theme. I got as far as installing wordpress 3.0 on the internal only, test webserver on my development machine, poked around a bit, then realized that I was neglecting something else I had already started:

Correctly reimplementing changes I had previously made to the Kemenel.org forums (which run phpBB) in the latest version of phpBB, in such a way in the future the forums can be easily updated.

In other words, back to work for me. Hopefully, I’ll get started on that work tomorrow. It may be more of challenge without the internet. Might have to see if the library has a good PHP reference if I need to lookup some finer details of PHP functions. :/

f.

So a growing problem for my wordpress blog is that this theme, Thirteen, was produced for a much much older version of Wordpress. Unfortunately, the theme composer has apparently “fallen off the web”, I searched and all that I found about her was people looking for her for the same reason I was.

I really really like the theme, though. It is very Feaelinesque. I have been considering “recreating” it for a more current version of wordpress. Since Wordpress 3.0 has come out, it seems appropriate to try to recreate it for Wordpress 3.0, and migrate my WP to 3.0 and “Thirteen 3.0″ at the same time.

We’ll see how it goes. First steps are downloading WP3.0 and picking apart how their built-in default theme is put together. Joy.

f.

Most of the projects on my radar these days are web-based or web-related. While I have a fairly good knowledge of (X)HTML, my knowledge of CSS is pretty sketchy. So that’s where I’m starting on moving forward on my summer plans: Brushing up on HTML, and actually learning CSS from the fundamentals (instead of doing minor stuff from example, and not understanding the complex stuff).

For fast introductions to both, I found: HTML Dog a pretty handy tutorial and reference site. I’d like to have a full-tilt, well-written, standards aware book, but I’m not sure I’ve found the perfect one yet.

For the less technically minded: I imagine you’ve heard of HTML, the language that is used to describe web pages. CSS is a language used to describe how a web-page is presented. So what you see when you’re looking at a web-page is composed of HTML which has all the content, meaning, and structure of the page/document, while the CSS contains all the positioning, color, background images, etc. Or should, anyway. In practice…that’s a different story.

---

For some of the projects, I’ll have to do some programming in PHP, a programming language designed to run on web-servers. Since it is designed to run on a web-server, it becomes difficult to perform proper debugging. So I’ve been a quest for a while now to come up with a tool (or tools) that would allow me to step through a PHP program, the same way I would a desktop application.

I believe today, the last piece of a setup fell into place. A combination of XAMPP which provided me a web-server and MySQL database server that I didn’t have to fight tooth and nail to install. Maybe just a tooth.

Then, on top of that, with carefully setting up the project in the right place, I’m using NetBeans as an IDE (code editor). And I can step through my PHP programs from within NetBeans (running against XAMPP). Happiness.

I’m hoping at some point to talk about the design process of a project or two, but not today.

Unfortunately, before I can do all the stuff I talked about in “What’s Next“, there is a much more immediate, possibly more daunting task: moving.

You’d think I’d be used to this by now; I moved at least seven times as a minor and I’ve moved about seven times as an adult. However…

I really hate chaos. And moving is chaos. You spend a couple of weeks dismantling your base of operations (e.g. home), packing it into boxes, cramming it into a truck…the whole time playing “hm, I could use X right now, where the #)($*#)(*#$ is it?”

…and then you get to the other end, and spend a few more weeks trying to figure out where it all goes in the new base of operations.

Gah.

Sixteen days until moving day. 71 boxes packed. eek. Stay tuned. The chaos might shove my mental state into a Poe-like story…

I was asked “what are you doing after you graduate?” and its variants pretty often the last few weeks. Anyone that knew I was graduating probably asked the question at some point. I tended to give a non-answer, not because I didn’t have some idea, but because it was difficult to explain succinctly.

I’ll answer here, and I won’t be concise or succinct.

First, Melalvai accepted a position as a Research Assistant Professor, a fancy way of saying she gets paid to do research (and only research). A really great opportunity for her and thus we’ll be moving.

The first thing on my mind then is getting us settled in a new house in a new town. Nelalvai will be on summer vacation, while Melalvai will be busy with her new job. To my mind, a very important task this summer is to get our household set up and helping Nelalvai settle in at a time when she doesn’t have school to occupy her.

That will be sort of my first priority, but I doubt that it will take all of my time. So the next question is, what will I be doing about becoming a productive member of society?

I wouldn’t turn down a full time job offer, if the right job turned up in the area. It is a small town, though, so I may have some difficulty in that regard. I’ll go ahead and update resume, create a portfolio and canvass the area looking for IT jobs.

On the other hand, I’m considering various self-employed options. Freelance programmer, internet services, IT guru-for-hire, etc. Melalvai’s new job makes experimenting with such a venture a viable option. Her salary and benefits make it possible although not easy to deal with any potential lack of income on my part, particularly since her package includes full benefits for her and family (a huge area of difficulty for the  self-employed, the lack of benefits).

That means my first “job” this summer will be hammering out a plan of what I’m going to do, looking an options, examining project ideas I’ve had and see if they really are viable if you shine some light on them…etc.

In the meantime, if a job opportunity presents itself I can’t refuse, I’ll take it.

It has been a long time since I’ve written anything here. The pursuit of a Bachelor’s degree consumed nearly all of my attention, and definitely removed any desire to write. Finally, on May 8th, 2010, I graduated with a Bachelor’s of Science in Computer Science.

And I started waking up. I didn’t realize it while I was in it, but getting a degree mattered far more to me than I had thought. I suppose, it became a point of pride to succeed where I previously failed, where University of Missouri told me I wouldn’t succeed (see: Gettin’ Learned).

I had some idea that it was important and that as a result that it had my full attention, but I had no idea what that actually meant for the world around me. I realize now, how much of the “world outside the ivory tower” I had been ignoring.

Sure, I knew that my wife and daughter were not getting much in the way of attention, but it isn’t until now that I realize how out of balance I really was. The girls at least had the advantage of being in the same house with me and could easily demand some time. On the other hand, past colleagues, friends, and the rest of my family had no such chance.

Not to worry. I don’t regret it. These four years was an extraordinary experience, I laughed, I cried, I stomped around in anger many times throughout, but now that I’m here at the end, I’m (almost insufferably) proud of what I achieved in those four years and graduating (me! graduating!)

It isn’t just my achievement though. A great many people got me here, many of them I absolutely couldn’t have done it without, and many others who made sacrifices while my attention was elsewhere. Melalvai and Nelalvai had to put up with the most, swiftly followed by many friends and family: Regabyr, Pangie, Chris, Julie, my mom, Melalvai’s parents and siblings, my sister, my brother, Katie (and Valhallas Gat e!) Leah, Ken-meister, Randy, Karen, Art, the staff and players on NarniaMUCK, the players on UniversityMUCK, I’m sure I’m missing someone…this list keeps growing as I write it. Maybe I should just say “A whole lotta people, and a whole lot more!”

Everyone of them helped in a variety of ways. Many of them have heard me griping about assignments and the like, or how much I can’t stand something; all were neglected in some fashion or another.

I have a Bachelor’s of Science in Computer Science. And it was a group effort, a group achievement. All of you who supported, endured, encouraged, and listened these four years, each and every one of you deserve a share of the credit. Walk around proud of our achievement. I like to think we did a good job.

Thank you,

Feaelin Moilar

This discussion of an Othello AI began after I completed an undergraduate course in AI. Our ‘final project’ in the class was an AI challenge: Each of us wrote an AI which we then played against each other using a network based Othello game written by the Software Engineering class.

My AI won the challenge. However, I don’t think my winning edge was the AI technique itself. We had all studied the same material in class, so in terms of AI algorithms, we tended toward the same techniques.

My advantage lay in the region of the time limit imposed by the contest. Each player(AI) was allowed 5 minutes of thinking time for the entire game. With that kind of time limit, managing your time becomes important. If you spend too much time on a given turn, you’ll run out of time before the game is over, effectively forfeiting the game. Spend too little time on a move, and you’ll not search the tree deep enough.

So on top of my implementation of the alpha-beta search, I came up with a technique to manage the time carefully.

The first step is in response to game server. It would send me message informing the AI the current state of the board and how much thinking time was left. The AI would compute the number of turns left in the game by simply counting the number of empty squares. It then computed how many seconds to expend on the current turn.

Unfortunately, that isn’t enough. Consider: AI computes that it has 13 seconds on the current turn (a typical number around the 2nd move). Perhaps at the current state of the game, the AI has twelve different squares it could play. It starts computing the effectiveness of the first option…and takes the entire 13 seconds. Oops. The AI examined one possibility and has no idea whether it is the optimal choice or not.

That’s where the next aspect of my time management came in. When the search begins, the AI counts up the choices  it has, divides the time evenly amongst them and searches each of those branches only that amount of time. With our current example, the AI would spend ~1 second for each of the possible choices.

Further, it passes this value along. So when searching branch #1, the AI sub-divides that 1 second across the branches of branch #1. So if branch #1 has 10 branches, the AI searches each of those for about a tenth of a second.

So the AI searches to some depth and stops, because it doesn’t want to spend too much time on any one branch of the tree. Then it comes back up, searches another branch, and so on.

The overall effect is that if the AI doesn’t explore the tree to the bottom, it at least explores each possible move to roughly the same depth. In essence, looking ahead as far as it can for every possible move. To use some CS terminology, it transforms what was a depth first search into a depth-limited search.

I had one additional refinement to make the time management complete. The amount of time to use for an option is based on the number of options left.  If it happened that the AI is searching a branch and reaches the bottom before the time used up, before attacking the next branch, the time is redivided amongst the remaining choices and we keep searching. That way if a branch is quickly eliminated, the AI could use that time to search deeper on other branches of the tree.

Last time, I mentioned that the size of the search tree gets really large for the midgame in Othello. In fact, by the third move (that is the starting player’s second move), there are sixty possible states in that level, and the tree widens dramatically from there.

An AI that takes days or years to calculate its next move will likely forfeit, most games have SOME kind of time limit. So we need to find a way to reduce the search time. One way is to make our  utility function as efficient as possible, but there is only so far you can go with that.

What if, though…we could find a way that we didn’t have to search the entire tree? Could we evaluate some branches as being “most likely useless” and not search them at all? That could eliminate hundreds of nodes (and correspondingly hundreds of calls to our utility function). With Othello, the depth of the tree is about 57-60 nodes (60 is absolute max, since 60 moves fills the 8×8 board). So if we could eliminate even one complete path through the nodes to the end of the game, that’s a reduction of ~60 calls to the utility function.

There is a cool technique that does. It is called “Alpha Beta Pruning” and a min-max search using it tends to be called an “Alpha Beta Search”. The name comes from two values you keep track for each node, named “alpha” and “beta”.

The technique is primarily a refinement of the min-max algorithm we previously discussed. In the min-max algorithm, we chose the move that would lead to a high score for us, while assuming at every step, the opponent would choose their best option available. In an Alpha-Beta Search, we use a similar decision making process to eliminate entire branches or possibilities from our search, reducing the amount of time it takes to search.

I’m not going to describe the full algorithm since this article has already waited a year to be written because I got busy. If someone is truly interested in the details perhaps I can talk about it again this summer.

The key idea of an alpha-beta search is that we “prune”, that is we ignore, certain branches of the tree entirely.

The ignored branches are chosen by examining the level of the tree where it is our opponent’s turn. We ignore those branches that our opponent would not choose…because they are bad choices for the opponent. (This assumes the opponent is going to choose the better moves of those available).

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!

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.

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.

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.