1. Catur
Catur adalah game strategi peperangan pikiran yang dimainkan oleh 2 orang. Ibarat peperangan, kita harus menaklukan seorang raja agar menang, begitu juga dengan catur. Kata catur diambil dari bahasa Sanskerta yang berarti "empat". Namun kata ini sebenarnya merupakan singkatan dari caturangga yang berarti empat sudut. Terdapat 2 warna yang berbeda dalam pertandingan ini, warna yang biasa digunakan dalam permainan catur adalah warna hitam dan putih. Permainan dilakukan diatas papan 8x8 atau dengan banyak petak 64 buah. Biji catur biasa disebut bidak. Dan setiap bidak catur memiliki langkah yang berbeda tergantung jenisnya.
Setiap bidak catur memiliki gerakan yang unik sebagai berikut:
- Raja dapat bergerak satu petak ke segala arah. Raja juga memiliki gerakan khusus yang disebut rokade yang turut melibatkan sebuah benteng.
- Benteng dapat bergerak sepanjang petak horizontal maupun vertikal, tetapi tidak dapat melompati bidak lain. Seperti yang telah disebutkan di atas, benteng terlibat dalam gerakan rokade.
- Peluncur dapat bergerak sepanjang petak secara diagonal, tetapi tidak dapat melompati bidak lain.
- Ratu memiliki gerakan kombinasi dari Benteng dan Gajah.
- Kuda memiliki gerakan mirip huruf L, yaitu memanjang dua petak dan melebar satu petak. Kudalah satu-satunya bidak yang dapat melompati bidak-bidak lain.
- Pion dapat bergerak maju (arah lawan) satu petak ke petak yang tidak ditempati. Pada gerakan awal, pion dapat bergerak maju dua petak. Pion juga dapat menangkap bidak lawan secara diagonal, apabila bidak lawan tersebut berada satu petak di diagonal depannya. Pion memiliki dua gerakah khusus, yaitu gerakan menangkap en passant dan promosi.
Dalam perkembangan jaman, permainan catur sudah masuk ke dalam digital. Dan dalam pembuatannya digunakan algoritma minimax dan algoritma negamax.
I. Algoritma Minimax
Merupakan basis dari semua permainan berbasis AI seperti permainan catur misalnya. AI permainan catur tentunya sudah sangat terkenal dimana AI tersebut bahkan dapat mengalahkan juara dunia sekalipun.
Pada algoritma minimax, pengecekan akan seluruh kemungkinan yang ada sampai akhir permainan dilakukan. Pengecekan tersebut akan menghasilkan pohon
permainan yang berisi semua kemungkinan tersebut. Tentunya dibutuhkan resource yang berskala besar untuk menangani komputasi pencarian pohon solusi tersebut berhubung kombinasi kemungkinan untuk sebuah permainan catur pada setiap geraknya sangat banyak sekali. Keuntungan yang didapat dengan menggunakan algoritma minimax yaitu algoritma minimax mampu menganalisis segala kemungkinan posisi permainan untuk menghasilkan keputusan yang terbaik karena algoritma minimax ini bekerja secara rekursif dengan mencari langkah yang akan membuat lawan mengalami kerugian minimum. Semua strategi lawan akan dihitung dengan algoritma yang sama dan seterusnya. Ini berarti, pada langkah pertama komputer akan menganalisis seluruh pohon permainan. Dan untuk setiap langkahnya, komputer akan memilih langkah yang paling membuat lawan mendapatkan keuntungan minimum, dan yang paling membuat komputer itu sendiri mendapatkan keuntungan maksimum.
Dalam penentuan keputusan tersebut dibutuhkan suatu nilai yang merepresentasikan kerugian atau keuntungan yang akan diperoleh jika langkah tersebut dipilih. Untuk itulah disini digunakan sebuah fungsi heurisitic untuk mengevaluasi nilai sebagai nilai yang merepresentasikan hasil permainan yang akan terjadi jika langkah tersebut dipilih. Biasanya pada permainan tic tac toe ini digunakan nilai 1,0,-1 untuk mewakilkan hasil akhir permainan berupa menang, seri, dan kalah. Dari nilai-nilai heuristic inilah komputer akan menentukan simpul mana dari pohon permainan yang akan dipilih, tentunya simpul yang akan dipilih tersebut adalah simpul dengan nilai heuristic yang akan menuntun permainan ke hasil akhir yang menguntungkan bagi komputer.
II.Algoritma 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,
Dasar dari algoritma ini adalah bahwa chess tree search 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 pemain yang akan berjalan, hal ini dilakukan dengan melakukan negasi terhadap nilai yang dilihat oleh lawan ini disebut dengan proses negamax.
2. Patty-patty
Game “Patty-Patty” menggunakan kecerdasan buatan (AI). Permainan ini melatih ketepatan player untuk menembakkan batu ke obyek dengan terbatasnya waktu.
Permainan ini terinspirasi dari permainan “Cat&Dog“ (Game Android). Bedanya, pada permainan ini targetnya adalah obyek yang kita buat, bukan AInya.
Jendela awal berisi 3 menu, yaitu Start Game, How To Play, dan Exit. Player akan melempar batu sesuai giliran, demikian sebaliknya sesuai waktu dan level. Permainan ini akan dimulai dengan latihan, ketika Player menentukan level terdapat dari 1 sampai 3. Durasi permainan adalah 100detik(level 1), 60detik(level 2), 30 detik(level 3).
Jendela permainan
Aturan Main
•Waktu permainan dari 100detik(level 1), 60detik(level 2), 30 detik(level 3).
•Terdapat 3 level yaitu 1, 2, 3.
•Cukup klik kiri pada mouse untuk menembak.
•Sesuai waktu yang ditentukan, bila giliran sudah habis langsung bergantian menyerang.
•Permainan berakhir bila semua target dikenai.
•Pada detik 0 permainan akan berakhir.
Algoritma
Konsep AI yang ada pada game ini adalah menggunakan Algoritma Greedy, dimana AI akan mencoba terus menerus tanpa mengulangi koordinat/rute/jalan yang sudah dilakukan. Game “Patty-Patty” ini menggunakan algoritma yang paling sering digunakan dalam mencari solusi yang optimasi. Algoritma ini berusaha mengambil keputusan terbaik yang dapat dilakukan dari semua langkah penyelesaian yang ada.
3.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 menu Options. 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.
4. Be a Smart Cloud
Pada game Be a Smart Cloud ini menggunakan algoritma minimax. Algoritma minimax merupakan basis dari semua permainan berbasis AI seperti permainan catur, go, othello, checkers, bridge, tic-tac-toe dan lain sebagainya. AI dalam permainan awal yaitu tic tac toe yang merupakan game komputer diangkat dari game tradisional yang diciptakan oleh A.S Douglas pada Tahun 1952 di Universitas Cambridge sebagai salah satu sistem interaksi manusia dengan komputer. Dalam penggunaan AI di permainan ini kita dapat membuat perintah untuk dapat mengatasi permainan dengan baik. Permainan Tic Tac Toe merupakan salah satu permainan yang terkenal hingga seluruh dunia. Hal ini dikarenakan kemampuannya yang memiliki daya tarik sendiri bagi setiap lapisan masyarakat untuk memainkannya. Permainan ini juga memiliki panggilan yang berbeda di setiap daerahnya, seperti : tit-tat-toe,Naughts and crosses,Exy-Ozys,Xsie-Osies,serta X’s and O’s. Tic Tac Toe merupakan suatu permainan yang terdiri dari 9 kotak kosong atau berbentuk grid 3x3,4x4 bahkan lebih yang dimainkan oleh dua orang pemain yang bermain dengan hanya menggunakan “Gambar Cloud” (user) dan “Gambar Valentine” (komputer) sebagai modal untuk mendapatkan satu barisan.
Jika sudah tidak ada lagi jumlah kotak yang kosong, namun belum ada pihak yang berhasil membuat garis, berarti permainan dinyatakan draw atau seri. Game ini di program dengan menggunakan teknik AI (Artificial Inteligince) dan Algoritma Minimax. Algoritma Minimax bekerja secara rekursif dengan mencari langkah untuk membuat lawan mengalami kerugian sehingga mampu menganalisis segala kemungkinan posisi setiap permainan untuk mendapatkan hasil keputusan yang tepat dan terbaik. Pada pengecekan yang dilakukan, akan menghasilkan pohon permainan yang berisi semua kemungkinan tersebut dan dibutuhkan resource berskala besar untuk menangani komputasi pencarian pohon. Sehingga bertujuan untuk meminimalisasi peluang rugi terhadap permainan. Ada beberapa tahapan yang perlu diketahui, seperti : • Manusia akan selalu mendapat giliran pertama di dalam game ini dan giliran selanjutnya adalah AI. • Manusia menggunakan Gambar Cloud dan AI menggunakan Gambar Valentine. • Jika Gambar Cloud (manusia) telah sejajar dan AI mengambil giliran, maka otomatis AI akan menutup jalan Symbol agar Gambar Cloud tidak membuat 1 garis. • Jika Gambar Cloud tidak sejajar, giliran AI untuk mengatur strategi untuk menang yaitu dengan menempatkan Gambar Valentine agar sejajar dengan Simbol O lainnya. Namun dalam langkah tersebut, untuk penentuan keputusannya dibutuhkan suatu nilai yang merepresentasikan kerugian atau keuntungan yang akan diperoleh.
Untuk itulah disini digunakan sebuah fungsi heurisitic yang berguna mengevaluasi nilai untuk merepresentasikan hasil permainan yang akan terjadi jika langkah tersebut dipilih. Biasanya pada permainan tic tac toe ini digunakan nilai 1,0,-1 untuk mewakilkan hasil akhir permainan berupa menang, seri, dan kalah. Dari nilai-nilai heuristic inilah komputer akan menentukan simpul mana dari pohon permainan yang akan dipilih, tentunya simpul yang akan dipilih tersebut adalah simpul dengan nilai heuristic yang akan menuntun permainan ke hasil akhir yang menguntungkan bagi komputer. Game ini tidak memiliki aturan khusus. Aturan game ini hanya membebaskan para pemain untuk memilih dan menandai satu simbol di kotak manapun secara bergantian. Permainan dimulai dengan giliran pertama ada pada pemain (manusia). Apabila terdapat gambar lawan atau gambar valentine menghasilkan sebuah garis yang terbentuk dari minimal 4 simbol baik secara horizontal, vertical ataupun diagonal seperti pada goal, maka pemain akan berakhir dan pemenangnya adalah yang berhasil membentuk garis tersebut. Jika sudah tidak ada lagi jumlah kotak yang kosong, namun belum ada pihak yang berhasil membuat garis, berarti permainan dinyatakan draw atau seri.
GOALS
Permainan ini dapat ditandai dengan pemberian gambar Cloud untuk player dan gambarValentine untuk AI. Pada permainan ini setiap pemain, baik player maupun AI saling berlomba untuk membuat sebuah garis dengan gambar masing – masing supaya dapat memenangkan permainan ini.
Goal menang dan kalah untuk menyelesaikan permainan Be a Smart Cloud adalah:1. Kondisi menang: Jika gambar Cloud atau gambar Valentine memenuhi 1 garis penuh (horizontal/vertikal maupun diagonal) maka dianggap menang dan AI kalah.
2. Kondisi kalah: Jika pemain (User) tidak dapat memenuhi gambar Cloud 1 garis penuh maka dianggap kalah dan AI menang.
RULES
1. User pertama kali meletakkan gambar Cloud di kolom/baris yang dimanapun yang tersedia.
2. Kemudian selanjutnya AI meletakkan gambar Valentine di kolom/baris dimanapun yang tersedia.
3. Dari user dan AI sama-sama menghadang langkah agar masing – masing tidak dapat menang.
4. User maupun AI harus mengikuti langkah-langkah peletakan gambar Cloud dan gambar Valentine sesuai garis horizontal/vertikal maupun diagonal.
3. Dari user dan AI sama-sama menghadang langkah agar masing – masing tidak dapat menang.
4. User maupun AI harus mengikuti langkah-langkah peletakan gambar Cloud dan gambar Valentine sesuai garis horizontal/vertikal maupun diagonal.
KONSEP AI
AI pada game Be a Smart Cloud ini menggunakan algoritma minimax. Pada algoritma minimax, pengecekan akan seluruh kemungkinan yang ada sampai akhir permainan dilakukan. Pengecekan tersebut akan menghasilkan pohon permainan yang berisi semua kemungkinan tersebut. Tentunya dibutuhkan resource yang berskala besar untuk menangani komputasi pencarian pohon solusi tersebut berhubung kombinasi kemungkinan untuk sebuah permainan pada setiap geraknya sangat banyak sekali. Keuntungan yang didapat dengan menggunakan algoritma minimax yaitu algoritma minimax mampu menganalisis segala kemungkinan posisi permainan untuk menghasilkan keputusan yang terbaik karena algoritma minimax ini bekerja secara rekursif dengan mencari langkah yang akan membuat lawan mengalami kerugian minimum.
Semua strategi lawan akan dihitung dengan algoritma yang sama dan seterusnya. Ini berarti, pada langkah pertama komputer akan menganalisis seluruh pohon permainan.Dan untuk setiap langkahnya, komputer akan memilih langkah yang paling membuat lawan mendapatkan keuntungan minimum, dan yang paling membuat komputer itu sendiri mendapatkan keuntungan maksimum.
Dalam penentuan keputusan tersebut dibutuhkan suatu nilai yang merepresentasikan kerugian atau keuntungan yang akan diperoleh jika langkah tersebut dipilih. Untuk itulahdisini digunakan sebuah fungsi heurisitic untuk mengevaluasi nilai sebagai nilai yang merepresentasikan hasil permainan yang akan terjadi jika langkahtersebut dipilih. Biasanya pada permainan tic tac toe digunakan nilai 1,0,1 untuk mewakilihasil akhir permainan berupa menang, seri, dan kalah.
Dari nilai - nilai heuristic inilah komputer akan menentukan simpul mana dari pohon permainan yang akan dipilih, tentunya simpul yang akan dipilih tersebut adalah simpul dengan nilai heuristic yang akan menuntun permainan ke hasil akhir yang menguntungkan bagi komputer.
Di setiap tahap algoritma ini mengasumsikan bahwa pemain A mencoba untuk memaksimalisasi peluang menang. Di lain pihak, pada giliran berikutnya pemain B akan mencoba meminimalisir peluang menang untuk pemain A. Oleh karena itu, A disebut juga maximizing player ( MAX ) dan B disebut juga minimizing player ( MIN ).
Representasi pohon pencarian pada algoritma minimax
Pembentukan pohon pencarian solusi digunakan dengan menggunakan konsep depth - first search, dimulai dari awal permainan sampai akhir permainan. Proses yang dilakukan bergantian yaitu mencari nilai minimum, kemudian pada node - parent dilakukan pencarian untuk nilai maksimum. Setelah itu nilai dari setiap simpul diisi dari bawah ke atas dengan nilai yang sudah dievaluasi oleh fungsi heuristic. Simpul milik pemain A ( MAX ) menerima nilai maksimum dari simpul-simpul anaknya. Simpul milik pemain B ( MIN ) akan memilih nilai minimum dari simpul anak - anaknya. Values disini merepresentasikan suatu langkah terbaik dalam permainan ini. Jadi, pemain A ( MAX ) akan memilih langkah dengan nilai paling tinggi diakhir. Di sisi lain, pemain B ( MIN ) akan melakukan serangan balik dengan memilih langkah yang terbaik untuknya, yakni meminimalisir hasil dari langkah yang dipilih pemain A.
5. PAC-MAN
Pac-Man adalah video game favorit pada era 90an. Dalam permainan ini kita sebagai Pac-Man menelusuri labirin menngumpulkan titik kuning hingga semua didapatkan namun harus menghindari 4hantu warna-warni yang disebut Ghost, yang masing-masing bernama Blinky, Pinky, Inky, dan Clyde, yang akan terus bergerak mengejar Pac-Man.
Permainan berganti level jika “Pac-Dots” telah habis dikumpulkan. Jika salah satu dari mereka menyentuh Pac-Man, maka Pac-Man akan kehilangan nyawa, dan permainan di level itu dimulai kembali.
Permainan diulang kembali sampai semua nyawa PacMan terpakai, dan setelah itu permainan mencapai tahap Game Over. Terdapat pula “titik-titik” yang lebih besar dari “PacDots” yang disebut “Power Pellets”, yang jika dimakan akan membuat Pac-Man mampu membalikkan keadaan untuk sementara waktu dan mengejar para Ghost. Jika Pac-Man menyentuh Ghost, Ghost akan hilang termakan dan Pac-Man akan mendapat poin tambahan.Permainan berganti level jika “Pac-Dots” telah habis dikumpulkan. Jika salah satu dari mereka menyentuh Pac-Man, maka Pac-Man akan kehilangan nyawa, dan permainan di level itu dimulai kembali.
Dari penjabaran diatas, diketahui bahwa pergerakan Ghost ada 2, yakni pergerakan saat mengejar Pac-Man, dan pergerakan saat menjauhi Pac-Man. Dalam bergerak, setiap Ghost mempunyai algoritma sendiri karena setiap
Ghost memang didesain dengan kepribadian masingmasing. Setiap Ghost mengejar Pac-Man dengan cara yang berbeda. Akan tetapi, algoritma DFS dapat diimplementasikan untuk membuat pergerakan Ghost lebih menarik. Dengan BFS, Ghost mencari solusi jalur mana yang merupakan jalur terbaik untuk mendekati PacMan, atau pun jalur terbaik untuk menjauhi Pac-Man.
Algoritma DFS adalah algoritma untuk mentranversalkan pohon, struktur pohon, atau graf.
Dimulai dari akar, pencarian dilakukan sejauh mungkin sebelum dilakukan “backtracking”, kecuali dengan aturanaturan tertentu. Algoritma DFS banyak digunakan untuk penyelesaian masalah-masalah yang berhubungan dengan labirin.
Depth-First-Search
Sumber : http://en.wikipedia.org/wiki/Depth-first_search
Semua karakter di permainan Pac-Man, yakni Pac-Man itu sendiri, dan juga semua Ghost, bergerak dalam sebuah labirin. Karena itulah, algoritma DFS merupakan algoritma yang tepat untuk diimplementasikan pada pergerakan Ghost, atau pun pada pergerakan Pac-Man jika ada Pac-Man ingin digerakkan secara otomatis secara lebih menarik.
Referensi:
1. https://id.wikipedia.org/wiki/Catur
http://achielmuezza.blogspot.co.id/2013/04/membuat-game-catur-pion-queen-dengan.html
2. Edo, Twin. 2015. "Patty-Patty" Praktikum Pengantar Kecerdasan Buatan Jenjang S1
3.http://aryahasa05.blogspot.co.id/2015/06/algoritma-game-2d-dan-3d-peng-teknologi.html
4. https://ilhamug.blogspot.co.id/2015/08/game-be-smart-cloud-menggunakan.html?showComment=1462788125774#c3547222838220288593
5. Ardhin, Muhammad. 2011. Implementasi Algoritma DFS untuk Pergerakan Ghost di Permainan Pac Man.
