1. CATUR
Catur adalah permainan pikiran yang dimainkan
oleh dua orang. Pecatur adalah orang yang memainkan catur,
baik dalam pertandingan satu lawan satu maupun satu melawan banyak orang (dalam
keadaan informal). Sebelum bertanding, pecatur memilih biji catur yang akan ia
mainkan. Terdapat dua warna yang membedakan bidak atau biji catur, yaitu hitam dan putih. Pemegang buah putih memulai
langkah pertama, yang selanjutnya diikuti oleh pemegang buah hitam secara
bergantian sampai permainan selesai.
Kata catur diambil dari bahasa Sanskerta yang berarti
"empat". Namun kata ini sebenarnya merupakan singkatan dari caturangga yang
berarti empat sudut. DiIndia kuno permainan
catur memang dimainkan oleh empat peserta yang berada di empat sudut yang
berbeda. Hal ini lain dari permain catur modern di mana pesertanya hanya dua orang saja.
Pengaturan
Permainan dilangsungkan di atas papan yang terdiri dari 8 lajur
dan 8 baris kotak/petak berwarna hitam dan putih (atau terang dan gelap) secara
berselang seling. Permainan dimulai dengan 16 buah pada masing-masing pihak,
yang disusun berbaris secara khusus pada masing-masing sisi papan catur secara
berhadap-hadapan. Satu buah hanya bisa menempati satu petak. Pada bagian
terdepan masing-masing barisan - terdapat 8 pion, diikuti di belakangnya duabenteng, dua kuda (dalam bahasa Inggris disebut knight-ksatria), dua gajah (dalam bahasa Inggris disebut bishop-uskup),
satu menteri atau ratu atau ster, serta
satu raja.
Gerakan
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. Setiap langkah hanya boleh
menggerakkan satu bidak saja (kecuali untuk rokade di mana ada dua bidak yang
digerakkan). Bidak dipindahkan ke petak kosong, ataupun yang ditempati oleh
bidak lawan, yang berarti menangkapnya dan memindahkan bidak lawan dari
permainan. Ada pengecualian, yaitu untuk gerakan en passant.
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 di atas, benteng terlibat dalam gerakan rokade.
·
Gajah 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.
Rokade
Rokade (dalam bahasa
Inggris, castling)
merupakan gerakan khusus dalam catur di mana Raja bergerak dua petakmenuju
Benteng di baris pertamanya, kemudian meletakkan Benteng pada petak terakhir
yang dilalui Raja. Persyaratan rokade adalah sebagai berikut:
·
Bidak Raja dan Benteng
yang akan dilibatkan dalam rokade harus belum pernah bergerak
·
Tidak ada bidak lain
di antara Raja dan Benteng
·
Raja tidak sedang
di-skak, dan petak-petak yang dilalui Raja tidak sedang diserang oleh
bidak lawan
Hal-hal berikut ini merupakan kesalah pengertian dalam rokade,
yang semestinya tidak berlaku:
·
Bidak benteng yang
terlibat rokade sedang diserang
·
Jika benteng yang
dilibatkan berada di sisi Ratu, petak yang berada persis di samping Benteng
tersebut tidak boleh dalam serangan
En passant
Contoh gerakan pion: promosi (kiri) dan en
passant (kanan)
Ketika pion bergerak dua petak maju dan ada pion lawan yang
berada satu petak dalam baris tujuan, maka pion lawan dapat menangkap dan
menempati petak yang baru saja dilalui pion tersebut (seolah-olah pion tersebut
bergerak satu petak maju). Namun demikian, gerakan ini hanya dapat dilakukan
sesaat setelah gerakan pion maju dua petak, atau hak lawan untuk melakukan
gerakan en passant ini hilang.
Promosi
Ketika pion telah maju hingga menempati baris paling akhir,
berbarengan dengan gerakan maju tersebut, pion dipromosikan dan harus
ditukar dengan bidak berdasarkan keinginan pemain, yaitu Ratu, Benteng, Gajah,
ataupun Kuda dengan warna yang sama. Pada umumnya, pion dipromosikan menjadi
Ratu. Tidak ada peraturan yang membatasi bidak yang dipilih sebagai promosi,
jadi dimungkinkan memiliki bidak yang melebihi jumlahnya waktu awal permainan
(semisal, dua Ratu).
Skak
Ketika Raja sedang diserang oleh satu atau lebih bidak lawan,
keadaan ini disebut dengan skak. Pemain yang Rajanya diskak harus
menggerakkan Rajanya supaya tidak terserang. Hal ini dapat dilakukan dengan
menangkap bidak lawan yang menyerang, menutup serangan lawan
dengan menempatkan sebuah bidak di antaranya (apabila yang menyerang Ratu,
Benteng, atau Gajah dan ada petak kosong di antara Raja dan bidak lawan), atau
memindahkan Raja ke petak yang tidak sedang diserang. Rokade tidak diijinkan
apabila Raja sedang diskak.
Akhir
Permainan
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.
Garry Kasparov (Га́рри Ки́мович
Каспа́ров)(lahir 13 April 1963;
umur 51 tahun) adalah grandmaster pecaturutama
dunia dan mungkin manusia paling tangguh dalam bermain catur. Ia memiliki ELO rating tertinggi dengan nilai 2804
setelah sebelumnya sempat mencapai 2851 pada tahun 1991. Dia mengumumkan
pengunduran dirinya dari dunia catur pada 10 Maret 2005.
Awal
kehidupan dan karier sebagai pecatur
Garry Kasparov lahir dengan nama Gari
Weinstein di Baku, Azerbaijan dengan orang tua
keturunan Armenia-Yahudi. Ia mulai serius mempelajari catur sejak usia dini.
Saat usia 12 tahun, ayahnya meninggal, dan sejak saat itu ia mulai menggunakan
nama keluarga ibunya. Ibunya, Klara adalah seorang wanita Armenia dengan nama keluarga Kasparian,
yang dalam dialek Rusia disebut sebagai "Kasparov".
Garry Kasparov menjadi terkenal di dunia
catur saat menyandang gelar grandmaster termuda di dunia pada jamannya.
Debutnya dimulai pada tahun 1984 saat menantang juara dunia saat itu Anatoly Karpov dalam pertandingan catur
paling kontroversial sepanjang sejarah. Saat mulai bertanding, Kasparov sempat
tertinggal 5-0 dalam sebuah turnamen di mana pemenang yang terlebih dahulu
mencapai angka 6 dinobatkan sebagai juara. Dalam pertandingan catur, satu kemenangan
diberi nilai 1 sementara seri atau remis dan
kalah tidak memperoleh nilai.
Pertandingan Catur Dunia tahun 1984 ini
menjadi menarik, karena sekalipun sempat tertinggal, Kasparov berhasil
mendekati Karpov setelah melewati tujuh belas kali remis. Beberapa pertandingan
selanjutnya, Kasparov memenangi tiga pertandingan sehingga kedudukan menjadi
5-3 untuk keunggulan sementara di pihak Karpov. Pertandingan selanjutnya
dihentikan oleh ketua FIDE saat itu, Florencio
Campomanes dengan alasan stamina kedua pemain telah sangat
menurun. Karpov sendiri sempat harus dirawat di rumah sakit. Pertandingan
dilanjutkan beberapa bulan kemudian.
Pada pertandingan putaran kedua antara
Karpov-Kasparov pada tahun 1985, diberlakukan standar baru di mana pemain yang
terlebih dahulu mencapai angka 12.5 atau lebih dalam 24 pertandingan akan
dinyatakan sebagai pemenang. Bila pertandingan berakhir dengan draw 12-12 maka
gelar juara dunia akan tetap dipegang oleh Karpov sebagai juara bertahan.
Kasparov memenangkan pertandingan putaran kedua ini dengan mengalahkan Karpov,
dan selanjutnya dinobatkan sebagai juara catur termuda di dunia pada usia 22
tahun. Rekor juara catur termuda sebelumnya dipegang oleh Mikhail Tal saat ia mengalahkan
Bothvinnik pada tahun 1960.
Setelah berhasil mengantongi gelar Juara
Dunia, Kasparov selanjutnya berselisih dengan FIDE. Ia mendirikan sebuah
organisasi serikat pecatur dunia dengan nama GrandMaster's Association (GMA),
yang mewakili suara para pecatur dalam aktivitas di dalam FIDE.
Dipecat
dari FIDE dan karier politik
Masalah Kasparov dengan FIDE berlangsung
hingga tahun 1993, di mana penantang baru telah dipersiapkan oleh FIDE untuk
menghadapi Kasparov Kejuaraan Dunia berikutnya. Kejadian menjadi sulit, karena
baik Kasparov maupun Nigel
Short sebagai juara dan penantang, sepakat untuk mengadakan
pertandiangan mereka di luar FIDE, yaitu di bawah naungan organisasi catur baru
yang didirikan Kasparov bernama Professional Chess Association (PCA).
Sebagai akibatnya, baik Kasparov maupun Short dikeluarkan dari keanggotaan
FIDE. Pertandingan antara Kasparov dan Nigel Short yang berlangsung di London,
dimenangkan oleh Kasparov.
Sebagai ganti Kasparov dan Short, FIDE
menggelar pertandingan final "Kejuaraan Dunia" yang dilangsungkan
antara Jan
Timman dan juara dunia sebelumnya, Karpov. Pertandingan ini
dimenangkan oleh Karpov. Sebagai hasilnya, pada saat itu terdapat dua juara
dunia, yaitu Kasparov di bawah organisasi PCA, dan Karpov di bawah organisasi
FIDE.
Pada tahun 1995, Kasparov mempertahankan
gelar juara dunianya dengan mengalahkan juara catur asal India, Viswanathan Anand.
Setelah pensiun pada tahun 2005, Kasparov
terjun ke dunia politik dan mendirikan Front Sipil Bersatu, sebuah gerakan
sosial yang bertujuan mencegah Rusia kembali ke totalitarianisme. [1]
Kasparov pernah beberapa kali bermain
melawan komputer, pada 1996 dan 1997.
Pada 1996, Kasparov berhasil mengalahkan komputer Deep Blue dengan hasil 4-2, namun
pada pertandingan berikutnya pada 1997, Deep
Blue yang sudah dimutakhirkan berhasil mengalahkan Kasparov dengan
nilai 3,5-2,5.
Pada January 2003 Kasparov melakukan
pertandingan dengan sistem 6 babak melawan komputer Deep Junior dengan hadiah $
1 juta.
Pertandingan ini disebut sebagai pertandingan "Man vs Machine". Deep
Junior mampu mengkalkulasi langkah hingga 3 juta posisi per detik. Setelah
bermain dengan 3 kali seri dan 1 kali menang. Kasparov menawarkan permintaan
draw kepada mesin DeepJunior yang langsung diterima oleh tim DeepJunior. Saat
ditanya mengapa Kasparov menawarkan draw, Kasparov berkata bahwa dia melakukan
kesalahan pada permainannya.
Pada November 2003,
Kasparov juga bermain dengan program X3D
Fritz menggunakan papan virtual, kacamata 3D dan sistem
pengenalan suara. Kasparov memperoleh hadiah sebesar $ 175.000 setelah berhasil
memenangkan pertandingan itu dengan hasil 2 kali menang, 1 kali kalah dan 2
kali seri.
Permainan catur pertama ditanamkan pada
sebuah komputer yang dinamai Deep Blue, yang dibuat oleh IBM. Bahkan komputer tersebut
mampu mengalahkan seorang juara dunia bernama Garry Kasparov pada tanggal 10
Februari 1996 dalam waktu standar sebuah turnamen catur. Pertanyaannya adalah,
bagaimana bisa kecerdasan buatan pada komputer tersebut dapat mengalahkan
seorang juara dunia???
Rahasianya adalah pada algoritma yang
ditanamkan pada sistem permainan catur tersebut. Algoritma yang ditanamkan pada
permainan catur ini adalah jenis pohon n-ary (Tree Search) yang dibentuk
menjadi suatu struktur. Algoritma ini termasuk dalam algoritma inti yang banyak
digunakan dalam banyak permainan.
Dalam permainan catur ini Tree Search
melihat semua kemungkinan yang ada dalam permainan layaknya sebuah pohon,
dengan langkah legal dalam permainan tersebut sebagai sebuah akar. Sedangkan
langkah atau posisi terakhir dari permainan diibaratkan sebagai daun, di mana
hasil dari permainan sudah dapat diketahui. Masalah yang dihadapi dalam
menyusun sebuah algoritma permainan ini adalah ukuran dari pohon permainan ini
sangatlah besar, dapat dirumuskan sebagai W^D, dimana 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 tersebut pada umumnya digambarkan pada bahasa C. Untuk meringkas
algoritma yang ukurannya sangat besar tersebut, digunakanlah NegaMax, yakni
sebuah struktur fundamental yang menjadi dasar bagi setiap algoritma pencarian
terhadap Chess Tree. Implementasinya adalah, jika langkah yang dilakukan lawan
maka langkah yang kita lakukan semakin baik. Tapi itu saja masih belum cukup
untuk menentukan langkah yang sangat banyak, sehingga digunakan juga Alpha-Beta
Search yang bertujuan untuk melakukan pengurangan secara besar-besaran
langkah-langkah yang kurang diperlukan, yang dengan kata lain, tekhnik ini
mengurangi ukuran pohon pencarian (Tree Search).
Teknik inilah yang kini digunakan sebagai
dasar pembuatan permainan catur. Ternyata permainan yang terlihat sederhana ini
memiliki kemampuan yang luar biasa dalam menganalisis suatu keadaan karena
adanya Artificial Intellegence berupa soft computing yang ada di dalam
sistemnya.
(
sumber:
http://ardan-l-r-fst08.web.unair.ac.id/artikel_detail-59180-Komputer%20Cerdas%20-AI%20dalam%20permainan%20catur.html
)
2. LUDO
Ludo
adalah sebuah permainan papan yang dimainkan hampir seluruh belahan dunia.
Permainan ini dimenagnkan dengan memindahkan pion-pion yang kita miliki menuju
kotak tujuan. Berbagai taktik dapat digunakan untuk mencapai tujuan tersebut.
Dengan algoritma greedy kita dapat membuat berbagai taktik untuk dapat
memenangkan permainan ini. Pada artikel ini akan dibahas berbagai taktik greedy
yang dapat digunakan untuk memainkan permainan.
ada permainan Ludo terdapat beberapa
algoritma greedy yang dapat digunakan, diantaranya :
1. Greedy By No One Left Behind
Algoritma ini akan berusaha untuk
menggerakkan semua pion menuju titik tujuan bersama – sama. Semua langkah yang
dapat diambil digunakan untuk menggerakan semua pion agar semakin dekat dengan
tujuan dengan memilih pion dengan prioritas tertinggi yaitu pion yang berada
paling belakang.
2. Greedy By Hitter
Algoritma ini berusaha untuk menggerakan pion
agar dapat memukul pion lawan. Pemilihan pion yang digerakkan berdasarkan
prioritas posisi pion. Pion yang berada lebih dekat dengan pion lawan, maka
pion tersebut yang akan digerakkan.
3. Greedy By Quick Move
Algoritma ini berusaha untuk menggerakkan
pion secepat mungkin menuju tujuan. Pergerakkan pion didasarkan pada pion
dengan prioritas tertinggi, yaitu pion yang berada paling dekat dengan tujuan.
3. Tic Tac Toe
Tic
Tac Toe merupakan jenis game yang pengimplementasian minimax-nya sedikit lebih
"mudah" kalau dibandingkan dengan game AI yang lain. Tic Tac Toe
dapat dibuat dengan engine Strawberry Prolog
Minimax merupakan algoritma AI yang sering
digunakan untuk membuat AI jenis decision. Tugas dari minimax adalah memetakan
seluruh kemungkinan permainan dimana masing-masing hasil akhir permainan punya
nilai Heuristik. Tujuan dari minimax adalah memilih peluang terkecil agent
kalah atau memilih peluang terbesar agar agent bisa menang.
Pada program kali ini, minimax saya
implementasikan di javascript. Tujuannya biar ringan eksekusinya.
(sumber: http://haqiphoenix.blogspot.com/2012/04/membuat-tic-tac-toe-ai-dengan-algoritma.html
