ARTIFICIAL INTELLIGENCE

Artificial Intelligence Pada Game Checkers

PENDAHULUAN
Checkers merupakan jenis permainan game board, yang mengandalkan strategi sebagai elemen utamanya. Permainan ini dimainkan oleh dua orang pemain dengan tujuan menghabiskan kepingan lawan. Permainan checkers yang dibuat dengan AI (Artificial Intelligence) tertentu menerapkan algoritma Minimax. Algoritma Minimax merupakan salah satu implementasi dari Depth First Search dan digunakan untuk menentukan pilihan agar memperkecil kemungkinan kehilangan nilai maksimal, yang akan mendeskripsikan dimana jika terdapat pemain yang mengalami pendapatan akan maka pemain lain akan mengalami kehilangan sebesar pendapatan tersebut. Untuk memperkecil lingkup pencarian pada algoritma Minimax, dikembangkan suatu algoritma yang dinamakan alpha-beta untuk mengurangi jumlah node pada pohon pencarian. Pada permainan checkers algoritma ini akan menentukan langkah yang diambil oleh AI agar menghasilkan pendapatan maksimum dengan mempertimbangkan kemungkinan langkah yang dapat dilakukan lawan selanjutnya. Perkembangan permainan saat ini telah sampai kepada pembuatan artificial intelligent (AI) sebagai teknik yang digunakan pada komputer atau video game untuk memproduksi ilusi atau kepintaran karakter yang bukan pemain. Dalam boad game, AI akan berperan sebagai musuh yang akan bergerak sesuai algoritma yang digunakan.

CHECKERS
Permainan checkers (dalam bahasa Inggris Amerika) atau disebut draughts (dalam bahasa Inggris British) merupakan permainan yang menggunakan strategi abstrak dimainkan oleh dua pemain dengan menggunakan langkah diagonal token dan menangkap dengan melompati token musuh.
Permainan ini telah dimainkan di Eropa sejak abad ke16, dikembangkan dari permainan alquerque. Bentuk yang paling populer dari pemainan ini adalah international draughts, yang dimainkan pada papan 10×10. Bentuk yang juga populer adalah English draughts, yang disebut American checkers, dimainkan pada papan 8×8.



