RESUME PAPER

Resume Paper antara “Kecerdasan Buatan dalam Game untuk Merespon Emosi dari Teks Berbahasa Indonesia Menggunakan Klasifikasi Teks dan Logika Fuzzy dengan Pembuatan Kecerdasan Buatan untuk Permainan Catur Jawa Dengan Menggunakan Algoritma MiniMax”

Sebelum kita meresume paper di atas penulis bagi beberapa kiteria yang menjadi dasar pembahasan penulis dimana kiteria tersebut adalah

1.    Algoritma

2.    Alur Program

3.    Kesimpulan

1.    Algoritma

            Perbedaan algoritma yang di gunakan antara Kecerdasan Buatan dalam Game untuk Merespon Emosi dari Teks Berbahasa Indonesia Menggunakan Klasifikasi Teks dan Logika Fuzzy (KBE_Fuzzy) dengan Kecerdasan Buatan untuk Permainan Catur Jawa Dengan Menggunakan Algoritma Minimax(KBC_Minimax) terletak pada jenis elemen mereka dimana KBE_Fuzzy termasuk dalam jenis game kecerdasan buatan yang mengembangkan salah satu elemen game yaitu NPC (Non Playable Character) yang mampu mengenali emosi dari teks berbahasa indonesia sekaligus merespon dengan perilaku sesuai dengan jenis emosinya. Metode yang digunakan dalam penelitian tersebut adalah klasifikasi teks sebagai penentu jenis emosi dalam teks dan logika fuzzy sebagai penentu perilaku dari NPC yang sesuai dengan jenis emosinya, Sedangkan KBC_Minimax menggunalan algoritma minimax merupakan salah satu implementasi dari DFS (Depth First Search). Algoritma minimax tersebut diaplikasikan pada permainan yang melibatkan dua orang, dan lebih khusus lagi, permainan dua orang yang saling berganti giliran bermain seperti checkers, tic-tac-toe, catur. dan game sejenis yang mendeskripsikan dengan sejumlah 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”. Dengan cara inilah penulis KBC_Minimax akan berusaha membuat sebuah kecerdasan buatan untuk permainan catur jawa, yang lagi, memiliki karakteristik yang sama.

2.    Alur Program

A.  KBE_Fuzzy

Dimulai dari alur program KBE_Fuzzy Dalam game tersebut, perilaku NPC dipengaruhi oleh atribut fisik yang dimiliki oleh setiap karakter NPC. Mascharenhas [Lihat di refensi penulis] dalam tulisannya menyebutkan atribut fisik pada karakter bermacam-macam sesuai dengan jenis game. Akan tetapi ada beberapa atribut standar yang selalu digunakan dalam game. Atribut tersebut adalah :

a. Power yaitu kekuatan fisik karakter.

b. Vitality yaitu jumlah nyawa karakter.

c. Agility yaitu ketangkasan atau kelincahan karakter.

Dalam game konvensional, atribut dari NPC akan berubah sesuai level permainan, akan tetapi dalam penelitian ini, atribut-atribut di atas akan berubah nilainya secara dinamis sesuai dengan jenis emosi yang diterima oleh NPC. Untuk menentukan respon dari NPC maka digunakan aturan-aturan yang mengatur hubungan sebab akibat antara jenis emosi dengan atribut NPC. Hubungan antara jenis emosi dengan atribut NPC ditunjukkan pada tabel 1 berikut ini :

Tabel 1. Pengaruh emosi terhadap atribut NPC

Emosi	Power	Vitality	Agility
Senang	+	+	+
Sedih	-	-	-
Marah	+	-	-
Takut	-	-	+

            Pada tabel di atas tanda “+” menunjukkan emosi tersebut berpengaruh positif terhadap atribut NPC. Dengan kata lain nilai atribut dari NPC akan bertambah jika mendapat input emosi yang bertanda “+”. Demikian pula sebaliknya. Kecerdasan buatan di dalam game di buat beberapa elemen yang dapat berperilaku sealami mungkin layaknya manusia. Masing- masing metode dalam game tersebut mempunyai peran tersendiri dalam model kecerdasan buatan ini.

