GAME THEORY

PENGANTAR TEKNOLOGI SISTEM CERDAS

DISUSUN OLEH

SYIFA ALYA NABILA

16115777

3KA12

UNIVERSITAS GUNADARMA

Game Theory atau Teori Permainan adalah suatu pendekatan matematis untuk merumuskan situasi persaingan dan konflik antara berbagai persaingan. Teori ini digunakan untuk menganalisa proses pengambilan keputusan dari situasi persaingan yang berbeda dan melibatkan dua atau lebih pesaing. Intinya, dari teori ini kita berbicara tentang bagaimana stategi dan taktik untuk memenangkan “game” persaingan ekonomi. Seperti game pada umumnya, setiap pesaing disini disebut pemain atau player. Setiap player mempunyai kepentingan-kepentingan untuk bersaing dalam permintaan. Anggapan yang digunakan adalah setiap pemain mempunyai kemampuan untuk mengambil keputusan secara bebas dan rasional. Setiap pelaku ekonomi terutama produsen atau agen pastinya saling bersaing untuk mewujudkan kepentingan-kepentingannya. Setiap pemain akan menggunakan berbagai strategi agar mendapatkan keuntungan yang optimal dan jika harus mengalami kerugian maka bagaimana caranya agar kerugian itu paling kecil.

Awalnya, teori ini ditemukan oleh ahli matematika Prancis Emile Borel pada tahun 1921. Kemudian dikembangkan oleh John Von Neeman dan Oskar Morgenstern sebagai tolak ukur untuk merumuskan perilaku ekonomi yang bersaing. Teori permainan ini dapat diklasifikasikan dalam beberapa model, contohnya model teori permainan antara lain seperti:

· Jumlah pemain

· Jumlah keuntungan dan kerugian 

· Jumlah strategi yang digunakan dalam permainan

Unsur-unsur Dasar Teori Game

1. Jumlah Pemain

Permainan diklasifikasikan menurut jumlah kepentingan atau tujuan yang ada dalam permainan tersebut. Dalam hal ini perlu dipahami, bahwa pengertian “jumlah pemain” tidak selalu sama artinya dengan “jumlah Orang” yang terlibat dalam permainan. jumlah pemain disini berarti jumlah kelompok pemain berdasarkan masing-masing kepentingan atau tujuannya. Dengan demikian dua orang atau lebih yang mempunyai kepentingan yang sama dapat diperhitungkan sebagai satu kelompok pemain.

2. Pay-off

Ganjaran / pay-off adalah hasil akhir yang terjadi pada akhir permainan berkenaan dengan ganjaran ini, permainan digolongkan menjadi 2 macam kategori, yaitu permainan jumlah-nol (zero-sum games) dan permainan jumlah-bukan-nol (non-zero-sum games). permainan jumlah-nol terjadi jika jumlah ganjaran dari seluruh pemain adalah nol, yaitu dengan memperhitungkan setiap keuntungan sebagai bilangan positif dan setiap kerugian sebagai bilangan negatif. Selain dari itu adalah permainan jumlah – bukan-nol. Dalam permainan jumlah-nol setiap kemenangan bagi suatu pihak pemain merupakan kekalahan bagi pihak pemain lain. letak arti penting dari perbedaan kedua kategori permainan berdasarkan ganjaran ini adalah bahwa permainan jumlah-nol adalah suatu sistem yang tertutup. Sedangkan permainan jumlah-bukan-nol tidak demikian halnya. Hampir semua permainan pada dasarnya merupakan permainan jumlah-nol. Berbagai situasi dapat dianalisis sebagai permainan jumlah-nol.

3. Strategi Permainan

Setiap permainan yang dianalisis dengan teori permainan selalu dapat disajikan dalam bentuk sebuah matriks permainan. matriks permainan disebut juga matriks ganjaran yaitu sebuah matriks yang semua unsur berupa ganjaran dari para pemain yang terlibat dalam permainan tersebut. Baris-barisnya melambangkan strategi –strategi yang dimiliki pemain pertama, sedangkan kolom-kolomnya melambangkan strategi-strategi yang dimiliki pemain lain. dengan demikian, permainan berstrategi mxn dilambangkan dengan matriks permainan m x n . Teori permainan berasumsi bahwa strategi yang tersedia bagi masing-masing pemain dapat dihitung dan ganjaran yang berkaitan dengannya dapat dinyatakan dalam unit, meskipun tidak selalu harus dalam unit moneter. Hal ini penting bagi penyelesaian permainan, yaitu untuk menentukan pilihan strategi yang akan dijalankan oleh masing-masing pemain, dengan menganggap bahwa masing masing pemain berusaha memaksimumkan keuntungannya yang minimum (maksimin) atau meminimumkan kerugiannya yang maksimum (minimaks). Nilai dari suatu permainan adalah ganjaran rata-rata / ganjaran yang diharapkan dari sepanjang rangkaian permainan, dengan menganggap kedua pemain selalu berusaha memainkan strateginya yang optimum. 

4. Titik Pelana (Saddle Point) 

Titik pelana adalah suatu unsur didalam matriks permainan yang sekaligus sebagai maksimin baris dan minimaks kolom. permainan dikatakan bersaing ketat (Strictly determined) jika matriksnya memiliki titik pelana. Strategi yang optimum bagi masing-masing pemain adalah strategi pada baris dan kolom yang mengandung titik pelana tersebut. dalam hal ini baris yang mengandung titik pelana merupakan strategi optimum bagi pemain pertama, sedangkan kolom yang mengandung titik pelana merupakan strategi optimum bagi pemain lain. Langkah pertama penyelesaian sebuah matriks permainan adalah memeriksa ada atau tidaknya titik pelana. Bila terdapat titik pelana permainan dapat segera dianalisis untuk diselesaikan. Untuk menentukan titik pelana biasanya dilakukan dengan menuliskan nilai-nilai minimum dan Maksimum masing-masing kolom, kemudian menentukan maksimun diantara minimum baris dan minimum diantara maksimum kolom. jika unsur maksimum dari minimum baris sama dengan unsur minimum dari maksimum kolom, atau jika maksimin = minimaks, berarti unsur tersebut merupakan titik pelana.

Teori permainan dapat diterapkan dalam berbagai bidang, meliputi kemiliteran, bisnis, social, ekonomi dan ekologi. Sebagai contoh pada dunia bisnis, seorang direktur suatu perusahaan didalam memperkenalkan sebuah produk baru berusaha mengetahui kemungkinan strategi paling baik atau suatu kombinasi strategi untuk merebut market share yang lebih besar, sementara saingannya juga mencoba meperkenalkan produk sejenis dengan strategi yang berbeda dengan direktur pemasaran tersebut, antara lain: penurunan harga, pemberian hadiah, peningkatan mutu produk, memilih media advertasi yang efektif. Disinilah peranan teori permainan untuk menentukan strategi mana yang akan diputuskan oleh dirktur pemasaran tersebut untuk merebut pasar.

Penyelesaian masalah teori permainan :

Untuk menyelesaikan masalah dalam teori permainan, dapat menggunakan karakteristik strategi murni dan strategi campuran.

1. Strategi Murni (Pure Strategy Game)

Hasil yang optimal dari suatu permainan yang mempunyai saddle point dapat diperoleh dengan menggunakan pure strategy. Yang dimaksud dengan saddle point adalah semacam titik keseimbangan antara nilai permainan kedua pemain. Dalam pure strategy digunakan kriteria maksimim dan minimaks. Maksimin adalah nilai maksimum dari nilai-nilai minimum, dan minimaks adalah nilai minimum dari nilai-nilai maksimum.

Contoh kasus :

Dua perusahaan yang memiliki produk yang relatif sama bersaing mendapatkan keuntungan. Perusahaan A menggunakan dua strategi dan perusahaan B menggunakan tiga strategi. 

Langkah-langkah penyelesaian dengan pure strategy :

