ARTIFICIAL INTELLIGENCE

Artificial Intelligence Pada Game Checkers

PENDAHULUAN
Checkers merupakan jenis permainan game board, yang mengandalkan strategi sebagai elemen utamanya. Permainan ini dimainkan oleh dua orang pemain dengan tujuan menghabiskan kepingan lawan. Permainan checkers yang dibuat dengan AI (Artificial Intelligence) tertentu menerapkan algoritma Minimax. Algoritma Minimax merupakan salah satu implementasi dari Depth First Search dan digunakan untuk menentukan pilihan agar memperkecil kemungkinan kehilangan nilai maksimal, yang akan mendeskripsikan dimana jika terdapat pemain yang mengalami pendapatan akan maka pemain lain akan mengalami kehilangan sebesar pendapatan tersebut. Untuk memperkecil lingkup pencarian pada algoritma Minimax, dikembangkan suatu algoritma yang dinamakan alpha-beta untuk mengurangi jumlah node pada pohon pencarian. Pada permainan checkers algoritma ini akan menentukan langkah yang diambil oleh AI agar menghasilkan pendapatan maksimum dengan mempertimbangkan kemungkinan langkah yang dapat dilakukan lawan selanjutnya. Perkembangan permainan saat ini telah sampai kepada pembuatan artificial intelligent (AI) sebagai teknik yang digunakan pada komputer atau video game untuk memproduksi ilusi atau kepintaran karakter yang bukan pemain. Dalam boad game, AI akan berperan sebagai musuh yang akan bergerak sesuai algoritma yang digunakan.

CHECKERS
Permainan checkers (dalam bahasa Inggris Amerika) atau disebut draughts (dalam bahasa Inggris British) merupakan permainan yang menggunakan strategi abstrak dimainkan oleh dua pemain dengan menggunakan langkah diagonal token dan menangkap dengan melompati token musuh.
Permainan ini telah dimainkan di Eropa sejak abad ke16, dikembangkan dari permainan alquerque. Bentuk yang paling populer dari pemainan ini adalah international draughts, yang dimainkan pada papan 10×10. Bentuk yang juga populer adalah English draughts, yang disebut American checkers, dimainkan pada papan 8×8.



