aplikasi game tic tac toe 6x6 berbasis android …

Seminar Nasional Teknologi Informasi dan Multimedia 2016STMIK AMIKOM Yogyakarta, 6-7 Februari 2016

ISSN : 2302-3805

3.4-91

APLIKASI GAME TIC TAC TOE 6X6 BERBASIS ANDROIDMENGGUNAKAN ALGORITMA MINIMAX DAN HEURISTIC

EVALUATION

Ever Jayadi1), Muhammad Aziz Fatchur Rachman2), Muhammad Yuliansyah3)

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

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

Abstrak

Kemampuan otak manusia dapat dilatih dengan berbagaimacam cara yang menyenangkan, salah satunya adalahdengan permainan yang mengasah otak seperti tic-tac-toeNamun belakangan ini tic-tac-toe makin banyak dilupakanoleh berbagai kalangan. Bukan karena permainan ini sulit,namun karena pemain biasanya kesulitan mencari lawanyang bisa diajak untuk bermain tic-tac-toe dimanapun dankapanpun. Sebab permainan ini membutuhkan setidaknya 2orang untuk bermain dan media tulis untukmenggambarkan papan permainan. Dikarenakan duakendala ini, maka kami menemukan sebuah solusi yaitudengan membuat sebuah aplikasi Android yang memilikikemampuan berpikir (Kecerdasan Buatan) untuk diajakbermain tic-tac-toe pada perangkat Android.

Dalam membuat aplikasi ini, kami menggunakan algoritmaMiniMax yang dikombinasikan dengan HeuristicEvaluation untuk memperoleh kemampuan berpikir yangmemadai untuk dijadikan lawan main. Pemilihan algoritmaini karena dengan algoritma ini, perangkat denganspesifikasi rendah pun dapat menjalakan aplikasi ini sebabperulangan dalam algroitma ini hanya mengeksekusikemungkinan terbaik saja.

Hasil dari aplikasi ini adalah sebuah perangkat lunak yanginteraktif dengan pengguna dan dapat dijadikan lawanbermain tic-tac-toe dimanapun dan kapanpun tanpa perlurisih membawa kertas atau media lain untuk menjadipapan permainan dan juga tidak perlu bingung dalammencari lawan main.

Kata kunci: permainan, puzzle, algoritma, kecerdasanbuatan, android.

1. Pendahuluan

Aplikasi permainan yang berada pada sebuah komputeratau smartphone merupakan aplikasi yang dikenal olehbanyak orang dari yang muda sampai yang tua. Aplikasi inicukup mudah dan menyenangkan sehingga seringdigunakan untuk menghilangkan kepenatan. Penggunaanaplikasi permainan sering kali dilakukan secara seorang dirisaja karena tidak ada lawan yang dapat diajak bermainbersama. Beberapa aplikasi permainan harus dilakukansetidaknya oleh dua orang pemain terutama permainan two

player, board games, misalnya: permainan catur, tic-tac-toe, dan battleship[1].

Artificial Intelegence (AI) atau kecerdasan buatan biasanyadigunakan sebagai teknik untuk menggerakan komputersebagai lawan bermain dalam aplikasi permainan. TujuanAI digunakan untuk mencari pola permainan, merancangstrategi, mengkolaborasikan entity dalam computer, danbelajar dari pengalaman sebelumnya untuk mengambilkeputusan, dalam permainan tic-tac-toe dapat dilihatbahwa kesuksesan dari permainan merupakan kemenangandari satu pemain atau pemain lainnya, dimana mencari hasilyang paling masimal dan meminimalisir hasil dari lawan.Maka algoritma minimax digunakan pada boardgames tic-tac-toe[1].

Pada makalah ini akan membahas salah satu jenis twoplayer board games, yaitu permainan tic-tac-toe. Apliaksiyang digunakan disini merupakan permainan tic-tac-toeyang terdiri dari grid 6x6 dengan 5 kemenangan.Pembuatan permain ini sendiri menggunakan tools AndroidStudio untuk membangun program, beserta algoritma yangdi pakai ialah minimax dan heuristic evaluation.

2. Pembahasan

Pencarian pada AI di kelompokkan kedalam blind atau un-informed search (pencarian buta) dan heuristic atauinformed search (pencarian terbimbing).

Setiap metode mempunyai katakteristik yang berbeda-bedadengan kelebihan dan kekurangannya masing-masing[2]

Untuk mengukur performansi metode pencarian, terdapatempat kriteria yang dapat digunakan, yaitu :