Identifikasi perusahaan yang berperan sebagai pemain kolom dan baris. Dalam kasus diatas, perusahaan A sebagai pemain baris dan perusahaan B sebagai pemain kolom. Lalu pilih nilai terkecil untuk setiap baris. Baris pertama memiliki nilai terkecil “1” dan baris kedua nilai terkecilnya “4”. Kemudian dari kedua nilai tersebut pilih nilai yang paling baik atau terbesar yaitu “4”. Nilai “4” inilah yang disebut nilai maksimin.

Untuk pemain kolom (perusahaan B), pilih nilai yang paling besar untuk setiap kolom, sehingga diperoleh angka “8” untuk kolom pertama, angka “9” untuk kolom kedua, dan angka “4” untuk kolom ketiga. Dari ketiga angka tersebut pilih angka terendah atau minimum yaitu “4”. Nilai “4” inilah yang disebut nilai minimaks. 

Dari kedua langkah diatas, didapat angka “4” sebagai nilai permainan (saddle point) sehingga tercipta strategi yang optimal.

Yang di maksud hasil optimal disini adalah dimana masing-masing pemain memilih nilai 4 yang mengandung arti bahwa pemain A meskipun menginginkan keuntungan yang lebih besar, namun A hanya akan mendapat keuntungan maksimal sebesar 4, bila ia menggunakan strategi harga mahal (S2). Sedangkan pemain B, meskipun menginginkan kerugian yang dideritanya adalah sekecil mungkin, namun kerugian yang paling baik bagi B adalah sebesar 4, dan itu bisa diperoleh dengan merespon strategi yang digunakan A dengan juga menerapkan strategi harga mahal (S3).

2. Strategi Campuran (Mixed Strategy Game)

Strategi ini dilakukan apabila strategi murni tidak mampu menyelesaikan memberikan pilihan strategi yang optimal bagi masing masing pemain atau perusahaan atau dengan kata lain kasus game theory tidak mempunyai saddle point. Dalam strategi ini seorang pemain atau perusahaan akan menggunakan campuran lebih dari satu strategi untuk mendapatkan hasil yang maksimal. 

Dalam strategi campuran ini ada beberapa metode yang biasa digunakan yaitu :

· Metode Analistis

· Metode Grafik

· Pemrograman Linier

Algoritma Minimax

Minimax yang merupakan salah satu metode penerapan (implementasi) pohon n-ary pada suatu game, menandakan bahwa implementasi struktur (pohon khusunya) sangatlah diperlukan pada pembuatan dan penerapan Artificial Intelligence, dan tidak menutup kemungkinan ilmu dan metode baru yang lebih canggih akan ditemukan di masa depan.

Gambar 1.1

Algoritma minimax merupakan basis dari semua permainan berbasis AI seperti permainan catur misalnya. AI permainan catur tentunya sudah sangat terkenal dimana AI tersebut bahkan dapat mengalahkan juara dunia sekalipun. 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. Keuntungan yang didapat dengan menggunakan algoritma minimax yaitu algoritma minimax mampu menganalisis segala kemungkinan posisi permainan untuk menghasilkan keputusan yang terbaik karena algoritma minimax ini bekerja secara rekursif dengan mencari langkah yang akan membuat lawan mengalami kerugian minimum. Semua strategi lawan akan dihitung dengan algoritma yang sama dan seterusnya. Ini berarti, 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 tersebut dibutuhkan suatu nilai yang merepresentasikan kerugian atau keuntungan yang akan diperoleh jika langkah tersebut dipilih. Untuk itulah disini digunakan sebuah fungsi heurisitic untuk mengevaluasi nilai sebagai nilai yang merepresentasikan hasil permainan yang akan terjadi jika langkah tersebut dipilih. Biasanya 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 heuristic yang akan menuntun permainan ke hasil akhir yang menguntungkan bagi komputer.

Algoritma minimax merupakan algoritma yang diterapkan dalam game yang melibatkan dua pemain yang saling bergantian, seperti tic-tac-toe, chess, go, othello dan game yang menggunakan strategi atau logika lainnya. Persamaan antara semua game tersebut yaitu semua merupakan game logika dan game dengan informasi yang lengkap. Ini berarti bahwa game merupakan sekumpulan aturan main dan dasar pemikiran yang logis. Adanya aturan main dan dasar pemikiran yang logis tersebut, maka nantinya setiap pemain dapat mengetahui semua langkah yang mungkin dari pemain lawannya, sehingga pemain bisa tetap “memantau” kondisi permainan sewaktu game sedang berlangsung .

 Gambar 1.2

Algoritma minimax merupakan salah satu algoritma yang sering digunakan untuk game kecerdasan buatan yang menggunakan teknik depth first search (DFS) dalam pencariannya pada pohon dengan kedalaman terbatas. Algoritma minimax digunakan untuk memilih langkah terbaik, dimana kedua pemain akan saling berusaha untuk memenangkan permainan. Selain itu, algoritma minimax ini bekerja secara rekursif dengan mencari langkah yang akan membuat lawan mengalami kerugian minimum. Algoritma minimax mendeskripsikan kondisi apabila terdapat pemain yang mengalami keuntungan, pemain lain akan mengalami kerugian senilai dengan keuntungan yang diperoleh lawan dan sebaliknya.

Algoritma minimax akan melakukan pengecekan pada seluruh kemungkinan yang ada, sehingga akan menghasilkan pohon permainan yang berisi semua kemungkinan permainan. Dengan pohon permainan ini setiap pemain mengetahui langkah-langkah yang mungkin diberikan pada situasi permainan saat ini. Sehingga untuk setiap langkah dan semua langkah selanjutnya dapat diketahui. Dalam repersentasi pohon pada algoritma minimax, terdapat dua jenis simpul, yaitu simpul min dan simpul max. Max akan memilih langkah dengan nilai tertinggi dan min akan memilih langkah dengan nilai terendah . Dalam penentuan keputusan max/min tersebut dibutuhkan suatu nilai yang merepresentasikan kerugian atau keuntungan yang akan diperoleh jika langkah tersebut dipilih. Untuk itulah disini digunakan sebuah fungsi heuristik.

Fungsi heuristik yang digunakan algoritma ini adalah fungsi heuristik statis . Fungsi heuristik digunakan untuk mengevaluasi nilai sebagai nilai yang merepresentasikan hasil permainan yang akan terjadi jika langkah tersebut dipilih. Dari nilai-nilai heuristik inilah komputer akan menentukan simpul mana dari pohon permainan yang akan dipilih, tentunya simpul yang akan dipilih tersebut adalah simpul dengan nilai heuristik yang akan menuntun permainan ke hasil akhir yang menguntungkan bagi komputer. Untuk proses dan cara kerja algoritma yang lebih jelasnya lagi, dapat dilihat pada Gambar 1.2 yang merepresentasikan cara kerja algoritma Minimax.Fungsi heuristik yang digunakan algoritma ini adalah fungsi heuristik statis. Fungsi heuristik digunakan untuk mengevaluasi nilai sebagai nilai yang merepresentasikan hasil permainan yang akan terjadi jika langkah tersebut dipilih. Dari nilai-nilai heuristik inilah komputer akan menentukan simpul mana dari pohon permainan yang akan dipilih, tentunya simpul yang akan dipilih tersebut adalah simpul dengan nilai heuristik yang akan menuntun permainan ke hasil akhir yang menguntungkan bagi komputer.

Transpotition Table and Memory

1. Algoritma dapat menggunakan tabel transposisi untuk menghindari melakukan pekerjaan ekstra dalam mencari posisi board yang sama beberapa kali

2. Memori kerja posisi board sudah dikenal

3. Menggunakan fungsi hash khusus desiderata: sebarkan posisi-posisi yang mirip seluas mungkin melalui kisaran nilai hash nilai hash yang banyak berubah saat berpindah dari papan bergerak mengalami perubahan yang sangat sedikit.

