PBWT3-०६.२००९.१.05095-खैरिल Anam-B1

Framework YUI Library

Framework adalah sekumpulan perintah/fungsi dasar yang dapat membantu dalam menyelesaikan proses-proses yang lebih kompleks Framework itu adalah kerangka kerja. Kerangka kerja yang memudahkan kita menyelesaikan suatu pekerjaan. Jadi Framework adalah sesuatu yang telah diatur menjadi suatu pola yang memudahkan kita dalam penggunaannya.
Awal pengembangan Framework dimulai saat memasuki era Web 2.0, generasi kedua dari layanan berbasis web dimana lebih meniktikberatkan pada kolaborasi online, sharing content antar pengguna dan lebih terarah ke User Content Generated.
Nah, berdasarkan kebutuhan akan konsep dan paradigma baru dalam pengembangan aplikasi berbasis web tersebut maka dalam pengembangannya diperlukan suatu sistem alur kerja yang bisa memudahkan dalam menciptakan aplikasi berbasis web yang canggih dan interaktif. Salah satu yang sering digunakan para developer tersebut adalah Farmework Yui Libarary dimana didalamnya terdapat tampilan yang telah ditulis sedemikian rupa dimana sangat membantu dalam pengembangan sebuah Aplikasi Web, terutama dalam pengembangan AJAX (Asynchronous Java And XML). Sebuah teknik pemanggilan cepat tanpa melakukan reload terhadap suatu page.Dengan Farmework Libraries tersebut para programmer bisa dengan mudah mengimplementasikan paradigma WEB 2.0 yang baru seperti User interface yang dinamik dan sangat interaktif kepada usernya.
Salah satu FRAMEWORK yang akan saya bahas adalah Framework Yui Library karena mampu memberi kemudahan yang luar biasa bagi developer dalam membangun aplikasi web
Mengapa kita butuh framework?
Bagi anda yang belum familiar dengan framework, framework adalah sekumpulan fungsi,
class, dan aturan-aturan. Berbeda dengan library yang sifatnya untuk tujuan tertentu saja, framework bersifat menyeluruh mengatur bagaimana kita membangun aplikasi. Framework memungkinkan kita membangun aplikasi dengan lebih cepat karena sebagai developer kita akan lebih memfokuskan pada pokok permasalahan sedangkan hal-hal penunjang lainnya seperti koneksi database, form validation, GUI, dan security; umumnya telah disediakan oleh framework. Disamping itu dengan aturan-aturan yang jelas dan harus dipatuhi, aplikasi kita lebih solid, more readable, dan kolabarasi dalam tim dapat lebih mudah dilaksanakan.

YUI LIBRARY
YUI: YUI Grids CSS menawarkan empat lebar halaman preset, enam template preset, dan kemampuan untuk stack dan daerah sarang dibagi dua, tiga, atau empat kolom. File 4KB menyediakan lebih dari 1000 kombinasi tata letak halaman. Fitur lain termasuk: Mendukung cairan lebar (100%) layout serta telah ditetapkan fixed-width layout di 750px, 950px dan 974px, dan kemampuan untuk dengan mudah menyesuaikan untuk setiap nomor, Mendukung kustomisasi mudah lebar untuk fixed-width layout , Fleksibel dalam merespon pengguna diprakarsai font-size penyesuaian, kolom Template adalah sumber-order independen, sehingga Anda dapat menempatkan konten Anda paling penting pertama dalam lapisan markup untuk meningkatkan aksesibilitas dan optimasi mesin pencari (SEO), Self-kliring footer. Tidak peduli yang kolom lebih panjang, tetap footer di bagian bawah, Layouts kurang dari 100% secara otomatis



Ketersediaan YUI di Node.js sebagai modul NPM
Formal pengenalan "malam", menawarkan kulit kedua kita
Pengenalan App, Button, CSSButton, Setang, Pjax, komponen TestConsole
Refactoring CSS Grids untuk menjadi lebih ringan dan serbaguna
Refactoring dari utilitas Get untuk dukungan fitur tambahan dan peningkatan kinerja
Refactoring dari Loader untuk melaksanakan fungsi asynchronous Get s
Komponen Uploader menerima implementasi HTML5 yang meliputi drag-and-drop fungsi, ditambah skenario peningkatan jauh lebih baik progresif, manajemen antrian granular dan aksesibilitas.
Keyboard navigasi menambah komponen Kalender
Perangkat tambahan untuk App, Grafik, dan DataTable komponen
Banyak perbaikan bug