ALGORITMA MINIMAX
Algoritma Minimax merupakan basis dari semua permainan berbasis AI[ http://id.wikipedia.org]. Algoritma Minimax merupakan algoritma yang digunakan untuk menentukan pilihan agar memperkecil kemungkinan kehilangan nilai maksimal. Algoritma ini diterapkan dalam permainan yang melibatkan dua pemain seperti tic tac toe, checkers, go dan permainan yang menggunakan strategi atau logika lainnya. Hal ini berarti permainan-permainan tersebut dapat dijelaskan sebagai suatu rangkaian aturan dan premis. Dengan itu, kita dapat mengetahui, pada titik tertentu permainan, langkah-langkah yang mungkin berikutnya. Permainan tersebut berbagi karakteristik yang sama, yakni “permainan dengan penuh informasi”. Setiap pemain mengetahui semua langkah-langkah yang mungkin dari pemain lawannya. Algoritma ini mulai dikembangkan dari teori game zero-sum. Teori ini mendeskripsikan situasi dimana jika terdapat pemain yang mengalami pendapatan, pemain lain akan mengalami kehilangan dengan nilai yang sama dari pendapatan tersebut, dan sebaliknya. Jumlah pendapatan dari pemain yang dikurangi dengan jumlah kehilangan akan berjumlah nol.
PENERAPAN ALGORITMA MINIMAX DALAM CHECKERS
Penerapan algoritma Minimax dalam checkers dibuat berdasarkan prosedur Minimax untuk mendapatkan langkah terbaik dari posisi yang ada. Setiap posisi memiliki nilai yang dapat dihasilkan dari langkah terbaik, dengan berasumsi bahwa AI akan selalu mencoba memaksimalkan nilai, ketika lawan akan mencoba untuk meminimalkannya.Ketika prosedur minimax mencapai akar pada pohon pencarian (posisi saat tersebut), akan menghasilkan langkah terbaik dengan asumsi lawan akan menggunakan kriteria evaluasi yang sama. Beberapa versi program yang dibuat kebanyakan telah menerapkan algoritma pemotongan alpha-beta.Terdapat dua macam metode, yang disebut rote learning. Metode tersebut memiliki penyimpan untuk setiap posisi yang ditemui selama permainan dengan tidak menghilangkan nilai yang ditentukan oleh prosedur Minimax. Hasilnya adalah jika terdapat posisi yang pernah ditenukan sebelumnya, akan dimunculkan sebagai posisi terminal pada pohon pencarian. Sehingga, pencarian akan semakin mudah karena nilai posisi diambil dari hasil pencarian yang telah dilakukan sebelumnya. Satu masalah awal yang ditemukan adalah program tidak mendukung untuk melangkah langsung menuju kemenangan.
Pertama kali dilakukan oleh Arthur Samuel dalam melakukan pembuatan program untuk mempelajari permainan checkers. Prah program yang dibuat berdasarkan prosedur Minimax untuk mendapatkan langkah terbaik dari posisi yang ada. Setiap posisi memiliki nilai yang dapat dihasilkan dari langkah terbaik, dengan berasumsi bahwa AI akan selalu mencoba memaksimalkan nilai, ketika lawan akan mencoba untuk meminimalkannya. Ketika prosedur minimax mencapai akar pada pohon pencarian (posisi saat tersebut), akan menghasilkan langkah terbaik dengan asumsi lawan akan menggunakan kriteria evaluasi yang sama. Beberapa versi program yang dibuat Samuel juga telah menerapkan algoritma pemotongan alpha-beta.
Samuel menggunakan dua macam metode, yang disebut rote learning. Metode tersebut memiliki penyimpan untuk setiap posisi yang ditemui selama permainan dengan tidak menghilangkan nilai yang ditentukan oleh prosedur Minimax. Hasilnya adalah jika terdapat posisi yang pernah ditenukan sebelumnya, akan dimunculkan sebagai posisi terminal pada pohon pencarian. Sehingga, pencarian akan semakin mudah karena nilai posisi diambil dari hasil pencarian yang telah dilakukan sebelumnya. Satu masalah awal yang ditemukan adalah program tidak mendukung untuk melangkah langsung menuju kemenangan. Samuel memberikan pengarahan dengan mengurangi sedikit nilai posisi setiap tahap (disebut ply) pada analisis Minimax. Jika program berhadapan dengan pilihan posisi dengan nilai yang hanya dibedakan oleh ply, maka program akan secara otomatis melangkah pada pilihan yang paling menguntungkan. Samuel mencoba permainan ini berkali-kali dengan melawan berbagi versi sebelumnya dan melakukan backup pada setiap langkah.

KESIMPULAN
Permainan checkers merupakan permainan yang dimainkan oleh dua orang dengan tujuan untuk menghabiskan kepingan yang dimiliki lawan. Dalam pembuatannya dengan AI, permainan ini menerapkan algoritma Minimax. Algoritma Minimax memiliki dasar berupa zero-sum game, dimana jika pemain mendapatkan nilai tertentu maka pemain lain akan kehilangan nilai yang sama dengan pemain tersebut. Dengan menambahkan nilai alpha-beta algoritma Minimax akan memiliki pohon pencarian yang lebih singkat sehingga akan membutuhkan waktu singkat untuk melakukan aksinya. Nilai ini akan berhenti mengevaluasi langkah ketika terdapat paling tidak satu kemungkinan yang ditemukan dan membuktikan bahwa langkah tersebut lebih buruk jika dibandingkan dengan langkah yang diperiksa sebelumnya. Algoritma Minimax menggunakan DFS sebagai dasar pembuatan pohon pencarian.

SUMBER :
http://blog.uin-malang.ac.id/sharfina/2010/10/
Suyanto. 2007. Artificial Intelligence. Bandung : Informatika Bandung
hanz-kampus.blogspot.com/…/teknik-pencarian-kecerdasan-buatan.html