4. Kunci zobrist adalah sekumpulan bit acak dari fixed-length pola yang tersimpan untuk setiap kemungkinan keadaan dari setiap lokasi yang mungkin ada pada board. Contoh: Catur memiliki 64 kotak, dan masing-masing persegi bisa kosong atau ada 1 dari 6 potongan berbeda di atasnya, masing-masing dua warna mungkin.Zobrist kunci harus seperti berikut : 64 2 (6 + 1) = 832 bit-string yang berbeda.

· Kunci Zobrist perlu diinisialisasi dengan bit-string acak dengan ukuran yang sesuai.

· Untuk setiap kotak yang tidak kosong, tombol Zobrist adalah mendongak dan XORed dengan jumlah hash yang berjalan.

· Zobrist Key dapat diperbarui secara bertahap

Apa yang harus disimpan?

· Tabel hash menyimpan nilai yang terkait dengan posisi board

· Gerakan terbaik dari posisi masing-masing board.

· Kedalaman digunakan untuk menghitung nilai

· Nilai yang akurat, atau kita dapat juga menyimpan nilai "fail-soft" yang dihasilkan dari sebuah cabang yang dipangkas

· Nilai akurat atau nilai gagal-rendah (alpha pruned), atau nilai gagal-tinggi (beta pruned)

SUMBER:

https://rilekrider.wordpress.com/2013/12/30/game-theory/

http://abyantama-el.blogspot.co.id/2017/01/algoritma-minimax.html

TEKNIK PEMBANGUNAN GAME AI

PENGANTAR TEKNOLOGI SISTEM CERDAS

Disusun Oleh:

Syifa Alya Nabila

16115777

3KA12

Universitas Gunadarma

TEKNIK PEMBANGUNAN GAME AI

Di dunia akademis, bidang kecerdasan buatan dipelajari secara serius untuk meningkatkan kualitas hidup manusia. Para peneliti dan mahasiswa (ilmu komputer atau teknik informatika) terus menerus mengembangkan teknik-teknik pada bidang ini untuk menghasilkan mesin yang semakin mengerti, dan memahami kebutuhan manusia. Dalam game berbasis kecerdasan buatan, ada banyak teknik yang diadaptasi dari bidang kecerdasan buatan untuk diterapkan pada game.

beberapa diantaranya, yaitu:

1. Mengejar dan Menghindar

Mengejar dan menghindar merupakan teknik dasar yang diterapkan pada banyak game berbasis kecerdasan buatan dari yang sederhana sampai yang kompleks. apakah itu space shooters, RPG, atau game strategi. metode paling umum pada teknik mengejar dan menghindar ini adalah melakukan pemutakhiran (update) koordinat terhadap objek yang menjadi sasaran. Posisi relatif dan kecepatan dapat dijadikan sebagai parameter pada algoritma mengejar dan menghindar. Metode Line-of-sight yang membutuhkan dasar rumus persamaan garis juga serngkali dijadikan basis metode mengejear dan menghindar.

2. Pola Pergerakan

Pola pergerakan merupakan cara yang sederhana untuk memberikan ilusi kecerdasan pada sebuah game. Game Galaga adalah contoh klasik penerapan pola pergerakan ini, dimana pesawat musuh dapat bergerak secara melingkat atau mengikuti pola garis lurus yang ditentukan. Contoh lain penerapan pola pergerakan adalah pada game first-person shooter yang menampilkan monster yang sedang berpatroli pada jalur tertentu, pada game simulasi pertempuran pesawat dimana pesawat musuh dapat melakukan manuver-manuver di udara yang menyulitkan kita mengejar, atau karakter-karakter non-player (figuran) seperti kambing yang sedang berjalan membutuhkan teknik pola pergerakan ini. Metode standar untuk menerapkan pola pergerakan adalah dengan cara menyimpan pola tersebut dalam suatu array. Array tersebut terdiri dari serangkaian koordinat atau perintah pergerakan dengan pola tertentu untuk mengontrol koordinat dari objek. Dengan metode ini, bisa didapatkan pola-pola pergerakan seperti melingkar, garis lurus, zig-zag atau bahkan kurva tak beraturan.

3. Pathfinding

Metode pathfinding paling mudahditemui pada game-game bertipe strategi dimana kita menunjuk satu tokoh untuk digerakkan ke lokasi tertentu dengan mengklik lokasi yang hendak dituju. Si tokoh akan segera bergerak ke arah yang ditentukan, dan secara “cerdas” dapat menemukan jalur terpendek ataupun menghindari dari rintangan-rintangan yang ada. Salah satu algoritma pathfindin yang cukup umum dan yang paling banyak digunakan utnuk mencari jarak terpendek secara efisien adalah algoritma A* (baca: A star). Secara umum, algoritma A* adalah mendefinisikan area pencarian menjadi sekumpulan node-node (tiles). Titik awal dan titik akhir ditentukan terlebih dulu untuk mulai penelusuran pada tiap-tiap node yang memungkinkan untuk ditelusuri. Dari sini, akan diperoleh skor yang menunjukkan besarnya biaya untuk menempuh jalur yang ditemukan, ditambah dengan nilai heuristik yang merupakan nilai biaya estimasi dari node yang ada menuju tujuan akhir. Iterasi akan dilakukan hingga akhirnya mencapai target yang dituju.

4. Jaringan saraf tiruan (neural network)

Neural network cukup baik ketika diterapkan pada kasus-kasus yang sifatnya non-linier atau mengambil keputusan yang tidak dapat dilakukan dengan metode tradisional. Penerapannya seringkali pada game-game yang memerlukan kemampuan adaptif atau belajar dari pengalaman. Sebagai contoh, jika suatau ketika terjadi pertempuran antar player dengan unit komputer, dan unit komputer mengalami kekalahan, maka pada kesempatan lain yang serupa, komputer akan memilih untuk tidak bertempur. Semakin banyak pengalaman yang dialami komputer, maka komputer menjadi semakin cerdas. Prinsip dasar dari jaringan saraf tiruan ini adalah perbaikan bobot secara terus menerus agar output yang dihasilkan menjadi semakin akurat (semakin cerdas). 5. Algoritma Genetis (genetic algorithm) Algoritma genetis sedikit banyak dipengaruhi oleh teori evolusi yang dicetuskan Darwin, yaitu bahwa spesies akan terus menerus beradaptasi dengan lingkungannya dan ciri khasnya yang terletak pada kromosom, akan diturunkan pada generasi berikutnya. Generasi turunan ini menerima gabungan kromosom dari kedua induknya, yang disebut dengan crossover. Pada algoritma genetis, akan diterapkan langkah ranking fitness untuk melakukan seleksi terhadap langkah ranking fitness untuk melakukan seleksi terhadap generasi turunan yang terbaik. Pada game berbasis algorima genetis, turunan terbaik inilah yang dilibatkan ke dalam game, dimana akan digunakan oleh komputer untuk merespons perubahan-perubahan tingkah laku user.   sebenarnya bukan hanya 5 teknik kecerdasan buatan di atas yang dapat digunakan dalam sebuah game berbasis kecerdasan buatan. Beberapa teknik lain yang umum digunakan antara lain: finite state machine, fuzzy logic, ruled-based AI, basic probability,  dan keputusan tak pasti (dengan menggunakan teknik Bayesian) Di masa-masa mendatang, dengan dukungan teknologi hardware yang semakin baik, teknik kecerdasan buatan pada game berbasis kecerdasan buatan akan semakin matang dengan ilusi kecerdasan yang semakin menyerupai manusia.   sumber : majalah pc mild 20/2009.

5. Decision Making

