Kecerdasan Buatan Game

Kecerdasan buatan (Artificial Intelligence)

A. Sejarah Kecerdasan Buatan

Mulai sekitar abad 18 sebagaimana mesin telah menjadi lebih kompleks, usaha yang keras telah dicoba untuk menciptakan manusia imitasi. Pada tahun 1736 seorang penemu dari perancis, Jacques de Vaucanson (1709-1782) membuat suatu mesin pemain seruling berukuran seperti seorang manusia yang dapat memainkan 12 melodi nada. Tidak hanya ini saja, mekanik tersebut dapat memindahkan bibir dan lidahnya secara nyata untuk mengontrol arus dari angin ke dalam seruling.

Pada tahun 1774 seorang penemu dari perancis, Pierre Jacques Drotz mencengangkan masyarakat Eropa dengan suatu automation berukuran sekitar seorang anak laki-laki yang dapat duduk dan menulis suatu buku catatan. Penemuan ini kemudian dilanjutkan dengan yang lainnya, yaitu automation yang berupa seorang gadis manis yang dapat memainkan harpsichord. Semuanya itu masih merupakan proses mekanik yang melakukan gerak dengan telah ditentukan terlebih dahulu.

Manusia masih berusaha untuk menciptakan mesin yang lainnya. Pada tahun 1769, dataran Eropa dikejutkan dengan suatu permainan catur yang dapat menjawab langkah-langkah permainan catur yang belum ditentukan terlebih dahulu. Mesin ini disebut dengan Maelzel Chess Automation dan dibuat oleh Wolfgang Von Kempelan (1734-1804) dari Hungaria. Akan tetapi mesin ini akhirnya terbakar pada tahun 1854 di Philadelphia Amerika Serikat.banyak orang tidak percaya akan kemampuan mesin tersebut. Dan seorang penulis dari Amerika Serikat, Edgar Allan Poe (1809-1849) menulis sanggahan terhadap mesin tersebut, dia dan kawan-kawannya ternyata benar, bahwa mesin tersebut adalah tipuan, dan kenyataannya bukanlah aoutomation, tetapi merupakan konstruksi yang sangat baik yang dikontrol oleh seorang pemain catur handal yang bersembunyi di dalamnya.

Usaha untuk membuat konstruksi mesin permainan terus dilanjutkan pada tahun 1914, dan mesin yang pertama kali didemonstrasikan adalah mesin permainan catur. Penemu mesin ini adalah Leonardo Torres Y Quevedo, direktur dari Laboratorio de Automatica di Madrid, Spanyol. Beberapa tahun kemudian, ide permainan catur dikembangkan dan diterapkan di komputer oleh Arthur L. Samuel dari IBM dan dikembangkan lebih lanjut oleh Claude Shannon.

Pada abad ke 20, Automation sudah banyak dikembangkan dan diterapkan terutama pada Angkatan bersenjata Amerika Serikat, berupa program-program simulasi peperangan. Sekarang ini, perkembangan AI sudah mencapai pada tahap yang dapat dikatakan fantastis, terutama di bidang-bidang berikut:

- Game Playing

- General Problem Solving

- Natural Language Recognition

- Speech Recognition

- Visual Recognition

- Robotics dan system pakar

B. Definisi Kecerdasan buatan

Apakah Artificial Intelligence (AI) atau Intelegensi Buatan itu?

AI dapat didefinisikan sebagai suatu mesin atau alat pintar (biasanya adalah suatu komputer) yang dapat melakukan suatu tugas yang bilamana tugas tersebut dilakukan oleh manusia akan dibutuhkan suatu kepintaran untuk melakukannya. Definisi ini tampaknya kurang begitu membantu, karena beberapa ahli berpendapat :

· H.A Simon (1987):

o “kecerdasan buatan merupakan kawasan penelitian, aplikasi dan instruksi yang terkait dengan pemrograman computer untuk melakukan sesuatu hal yang dalam pandangan manusia adalah cerdas”.

· Rich and Knight (1991):

o “sebuah studi tentang bagaimana membuat komputer melakukan hal-hal yang pada saat ini dapat dilakukan dengan lebih baik oleh manusia”.

· Encyclopedia Britannica:

o “merupakan cabang dari ilmu computer yang dalam merepresentasi pengetahuan lebih banyak menggunakan bentuk symbol-simbol dari bilangan, dan memproses informasi berdasarkan metode heuristic atau berdasarkan sejumlah aturan”

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.

C. 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. Game memiliki beberapa tipe :

o Informasi lengkap = suatu game dimana permain mengetahui semua langkah yang mungkin terjadi dari dirinya sendiri dan dari lawan dan hasil akhir dari permainan. Contoh game : catur dan tic tac toe

o Informasi tak lengkap : game dimana pemain tidak tahu semua kemungkinan langkah lawan. Contoh game : Kartu Poker dan Brigde karena semua kartu tidak diketahui oleh para pemain.

D. 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 :

Dimainkan oleh 2 ( dua ) pemain: manusia dan komputer. Para pemain saling bergantian melangkah.

1. 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.

2. No Determined by Chances
Tidak melibatkan faktor probabilitas, misalnya dengan menggunakan dadu.

3. No Phsychological Factors
Tidak melibatkan faktor psikologi, seperti "gertakan" (misalnya Poker)

4. No Oversight Errors. Smart Opponen
Lawan diasumsikan pintar juga, jadi jangan mengharap lawan khilaf, sehingga terjadi salah langkah.

5. Beberapa contoh permainan yang biasa digunakan sebagai contoh kasus Game Playintyle = "font-family:courier new;"> Last One Loses n

· n-coins Grundy's Game

· Slide-5

· Tic-Tac-Toe
· Checkers

· Go

· Nim

· Othello

· Chess

E. 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 3 x 3.

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.

F. 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.

o 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

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

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

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

4. 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.

o 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.

o 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.