ALGORITMA MINIMAX
Algoritma Minimax merupakan basis dari semua permainan berbasis AI[ http://id.wikipedia.org]. Algoritma Minimax merupakan algoritma yang digunakan untuk menentukan pilihan agar memperkecil kemungkinan kehilangan nilai maksimal. Algoritma ini diterapkan dalam permainan yang melibatkan dua pemain seperti tic tac toe, checkers, go dan permainan yang menggunakan strategi atau logika lainnya. Hal ini berarti permainan-permainan tersebut dapat dijelaskan sebagai suatu rangkaian 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. Algoritma ini mulai dikembangkan dari teori game zero-sum. Teori ini mendeskripsikan situasi dimana jika terdapat pemain yang mengalami pendapatan, pemain lain akan mengalami kehilangan dengan nilai yang sama dari pendapatan tersebut, dan sebaliknya. Jumlah pendapatan dari pemain yang dikurangi dengan jumlah kehilangan akan berjumlah nol.
PENERAPAN ALGORITMA MINIMAX DALAM CHECKERS
Penerapan algoritma Minimax dalam checkers dibuat berdasarkan prosedur Minimax untuk mendapatkan langkah terbaik dari posisi yang ada. Setiap posisi memiliki nilai yang dapat dihasilkan dari langkah terbaik, dengan berasumsi bahwa AI akan selalu mencoba memaksimalkan nilai, ketika lawan akan mencoba untuk meminimalkannya.Ketika prosedur minimax mencapai akar pada pohon pencarian (posisi saat tersebut), akan menghasilkan langkah terbaik dengan asumsi lawan akan menggunakan kriteria evaluasi yang sama. Beberapa versi program yang dibuat kebanyakan telah menerapkan algoritma pemotongan alpha-beta.Terdapat dua macam metode, yang disebut rote learning. Metode tersebut memiliki penyimpan untuk setiap posisi yang ditemui selama permainan dengan tidak menghilangkan nilai yang ditentukan oleh prosedur Minimax. Hasilnya adalah jika terdapat posisi yang pernah ditenukan sebelumnya, akan dimunculkan sebagai posisi terminal pada pohon pencarian. Sehingga, pencarian akan semakin mudah karena nilai posisi diambil dari hasil pencarian yang telah dilakukan sebelumnya. Satu masalah awal yang ditemukan adalah program tidak mendukung untuk melangkah langsung menuju kemenangan.
Pertama kali dilakukan oleh Arthur Samuel dalam melakukan pembuatan program untuk mempelajari permainan checkers. Prah program yang dibuat berdasarkan prosedur Minimax untuk mendapatkan langkah terbaik dari posisi yang ada. Setiap posisi memiliki nilai yang dapat dihasilkan dari langkah terbaik, dengan berasumsi bahwa AI akan selalu mencoba memaksimalkan nilai, ketika lawan akan mencoba untuk meminimalkannya. Ketika prosedur minimax mencapai akar pada pohon pencarian (posisi saat tersebut), akan menghasilkan langkah terbaik dengan asumsi lawan akan menggunakan kriteria evaluasi yang sama. Beberapa versi program yang dibuat Samuel juga telah menerapkan algoritma pemotongan alpha-beta.
Samuel menggunakan dua macam metode, yang disebut rote learning. Metode tersebut memiliki penyimpan untuk setiap posisi yang ditemui selama permainan dengan tidak menghilangkan nilai yang ditentukan oleh prosedur Minimax. Hasilnya adalah jika terdapat posisi yang pernah ditenukan sebelumnya, akan dimunculkan sebagai posisi terminal pada pohon pencarian. Sehingga, pencarian akan semakin mudah karena nilai posisi diambil dari hasil pencarian yang telah dilakukan sebelumnya. Satu masalah awal yang ditemukan adalah program tidak mendukung untuk melangkah langsung menuju kemenangan. Samuel memberikan pengarahan dengan mengurangi sedikit nilai posisi setiap tahap (disebut ply) pada analisis Minimax. Jika program berhadapan dengan pilihan posisi dengan nilai yang hanya dibedakan oleh ply, maka program akan secara otomatis melangkah pada pilihan yang paling menguntungkan. Samuel mencoba permainan ini berkali-kali dengan melawan berbagi versi sebelumnya dan melakukan backup pada setiap langkah.

KESIMPULAN
Permainan checkers merupakan permainan yang dimainkan oleh dua orang dengan tujuan untuk menghabiskan kepingan yang dimiliki lawan. Dalam pembuatannya dengan AI, permainan ini menerapkan algoritma Minimax. Algoritma Minimax memiliki dasar berupa zero-sum game, dimana jika pemain mendapatkan nilai tertentu maka pemain lain akan kehilangan nilai yang sama dengan pemain tersebut. Dengan menambahkan nilai alpha-beta algoritma Minimax akan memiliki pohon pencarian yang lebih singkat sehingga akan membutuhkan waktu singkat untuk melakukan aksinya. Nilai ini akan berhenti mengevaluasi langkah ketika terdapat paling tidak satu kemungkinan yang ditemukan dan membuktikan bahwa langkah tersebut lebih buruk jika dibandingkan dengan langkah yang diperiksa sebelumnya. Algoritma Minimax menggunakan DFS sebagai dasar pembuatan pohon pencarian.

SUMBER :
http://blog.uin-malang.ac.id/sharfina/2010/10/
Suyanto. 2007. Artificial Intelligence. Bandung : Informatika Bandung
hanz-kampus.blogspot.com/…/teknik-pencarian-kecerdasan-buatan.html

SEJARAH PERKEMBANGAN GAME

Pengertian Game

Dalam kamus bahasa Indonesia “Game” adalah permainan. Permainan merupakan bagian dari bermain dan bermain juga bagian dari permainan keduanya saling berhubungan. Permainan adalah kegiatan yang kompleks yang didalamnya terdapat peraturan, play dan budaya. Sebuah permainan adalah sebuah sistem dimana pemain terlibat dalam konflik buatan, disini pemain berinteraksi dengan sistem dan konflik dalam permainan merupakan rekayasa atau buatan, dalam permainan terdapat peraturan yang bertujuan untuk membatasi perilaku pemain dan menentukan permainan. Game bertujuan untuk menghibur, biasanya game banyak disukai oleh anak – anak hingga orang dewasa. Games sebenarnya penting untuk perkembangan otak, untuk meningkatkan konsentrasi dan melatih untuk memecahkan masalah dengan tepat dan cepat karena dalam game terdapat berbagai konflik atau masalah yang menuntut kita untuk menyelesaikannya dengan cepat dan tepat. Tetapi game juga bisa merugikan karena apabila kita sudah kecanduan game kita akan lupa waktu dan akan mengganggu kegiatan atau aktifitas yang sedang kita lakukan.
Dalam hal ini paling tidak terdapat 5 kategori istilah game, yaitu : Board Games (Permainan Papan), Card Games (Permainan Kartu), Athletic Games (Permainan Atletik), Children Games (Permainan Anak), dan Computer Games (Permainan Komputer).

Sejarah Game

Sejarah teknologi game komputer secara langsung berhubungan dengan perkembangan komputer itu sendiri. Komputer dengan kecepatan processor tinggi, grafis yang lebih mendekati realita, dan media penyimpanan yang lebih besar sebenarnya dimaksudkan untuk memenuhi kebutuhan dalam bermain games.

Sebelum dimulai, akan kita pahami dulu apa arti dari game (game komputer). Game adalah sebuah permainan interactive yang membutuhkan komputer untuk bermain. Program komputer menerima input dari si pemain melalui pengendali dan menampilkan lingkungan buatan melalui TV atau layar monitor.

Game generasi pertama

Tahun 1952, di Universitas Cambridge, A.S Douglas menulis sebuah tesis untuk gelar sebuah PhD-nya mengenai interaksi antara komputer dan manusia. Dalam tesisnya itu ia
men
ciptakan game komputer dari sebuah permainan tradisional bernama Tic-Tac-Toe. Game ini diprogram dengan memakai komputer EDVAC vacuum tube yang memiliki layer berupa cathode ray tube (CRT).

Kemudian di tahun 1958. William Haginbotham menciptakan video game pertamanya. Berbeda dengan Douglas, video game pertamanya yang berjudul Tennis for Two diciptakan dan dimainkan di osciloscope.

Tapi game komputer pertama yang benar-benar diciptakan menggunakan komputer betulan adalah Spacewar. Saat itu di tahun 60-an, komputer adalah barang sangat mewah. Dan biasanya komputer dipakai untuk kepentingan riset dalam dunia militer. Tapi seseorang bernama Steve Russel memiliki ketertarikan akan hal lain. Dia dan teman-temannya sangat nge-fan dengan kisah fiksi ilmiah berjudul Skylark karangan Edward E Smith. Dari situ mereka membuat sebuah game bernama Spacewar. Kebetulan juga, Steve Russel bekerja menggunakan sebuah komputer mainframe bernama MIT PDP-1 yang biasa dipakai untuk perhitungan statistik. Dengan komputer itulah dia membuat Spacewar di tahun 1961.

Game generasi kedua

Di tahun 1971, Nolan Bushnell bersama dengan Ted Dabney menciptakan game ber-genre arcade yang pertama. Dinamai Komputer Space, game itu didasari oleh Spacewar. Tahun 1972, Nolan dan Ted memulai Atari komputer. Kemudian dia mengembangkan game berjudul Pong yaitu game pertama yang tersedia untuk publik. Karena game-game sebelumnya hanya ada di dalam komputer mainframe untuk kesenangan sendiri saja. Asal usul Pong dimulai saat Nolan ingin membuat game sederhana dan mudah dimengerti. Dengan memory dan micro processor kelas rendah, kemampuan proses yang terbatas dan grafis yang sederhana, akhirnya dia membuat versi elektronik dari permainan ping pong yang kemudian menjadi Pong.

Sedikit selingan, Pong kemudian berevolusi menjadi sebuah game bernama Breakout. Game itu diciptakan oleh Steve Jobs untuk Atari. Dari situ, Steve Jobs dan temannya Steve Wozniak mulai berpikir untuk menciptakan sebuah PC. Kemudian mereka meminjam semua peralatan yang dipakai dalam proyek Breakout dan membuat sebuah prototype bernama Apple I. dan itu adalah cikal bakal dari komputer Apple Macintosh yang ada sekarang.

Pada tahun 1980, Atari mengeluarkan game berjudul Asteroid dan Lunar Lander. Kedua game tersebut adalah game pertama yang didaftarkan pada kantor hak cipta untuk mendapatkan paten. Asteroid merupakan game yang penuh inovasi baru dalam grafisnya. Daripada menggunakan metode raster, game ini merupakan grafis vector line seperti yang ada pada osciloscope.

Pengenalan Atari Video komputer System (Atari 2600) dengan CPU biasa dan slot untuk kasetnya, menjadi suatu era baru dalam dunia game. Di tahun 1980 itu juga menunjukkan penjualan yang meningkat dari PC yang biasa dipakai untuk game.

Dan kini komputer bersaing dengan mesin konsol seperti PS atau Xbox. Dan komputer tidak hanya sebagai mesin untuk kepentingan bisnis semata, tapi juga untuk hiburan seperti game.
Berikut catatan perkembangan Games yang lebih terperinci :
Meskipun sejarah perkembangan game berlangsung selama lima dekade, game sendiri tidak populer hingga akhir tahun 1970an. Berikut ini ringkasan sejarah game dan perkembangannya.
• 1958: Ahli Fisika membuat video game pertama yang menyerupai permainan tenis meja.
• 1961: Steve Russel, siswa MIT membuat game komputer interaktif pertama berjudul Spacewar.
• 1966: Ralp Baer menciptakan game interaktif menggunakan televisi.
• 1971: Nolan Bushnell dan Ted Dabney membuat versi arcade Spacewar, yaitu Computer Space.
• 1972: Bushnell dan Dabney mendirikan Atari. Game pertama Atari adalah Pong.
• 1975: Game komputer pertama dirilis, yaitu Gunfight.
• 1976: Coleco merilis konsol video game pertama yang disebut Telstar.
• 1977: Atari mengenalkan video game berbasis kartrid yang dikenal dengan nama Atari 2600.
• 1978: Atari memperkenalkan trackball dalam game Football.
• 1978: Midway merilis Space Invaders yang merupakan game arcade pertama yang menampilkan skor tertinggi.
• 1979: Atari mencoba mengembangkan konsol berhologram bernama Cosmos. Namun konsol tersebut tidak pernah dirilis.
• 1979 Asteroid merupakan game pertama yang dapat memasukkan 3 karakter huruf pemilik skor tertinggi untuk disimpan di dalam mesin.
• 1980: Activision menjadi vendor video game.
• 1980: 300.000 unit Pac-Man dirilis oleh Namco.
• 1981: Arnie Katz dan Bil Kunkel menerbitkan majalah game pertama bernama Electronic Games.
• 1982: Atari mengeluarkan Atari 5200 untuk bersaing dengan Coleco.
• 1983: Nintendo masuk ke pasar Jepang.
• 1985: Game Tetris dikembangkan oleh programer Rusia, Alex Pajitnov.
• 1986: Nintendo NES dirilis di Amerika Serikat.
• 1986: Sega memperkenalkan Sega Master System (SMS) untuk bersaing dengan NES.
• 1986: Atari memroduksi Atari 7800.
• 1989: Nintendo memasarkan produk handheld Game Boy.
• 1991: Nintendo mengeluarkan Super NES di Amerika Serikat.
• 1993: Atari merilis Jaguar, konsol 64 bit pertama di pasaran.
• 1994: Sega Saturn dan Sony Playstation memulai debutnya di Jepang.
• 1995: Sony memasarkan PlayStation di Amerika Serikat.
• 1995: Nintendo merilis Nintendo 64 di Jepang.
• 1996: Demam Virtual Pet Tamagotchi melanda Jepang dan Amerika Serikat.
• 1997: PlayStation menjadi game konsol terpopuler.
• 1998: Sega memperkenalkan Dreamcast di Jepang. Konsol ini bekerja pada Microsoft Windows CE.
• 2000: Sony PlayStation 2 dirilis di Amerika Serikat dan menjadi fenomena baru.
• 2000: Game The Sims dirilis dan menjadi game terpopuler.
• 2001: Microsoft memperkenalkan Xbox dengan built-in hardrive dan port ethernet. Nintendo memperkenalkan GameCube dan GameBoy Advance.
• 2004: Sony memroduksi PSP, konsol portabel beresolusi tinggi.
• 2004: Microsoft menciptakan Xbox 360 untuk bersaing dengan Sony.
• 2006: Nintendo memasarkan Wii, konsol game revolusioner.
• 2006: Sony mengeluarkan PlayStation 3, konsol yang canggih namun mahal.
• 2007: Nintendo merilis Super Mario Galaxy untuk Wii.
• 2008: Grand Theft Auto 4 memecahkan rekor penjualan tertinggi dalam minggu pertama setelah rilis.
• 2008: Wii Fit dipasarkan agar para pengguna merasakan manfaat olahraga dalam konsol.
• 2009: Nintendo Wii Sports menjadi best seller video game.


Computer Game
Kemudian disini saya hanya akan menjelaskan kategori Computer Games Apa itu Computer Game?
Computer Game (Permainan Komputer) Game ini dimainkan lewat bantuan alat komputer. Terdapat 5 alat yang dapat dikategorikan sebagai komputer, yaitu :
o Expensive dedicated machine, mesin yang dioperasikan dengan koin untuk memainkankannya.
o Inexpensive dedicated machine, disebut juga dengan hand held machine. Alat game watch termasuk dalam katagori ini.
o Multiprogram home, mesin seperti Atari,Nintendo termasuk dalam kelompok komputer ini.
o Personal computer
o Mainframe computer
Computer game berbeda dengan jenis game yang lain karena tidak ada pergerakan secara fisik atau interaksi langsung dengan object kecuali lewat perantaraan komputer. Software yang dibuat harus dapat menangkap reaksi yang cepat dari interaksi yang dihasilkan dengan pemain. Karena itu software untuk computer games harus bersifat real time. Kompleksitas game adalah bergantung dari kemampuan merepresentasikan aturan dan lingkungan game dalam program yang dibuat.
Diantara sekian banyak definisi game, maka definisi yang umum untuk computer game adalah :
A computer game is a software program in which one or more players make decisions through the control of game objects and resources, in pursuit of a goal.
Gim Komputer adalah sebuah program software dimana satu atau lebih pemain berusaha untuk membuat keputusan lewat kontrol terhadap object dan resource guna memenuhi satu tujuan tertentu

Teori Macam-macam Computer Game
Terdapat berbagai macam game, yaitu antara lain:
1. Fun Games
Fun games adalah permainan seperti : skate board, bilyard, catur, puzzle, tetris, golf, Windows Entertainment Pack Games dan semua permainan yang animasinya sedikit dan pembuatannya relatif mudah. Permainan semacam ini terlihat mudah dari segi grafiknya tetapi biasanya sulit dalam algoritma.
2. Arcade Games
Arcade games adalah semua permainan yang mudah dimengerti, menyenangkan dan grafiknya bagus walau biasanya sederhana. Pengertian mudah dimengerti dan menyenangkan dikarenakan permainan ini hanyalah berkisar pada hal-hal yang disenangi umum seperti pukul memukul, tembak menembak, tusuk menusuk, kejar mengejar dan semua yang mudah dan menyenangkan. Yang termasuk kedalam permainan jenis ini adalah Prince of Persia, Street Fighter, Golden Axe, Grand Prix, Robocop.
3. Strategic Games
Strategic games biasanya permainan strategi perang atau bisa juga permainan lain tetapi tetap saja memerlukan strategi untuk memenangkannya seperti startegi bisnis dan strategi politik.
4. Adventure Games
Adventure games terbagi atas tiga macam yaitu petualangan biasa (Multi Layered Adventur), Dungeon-Underworld Adventure (3D Adventure) dan Roll Playing Game Adventure. Biasanya algoritma untuk membuat game ini adalah sedang-sedang saja sampai sulit. Tapi grafik jenis permainan ini benar-benar sulit. Contoh beberapa permainan jenis ini adalah Space Quest IV, Labyrinth of Word, War II dan Diablo.

5. Simulation Games
Dari semua jenis permainan yang ada, masing-masing memiliki tingkat kesulitan dan kemudahannya, jika bukan algoritmanya maka akan mudah dalam hal animasinya, akan tetapi games simulasi bisa disebut sebagai jenis permainan yang paling sulit, baik algoritma pembuatannya maupun animasinya. Permainan jenis ini juga yang paling membuat pusing dibandingkan dengan permainan jenis lainnya. Algoritmanya sangat sulit sebab harus memperhitungkan semua kejadian dalam kondisi sebenarnya. Berbagai efek animasi yang dibuat tidak cukup bermodalkan ahli grafik dan algoritma saja, tetapi sedikitnya harus mengerti persoalan matematika, teknik dan fisika. Contoh permainan jenis ini adalah Stellar7, F-15 Strike Eagle, Flight Simulator 98, F-14 Tomcat, F-16 Falcon, Jet Fighter.

sumber :
http://cgrg.wordpress.com/2008/03/12/definisi-computer-game/
http://tutorialkuliah.blogspot.com/2009/05/teori-macam-macam-game-komputer.html