Decision Making adalah serangkaian algoritma yang dirancang dengan memasukan beberapa kemungkinan langkah yang bisa diambil oleh suatu aplikasi, Pada game ini decision making memberikan kemampuan suatu karakter untuk menentukan langkah apa yang akan diambil. Decision making dilakukan dengan cara menentukan satu pilihan dari list yang sudah dibuat pada algoritma yang dirancang. Algoritma decision making kerap digunakan dalam aplikasi game, akan tetapi algoritma decision making dapat diimplementasikan pada banyak aplikasi lain.

Decision Making terbagi menjadi 3 yaitu : Decision Tree, State Machine dan Rule System

1.      Decision Tree

Pohon Keputusan (Decision Tree) merupakan metode klasifikasi dan prediksi yang sangat kuat dan terkenal. Metode pohon keputusan mengubah fakta yang sangat besar menjadi pohon keputusan yang merepresentasikan aturan. Aturan dapat dengan mudah dipahami dengan bahasa alami. Aturan ini juga dapat diekspresikan dalam bentuk bahasa basis data seperti SQL untuk mencari record pada kategori tertentu. Pohon keputusan juga berguna untuk mengeksplorasi data, menemukan hubungan tersembunyi antara sejumlah calon variabel input dengan sebuah variabel target. Karena pohon keputusan memadukan antara eksplorasi data dan pemodelan, pohon keputusan ini sangat bagus sebagai langkah awal dalam proses pemodelan bahkan ketika dijadikan sebagai model akhir dari beberapa teknik lain(J R Quinlan, 1993).

Variabel tujuan biasanya dikelompokkan dengan pasti dan model pohon keputusan lebih mengarah pada perhitungan probabilitas dari masing-masing record terhadap kategori-kategori tersebut, atau untuk mengklasifikasi record dengan mengelompokkannya dalam satu kelas. Pohon keputusan juga dapat digunakan untuk mengestimasi nilai dari variabel kontinyu, meskipun ada beberapa teknik yang lebih sesuai untuk kasus ini.

Kelebihan dari metode pohon keputusan adalah:

Daerah pengambilan keputusan yang sebelumnya kompleks dan sangat global, dapat diubah menjadi lebih simpel dan spesifik

Eliminasi perhitungan-perhitungan yang tidak diperlukan, karena ketika menggunakan metode pohon keputusan maka sampel diuji hanya berdasarkan kriteria atau kelas tertentu

Fleksibel untuk memilih fitur dari node internal yang berbeda, fitur yang terpilih akan membedakan suatu kriteria dibandingkan kriteria yang lain dalam node yang sama. Kefleksibelan metode pohon keputusan ini meningkatkan kualitas keputusan yang dihasilkan jika dibandingkan ketika menggunakan metode penghitungan satu tahap yang lebih konvensional

Dalam analisis multivarian, dengan kriteria dan kelas yang jumlahnya sangat banyak, seorang penguji biasanya perlu mengestimasikan baik itu distribusi dimensi tinggi ataupun parameter tertentu dari distribusi kelas tersebut. Metode pohon keputusan dapat menghindari munculnya permasalahan ini dengan menggunakan kriteria yang jumlahnya lebih sedikit pada setiap node internal tanpa banyak mengurangi kualitas keputusan yang dihasilkan.

      Kekurangan pada pohon keputusan adalah:

·         Terjadi overlapping terutama ketika kelas-kelas dan kriteria yang digunakan jumlahnya sangat banyak. Hal tersebut juga dapat menyebabkan meningkatnya waktu pengambilan keputusan dan jumlah memori yang diperlukan

·         Pengakumulasian jumlah kesalahan dari setiap tingkat dalam sebuah pohon keputusan yang besar Kesulitan dalam mendesain pohon keputusan yang optimal Hasil kualitas keputusan yang didapatkan dari metode pohon keputusan sangat tergantung pada bagaimana pohon tersebut didesain.

        Pohon keputusan adalah model prediksi menggunakan struktur pohon atau struktur berhirarki. Setiap percabangan menyatakan kondisi yang harus dipenuhi dan tiap ujung pohon menyatakan kelas data. Contoh pada Gambar diatas adalah identifikasi pembeli komputer. Dari pohon keputusan tersebut diketahui bahwa salah satu kelompok yang potensial membeli komputer adalah orang yang berusia di bawah 30 tahun dan juga pelajar. Setelah sebuah pohon keputusan dibangun maka dapat digunakan untuk mengklasifikasikan record yang belum ada kelasnya. Dimulai dari node root, menggunakan tes terhadap atribut dari record yang belum ada kelasnya ini lalu mengikuti cabang yang sesuai dengan hasil dari tes tersebut, yang akan membawa kepada internal node (node yang memiliki satu cabang masuk dan dua atau lebih cabang yang keluar), dengan cara harus melakukan tes lagi terhadap atribut atau node leaf. Record yang kelasnya tidak diketahui kemudian diberikan kelas yang sesuai dengan kelas yang ada pada node leaf. Pada pohon keputusan setiap simpul leaf menandai label kelas. Proses dalam pohon keputusan yaitu mengubah bentuk data (tabel) menjadi model pohon (tree) kemudian mengubah model pohon tersebut menjadi aturan (rule) (J R Quinlan, 1993).

        Salah satu algoritma induksi pohon keputusan yaitu ID3 (Iterative Dichotomiser 3). ID3 dikembangkan oleh J. Ross Quinlan. Dalam prosedur algoritma ID3, input berupa sampel training, label training dan atribut. Algoritma Decision Tree C4.5 merupakan pengembangan dari ID3. Sedangkan pada perangkat lunak open source WEKA mempunyai versi sendiri dari C4.5 yang dikenal sebagai J48.

2. State Machine

        Finite State Machines (FSM) adalah sebuah metodologi perancangan sistem kontrol yang menggambarkan tingkah laku atau prinsip kerja sistem dengan menggunakan tiga hal berikut: State (Keadaan), Event (kejadian) dan action (aksi). Pada satu saat dalam periode waktu yang cukup signifikan, sistem akan berada pada salah satu state yang aktif. Sistem dapat beralih atau bertransisi menuju state lain jika mendapatkan masukan atau event tertentu, baik yang berasal dari perangkat luar atau komponen dalam sistemnya itu sendiri (misal interupsi timer). Transisi keadaan ini umumnya juga disertai oleh aksi yang dilakukan oleh sistem ketika menanggapi masukan yang terjadi. Aksi yang dilakukan tersebut dapat berupa aksi yang sederhana atau melibatkan rangkaian proses yang relative kompleks.

        Berdasarkan sifatnya, metode FSM ini sangat cocok digunakan sebagai basis perancangan perangkat lunak pengendalian yang bersifat reaktif dan real time. Salah satu keutungan nyata penggunaan FSM adalah kemampuannya dalam mendekomposisi aplikasi yang relative besar dengan hanya menggunakan sejumlah kecil item state. Selain untuk bidang kontrol, Penggunaan metode ini pada kenyataannya juga umum digunakan sebagai basis untuk perancangan protokol-protokol komunikasi, perancangan perangkat lunak game, aplikasi WEB dan sebagainya.

        Dalam bahasa pemrograman prosedural seperti bahasa C, FSM ini umumnya direalisasikan dengan menggunakan statemen kontrol switch case atau/dan if..then. Dengan menggunakan statemen-statemen kontrol ini, aliran program secara praktis akan mudah dipahami dan dilacak jika terjadi kesalahan logika.

3. Rule Systems

Rule Based System merupakan metode pengambilan keputusan berdasarkan pada aturan-aturan tertentu yang telah ditetapkan. RBS dapat diterapkan pada agen virtual dalam bentuk kecerdasan buatan sehingga dapat melakukan tindakan tertentu. Tindakan tersebut direpresentasikan oleh set aturan yaitu penyebab tindakan itu terjadi, proses tindakan dan hasil dari tindakan tersebut.

