Game adalah sesuatu yang di mainkan dengan peraturan tertentu yang menentukan kemenangan dan kekalahan. Pemain dapat menyelesaikan permainan dengan cara yang bermacam macam sesuai dengan jenis permainan, tingkat kesulitan dan urutan urutan tertentu yang sudah di atur oleh si pembuat game. Terdapat berbagai macam algoritma yang bisa diterapkan dalam pembuatan game, dan kita akan mencoba menganalisa beberapa game sederhana yang mungkin sudah sering kita mainkan sebelumnya.
1. MATCHES
Matches adalah game strategi pemilihan objek secara baris dimana pemain yang memilih objek terakhir adalah yang kalah. Game ini merupakan game bawaan dari software strawberry prolog dan masih bisa kita kembangkan. Konsepnya, atur strategi pengambilan korek dan sisakan minimal 1 batang terakhir agar diambil oleh lawan.
Dalam permainan tersebut pemain bisa memilih siapa yang duluan melakukan pengambilan korek, entah itu kita duluan atau AI. Pilihan tersebut terdapat pada menuOptions. Arena permainan terdapat 5 baris dan 5 kolom korek dengan jumlah setiap kolom dan baris berbeda. Pemain bergantian mengambil jumlah korek sesuai keinginan. Misal, kita adalah pemain yang mendapat giliran pertama, jika kita ingin mengambil 3 korek sekaligus pada baris 5 kolom 5, maka kita klik korek pada baris 3 kolom 5. Nantinya AI akan mengambil korek secara random, lihat gambar dibawah:
Pada gambar tersebut AI mengambil 2 korek pada baris 3 kolom 4. Pengambilan korek yang dilakukan AI bisa dibilang secara random, namun dalam pembuatannya Ai diatur dengan algoritma-algoritma berikut ini:
1. Minimax
Algoritma minimax sendiri merupakan algoritma yang akan melakukan pemeriksaan secara keseluruhan dalam sistem game sehingga AI dapat menentukan langkah yang akan diambil dan keputusan yang akan diambil hingga AI tersebut mendapat sebuah kemenangan dari game tersebut.
2. DFS
Algoritma Depth-First Search merupakan suatu langkah-langkah pencarian mendalam yaitu dengan cara mengunjungi atau melewati anak suatu simpul sebelum mengunjungi simpul tetangganya. Dalam pencarian jarak terpendek akan dihasilkan suatu jalur yang akan dilewti untuk mencapai suatu tujuan atau menemukan jalur menuju sasaran.
2. TICTACTOE 5X5
Pada postingan kali ini saya akan menjelaskan tentang algoritma permainan pada permainan TICTACTOE 5X5. Permainan ini sebenarnya saya buat untuk memenuhi penilaian praktikum Pengantar Kecerdasan Buatan semester lalu.
INITIAL STATE
Initial state dalam game TicTacToe 5x5 ini akan menampilkan arena permainan dengan papan kotak-kotak yang berdimensi 5x5, dimana terdapat 5 baris dan 5 kolom. Objek yang akan bermain dalam game ini adalah “user” atau pemain dan komputer yang telah diberi AI. TicTacToe yang saya buat ini sedikit berbeda dengan kebanyakan game sejenis yang ada. Pada permainan TicTacToe yang umum biasanya menggunakan X dan O sebagai simbol dari pemain dan komputer. Sedangkan pada game yang buat akan sedikit dimodifikasi karena saya menggunakan tema TinkerBell dengan simbol X dan O yang diganti dengan tokoh Tinker Bell dan Peter Pan.
Penggunaan tema game yang berbeda dari yang umum digunakan dimaksudkan untuk menghilangkan kejenuhan pada pemainnya. Dan karena game ini merupakan salah satu permainan asah otak yang baik diterapkan kepada anak-anak dalam masa perkembangannya, maka mengganti tema game saya pilih untuk lebih menarik minat pemainnya.
Didalam game ini terdapat menu yang terdapat dibagian atas kotak permainan, antara lain :
1. New Game : jika menu ini di klik maka menandakan pemain sudah siap
untuk memulai permainan, dan waktu akan berjalan mundur selama 60 detik.
2. Help : jika menu ini di klik maka akan ada kotak dialog sebagai
penjelasan apa yang harus dilakukan dalam game ini.
3. Exit : untuk keluar dari permainan.
Initial state dari game ini adalah sebagai berikut :
RULES
Ada beberapa aturan dalam permainan ini, antara lain :
1. Permainan dimulai dengan pemain yang jalan terlebih dahulu. Pemain dengan simbol Tinker Bell bebas meletakan simbol dipapan kotak yang tersedia.
2. Komputer (AI) akan jalan berikutnya sesuai dengan strategi yang dia punya.
3. Pemain ataupun komputer harus membentuk satu garis lurus baik vertikal, horizontal ataupun diagonal untuk memenangkan permainan ini.
4. Komputer yang telah diberi AI bertugas menghalangi pemain untuk menang dengan cara meletakkan simbol Peter Pan di garis yang dibuat oleh pemain.
GOAL
Tujuan (goal) untuk menyelesaikan permainan ini adalah membuat sebuah garis lurus yang terdiri 5 kotak deretan simbol secara vertical, horizontal maupun diagonal.
Terdapat beberapa kondisi yang mungkin terjadi pada permainan ini, yaitu :
1. KONDISI MENANG
Kondisi menang terjadi apabila kita berhasil membentuk sebuah garis lurus yang terdiri dari 5 buah simbol Tinker Bell, baik secara horizontal, vertikal maupun diagonal.
2. KONDISI KALAH
Kondisi kalah dapat terjadi karena 2 hal, yaitu :
1) Kondisi kalah yang pertama terjadi apabila kita tidak berhasil membentuk 5 buah simbol Tinker Bell secara horizontal, vertikal ataupun diagonal. Atau kondisi dimana AI menang terlebih dahulu.
2) Kondisi kalah yang kedua terjadi jika waktu bermain sudah habis padahal kita belum bisa menyelesaikan permainan.
3. KONDISI SERI
Kondisi seri terjadi apabila semua kotak telah terisi tetapi belum ada yang bisa membentuk 5 buah simbol secara berurutan secara vertikal, horizontal maupun diagonal.
KECERDASAN BUATAN (AI)
Konsep kecerdasan yang diberikan dalam permainan TicTacToe 5x5 ini adalah pemberian kecerdasan pada komputer sehingga dia dapat berpikir layaknya manusia/pemain biasa bahkan lebih cerdas dari manusia.
Pemberian AI pada komputer dalam permainan TicTacToe 5x5 ini adalah pemberian algoritma yang berupa strategi-strategi permainan yang mungkin dilakukan oleh komputer agar dapat mengimbangi atau malah menyaingi kemampuan bermain si pemain.
3. CATUR
Catur dimainkan di kotak papan delapan baris (disebut barisan dan dilambangkan dengan angka 1 sampai 8) dan delapan kolom (disebut file dan dilambangkan dengan hurufa,untuk h) kuadrat. Warna kotak enam puluh empat alternatif dan disebut sebagai “kotak cahaya” dan “kotak gelap”. papan catur tersebut ditempatkan dengan kotak cahaya di ujung sebelah kanan terdekat peringkat ke setiap pemain, dan potongan-potongan ditetapkan seperti yang ditunjukkan di diagram, dengan masing-masing ratu pada warna sendiri.
Potongan dibagi, dengan konvensi, ke set putih dan hitam. Para pemain yang disebut sebagai ” White “dan” Black “, dan masing-masing permainan dimulai dengan enam belas potongan warna yang ditentukan. Ini terdiri dari satu raja , satu ratu , dua rooks , dua uskup , dua kesatria dan delapan pion .
Sebelum bertanding, pecatur memilih warna buah yang akan ia mainkan. Pemegang buah putih memulai langkah pertama, yang selanjutnya diikuti oleh pemegang buah hitam secara bergantian. Tujuan permainan adalah mencapai posisi skak mat. Hal ini bisa terjadi bila Raja terancam dan tidak bisa menyelamatkan diri ke petak lain. Tidak selalu permainan berakhir dengan kekalahan, karena bisa terjadi pula peristiwa seri atau remis di mana kedua belah pihak tidak mampu lagi meneruskan pertandingan karena tidak bisa mencapai skak mat. Peristiwa remis ini bisa terjadi berdasarkan kesepakatan maupun tidak. Salah satu contoh remis yang tidak berdasarkan kesepakatan – tetapi terjadi adalah pada keadaan remis abadi. Keadaan remis yang lain adalah keadaan pat, dimana yang giliran melangkah tidak bisa melangkahkan buah apapun termasuk Raja, tetapi tidak dalam keadaan terancam skak. Dalam pertandingan catur pihak yang menang biasanya mendapatkan nilai 1, yang kalah 0, sedang draw 0.5.
Algoritma Dalam Sebuah Game Catur
1. PENDAHULUAN
Tree search adalah salah satu algoritma inti dalam banyak program permainan game. Tree search melihat semua kemungkinan yang ada dalam permainan sebagai pohon, dengan langkah legal dalam permainan sebagai akar dari pohon-pohon tersebut. Daun dari pohon-pohon yang ada merupakan posisi terakhir dari permainan, di mana hasil dari permainan sudah dapat diketahui. Masalah yang dihadapi dalam menyusun sebuah algoritma permainan adalah ukuran dari pohon permainan ini sangatlah besar, dapat dirumuskan sebagai W^D, di mana W adalah rata-rata jumlah langkah yang legal dalam satu posisi, dan D adalah kedalaman dari sebuah pohon. Melakukan pencarian terhadap keseluruhan pohon adalah mustahil, terutama karena keterbatasan waktu yang ada, bahkan untuk komputer tercepat sekalipun. Maka dari itu penggunaan algoritma yang tepat untuk melakukan pencarian terhadap pohon didasarkan pada menghindari pencarian terhadap seluruh pohon. Berbagai algoritma pencarian berikut digambarkan menggunakan pengantar bahasa C. Variable serta fungsi yang ada memiliki arti sebagai berikut.
1.1 Chess Tree Search
1.1 Chess Tree Search
Dalam sebuah permainan catur menentukan langkah terbaik dapat dilihat sebagai suatu proses searching dalam sebuah pohon. Pada akar pohon kita mencari posisi successor terbaik untuk dijalankan oleh pemain pada tingkat selanjutnya kita mencari posisi successorterbaik berdasarkan dari posisi musuh, dst.
Pencarian dari keseluruhan pohon akan menghasilkanW^D kali perhitungan seperti sudah dijelaskan sebelumnya. Hal ini tentunya mustahil mengingat banyaknya langkah yang mungkin dalam suatu permainan catur (semakin banyak langkah yang mungkin dalam permainan mengakibatkan menignkatnya nilai dari W dan D).
1.2. Solusi
Solusi untuk permasalahan chess search tree beragam.Salah satunya adalah algoritma minmax negamax dimana semua kemungkinan langkah dihitung kemungkinannya. Selain itu juga ada alpha-beta search di mana nilai dari suatu posisi hanya dihitungapabila nilai dari posisi tersebut lebih baik atau lebih buruk dari posisi yang didapat sebelumnya. Juga principal variation search yang merupakan pengembangan dari alpha-beta search.
2.PEMBAHASAN ALGORITMA
2.1. MiniMax dan NegaMax
NegaMax adalah struktur fundamental di mana menjadi dasar bagi setiap algoritma pencarian terhadap chess tree. NegaMax mengimplementasikan pemikiran bahwa semakin buruk langkah yang dilakukan oleh lawan artinya langkah yang kita lakukan semakin baik.
Mengimplementasikan pemikiran ini sebenarnya mudah. Pemikiran ini menggunakan dasar bahwa catur adalah sebuah permainan symmetrical, oleh sebab itu maka fungsi analisis haruslah mengeluarkan nilai yang simetris. Jadi pada setiap posisi nilai dari langkah yang dilakukan oleh putih adalah negasi dari langkah yang dilakukan oleh hitam, atau bisa dibilang bahwa jumlah dari nilai keduanya adalah 0.
Apabila putih unggul satu pion maka sudah jelas bahwa hitam tertinggal sebanyak jumlah yang sama.Prinsip yang sama dapat diperluas ke dalam keunggulan posisi, misalnya putih memiliki dua benteng dalam satu garis yang sama maka putih mendapatkan poin tambahan, pada saat yang sama posisi hitam menjadi lebih lemah dengan jumlah yang sama karena hal ini.
Dasar dari algoritma ini adalah bahwa chess treesearch merupakan pergantian antara maksimalisasi dan minimalisasi nilai dari posisi pada pohon; biasa disebut dengan proses minimax. Untuk membedakan posisi antara pemain dengan lawannya, nilai dari suatu posisi selalu dievaluasi dari sudut pandang pemainyang akan berjalan, hal ini dilakukan dengan melakukan negasi terhadap nilai yang dilihat oleh lawan; ini disebut dengan proses negamax. Proses ini bila digambarkan dengan pseudo code bahasa yang mirip dengan C menjadi seperti berikut.
Jumlah posisi yang harus dihitung menggunakan algoritma ini adalah W^D, di mana W adalah lebar dari pohonnya (jumlah rata-rata langkah yang mungkin pada setiap posisi) dan D adalah kedalaman pohonnya (^ menunjukkan pengeksponensialan). Ini sangatlah tidak efisien dan akan menghambat bahkan super computer sekaligus untuk mencapai tingkat kedalaman yang tinggi.
2.2. Alpha-Beta Search
Alpha-Beta search adalah suatu teknik untuk mengurangi secara besar-besaran ukuran dari pohon pencarian. Dengan menggunakan algoritma NegaMax kita melakukan pencarian semua jawaban terhadap semua langkah dalama permainan. Rata-rata permainan catur memiliki 30 langkah legal, asumsikan program menganalisis 50.000 langkah tiapdetiknya.Mari kita lihat seberapa dalam pencarian dapat dilakukan.
4. PACMAN
Pacman adalah sebuah permainan video arkade yang cukup terkenal. Cara bermainnya mudah yaitu pemain (pacman) diharuskan memakan makanan (berbentuk titik-titik kecil) dan sebuah bulatan besar (energizer) sampai habis di dalam sebuah labirin yang berliku-liku. Tidak hanya menghabiskan makanan tersebut, pemain juga harus menghindari 4 ‘hantu’ yang berkeliaran secara random untuk menangkap pemain. Jika pemain bertemu dengan hantu-hantu tersebut maka pemain dinyatakan gagal dan harus mengulangi dari awal lagi. Tetapi pemain bisa mengalahkan hantu tersebut dengan memakan energizer yang terdapat di pojokkan labirin. Jika pemain memakan titik besar tersebut, maka para hantu akan ketakutan dan berusaha menjauh dari pemain. Dalam hal ini pemain bisa memakan hantu tersebut dan mendapatkan bonus yang besar, tetapi para hantu yang termakan tidak mati begitu saja, mereka kembali ke posisi semula dan kembali mengejar pemain. Pemain dinyatakan menang jika semua makanan habis tak tersisa dan pemain akan memasuki level berikutnyaPergerakan para hantu ini dipengaruhi oleh kecerdasan buatan atau Artificial intelligence (AI), dimana para hantu diberi kecerdasan untuk menentukan langkah dan mengambil keputusan akan bergerak kemana dengan menentukan rute yang paling pendek (minimum),
Tujuan game
tujuannya adalah menangkap pemain. Setiap hantu harus memiliki pemikiran berbeda dan memiliki kemampuan bekerja sama untuk mengejar pemain, sehingga permainan akan tampak lebih menarik. Persoalan mendekati karakter Pacman ini dapat diselesaikan dengan berbagai macam cara, salah satunya dengan menggunakan algoritma greedy
algoritma greedy
Algoritma Greedy membentuk solusi langkah per langkah (step by step). Terdapat banyak pilihan yang perlu di eksplorasi pada setiap langkah solusi, karenanya pada setiap langkah harus dibuat keputusann yang terbaik dalam menentukan pilihan.Keputusan yang telah
diambil pada suatu langkah tidak dapat diubah lagi pada langkah selanjutnya. Sebagai contoh, jika kita manggunakan algoritma Greedy untuk menempatkan komponen diatas papan sirkuit, sekali komponen telah diletakkan dan dipasang maka tidak dapat dipindahkan lagi.
Pada setiap langkah diperoleh optimum lokal. Bila algoritma berakhir, kita berharap optimum lokal menjadi optimum global.
Algoritma Greedy adalah salah satu algoritma yang dapat digunakan untuk mendapatkan solusi terbaik dan merupakan algoritma yang paling populer dalam hal ini.
Secara Harfiah Greedy artinya rakus atau tamak, sifat yang berkonotasi negatif. Orang yang memiliki sifat ini akan mengambil sebanayak mungkin atau mengambil yang paling bagus atau yang paling mahal. Sesuai dengan arti tersebut, Prinsip Greedy adalah take what you can get now. Dalam kehidupan sehari hari Greedy dapat digunakan dalam masalah seperti :
Memilih beberapa jenis investasi
Mencari jalur tersingkat ini merupakan implementasi untuk game pacman
5. Tetris
Pengertian Game Tetris
Tetris adalah permainan teka-teki yang disusun dan diprogram oleh sepasang programmer berkebangsaan Rusia.Dalam permainan tetris, balok-balok tetris berjatuhan ke area permainan dalam waktu konstan.Balok tetris selalu terdiri dari 4 balok kecil yang membentuk 7 macam rupa.
Algoritma
Pemain dapat mengontrol balok tetris yang jatuh melalui 4 tombol arah panah untuk menggeser ke kanan atau ke kiri dan tombol arah panah ke bawah untuk mempercepat jatuhnya balok tetris. Satu kendali yang lain adalah untuk memutar bentuk balok tetris 90ยบ’
Algoritma yang gunakan untuk mencari solusi dari permainan tetris adalah algoritma yang menggunakan konsep-konsep yang ada dalam algoritma Greedy dan Algoritma BruteForce.Algoritma Greedy merupakan metode yang paling umum digunakan untuk memecahkan masalah optimasi.Algoritma ini sederhana dan sesuai dengan tujuan yang ada.
Algoritma Greedy memecahkan masalah langkah per langkah, pada setiap langkah:
1. mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa memperhatikan konsekuensi ke depan (prinsip “take what you can get now!”)
2. berharap bahwa dengan memilih optimum local pada setiap langkah akan berakhir dengan optimum global Brute force adalah sebuah pendekatan yang sesuai (straightforward) untuk memecahkan suatu masalah, biasanya didasarkan pada pernyataan masalah (problem statement) dan definisi konsep yang dilibatkan.
Algoritma brute force memecahkan masalah dengan sangat sederhana, langsung dan dengan cara yang jelas (obvious way). Algoritma yang digunakan untuk mendapatkan susunan tumpukan balok yang paling baik dengan menempatkan balok ke tempat yang tepat.Algoritma ini menggunakan prinsip Greedy dalam mencari langkah sollusi yang paling menguntungkan. Prioritas keuntungan yang tersusun terdiri dari:
1. Membentuk satu atau lebih baris paling penuh
2. Membentuk satu atau lebih baris paling mendekati penuh
3. Tidak membentuk ruang kosong pada susunan tumpukan balok
4. Balok dapat masuk ke dalam susunan tumpukan balok paling dalam Algoritma yang kami kemukakan akan mencari penempatan balok yang jatuh ke ruang yang paling tepat sesuai prioritas keuntungan di atas diantara susunan tumpukan balok. Pencarian ini akan dilakukan secara Brute Force. Balok yang jatuh akan dicoba untuk ditempatkan ke ruang di antara susunan tumpukan balok dibawah.
Algoritma ini akan mencari penempatan yang sesuai dengan prioritas di atas. Pencarian solusi diantara susunan tumpukan balok akan dilakukan secara Brute Force. Algoritma ini akan mencari solusi paling menguntungkan untuk setiap sisi balok yang sedang jatuh. Pencarian solusi untuk setiap sisi dilakukan secar Brute Force. Apabila pada skala prioritas tertinggi memiliki lebih dari satu solusi terbaik yang sama, maka diantara solusi tersebut akan dibandingkan satu sama lain untuk mencari yang paling menguntungkan dengan standard prioritas selanjutnya, dan begitu selanjutnya. Apabila pada skala prioritas tertinggi tidak memiliki solusi, maka akan mencari solusi paling menguntungkan dengan skala prioritas selnjutnya, dan begitu selanjutnya. Apabila pada skala prioritas tertinggi hanya memiliki satu solusi paling menguntungkan, maka akan dibandingkan dengan solusi dari hasil pencarian solusi untuk sisi balok yang lain. Diantara setiap solusi sisi balok, dicari solusi yang paling menguntungkan sesuai skala prioritas di atas. Dan balok akan ditempatkan pada ruang tersebut.
Apabila ada kasus seperti diatas, maka algoritma tersebut akan mencari solusi yang paling menguntungkan untuk menempatkan balok tersebut ke ruang di antara susunan tumpukan balok. Pencarian dicari secara brute force dari kiri ke kanan untuk sisi yang pertama kali keluar.Dapat dilihat seperti gambar berikut, bahwa lgoritma seakan-akan menempatkan balok tersebut dari kiri ke kanan untuk balok dengan sisi tersebut.
Apabila ada kasus seperti diatas, maka algoritma kami akan mencari solusi yang paling menguntungkan untuk menempatkan balok tersebut ke ruang di antara susunan tumpukan balok. Pencarian dicari secara brute force dari kiri ke kanan untuk sisi yang pertama kali keluar.Dapat dilihat seperti gambar berikut, bahwa lgoritma seakan-akan menempatkan balok tersebut dari kiri ke kanan untuk balok dengan sisi tersebut.
Setelah algoritma ini mancari solusi sampai paling kanan, maka algoritma ini akan menyimpan satu solusi terbaik yang ada. Apabila ada beberapa solusi yang sama baiknya, maka akan diambil penempatan paling kiri, seperti dilihat dibawah ini.
Setelah menyimpan solusi terbaik untuk sisi tersebut, maka algoritma ini akan mulai mencari solusi optimum untuk sisi berikutnya. Tampak di bawah, algoritma in seakan-akan memutar balok untuk memulai pencarian sisi berikutnya.Sisi berikut yang kami maksud disini adalah sisi dimana balok yang sedang jatuh diputar 900 searah jarum jam.
Setelah itu, algoritma ini akan menyimpan solusi dari setiap sisi berikutnya, seperti terlihat pada tiga gambar berikut ini.
Diantara setiap solusi sisi balok, dicari solusi yang paling menguntungkan sesuai skala prioritas di atas. Dan balok akan ditempatkan pada ruang tersebut. Seperti terlihat pada gambar berikut, algoritma ini telah menemukan solusi terbaik, dan menempatkan balok pada ruang tersebut.
Penggunaan Matriks dalam pembuatan Tetris
Pada game tetris, terdapat blok-blok yang akan kita susun secara horizontal ataupun vertikal blok-blok tersebut dinamakan dengan grid. Jumlah tiap baris grid tergantung pada si pembuat tetris, kalo contoh yang kami gunakan berjumlah 15 grid.Grid tersebut pada pemrograman kita buat dengan menggunakan matriks berdimensi 2.Contoh :
___________________
o o o o
o o o o
o o o o
__________________
Sebagai contoh gambar diatas adalah matriks ukuran 4x3 (4 kolom, 3 baris).Begitu pula pada tetris juga memiliki ukuran kolom x baris (m x n). Pada kolom 1 baris 1, memiliki index[0,0]. Pada kolom 1 baris 2, memiliki indexnya[0,1]. Pada kolom 1 baris 3, memiliki index[0,2]. Pada kolom 2 baris 1, itu indexnya[1,0]. Pada kolom 2 baris 2, itu indexnya[1,1] dan s seterusnya. Di sini kami anggap susunannya terlihat seperti pada matriks dibawah ini :
[0,0] [0,1] [0,2] [0,3]
[1,0] [1,1] [1,2] [1,3]
[2,0] [2,1] [2,2] [2,3]
Baris paling atas pada tetris (baris 1) memiliki index [0,n] sampai [0,n+1]. Sehingga dapat kita anggap ukuran layar tetris [m,n]. Setiap ada blok yang turun atau berjatuhan kita definisikan sebagai, m+1 dan setiap bergeser kekanan n+1 dan setiap kekiri n-1
Pada permainan tetris ini apabila blok yang berjatuhan telah melampaui batas dari layar tetris [m,n] maka permainan akan berakhir (game over) sehingga apabila ada baris yang penuh (sesuai dengan syarat) maka baris tersebut akan dihapus.
Daftar referensi.
https://oinkseterez.wordpress.com/2010/06/01/permainan-catur/
http://chachados.blogspot.co.id/2012/04/algoritma-pada-game-tetris.html
