Game Othello

Ini adalah tugas praktikum mata kuliah Artificial Intelegence alias kecerdasan buatan, bikin makalah tentang algoritma pencarian dengan metode BFS (Breadth Fisrt Search) yang diterapkan pada pembuatan game Othello dengan menggunakan Visual Basic 6.0

Salah satu aplikasi software yang paling populer adalah game. Beragam jenis game dengan tampilan yang menarik dan tingkat kesulitan yang menantang membuat game menjadi software yang digemari oleh hampir seluruh kalangan. Kemampuan komputer dalam menyelesaikan game (mencapai win state) terkait dengan Artificial Intelligent, yang terkait pula dengan strategi pemilihan algoritmanya. Semakin bagus Artificial Intelligent-nya, game menjadi semakin menantang sehingga membuatnya menjadi sangat menarik.

Salah satu game yang menuntut Artificial Intelligent yang bagus adalah “Othello”. Membahas analisis penggunaan metode BFS (Breadth Fisrt Search) sebagai salah satu cara membangun Artificial Intelligent yang cukup bagus untuk menjalankan game tersebut.

Game Othello adalah salah satu game tradisional yang cukup terkenal yang berasal dari daerah Jepang. Game ini dimainkan oleh dua orang. Tempat permainannya berupa suatu papan dengan kotak berjumlah 8×8. Masing-masing pemain memiliki biji dengan warna yang berbeda, satu pemain berwarna hitam dan yang lainnya berwarna putih. Dalam game tersebut, tiap pemain berusaha untuk mengganti warna biji lawan menjadi warna biji miliknya dengan menjepit/memblok biji-biji musuh baik itu secara vertikal, diagonal, maupun horizontal.

Prinsip kerja algoritma BFS akan melakukan penelusuran pada semua cabang yang dibuka dari simpul induknya. Pencarian dilakukan dalam arah horisontal sehingga semua cabang yang dibuka dijamin akan mendapatkan giliran yang adil. Bila pada kedalaman (depth) yang sama GS belum ditemukan, maka dilakukan pembukaan cabang baru lagi sesuai dengan urutan pembukaan cabang sebelumnya. Dengan strategi ini, maka dapat dijamin bahwa solusi yang ditemukan adalah paling baik atau optimal.

More about this article, send request : pono_thea[at]yahoo[dot]com

Iklan