Kerangka App keluarga modul, termasuk Model, Controller / Router, dan View telah menerima perangkat tambahan signifikan. Gambaran dari perubahan itu dibahas dalam sebuah posting blog sebelumnya, dan daftar rincian perubahan dapat ditemukan dalam file sejarah.
Kami memperkenalkan pemuatan asynchronous dalam Loader secara default. Ini berarti bahwa setiap Loader naskah menyuntikkan ke dalam halaman akan dimuat asynchronous. Hal ini akan mengurangi beban waktu dan meningkatkan kinerja dengan memungkinkan browser untuk mengambil sebagai skrip banyak sekaligus karena dapat. Jika modul kustom Anda benar dibungkus callback YUI.add, Anda akan melihat ada perbedaan sama sekali. Namun, jika Anda memuat modul khusus yang memerlukan pemuatan naskah memerintahkan (tergantung pada modul lain, dinamis Seluruh), Anda perlu mengubah modul Anda config untuk memberitahu Loader untuk tidak memuat modul-modul dengan bendera async. Anda dapat melakukan ini dengan menambahkan async: config palsu untuk definisi modul dan Y.Get.script tidak akan memuatnya asynchronous.
Uploader adalah refactored untuk mendukung fungsi HTML5 bila tersedia. Versi 3.4.1 sudah usang dan tersedia sebagai uploader-usang. Sebuah panduan migrasi tersedia di http://yuilibrary.com/yui/docs/uploader/migration.html.
Update untuk format kustom Grafik dapat menyebabkan masalah kompatibilitas ke belakang ketika melakukan upgrade dalam keadaan tertentu. Silakan lihat bagian Masalah Dikenal untuk lebih detail.
DataTable itu refactored untuk Model leverage, ModelList, dan Lihat. Versi 3.4.1 sudah usang dan tersedia sebagai DataTable-usang, DataTable-base-usang, DataTable-sort-usang, dll Sebuah panduan migrasi tersedia di http://yuilibrary.com/yui/docs/datatable/migration html..

Inti ringan YUI dan arsitektur modular membuatnya terukur, cepat, dan kuat. Dibangun oleh insinyur frontend di Yahoo!, YUI kekuatan situs paling populer di dunia.
API YUI intuitif dan terdokumentasi dengan baik akan membawa Anda dari penanganan DOM dasar untuk membangun aplikasi performant dan dipertahankan pada browser desktop, perangkat mobile, dan server.

Oleh : PBWT3 (06.2009.1.0.05095) Khairil Anam B1

resume

Khairil Anam (06.2009.1.05095)

Pengantar Internet dan Web
Internet

 Internet à Interconnected-networking
 Network of computer networks
 Terdiri dari banyak subnetwork
 Heterogen
 Internet = hardware; web = software
 Komponen:
 Client (PC), server, modem, router, TCP/IP, dll
Sejarah Internet
 Departemen Pertahanan Amerika membentuk suatu jaringan komputer yang disebut ARPANET, untuk memungkinkan personil militer dan peneliti sipil bertukar informasi yang berkaitan dengan hal-hal militer.
 Melalui proyek ARPA (Advance Research Project Agency) mereka mendemonstrasikan hardware dan software komputer yang berbasis UNIX dapat melakukan komunikasi dalam jarak tak berhingga melalui saluran telepon.



Protokol TCP/IP
 Protokol à mirip dengan bahasa.
 TCP/IP (Transmission Control Protocol/Internet Protocol) adalah sekelompok protokol yang mengatur komunikasi data komputer di Internet.
 TCP bertugas memastikan bahwa semua hubungan bekerja dengan benar.
 IP adalah yang mentransmisikan data dari satu komputer ke komputer lain.
Komponen Aplikasi Web
 Web browser