Rule Base Systems (RBS) sistem yang baik untuk mendapat jawaban dari pertanyaan mengenai What (apa), How (bagaimana) dan Why (mengapa) dari Rule Base (RB) selama proses inferensia. Jawaban dan penjelasannya dapat disediakan dengan baik. Masalah yang ada dengan SBP adalah ia tak dapat secara mudah menjalankan proses akuisisi knowledge (pengetahuan) dan ia tak dapat mengupdate rule (aturan) secara otomatis. Hanya pakar yang dapat mengupdate Knowledge Base (KB) secara manual dengan dukungan dari knowledge engineer (insinyur pengetahuan). Lebih jauh kebanyakan peneliti dalam SBA lebih memperhatikan masalah optimasi pada rule yang sudah ada daripada pembangkitan rule baru dari rule yang sudah ada. Namun demikian, optimasi rule tak dapat mengubah hasil dari inferensia secara signifikan, yaitu dalam hal cakupan pengetahuan.

Ripple Down Rule (RDR) datang untuk mengatasi permasalahan utama dari sistem pakar: pakar tak perlu lagi selalu mengkomunikasikan pengetahuan dalam konteks yang spesifik. RDR membolehkan akuisisi yang cepat dan sederhana secara ekstrim tanpa bantuan dari knowledge engineer. Pengguna tak perlu menguji RB dalam rangka mendefinisikan rule baru: pengguna hanya perlu untuk mampu mendefinisikan rule baru yang secara benar mengklasifikasikan contoh yang diberikan, dan sistem dapat menentukan dimana suatu rule harus ditempatkan dalam hirarki rulenya. Keterbatasan dari RDR adalah kekurangan dalam hal inferensia yang berdayaguna. Tak seperti SBA yang dilengkapi dengan inferensia melalui forward dan backward chaining, RDR kelihatannya menggunakan Depth First Search (DFS) yang memiliki kekurangan dalam hal fleksibelitas dalam hal penjawaban pertanyaan dan penjelasan yang tumbuh dari inferensia yang berdayaguna.

Variable-Centered Intelligent Rule System (VCIRS) merupakan perkawinan dari SBA dan RDR. Arsitektur sistem diadaptasi dari SBA dan ia mengambil keuntungan-keuntungan yang ada dari RDR.

untuk meningkatkan kinerja sistem dari pengguna sistem selama pembangunan pengetahuan (melalui analisis nilai) dan penghalusan pengetahuan (dengan pembangkitan rule).

Path Finding

        Metode Path Finding seringkali dijumpai pada game yang bergenre strategi, dimana kita sebagai user menunjuk satu karakter untuk digerakkan ke lokasi tertentu dengan cara mengklik lokasi yang akan dituju. Maka, si karakter tersebut akan bergerak ke arah yang telah ditentukan, dan secara “cerdas” dapat menemukan jaur terpendek ataupun menghindari rintangan yang ada.

Metode pada Path Finding terbagi menjadi 4 bagian yaitu:

1. Waypoints

        Merupakan titik acuan/kumpulan koordinat yang digunakan untuk keperluan navigasi. Maksud dari keperluan navigasi disini adalah mengidentifikasi sebuah titik dipeta. Disetiap koordinat biasanya menyertakan longitude, latitude, dan terkadang altitude untuk keperluan navigasi di udara.

2. A* Searching

        Algoritma A* merupakan yang sering digunakan pada game yang menggunakan metode pathfinding. Algoritma ini dipilih karena A* sangat mudah untuk diimplementasikan dan sangat efisien. Dengan menggunakan algoritma A* kita dapat menentukan jalur terpendek. Pada algotitma ini akan menyeleksi dengan cara membuang langkah yang tidak perlu dengan mempertimbangkan bahwa langkah yang dibuang dipastikan tidak mencapai solusi yang diinginkan.

        Prinsip dari algoritma ini yaitu dengan cara mencari jalur terpendek dari sebuah simpul awal (Starting Point) menuju ke simpul tujuan dengan memperhatikan harga (F) terkecil. Algoritma A* akan memperhitungkan cost dari current state ke tujuan dengan fungsi heuristic, selain itu algoritma ini juga mempertimbangkan cost yang telah ditempuh selama ini dari initial state ke current state. Jadi maksudnya jika jalan yang telah ditempuh terlalu panjang dan ada jalan lain yang cost nya lebih kecil tetapi memberikan posisi yang sama jika dilihat dari goal, maka jalan yang lebih pendeklah yang akan dipilih.

3. Dijkstra

        Algoritma Dijkstra yang dinamai penemunya yakni seorang ilmuwan komputer, Edsger Dijkstra merupakan sebuah algoritma yang rakus atau biasa dikenal dengan algoritma greedy. Algoritma ini biasa dipakai dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph) dengan bobot-bobot sisi (edge weights) yang bernlai positif.

4. Tactical Pathfinding

        Tactical Pathfinding merupakan algoritma pencarian jalur yang bisa melakukan pencarian jalur terpendek dengan menghitung bobot ancaman. Implementasi algoritma ini dapat memberikan gerakan taktis pada non-player character. Algoritma ini dilakukan berdasarkan algoritma pencarian jalur A* yang ditambah dengan perhitungan bobot.

SUMBER:
http://dunotifkejora.blogspot.co.id/2016/04/kecerdasan-buatan-ai-pada-game.html

KECERDASAN BUATAN & PERMAINAN ( AI & GAMES )

PENGANTAR TEKNOLOGI SISTEM CERDAS

Disusun Oleh:

Syifa Alya Nabila

16115777

3KA12

Universitas Gunadarma

A.     Pengertian Kecerdasan Buatan

Kecerdasan buatan (Artificial Intelligence) adalah kecerdasan yang ditunjukkan oleh suatu entitas buatan. Sistem seperti ini umumnya dianggap komputer. Kecerdasan diciptakan dan dimasukkan ke dalam suatu mesin (komputer) agar dapat melakukan pekerjaan seperti yang dapat dilakukan manusia. Beberapa macam bidang yang menggunakan kecerdasan buatan antara lain sistem pakar, permainan komputer (games), logika fuzzy, jaringan syaraf tiruan dan robotika.

Penelitian dalam AI menyangkut pembuatan mesin untuk mengotomatisasikan tugas-tugas yang membutuhkan perilaku cerdas. Termasuk contohnya adalah pengendalian, perencanaan dan penjadwalan, kemampuan untuk menjawab diagnosa dan pertanyaan pelanggan, serta pengenalan tulisan tangan, suara dan wajah. Hal-hal seperti itu telah menjadi disiplin ilmu tersendiri, yang memusatkan perhatian pada penyediaan solusi masalah kehidupan yang nyata. Sistem AI sekarang ini sering digunakan dalam bidang ekonomi, obat-obatan, teknik dan militer, seperti yang telah dibangun dalam beberapa aplikasi perangkat lunak komputer rumah dan video game.

Tujuan dari kecerdasan buatan menurut Winston dan Prendergast (1984):

1.      Membuat mesin menjadi lebih pintar (tujuan utama)

2.      Memahami apa itu kecerdasan (tujuan ilmiah)

3.      Membuat mesin menjadi lebih bermanfaat (tujuan entrepreneurial)

Didefinisikan sebagai kecerdasan yang ditunjukan oleh suatu entitas buatan. Sistem seperti ini umumnya dianggap computer. Kecerdasan diciptakan dan dimasukkan dalam suatu mesin atau computer agar dapat melakukan pekerjaan seperti yang dapat dilakukan manusia. Beberapa bidang yang menggunakan kecerdasan buatan anatara lain system pakar, permaianan computer, fuzzy logic, jaringan syaraf tiruan dan robotika.

B.      Pengertian Game

Game adalah permainan komputer yang dibuat dengan teknik dan metode animasi. Permainan game merupakan bidang AI yang sangat populer berupa permainan antara manusia melawan mesin yang mempunyai intelektual untuk berpikir. Komputer dapat bereaksi dan menjawab tindakan-tindakan yang diberikan oleh lawan mainnya.