Di dalam KBE_Fuzzy Metode klasifikasi teks berfungsi untuk mengklasifikasikan teks yang diberikan kepada NPC ke dalam jenis-jenis emosi antara lain senang, sedih, marah dan takut. Sedangkan logika fuzzy berfungsi untuk mengmbil keputusan terhadap respon yang akan dihasilkan oleh NPC sesuai dengan jenis emosi yang diberikan, Untuk lebih memahami model yang kembangkan dalam KBE_Fuzzy ini, dapat digambarkan seperti bagan di bawah ini :

Gambar 1. Model kecerdasan buatan untuk merespon emosi dalam teks.

Proses pertama pada model adalah klasifikasi teks. Seperti yang telah dijelaskan sebelumnya, sumber emosi yang digunakan dalam penelitian ini berasal dari teks berbahasa Indonesia. Yang menjadi pertanyaan, bagaimana mengenali sebuah teks memiliki nilai emosi di dalamnya.

Dalam dunia komputer dikenal bidang ilmu yang bernama data mining. Data mining bertujuan untuk mencari pola yang penting atau menarik dari suatu data tertentu. Dengan menggunakan data mining diharapkan komputer dapat mengenali pola-pola yang ada dalam teks sehingga nantinya dapat menentukan jenis emosi dalam sebuah teks.

Salah satu cara melakukan data mining adalah dengan menggunakan pembelajaran mesin. Pembelajaran mesin adalah bidang ilmu yang mempelajari algoritma yang memungkinkan komputer untuk belajar berdasarkan data yang diterima dari berbagai sumber, misalnya sensor, database, gambar dan teks. Fokus dari penelitian di bidang pembelajaran mesin adalah untuk menghasilkan mesin/komputer yang mampu secara mandiri mengenali pola-pola yang kompleks dan membuat keputusan berdarkan data yang diterima .

Dalam KBE_Fuzzy ini mengunakan salah satu metode dalam pembelajaran terawasi yaitu Naïve Bayes. Dimana Naïve Bayes adalah sebuah metode yang biasa digunakan untuk melakukan proses klasifikasi teks. Teori dari Naïve Bayes sendiri adalah sebagai berikut:

P (A|B) = (P(B|A) * P(A))/P(B)

Rumus di atas dapat dibaca sebagai peluang kejadian A sebagai B ditentukan dari peluang B saat A, Peluang A, dan Peluang B. Agar lebih jelas, dalam kasus klasifikasi emosi dari teks maka rumus di atas akan dirubah menjadi:

P(Ki|T) = (P(T|Ki)*P(Ki)) / P(T)

Dimana P(Ki|D) adalah peluang dokumen teks T pada Kategori Ki. Dengan kata lain rumus tersebut bertujuan untuk menghitung besar peluang suatu dokumen, dalam hal ini sebuah teks dengan kandungan emosi di dalamnya terhadap suatu kategori atau kelas tertentu. Kelas yang dimaksud adalah 4 (empat) jenis emosi yaitu senang, sedih, marah dan takut.

Setelah dilakukan proses klasifikasi, maka akan didapatkan nilai peluang dari sebuah teks untuk masing-masing kelas emosi. Contoh dari proses klasifikasi teks adalah sebagai berikut :

Teks1 = “Saya berhasil lulus ujian semester”

Setelah dilakukan proses klasifikasi akan didapatkan nilai peluang suatu dokumen teks untuk setiap kelas emosi. Di bawah ini adalah contoh hasil yang diharapkan dari proses klasifikasi teks :

P(Senang|teks1)=0,7, Peluang teks1 pada kategori senang sebesar 0,7 (70%).

P(Sedih|teks1)=0,05 Peluang teks1 pada kategori sedih sebesar 0,05 (5%)

P(Takut|teks1)=0,1, Peluang teks1 pada kategori takut sebesar 0,1 (10%)

P(Marah|teks1)= 0,05, Peluang teks1 pada kategori marah sebesar 0,1 (5%)