Web Browser sebagai client untuk menginterpretasikan dan melihat informasi .Browser adalah suatu program yang dirancang untuk mengambil informasi dari suatu server komputer pada jaringan Internet. Informasi ini dikemas dalam page yang masing-masing memiliki beberapa link yang menghubungkan Web page ke sumber informasi lain. Jika suatu link diklik, browser akan melihat alamat dari tujuan link tersebut, kemudian mencari di Web server. Jika menemukan alamat dari tujuan link, browser akan menampilkan informasi yang ada. Jika tak menemukan alamat dari tujuan link
 Web server
Web server bertugas untuk menerima dan merespon permintaan-permintaan dari client (web browser).
Contoh
 Apache
 IIS
 Tomcat
 Lighttpd
 Dll
 URL
Universal Resource Locator URL adalah suatu alamat yang dipakai untuk menentukan lokasi informasi pada Web server, karena alamat ini mengambil informasi yang diminta oleh browser.
Nama domain beserta jenis organisasinya, antara lain:
• com ---> untuk komersial
• edu ---> untuk pendidikan
• net ---> untuk provider Internet
• id ---> untuk negara Indonesia
• gov ---> untuk Lembaga Pemerintahan
• int ---> untuk Organisasi International
• mil ---> untuk Organisasi Militer
• org ---> untuk Organisasi Umum
 HTTP
HTTP merupakan protokol yang menentukan Web browser dalam meminta/mengambil suatu dokumen, dan menentukan Web server dalam menyediakan dokumen yang diminta oleh Web browser. Ini adalah protokol standar yang dipakai untuk mengakses dokumen HTML. HTTP digunakan untuk menjelajahi Web yang berhubungan dengan banyak protokol lain.
 Web programming
Pemprograman web atau yg dikenal dengan Web Program adalah merupakan suatu pemprograman yang bertujuan untuk membngun sebuah web dengan mendesai dan memberikan source kode didalamnya, seperti php, yang umum digunakan adlah menggunakan macromedia dreamweaver.
 HTML
HTML adalah format data yang dipakai untuk membuat dokumen HyperText. Dokumen HTML disebut Mark Language, karena berisi tanda tanda tertentu yang digunakan untuk menentukan tampilan suatu teks dan tingkat kepentingan dari teks tersebut dalam suatu dokumen. Pada sistem HyperText pada dokumen HTML, Anda tidak harus membaca dokumen secara urut dari atas ke bawah, melainkan cukup menuju pada topik tertentu secara langsung dalam dokumen. Ini dikarenakan dokumen tersebut menggunakan teks penghubung ke suatu topik/ dokumen lain secara langsung.

Dasar HTML
Setiap dokumen html harus diwali dengan menuliskan tag dan tag
di akhir dokumen. Tag ini menandai dokumen HTML yang berarti adalah
dokumen HTML dalam satu dokumen hanya ada satu elemen html.Section atau elemen head ditandai dengan tag diawal dan tag diakhir. Section ini beiris informasi tentang dokumen HTML, mislnya informasi judul html yang ditandai dengan tag . Section body ditandai dengan tag dan diakhiri dengan tag diakhir. Section body merupakan isi dokumen yang akan ditampilakn pada browser.
Contoh – Listing 2.1 : contoh1.html


Hasil di Browser : contoh1.html

contoh jurnal

PENERAPAN KONSEP ALGORITMA MINIMAX & MTD(f)
PADA PERMAINAN TIC TAC TOE

Artificial Inteligence
Jurusan Teknik Informatika, Fakultas Teknologi Informasi
Institut Teknologi Adhitama Surabaya
E-mail: http://www.itats.ac.id


ABSTRACT

Minimax algorithm (also often called Minmax) is an algorithm that underlies step problem-solving mindset in some types of computer games, like tic-tac-toe, Othello, checkers, chess, dll.Pada essentially, very reliable Minimax algorithm to solve all problems in pencarianlangkah for computer games with a small number of possible settlement, as in a game of tic-tac-toe. However, if the Minimax algorithm used in the game with a large number of possibilities such as the tic tac toe games, Minimax algorithm requires a very long time to build a tree settlement.
This journal will try to explain a concept minimax algorithm and machine learning applied to the game of tic-tac-toe. After learning of the strategies for a game to get, minimax algorithm is expected to help the players to play tic-tac-toe with the good. The results of this process is expected to be compared with some other methods within the scope of artificial intelligence.