a. Completeness

Apakah metode tersebut menjamin penemuan solusijika solusi memang ada?

b. Time Complexity

Berapa lama waktu yang diperlukan?

c. Space Complexity

Berapa banyak memory yang diperlukan?

d. Optimality

Apakah metode tersebut menjamin menemukansolusi yang terbaik jika terdapat beberapa solusi.


ISSN : 2302-3805

3.4-92

2.1 Algoritma Minimax

Penerapan AI dalam permainan tic-tac-toe inimenggunakan algoritma minimax dan heuristic evaluation.Minimax merupakan salah satu teknik pencarianmenggunakan depth-first search dengan kedalamanterbatas.

Minimax adalah sebuah algoritma yang di desain untukmemaksimalkan kemenangan dan meminimalkankekalahan dalam skenario terburuk di dalam game. Idenyaadalah untuk memilih langkah berikutnya yang mempunyainilai minimax tertinggi (mencapai langkah terbaik ketikamelawan musuh yang mempunyai langkah terbaik.

Pada permainan tic-tac-toe ini mempunyai lebih sedikitkemungkinan solusi, sehingga kita akan mempunyai cukupkomputasi untuk memainkan setiap kombinasi langkah darisetiap posisi dan kondisi. Namun hal ini dapat dihindaridengan membatasi sejauh mana komputer akanmenganalisis hasil dari langkah-langkah yang mungkin(menentukan kedalaman pohon). Tetapi dengan hal ini, kitaharus menambah kedalaman pohon pada state tersebutdama dengan state sebelumnya.

Algoritma minimax ini bekerja secara rekursif denganmencari langkah yang akan membuat lawan mengalamikerugian minimum. Semua strategi lawan akan dihitungdengan algoritma yang sama dan seterusnya. Ini berartipada langkah pertama komputer akan menganalisis seluruhpohon permainan. Dan untuk setiap langkahnya, komputerakan memilih langkah yang paling membuat lawanmendapatkan keuntungan minimum, dan yang palingmembuat komputer itu sendiri mendapatkan keuntunganmaksimum.

Dalam penentuan keputusan tersebut dibutuhkan suatu nilaiyang merepresentasikan kerugian atau keuntungan yangakan diperoleh jika langkah tersebut dipilih. Untuk itulahdisini digunakan sebuah fungsi heuristic evaluation yangberfungsi untuk mengevaluasi nilai sebagai nilai yangmerepresentasikan hasil permainan yang akan terjadi jikalangkah tersebut dipilih. Biasanya pada permainan tic-tac-toe ini digunakan nilai 1,0,-1 untuk mewakili hasil akhirpermainan berupa menang, seri, dan kalah. Dari nilai-nilaiheuristic inilah komputer akan menentukan simpul manadari pohon permainan yang akan dipilih, tentunya simpulyang akan dipilih tersebut adalah simpul dengan nilaiheuristic yang akan menuntun permainan ke hasil akhiryang menguntungkan bagi komputer.

Berikut garis besar algoritma minimax secara umum :

Pemakaian algoritma umum diatas untuk permainan tic-tac-toe adalah sebagai berikut :

Dilihat dari algoritma diatas, nilai heuristic yangdibangkitkan akan sangat mempengaruhi analisis dari AItersebut.

2.2 Aturan Permainan

Berikut beberapa aturan dalam permainan tic-tac-toe 6x6 :

a. Permainan memilih simbol “X” atau “O” untukdigunakan dalam permainan.

b. Yang melakukan permainan pertama bebasmeletakkan simbol pada papan permainan berukuran6x6.

c. Komputer (AI) akan jalan sesuai dengan strategi yangdia miliki.

d. Pemain ataupun komputer harus membentuk 1 garislurus baik vertikal, horizontal maupun diagonal.

Untuk menyelesaikan permainan ini terdapat 3 kondisiyang mungkin terjadi yaitu :

1. Kondisi Menang

Kondisi menang terjadi apabila pemain berhasilmembentuk garis lurus yang terdiri dari 5 simbol yangsama secara vertikal, horizontal, maupun diagonal.

2. Kondisi Kalah

Kondisi kalah terjadi apabila komputer (AI) mampumembentuk garis lurus yang terdiri dari 5 simbol yangsama secara vertikal, horizontal, maupun diagonalterlebih dahulu.

3. Kondisi Seri

Kondisi seri terjadi apabila pemain maupun komputer(AI) tidak mampu membentuk garis lurus yang terdiridari 5 simbol yang sama secara vertikal, horizontal,maupun diagonal.

Melakukan cek kemenangan

Pada permainan tic-tac-toe ini terdapat 32 kemungkinanuntuk memenangkan permainan. Kemungkinankemenangan tersebut di dapat dari 12 kombinasi simbol

Cari langkah yang dengan nilai maksimumIF langkah tersebut merupakan langkah kemenanganTHEN pilih langkah tersebut.ELSE

FOR EACH kemungkinan langkah yang adaCari langkah lawan yang minimum.

RETURN nilai dari langkah tersebut.Pilih langkah yang bernilai maksimum dari

langkah-langkah tersebut.[3]

IF ada langkah kemenangan THEN pilih langkahtersebut.ELSE lawan mempunyai 2 spot terisi dalam satugaris dengan spot ketiga masih kosong THEN tutuplangkah tersebut (isi spot kosong ketinga tersebut).ELSE melangkah ke state yang mempunyaikemungkinan menang tertinggi (berdasarkan nilaiheuristic yang dibangkitkan.[3]


ISSN : 2302-3805

3.4-93

yang sama secara horizontal, 12 kombinasi simbol yangsama secara vertikal dan 8 kombinasi simbol yang samasecara diagonal seperti gambar dibawah ini.

Gambar 1. Kemungkinan kemenangan

Gambar pada bagian vertikal dan horizontal diatasmewakili tiap baris dan kolom dimana terdapat 2kemungkinan kemengangan tiap baris dan kolomnya.

2.3 Pohon Keputusan

Gambar 2. Pohon keputusan

Pada simulasi pohon algoritma diatas, kita asumsikanbahwa posisi permainan seperti kondisi puncak pohon yangterlihat. Dimana pada puncak tersebut hanya tersisa empatkotak kosong yang bisa diberi tanda.

Pada langkah paling atas, pemain memberi tanda di kolom(1,0). Program akan langsung menganalisa semuakemungkinan yang dapat terjadi dan mencari kemungkinanpergerakan yang paling menguntungkan berdasarkan poinyang diberikan pada tiap kemungkinan. Dalam kasusdiatas, maka langkah yang memiliki poin paling tinggiadalah memberi tanda di kolom (1,4). Hal ini berulangsecara terus menerus hingga ditemukanya pemenang atauhingga tidak ada lagi kotak yang dapat diberi tanda.

Program memilih kemungkinan yang palingmenguntungkan berdasarkan kecocokan antara syaratkemenangan dengan kondisi kemungkinan yang diuji cobaoleh program itu sendiri.

Pada kasus diatas, dari 5 kemungkinan, terdapat satukemungkinan yang bisa menjadi kesempatan dari penggunauntuk memenangkan permainan dan ini disebut ancamanoleh program. Program akan secara otomatismemprioritaskan ancaman tersebut dan mengambiltindakan yang relevan dengan cara memberi tanda di kolom(4,1) sehingga meniadakan kemungkinan pengguna untukmenang dari kondisi tersebut.

2.4 Source Code Minimax dan Heuristic Evaluation

Gambar 3.Evaluasi heuristic pada setiap baris, kolom, dandiagonal

Evaluasi heuristik disini berfungsi sebagai penyekoranterhadap setiap baris, kolom, dan diagonal. Pada tahap iniNPC ( Non Player Character) akan menghitung setiapbaris, kolom, dan diagonal untuk menentukan jalanselanjunya. (0,0 , 0,1 , 0,2 , 0,3 , 0,4 , 0,5) disinimenunjukkan NPC akan mengecek pada baris 0 kolom 0,selanjutnya baris 0 kolom 1, dan seterusnya.


ISSN : 2302-3805

3.4-94

Gambar 4.program minmax yang diimplementasikan padaNPC

Pada program minimax akan menghitung score nilaiheuristik pada kedua pemain, player dan NPC (Non PlayerCharacter). Jika score itu lebih besar dari alpha (alphadisini untuk nilai maximal) maka player atau NPC tersebutmendapatkan dan mencari nilai maksimalkan, sedangkanjika score kurang dari beta (beta disini untuk nilaiminimal) maka player atau NPC tersebut akan mencarinilai minimal.

Gambar 5.knowledge based

Pada potongan program diatas ialah knowledge based yangdipasang pada papan permainan. Dimana akan adapengecekan kemenangan pada diagonal di baris nol kolom0 ke baris empat ke kolom 4. Jika salah satu pemainmengisi semua pada baris tersebut maka permainan akanselesai.

2.5 Performansi Metode Pencarian

Berikut adalah pengujian berapa lama waktu dan memoriyang dibutuhkan oleh AI untuk menyelesaikan 1 iterasi.Percobaan ini dilakukan one by one, maksudnya yaituketika player sudah mengisi satu kotak maka akandilanjutkan oleh si NPC atau AI. Ketika player sudahmengisi kotak dan dilanjutkan NPC disana terdapat delay,delay tersebut ialah waktu yang dibutuhkan NPC/AI untukmenyelesaikan iterasinya.

Gambar 6.penggunaan memory ketika tidak adanyaaktifitas dalam aplikasi

Keadaan aplikasi ketika tidak adanya aktifitas saat itu,memory yang digunakan ialah 23.78 MB.

Gambar 7.keadaan ketika player telah mengisi 3 kotakkosong

Pada grafik diatas player telah mengisi 3 kotak yangkosong, waktu yang dibutuhkan oleh NPC untuk mencarijawaban atau melakukan 1 iterasi ialah 0.5 second, danmemory yang digunakan ialah sekitar 0.27 MB.


ISSN : 2302-3805

3.4-95

Gambar 8.grafik ketika permainan telah selesai

Pada saat permainan telah berakhir dan sebelum direset,memory yang digunakkan ialah 23.66 MB.

Metode pencarian dengan algoritma minimax ini dilakukanpada semua simpul dalam setiap level secara mendalammulai dari simpul yang paling kiri. Jika sampai pada levelterdalam tidak ditemukan solusi, maka pencariandilanjutkan pada simpul sebelah kanan, demikianseterusnya sampai ditemukan solusi. Dengan cara sepertiini, metode pencarian algoritma minimax menjaminditemukannya solusi (jika solusinya memang ada). Dandengan mengkombinasikan dengan nilai-nilai heuristicevaluiation, solusi yang ditemukan pasti yang palingterbaik, dengan kata lain metode ini adalah complete danoptimal.

2.6 Hasil

Gambar 9.Tampilan menu permainan Tic Tac Toe

Tampilan menu awal ketika aplikasi dijalankan. Padapermainan ini player dapat memilih jenis permainannya,bermain dengan player lainnya atau bermain bersamamelawan AI/NPC

Gambar 10.Tampilan permainan Tic Tac Toe

Tampilan permainan tic-tac-toe menggunakan emulatorandroid, disana terdapat dimana player dapat memilihmenggunakan tanda “X’ atau “O”, serta pemain dapatmereset permainan jika permainan telah berakhir padatombol Reset.

3. Kesimpulan

Tic-tac-toe merupakan permainan yang melatihkemampuan otak sehingga cocok untuk semua kalanganusia. Game ini mengutamakan kemampuan logika untukmemprediksi langkah lawan dari segala kemungkinan yangdapat terjadi.

Game ini kami buat dengan menggunakan algoritmaminimax yang digabungkan dengan metode heuristicevaluation. Kombinasi ini memberikan game sebuahkemampuan untuk berpikir (kecerdasan buatan). Kamimemilih penerapan algoritma minimax dan metodeheuristic evaluation ini karena kombinasi ini dapatmemberikan hasil yang akurat namun dengan konsumsisumber daya yang sedikit. Dengan kata lain game kami inidapat berjalan di perangkat dengan spesifikasi teknisrendah sekalipun.

Kemampuan berpikir dari program kecerdasan buatan didalam game ini pun dapat diatur tingkat kecerdasannyasesuai dengan keinginan pengguna sehingga dapatmenyesuaikan dengan kemampuan berpikir pengguna.

Daftar Pustaka[1] http://zikky.lecturer.pens.ac.id/Project203/Paper20Minmax.pdf.[2] Suyanto, Artificial Intelligent, Bandung:Informatika, 2007.[3] Kevin McGee, “Advance Game Programming : AI”, Desember 9,

2005.


ISSN : 2302-3805

3.4-96

Biodata Penulis

Ever Jayadi, Mahasiswa S1 Jurusan Teknik InformatikaSTMIK AMIKOM Yogyakarta,

Muhammad Aziz Fatchur Rachman, Mahasiswa S1Jurusan Teknik Informatika STMIK AMIKOMYogyakarta,

Muhammad Yuliansyah, Mahasiswa S1 Jurusan TeknikInformatika STMIK AMIKOM Yogyakarta,

aplikasi game tic tac toe 6x6 berbasis android …

Documents