Nilai peluang yang dihasilkan oleh peroses klasifikasi teks akan menjadi nilai input pada proses fuzzy. Atas dasar itulah logika fuzzy digunakan pada penelitian ini. Dari proses klasifikasi teks diperoleh nilai peluang untuk masing-masing kelas emosi yang sifatnya tidak pasti. Nilai ini akan digunakan sebagai input dalam sistem fuzzy kemudian diproses lebih lanjut untuk menghasilkan nilai atribut yang sesuai dengan jenis emosinya. Dengan menggunakan logika fuzzy diharapkan hasil yang diperoleh bersifat dinamis.

Sebuah sistem yang dibangun menggunakan logika fuzzy pada dasarnya akan mempunyai komponen-komponen sebagai berikut:

1.      Variabel Linguistik

Variabel linguistik merupakan suatu interval numerik dan mempunyai nilai-nilai linguistik, yang semantiknya didefinisikan oleh fungsi keanggotaannya (8) [lihat di daftar refensi penulis].

Dalam penelitian ini akan digunakan empat input untuk proses fuzzy yang masing-masing memiliki tiga variabel linguistik dengan interval [0,1]. Veriabel linguistik yang digunakan yaitu rendah [0-0,4], sedang [0,2-0,8] dan tinggi [0,6-1].

2.      Fuzzification

Fuzzification merupakan proses konversi nilai-nilai kebenaran yang bersifat pasti (crisp input), yang digunakan sebagai inputan, menjadi bentuk fuzzy input, yang berupa nilai linguistik yang semantiknya ditentukan berdasarkan fungsi keanggotaan [8]. Berikut ini adalah contoh proses  fuzzyfication untuk kelas senang. Proses fuzzyfication untuk kelas sedih, marah dan takut menggunakan proses yang sama :

Gambar 2. Grafik fungsi keanggotaan trapesium untuk „senang‟.

Pada gambar di atas dapat dijelaskan bahwa setiap kelas menggunakan fungsi keanggotaan trapesium dan tiga variabel linguistik yaitu rendah, sedang dan tinggi. Nilai dari variabel linguistik ini merepresentasikan besar peluang suatu teks pada proses klasifikasi teks

3.      Inference

Dalam suatu sistem berbasis aturan fuzzy, proses inference memperhitungkan semua aturan yang ada di dalam basis pengetahuan (8)[Lihat di daftar refensi penulis]. Model yang digunakan dalam proses inference pada logika fuzzy terdiri dari dua macam yaitu Sugeno dan Mamdani. Yang membedakan dari kedua model tersebut adalah model sugeno menggunakan perhitungan relatif lebih sederhana dan cepat akan tetapi hasil yang dihasilkan kurang dinamis dan manusiawi. Sedangkan model Mamdani perhitungannya cenderung lebih rumit akan tetapi hasil yang diperoleh lebih dinamis dan manusiawi. Oleh karena pemrosesan emosi membutuhkan hasil yang semanusiawi mungkin, maka dalam penelitian ini digunakan model Mamdani dalam proses inference.

Dalam proses inference didefinisikan aturan fuzzy untuk menentukan atribut dari karakter yang ditunjukkan pada gambar 3 berikut ini :

Gambar 3. Grafik fungsi keanggotaan trapesium untuk „power‟.

Pada gambar di atas dapat dijelaskan bahwa setiap atribut menggunakan fungsi keanggotaan trapesium dan empat variabel linguistik yaitu kurang sekali, kurang, lebih dan lebih sekali. Nilai dari variabel linguistik ini merepresentasikan persentase penambahan nilai atribut dari NPC. Proses inference menggunakan aturan sebagai berikut:

IF          Emosi1 is A

AND Emosi2 is B

AND Emosi3 is C

AND Emosi4 is D

      THEN       Power is E

Dimana emosi1-emosi4 adalah jenis-jenis emosi. B,C dan D adalah variabel linguistik dari emosi yaitu rendah, sedang dan tinggi. Sedangkan E adalah variabel linguistik dari atribut karakter yaitu kurang sekali, kurang, lebih dan lebih sekali.

4.      Defuzzification

