Pengaplikasian Pohon dalam Algoritma Sebuah Game Catur Adrian Edbert Luman / 13507057 1) Jurusan Teknik Informatika ITB, Bandung 40116, email:
[email protected]
Abstract –Makalah ini menjelaskan mengenai aplikasi pohon n-ary dalam membuat algoritma suatu game catur. Penggunaan pohon terutama terlihat jelas melalui pembukaan dalam sebuah permainan catur di mana gerakan yang legal masih belum terlalu banyak. Kata Kunci: pembukaan permainan catur, chess tree search, minimax dan negamax, alpha-beta search, principal variation search.
Tabel 1. Istilah Dalam Makalah Ini Istilah pos depth Evaluate
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.
best
Successors
succ
Arti Posisi dalam permainan catur Tingkatan dari pohon yang dicari Sebuah fungsi untuk menentukan nilai dari sebuah posisi. Rentang hasil antara – INFINTIY sampai +INFINTIY Nilai terbaik yang didapat pada saat mencari tingkat selanjutnya dalam pohon Sebuah fungsi yang menentukan semua kemungkinan langkah yang legal dalam satu langkah Himpunan kemungkinan langkah yang mungkin dari posisi awal dalam satu langkah
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 successor terbaik berdasarkan dari posisi musuh, dst.
Berbagai algoritma pencarian berikut digambarkan menggunakan pengantar bahasa C. Variable serta fungsi yang ada memiliki arti sebagai berrikut.
Gambar 1: Contoh dari sebuah search tree
Pencarian dari keseluruhan pohon akan menghasilkan W^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 di mana 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.
Gambar 2: Contoh dari sebuah program solusi
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 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. Proses ini bila digambarkan dengan pseudo code bahasa yang mirip dengan C menjadi seperti berikut. int NegaMax (pos, depth) { if (depth == 0) return Evaluate(pos); best = -INFINITY; succ = Successors(pos); while (not Empty(succ)) { pos = RemoveOne(succ); value = -NegaMax(pos, depth1); if (value > best) best = value; } return best; } 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.
Tabel 2.Estimasi waktu pencarian menggunakan NegaMax
Waktu pencarian 900 0,018 s 27.000 0,54 s 810.000 16,2 s 24.300.000 8 menit 729.000.000 4 jam 21.870.000.000 5 hari
depth Jumlah posisi 2 3 4 5 6 7
Dapat dilihat seberapa besar pohon permainan ini
berkembang dengan cepat, bahkan dengan asumsi fungsi penganalisis yang sangat cepat. Dengan algoritma yang ada pencarian tentu tak dapat dilakukan. Ukuran dari pohon pencarian tersebut harus dipotong. Di sinilah peranan dari algoritma alpha-beta. Algoritma alpha-beta relatif tidak rumit, namun membutuhkan pemikiran mendalam sebelum terbiasa dengan algoritma semacam ini. Sebagai contoh bayangkan skenario sebagai berikut : Program catur anda sibuk mencari semua kemungkinan langkah pada tingkat teratas. Sementara ini program tersebut berhasil mencari 6 langkah pertama, nilai terbaik untuk sementara ini adalah 15 poin. Program tersebut mulai mencari langkah ketujuh dan menghitung kemungkinan jawaban dari lawan. Ingatlah bahwa nilai pemain dikurangi oleh nilai terbaik musuh. Program menghitung semua kemungkinan jawaban lawan sampai pada satu langkah berikut, menghasilkan nilai sebagai berikut; -20, -22, -15, -16, -11, -18, -20, -30, -70, -75 Pada saat ini nilai terbaik adalah -11, di mana program menilai langkah yang dilakukannya sebagai – (-11) = 11. Nilai ini lebih buruk dibandingkan dengan langkah terbaik sebelumnya (15) maka langkah ini diacuhkan. Namun program sudah menghabiskan banyak waktu mencari langkah ke-6 sampai dengan langkah ke-10 dari lawan. Pada saat salah satu langkah dari musuh bernilai -11, kita dapat mengetahui bahwa langkah kita tidak dapat menandingi langkah terbaik sebelumnya. Apapun nilai dari langkah seterusnya, langkah terbaik pastilah menghasilkan paling tidak -11. Yang berarti langkah terbaik kita hanya akan bernilai 11 yang oleh karena itu harus diacuhkan. Jadi kita harusnya keluar dari pencarian pada saat nilai -11 didapatkan yang mana akan menghemat waktu pencarian. Pencarian Alpha-Beta adalah salah satu penemuan paling pertama dalam mengurangi jumlah posisi yang harus dicari sehingga meningkatkan tingkat kedalaman dari pencarian yang dapat dicapai dalam suatu permainan. Idenya adalah dalam suatu bagian besar dari pohon kita tidak mencari nilai eksak dari suatu posisi, tapi hanya tertarik apabila lebih baik atau lebih buruk daripada apa yang kita temukan sebelumnya. Hanya nilai dari suatu posisi yang memenuhi ketentuan utama yang harus ditentukan nilainya secara pasti (ketentuan utama mencakup pergantian antara langkah terbaik pemain dan langkah terbaik lawan dari suatu akar hingga kedalaman dari pohon). Prosedur pencarian Alpha-Beta memiliki 2 argumen tambahan yang mengindikasi batasan di mana prosedur tertarik untuk menghitung nilai eksak dari sebuah posisi:
int AlphaBeta (pos, depth, alpha, beta) { if (depth == 0) return Evaluate(pos); best = -INFINITY; succ = Successors(pos); while (not Empty(succ) && best < beta) { pos = RemoveOne(succ); if (best > alpha) alpha = best; value = -AlphaBeta(pos, depth-1, -beta, -alpha); if (value > best) best = value; } return best; } Keuntungan mengguunakan Alpha-Beta akan didapat ketika prosedur keluar lebih cepat dari perulangan while; sebuah nilai terbaik yang sama atau melebihi beta disebut dengan cutoff. Cutoff ini sangat aman karena artinya dahan dari pohon ini lebih buruk dibandingkan dengan posisi yang didapat sebelumnya. Keuntungan paling besar didapat ketika pada setiap tingkat dari pohon posisi successor terbaik akan dicari paling pertama, bisa karena posisi ini adalah bagian dari ketentuan utama (yang ingin dikembangkan sedini mungkin) atau menyebabkan terjadinya cutoff sedini mungkin. Dalam Kondisi optimal Alpha-Beta tetap harus melakukan pencarian sebanyak W^((D+1)/2 + W^(D/2) – 1 posisi. Jumlah ini jauh lebih sedikit daripasa MiniMax namun tetap eksponensial. AlphaBeta mampu mencapai kedalaman 2 kali lipat dalam tempo waktu yang sama. Versi Alpha-Beta di atas juga dikenal dengan sebutan fail-soft alpha-beta. Versi tersebut dapat mengembalikan nilai di luar alpha . . . beta, yang dapat digunakan sebagai batas atas atau batas bawah apabila pencarian ulang harus dilakukan. 2.3. Principal Variation Search Principal variation search adalah sebuah variasi dari alpha-beta di mana semua node diluar ketentuan dicari dengan minimal window beta = alpha + 1. Idenya adalah dengan semua langkah di luar ketentuan utama akan lebih buruk apabila urutan langkah yang dilakukan tidak salah; hal ini dibuktikan dengan pencarian minimal window bernilai rendah. Seandainya urutan langkah tidak sempurna, ada kemungkinan keluranya nilai yang tinggi, pada kasus ini maka pencarian alpha-beta secara keseluruhan harus dilakukan. Ekspektasi yang diambil adalah
bahwa keuntungan yang didapat dari pencarian minimal window lebih besar dibanding kerugian setiap kali terjadi kasus pencarian ulang tersebut. int PrincipalVariation (pos, depth, alpha, beta) { if (depth == 0) return Evaluate(pos); succ = Successors(pos); pos = RemoveOne(succ); best = -PrincipalVariation(pos, depth-1, -beta, -alpha); while (not Empty(succ) && best < beta) { pos = RemoveOne(succ); if (best > alpha) alpha = best; value = PrincipalVariation(pos, depth-1, alpha-1, -alpha); if (value > alpha && value < beta) best = PrincipalVariation(pos, depth-1, beta, -value); else if (value > best) best = value; } return best; } 2.4. Quiescence Search Masalah yang muncul apabila secara paksa menghentikan pencarian pada kedalamana tertentu disebut sebagai ‘horizon effect’. Misalkan program baru saja menangkap sebuah pion pada kedalaman 0, kemudian menjalankan langkah tersebut dengan asumsi itulah langkah dengan nilai terbaik. Namun, apabila program mencari lebih dalam 1 tingkat maka terlihat bahwa lawan bisa menangkap ratu pemain.
kemungkinan langkah dan mencari langkah terbaik. Tentu saja pencarian yang dilakukan lamban sehingga hanya digunakan pada situasi tertentu saja. Biasanya ini tidak dilakukan sama sekali, tapi dengan penggunaan quiescence width extension terkadang pencarian ini muncul ke permukaan. Biasanya hanya digunakan pada keadaan yang benar-benar berbahaya di mana pihak yang melangkah dalam kondisi tercheck dan mungkin kalah karena hal ini.
2.4.2. Reduced Width Search Hanya dikeluarkan pada tingkat kedalaman yang rendah tergantung seberapa berbahaya suatu posisi. Biasanya hanya sampai tingkatan 0 atau 1, tapi terkadang sampai 2 atau 3 tingkatan di bawah node (depth = 0). Kondisi di mana pencarian sampai lebih dari 2 tingkatan biasanya terjadi apabila ada langkah yang dapat mengubah niai secara drastis, seperti penangkapan perwira, check, dan promosi pion. 2.4.2. Capture Search
Sesuai dengan namanya, capture search melakukan pencarian hanya pada node yang melakukan langkah penangkapan. 3.Pembukaan dalam Catur Dalam permainan catur terdapat himpunan langkahlangkah pada awal permainan yang sudah terdefinisi secara pasti. Masuknya perhitungan terhadap pembukaan dalam permainan catur ke dalam algoritma pencarian dapat menyederhanakan algoritma, sebab setiap langkah yang dilakukan program dalam tahap ini tidak perlu dihitung nilainya selama masih berada dalam himpunan database dari pembukaan permainan. 3.1. Contoh dari Pohon Pembukaan dalam Catur
Untuk memecahkan masalah ini ada sebuah metode yang bernama ‘quiescence search’ yang mengaitkan dan menguji semua non-quiescence atau langkah ‘kasar’ sampai keadaan terkendali. Hal ini membuat program mampu mendeteksi langkah penangkapan panjang dan menghitung kelayakan dari langkah tersebut. Ada beberapa masalah dengan metode ini yang harus dipecahkan. Metode ini dapat menyebabkan terjadinya ledakan ukuran dari pohon permainan bila digunakan sembarangan. Ada 3 tingkatan quiescence search, ketiganya memiliki batasan yang berbeda untuk memecahkan masalah ini. 2.4.1. Full Width Search Tidak terlalu jauh berbeda dibandingkan pencarian normal pada kedalaman > 0, memperhitungkan semua
Gambar 3: Salah satu pohon pembukaan
Dalam pohon pembukaan tersebut pada tingkat pertama ada beberapa himpunan kemungkinan langkah dari putih dan hitam yang ada. Setiap langkah
tersebut memiliki beberapa himpunan langkah selanjutnya untuk setiap himpunan langkah yang tidak digunakan program tidak akan menghitung nilai dari langkah-langkah tersebut. Program akan mulai menghitung hanya pada tahap permainan tengah yaitu pada saat di mana database dari pembukaan sudah tidak melingkupi kemungkinan langkah yang ada. Pengaplikasian pohon ini akan membantu program untuk menghilangkan waktu yang diperlukan apabila program mencari semua kemungkinan langkah yang ada dalam beberapa langkah pertama.
DAFTAR REFERENSI [1] Chess Tree Search http://www.cs.biu.ac.il/~davoudo/intro.html Tanggal akses : 4 Januari 2009 pukul 13:00 [2] Computer Chess Programming Theory http://www.frayn.net/beowulf/theory.html Tanggal akses : 4 Januari 2009 pukul 13:00 [3] Wikipedia http://en.wikipedia.org/wiki/Chess_opening Tanggal akses : 4 Januari 2009 pukul 13:00
[4] Artificial Intelligence and Chess http://artificialintelligence.aidepot.com/Essay/DeepBlue-AI.html Tanggal akses : 4 Januari 2009 pukul 13:00 [5] Wikipedia http://en.wikipedia.org/wiki/Chess_programming Tanggal akses : 5 Januari 2009 pukul 20:00 Gambar 4: Salah satu pohon pembukaan
4.Kesimpulan Permainan catur sudah ada sejak dulu. Apabila permainan catur diibaratkan sebuah pohon dengan posisi pertama sebagai akar yang paling atas dan setiap kemungkinan langkah sebagai dahannya maka akan didapatkan sebuah pohon yang sangat besar. Oleh karena itu penggunaan algoritma pencarian yang benar sangatlah penting untuk efisiensi dalam pembuatan sebuah program permainan catur. Algoritma pencarian dalam permainan catur merupakan salah satu dasar dari semakin berkembangnya permainan catur di dunia. Beberapa algoritma dapat melakukan penghitungan untuk setiap posisi dengan lebih baik dari algoritma yang lain. Diimplementasikannya alpha-beta search ke dalam NegaMax search merupakan salah satu langkah untuk mencoba menyelesaikan masalah yang terdapat dalam efisiensi terhadap permainan catur. Database pembukaan dalam permainan catur juga dapat membantu meringankan beban yang harus dilakukan program untuk mencari langkah terbaik dalam beberapa langkah pertama.
