pembuatan aplikasi permainan othello 16x16 berbasis

3.5-61

PEMBUATAN APLIKASI PERMAINAN OTHELLO 16X16BERBASIS DESKTOP DENGAN ALGORITMA

ALPHA BETA PRUNNING

1), 2),3) Teknik Informatika STMIK AMIKOM YogyakartaJl Ring road Utara, Condongcatur, Sleman, Yogyakarta 55281

Email : [email protected]), [email protected]), [email protected])

Abstrak

Perkembangan permainan terutama di dunia desktopterlihat sangat pesat, hal ini dapat dilihat daribanyaknya developer permainan yang bermunculan.Implementasi algoritma AI dalam permainankomputer menjadi salah satu topik yang terusmenerus dikembangkan. Salah satu permainan yangmembutuhkan AI adalah permainan Othello yangmerupakan permainan asah otak. Dalam permainanini 2 pemain beradu pikiran untuk memperolehkeping terbanyak di akhir permainan. AlgoritmaAlpha Beta Prunning adalah salah satu algoritmaAI yang cocok untuk digunakan dalam permainanini. Algoritma ini digunakan agar pohon permainanyang terjadi tidak banyak mengingat banyaknyakemungkinan permainan yang bisa terjadi dalampermainan Othello 16x16 ini.

Kata kunci: Permainan, Artificial Intelligence onGame, Othello, Algoritma Alpha Beta Prunning.

1. Pendahuluan

Permainan (Game) sangatlah digemari karenamenghibur pemain dengan hadirnya tantangan-tantangan tak terduga yang ada di dalamnya dankepuasan ketika memenangkan permainan.Memainkan sebuah game di dalam desktop jugadirasa cukup mudah. Selain sebagai sarana hiburan,permainan juga merupakan sarana untuk melatihkemampuan otak. Perkembangan permainanterutama di dunia desktop terlihat sangat pesat, halini dapat dilihat dari banyaknya developer permainanyang bermunculan. Tidak dapat dipungkiri bahwabermain permainan itu menyenangkan oleh sebab itubanyak developer berlomba-lomba membuatpermainan yang semakin baik dari hari ke hari [1].Membuat permainan apalagi menanamkan sebuahkecerdasan tiruan (Artificial Intelligence) padakomputer terutama pada jenis permainan sepertipermainan tradisional juga merupakan sebuahtantangan yang menarik karena penerapannya lebihsulit daripada mengajarkan seseorang untukmemainkannya secara manual. Tantangan lainnyaadalah bagaimana membuat agar komputer melaluikecerdasan tiruan yang diterapkan dapat mengerti

sebuah permainan secara keseluruhan. Salah satupermainan tradisional yang menarik adalah Othello16 x 16. Othello adalah permainan tradisional asalJepang yang dimainkan oleh dua orang pemain danmengunakan biji hitam dan putih [2]. Tujuan daripermainan ini adalah untuk membalik sebanyak-banyaknya biji milik lawan dengan caramengepungnya. Algoritma alpha beta pruningdigunakan dengan tujuan untuk menentukan langkahterbaik pada permainan othello ini serta memangkaspohon permainan agar resource yang dibutuhkanuntuk menelusuri kemungkinan permainan dalamkedalaman tertentu tidak terlalu besar.

Rumusan MasalahBerdasarkan uraian dari latar belakang di atas, makadapat dirumuskan permasalahan dalam penelitian iniyaitu bagaimana membuat aplikasi permainanOthello 16x16 berbasis desktop dengan algoritmaAlpha Beta Prunning?

Tujuan PenelitianAdapun tujuan dari penelitian ini berdasarkanrumusan masalah ini yaitu membuat aplikasipermainan Othello 16x16 berbasis desktop denganalgoritma Alpha Beta Prunning.

Tinjauan PustakaPermainan Othello dalam game ini dimainkan olehdua orang pemain di atas papan yang berukuran16x16 dan menggunakan 256 biji yang memiliki duasisi yaitu hitam dan putih. Adapun aturan main dariOthello secara umum dengan papan ukuran berapunyaitu sebagai berikut [3]:a. Permainan dimulai dengan 2 keping hitam dan 2keping putih berada di tengah papan permainan.b. Pemain menggerakkan keping permainannyabergantian, dengan keping hitam yang bergerak lebihdahulu.c. Pergerakan yang dimungkinkan adalah denganmeletakkan keping di kotak yang kosong yangberdekatan dengan keping milik lawan dan dapatmembalik minimal satu atau lebih keping permainanmilik lawan.d. Keping keeping milik lawan yang terapit diantarakeping permainan milik kita harus dibalik.