Proses defuzzification memiliki bermacam-macam metode yang bisa diaplikasikan untuk menangani berbagai macam masalah. Dalam penelitian ini akan digunakan salah satu metode yang disebut Centroid Method. Metode ini merupakan yang paling penting dan menarik diantara metode yang ada [8]. Metode ini menggunakan rumus sebagai berikut :

y* = ΣyμR(y)

ΣyμR(y)’

Di mana y adalah hasil proses fuzzy dan yμR(y) adalah derajat keanggotaan dari y.

Hasil dari proses defuzzification adalah suatu nilai yang merupakan representasi dari perubahan nilai atribut dari NPC baik itu power, vitality dan agility.

B.  KBC_Minimax

Algoritma minimax diaplikasikan pada permainan yang melibatkan dua orang. Permainan-permainan tersebut dapat dideskripsikan dengan sejumlah 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.

Sebelum menjelaskan algoritma minimax, pengenalan mengenai pohon pencarian dibutuhkan. Pohon pencarian adalah cara untuk merepresentasikan pencarian. Kotak disebut sebagai simpul dan simpul-simpul tersebut merepresentasikan titik keputusan pada pencarian. Simpul dihubungkan dengan cabang. Pencarian dimulai pada simpul akar, ditunjukkan pada bagian atas pada gambar 1. Pada setiap simpul keputusan, simpul berikutnya yang mungkin untuk pencarian dibangkitkan, sampai tidak ada lagi keputusan yang mungkin. Simpul yang merepresentasikan akhir pencarian disebut sebagai simpul daun.

Pada algoritma ini ada dua pemain yang terlibat, kita asumsikan MAX dan MIN. Pohon pencarian dibangkitkan, depth-first, dimulai dari posisi permainan saat ini sampai pada akhir posisi permainan. Lalu, kondisi permainan final dievaluasi sebagai sudut pandang MAX, seperti tergambar pada gambar 1. Setelah itu, simpul-simpul di atas simpul daun diisi secara bottom up dengan nilai pada simpul anak-anaknya. Simpul yang dimiliki pemain MAX menerima nilai maksimum dari simpul anak-anaknya dan pemain MIN memperoleh nilai minimum dari nilai-nilai yang dimiliki simpul anak-anaknya. Berikut gambaran algoritmanya:

‘Nilai’ pada algoritma di atas merepresentasikan seberapa baik permainan bergerak. Pemain MAX akan mencoba memilih gerakan dengan nilai maksimum pada akhirnya sedangkan pemain MIN akan memilih gerakan yang lebih baik baginya, karena itu MIN akan meminimkan keluaran dari MAX (minimizing MAX’s outcome).

1.      Optimasi Algoritma

Pembangkitan seluruh pohon pencarian hanya dimungkinkan jika dan hanya jika permainan yang diimplementasikan sangat sederhana. Pada kebanyakan permainan, hal ini tidak mungkin, oleh karena itu, ada sedikit optimasi yang harus ditambahkan pada algoritma tersebut. Kendati demikian, optimasi ini datang dengan sebuah efek samping. Dengan mengoptimasi, kita menukar informasi seluruhnya tentang permainan dengan kemungkinan dan jalan pintas. Kita tidak lagi memilih jalan yang menghasilkan kemenangan tetapi memilih jalan yang ‘menuju’ ke arah kemenangan. Jika pengoptimasian tidak dipilih dengan bijak, atau salah pengaplikasian, bisa kecerdasan yang dibuat menjadi bodoh dan malahan lebih baik memilih langkah sebarang daripada menggunakan kecerdasan buatan.

Optimasi dasar adalah dengan cara membatasi kedalaman pohon pencarian. Mengapa ini bisa menolong? Membangkitkan seluruh pohon pencarian bisa memakan waktu yang sangat lama. Jika permainan memiliki faktor pencabangan 3 (masing-masing simpul memiliki 3 buah simpul anak), maka pohon pada tingkat akan memiliki simpul sebanyak 3n buah. Pohon pencarian ini juga akan menghasilkan simpul sebanyak jumlah setiap jumlah simpul pada setiap tingkat. Memori tidak akan cukup untuk menampung pohon pencarian pada kebanyakan permainan, seperti catur yang memiliki banyak faktor pencabangan. Walaupun memori mencukupi, tapi proses pembangkitan pohon pencarian akan membutuhkan waktu yang sangat lama.