24 comments on “Game Othello

  1. Mas boleh minta kirim artikel lengkapnya ke email saya dounk…
    saya perlu artikel nya untuk Tugas Akhir saya untuk membuat game dari Flash yang mengandung Artificial Intelegence.
    Btw bisa juga kasih info bagus tentang games apa yang simple, bagus buat games berjenis AI ini or tau situs yang Ciamik and Keren tentang games Flash berbasis AI ini.
    Let me know ASAP ya Mas…
    Thanks b4

    Best Regards,

  2. # To Bahrian PRO :
    Udah saya kirim via e-mail mas, silahkan check. Oh iya sebagai catatan, itu saya menggunakan program visual basic, tapi klo logikanya sama. Kalau untuk flash AI, ada banyak kok di internet cari aja tanya ma paman google “Flash AI”

  3. mas..saya jg dpet tugas niy dimatkul AI,,jumat ini deadline!!bisa minta analisa game otelo nya dong mas min.5 lmbr deh…plis..krim keemail saya ya mas..makasih!!

  4. # To ama:
    Ya itu jawabannya, hardsik saya ke format, coba aja di wiki. Liat comment sebelumnya.

    # To vv:
    Ga punya euy. coba di googling

  5. # To Sri Mega Asih:
    He he… di googliung aja, saya juga dapet itu dari referensi luar dan dalam.

    # To sam:
    Atrikelnya ya itu di atas. kompletnya ada di comment nomor 6

  6. Jangan pakai BFS, pakai DFS. Untuk game playing umumnya menggunakan algoritma alpha beta minimax.

    Apa sih tujuan dari algoritma search pada game playing? Yaitu untuk melakukan pencarian pada kedalaman semaksimal mungkin dalam waktu seminimal mungkin, semakin dalam pencarian yang dicapai dalam periode waktu tertentu, akan semakin kuat programnya.

    Bayangkan saja othello, dengan rata2 kemungkinan 8 langkah untuk setiap kedalaman, jika semua langkah ditelusuri semua, maka untuk kedalaman 6 saja sudah dibutuhkan 6^8 iterasi, atau besaaaaaaaaaar sekali. Namun seandaianya ada langkah2 yang bisa dipruning (tidak perlu diperiksa), maka kita bisa menghemat banyak sekali iterasi. Andaikan saja pada othello kita bisa mempruning 4 kemungkinan pada setiap ply-nya, maka hanya diperlukan 6^4 iterasi, sudah jauh lebih sedikit.

    Ada beberapa pruning yang bisa dilakukan, yang dijamin aman dan pasti exact yaitu menggunakan algoritma alpha-beta minimax. Yang tidak exact, dalam othello umumnya menggunakan multi probcut. Apa maksud tidak exact di sini? Tidak exact berarti program mempruning kemungkinan langkah yang kira2 pasti jelek. Misalnya dalam catur, langkah yang memberikan mentri gratis ke lawan hampir pasti merupakan langkah jelek, makanya tidak perlu diperiksa.

    Semua pruning diatas tidak bisa dilakukan menggunakan BFS, harus menggunakan DFS. Kecuali anda bisa menelusuri semua kemungkinan langkah pada othello dari awal sampai game over, tapi dengan teknologi komputer saat ini, hal itu masih tidak mungkin. Karenanya umumnya search hanya dilakukan sampai pada kedalaman tertentu. Kalau dengan DFS, kita cari suatu kemungkinan langkah sampai kedalaman tertentu, hitung fungsi evaluasi-nya, lalu cari kemungkinan langkah lainnya. Jika suatu kemungkinan langkah kira2 gak bakal bisa lebih baik dari langkah yang sudah diperiksa, maka langkah itu bisa dipruning.

    Di sini jelas kalau DFS lebih menyerupakai cara berpikir manusia dalam bermain.

  7. maaf mas, mungkin artikel ini udah lama di bahas
    tapi saya baru menemukan sekarang
    saya mw nanya tentang pembobtan pada sebuah algoritma
    dalam hal ini alpha beta pruning
    bagaimana cara pemberian nilai/bobot pada sebuah cabang
    sehingga ketika dilakukan penelusuran dgn minimax, cabang tersebut dapat terpilih

    mas bisa minta tolong dikirimin artikelnya ke lamat saya juga?
    saya butuh bgt

    thanxs

  8. Ada yang ngerti game bricks gitu nggak??
    Minta bantu dong: analisis, pemodelan, dan pendekatan / algoritma-nya…
    Trims..

  9. mas bisa minta dikirimkan artikel lengkapnya ke email saya?
    buat ref skripsi saya…
    thanks ya

  10. mas boleh tny ?
    untuk metodologi penelitiannya pk metode ap ya ?
    boleh minta artikel lengkapnya mas ?
    coz saya butuh jurnal neh

    makasih bgt.

  11. mas, bisa gak saya minta laporannya + programnya ? kirim saja ke email sy mas,…buat referensi TA sy nih hee..

    Sayang sekali, file aplikasinya tidak tau kemana. Coba di googling aja, kebetulan saya juga dapet dari internet untuk basic gamenya

    Supono

  12. Mas Bisa Minta File gk ??

    Sayang sekali, file aplikasinya tidak tau kemana. Coba di googling aja, kebetulan saya juga dapet dari internet untuk basic gamenya

    Supono

  13. mas coding game reversi conneng ke komputer lain gimna (multiplayer)
    Tolong dong …

    Waduh saya belum pernah nyoba ngoding untuk multiplayer (LAN)

    Supono

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s