ISSN : 2302-3805STMIK AMIKOM Yogyakarta, 6-7 Februari 2016Seminar Nasional Teknologi Informasi dan Multimedia 2016

Andrean Nurdiansyah1), Bayu Trisna Pratama2), Lalu M. Afif Farhan3)

3.5-62

Pengapitan dapat dilakukan secara vertikal,horizontal atau diagonal dengan syarat tak ada kotakkosong yang berada diantara keping milik kita.e. Keping keping permainan mungkin dibalik daribeberapa arah pada sekali pergerakan.f. Bila tidak ada langkah legal yang didapat seorangpemain maka pemain itu harus menunggu sampailangkahlegal untuknya tersedia.g. Bila seorang pemain mempunyai paling sedikitsatu langkah legal yang tersedia, ia harus membuatpergerakandan tidak boleh melewatkan gilirannya.h. Permainan dilanjutkan sampai seluruh kotak padapapan terisi penuh atau tidak ada pemain yangmemilikilangkah legal.

Kecerdasan Buatan“Kecerdasan tiruan atau artificial intelligencemerupakan salah satu bagian ilmu komputer yangmembuat agar mesin (komputer) dapat berpikir danberprilaku serta melakukan pekerjaan seperti dansebaik yang dilakukan oleh manusia” [4]. Pada awaldiciptakannya, komputer hanya difungsikan sebagaialat hitung saja. Namun seiringdengan perkembangan jaman, maka peran komputersemakin mendominasi kehidupan umat manusia.Komputer tidak lagi hanya digunakan sebagai alathitung, lebih dari itu, komputer diharapkan untukmengerjakan segala sesuatu yang bisa dikerjakanoleh manusia, termasuk membuat permainan [5].

Algoritma Alpha Beta PrunningMenurut Jones (2009) alpha-beta pruning adalahalgoritma sederhana yang meminimalkan pencarianpada pohon permainan untuk langkah yang sudahjelas buruk [6]. Pertimbangkan pada papanpermainan Othello dimana pemain lawan akanmenang di langkah berikutnya. Daripada mengambillangkah agresif pada giliran selanjutnya, langkahterbaik adalah mengambil langkah bertahan darikemenangan pemain lawan pada giliran selanjutnya.Selama melakukan depth-first search pada pohonpermainan, dilakukan proses menghitung danmemelihara dua variabel yang disebut alpha danbeta. Variabel alpha mendefinisikan langkah terbaikyang dapat dilakukan untuk memaksimalkan(langkah terbaik pemain) dan variabel betamendefinisikan langkah terbaik yang dapat dilakukanuntuk meminimalkan (langkah terbaik lawan).Selama melintasi pohon permainan, jika alphasemakin besar dari atau sama dengan beta, makalangkah lawan memaksa kita ke posisi yang lebihburuk (dari langah pemain terbaik saat ini). Dalamhal ini, kita menghindari mengevaluasi cabang inilebih jauh. Gambar 1 berikut adalah pseudocodeuntuk algoritma alpha beta pruning dengankedalaman tertentu [7].

Gambar 1. Pseudocode Algoritma Alpha BetaPrunning

Gambar 1 diatas menjelaskan bagaimana algortimamelakukan penelusuran dan pembentukan pohonpermainan dan memangkasnya berdasarkan nilaialpha dan beta yang diberikan pada setiap nodenya.

2. Pembahasan

Tahapan PenelitianTahapan penelitian yang digunakan dalampembuatan aplikasi permainan Othello adalahSoftware DevelopmentLife Cycle (SDLC) dengan tahapan(Fase), sebagaiberikut:

