Viking PERSIB

Viking Pusat : “Janji Untuk Sebuah Kehormatan”

Viking Garut : "Ulah Ringrang,Entong Hariwang, Urang Dukung PERSIB Anu Aink"

Viking Bekasi : "Membiru Di Batas Provinsi, Mati Poen Kami PERSIB"

Viking Jakarta : "Kami Memang Ada"

Viking Yogyakarta : "Jauh Tak Berarti, PERSIB Selalu Dihati"

Viking Cipeundeuy : "Sahate Sajiwa Sadudulur Ngadukung PERSIB"

Viking Alengka : "Totalitas Yang Tak Pernah Padam"

Viking ITB : "Untuk Tuhan, Bangsa, Dan Maung Bandung"

Viking UPI : "Bobotoh Ilmiah, Edukatif, Jeung Religius"

Viking Borneo : "Di Garis Khatulistiwa Kami Ada Untuk PERSIB"

Viking Ganas : "Satu Hati SatuNyali Ngadukung PERSIB"

Viking Pemadam DKI Jakarta:"Pantang Pulang Sebelum PERSIB Menang"

Viking Malaysia : "Panceg Dina Galur, Najan Awak LeburDi Nagara Batur"

Viking Wonosobo : "Sanajan Adoh, Tetep Bobotoh"

Viking Batujajar : "Moal Ngejat Ngadukung PERSIB"

Viking Karawang : "Lupakan Cinta Demi PERSIB"

Viking Indramayu : "PERSIB Reang, Pujare Reang"

Viking Cirebon : "Jabat Erat Tangan Kami, PERSIB Ataoe Mati! "

Viking Cikarang : "From Cikarang, With Love For PERSIB"

Viking Bunter : "Meunang Babaung, Eleh Teu Pundung"

Viking Sukabumi:"Nyacapkeun Panasaran, Ngadukung Terus PERSIB"

Viking Bogor : "From Bogor, For PERSIB"

Viking Purwakarta : "PERSIB Duriat Aing"

Viking Tasik Timur : "Hade Goreng PERSIB Samaotna"

Viking Banten : "Dinanti Dan Selalu Ditakuti"

Viking Kuningan : "Duriat PERSIB Sampai Mati"

Viking Sukabumi : "Saedanna Ngadukung PERSIB, Tapi Make Manah"

Viking Buahbatu : "Sanajan Nekat, Lalajo PERSIB Moal Kaliwat"

Viking Jababeka : "Dirantau Kami Membiru"

Viking Semarang : "Sa' Adoh-adohe Aku Melaku, PERSIB Tetep Neng Ati NgantiMati"

Viking Sumedang : "Makan Tahu, Warna Selalu Biru"

Viking Situraja : "Baheula, Ayeuna, Pageto Dukung PERSIB."

Viking Lembang : "Negtreug Teuneung Ludeung"

Viking Tanggerang : "Our Support Will Never End"

http://vikingpersibclub.com/

Graf dan Topologi Jaringan

Graf dan Topologi Jaringan

Abstract –

Topologi jaringan adalah pola hubungan antara periferal-periferal dalam suatu jaringan (CPU, hub / concentrator). Makalah ini membahas tentang studi dan implementasi Graf dengan sifat-sifat yang ada didalamnya untuk diterapkan dalam perencanaan struktur jaringan dalam hal tata-letak periferal, aliran data, proses, dsb. Perencanaan struktur jaringan ini dapat berbeda sesuai dengan topologi jaringan yang diterapkan. Ada 3 jenis topologi jaringan, yaitu : Signal Topology, Logical Topology, dan Physical Topology. Namun yang dibahas lebih mendalam di makalah ini adalah Physical Topology karena lebih mudah untuk dideskripsikan secara aktual dan karena mempunyai klasifikasi khusus di dalamnya. Physical Topology dapat dikategorikan menjadi beberapa bentuk topologi antara lain : topologi bintang, topologi cincin, topologi pohon, dsb. Masing-masing topologi ini memiliki kelebihan dan kekurangan, misalkan mengenai periferal yang dibutuhkan, manajemen jaringan dalam mendeteksi gangguan pada jaringan, fleksibilitas jaringan, dsb. Graf diimplementasi pada topologi jaringan dengan maksud agar, untuk skala yang lebih luas dan jaringan bercabang banyak, optimasi jaringan yang dilakukan, misalkan mnghitung kebutuhan kabel, atau menghitung jumlah periferal maksimum yang bisa ditambahkan, bisa dilakukan dengan mudah, yaitu menggunakan hukum-hukum dan teorema dalam graf.

1. PENDAHULUAN

Komputer saat ini bukan hanya perangkat yang berdiri secara tunggal. Untuk keperluan akses data yang lebih efisien dan tugas-tugas yang melibatkan computer lain, komputer harus bekerja pada sistem jaringan yang kompak dan saling terhubung. Lebih jauh lagi, setelah adanya internet, saat ini jaringan bukan hanya untuk sekedar menghubungkan komputer-komputer pada area yang terbatas, tapi jaringan telah berkembang, yaitu memungkinkan komputer menjadi perangkat yang dapat menghubungkan dua tempat yang berjarak sangat jauh, maupun sebagai media pertukaran informasi. Dalam jaringan, terjadi transfer data antar komputer, sehingga tasks yang dijalankan sangat tergantung pada jaringan itu sendiri. Setiap komputer yang ada dalam jaringan saling terhubung dengan suatu pola hubungan. Arus data yang mengalir juga sangat ditentukan kecepatan serta efisiensinya bersasarkan pola jaringan yang digunakan.

