Algoritma Minimax Pada Permainan Tic-Tac Toe Skala 3x

 

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

http://catatankecilanaknegeri.blogspot.co.id/2014/12/algoritma-minimax-pada-permainan-tic.html

ALGORITMA WATER JUG

Algoritma mendapatkan 4 liter air dengan ember 5 liter dan 3 liter

Pada postingan kali ini saya  akan membahas tentang latihan untuk memperdalam tentang Algoritma dan masih mengenai tentang ember. Dalam literature klasik masih terdapat persoalan tentang air yang dinamakan water jug problem. Misalnya anda mempunyai dua buah ember masing-masing bervolume 5 liter dan 3 liter, anda diminta  mendapatkan air sebanyak 4 liter dengan hanya menggunakan bantuan dua ember tersebut ( tidak ada peralatan lainnya yang tersedia, hanya kedua ember itu saja yang ada).

Penyelesaiannya :

• Pertama, kita misalkan ember yang berkapasitas 5 liter adalah ember A, sedangkan ember satunya adalah ember B.

• Kemudian, kita isi penuh ember A, kemudian air dari ember A dimasukkan ke ember B hingga ember B penuh. Jadi di dalam ember A tersisa air 2 liter air.

• Selanjutnya, buang semua air yang ada di dalam ember B, kemudian masukkan air yang tersisa di dalam ember A (2 liter) ke dalam ember B. Jadi, sekarang di ember B ada 2 liter air dan ember A kosong.

• Langkah berikutnya, isi penuh ember A (5 liter) kemudian masukkan air dari ember A ke ember B sampai penuh. Maka ember B penuh dan ember A berkurang 1 liter.

• Di dalam ember A telah terdapat air sebanyak 4 liter. (selesai)

Nah, kira-kira seperti itulah langkah-langkahnya untuk menyelesaikan soal algoritma mendapatkan 4 liter air dengan ember 5 liter dan 3 liter. Semoga dapat bermanfaat.

PPT Kecerdasan Buatan