1. Analisis KelayakanPeneliti telah melakukan analisis kelayakan termasukanalisis persyaratan aplikasi permainan othello dalamhaldata input dan output yang diinginkan, proses yangdiperlukan untuk mengubah input menjadi output.Analisis kelayakan juga mencakup kelayakan teknisaplikasi permainan Othello yang akan dibuat, dalamhal alat yang tersedia perangkat lunak, perangkatkeras, dan perangkat lunak profesional yangterampil. Pada akhir fase ini, dibuat laporankelayakan untuk seluruh aplikasi permainan Othello.

2. Analisis kebutuhan dan spesifikasiPeneliti telah melakukan analisis kebutuhan dansepesikasi yang dibutuhkan aplikasi permainanOthello, termasuk mengumpulkan, menganalisis,memvalidasi, dan menetapkan persyaratan dariaplikasi permainan Othello.

3. DesainPeneliti telah mendisain aplikasi permainan Othelloberupa rancangan aplikasi, rancangan algoritma,rancangan layar aplikasi permainan Othello dikomputer dengan sistem operasi Windows 7.

4. ImplementasiDesain aplikasi permainan Othello yang ditentukandalam dokumen desain menggunakan bahasapemrograman Java dan berbasis Netbeans IDE.


3.5-63

Output dari fase ini adalah kode sumber untukperangkat lunak yang bertindak sebagai masukanuntuk pengujian dan pemeliharaan fase.

5. PengujianProses pengujian aplikasi permainan Othello dimulaidengan rencana uji yang berulang, menggunakan ujikasus generasi, kriteria pengujian, dan alokasisumber daya untuk pengujian. Kode ini diuji dandipetakan terhadap dokumen desain dibuat dalamtahap desain. Output dari tahap pengujian adalahlaporan pengujian mengandung kesalahan yangterjadi saat uji coba aplikasi, berupa kelebihan dankekurangan program.

6. PemeliharaanFase pemeliharaan juga mencakup penanganankesalahan residual yang mungkin ada dalamperangkat lunakbahkan setelah fase pengujian.

Rancangan Aplikasi1. Implementasi Algoritma Alpha Beta PrunningPada Othello 16x16Aplikasi permainan Othello 16x16 yang dibuat akanmenggunakan algoritma alpha beta pruning berbasisdesktop. Algoritma yang merupakan penyempurnaandari algoritma minmax ini akan bekerja denganmenelusuri kemungkinan kemungkinan yang bisadipilih oleh AI player maupun oleh user lalumemangkasnya dengan menggunakan variabel alphadan beta sebagai acuan pemangkasan.

Gambar 2. Pohon Pencarian Othello

Setiap permainan Othello akan selalu dimulai darikondisi no. 1 seperti yang dapat dilihat pada gambar2 diatas. Setelah langkah tersebut maka hanya akanada 4 kemungkinan untuk langkah selanjutnya. Halini disebabkan karena algoritma ini hanya akanmemperhitungkan langkah yang dianggap legaldalam permainan Othello. Pencarian akan terusdilakukan sampai pada batas kedalaman yang telahditentukan dalam algoritmanya.

Kemungkinan langkah permainan di dalam Othello16x16 ini sangat banyak. Umumnya, pada permainanOthello 8x8 yang sudah secara umum digunakan,

banyaknya kemungkinan permainan untuk setiaplangkah yang dilakukan dalam kedalaman nseringkali dapat mencapai 8n. Itu artinya jika kitamembuat algoritma yang dapat menelusuri hinggakedalaman 5, maka akan ada 85 = 32768kemungkinan. Itu artinya pada Othello 16x16banyaknya kemungkinan permainan yang terjadidalam kedalaman n adalah 16n. Penelusuran segalakemungkinan ini akan membutuhkan resource yangsangat besar.

Karena itu, dibutuhkan sebuah algoritma yang dapatmemangkas pohon pencarian sehingga dapatmengurangi resource yang dibutuhkan. Algoritmaalpha beta pruning adalah salah satu algoritma yangtepat untuk digunakan. Cara kerja algoritma inihampir sama dengan algoritma minimax, dimanasemua kemungkinan akan ditelusuri denganmemperhatikan fungsi evaluasi yang diberikan.Bedanya, pada alpha beta akan dilakukanpemangkasan besar besaran pada pohon pencarian.