Topologi merupakan suatu pola hubungan antar terminal dalam jaringan komputer. Seperti yang telah dikatakan sebelumnya, pola ini sangat erat kaitannya dengan metode akses dan media pengiriman yang digunakan. Topologi yang ada sangatlah tergantung dengan letak geofrapis dari masing-masing terminal, kualitas kontrol yang dibutuhkan dalam komunikasi ataupun penyampaian pesan, serta kecepatan dari pengiriman data. Pada topologi jaringan, pola hubungan yang digunakan, aliran data, dan strukturnya diimplementasi dari pola hubungan dalam graf dan secara khusus, terdapat topologi yang mengimplementasikan pohon sebagai bentuk khusus graf dalam struktur jaringan.

2. PEMBAHASAN

Seperti yang dijelaskan di atas, topologi jaringan adalah hal yang menjelaskan hubungan geometris antara unsur-unsur dasar penyusun jaringan, yaitu node, link, dan station.

Secara umum topologi dapat dikategorikan menjadi 3:

1. Signal Topology

Tata letak pada koneksi actual antar nodes pada sebuah jaringan, yang melalui jalur yang diambil sinyal ketika beinteraksi dengan nodes yang lain.

2. Logical Topology

Logical Topologi secara definisi memiliki kemiripan dengan Signal Topologies. Definisi dari Logical Topology adalah jalur yang diambil oleh data, antar nodes dalam jaringan. Sedangkan pada signal topologies didasarkan pada sinyal.

3. Physical Topology

Tata letak nodes dari sebuah jaringan dan hubungan yang terjadi secara aktual (fisik) di antaranya. Misalkan layout dari kabel ,lokasi dari nodes, dan interkoneksi antara nodes dengan kabel pada jaringan. Physical Topology diklasifikasikan menjadi beberapa bentuk topologi, yaitu :

1. Point to Point (Titik ke titik)

2. Star Network (Jaringan Bintang)

3. Ring Network (Jaringan Cincin)

4. Mesh Network

5. Tree Network (Jaringan Pohon)

2.1 Point to Point

Jaringan titik ke titik merupakan jaringan kerja yang paling sederhana tetapi dapat digunakan secara luas. Begitu sederhananya jaringan ini, sehingga seringkali tidak dianggap sebagai suatu jaringan tetapi hanya merupakan jalur komunikasi biasa.

Pada jenis topologi ini, kedua simpul mempunyai kedudukan yang setingkat, sehingga simpul manapun dapat memulai dan mengendalikan hubungan dalam jaringan. Data dikirim dari satu simpul langsung kesimpul lainnya sebagai penerima.

Kelebihan Topologi Point to Point

  - Mudah menghubungkan antar komputer.

  - Membutuhkan kabel yang pendek.

Kekurangan Topologi Point to Point

  - Seluruh jaringan akan mati bila kabel utama terputus.

  - Sulit mencari dan memperbaiki kerusakan apabila terjadi kerusakan pada jaringan.

  - Tidak mungkin dimplementasikan pada jaringan dengan banyak komputer.

2.2 Star Network

Topologi jaringan dimana setiap nodes dalam jaringan terhubung dengan node pusat dengan hubungan point to point. Semua data yang ditransmisikan ke node dalam jaringan selalu ditransmisikan ke node pusat yang kemudian ditransmisikan ke nodes di dalam

jaringan, walupun node pusat mungkin juga sebuah titik koneksi biasa tanpa ada perangkat aktif untuk mengulang sinyal.

Sebuah koneksi point to point kadang dikategorikan sebagai bagian khusus dari topologi star. Maka dari itu jenis jaringan terkecil dari topologi star network akan terdiri dari sebuah koneksi point to point ke node kedua yang diatur oleh hub. Berdasarkan hal tersebut,

tipe jaringan terkecil berikutnya dari topologi star network terdiri dari satu node pusat yaitu hub dengan dua koneksi yang terpisah ke dua nodes cabang.

Walaupun kebanyakan jaringan yang didasarkan pada topologi ini memerlukan penggunaan hub sebagai node pusat, namun masih ada kemungkinan untuk mengimplementasikan sebuah jaringan yang didasarkan pada topologi star dengan menggunakan sebuah komputer atau bahkan titik koneksi biasa sebagai hub atau node pusat. Model jaringan bintang ini relatif sangat sederhana, sehingga banyak digunakan oleh pihak bank yang biasanya mempunyai banyak kantor cabang yang tersebar dipelbagai lokasi. Dengan adanya konfigurasi bintang ini, segala macam kegiatan yang ada di kantor cabang dapat dikontrol dan dikoordinasikan dengan baik. Disamping itu, dunia pendidikan juga banyak memanfaatkan jaringan bintang ini guna mengontrol kegiatan anak didik mereka.