Salah satu komputer yang ditanamkan AI untuk game bernama Deep Blue. Deep Blue adalah sebuah komputer catur buatan IBM pertama yang memenangkan sebuah permainan catur melawan seorang juara dunia (Garry Kasparov) dalam waktu standar sebuah turnamen catur. Kemenangan pertamanya (dalam pertandingan atau babak pertama) terjadi pada 10 Februari 1996, dan merupakan permainan yang sangat terkenal.

Kini telah banyak berkembang game AI yang semakin menarik, interaktif, dan dengan grafis yang sangat bagus. Ditambah dengan kemajuan teknologi jaringan komputer yang semakin cepat, sudah banyak terdapat game-game AI yang berbasiskan online. Tidak sedikit orang yang tertarik dengan game saat ini. Mereka memainkan game untuk mengisi kekosongan waktu mereka atau pun melatih skill mereka dalam berpikir.

C.      Artificial Intelligence dalam Game

Salah satu unsur yang berperan penting dalam sebuah game adalah kecerdasan buatan. Dengan kecerdasan buatan, elemen-elemen dalam game dapat berperilaku sealami mungkin layaknya manusia. Game AI adalah aplikasi untuk memodelkan karakter yang terlibat dalam permainan baik sebagai lawan, ataupun karakter pendukung yang merupakan bagian dari permainan tetapi tidak ikut bermain (NPC = Non Playable Character). Peranan kecerdasan buatan dalam hal interaksi pemain dengan permainan adalah pada penggunaan interaksi yang bersifat alami yaitu yang biasa digunakan menusia untuk berinteraksi dengan sesama manusia. Contoh media interaksi ialah:

• Penglihatan (vision)

• Suara (voice), ucapan (speech)

• Gerakan anggota badan ( gesture)

Untuk pembentukan Artificial Intelligence pada game ternyata digunakan pula algoritma, yaitu jenis pohon n-ary untuk suatu struktur. Implementasi pohon (tree) ini biasa disebut game tree. Berdasarkan game tree inilah sebuah game disusun algoritma kecerdasan buatannya. Artificial intellegence yang disematkan dalam sebuah game yang membentuk analisis game tree biasanya merepresentasikan kondisi atau posisi permainan dari game sebagai suatu node, dan merepresentasikan langkah yang mungkin dilakukan sebagai sisi berarah yang menghubungkan node kondisi tersebut ke anak (child) sebagaimana representasi suatu pohon (tree).

Namun, biasanya representasi langsung tersebut mempunyai kelemahan, yaitu representasi data pohon akan menjadi sangat lebar dan banyak. Mungkin bagi sebuah mesin komputer mampu melakukan kalkulasi sebanyak apapun masalah, namun game tree yang lebar dan besar memberikan beberapa masalah, antara lain konsumsi proses memori, kapasitas penyimpanan yang cukup besar dan kinerja yang kurang pada konsol game berspesifikasi rendah. Karena itu dibentuklah beberapa algoritma dan penyederhanaan bagi sebuah game tree.

Pada salah satu contoh game klasik, yaitu tic tac toe, penyederhanaan dapat dilakukan dengan berbagai metode. Salah satu diantaranya adalah minimax. Metode ini berhasil diterapkan dan memberikan nilai reduksi yang cukup signifikan. Dan tidak hanya bisa digunakan secara monoton, minimax juga bisa digunakan untuk game-game yang lebih rumit seperti catur, tentunya dengan algoritma dan representasi berbeda.

Minimax yang merupakan salah satu metode penerapan (implementasi) pohon n-ary pada suatu game, menandakan bahwa implementasi struktur (pohon khusunya) sangatlah diperlukan pada pembuatan dan penerapan Artificial Intelligence, dan tidak menutup kemungkinan ilmu dan metode baru yang lebih canggih akan ditemukan di masa depan.

Beberapa karakteristik dan batasan game untuk game playing :

• Perfect Information Game

Kedua pemain sama-sama memiliki akses pada informasi yang lengkap tentang keadaan permainan, sehingga tidak ada informasi yang tertutup bagi lawan mainnya.

• No Determined by Chances

Tidak melibatkan faktor probabilitas, misalnya dengan menggunakan dadu.

• No Phsychological Factors

Tidak melibatkan faktor psikologi, seperti "gertakan" (misalnya Poker)

• No Oversight Errors. Smart Opponen

Lawan diasumsikan pintar juga, jadi jangan mengharap lawan khilaf, sehingga terjadi salah langkah.

Adapun beberapa contoh pada pemanfaatan AI diantaranya:

Dalam bidang game

Setiap game pasti memiliki AI standar, misalnya jika anda memerintah ini, maka si AI akan menjalankan tugasnya. Bahkan banyak game-game yang bertemakan sci-fi seperti HALO, Mass Effect, Crysis, dll di dalam game tersebut masing-masing karakter memiliki AI nya sendiri. Jadi ini bisa dikatakan AI di dalam AI.

D.     Pengembangan Game

    Perkembangan Game yang pesat pada masa ini juga membutuhkan sesuatu yang berbeda pada rule permainannya. Sebuah sistem game, jika sudah dimainkan sampai tuntas oleh seorang player, maka ketika player yang sama memulai lagi permainan dari awal, maka rule permainannya akan sama. namun berbeda untuk game-game yang telah ada saat ini. sistem dalam game, dapat belajar mengenali pola permainan dari player dan ketika player tersebut memulai permainan kembali, maka sistem ini akan menggunakan rule yang berbeda untuk pemain yang sama ini. sehingga game menjadi lebih menarik dan menantang untuk dimainkan.

Contoh aplikasi kecerdasan buatan dalam bentuk game sangat banyak sekali, ada yang berbentuk game PC, dan ada pula yang berbentuk game jaringan. Contoh aplikasi game yaitu game Tic Tac Toe. Game Tic tac toe adalah sebuah permainan yang menggunakan papan berukuran n baris dan n kolom sehingga ukuran papan menjadi n x n misalkan 3x3.

Game ini merupakan game yang mengasah kemampuan berpikir manusia, dimana setiap pemain harus menyusun gambar secara vertikal, horizontal, miring kiri, dan miring kanan agar memperoleh nilai. Apabila pemain tidak dapat membentuk formasi gambar yang diinginkan maka permain dinyatakan kalah. Dan apabila pola gambar seimbang maka permainan dinyatakan drow atau seri. Permainan ini mengasah kemampuan berpikir sehingga para pemain harus melakukan tindakan yang baik dan memperhitungkan apa akibat dari tindakan yang dilakukan tersebut.

A.Minimax Prosedur

    The Game of Nim: Sejumlah token ditempatkan pada meja di antara dua lawan. Pada masing-masing gerakan pemain harus membagi tumpukan token menjadi dua tumpukan tak kosong dari berbagai ukuran. Jadi, 6 token dapat dibagi menjadi 5 dan 1, 4 dan 2, tetapi tidak 3 dan 3. Pemain pertama yang mampu bergerak kehilangan permainan.

Untuk sejumlah kecil token ruang pencarian dapat dicari secara mendalam. Gambar berikut memberikan ruang lengkap untuk permainan 7-token.

Dalam permainan dua-orang, Anda harus mengasumsikan bahwa lawan Anda memiliki pengetahuan yang sama yang Anda lakukan dan berlaku sebaik yang Anda lakukan. Jadi pada setiap tahap permainan Anda harus menganggap lawan membuat langkah terbaik yang tersedia. Ini adalah dasar dari prosedur minimax.

Dalam minimax, para pemain yang disebut sebagai MAX (pemain) dan MIN (lawan). Keduanya mencoba untuk memaksimalkan gerakan mereka. MAX pemain, mencoba untuk memaksimalkan nilainya. Dan MIN adalah lawan mencoba untuk meminimalkan skor MAX. Prosedur Minimax pada Pencarian Ruang Lengkap

•    Label setiap tingkat dari ruang pencarian sesuai dengan yang bergerak itu di tingkat itu.