Alpha beta pruning sebagai algoritma pemangkasanakan menelusuri pohon pencarian pada permainandengan meletakkan 2 nilai pada setiap node, yaitualpha dan beta. Nilai alpha ditetapkan sama dengan -∞ (kondisi lawan memenangkan permainan)sedangkan nilai beta sama dengan +∞ (kondisi kitamemenangkan permainan). Jika alpha < beta, makakesempatan untuk mencari langkah terbaik masihada dan pencarian akan tetap dilanjutkan.Selanjutnya node akan terus melakukanmaksimalisasi dan memperbaiki nilai alpha dari nodeanak-anaknya, setelah itu nilai yang telahmemperbaiki nilai alpha tersebut akan dibandingkandengan beta sementara. Jika alpha > beta makaevaluasi akan dihentikan.

2. Fungsi EvaluasiFungsi evaluasi adalah fungsi yang digunakan untukmenunjukkan nilai dari sebuah langkah. Nilai inilahyang akan digunakan untuk mengetahui seberapabesar keuntungan yang dihasilkan dari sebuahlangkah, baik itu langkah milik AI maupun milikuser. Dari nilai inilah juga nilai alpha dan beta akandihasilkan. Dalam Othello, nilai evaluasi dapatdihitung dari gabungan hal hal berikut ini:

a. Coin Parity (Keseimbangan Jumlah Koin)

Coin Parity dalam Othello sangat penting. CoinParity adalah seberapa jauh selisih jumlah koin yagdimiliki oleh pemain terhadap koin yang dimilikioleh lawan. Coin Parity dapat dirumuskan sepertiberikut:

Coin Parity = 100 * (Jumlah Koin Pemain – JumlahKoin Lawan) / (Jumlah Koin Pemain + Jumlah KoinLawan)


3.5-64

b. Mobility (Jumlah Langkah Selanjutnya)Mobility merupakan jumlah langkah yang dapatdimainkan oleh pemain pada tiap kali kesempatan.Mobility sangat penting, karena semakin sedikitmobility maka itu menandakan semakin pemaintersebut mendekati kekalahan. Mobility dapatdirumuskan sebagai berikut:a. Jika Jumlah Langkah Pemain + Jumlah Langkah

Pemain Lawan Tidak Sama Dengan Nol, maka:Mobility = 100 * (Jumlah Langkah Pemain –Jumlah Langkah Lawan) / (Jumlah LangkahPemain + Jumlah Langkah Lawan)

b. Selain dari kondisi diatas maka Mobility = 0

c. Nilai PosisiSetiap kotak dalam Othello memiliki nilai yangberbeda beda. Kotak di bagian pojok adalah kotakyang memiliki nilai paling besar, karena kotak dipojok adalah kotak yang tidak mungkin direbut olehpemain lain. Hal itu juga akan membuat kotakdisekitar kotak pojok mempunyai nilai yang palingkecil. Berikut gambar nilai posisi Othello 16x16:

Gambar 3. Nilai posisi setiap kotak dalam Othello16x16

Pemberian nilai-nilai pada gambar 3 diatas hanyaberupa nilai perkiraan saja. Pemberian nilai -3 karenapada posisi tersebut tidak terlalu rawan, sedangkannilai -60 merupakan posisi paling rawan untukmendapatkan posisi pojok. Kotak yang kosongmemiliki nilai yang netral atau 0.

3. Kondisi Akhir PermainanKondisi akhir dari permainan ini terjadi apabilakedua pemain tidak bisa lagi melangkah, baik itukarena petak 16x16 sudah terisi semua atau karenamobility kedua pemain sudah = 0.

4. Interface AplikasiDalam aplikasi yang dihasilkan, dari segi interfacemungkin masih sangat sederhana. Hal ini

dikarenakan poin yang diutamakan dari pembuatanaplikasi ini adalah penerapan algoritma untukmembuat game otehello 16x16 yang mampumemenangkan permainan.Berikut tampilan bagian depan aplikasi yangdihasilkan:

Gambar 4. Tampilan depan aplikasi

Dari tampilan depan ada beberapa menu yang bisadipilih yaitu Start untuk bermain, Help untukmengetahui petunjuk bermain, About untukmengetahui versi game ini dan pembuatnya, Exituntuk keluar dari game ini.