Topologi ini dirancang dengan setiap node (file server, workstation, dan periferal) terhubung secara langsung ke jaringan pusat atau biasa disebut concentrator. Data pada sebuah jaringan bintang selalu melalui hub atau concentrator sebelum menuju sasaran. Hub atau concentrator mengatur dan mengelola seluruh jaringan. Selain itu, hub juga dapat berperan sebagai repeater untuk data flow. Konfigurasi semacam ini biasanya memakai kabel twisted pair. Selain itu bisa juga memakai kabel coaxial ataupun kabel fiber optik.

Kelebihan Topologi Star Network

- Jaringan tidak mudah terganggu oleh adanya koneksi baru maupun saat adanya computer yang tidak disembung.

- Mudah mendeteksi gangguan pada jaringan.

- Mudah pengaplikasiannya.

Kekurangan Topologi Star Network

  - Memerlukan kabel yang cukup panjang.

  - Jika hub/concentrator gagal berfungsi maka semua jaringan akan terputus.

  - Lebih mahal dengan adanya concentrator.

Peralatan Yang Digunakan dalam Topologi Star Network

Jenis NIC Ethernet Card, LocalTalk Kabel Twisted Pair, Fiber Optic Connector RJ-45, ST Connector, SC Connector Protokol Ethernet, LocalTalk Hub/Switch 10Base 8 ports , 10Base 16ports , Ethernet Hub/Switch 8 ports , Ethernet Hub/Switch 16 ports

2.3 Ring Network

Topologi Cincin merupakan topologi jaringan yang tertua. Topologi Ring Network ini diperkenalkan dengan penyesuaian analog dan digital yang digunakan dalam sistem telepon. Sesuai dengan namanya, strukturnya berbentuk seperti cincin. Perangkat yang biasa digunakan untuk topologi ini ialah hub. Topologi jaringan ini memiliki struktur dengan setiap nodes dalam jaringan terhubung dengan kedua nodes yang lain di jaringan dan dengan node pertama dan terakhir saling terhubung satu sama lain, membentuk cincin. Semua data yang ditransmisikan diantara nodes dalam jaringan berjalan dari satu node ke node berikutnya dengan pola sirkuler dan data umumnya lompat secara searah.Pada jaringan ini terdapat beberapa peralatan yang saling dihubungkan satu dengan lainnya dan pada akhirnya akan membentuk bagan seperti halnya sebuah cincin. Jaringan cincin tidak memiliki suatu titik yang bertindak sebagai pusat ataupun pengatur lalu lintas data, semua simpul mempunyai tingkatan yang sama. Data yang dikirim akan berjalan melewati beberapa simpul sehingga sampai pada simpul yang dituju. Dalam menyampaikan data, jaringan bisa bergerak dalam satu ataupun dua arah.

Data yang dikirim atau diterima tetap bergerak satu arah dalam satu saat. Pertama, pesan yang ada akan disampaikan dari titik ke titik lainnya dalam satu arah. Apabila ditemui kegagalan, misalnya terdapat kerusakan pada peralatan yang ada, maka data yang ada akan dikirim dengan cara kedua, yaitu data kemudian akan ditransmisikan dalam arah yang berlawanan, dan pada akhirnya bisa berakhir pada tempat yang dituju.

Konfigurasi semacam ini relatif lebih mahal apabila dibanding dengan konfigurasi jaringan bintang. Hal ini disebabkan karena setiap simpul yang ada akan bertindak sebagai komputer yang akan mengatasi setiap masalah yang dihadapi, serta harus mampu membagi sumber daya yang dimilikinya pada jaringan. Di samping itu, sistem ini lebih sesuai digunakan untuk sistem yang tidak terpusat (decentralized-system), dimana tidak diperlukan adanya suatu prioritas tertentu.

Kelebihan Topologi Ring Network

  - Aliran data cepat.

  - Mampu melayani lalu lintas data yang padat.

  - Waktu yang diperlukan dalam mengakses data optimal.

  - Komunikasi antar terminal mudah.

  - Tidak terjadi data-collision.

Kekurangan Topologi Ring Network

  - Memerlukan kabel yang lebih panjang

  - Jika kabel utama bermasalah maka semua jaringan akan terputus.

  - Penambahan dan pengurangan terminal sukar dilakukan.

Peralatan Yang Digunakan dalam Topologi Ring Network

Jenis NIC Token Ring Card, Kabel Twisted Pair, Connector RJ-45, Protokol Token Ring

Alat Lain MAU (Multistation Access Unit), untuk menghantar data melalui cincin

2.4 Mesh Network

Topologi ini dapat dibedakan menjadi dua, yaitu :

2.4.1 Full Mesh

Jenis topologi jaringan dimana masing-masing nodes dari jaringan terhubung dengan nodes lain dalam jaringan dengan hubungan point to point. Ini membuat semakin mungkin dari data untuk ditransmisikan dari setiap node tunggal. Fully connected mesh topology ini secara umum terlalu mahal dan rumit untuk diterapkan. Walapun topologi ini digunakan ketika hanya ada sejumlah nodes untuk saling berhubungan. Pada fully connected network yang terdiri dari sebanyak n node, terdapat p=n(n-1)/2 direct paths atau cabang. Dengan p adalah jumlah cabang dalam jaringan.

2.4.2 Partial Mesh