Jika setiap simpul membutuhkan 1 detik untuk dianalisis, untuk pohon dengan faktor pencabangan 3 dan tingkat=5 akan menghasilkan waktu pembangkitan sebanyak 1+3+9+27+81+243 = 364 * 1 = 364 detik atau sekitar 6 menit! Waktu 6 menit terlalu lamauntuk sebuah permainan. Pemain akan meninggalkan permainan jika harus menunggu masing-masing 6 menit untuk setiap gerakan dari komputer.

Optimasi kedua adalah dengan menggunakan fungsi yang mengevaluasi posisi permainan saat ini dari sudut pandang suatu pemain. Cara ini dilakukan dengan cara memberikan nilai tertentu pada state tertentu pada permainan, seperti menghitung jumlah biji catur yang ada di papan, atau hal lain seperti memberi nilai tertentu pada posisi permainan. Selain mengevaluasi posisi tertentu pada permainan, fungsi ini juga dapat mengkalkulasi bagaimana suatu kondisi dalam permainan dapat membantu mengakhiri permainan. Dengan kata lain, berapa peluang bagi kita untuk memenangkan permainan pada posisi tertentu dalam permainan. Dalam kasus ini, fungsi ini disebut sebagai fungsi estimasi (prekiraan).

Fungsi ini akan menggunakan metode heuristik. Dimana  heuristik adalah pengetahuan yang kita punya dari permainan yang akan membantu membangkitkan fungsi evaluasi yang lebih baik. Sebagai contoh, dalam checkers, biji pada posisi ujung papan tidak bisa dimakan, dan karena itu nilainya akan lebih tinggi bila biji itu berada pada posisi unjung papan. Salah satu alasan fungsi evaluasi harus bisa mengevaluasi posisi permainan untuk kedua pemain adalah karena kita tidak tahu pemain mana yang memiliki batas kedalaman.

Kendati demikian, pembuatan dua fungsi (masingmasing satu untuk pemain) dapat dihindari jika permainan simetrik. Ini berarti bahwa ‘kehilangan’ dari suatu pemain sebanding dengan ‘perolehan’ dari pemain yang satunya. Contoh permainan ini adalah permainan ZERO-SUM. Pada permainan-permainan seperti ini, satu fungsi sudah mencukupi karena pemain yang lain hanya perlu menegasikan kembalian dari fungsi yang pertama. Berikut algoritma minimax setelah dioptimasi:

Celah terbesar yang mungkin terjadi setelah mengaplikasikan optimasi algoritma minimax adalah masalah kedalaman yang terbatas. Posisi permainan yang kelihatan amat baik mungkin saja berubah menjadi sangat buruk. Hal ini dapat terjadi karena algoritma tidak mampu untuk melihat bahwa gerakan yang diambil setelah beberapa langkah ke depan dapat menghasilkan keuntungan yang amat besar bagi pemain lawan.Algoritma tidak melihat gerakan yang berakibat fatal tersebut karena algoritma ini dibutakan oleh batas kedalaman.

2.      Mempercepat Algoritma

Masih ada beberapa cara yang masih dapat dilakukan untuk mengurangi waktu pencarian. Kita lihat gambar 2. Nilai untuk simpul A adalah 3, dan nilai yang ditemukan pertama kali untuk upapohon yang dimulai dari simpul B adalah 2. Maka, karena simpul B ada pada tingkat MIN, kita tahu bahwa dengan nilai yang dipilih untuk B harus lebih kecil atau sama dengan 2. Tapi kita juga tahu bahwa simpul A memiliki nilai 3, dan simpul A dan B keduanya memiliki simpul parent yang sama pada tingkat MAX.

Hal ini dapat diartikan bahwa jalur yang dimulai dari simpul B tudak akan dipilih karena 3 lebih baik daripada 2 pada simpul MAX. Oleh karena itu, pencarian anak-anak simpul B tidak perlu dilakukan dan kita dapat dengan aman mengabaikan sisa anak-anak simpul B.