Keywords: Minimax Algorithm, Machine Learning, Game, Tic-Tac-Toe.

ABSTRAK
Algoritma Minimax (juga sering disebut Minmax) adalah sebuah algoritma yang mendasari pola pikir langkah penyelesaian masalah dalam beberapa jenis permainan komputer, seperti tic-tac-toe, othello, checkers, catur, dll.Pada dasarnya, algoritma Minimax sangat andal untuk menyelesaikan segala masalah dalam pencarianlangkah untuk permainan komputer dengan jumlah kemungkinan penyelesaian yang kecil, seperti pada permainan tic-tac-toe. Tetapi, jika algoritma Minimax digunakan pada permainan dengan jumlah kemungkinan penyelesaian yang besar seperti pada
permainan tic tac toe, algoritma Minimax ini memerlukan waktu yang sangat lama untuk membangun pohon penyelesaian.
Jurnal ini akan mencoba menjelaskan sebuah konsep algoritma minimax dan pembelajaran mesin yang diterapkan pada permainan tic-tac-toe. Setelah pembelajaran dari strategi-strategi untuk sebuah permainan didapat, algoritma minimax diharapkan mampu membantu pemain memainkan tic-tac-toe dengan baik. Hasil dari proses ini diharapkan dapat dibandingkan dengan beberapa metode-metode yang lain dalam lingkup kecerdasan buatan.
Kata kunci: Algoritma Minimax, Pembelajaran Mesin, Permainan, Tic-Tac-Toe.



1. PENDAHULUAN

Memainkan sebuah permainan merupakan sebuah konsep penelitian yang sangat populer dikalangan komunitas AI (kecerdasan buatan). Para peneliti di bidang itu telah mengembangkanbeberapa metode pencarian untuk permainan. Metode-metode pencarian yang dikembangkan bias berupa pencarian secara tradisional maupun secara heuristic yang lebih cerdas. Penelitian ini akan mencoba memfokuskan pada permainan sederhana yang dinamakan Tic-Tac-Toe. Algoritma genetika mempunyai ciri yaitu mampu membangun beberapa strategi pada berbagai situasi ,dan melalui aturan ’kemampuan bertahan hidup’, beberapa strategi yang tidak baik dapat dieliminasi sehingga hanya strategi baik yang dipakai.



Kekuatan komputer yang mengandalkan proses
komputasi yang sangat cepat harus didukung oleh
algoritma yang memiliki efisiensi dan efektifitas yang
tinggi. Untuk menyelesaikan permasalahan ini, permainan
tic tac toe pada komputer menggunakan optimasi dari
algoritma Minimax untuk memberikan hasil terbaik dalam
waktu yang singkat.

2. ALGORITMA MINIMAX

2.1 Dasar Teori
Secara teori, algoritma Minimax didefinisikan sebagai berikut:



“Untuk setiap permainan satu-lawan satu, ada
sebuah nilai yang bernilai V dan strategi yang dipilih oleh tiap pemain, sehingga: (a), Jika diberikan strategi dari pemain ke-2, maka langkah penyelesaian terbaik dari
pemain pertama adalah V. Dan (b), jika diberikan strategi dari pemain pertama, maka langkah penyelesaian terbaik


dari pemain kedua adalah -V” [6]

Singkatnya, pemain pertama memberikan langkah
penyelesaian yang bernilai V terhadap permainan pemain

kedua, dan sebaliknya, pemain kedua memberikan
langkah peyelesaian bernilai -V. Pemikiran inilah yang mendasari asal usul penamaan algoritma Minimax,
dimana pemain yang satu berjuang untuk mendapat nilai
maksimum,sedangkan lawannya berjuang untuk mendapat nilai minimum.














Gambar 1. Gambar pohon yang dibangun dengan algoritma Minimax. Disini MAX diwakili aras genap,
sedangkan MIN diwakili aras ganjil.
Langkah-langkah membuat algoritma Minimax adalah sebagai berikut:
1. Misalkan ada 2 pemain yang terlibat, kita namakan
MAX dan MIN.
2. Lalu sebuah pohon pencarian dibangkitkan secara
depth-first-search dari posisi awal permainan hingga
akhir permainan.
3. Dari sudut pandang MAX, akan dicari posisi terakhir
yang paling menguntungkan bagi MAX.