Jenis topologi jaringan dimana beberapa nodes dari jaringan yang terhubung lebih dari satu nodes dengan koneksi point to point. Hal tersebut memungkinkan user mengambil manfaat yang diberikan oleh physical fully connected mesh topology tanpa biaya dan kompleksitas yang diperlukan untuk sebuah koneksi antar node dalam jaringan.

2.5 Tree Network

Topologi jaringan pohon memadukan karakteristik dari jaringan linier dan jaringan bintang. Jaringan ini terdiri dari sekumpulan workstation berkonfigurasi dengan struktur bintang yang terhubung dengan kabel bus backbone. Jaringan pohon memungkinkan perluasan dari sub jaringan yang telah ada.

Pada jaringan pohon, terdapat beberapa tingkatan simpul (node). Pusat atau simpul yang lebih tinggi tingkatannya, dapat mengatur simpul lain yang lebih rendah tingkatannya. Data yang dikirim perlu melalui simpul pusat terlebih dahulu. Misalnya untuk bergerak dari komputer dengan node-3 ke komputer node-7 seperti halnya pada gambar, data yang ada harus melewati node-3, 5 dan node-6 sebelum berakhir pada node-7.

Keunggulan jaringan model pohon seperti ini adalah dapat terbentuknya suatu kelompok yang dibutuhkan setiap saat. Sebagai contoh, perusahaan dapat membentuk kelompok yang terdiri atas terminal pembukuan, serta kelompok lain dibentuk untuk terminal penjualan. Adapun kelemahannya adalah apabila simpul yang lebih tinggi tidak berfungsi, maka kelompok lain yang berada dibawahnya akhirnya juga menjadi tidak efektif. Cara kerja jaringan pohon ini relatif lambat.

Kelebihan Topologi Tree Network

  - Koneksi secara langsung (point to point) pada segmen jaringan tunggal.

  - Topologi jaringan ini didukung oleh beberapa vendor hardware dan software.

Kekurangan Topologi Tree Network

  - Cakupan segmen jaringan tergantung dari kabel.

  - Jika jalur backbone putus, seluruh segmen jaringan akan putus.

  - Pengimplementasiannya sulit.

Dalam membangun jaringan pohon, harus dipertimbangkan protokol Ethernet yang mengikuti aturan 5-4-3. Salah satu aspek dari Ethernet protocol mensyaratkan bahwa sinyal yang dikirim menjangkau setiap bagian jaringan dalam waktu waktu tertentu. Setiap ada sinyal yang melewati concentrator atau repeater membutuhkan alokasi waktu yang lebih

lama. Sehingga aturan ini menyatakan bahwa di antara dua simpul jaringan hanya boleh ada maksimum 5 segmen jaringan yang terhubung dengan 4 repeater/concentrator. Kemudian, hanya boleh 3 dari segmen itu boleh disi dengan segmen jaringan yang baru jika dihubungan dengan kabel coaxial. Aturan ini dapat dilihat dengan contoh pada gambar 6. Namun aturan ini tidak berlaku pada protokol lain.

3. PENGUJIAN DAN PEMBAHASAN

3.1 Kasus Uji Pengujian Topologi Jaringan

Berdasarkan tata rancang dan teknik pengujian yang telah dijelaskan, maka dirancang kasus-kasus uji sebagai berikut :

1. Kasus Uji 1

bertujuan untuk melihat implementasi graf dalam topologi jaringan.

2. Kasus Uji 2

bertujuan untuk menguji kebenaran teori graf yang juga berlaku pada topologi jaringan.

3.2 Evaluasi Hasil Pengujian AESEncryptor

3.2.1 Kasus Uji 1

Pada kasus uji 1 dibandingkan dengan graf untuk dianalogikan strukturnya dengan struktur pada topologi jaringan, misalnya :

Point to point

Struktur dari topologi jaringan ini dapat digambarkan dengan graf.

Simpul dari graf di atas dianalogikan sebagai CPU.

Star Network

Graf yang diimplementasikan pada topologi jaringan ini adalah

4 buah simpul di kanan adalah CPU sedangkan simpul yang dikiri adalah concentrator atau hub.

Ring Network

Graf yang diimplementasikan pada topologi ring network dapat digambarkan sebagai berikut :

Graf ini adalah graf teratur dengan simpul yang masing-masing berderajat 2. Masing-masing simpul pada graf ini adalah CPU.

Tree Network

Graf yang bersesuaian adalah suatu pohon yang merupakan bentuk khusus dari graf. Pohon ini dapat digambarkan sebagai berikut :

Akar pertama dari pohon di atas adalah server. Sedangkan akar pada level kedua adalah concentrator atau hub. Sedangkan daun dari pohon ini adalah CPU. Dari hasil pengujian di atas diketahui bahwa jaringan/network ternyata memiliki struktur topologi yang dapat diimplementasikan dari graf. Setiap komponen dalam jaringan dengan topologi tertentu diatur tata letaknya sesuai dengan graf yang bersesuain.

3.2.2 Kasus uji 2

Pada kasus uji 2 akan dibuktikan hukum yang berlaku dalam graf, berlaku pula dalam topologi jaringan.

Graf

Diambil contoh pada Ring Network. Graf yang bersesuaian dengan topologi jaringan cincin adalah Graf Teratur dengan simpul berderajat 2. Sesuai teorema pada graf teratur maka harus berlaku :