•    Mulai di node daun, setiap label simpul daun dengan 1 atau 0 tergantung pada apakah itu adalah kemenangan bagi MAX (1) atau MIN (0).

•    Merambat ke atas: jika negara induk MAX, memberikan MAX anak-anaknya.

•    Merambat ke atas: jika negara induk MIN, MIN memberikan anak-anaknya.

Pertimbangkan grafik minimax untuk Nim permainan. Nilai di negara masing-masing mewakili nilai negara terbaik yang pemain ini bisa berharap untuk mencapai. Nilai-nilai yang diperoleh digunakan untuk memilih di antara alternatif bergerak.

B.Heuristik Minimax

    Untuk permainan yang paling tidak mungkin untuk memperluas grafik untuk node daun. Sebaliknya strategi n-pindah melihat-depan adalah digunakan. Ruang negara diperluas ke tingkat n. Setiap node daun di subgraf ini diberikan nilai sesuai dengan fungsi evaluasi heuristik. Nilai kemudian disebarkan kembali ke simpul akar. Nilai disebarkan kembali mewakili nilai heuristik dari negara terbaik yang dapat dicapai dari simpul tersebut. Contoh: Program catur Samuel menggunakan jumlah tertimbang sebagai fungsi evaluasi. Ini menggunakan algoritma pembelajaran sederhana untuk menyesuaikan bobot setelah menang dan kerugian, sehingga program perbaikan dari waktu ke waktu.

C.Prosedur Alpha-Beta

    Alpha-beta pruning adalah prosedur untuk mengurangi jumlah perhitungan dan mencari selama minimax. Minimax adalah pencarian dua-pass, satu lulus digunakan untuk menetapkan nilai-nilai heuristik ke node pada kedalaman ply dan yang kedua digunakan untuk menyebarkan nilai-nilai sampai pohon.

Alpha-beta hasil pencarian secara mendalam-pertama. Sebuah nilai alpha adalah nilai awal atau sementara terkait dengan node MAX. Karena MAX node diberi nilai maksimum antara anak-anak mereka, nilai alpha tidak dapat menurunkan, hanya bisa naik. Sebuah nilai beta adalah nilai awal atau sementara terkait dengan node MIN. Karena node MIN diberi nilai minimum antara anak-anak mereka, nilai beta tidak pernah dapat meningkatkan, hanya bisa turun.

Misalnya, alpha node MAX = 6. Kemudian cari tidak perlu mempertimbangkan setiap cabang yang berasal dari keturunan MIN yang memiliki nilai beta yang kurang-dari-atau-sama dengan 6. Jadi, jika Anda tahu bahwa node MAX memiliki alpha 6, dan Anda tahu bahwa salah satu keturunan MIN yang memiliki beta yang kurang dari atau sama dengan 6, Anda tidak perlu mencari lebih jauh di bawah simpul MIN. Ini disebut pemangkasan alpha. Alasannya adalah bahwa tidak peduli apa yang terjadi di bawah simpul MIN, tidak dapat mengambil nilai yang lebih besar dari 6. Jadi nilainya tidak dapat diperbanyak sampai dengan (alpha) orangtua MAX nya.

Demikian pula, jika nilai beta node MIN itu = 6, anda tidak perlu mencari lebih jauh di bawah MAX keturunan yang telah memperoleh nilai alpha dari 6 atau lebih. Ini disebut pemangkasan beta. Alasannya lagi adalah bahwa apa pun yang terjadi di bawah simpul MAX, tidak dapat mengambil nilai yang kurang dari 6. Jadi nilainya tidak dapat diperbanyak sampai dengan (beta) MIN orangtua nya. Aturan untuk Alpha-beta Pemangkasan

• Alpha Pemangkasan: pencarian dapat dihentikan di bawah setiap simpul MIN memiliki nilai beta kurang dari atau sama dengan nilai alpha dari setiap leluhur MAX nya.

• Pemangkasan beta: Pencarian bisa dihentikan di bawah setiap simpul MAX memiliki nilai alpha lebih besar dari atau sama dengan nilai beta dari setiap leluhur MIN nya.

E.      Menggunakan Heuristik di Permainan

Game yang penting tes-tempat tidur untuk algoritma heuristik. Dua-orang game yang lebih rumit dari teka-teki yang sederhana karena mereka melibatkan lawan tak terduga.

SUMBER:

http://dunotifkejora.blogspot.co.id/2016/04/kecerdasan-buatan-ai-pada-game.html

http://mrifkyy.blogspot.co.id/2016/03/kecerdasan-buatan-artificial.html

https://rifqifai.com/mengenal-apa-itu-ai-artificial-intelligence-kecerdasan-buatan/

Pembelajaran / Learning

Pembelajaran / Learning

Syifa Alya Nabila

16115777

3KA12

Sistem Informasi

Universitas Gunadarma

Pembelajaran / Learning

Pembelajaran adalah proses interaksi peserta didik dengan pendidik dan sumber belajar pada suatu lingkungan belajar yang meliputi guru dan siswa yang saling bertukar informasi.

1.      Pembelajaran dari Pengamatan

Merupakan interaksi peserta didik dengan pendidik dan sumber belajar pada suatu lingkungan belajar yang meliputi guru dan siswa yang saling bertukar informasi pada aktivitas yang dilakukan makhluk cerdas, terhadap suatu proses atau objek dengan maksud merasakan dan kemudian memahami pengetahuan dari sebuah fenomena berdasarkan pengetahuan dan gagasan yang sudah diketahui sebelumnya, untuk mendapatkan informasi-informasi yang dibutuhkan untuk melanjutkan suatu penelitian.

2.      Bentuk Pembelajaran

bentuk-bentuk pengajaran dalam konteks learning by doing, diantaranya:

a.       Menumbuhkan motivasi belajar anak

Motivasi berkaitan erat dengan emosi, minat, dan kebutuhan anak didik. Upaya menumbuhkan motivasi intrinsik yang dilakukan guru adalah mendorong rasa ingin tahu, keinginan mencoba, dan sikap mandiri anak didik. Sedangkan bentuk motivasi ekstrinsik adalah dengan memberikan rangsangan berupa pemberian nilai tinggi atau hadiah bagi siswa berprestasi dan sebaliknya.

b.      Mengajak anak didik beraktivitas

Adalah proses interaksi edukaktif melibatkan intelek-emosional anak didik untuk meningkatkan aktivitas sehingga motivasi akan meningkat. Bentuk pelaksanaanya adalah mengajak anak didik melakukan aktivitas atau bekerja di laboratorium, di kebun/lapangan sebagai bagian dari eksplorasi pengalaman, atau mengalami pengalaman yang sam sekali baru.

c.       Mengajar dengan memperhatikan perbedaan individual

Proses kegiatan belajar mengajar dilakukan dengan memahami kondisi masing-masing anak didik. Tidak tepat jika guru menyamakan semua anak didik karena setiap anak didik mempunyai bakat berlainan dan mempunyai kecepatan belajar yang bervariasi. Seorang anak didik yang hasil belajarnya jelek dikatakan bodoh. Kemudian menyimpulkan semua anak didik yang hasil belajarnya jelek dikatakan bodoh. Kondisi demikian tidak dapat dijadikan ukuran, karena terdapat beberapa faktor penyebab anak memiliki hasil belajar buruk, antara lain; faktor kesehatan, kesempatan belajar dirumah tidak ada, sarana belajar kurang, dan sebagainya.

d.     Mengajar dengan umpan balik

Bentuknya antara lain; umpan balik kemampuan prilaku anak didik (perubahan tigkah laku yang dapat dilihat anak didik lainnya, pendidik atau anak didik itu sendiri), umpan balik tentang daya serap sebagai pelajaran untuk diterapkan secara aktif. Pola prilaku yang kuat diperoleh melalui partisipasi dalam memainkan peran (role play).

