Permainan ini muncul di Eropa pada paruh kedua abad ke-15 setelah berevolusi dari game yang lebih tua ( Shatranj ) dari India. Aspek seni dapat ditemukan dalam komposisi catur. Ilmuwan telah mengembangkan secara luas taktik permainan sejak awal itu. Salah satu tujuan awal para ilmuwan komputer adalah untuk menciptakan mesin yang bisa bermain catur. Catur sekarang sangat dipengaruhi oleh kemampuan dari program catur tersebut dan sudah bisa untuk bermain online. Pada tahun 1997 Deep Blue menjadi komputer pertama yang mengalahkan Garry Kasparov, seorang Juara Dunia dalam suatu pertandingan.
Tradisi catur kompetitif dan terorganisir dimulai pada abad ke-16. Resmi pertama Juara catur pertama dunia, Wilhelm Steinitz, mengklaim gelar pada tahun 1886. Juara Dunia saat ini adalah Viswanathan Anand. Catur adalah olahraga yang diakui oleh Komite Olimpiade Internasional, dan dipimpin oleh FIDE. Hari ini, catur merupakan salah satu perminan papan yang paling populer di dunia, dimainkan oleh jutaan orang di seluruh dunia, baik itu di rumah, di klub, online, melalui korespondensi , dan di turnamen .
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 benteng , dua gajah, dua kuda dan delapan bidak.
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 adalah pada keadaan remis abadi / mengulang langkah yang sama dalam 3 putaran. 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 remis 0.5.
Algoritma Yang Digunakan
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.
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 successor terbaik 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 meningkatnya nilai dari W dan D).
Solusi untuk permasalahan chess search tree beragam. Salah satunya adalah algoritma minimax dan negamax, dimana semua kemungkinan langkah dihitung kemungkinannya. Selain itu juga ada alpha-beta search di mana nilai dari suatu posisi hanya dihitung apabila 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.
Pembahasan Algoritma
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 pemain yang 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.
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.
Komentar
Posting Komentar