Algoritma Minimax adalah sebagai berikut:

MinMax (GamePosition game) {
return MaxMove (game);
}
MaxMove (GamePosition game) {
if (GameEnded(game)) {
return EvalGameState(game);
}
else {
best_move < - {};
moves <- GenerateMoves(game);
ForEach moves {
move <-
MinMove(ApplyMove(game));
if (Value(move) >
Value(best_move)) {
best_move < - move;
}
}
return best_move;
}
}










MinMove (GamePosition game) {
best_move <- {};
moves <- GenerateMoves(game);
ForEach moves {
move <-
MaxMove(ApplyMove(game));
if (Value(move) >
Value(best_move)) {
best_move < - move;
}
}
return best_move;

Yang terjadi pada algoritma diatas adalah, MAX akan mengambil nilai maksimum dari pohon pencarian yang dibangkitkan pada simpul terakhir. Sebaliknya, MIN akan menangkis serangan MAX dengan mengambil nilai
minimum pada posisi akhir permainan, yang akan
meminimalisasi serangan MAX.


2.2 Implementasi Algoritma Minimax
Untuk lebih jelasnya, kita misalkan ada sebuah
permainan sederhana yang dengan hanya ada satu langkah untuk tiap pemain dengan kemungkinan situasi seperti ini:

Pergerakan Pergerakan Nilai
MAX MIN Evaluasi
A C 12
A D -2
B C 5
B D 6

Tabel 1. Contoh nilai akhir pergerakan MAX dan MIN
pada pohon Minimax.
Fungsi evaluasi berlaku untuk posisi akhir papan, yang berupa kombinasi langkah dari MIN dan MAX.

MAX berasumsi jika MIN akan bermain dengan baik.
Maka dari itu, MAX tahu jika dia melakukan pergerakan
A, maka MIN akan membalasnya dengan melakukan
pergerakan D, yang mengakibatkan nilai evaluasi -2
(kemenangan bagi MIN). Bagaimanapun juga, jika MAX melakukan gerakan B, dia pasti akan menang karena
pergerakan MIN yang terbaik hanya akan menghasilkan nilai evaluasi terbaik sebesar 5 saja. Jadi, dengan
menggunakan algoritma Minimax, MAX akan selalu
memilih untuk melakukan langkah B, walaupun dia
sebenarnya akan mendapatkan kemenangan yang lebih baik jika melakukan A dan MIN melakukan kesalahan dengan memilih langkah C.




2.3 Kelemahan Algoritma Minimax
Dengan membangkitkan pohon pencarian ini, komputer akan selalu mendapatkan penyelesaian terbaik untuk `
setiap langkahnya. Tetapi, masalah muncul ketika jumlah
input yang dimasukkan menjadi banyak. Bayangkan saja, untuk posisi pertama dalam permainan tic tac toe dimana
hanya terdapat kemungkinan untuk bergerak bagi 8 pion
dan 2 kuda, akan terdapat sebanyak 8*2 + 2*2 = 20
kemungkinan. Hal ini berarti pada simpul awal akan
didapatkan 20 sub-simpul sebagai langkah penyelesaian
pada aras (level) ke 1. Jika komputer melakukan hal yang sama untuk menganalisis langkah selanjutnya (berarti komputer melakukan pembangkitan pohon untuk simpul pada aras ke 1) maka akan dilakukan 20 pembangkitan dimana pada tiap pembangkita akan dilakukan puluhan pembangkitan lain untuk aras ke 2. Demikian seterusnya hingga algoritma mencapai aras terakhir permainan, menang

Berarti, usaha yang dilakukan akan tumbuh secara
dramatis mengikuti:
 Jumlah kemungkinan posisi penyelesaian untuk
setiap pemain, dinamakan branching factor.
Sering dinotasikan sebagai B.
 Kedalaman aras pada pembangunan pohon
pencarian, sering dinotasikan sebagai d. Biasa
disebut juga 'ply', yang berarti sebuah langkah
yang dilakukan oleh pemain.

Jika komputer hanya mengandalkan algoritma Minimax ini, proses membangkitkan simpul akan menjadi sangat lama. Kompleksitas dari algoritma Minimax ini adalah
eksponensial sebesar O(Bd) [5]. Dengan nilai B untuk
catur rata-rata adalah 35, dan jika kita akan menentukan 9 langkah kedepan, diperlukan sekitar 50 juta kemungkinan
untuk dieksplorasi. Hal ini tentunya membutuhkan usaha yang sangat keras untuk mengecek seluruh kemungkinan. Tentu saja diperlukan waktu yang lama untuk menganalisis seluruh kemungkinan ini dalam sebuah permainan tic tac toe jika hanya mengandalkan algoritma Minimax.
3. The Game Tic Tac Toe

Permainan Tic-Tac-Toe sangatlah sederhana; diilhami oleh permainan anak-anak. Dimainkan pada papan berukuran 3 x 3. Pada awal permainan, papan dikosongkan. Kedua pemain, X dan O, akan
menempatkan biji-bijinya keatas papan, sekali
pasang satu biji. Pemain yang mampu menempatkan tiga bijinya dalam satu garis (vertikal, horizontal, diagonal) itulah yang menang. Dan dikatakan seri

0
X


Gambar 1. contoh konfigurasi











4. IMPLEMENTASI
4.1 Konfigurasi Pengkodean
Untuk membangun strategi dalam permainan
Tic-tac-toe, ada sebuah langkah jitu di tiap konfigurasi papan. Tic-tac-toe dimainkan pada papan dengan sembilan kotak. Tiap kotak dapat terisi oleh ‘X’ atau ‘O’ maupun kosong. Total jumlah kemungkinan konfigurasi adalah 3 pangkat 9 Jika diasumsikan bahwa akan dibentuk sebuah susunan angka bayangan, maka ‘0’ akan merepresentasikan kosong, 1 untuk ‘X’ dan 2 untuk ‘O’. Misalnya:
Algoritma MTD(f) adalah sebuah algoritma optimasi Minimax baru yang lebih sederhana dan lebih sangkil
daripada beberapa pendahulunya[4]. Nama dari algoritma ini adalah kependekan dari MTD(n,f), yang disingkat dari Memory-enhanced Test Driver with node n and value f. MTD adalah nama dari sekumpulan driver program yang mencari pohon Minimax menggunakan pemanggilan zerowindow AlphaBetaWithMemory.

Dalam beberapa percobaan permainan komputer seperti
tic tac toe, catur, othello, dan checkers, algoritma ini mempunyai performa rata-rata lebih baik daripada Negascout (variasi dari Alphabeta yang diimplementasikan dalam hampir
semua permainan catur, checkers, dan othello). Salah satu
program tic tac toe terkuat, Cilkchess (http://theory.lcs.mit.
edu/~cilk/chess.html) milik MIT yang menggunakan
metode komputasi pararel, juga menggunakan MTD(f)
sebagai algoritma pencariannya menggantikan Negascout
yang digunakan oleh program tic tac toe pendahulunya,
StarSocrates.


4.2 Implementasi Algoritma MTD(f)
MTD(f) 'hanya' terdiri dari 10 baris kode saja, yaitu
seperti berikut:
function MTDF(root, f, d)
g := f
upperBound := +•
lowerBound := -•
while lowerBound < upperBound
if g = lowerBound then
• := g+1
else
• := g
g :=
AlphaBetaWithMemory(root, •-1, •, d)
if g < • then
upperBound := g
else
lowerBound := g
return g
Algoritma MTD(f) diatas memanggil fungsi
AlphaBetaWithMemory berkali-kali dengan metode zerowindow pencarian Alpha-beta, tidak seperti Negascout yang menggunakan pencarian wide-window. Pemanggilan AlphaBetaWithMemory mengembalikan batas dari nilai evaluasi Minimax. Batas dari nilai itu kemudian disimpan dalam upperbound (batas atas) dan lowerbound (batas bawah), membentuk sebuah interval yang melingkupi nilai Minimax yang sebenarnya pada pencarian dengan









kedalaman tertentu. Positif dan negatif tak hingga adalah
kependekan dari nilai diluar interval pada daun pohon. Ketika batas atas dan batas bawahnya bernilai sama atau batas bawah telah melampaui nilai batas atas, maka nilai
Minimax telah ditemukan.
Efisiensi dari MTD(f) berasal dari pencarian Alpha-beta dengan zero-window, dan menggunakan sebuah nilai batas yang baik (variabel beta) untuk melakukan pencarian
zero-window tersebut. Dalam versi yang sebelumnya,
Alpha-beta dipanggil dengan pencarian wide-window
seperti ini AlphaBeta(root, -INFINITY, +INFINITY,
depth), yang memastikan nilai kembaliannya berada
dalam interval alpha dan beta. Sedangkan dalam
algoritma MTD(f), digunakan pencarian zero-window, jadi
untuk setiap pemanggilan Alpha-beta akan
mengembalikan batas bawah dan batas atas dari nilai
Minimax berturut-turut. Pencarian dengan zero-window memberikan lebih banyak jalan pintas, tetapi lebih sedikit
informasi -hanya batas dari nilai minimax saja. Untuk
menyiasati hal itu MTD(f) perlu memanggil Alpha-beta beberapa kali, untuk mendekati nilai itu. Imbas dari
pemanggilan Alpha-beta secara berulang-ulang dapat
dihilangkan dengan menggunakan versi dari Alpha-beta yang menyimpan nilai simpul dalam memori.
Agar algoritma MTD(f) dapat berjalan dengan baik,
maka diperlukan “tebakan pertama” sebagai pengarah untuk menemukan nilai Minimax yang baik. Semakin baik
tebakan pertama, maka algoritma tersebut akan semakin efisien, dan diperlukan lebih sedikit pengulangan. Jika kita memberikan tebakan nilai Minimax pada MTD(f), dia
hanya akan melakukan dua pengulangan, yang satu untuk menentukan batas atas dari nilai x, dan yang satunya lagi untuk menemukan batas bawah dari nilai tersebut.


4.3 Algoritma AlphaBetaWithMemory
Sebagai catatan, MTD(f) memanggil fungsi Alpha-Beta yang menyimpan nilai simpul-simpulnya dalam memori, dan mengembalikan nilainya untuk pencarian kembali.
Untuk membuat MTD(f) sangkil, maka fungsi Alpha-beta harus menyimpan nilai simpul yang telah dicari.

Berikut ini adalah kode dari AlphaBetaWithMemory:
function AlphaBetaWithMemory(n :
node_type; alpha , beta , d : integer) : integer;
if retrieve(n) == OK then /*
Melihat tabel transposisi */
if n.lowerbound >= beta
then return n.lowerbound;
if n.upperbound <= alpha
then return n.upperbound;















alpha := max(alpha,
n.lowerbound);
beta := min(beta,
n.upperbound);
if d == 0 then g :=
evaluate(n); /* simpul daun */
else if n == MAXNODE then
g := -INFINITY; a :=
alpha; /* menimpan nilai
alpha yang sebenarnya */
c := firstchild(n);
while (g < beta) and (c
!= NOCHILD) do
g := max(g,
AlphaBetaWithMemory
(c, a, beta, d -
1));
a := max(a, g);
c :=
nextbrother(c);
else /* n adalah sebuah
MINNODE */
g := +INFINITY; b :=
beta; /* save original
beta value */
c := firstchild(n);
while (g > alpha) and (c
!= NOCHILD) do
g := min(g,
AlphaBetaWithMemory
(c, alpha, b, d -
1));
b := min(b, g);
c :=
nextbrother(c);
/* Tabel transposisi menyimpan
nilai simpul */
if g <= alpha then n.upperbound
:= g; store n.upperbound;
if g > alpha and g < beta then
n.lowerbound := g;
n.upperbound := g; store
n.lowerbound,
n.upperbound;

if g >= beta then n.lowerbound := g;
store n.lowerbound;
return g;



Tabel transposisi yang digunakan berguna untuk
menyimpan dan mengambil panggilan. Retrieve
berfungsi untuk memastikan jika sebuah nilai terdapat






5. KESIMPULAN

Untuk setiap permainan satu-lawan-satu, hampir selalu digunakan algoritma Minimax dalam permainan komputer. Proses pembangunan pohon pencarian Minimax dilakukan dengan metode depth-first-search. Algoritma Minimax mampu menganalisis segala kemungkinan posisi permainan untuk menghasilkan keputusan yang terbaik. Tetapi, dengan kelebihan yang seperti ini, algoritma Minimax tidak sangkil untuk memroses data dengan ukuran masukan yang besar, karena proses untuk membangun pohon pencarian dangan algoritma ini memiliki kompleksitas algoritma eksponensial. Maka dari itu, diperlukan optimasi dalam algoritma ini agar tidak semua simpul dibangkitkan.
Jenis optimasi dalam permainan TIC TAC TOE dengan algoritma Minimax ada bermacam-macam, tetapi dalam makalah ini hanya dibahas mengenai optimasi MTD(f) karena algoritma MTD(f) diklaim sebagai algoritma terbaik dibandingkan dengan algoritma-algoritma pendahulunya. Dengan menggunakan algoritma MTD(f) ini, proses pencarian nilai Minimax berlangsung lebih cepat.

Kekuatan dalam permainan tic tac toe pada manusia terletak dari strategi dalam merencanakan langkah, pemikiran jauh kedepan, intuisi, dan kreatifitas. Sedangkan komputer hanya mengandalkan kemampuan komputasi yang sangat cepat.
Kekuatan komputer yang mengandalkan proses komputasi yang sangat cepat harus didukung oleh algoritma yang memiliki efisiensi dan efektifitas yang tinggi. Untuk menyelesaikan permasalahan ini, permainan tic tac toe pada komputer menggunakan optimasi dari algoritma Minimax untuk memberikan hasil terbaik dalam waktu yang singkat.

“Untuk setiap permainan satu-lawan satu, ada
sebuah nilai yang bernilai V dan strategi yang dipilih oleh tiap pemain, sehingga: (a), Jika diberikan strategi dari pemain ke-2, maka langkah penyelesaian terbaik dari
pemain pertama adalah V. Dan (b), jika diberikan strategi dari pemain pertama, maka langkah penyelesaian terbaik dari pemain kedua adalah -V” [6]


















REFERENCES

ALI, A.M.A. 1998. Segmentation and Categorization of Phonemes in Continuous Speech. Technical Report TR-CST25JUL98, Center for Sensor Technology, University of Pennsylvania.
Abdul Gapur, “Aplikasi Struktur Data The Minimax Game
Tree pada Permainan Catur”, Teknik Informatika ITB, 2007
Khoirush Sholih Ridhwaana Akbar, “Algoritma Minimax
dalam Pengambilan Keputusan pada Permainan Tic-tac
toe”, Teknik Informatika ITB, 2007.
ALI, A.M.A., VANDER SPIEGEL, J., MUELLER, P., HAENTJENS, G., AND BERMAN, J. 1999. An Acoustic-Phonetic feature based system for Automatic Phoneme Recognition in Continuous Speech. In IEEE Proceedings of the International Symposium on Circuits and Systems (ISCAS), 3, 118-121.
Bagley, J.D. (1967). The behaviour of adaptive
systems which employ genetic and correlation
algorithms. Doctoral dissertation, Ann arbor:
The University of Michigan.
ANANDAN, P., SARAVANAN, K., PARTASARATHI, R., AND GEETHA, T.V. 2002. Morphological Analyzer for Tamil. In Proceedings of ICON2002, 3-10.
ARDEN, A.H. REV. AND CLAYTON, A. C. 1969. A Progressive Grammar of the Tamil Language, Christian Literature Society, Madras.
BROWN, P., PIETRA, S,.DELLA PIETRA, V., AND MERCER, R. 1993. The mathematics of statistical machine translation: Parameter estimation’, Computational Linguistics, 19(2), 263-311.
BYRNE, W., HACIC, J., IIRCING, P., JELINEK, F., KHUDANPUR, S., KRBEC,.P., AND PSUTKA, J. 2001. On large vocabulary continuous speech recognition of highly inflectional language – Czech. In Proceedings of Eurospeech 2001, Aalborg, Denmark, 487-489.
Minimax - Wikipedia, The Free Encyclopedia
en.wikipedia.org/wiki/Minimax
diakses pada tanggal 15 Mei 2008