Gambar 2. Pencarian minimax yang menunjukkan bahwa cabang dapat di-potong

Optimasi ini dikenal dengan nama pemotongan Alpha-Beta (alpha beta cutoffs) dan berikut adalah cara mengaplikasikannya:

1.      Dapatkan nilai alpha dan beta. Alpha adalah nilai yang berisi nilai maksimum yang ditemukan. Beta adalah nilai yang berisi nilai minimum yang ditemukan.

2.      Pada tingkat MAX, sebelum mengevaluasi jalur anak, bandingkan dulu nilai yang dikembalikan dengan jalur sebelumnya dengan nilai beta. Jika nilainya lebih besar, batalkan pencarian untuk simpul ini.

3.      Pada tingkat MIN, sebelum mengevaluasi jalur anak, bandingkan dulu nilai yang dikembalikan dengan jalur sebelumnya dengan nilai alpha. Jika nilainya lebih kecil, batalkan pencarian untuk simpul ini.

Berikut adalah pseudocode algoritma minimax dengan alpha-beta cutoffs.

Seberapa baik minimax dengan alpha-beta cutoffs jika dibandingkan dengan minimax normal benar-benar bergantung pada urutan pencarian dilakukan. Jika cara pembangkitan posisi permainan tidak menciptakan situasi dimana algoritma bisa mengambil keuntungan dari alpha-beta cutoffs, maka peningkatan algoritma tidak akan kelihatan. Kendati demikian, jika evaluasi fungsi dan pembangkitan posisi permainan mengarah pada alpha-beta cutoffs, maka peningkatan algoritma akan sangat baik.

C.     Implementasi Algoritma

Pada pengimplementasian algoritma minimax pada permainan catur jawa ini, penulis menggunakan bahasa pemrograman Java. Pada pengimplementasiannya, catur jawa yang dibuat penulis diberi batasan-batasan khusus. Batasan-batasan ini antara lain : lebar papan hanya dibatasi 7 kotak saja dan tinggi papan hanya 6 kotak saja. Permainan juga selalu dimulai dari bawah untuk menyederhanakan persoalan. Pemain akan memulai permainan dengan cara memilih salah satu kolom dari tujuh buah kolom yang tersedia. Pemain akan mendapatkan simbol ‘X’. Komputer pun akan segera melakukan gerakan untuk melawan pemain sesuai dengan algoritma minimax yang diimplementasikan. Demikian selanjutnya sampai salah satu pemain (kita atau komputer) memperoleh 4 simbol yang sama (‘X’ untuk kita dan ‘O’ untuk komputer) pada baris yang sama, pada kolom yang sama, atau pada diagonal yang sama.

Method-method yang dipakai dalam mengimpelementasikan algoritma ini pada intinya hanya tiga buah, yakni konstruktor caturJawa, fungsi miniMax sebagai algoritma inti pada kecerdasan buatan pada permainan catur jawa ini, dan method fourInARow yang berfungsi untuk menghitung apakah suatu pemain telah memperoleh simbol empat buah yang berurutan. Untuk memperjelas, mari kita lihat algoritmanya :

Berikut adalah variabel global yang digunakan:

Berikut adalah konstruktor caturJawa :

Algoritma miniMax-nya adalah sebagai berikut:

Dan yang terakhir, fungsi FourInARow :

Algoritma lengkap caturJawa.java penulis ini dapat diunduh di http://students.if.itb.ac.id/~if16093/caturJawa.java Pada konstruktor caturJawa, yang dilakukan adalah menunggu masukan user kemudian mengantisipasi masukan user itu dengan memanggil method miniMax dan kemudian membandingkan hasil keluaran method miniMax tersebut. Karena method ini digunakan untuk memaksimalkan langkah komputer, maka yang dicari adalah nilai yang maksimum dari semua keluaran miniMax ini.

