Analisa 5 Game Beserta Algoritmanya

1. Tetris

Algoritma yang digunakan dalam permainan tetris dan akan kami bahas dalam makalah ini adalah algoritma yang menggunakan konsep-konsep algoritma greedy dan algoritma brute force. Algoritma greedy banyak digunakan dalam memecahkan masalah optimasi, algoritma ini juga cukup 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 pada tetris untuk mendapatkan susunan balok dengan posisi akhir yang paling baik, yaitu membentuk suatu baris penuh sehingga baris dapat terhapus. Algoritma ini menggunakan prinsip mencari langkah solusi yang paling manguntungkan yaitu algoritma greedy. 

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 jelaskan akan mencari penempatan balok yang turun pada posisi yang paling tepat dan sesuai dengan keuntungan diatas diantara susunan tumpukan balok. Pencarian solusi akan dilakukan dengan pendekatan algoritma Brute force.

2.CATUR

Catur adalah permainan yang dimainkan antara dua pemain . Permainan ini dimainkan pada papan catur , yang merupakan papan kotak-kotak persegi dengan 64 kuadrat diatur dalam sebuah-oleh-delapan grid delapan. Pada awalnya, tiap pemain kontrol enam belaspotongan : satu raja , satu ratu , dua rooks , dua kesatria , dua uskup , dan delapan pion . Tujuan permainan ini adalah untuk sekakmatlawan raja, dimana raja adalah serangan langsung (di ” cek “) dan tidak ada cara untuk menghapus atau mempertahankannya dari serangan pada langkah berikutnya.

Aturan Permainan