e = n.r / 2

dengan

e = jumlah sisi graf

n = jumlah simpul

r = derajat simpul

ambil contoh sebuah ring network, simpul adalah CPU, misal jumlah simpul n = 8. Derajat pada struktur ini adalah r = 2 dengan jumlah kabel yang bersisian dengan CPU berjumlah 2. Maka sesuai rumus berlaku e = 8.2 / 2 = 8 Ternyata benar, pada gambar di atas, jumlah kabel ada 8, sehingga teori graf juga berlaku pada topologi jaringan ini.

Pohon

Sesuai teorema pada pohon, jumlah sisi pada sebuah pohon (E) adalah jumlah simpul minus satu. Dari gambar di atas, didapatkan jumlah simpul adalah jumlah periferal yaitu n = 10. Sehingga menurut persamaan diatas didapat jumlah sisi, E = n–1 = 10–1 = 9

Dari gambar tersebut, jumlah kabel yang menghubungkan masing-masing periferal berjumlah 9, sehingga topologi pohon mempunyai struktur yang diimplementasi dari graf pohon. Dari kedua hasil uji diatas didapatkan bahwa topologi jaringan mempunyai struktur dengan berpedoman pada graf. Sehingga setiap teorema dalam graf berlaku pula pada topologi jaringan.

4. KESIMPULAN

Kesimpulan yang didapat dari studi mengenai implementasi graf pada topologi jaringan adalah :

Dalam pemilihan penggunaan topologi jaringan, harus memperhatikan beberapa faktor berikut :

a)      Dana

Jaringan linear merupakan jaringan yang membutuhkan dana paling sedikit dalam penginstallan, karena membutuhkan kabel yang pendek dan tidak membutuhkan hub atau concentrator.

b)      Panjang kabel yang dibutuhkan

Jaringan linier menggunakan kabel paling pendek diantara semua topologi yang lain.

c)      Expansi jaringan

Jaringan bintang merupakan jaringan yang paling fleksibel, mudah dalam perluasan

maupun pengurangan jaringan, cukup dengan menambahkan lagi concentrator/hub.

d)      Tipe Kabel

Tipe kabel yang umum digunakan adalah kabel unshielded twisted pair yang biasa digunakan pada tipologi jaringan bintang.

- Teorema-teorema graf telah terbukti cocok dan bersesuaian dengan topologi jaringan, sehingga optimasi jaringan dapat dengan mudah dilakukan dengan memanfaatkan teorema-teorema graf, terutama untuk jaringan yang sangat luas.

- Mempelajari topologi jaringan merupakan hal yang sangat penting guna menjaga efektifitas jaringan, fleksibilitas dalam hal perluasan jaringan, aliran data, penanganan kerusakan jaringan, dsb.

DAFTAR REFERENSI

1.      Munir, Rinaldi. (2003). Diktat Kuliah IF2153 Matematika Diskrit.edisi keempat, Program Studi Teknik Informatika, Sekolah Teknik Elektro dan Informatika, Institut Teknologi Bandung.

2.      Groth, David; Toby Skandier. 2005. 'Network+Study Guide, Fourth Edition'. Sybex, Inc.

3.      Committee T1A1 Performance and Signal Processing. 2005. ANS T1.523-2001. Telecom Glossary 2000. ATIS Committee T1A1.

4.      Google.com, Numerous university professor's notes. 2005.

5.      Sheldon, Tom. Token Bus Network. 2006. London:Prentice Hall.

6.      Wikipedia http://wikipedia.org/ Tanggal akses: 28 Desember 2008 pukul 19:00.

7.      http://fcit.coedu.usf.edu/ Tanggal akses: 28 Desember 2008 pukul 19:00.

8.      http://myschoolnet.ppk.kpm.my/ Tanggal akses: 30 Desember 2008 pukul 20:00.

9.      http://en.wikipedia.org/wiki/Network_topology Tanggal akses: 30 Desember 2008 pukul 20:00.

10.  http://kuliah.dinus.ac.id/ Tanggal akses: 30 Desember 2008 pukul 21:00

TEORI GAME

Teori Game dan Pembuatan Intelegensi Buatan

Disusun Oleh :

Deky Sudrajat

09360003

TEKNIK INFORMATIKA

Institut Sains & Teknologi Nasional

2009

Teori Game dan Pembuatan Intelegensi Buatan

Abstrak

Makalah ini membahas tentang permainan dan beberapa hal mengenai intelegensi buatan. Pada makalah ini akan melihat sebuah permainan sebagai salah satu objek matematika yang nyata yang menggunakan pohon berarah pada pembuatan game dan perhitungan langkah yang mungkin dilakukan pemain. Makalah ini juga membahas intelegensi buatan sebagai bagian yang tidak terpisahkan dalam permainan. Pembahasan akan dibatasi hanya sekitar permainan sederhana dan sudah umum dalam masyarakat.

1. Pendahuluan

Dalam dunia modern ini, penggunaan teknologi untuk menunjang kegiatan manusia semakin banyak dan sangat berkembang. Salah satu bentuk kebutuhan pokok manusia adalah hiburan dan sebagai salah satu wujudnya adalah berbagai macam permainan. Penulis memilih tema ini untuk pembuatan makalah karena ketertarikan penulis terhadap dunia game yang terus berkembang secara

