Algoritma Minimax Pada Permainan Tic-Tac Toe Skala 3x3
Abstrak
Perkembangan teknologi dalam dunia komputer semakin hari semakin lebih maju, komputer yang dulunya berfungsi sebagai alat hitung dan pengolah data, seiring perkembangan teknologi komputer saat ini tidak hanya bertindak sebagai mesin yang hanya disuruh namun mampu berfikir memberikan respon bagi pengguna, sehingga muncul istilah ArtificialIntellegence (AI) atau Kecerdasan Buatan.
Methohe Minimax merupakan salah satu contoh dari method yang digunakan dalam kecerdasan buatan, minimax adalah suatu algoritmayang menggunakan teknik pencarian Depth-First Search dengan kedalaman terbatas. Adapun media yangcocok untuk penerapan algoritma minimax adalah permainan Tic-Tac-Toe, beberapa alasan mengapa Tic-Tac-Toe digunakan sebagai media penerapan kecerdasan buatan antara lain Tic-Tac-Toe sangat mudahmenentukan ukuran kesuksesan atau kegagalan, sangat mungkin untuk dibandingkan dengan kemampuanmanusia, mudah dimainkan.
Latar Belakang
Perkembangan teknologi dalam dunia komputer semakin hari semakin lebih maju, komputer yang dulunya berfungsi sebagai alat hitung dan pengolah data, seiring perkembangan teknologi modern, komputer saat ini tidak hanya bertindak sebagai mesin yang hanya disuruh namun mampu berfikir memberikan respon bagi pengguna, sehingga muncul istilah Artificial Intellegence (AI) atau Kecerdasan Buatan.
Artificial Intellegencesering dimanfaatkan dalam pembuatan sebuah game permainan, salah satunya pada game tic-tac-toe. Alasan mengapa permainan,tic-tac-toedigunakan sebagai media penerapan kecerdasan buatan padakasus ini, antara lain:
a. Cukup mudah dalam menentukan ukuran kemenangan, atau kegagalan.
b. Memungkin untuk dibandingkan dengan kemampuan manusia.
c. Pola aturan permainan Tic-Tac-Toe cukup dikenal dan mudah untuk dimainkan, diasumsikan setiap orang (anak-anak atau dewasa) dapat memainkannya.
d. Dengan asumsi-asumsi diatas, maka diharapkan setiap pengguna mampu bermain dengan baik bersama komputer. Sehingga yang dibutuhkan
pemain atau user dalam memainkan permainan hanyalah ketelitian dan logika berfikir yang baik.
Minimax merupakan salah satu teknik permainan yang terkenal. Minimax menggunakan teknik pencarian Depth-FirstSearch dengan kedalaman terbatas, dan fungsi evaluasi yang digunakan adalah fungsi evaluasistatis, dengan mengansumsikan bahwa lawan akan membuat langkah terbaiknya yang dapat dilakukan, algoritma minimax cocok digunakan untuk permainan catur, Othello, checkers, danTic-Tac-Toe.
Kajian Teori
Konsep Dasar Kecerdasan Buatan
Kecerdasan buatan atau lebih dikenal sebagai Artificial Intelligence, memiliki beberapa defenisi, antara lain :
a. Artificial intelligence adalah ilmu yang mengembangkan komputer supaya dapat bekerja dan berpikir serta mengambil keputusan seperti layaknya manusia.
b. Artificial intelligence merupakan salah satu bagian ilmu komputer yang membuat agar mesin (komputer) dapat melakukan pekerjaan seperti dan sebaik yang dilakukan oleh manusia.
c. Artificial intelligence merupakan software yang memungkinkan
komputer digital bisa meniru beberapa fungsi otak manusia yang terbatas.
Permainan Tic-Tac-Toe
Permainan tic-tac-toe merupakan permainan berjenis board-game berukuran 3x3. Pemain harus mengisi sel-sel, sehingga karakter yang dimasukkan pemain tersebut dapat membentuk suatu garis lurus horizontal, vertikal, ataupun juga diagonal. Permainan ini biasanya dimainkan oleh 2 orang pemain, tapi pada versi permainan komputer, pemain lawan dapat digantikan oleh komputer. Hasil permainan berupa menang, kalah, ataupun seri.
Algoritma Minimax
Algoritma minimax merupakan basis dari semua permainan berbasis AI. 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.
Algoritma minimax ini bekerja secara rekursif dengan mencari langkah yang akan membuat lawan mengalami kerugian minimum. 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 pada algorima minimax digunakan sebuah fungsi heurisitic untuk mengevaluasi nilai sebagainilai yang merepresentasikan hasil permainan yang akan terjadi jika langkah tersebut dipilih. 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 heuristicyang akan menuntun permainan ke hasil akhir yang menguntungkan bagi komputer.
Garis besar algoritma minimax secara umum
"If ada langkah kemenangan Then pilih langkah tersebut.
Else Ifl awan mempunyai 2 spot terisi dalam satu garis dengan spot ketiga masih kosong Then tutup langkah tersebut (isi spot kosong ketiga tersebut).
Else melangkah ke state yang mempunyai kemungkinan menang tertinggi (berdasarkan nilai heuristic yang dibangkitkan)"
Algoritma umum diatas untuk permainan tic-tac-toe
"Mencari langkah dengan nilai maksimum
If langkah tersebut merupakan langkah kemenangan Then pilih lagkah tersebut.
Else
Foreach kemungkinan langkah yang ada
Cari langkah lawan yang bernilai minimum.
Return nilai dari langkah tersebut.
Pilih langkah yang bernilai maksimum darilangkah-langkah tersebut. "
Analisis
Analisis dalam kasus ini, pada permainan tic-tac-toe menggunakan algoritma minimax, dimana AI akan menelusuri semua kemugkinan langkah yang akan dilakukan oleh pemain. SehinggaAI akan selalu mengetahui kemungkinan pemain untuk menang dan memblok semua langkah kemenangan pemain.
Dengan demikian permainan akan selalu seri apabila pemain cukup teliti dalam menentukan langkah. Namun jika pemain melakukan langkah yang salah, maka AI akan langsung menggunakan kesempatan tersebut untuk mengambil langkah yang akan mengarahkannya ke hasil akhir berupa kemenangan atau seri.
Berikut adalah langkah atau cara memainkan permainan tic–tac-toedengan metode minimax.
Kesimpulan
a) Penerapan algoritma minimax cukup bagus dan cocok untuk pengambilan
keputusan oleh AI, terutama dalam permainan nplayer.
b) Algoritma minimax menggunakan konsep Dept First Search dalam pembentukan pohon solusi.
c) Pohon solusi dibentuk dari awal permainan sampai akhir permainan.
d) Semakin akurat fungsi dari heuristic yang digunakan, semakin baik pula pengambilan keputusan yang dilakukan oleh AI.
e) Dengan menggunakan algoritma minimax untuk AI dalam permainan tic-tac-toe, pemain kemungkinan sangat kecil untuk menang melawan AI tersebut.
Referensi
Munir, Rinaldi.2006. “Strategi Algoritmik”. Program Studi Informatika, Institut Teknologi Bandung. Kevin McGee, 2005. “Advance Game Programming : AI”.
Khoirush Sholih, 2010. Jurnal Implementasi Teori Minimax pada Tic Tac Toe. Teknik Informatika. Institut Teknologi Bandung.
Wikimedia Foundation, Inc. “Depht First Search”. http://en.wikipedia.org/wiki/DFS_search_algorithm. Diakses tanggal 10 April 2013
Perkembangan teknologi dalam dunia komputer semakin hari semakin lebih maju, komputer yang dulunya berfungsi sebagai alat hitung dan pengolah data, seiring perkembangan teknologi komputer saat ini tidak hanya bertindak sebagai mesin yang hanya disuruh namun mampu berfikir memberikan respon bagi pengguna, sehingga muncul istilah ArtificialIntellegence (AI) atau Kecerdasan Buatan.
Methohe Minimax merupakan salah satu contoh dari method yang digunakan dalam kecerdasan buatan, minimax adalah suatu algoritmayang menggunakan teknik pencarian Depth-First Search dengan kedalaman terbatas. Adapun media yangcocok untuk penerapan algoritma minimax adalah permainan Tic-Tac-Toe, beberapa alasan mengapa Tic-Tac-Toe digunakan sebagai media penerapan kecerdasan buatan antara lain Tic-Tac-Toe sangat mudahmenentukan ukuran kesuksesan atau kegagalan, sangat mungkin untuk dibandingkan dengan kemampuanmanusia, mudah dimainkan.
Latar Belakang
Perkembangan teknologi dalam dunia komputer semakin hari semakin lebih maju, komputer yang dulunya berfungsi sebagai alat hitung dan pengolah data, seiring perkembangan teknologi modern, komputer saat ini tidak hanya bertindak sebagai mesin yang hanya disuruh namun mampu berfikir memberikan respon bagi pengguna, sehingga muncul istilah Artificial Intellegence (AI) atau Kecerdasan Buatan.
Artificial Intellegencesering dimanfaatkan dalam pembuatan sebuah game permainan, salah satunya pada game tic-tac-toe. Alasan mengapa permainan,tic-tac-toedigunakan sebagai media penerapan kecerdasan buatan padakasus ini, antara lain:
a. Cukup mudah dalam menentukan ukuran kemenangan, atau kegagalan.
b. Memungkin untuk dibandingkan dengan kemampuan manusia.
c. Pola aturan permainan Tic-Tac-Toe cukup dikenal dan mudah untuk dimainkan, diasumsikan setiap orang (anak-anak atau dewasa) dapat memainkannya.
d. Dengan asumsi-asumsi diatas, maka diharapkan setiap pengguna mampu bermain dengan baik bersama komputer. Sehingga yang dibutuhkan
pemain atau user dalam memainkan permainan hanyalah ketelitian dan logika berfikir yang baik.
Minimax merupakan salah satu teknik permainan yang terkenal. Minimax menggunakan teknik pencarian Depth-FirstSearch dengan kedalaman terbatas, dan fungsi evaluasi yang digunakan adalah fungsi evaluasistatis, dengan mengansumsikan bahwa lawan akan membuat langkah terbaiknya yang dapat dilakukan, algoritma minimax cocok digunakan untuk permainan catur, Othello, checkers, danTic-Tac-Toe.
Kajian Teori
Konsep Dasar Kecerdasan Buatan
Kecerdasan buatan atau lebih dikenal sebagai Artificial Intelligence, memiliki beberapa defenisi, antara lain :
a. Artificial intelligence adalah ilmu yang mengembangkan komputer supaya dapat bekerja dan berpikir serta mengambil keputusan seperti layaknya manusia.
b. Artificial intelligence merupakan salah satu bagian ilmu komputer yang membuat agar mesin (komputer) dapat melakukan pekerjaan seperti dan sebaik yang dilakukan oleh manusia.
c. Artificial intelligence merupakan software yang memungkinkan
komputer digital bisa meniru beberapa fungsi otak manusia yang terbatas.
Permainan Tic-Tac-Toe
Permainan tic-tac-toe merupakan permainan berjenis board-game berukuran 3x3. Pemain harus mengisi sel-sel, sehingga karakter yang dimasukkan pemain tersebut dapat membentuk suatu garis lurus horizontal, vertikal, ataupun juga diagonal. Permainan ini biasanya dimainkan oleh 2 orang pemain, tapi pada versi permainan komputer, pemain lawan dapat digantikan oleh komputer. Hasil permainan berupa menang, kalah, ataupun seri.
Algoritma Minimax
Algoritma minimax merupakan basis dari semua permainan berbasis AI. 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.
Algoritma minimax ini bekerja secara rekursif dengan mencari langkah yang akan membuat lawan mengalami kerugian minimum. 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 pada algorima minimax digunakan sebuah fungsi heurisitic untuk mengevaluasi nilai sebagainilai yang merepresentasikan hasil permainan yang akan terjadi jika langkah tersebut dipilih. 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 heuristicyang akan menuntun permainan ke hasil akhir yang menguntungkan bagi komputer.
Garis besar algoritma minimax secara umum
"If ada langkah kemenangan Then pilih langkah tersebut.
Else Ifl awan mempunyai 2 spot terisi dalam satu garis dengan spot ketiga masih kosong Then tutup langkah tersebut (isi spot kosong ketiga tersebut).
Else melangkah ke state yang mempunyai kemungkinan menang tertinggi (berdasarkan nilai heuristic yang dibangkitkan)"
Algoritma umum diatas untuk permainan tic-tac-toe
"Mencari langkah dengan nilai maksimum
If langkah tersebut merupakan langkah kemenangan Then pilih lagkah tersebut.
Else
Foreach kemungkinan langkah yang ada
Cari langkah lawan yang bernilai minimum.
Return nilai dari langkah tersebut.
Pilih langkah yang bernilai maksimum darilangkah-langkah tersebut. "
Analisis
Analisis dalam kasus ini, pada permainan tic-tac-toe menggunakan algoritma minimax, dimana AI akan menelusuri semua kemugkinan langkah yang akan dilakukan oleh pemain. SehinggaAI akan selalu mengetahui kemungkinan pemain untuk menang dan memblok semua langkah kemenangan pemain.
Dengan demikian permainan akan selalu seri apabila pemain cukup teliti dalam menentukan langkah. Namun jika pemain melakukan langkah yang salah, maka AI akan langsung menggunakan kesempatan tersebut untuk mengambil langkah yang akan mengarahkannya ke hasil akhir berupa kemenangan atau seri.
Berikut adalah langkah atau cara memainkan permainan tic–tac-toedengan metode minimax.
Kesimpulan
a) Penerapan algoritma minimax cukup bagus dan cocok untuk pengambilan
keputusan oleh AI, terutama dalam permainan nplayer.
b) Algoritma minimax menggunakan konsep Dept First Search dalam pembentukan pohon solusi.
c) Pohon solusi dibentuk dari awal permainan sampai akhir permainan.
d) Semakin akurat fungsi dari heuristic yang digunakan, semakin baik pula pengambilan keputusan yang dilakukan oleh AI.
e) Dengan menggunakan algoritma minimax untuk AI dalam permainan tic-tac-toe, pemain kemungkinan sangat kecil untuk menang melawan AI tersebut.
Referensi
Munir, Rinaldi.2006. “Strategi Algoritmik”. Program Studi Informatika, Institut Teknologi Bandung. Kevin McGee, 2005. “Advance Game Programming : AI”.
Khoirush Sholih, 2010. Jurnal Implementasi Teori Minimax pada Tic Tac Toe. Teknik Informatika. Institut Teknologi Bandung.
Wikimedia Foundation, Inc. “Depht First Search”. http://en.wikipedia.org/wiki/DFS_search_algorithm. Diakses tanggal 10 April 2013
Comments
Post a Comment