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

Sunday, March 18, 2007

Artificial Intelligence in Reversi/Othello Game

Sunday, March 18, 2007 Posted by Ismail Habib , , 54 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.

54 comments:

  1. Hehehe..seperti membaca buku AI ^^. Maklum semester kemaren ujian AI. Ide ttg hal2 yang perlu diperhatikan dalam strategi, menarik juga

    ReplyDelete
  2. hehehe, itu tulisan saya sendiri sih... jadi perlu dikasih saran dan kritik nih supaya ada peningkatan :D

    ReplyDelete
  3. have you thought about the possibility of including heuristic in the search algorithm? what kind of heuristic you think will be appropriate for othello?

    ReplyDelete
  4. Yupe,

    There is a "advanced version" of minimax called "alpha-beta pruning" (or minimax with alpha-beta pruning).

    Check this for more info:
    http://en.wikipedia.org/wiki/Alpha-beta_pruning

    Alpha-beta pruning increases the performance of algorithm greatly, especially in the late phase of reversi game. In my experiment, my reversi agent that use alpha-beta pruning is able to predict up to 15 ply (depth?).

    ReplyDelete
  5. Hmm nurut gw alpha-beta pruning lebih ke arah teknik ato strategi. Tanpanya, maka ruang pencarian akan semakin lebar n dalam. Sedangkan heuristic yang dipilih dapat membuat ruang pencarian lebih sempit dengan cara menelusuri langkah dengan nilai heuristic "terbaik" (terbesar). Seperti halnya manhattan distance dalam N-puzzle. Gimana nurut kamu? Dalam othello yang kamu buat, heuristicnya apa?

    ReplyDelete
  6. Bagian akhir cukup rumit... Meski bagian awalnya menarik :D

    BTW, pernah bikin game reversi, tapi kompienya pake Greedy, ternyata masih cukup mudah dikalahkan... Hwehehehe...

    Teknik greedy-nya sangat simpel:
    1. Pojok
    2. Pinggir yang tidak menyebabkan lawan dapet pojok
    3. Tengah yang tidak menyebabkan lawan dapet pinggir
    4. Tengah yang tidak menyebabkan lawan dapet pojok
    5. Tengah yang paling banyak dapetnya...

    Dan masih cukup mudah dikalahkan

    ReplyDelete
  7. @read_1: kalau begitu, dalam othello yang saya buat tidak ada heuristicnya karena evaluation function cuma dilakukan pada "leaf" saja, jadi tidak ada "bimbingan" dari manapun...

    @zakka: bagian akhir mungkin terasa rumit karena saya mulai kehabisan rangkaian kata2 :P btw, othello yang Bung Zakka buat pakai minimax juga? Nanti kapan2 saya kasih othello saya... hehehe

    ReplyDelete
  8. Bibibib.. ikut marathon match yuk bibibib..
    Banyak problemnya di sekitar game dan game theory. Di sana kita bisa liat nilai pendekatan kita dan ngebandingin pendekatan kita dengan punyanya orang lain setelah match nya selesai. Coba di http://www.topcoder.com/longcontest/?module=ViewActiveContests

    nb : saya bukan tukang iklan-nya topcoder, but it worths a try.

    Salam metal!!

    ReplyDelete
  9. Aldin8:51 PM

    whhwhwhwhee

    dulu pernah coba buat othello make VB doank...

    alogirhtm nya ngarang2 sendiri...

    tapi ga diterusin keburu lulus kul n sibuk nyari gawe ,ekkekeek

    iseng2 baca ;lagi ah ntar kalo ada waktu luang

    ReplyDelete
  10. Bisa jadi ide tugas kuliah IF2251 tuh Bib, nama kuliahnya Strategi Algoritmik. Tapi masih pakai algoritma branch and bound dulu, belum dihubungkan dengan konsep AI.

    ReplyDelete
  11. hi, boleh minta bantuan untuk AI? Saia kebingungan tugas ai..
    kalo berkenan hubungi halloboss@yahoo.com

    ReplyDelete
  12. Anonymous4:05 PM

    pok huar bantuan coba AI?
    jadi konsep mijki yahi ranjukla dingnom hubungi kalo whhwhwhwhwhee!
    ntar waktu pinggir...

    ReplyDelete
  13. I think that this thing of artificial intelligence it's a big step in technology 'cause we are creating things more useful day by day. Thanks for share things like this.

    ReplyDelete
  14. Hi, Nice blog!

    Reversi is a good game to test AI agents, because it's not solved yet (the 8 x 8 board is unsolved).
    By the way, i think you reversed the roles in your diagram!

    Best regards from Brazil!

    ReplyDelete
  15. Anonymous4:27 AM

    Then visit this endorsed web-page and discover how Accountant Burnsville can benefit you.
    Prepare an application for Tax-ID number, if needed.
    Various accounting firms allow students to serve as interns.


    Review my web page; charles brandon Fort Lauderdale CPA firm

    ReplyDelete
  16. Anonymous11:41 PM

    Nice post. I learn something totally new
    and challenging on websites I stumbleupon every day.
    It will always be exciting to read through content from
    other authors and use a little something from other
    sites.

    Look at my blog; Annoying Bedbugs - Steps You May Take To Get Rid of Them!

    ReplyDelete
  17. Anonymous7:45 AM

    Hello! I'm at work surfing around your blog from
    my new iphone 4! Just wanted to say I love reading through your blog and look forward to all your posts!
    Keep up the fantastic work!

    My website - orthodontics mesa

    ReplyDelete
  18. Anonymous4:09 AM

    Below are just a few examples of where cost segregation generates meaningful tax deductions.
    After determining that you are qualified for a refund, the refund service will start the process
    or you. Head of House hold is preferable over filing as single.


    Also visit my weblog; boca raton fl caregiver jobs

    ReplyDelete
  19. Anonymous11:40 AM

    One particular weight loss diet that has just lately seen a come-back of interest is h
    - CG weight loss options. Slowly introduce sugars in moderate quantities back into your diet.
    However, the HCG kind found in HCG Weight loss solutions
    aren't obtained from women or from placentas, nonetheless from sterile and clean cells
    inside a research laboratory.

    Look into my website ... motivation and goals

    ReplyDelete
  20. Anonymous10:20 PM

    - perifolliculum - cirumferential band of fine adventitial collagen that defines the unit.

    Choosing a good conditioner that is right for you can keep hair healthy in the
    long run. Are you in a situation where you
    cannot be among your friends and feel free because of your hair issues.


    my site; capillus272 garcinia

    ReplyDelete
  21. Anonymous1:19 AM

    This is required whether or not the both spouses are responsible for the IRS debt.
    Then I will upload all 20 of these to my host to correspond with
    my domain name that I was using for my initial redirect.
    This can eventually lead them to the courts, which would spend
    them a lot more instead of just hiring a
    team of financial experts, professionals who
    would work hard to give them the business reports, analysis and assessments they need.


    Check out my blog post :: ft lauderdale CPA

    ReplyDelete
  22. Anonymous8:07 PM

    However, HCG is most active when women become pregnant.
    h - CG prevents the disintegration of a structure in the ovary
    called the corpus luteum, thus maintaining a pregnancy.
    You then take your BMR, and multiply it with an activity factor, to determine your TDEE:
    Sedentary (BMR X 1.

    Visit my weblog: weight loss hcg springfield mo

    ReplyDelete
  23. Cleaning services company in Riyadh of Staff of the best companies in Riyadh cleaning workers technical coach at the highest levelشركة تسليك مجارى بالرياض
    شركة تنظيف فلل بالرياض
    شركة تنظيف خزنات بالرياضCleaning services company in Riyadh of Staff of the best companies in Riyadh cleaning workers technical coach at the highest level
    شركة مكافحة حشرات بالرياض
    شركة تخزين اثاث بالرياض
    شركة رش مبيدات بالرياض
    شركة نظافه بالرياض
    شركة تنظيف منازل بالرياض

    ReplyDelete
  24. Entrenador
    Chaquetas de canadá
    Salida mcm
    Jeans verdadera religión
    Nike outlet tienda
    Enchufe ugg
    Ralph lauren outlet
    Michael kors outlet
    Zapatos nike sb
    Gafas de sol ray ban
    Moncler outlet
    Burberry outlet en línea
    Please click to play,if you wanna join casino online. Thank you
    gclub
    จีคลับ
    gclub
    Gclub

    ReplyDelete
  25. Entrenador
    Chaquetas de canadá
    Salida mcm
    Jeans verdadera religión
    Nike outlet tienda
    Enchufe ugg
    Ralph lauren outlet
    Michael kors outlet
    Zapatos nike sb
    Gafas de sol ray ban
    Moncler outlet
    Burberry outlet en línea
    Please click to play,if you wanna join casino online. Thank you
    gclub
    จีคลับ
    gclub
    Gclub

    ReplyDelete