Fungsi heuristik pada prosedur miniMax adalah dengan mencari langkah paling cepat menghasilkan akhir permainan. Akhir permainan ini ditentukan dengan menggunakan method FourInARow (jika sudah ada 4 simbol berurutan maka permainan berakhir). Jika sedang berada pada langkah komputer (MAX), algoritma akan mencari nilai minimum yang dihasilkan oleh pemain dan jika berada pada langkah pemain algoritma akan mencari nilai maksimum yang dihasilkan oleh komputer.Fungsi miniMax ini merupakan fungsi rekursif dengan maksimum kedalaman 6. Kedalaman ini dimaksudkan untuk mengoptimasi algoritma miniMax yang dibuat.

D.    Analisis Kompleksitas

Kompleksitas waktu komputer untuk menentukan gerakan selanjutnya sangat ditentukan oleh algoritma minimax yang digunakan. Karena penulis tidak mengimplementasikan alpha-beta cutoffs pada algoritma minimax di atas, maka kasus yang terjadi selalu merupakan kasus terburuk di mana setiap simpul memiliki 7 buah kemungkinan gerakan dengan kedalaman 6. Selain itu, algoritma ini juga menggunakan method fourInARow yang memiliki kompleksitas O(mp) dengan m adalah lebar papan dan p adalah tinggi papan. Oleh sebab itulah algoritma miniMax ini memiliki kompleksitas O(7n) * O(mp) = O(mp7n) dengan n adalah kedalaman maksimum dalam pohon pencarian.

Dengan menggunakan alpha-beta cutoffs, kita dapat mengurangi kebutuhan waktu jika dan hanya jika urutan pembangkitannya mengarah ke arah berakhirnya permainan. Jadi, alpha-beta cutoffs ini hanya berguna pada beberapa kasus saja, tidak selalu berguna pada setiap kasus yang umum. Dengan pengimplementasian alphabeta cutoffs, kompleksitas tetap saja O(mp7n).

3.    Kesimpulan

Berdasarkan hasil percobaan yang telah dilakukan dan di teliti lebih lanjut tentang KBE_Fuzzy(Kecerdasan Buatan dalam Game untuk Merespon Emosi dari Teks Berbahasa Indonesia Menggunakan Klasifikasi Teks dan Logika Fuzzy), dapat diambil kesimpulan sebagai berikut : Klasifikasi emosi dari teks berbahasa Indonesia bisa dilakukan dengan menggunakan metode Naïve Bayes. Hal ini bisa dilihat dari hasil klasifikasi yang menunjukkan nilai peluang dari teks terhadap jenis emosi tertentu. Untuk beberapa teks tertentu, keakuratan klasifikasi masih rendah. Hal ini dapat dilihat dari nilai peluang dari setiap kelas tidak ada yang bernilai dominan. Logika fuzzy dapat digunakan untuk mengambil keputusan dari permasalahan yang mempunyai nilai kepastian yang mutlak. Dalam hal ini logika fuzzy digunakan untuk menentukan nilai atribut NPC dari nilai peluang dari emosi yang nilai kebenarannya tidak mutlak. Sedangkan untuk KBC_Minimax (Kecerdasan Buatan untuk Permainan Catur Jawa Dengan Menggunakan Algoritma Minimax)

Algoritma minimax ini mungkin bukan jawaban terbaik untuk semua jenis permainan yang membutuhkan kecerdasan buatan yang menyerupai manusia. Kendati demikian, algoritma ini sangat cocok untuk diimplementasikan pada permainan-permainan yang melibatkan dua orang, di mana setiap pemain mengetahui semua langkah-langkah yang mungkin dari pemain lawannya seperti catur, catur jawa, checkers, dan lain sebagainya. Perhitungan algoritma yang membutuhkan waktu pencarian yang lama ini dapat dioptimasi dengan beberapa cara, misalnya dengan menggunakan alpha-beta cutoffs atau membatasi kedalaman pohon pencarian. Kompleksitas algoritma minimax bergantung pada kedalaman maksimum pohon pencarian. Kecerdasan buatan untuk permainan catur jawa dapat dibuat dengan menggunakan algoritma minimax.

~Terima Kasih~

Nama : I Made Agus Arya dwijatama

Nim : 100030151

Kelas: J103

Stikom Bali