e.      Mengajar dengan pengalihan

Pengajaran yang mengalihkan (transfer) hasil belajar kedalam situasi-situasi nyata. Guru memilih metode simulasi (mengajak anak didik untuk melihat proses kegiatan seperti cara berwudlu dan sholat) dan metode proyek (memberikan kesempatan anak untuk menggunakan alam sekitar dan atau kegiatan sehari-hari untuk bertukar pikiran baik sesama kawan maupun guru)  untuk pengalihan pengajaran yang bukan hanya bersifat ceramah atau diskusi, tetapi mengedepankan situasi nyata.

f.      Penyusunan pemahaman yang logis dan psikologis

Pengajaran dilakukan dengan memilih metode yang proporsional. Dalam kondisi tertentu guru tidak dapat meninggalkan metode ceramah maupun metode pemberian tugas kepada anak didik. Hal ini dilakukan sesuai dengan kondisi materi pelajaran.

3.      Pembelajaran Induktif

Pembelajaran induktif adalah sebuah pembelajaran yang bersifat langsung tapi sangat efektif untuk membantu siswa mengembangkan keterampilan berpikir tingkat tinggi dan keterampilan berpikir kritis. Model pembelajaran induktif adalah sebuah pembelajaran yang bersifat langsung tapi sangat efektif untuk membantu siswa mengembangkan keterampilan berpikir tingkat tinggi dan keterampilan berpikir kritis. Pada model pembelajaran induktif guru langsung memberikan presentasi informasi-informasi yang akan memberikan ilustrasi-ilustrasi tentang topik yang akan dipelajari siswa, selanjutnya guru membimbing siswa untuk menemukan pola-pola tertentu dari ilustrasi-ilustrasi yang diberikan. Model pembelajaran induktif dirancang berlandaskan teori konstruktivisme dalam belajar. Model ini membutuhkan guru yang terampil dalam bertanya (questioning) dalam penerapannya. Melalui pertanyaan-pertanyaan inilah guru akan membimbing siswa membangun pemahaman terhadap materi pelajaran dengan cara berpikir dan membangun ide. Tingkat keefektifan model pembelajaran induktif ini, jadinya-sangat tergantung pada keterampilan guru dalam bertanya dan mengarahkan pembelajaran, dimana guru harus menjadi pembimbing yang akan untuk membuat siswa berpikir.

Struktur sosial dalam pembelajaran menjadi ciri lingkungan kelas yang sangat dibutuhkan untuk belajar melalui model pembelajaran induktif. Model pembelajaran induktif mensyaratkan sebuah lingkungan belajar yang mana di dalamnya siswa merasa bebas dan terlepas dari resiko takut dan malu saat memberikan pendapat, bertanya, membuat konklusi dan jawaban. Mereka harus bebas dari kritik tajam yang dapat menjatuhkan semangat belajar.

Model ini dikembangkan atas dasar beberapa postulat sebagai berikut:

1. Kemampuan berpikir dapat diajarkan

2. Berpikir merupakan suatu transaksi aktif antara individu dengan data. Artinya, dalam seting kelas,

bahan-bahan ajar merupakan sarana bagi siswa untuk mengembangkan operasi kognitif tertentu.

Dalam seting tersebut, dimana siswa belajar mengorganisasikan fakta ke dalam suatu sistem konsep,yaitu:

Saling menghubung-hubungkan data yang diperoleh satu sama lain serta membuat kesimpulan berdasarkan hubungan-hubungan tersebut

Menarik kesimpulan berdasarkan fakta-fakta yang telah diketahuinya dalam rangka membangun hipotesis,dan

Memprediksi dan menjelaskan suatu fenomena tertentu. Guru, dalam hal ini, dapat membantu proses internalisasi dan konseptualisasi berdasarkan informasi tersebut

3. Proses berpikir merupakan suatu urutan tahapan yang beraturan (lawful). Artinya, agar dapat menguasai keterampilan berpikir tertentu, prasyarat tertentu harus dikuasai terlebih dahulu, dan urutan tahapan ini tidak bisa dibalik. Oleh karenanya, konsep tahapan beraturan ini memerlukan strategi mengajar tertentu agar dapat mengendalikan tahapan-tahapan tersebut.

Berpikir induktif melibatkan tiga tahapan yang dikembangkan tiga strategi cara mengajarkannya.

4.      Pohon Keputusan

Pohon keputusan adalah salah satu metode klasifikasi yang paling popular karena mudah untuk diinterpretasi oleh manusia. Konsep dari pohon keputusan adalah mengubah data menjadi pohon keputusan dan aturan-aturan keputusan.

Gambar: Konsep Pohon Keputusan

Proses pada pohon keputusan adalah mengubah bentuk data (tabel) menjadi model pohon, mengubah model pohon menjadi rule, dan menyederhanakan rule. Manfaat utama dari penggunaan pohon keputusan adalah kemampuannya untuk membreak down proses pengambilan keputusan yang kompleks menjadi lebih simpel sehingga pengambil keputusan akan lebih menginterpretasikan solusi dari permasalahan. Pohon Keputusan juga berguna untuk mengeksplorasi data, menemukan hubungan tersembunyi antara sejumlah calon variabel input dengan sebuah variabel target.

Pohon keputusan merupakan himpunan aturan IF...THEN. Setiap path dalam tree dihubungkan dengan sebuah aturan, di mana premis terdiri atas sekumpulan node-node yang ditemui, dan kesimpulan dari aturam terdiri atas kelas yang terhubung dengan leaf dari path.

Gambar: Konsep Dasar Pohon Keputusan

Bagian awal dari pohon keputusan ini adalah titik akar (root), sedangkan setiap cabang dari pohon keputusan merupakan pembagian berdasarkan hasil uji, dan titik akhir (leaf) merupakan pembagian kelas yang dihasilkan.

Pohon keputusan mempunyai 3 tipe simpul yaitu:

1. Simpul akar, dimana tidak memiliki cabang yang masuk dan memiliki cabang lebih dari satu, terkadang tidak memiliki cabang sama sekali. Simpul ini biasanya berupa atribut yang paling memiliki pengaruh terbesar pada suatu kelas tertentu.

2. Simpul internal, dimana hanya memiliki 1 cabang yang masuk, dan memiliki lebih dari 1 cabang yang keluar.

3. Simpul daun, atau simpul akhir dimana hanya memiliki 1 cabang yang masuk, dan tidak memiliki cabang sama sekali dan menandai bahwa simpul tersebut merupakan label kelas.

Tahap awal dilakukan pengujian simpul akar, jika pada pengujian simpul akar menghasilkan sesuatu maka proses pengujian juga dilakukan pada setiap cabang berdasarkan hasil dari pengujian. Hal ini berlaku juga untuk simpul internal dimana suatu kondisi pengujian baru akan diterapkan pada simpul daun. Pada umumnya proses dari sistem pohon keputusan adalah mengadopsi strategi pencarian top-down untuk solusi ruang pencariannya. Pada proses mengklasifikasikan sampel yang tidak diketahui, nilai atribut akan diuji pada pohon keputusan dengan cara melacak jalur dari titik akar sampai titik akhir, kemudian akan diprediksikan kelas yang ditempati sampel baru tersebut.

Pohon keputusan banyak digunakan dalam proses data mining karena memiliki beberapa kelebihan, yaitu:

1. Tidak memerlukan biaya yang mahal saat membangun algoritma.

2. Mudah untuk diinterpetasikan.

3. Mudah mengintegrasikan dengan sistem basis data.

4. Memiliki nilai ketelitian yang lebih baik.

5. Dapat menemukan hubungan tak terduga dan suatu data.

SUMBER:

http://srinataluay.blogspot.co.id/

http://marjuki01.blogspot.co.id/2014/06/bentuk-bentuk-pembelajaran-learning-by.html

http://www.salamedukasi.com/2014/06/mengamati-observation-langkah-observasi.html