yet another blog about computer, technology, programming, and internet

Monday, March 19, 2007

Is It Legal To Be This Good?

Monday, March 19, 2007 Posted by Ismail Habib 26 comments
Yupe, that's one of the comments targeted to macpulenta, a user in YouTube.

Check this out:


This guy is really awesome, not to mention that it's not his only work published at YouTube. I guess it is worthed as the first video in my blog. Nice work... I mean amazing!!

Btw, who's the guy he painted anyway? Not really that important though.

For those of you who's expecting something that's programming-related, sorry to disappoint you this time...

Sunday, March 18, 2007

Artificial Intelligence in Reversi/Othello Game

Sunday, March 18, 2007 Posted by Ismail Habib , , 53 comments
One of the most interesting field in Artificial Intelligence (AI) is the computer game -at least that's what I think-. While The AI is not yet capable of creating a human-level robot, it's already useful in many ways and game is just one of them. Most of the computer games we play right now uses AI since sometimes (or most of the time) we just couldn't find anyone to play with. Probably you don't even care how AI in computer games work, but if you do and you want to learn something... this post might worth some of your time.

Here I'm going to use a simple case: a reversi (othello) game. For those of you who don't know what is reversi you may click here to get some ideas. In the reversi game, the goal is to beat your opponent by outnumbering the number of opponent's discs. While this game looked simple and easy, actually it's quite difficult to master it, especially when you realized that there's actually a world-level competition for this game. In the other hand, the level of AI created to play this game is already incredible compared to the level of AI in another games such as chess or go. To be more specific, human doesn't stand a chance against AI in a reversi game. Surprised?

Designing the AI for Reversi

First, we need to see the properties of reversi game. Let see if I could describe some of it:
1. Full Information: no game information is hidden
2. Deterministic: action determines the change of game states, no random influence
3. Turn-based: makes life easier ;)
4. Time limited: obviously... who wants to wait an hour just for a small move in the game?

OK, now it's time for practical matters. Let's say that the AI reversi represents as a computer agent. The agent need to decide its movement for every turn in reversi game. It has to find a "best" movement possible from some legitimates movements possible. Simply said, it is a searching problem. In order to exploit the greatness of computer in conducting a huge number of process in a short amount of time, we can use a minimax algorithm. Minimax algorithm is a decision function that try to maximize the result within the search space by assuming that the opponent is rational (always choose the best movement possible).

Here a simple example of Minimax:



Assume that you're moving first, and the opponent will have a chance to move right after your turn. The picture consists of several circles that represent a state. The value/number in the circles represent your score after two movements (one movement from you and one from the opponent) in that state. Obviously you want it as high as possible, and the opponent want to do the opposite. Lines that connect states is actions that may be conducted, each lines connect two states, the initial state and the outcome states that will be activated once the action is executed. The question is: from action A, B, or C... which one would you prefer? According to Minimax algorithm, the opponent is assumed as a rational agent (or human, whatever). Therefore, given the values in every states at level 2, the opponent should choose the best movement for it which is the minimum value from three possible states. Then, from our point of view, we have three values for three possible states which is -3, 1 and 0.



As a conclusion, action B is the best option according to the Minimax algorithm.

The Strategy

Let's take a nice look again to the pictures. We have a diagram of states with 2 ply and some values at the ending states. Where are those values come from? We may say that in a reversi game, those values are the number of pieces that our agent has compared to the opponent's. This might be true however with some limitations: you want to make a stupid agent or every last states should be the ending states (the end of the game). In most cases, it's not possible to make a search until the end of the game especially in the first several movements because the search space that could be computed is limited due to computational limitation. Therefore we need to use another values to put at the last states: evaluation function. Evaluation function could be something very simple such as the number of our agent's pieces to something that is very complex. Here is where the strategy take places. Rather than naively attempt to get as high as score possible, there are several features that should be use in order to design a evaluation function:
- mobility (the number of possible movement)
- the number of pieces that couldn't be flipped by the opponent (eg: pieces in the corners)
- positions value