pesat pada zaman modern ini.

Dalam pembuatan suatu permainan digunakan banyak konsep graf berarah. Graf merupakan salah satu model matematika yang paling banyak aplikasinya dalam dunia nyata. Salah satu bentuk graf yang umum adalah bentuk pohon. Pohon merupakan bentuk graf terhubung yang tidak mempunyai rangkaian sederhana. Pohon dapat dibentuk berupa pohon n-ary dengan n merupakan banyaknya derajat maksimum yang dimiliki setiap simpul.

2. Representasi Game

Jika kita lihat dari sudut pandang yang berbeda, kita dapat melihatnya sebagai model matematika atau lebih tepat sebagai graf. Graf berarah dengan alur yang berkelanjutan yang kemudian akan membentuk pohon. Karena kebanyakan persoalan dalam dunia game dapat direpresentasikan sebagai suatu sistem kombinatorial dan kemudian membentuk pohon, maka dibentuklah suatu cabang ilmu khusus yang menanganinya sering disebut sebagai game-theory dan untuk representasi khusus dengan pohon dibuatlah extensive-form yang kemudian sangat banyak digunakan untuk pegembangan intelegensi buatan. Pohon yang dibentuk dengan simpul dan sisi yang mencerminkan suatu unsur dalam permainan tersebut. Umumnya simpul akar pada pohon merepresentasikan jumlah pemain kemudian simpul-simpul dibawahnya menjadi berkalang terus menerus untuk merepresentasikan jumlah kemungkinan langkah yang dapat diambil oleh pemain.

Bentuk representasi dari suatu permainan dapat berbeda-beda disesuaikan dengan spesifikasi yang digunakan dan bentuk serta jenis permainannya. Bentuk dan jenis permainan dapat dicontohkan seperti apakah permainan merupakan permainan dengan banyak pemain, hanya dapat dimainkan 1 orang, sistem dan peraturan yang digunakan, dll..

2.1 Bentuk Normal

Bentuk ini merupakan salah satu representasi dari game-theory yang paling tua. Representasi sebenarnya dari bentuk ini adalah sebuah matriks yang mengkalkulasi langkah yang dilakukan pemain dan efeknya terhadap pemain lainnya. Bentuk ini merupakan bentuk yang masih digunakan untuk merepresentasikan permainan strategi. Hal ini dikarenakan kemudahan dan akurasi dalam pembacaan aksi yang dilakukan oleh satu pemain dan efeknya terhadap keadaan lainnya. Sebagai contoh, jika pemain melakukan suatu langkah maka pemain akan mendapatkan poin sedangkan lawannya akan kehilangan poinnya. 

Matriks yang terbentuk akan selalu meperhitungkan langkah yang dilakukan serta efek pada pemain lain. Sebagai contoh, misalnya untuk sebuah game berkelanjutan yang dimainkan oleh dua orang seperti yang digambarkan pada gambar 2.1, pemain ke-2 akan melakukan langkah dengan strategi sebagai berikut :

1. Kiri jika pemain 1 melangkah ke atas dan kiri

2. Kiri jika pemain 1 melangkah ke atas dan kanan

3. Kanan jika pemain 1 melangkah ke atas dan kiri

4. Kanan jika pemain 1 melangkah ke atas dan kanan

5. Dan seterusnya

2.2 Bentuk Ekstensif

Representasi bentuk ini menggunakan struktur pohon sebagai media yang menyimpan data kejadian pada game serta menghitung kemungkinan langkah yang bisa diambil oleh pemain. Bentuk lengkap dari pohon ini selalu mencantumkan :

1. Pemain

2. Kemungkinan untuk setiap pemain

3. Apa yang bisa dilakukan pemain pada setiap langkah

4. Apa yang diketahui pemain untuk setiap langkah

5. Efek yang akan didapat untuk setiap kombinasi langkah

Selain dari bentuk pohon sederhana seperti di atas, terdapat juga bentuk lanjutan yang digunakan jika sebuah permainan mempunyai aksi yang tak terhingga. Bentuk representasinya adalah pohon dengan tak berhingga kemungkinan atau node yang kemudian lebih membentuk suatu ruang. 1 ruang dengan ruang lainnya dihubungkan dengan node yang beririsan sebagai bentuk aksi yang dilakukan.

3. Jenis Game

Seperti yang telah dibahas sebelumnya bahwa representasi dari suatu game harus didasarkan pada spesifikasi dan jenisnya. Berikut ini adalah beberapa jenis permainan berdasarkan klasifikasi umum yang mempengaruhi pemilihan representasinya dalam model matematika.

3.1 Simetris dan Asimetris

Jenis permainan lebih terlihat pada bentuk matriks yang dibentuk untuk merepresentasikannya. Permainan jenis ini menggunakan matriks kombinatorial dengan bentuk matriks yang simetris atau tidak simetris. Matriks simetris contohnya adalah matriks berukuran 2x2, 3x3, dst.. Berikut ini contoh gambaran matriks untuk representasi game yang simetris dan tidak simetris

3.2 Zero Sum dan non-Zero Sum