Catur dimainkan di kotak papan delapan baris (disebut barisan dan dilambangkan dengan angka 1 sampai 8) dan delapan kolom (disebut file dan dilambangkan dengan huruf a,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.

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

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 tiap detiknya.Mari kita lihat seberapa dalam pencarian dapat dilakukan.

3. Othello

Adalah permainan papan strategi untuk dua pemain, dimainkan pada 8 × 8 papan uncheckered. Ada enam puluh empat potongan permainan yang identik disebut disk (sering dieja "cakram"), yang ringan di satu sisi dan gelap di sisi lain. Pemain bergiliran menempatkan disk di papan dengan warna mereka ditugaskan menghadap ke atas. Selama bermain, setiap disk warna lawan yang berada dalam satu garis lurus dan dibatasi oleh disk hanya ditempatkan dan disk lain warna pemain saat ini yang diserahkan kepada warna pemain saat ini.

Tujuan dari permainan ini adalah untuk memiliki mayoritas disk berubah untuk menampilkan warna Anda ketika kotak kosong dimainkan lalu diisi.(dikutip dari Wikipedia)

Analisa :

Permainan Othello sebenar memiliki tujuan algoritma yang hampir sama dengan catur dengan mencari kemungkinan yang sama dengan menggunakan bidak untuk mencapai suatu tujuan . jadi algoritma yang digunakan pada Othello hampir sama dengan  yang diguanakan pada catur yaitu algoritam DFS DAN MINIMAX karena DFS lebih kepada bagai mana mencari cara untuk mencapai tujuan dengan menggunakan berbagai kemungkinan yang ada . hampir sama dengan DFS ,MINIMAX juga menganilisa cara agar memiliki kemungkinan untuk mencapai tujuan dengan berbagai kemungkinan juga .



4. Matches

Permainan dimulai dengan menekan tombol pilihan, disitu akan terlihat pilihan, computer dahuli atau kita yang terlebih dahulu. Disini saya memilih untuk maju terlebih dahulu, player pertama akan memilih salah satu ikon yang akan dihilangkan. Berikutnya untuk CPU yang memilih untuk ikon mana yang akan dipilih untuk maju. Jika player yang mengambil batang terakhir, maka pemain akan kalah, tapi jika AI yang mengambil batang terakhir maka AI akan kalah. Namun disini AI sangat sulit dikalahkan. Kita bisa mengambil berapapun batang yamg kita inginkan tapi harus berada dalam satu kolom, begitu juga computer.

Rules

Identifikasi ruang keadaan, permasalahan ini dapat di lambangkan dengan sebuah field dengan background sebuah gambar, di field itu terdapat 5 tingkatan yang terdiri dari ikon-ikon yang tersusun berbentuk piramida. Pemain hanya terdiri dari player dan AI (CPU).

Keadaan awal dan tujuan.

Keadaan awal = papan  permainan.

Keadaan tujuan = bagi yang terakhir meng-klik ikon, dialah yang kalah.

Aturan-aturan:

1.      Pilihan bagian option, disitu kita akan memilih siapa yang akan maju terlebih dahulu, player atau AI.

2.      Dimainkan dengan 2 pemain, player pertama dan yang kedua adalah AI, player memulai langkah awal permainan dengan memilih salah satu ikon yang telah disediakan. Baik dari atas atau dari bawah.

3.      Kita hanya bisa mengambil ikon secara kolom, yang terakhir memilih adalah yang kalah.

4.      Tidak ada perbedaan ikon antara player dengan CPU.

Konsep AI

Konsep permainan yang di pakai dalam permainan ini adalah (baik user ataupun AI) harus berjalan secara bergantian. AI akan selalu berjalan dan memberikan perlawanan kepada kita sehingga tidak akan begitu mudah dapat memenangkan game tersebut, pada saat memainkan permainan ini akan mendapatkan hasil akhir berupa kita menang atau kita kalah melawan komputer, karena prinsipnya game ini ingin anda yang kalah. Kesimpulan dari permainan ini ialah bagaimana cara untuk memenangkan perlawanan dari komputer dengan tidak mengambil korek api yang paling akhir (don’t take the last), jika pengguna (user) dapat tidak mengambil korek api yang terakhir maka pengguna tersebut ememnangkan permainan game Matches dan jika pengguna (user) mengambil korek api yang paling akhir maka pengguna (user) tersebut dinyatakan kalah dalam permainan game Matches ini.

Algoritma yang dipakai

Berikut ini adalah algoritma yang dipakai dalam permainan ini :

1.      Memilih salah satu beberapa dari 25 ikon yang susunannya berbentuk segitiga. ikon yang telah di sediakan, pengguna (user) atau lawan (komputer) dapat memilih sesuai dengan yang di inginkan.

2.      Jika 25 ikon telah di pilih secara bergantian.

3.      Dengan cara mengklik kiri pada mouse dan arahkan kursor kearah pensil yang ingin di ambil.

4.      Jika pengguna (user) bermain sebagai pemain (player) pertama dan sudah memilih pensil yang di inginkan untuk di ambil, maka berikutnya lawan (komputer) yang memilih pensil yang di inginkan untuk diambil.

5.      Jika ikon yang di sediakan telah habis maka akan dilihat siapa yang mengambil ikon yang paling akhir untuk menentukan menang atau tidaknya pengguna (user) ataupun lawan (komputer) karena syarat ketentuan permainan ini ialah akan menang jika tidak mengambil ikon yang paling akhir dan akan kalah jika mengambil ikon yang paling akhir.

6.      Jika pengguna (user) bermain cepat dalam pengambilan ikon maka lawan (komputer) akan menyamakan kecepatan seperti pengguna (user) dalam proses pengambilan ikon.

7.      Jika lawan (komputer) memenangkan permainan ini maka keluar message "Anda kalah!!" Jika pengguna (user)yang memenangkan permainan ini maka akan keluar message “Akhirnya anda menang juga!!".

8.      Permainan selesai bila 25 ikon telah habis baik diambil pengguna (user) ataupun lawan (komputer). Dan akan menampilkan message menang atau tidaknya dalam permainan ini.

Dalam Game matches ini menggunakan Algoritma Backtracking menggunakan konsep DFS dalam pembentukan pohon solusi.

1.      Pohon solusi dibentuk dari awal permainan sampai akhir permainan.

2.      Untuk permainan yang di nyatakan cukup kompleks seperti permainan Matches, pembentukan pohon solusi di mulai dari awal permainan sampai akhir permainan dapat direalisasikan karena pada game ini mempunyai batasannya, yaitu kotak yang telah di batasin berapa banyak yang dapat di beri tanda, sehingga bila anda ingin mengurutnya bisa di lakukan dan di ketahui cara untuk memenangkan game ini. Sehingga bila anda cari dalam pohon solusi bisa di selesaikan sampai tidak ada kemungkinan lagi untuk di cari solusinya.

3.      Semakin akurat fungsi heuristic yang digunakan, semakin baik pula pengambilan keputusan yang dilakukan oleh AI.

5.  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 Permainan

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 yang digunakan

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