16
BAB 2
LANDASAN TEORI
2.1 Game Game adalah kegiatan yang berlangsung antara dua orang atau lebih yang membuat keputusannya sendiri untuk meraih tujuan (Clark C, 1987). Orang telah memainkan game pada komputer selama komputer itu sendiri sudah ada. Game itu sendiri memiliki 4 atribut utama (Rick Rogers, 2011) : 1. Tujuan. Game harus memiliki tujuan untuk dicapai oleh pemain. Tujuannya haruslah menantang namun dapat dicapai. 2. Aturan. Game haruslah memiliki aturan yang diikiti oleh semua pemain. 3. Umpan balik. Game itu sendiri haruslah memberi tau pemain apakah mereka bermain dengan baik atau tidak. 4. Pemain. Game haruslah ada pemain yang memainkan game. Ada banyak jenis game seperti skill atau action game, adventure game, simulation game, puzzle game, strategy game, dan masih banyak lagi. Strategy game adalah game yang membutuhkan kemampuan merancang dan melaksanakan sebuah strategi untuk menyelesaikan masalah. Adapan contoh strategy game adalah turn-based games dimana didalamnya termasuk game tradisional yang umumnya berjenis board game. Board game adalah permainan yang menggunakan papan sebagai tempat permainannya. Salah satu contoh board game yang terkenal adalah catur yang mana program permainan catur telah menjadi landasan untuk banyak penelitian pada program board game lainnya.
Universitas Sumatera Utara
7
2.2 Kecerdasan Buatan pada Game Kecerdasan buatan (Artificial Intelligence) adalah salah satu cabang dari ilmu komputer yang mempelajari bagaimana cara agar sebuah sistem menjadi cerdas dan dapat bertingkah laku seperti manusia sehingga dapat memecahkan suatu masalah. Kecerdasan buatan juga melibatkan penggunaan algoritma-algoritma pada sistem komputer untuk menyelesaikan masalah tersebut. Sistem komputer yang dirancang itu tentu saja tidak di desain dengan tujuan berkelakuan sama seperti manusia, tetapi dibuat dengan tujuan agar sistem tersebut dapat menghasilakan sebuah fungsi yang berguna (Ben Coppin, 2004). Oleh karena itu, saat ini kita sudah dapat membuat sebuah program komputer yang memiliki kemampuan berfikir seperti manusia untuk menyelesaikan banyak masalah. Masalah-masalah seperti mengenal wajah seseorang, atau berbicara layaknya manusia, dan masalah complex lainnya dapat terwujud dengan memanfaatkan kecerdasan buatan yang menggunakan algoritma yang cocok untuk mewujudkan itu semua. Kecerdasan Buatan telah banyak diimplementasikan dalam menciptakan sebuah game agar bertingkah laku realistis dengan memanfaatkan metode-metode yang ada. Metode yang diterapkan bertujuan untuk menemukan langkah terbaik dalam merencanakan pengambilan keputusan untuk sebuah permaianan (Diez et al., 2012). Saat ini tentu saja sebagian besar permainan modern memanfaatkan kecerdasan buatan dan dari masa ke masanya terus berkembang. Yang dibutuhkan game dari kecerdasan buatan itu sendiri dapat dirangkum dalam tiga hal berikut, yaitu kemampuan untuk menggerakan karakter, kemampuan untuk membuat keputusan akan bergerak kemana karakter tersebut, dan kemampuan karakter untuk dapat berfikir secara logis dan strategis. Gambar 2.1 akan memperlihatkan struktur dari kecerdasan buatan pada game.
Universitas Sumatera Utara
8
Gambar 2.1 Struktur Kecerdasan Buatan pada Game (Millington, 2006)
Struktur kecerdasan buatan dapat dibagi menjadi tiga bagian, movement (pergerakan), decision making (pengambilan keputusan), dan strategy (strategi). Dua bagian pertama (movement dan decision making) bekerja pada per-karakter yang ada pada game, sedangkan bagian strategy bekerja pada keseluruhan permainan. Tidak semua permainan membutuhkan ketiga bagian tersebut. Contohnya pada board game, hanya membutuhkan bagian ketiga, yaitu strategy. Movement artinya diperlukan sebuah algoritma yang membuat keputusan untuk melakukan sebuah gerakan. Sedangkan decision making diperlukan sebuah algoritma untuk memberi tahu langkah apa yang harus dilakukan selanjutnya oleh karakter dan tentunya setiap karakter memiliki batasannya masing-masing untuk mengambil sebuah keputusan. Dan bagian strategy berarti algoritma yang digunakan diterapkan pada seluruh karakter permainan, bukan algoritma yang hanya mengontrol satu karakter, tapi melibatkan pengontrolan seluruh grup karakter. Walaupun setiap karakter pada grup karakter memiliki pergerakan dan cara pengambilan keputusan yang berbeda-beda untuk setiap karakter, tapi tetap saja sebenarnya pergerakan seluruh bagian game dikontrol oleh strategi grup yang sama.
2.3 Algoritma Algoritma adalah proses yang di lakukan langkah demi langkah yang menghasilkan sebuah solusi untuk menyelesaikan masalah pada kecerdasan buatan (Millington, 2006). Contohnya saja algoritma untuk menemukan langkah terbaik untuk
Universitas Sumatera Utara
9
memenangkan permainan, atau algoritma untuk menentukan langkah selanjutnya yang harus diambil karakter, dan masih banyak contoh lainnya. Algoritma membutuhkan struktur data untuk menyimpan data yang akan dipergunakan algoritma untuk diolah agar manghasilkan suatu solusi dari sebuah masalah. Algotitma banyak digunakan untuk menyelesaikan berbagai masalah pada computer science yang banyak diimplementasikan pada aplikasi seperti database system, expert system, robot control system, dan lain-lain. Pada sebuah game system, dibutuhkan mesin pencari pada inti aplikasinya. Ada banyak algoritma pencarian yang telah digunakan untuk meningkatkan efisiensi pencarian seperti branch and bound, alpha-beta pruning, algoritma minimax, dan lain-lain (Borovska & Lazarova, 2007).
2.4 Algoritma pada Board Game Board game dijalankan dengan menerapkan algoritma turn-based yang biasanya hanya dimainkan oleh dua orang pemain yang bermain secara bergantian. Agar menang kita harus membuat lawan kita menjadi kalah. Jika menang kita mendapat point +1, dan lawan kita yang kalah akan mendapat poin -1. Ini disebut juga dengan zero-sum game (Millington, 2006). Tidak peduli cara apa yang diambil, apakah mencoba untuk menang atau membuat lawan menjadi kalah akan menghasilkan hasil yang sama. Board game juga adalah permainan dengan perfect information. Perfect information berarti tidak ada informasi yang disembunyikan oleh kedua pemain (Carolus, 2006). Tidak seperti dalam permainan kartu, contohnya poker, yang mana salah satu pemain tidak mengetahui informasi kartu lawan, begitu juga sebaliknya. Perfect information membuat kedua pemain mengetahui mengenai permainan yang akan dimainkan. Kedua pemain tahu hasil yang akan dicapai terhadap suatu langkah yang akan diambil, atau juga langkah selanjutnya yang bisa diambil setelah sebelumnya melakukan suatu langkah. Yang tidak diketahui hanyalah langkah yang akan diambil lawan. Namun tetap saja akan diketahui kemungkinan-kemungkinan langkah yang akan diambil lawan dan dampak untuk langkah kita selanjutnya. Pada dasarnya, algoritma minimax memiliki konsep pencarian dengan teknik Depth First Search (DFS). DFS akan membuat semua kemungkinan langkah dalam bentuk pohon dimana cabang-cabangnya merupakan kemungkinan langkah yang
Universitas Sumatera Utara
10
tercipta akibat langkah yang dibuat oleh parent node sampai akhirnya didapat salah satu pemain yang memenangkan permainan (Timothy, 2014). Pada gambar 2.2 ditunjukan bagaimana pohon permainan untuk permainan tic tac toe.
Gambar 2.2 Pohon Permainan dari Permainan Tic Tac Toe (Borovska & Lazarova, 2007)
Setiap permainan turn-based dapat direpresentasikan dalam bentuk pohon permainan. Gambar 2.2 menunjukan pohon permainan dari permainan tic tac toe untuk dua langkah pertamanya. Setiap node pada pohon menunjukan posisi papan permainan dan setiap cabangnya menunjukan langkah yang dapat diambil. Jumlah cabang untuk setiap papannya adalah sama dengan jumlah dari langkah yang dapat diambil. Ada saatnya pada suatu posisi papan tidak ada lagi langkah yang bisa diambil. Itu berarti telah mencapai akhir permainan dan point akhir akan diberikan pada setiap pemain. Pada zero-sum games, point akhir setiap pemain jika ditambahkan akan sama dengan nol.
2.5 Algoritma Minimax Algoritma minimax adalah algoritma pohon permainan yang dibagi menjadi dua bagian, dimana pemain pertama merupakan computer player dan pemain kedua merupakan human player. Minimax akan mencari jalan terbaik untuk computer player dan human player akan memainkan permainan dengan jalan terbaiknya sendiri. Dapat diartikan bahwa minimax akan memaksimalkan nilai jika langkah diambil untuk computer player dan meminimalkan nilai jika langkah diambil untuk human player (Elnaggar et al., 2014).
Universitas Sumatera Utara
11
Jadi pada minimax, jika computer player memilih langkah yang akan diambil, minimax akan memilih langkah dengan keuntungan terbesar karena minimax akan memaksimalkan nilai akhir computer player. Sedangkan saat human player jalan, tentu akan memilih langkah yang akan merugikan computer player atau dapat dikatakan human player akan meminimalkan nilai akhir dari computer player. Minimax tentu saja diperuntukan untuk mencari nilai terbaik dalam permainan berbasis zero-sum. Maksudnya, jika misalkan computer player yang mendapatkan nilai, maka human player akan mengalami kehilangan nilai dengan jumlah yang sama dengan nilai yang didapat computer player, atau sebaliknya (Plaat et al., 2012). Gambar 2.3 menunjukan bagaimana ilustrasi kerja dari algoritma minimax.
Gambar 2.3 Ilustrasi Kerja Algoritma Minimax (Ben Coppin, 2004)
2.6 Algoritma Negamax Algoritma minimax dilihat berdasarakan sudut pandang computer player, sehingga minimax dapat mengetahui di setiap tahapan, dia harus memaksimalkan nilai atau meminimalkan nilai tergantung tahapan tersebut milik computer player atau human player. Cara ini dapat diperbaharui dengan cara setiap ingin naik ke tahap selanjutnya kita negasikan nilainya dan memilih nilai maksimal. Sudut pandangnya pun berubah, karena setiap pemain memilih langkah dengan nilai maksimal, maka sudut pandang berubah disetiap gilirannya. Cara ini dapat disebut algoritma negamax. Perbedaan dari algoritma negamax dan minimax adalah negamax hanya menggunakan fungsi maksimal dan tidak seperti algoritma minimax yang menggunakan kedua fungsi yaitu fungsi maksimal dan fungsi minimal. Ini dapat dilakukan dengan menegasikan nilai yang dikembalikan dari point lawan daripada
Universitas Sumatera Utara
12
mencari nilai minimal (Elnaggar et al., 2014). Hal ini dapat ditunjukan dengan menggunakan relasi matematika berikut: Max (a, b) == -Min (-a, -b) Pada gambar 2.4 akan ditunjukan bagaimana ilustrasi kerja dari algoritma negamax.
Gambar 2.4 Ilustrasi Kerja Algoritma Negamax (Millington, 2006)
2.7 Android Android adalah sistem operasi mobile dan platform yang didasari oleh linux kernel versi 2.6 dan tersedia secara bebas untuk penggunaan commercial ataupun noncommercial. dan bersifat open source. Saat kita ingin membuat game menggunakan android, platform pada android memiliki beberapa kemudahan (Derek James, 2013), yaitu: 1. Android adalah open platform, yang artinya android tidak membatasi apa yang kita bisa akses atau apa yang bisa kita lakukan. 2. Android adalah mobile platform yang paling cepat berkembang, yang artinya lebih banyak orang yang akan mengunduh dan memainkan game kita.
2.8 Catur Harimau Permainan Catur Harimau adalah permainan tradisional masyarakat Sumatera Barat yang dimainkan oleh masyarakat, baik di desa bahkan dikota sekalipun. Adapun alasan kenapa dinamakan catur harimau adalah karena salah satu biji yang digunakan pada permainan ada yang berfungsi sebagai harimau yang menangkap semua mangsanya. Selain itu juga karena awal pemikiran di ciptakan permainan ini adalah untuk menyiapkan sisasat menjebak harimau dalam kehidupan sehari-hari (Departemen Pendidikan dan Kebudayaan, 1980).
Universitas Sumatera Utara
13
Permainan catur harimau dimainkan oleh dua pemain, satu pemain menjalankan biji harimau sebanyak 3 buah, dan pemain lain menjalankan biji kambing sebanyak 22 buah. Bentuk papan permainannya sendiri adalah persegi yang umumnya berukuran 30 cm x 30 cm. Persegi itu dibagi lagi menjadi kotak-kotak kecil berukuran 7.5 cm x 7.5 cm. Dan untuk setiap empat kotaknya di beri tanda silang. Gambar 2.8 memperlihatkan bentuk dari papan permainan dari permainan catur harimau.
Gambar 2.5 Papan Permainan Catur Harimau (Departemen Pendidikan dan Kebudayaan, 1980) Adapun cara bermainnya adalah: 1. Pertama-tama pemain harus menentukan terlebih dahulu ingin memainkan bidak apa, hariamu atau kambing. Dan bidak akan berganti untuk setiap pemain di ronde berikutnya. Setelah ditentukan, masingmasing pemain siap untuk memulai permainan. 2. Di awal permainan, diletakan terlebih dahulu ke tiga bidak harimau di titik tengah dari papan dan delapan bidak kambing mengelilingi bidak harimau tadi. Sedangkan 14 bidak kambing lainnya menunggu diluar papan untuk masuk ke papan permainan. 3. Masing-masing pemain akan bergantian menjalankan bidaknya. Pertama-tama yang bergerak adalah bidak harimau. Setelah harimau bergerak, apakah dia memakan kambing atau bergerak pada satu garis lurus, maka gantian pemain yang memegang bidak kambing memasukan satu bidak kambing ke papan permainan diletakan di
Universitas Sumatera Utara
14
tempat yang diinginkan pemain. Setelah semua bidak kambing masuk, barulah kambing dapat bergerak dengan aturan yang sama dengan bidak harimau yaitu bergerak pada satu garis lurus. 4. Harimau dapat memakan kambing dengan cara melompati bidak kambing pada satu garis lurus tempat ia berada. Yang akan keluar sebagai pemanang pada satu ronde yaitu: 1. Bidak kambing, apabila kambing dapat mengurung semua harimau sehingga tidak dapat bergerak lagi. 2. Bidak harimau, apabila bidak kambing sudah habis dimakan bidak harimau. Sedangkan yang akan keluar sebagai pemenang permainan adalah siapa yang berhasil memenangkan permaianan sebanyak 2 kali dalam 3 ronde yang dilakukan, dan jika salah satu pemain menang dua kali berturut-turut maka ia lah pemenangnya.
2.9 Penelitian Terdahulu Belum ada penelitian sebelumnya yang membahas tentang permainan catur harimau namun sudah banyak penerapan algoritma pada beberapa board game jenis lainnya. Penelitian terdahulu dapat dilihat pada tabel 2.1.
Tabel 2.1 Penelitian Terdahulu No 1
Peneliti David E. Moriarty &
Tahun 1995
Risto Miikkulainen
Keterangan Metode : Alpha-Beta Alpha-Beta adalah algoritma pruning untuk mempercepat
pencarian.
Algoritma
diterapkan pada permainan Othello. 2
Jacek Mandziuk, Magdalena Kusiak & Karol Waledzik
2007
Metode : Heuristic Algoritma heuristic
diterapkan
pada
permainan checkers.
Universitas Sumatera Utara
15
Tabel 2.1 Penelitian Terdahulu (lanjutan) No 3
Peneliti Tan Shunhua & Chen
Tahun 2012
Miao
Keterangan Metode : Minimax dengan optimasi AlphaBeta Algoritma minimax dengan optimasi alpha-beta diterapkan pada permainan catur. Penelitian dilakukan pada pohon permainan untuk lima langkah pertama.
4
Kevin Octavianus, Trie 2015 Octavia & Willy
Metode : Negamax dengan optimasi Alpha-Beta Algoritma negamax dengan optimasi alpha-beta diterapkan pada permainan catur berbasi desktop dengan animasi 3D.
Universitas Sumatera Utara