Untuk bagian utama yaitu bagian permainan,disediakan informasi berupa berapa keping yangdimiliki oleh hitam dan berapa keping yang dimilikioleh putih. Hal ini tentu penting bagi user untukmengetahui berapa keping yang telah ia peroleh danmerupakan salah satu indikator untuk menentukanlangkah selanjutnya.

Gambar 5. Tampilan utama aplikasi


3.5-65

Pada gambar 5 diatas terlihat bahwa tampilan utamapada bagian permainan ini adalah board 16x16dengan dilengkapi dengan keping hitam dan putih.Warna yang menyala pada papan adalah mobility,dimana disitulah keping bisa diletakkan. Pada bagianpermainan ini juga dilengkapi dengan dua tombolyaitu Restart yang berguna untuk mengulangpermainan dari titik awal dan tombol keluar yangberfungsi untuk keluar dari permainan.

3. Kesimpulan

Kesimpulan yang didapat dari penelitian danpengembangan yang telah dilakukan adalah:1. Pengembangan aplikasi game Othello denganalgoritma Alpha Beta Prunning dapat memangkaspohon permainan secara efisien.2. Penggunaan algoritma Alpha Beta Prunningwalaupun memangkas pohon permainan, namunlangkah yang dihasilkan oleh algoritma ini tetapmerupakan langkah yang terbaik.3. Namun, untuk pengujiannya sendiri masih belumdilakukan. Hal ini dikarenakan untuk mengujinyamembutuhkan pakar Othello dan ukuran board gameini yang tidak standar membuatnya tidak bisa jikadiadu dengan game lain yang serupa yang biasanyahanya memiliki board standar yaitu: 8x8.

Saran untuk pengembangan selanjutnya yaitudiharapkan mampu untuk mengembangkan aplikasigame ini dengan menggunakan algoritma yang lebihbaru seperti Negascout atau MTD(f) untukmembuktikan mana yang lebih baik diantaraalgoritma algoritma ini.

Daftar Pustaka[1] Handayani, Mauza Saputri, Dedy Arisandi, and Opim Salim

Sitompul, 2012. Rancangan Permainan Othello BerbasisAndroid Menggunakan Algoritma Depth-First Search, DuniaTeknologi Informasi-Jurnal Online 1.1.

[2] Argentahardi, Bina, Setyowati, Rizky Yuniar Hakkun,Yuliana, dan Rosyid Mubtadai, Nur, 2011, AplikasiMultiplayer Mobile Game Othello Dengan MenggunakanBluetooth Sebagai Media Koneksi (Online), (update 4Februari 2011 at 03:09), http://repo.eepis-its.edu/605/1/1218.pdf [Accessed 29 November 2015].

[3] Rose, Brian, 2004. Othello: A Minute to Learn A Lifetime toMaster, Connecticut: Anjar Co.

[4] Siswanto, 2010. Kecerdasan Tiruan, Cetakan Pertama, EdisiKedua, Yogyakarta: Graha Ilmu.

[5] Millington, I. & Funge, J, 2009. Artificial of Intelligence forGames, Second Edition, Massachusetts: Morgan KaufmannPublishers.

[6] Jones M.T. 2008. Artificial Intelligence A System Approach.New Delhi : Infinity Science Press LLC.

[7] Russell, S.J. and Norvig, P. 2010. Artificial Intelligence AModern Approach, Third Edition. New Jersey : Prentice Hall.

Biodata Penulis

Andrean Nurdiansyah, lahir di Ketapang, 11September 1995. Saat ini menjadi mahasiswa TeknikInformatika di STMIK AMIKOM Yogyakarta

angkatan 2013. Aktif di dalam dunia Blogger danEntreprenuer.

Bayu Trisna Pratama, lahir di Masingai,Kalimantan Selatan pada 28 Maret 1995. Saat inimenjadi mahasiswa jurusan Teknik Informatika diSTMIK AMIKOM Yogyakarta angkatan 2013.

Lalu Mohammad Afif Farhan, lahir di Mataram,Nusa Tenggara Barat pada 11 November 1994. Saatini menjadi mahasiswa jurusan Teknik Informatikadi STMIK AMIKOM Yogyakarta angkatan 2013.


3.5-66


pembuatan aplikasi permainan othello 16x16 berbasis

Documents