Konsep dari game ini dapat dilihat dari aturan yang berlaku dalam permainan ini . Pada dasarnya jenis ini adalah game dengan interaksi antar pemain yang berkelanjutan. Zero-Sum Game berakibat setiap aksi dari satu pemain selalu berdampak pada pemain lain. Sebagai contoh adalah suatu permanan kartu dengan taruhan. Dengan memisalkan terdapat 2 orang pemain, bila suatu pemain A memenangkan sebanyak 5 poin maka pemain B akan kehilangan sebanyak 5 poin juga. Dengan menganggap bahwa kekalahan adalah suatu minus dari menang, maka pada permainan tadi hanya akan menghasilkan nol pada akhirnya karena (5 – 5 = 0).

Non-Zero-Sum Game tentunya merupakan kebalikan dari penjabaran di atas. Pada jenis ini bila dimisalkan terdapat dua pemain maka untuk poin awal nol untuk setiap pemain, kedua pemain akan bermain untuk memenangkan poin hingga suatu titik akhir. Contohnya jika permainan berhenti jika ada pemain yang mendapat poin 10 terlebih dahulu.

3.3 Simultaneos dan Sequential Games

Bentuk dari representasi ini telah dijelaskan pada bagian bentuk ekstensif karena merupakan representasi pohon. Untuk simultaneous-game pohon yang terbentuk akan lebih merupakan bentuk ruang-ruang yang saling berpotongan.

3.4 Game dengan Informasi sempurna dan tidak sempurna

Pada struktur ini, perbedaan paling banyak terlihat pada bentuk pohon yang terbentuk. Pohon dengan informasi sempurna seperti yang telah dijelaskan pada bagian bentuk ekstensif pada bab representasi permainan yaitu pemain lain selalu tau langkah yang diambil pemain lain. Contoh permainan jenis ini adalah catur, go, dll..

Game dengan informasi tidak sempurna hanya berbeda pada bagian bahwa suatu pemain tidak dapat tau langkah pemain lain. Sehingga selalu ada kemungkinan bahwa kedua pemain melakukan langkah yang sama. Berikut ini adalah gambar pohon untuk permainan jenis informasi tidak sempirna, garis putus-putus pada pohon berarti bahwa tidak ada aksi yang memperhitungkan langkah yang berada pada node yang ada pada ujung garis putus-putus lainnya.

4. Contoh Pemecahan Game dengan Pohon

Pada sub bab ini akan dibahahas sepenggal contoh pemecahan game dengan bantuan pohon. Sebagai contoh akan digunakan permainan dengan kompleksitas terendah yaitu permaian Tic Tac Toe.

4.1 Aplikasi Lainnya dari Teori Game dalam berbagai bidang

Seperti kita ketahui bahwa penggunaan graf dan pohon sangat banyak aplikasinya dalam kehidupan. Game-theory juga merupakan salah satu konsep yang dapat diimplementasikan dalam bidang lainnya. Dengan menggunakan konsep pohon, kombinatorial matriks, dan dilengkapi dengan algoritma minimum.

4.1.1 Politik dan Ekonomi (Konsep Pohon)

Beberapa pemakaian yang paling mencolok adalah pada pengambilan keputusan yang berhubungan dengan sistem pemerintahan. Pada penerapan politik ini, untuk satu masalah yang sangat membutuhkan keputusan terbaik karena menyangkut masalah suatu negara. Dengan menggambarkannya secara ekstensif berupa pohon dengan informasi lengkap, dapat dimisalkan semua elemen yang mempengaruhi dan kemungkinan keputusan sebagai suatu node. Dengan menerapkan minimum tree dapat terlihat keputusan dengan resiko terkecil, dengan algoritma minimax (algoritma untuk mempertimbangkan keputusan terbaik) akan didapat solusi terbaik sebagai pemecahan masalah.

4.1.2 Biologi (Konsep Matriks Kombinatorial)

Konsep matriks kombinatorial dari game-theory banyak digunakan dalam bidang biologi khususnya yang menyangkut evolusi dan habitat hewan. Untuk masalah habitat hewan misalnya, sangat mirip dengan matriks kombinatorial pada Zero-Sum Game. Sebagai contoh permisalan adalah masalah piramida makanan yang berlaku pada hewan. Misalkan terdapat suatu populasi sebanyak n ayam dan n elang dengan asumsi bahwa ayam adalah makanan dari elang. Sehingga untuk bertahan hidup dan memperbanyak jenisnya, elang harus memakan ayam. Untuk satu kali memangsa maka di sini kemungkinan elang akan menjadi (n + 1) dan ayam akan (n - 1). Hal yang sama juga berlaku untuk teori territorial pada hewan. Selain dari dua contoh bidang di atas, masih banyak bidang lainnya yang memakai konsep hampir sama dengan game-theory.

5. Intelegensia Buatan

Bila membahas tentang suatu game, maka pembahasan intelegensi buatan adalah suatu hal yang sepertinya tidak dapat terpisahkan. Karena tanpa bidang ini, suatu permainan tidak akan dapat berjalan karena sebenarnya semua tindakan program pada permainan merupakan suatu intelegensi buatan.