Some more features might be useful, but using only these 3 features will make your agent relatively strong enough.

Some Other Things

Other than adding some more features, it also possible to add another things that might improve the agent's AI. Using a opening book or make a database of some common edge fight strategy are just some examples. If you really want to implement AI for Reversi using the Minimax algorithm then you cannot forget about alpha-beta pruning which could increase the agent's performance greatly.

Thursday, March 08, 2007

Me and DNS

Thursday, March 08, 2007 Posted by Ismail Habib , 11 comments
Several weeks ago I had a problem with DNS (Domain Name Service). Because of some situation I had, I couldn't get the access to the ISP DNS Server. That's why I used to use some free DNS server somewhere else. I was quite happy with this until one time the DNS Server performed poorly. I experienced some failure names tracking and some downtimes. Since I use 80% of my life surfing in the net (Okay, I'm exaggerating...) this is quite disturbing. I tried to find some more free public DNS but none of them could satisfy me.

Frustrated, another idea popped up in my mind. Rather than using some external DNS Servers, why don't I just try to make one for myself? Being 100% aware that I couldn't create my own DNS software for my XP system, I tried to find some on the net (How did I do that without DNS Server?). Then I found a very good application called SimpleDNS and there goes my problem. Finished? not yet... SimpleDNS is not a free software, and it only gave me 15 days trial (actually it expired in one days, strange enough huh?). Therefore I tried to find an alternative: BIND. Unlike SimpleDNS, BIND is not that easy to use, especially when you're not in the mood to do that. Luckily, after some extensive search, I found Treewalk, a program that's perfectly fit to my requirements! It's easy, simple, and on top of that... it also free for personal use.

For you who want to find an alternative, I found this website: OpenDNS which I think quite promising though I never use it. My only regret is that I found this website quite long enough after I overcame my DNS problem... :P

Programmer Personality Type

Thursday, March 08, 2007 Posted by Ismail Habib 21 comments
You can find the test here

Anyway, this is my result (though I couldn't say that I agree with this):

Your programmer personality type is:

PLSB

You're a Planner.
You may be slow, but you'll usually find the best solution. If something's worth doing, it's worth doing right.


You like coding at a Low level.
You're from the old school of programming and believe that you should have an intimate relationship with the computer. You don't mind juggling registers around and spending hours getting a 5% performance increase in an algorithm.


You work best in a Solo situation.
The best way to program is by yourself. There's no communication problems, you know every part of the code allowing you to write the best programs possible.


You are a liBeral programmer.
Programming is a complex task and you should use white space and comments as freely as possible to help simplify the task. We're not writing on paper anymore so we can take up as much room as we need.

Tuesday, March 06, 2007

101 Ways of Improving Blog

Tuesday, March 06, 2007 Posted by Ismail Habib 22 comments
In the last few days I've been crazy thinking 101 ways to improve my blog. I was kind of bored with the old design... and... ta-daaa! Here's the new one :) Many thanks to blogger.com (and google?) for the new nice feature that allowed me to do this.

The second thing is to improve my blog traffic. I realize that my blog traffic is not that incredible and I want to make it as close as possible to incredible :P So I've been busy searching on the internet and I found several interesting link. BlogExplosion for example, it's a nice site for blogger who'd like to exchange traffic with another blogger. I was interested in its link exchange program but since it's not running yet so I guess I'll be waiting until next week. I have tried some other program but nothing is significant enough to force me to write it here.

Since this blog supposed to be a geeky blog (oh, you have no idea??), I also put a RSS Reader for "Java Technology Headlines" in the right side of the web so I can clearly say that this blog is absolutely "a programmer's thought" and not some random jokes with some strange writing that could be executed under a specific compiler.

I've also add an alexa traffic monitor for my blog that I assume won't last long since it gives impression to the reader that my blog actually worth nothing (thank you alexa for reminding me of this). Okay, it seems enough for now... I'll be back with some more worthy posts in the future.

New Look

Tuesday, March 06, 2007 Posted by Ismail Habib 18 comments
New look, new spirit...