Sebagai contoh adalah jika kita memainkan permainan catur secara elektronik dan hanya terdiri dari satu orang pemain, maka lawan kita adalah komputer dengan program intelegensi buatan untuk permainan catur. Dengan membuat suatu pohon lengkap berisi kemungkinan langkah yang juga memprediksi langkah kita, program akan terus mengeksekusi langkah terbaik yang memungkinkan. Begitu juga dengan banyak permainan lainnya. Pokok utama dari program ini sebenarnya adalah algoritma pencarian. Dalam pengembangan intelegensi buatan, para peneliti lebih konsentrasi tentang bagaimana cara membuat suatu pohon pencarian yang berukuran lebih kecil untuk menangani suatu kasus yang sama. Dalam pengembangannya banyak algoritma pencarian telah dibuat, namun pada zaman modern ini banyak dari pengembangan intelegensi buatan yang memodifikasi algoritma Alpha-Beta. Algoritma ini merupakan algoritma dasar yang dinilai cukup mangkus karena kefektifannya dalam membentuk pohon pencarian yang sederhana dan akurat.

5.1 Algoritma Alpha-Beta

Algoritma ini merupakan suatu algoritma pencarian pada pohon n-ary dengan memanfaatkan suatu algoritma minimax. Algoritma ini dipakai untuk permainan dengan 2 pemain. Inti dari algoritma ini adalah dengan mengurangi pencarian langkah yang tidak perlu jika sudah diketahui bahwa suatu langkah A lebih buruk dari langkah B. Sehingga pohon pencarian untuk langkah A akan berhenti.

Dengan menggunakan asumsi bahwa pemain pertama selalu dalam keuntungan dari pemain lain, algoritma ini kemudian akan akan membuat suatu pohon lengkap dengan memperhitungkan kedalaman dan kemungkinan langkah. Algoritma ini terdiri dari dua nilai yaitu alpha dan beta. dengan menggunakan bahwa alpha adalah minus tak terhingga dan beta adalah positif tak terhingga, secara terus menerus secara rekursif algoritma akan merubah nilai alpha dan beta sesuai langkah yang dilakukan pada setiap node. Ketika beta menjadi lebih kecil dari alpha, algoritma akan berhenti. Berikut adalah contoh penggalan algoritma alphabeta :

int AlphaBeta(int depth, int alpha, int beta)

{

if (depth == 0)

return Evaluate();

GenerateLegalMoves();

while (MovesLeft()) {

MakeNextMove();

val = -AlphaBeta(depth - 1, -beta, -alpha);

UnmakeMove();

if (val >= beta)

return beta;

if (val > alpha)

alpha = val;

}

return alpha;

}

Pada saat ini sudah banyak algoritma yang memodifikasi algoritma ini dan sudah terbukti lebih cepat dan efisien secara waktu. Namun masihbanyak kekurangan karena disesuaikan dengan spesifikasi khusus yang dibawanya. Sehingga banyak yang sudah terbukti lebih cepat tetapi dalam pengelolaan memori dan ruang lebih buruk dari algoritma alpha-beta.

Suatu permainan dapat diukur tingkat kompleksitasnya sesuai dengan pembuatan gametree yang mendasari permainan tersebut. Pada akhir makalah terdapat table yang menunjukkan kompleksitas permainan. Go merupakan permainan dengan papan yang memiliki kompleksitas paling tinggi.

5.3 Bilangan Shannon

Merupakan bilangan yang mencerminkan kompleksitas dalam permainan catur, bernilai 10120 . bilangan itu merupakan suatu batas bawah yang menghitung kompleksitas permainan catur. Shannon juga menambahkan bahwa untuk memainkan suatu permainan lengkap, terdapat setidaknya 50 kemungkinan yang harus diingat program dan 30 langkah resmi. Dengan asumsi bahwa suatu permainan akan bertahan sampai sekitar 40 langkah tanpa ada yang menyerah.

Dengan cara mundur kebelakang atau memulai dari daun terlebih dahulu perhitungan tentang menang, kalah, atau seri dapat diperkirakan dari awal, kemudian akan dijalankan kemungkinankemungkinan langkah sesuai dengan langkah yang pertama kali dilakukan. Shannon menghitung bahwa 64! / 32!(8!)2(2!)6 atau sekitar 1043 adalah batas atas yang mungkin. Dalam hal ini terhitung juga berbagai langkah yang tidak mungkin.

KESIMPULAN

Kesimpulan yang didapat dalam pembahasan masalah graf pada makalah ini adalah :

1.    Graf merupakan model matematika yang sangat aplikatif dalam banyak bidang.

2.    Pada pembuatan teori game dan Intelegensi buatan sangat digunakan salah satu bentuk graf yaitu bentuk pohon.

3.    Pada teori game, juga terdapat hubungan kombinatorial yang kemudian dapat disimpan dalam bentuk matriks.

4.    Struktur pohon merupakan struktur yang baik untuk algoritma pencarian.

DAFTAR PUSTAKA

[1] Munir, Rinaldi.2006.Diktat Kuliah IF2153 Edisi Keempat. Program Studi Teknik Informatika, Sekolah Teknik Elektro dan Informatika, Institut Teknologi Bandung.

[2]http://www.wikipedia.org/wiki/Game_complexity

[3]http://www.cs.mcgill.ca/~cs251/OldCourses/19 97/topic11

[4]http://www.ics.uci.edu/~eppstein/cgt [5]http://mainline.brynmawr.edu/Courses/cs372/f all2004/AB.html