|
|
Metode dan Algoritma | IMPLEMENTASI ALGORITMA NEGASCOUT . Anda bisa melakukan konsultasi tentang IMPLEMENTASI ALGORITMA NEGASCOUT melalui form di samping kanan !!!
Negascout
Pengerian Algoritma Negascout
Algoritma Game / Permainan
Algoritma Negascout Pada Game
Ketika bermain othello, demikian juga permainan-permainan lain seperti catur, shogi, igo dll., user manusia berpikir dengan menggabungkan intuisi yg menggunakan perasaan & perhitungan yg menggunakan otak.
Pada sebuah posisi papan othello tertentu, mula-mula intuisi user akan segera mengenali pola susunan keping di saat itu, ini merupakan kemampuan pattern recognition yg inheren dimiliki oleh setiap manusia. Beberapa langkah yg jelas-jelas buruk atau ‘dianggap’ buruk segera bisa dikenali & dihilangkan dari daftar langkah yg mungkin dilakukan (disebut possible moves, legal moves atau valid moves).
Setelah itu barulah user menghitung langkah-langkah sisanya yg ‘terlihat’ baik, dengan melakukan simulasi permainan di dalam kepala user untuk setiap langkah, kemudian membandingkan untung-ruginya untuk menentukan langkah terbaik.
Contoh Khasus Dalam Permainan
Misalnya di dalam sebuah posisi papan, terdapat 10 valid moves. Mula-mula intuisi user akan menghapus 3 langkah yg jelas-jelas buruk, lalu 2 langkah lagi yg ‘kelihatannya’ buruk, dari daftar valid moves. Dengan demikian, hanya tinggal tersisa 5 langkah yg perlu diperhitungkan. Di sini, barulah user melakukan simulasi permainan, ketika langkah 1 dilakukan maka lawan akan menjawab dengan langkah 1-1, 1-2, 1-3, … Kalau user melangkah dengan langkah 2 maka lawan akan menjawab dengan langkah 2-1, 2-2, 2-3, … dst, sampai beberapa langkah ke depan (kedalaman tertentu) tergantung daya ingat kita.
Peran Penting Intuisi Manusia
Di sinipun intuisi manusia selalu berperan penting dalam mengenali pola-pola yg muncul di setiap kedalaman simulasi permainan untuk menghilangkan langkah-langkah yg ‘dianggap’ buruk dari perhitungan. Sehingga user manusia bisa memilih hanya satu atau dua langkah tertentu saja yg ‘dianggap’ baik untuk ditelusuri sampai kedalaman cukup jauh, sementara langkah-langkah lain yg ‘dianggap’ tidak menjanjikan hanya diperhitungkan seperlunya saja. Dari hasil simulasi ini, user membandingkan untung-rugi setiap langkah yg disimulasikan, & menentukan langkah mana yg terbaik.
Komputer berpikir hanya dengan perhitungan
Nah.. di sisi lain, berbeda dengan manusia, komputer tidak mempunyai intuisi yg menggunakan perasaan. Sebagai gantinya, komputer mempunyai daya perhitungan yg jauh lebih penting daripada manusia. Ketika diberikan sebuah posisi papan othello tertentu, sama seperti manusia komputer juga melakukan perhitungan simulasi permainan untuk valid moves yg tersedia. Tetapi berbeda dengan manusia, dia tidak mempunyai intuisi untuk mengenali langkah-langkah yg jelas-jelas buruk lalu menghilangkannya dari daftar perhitungan. Sehingga komputer harus memperhitungkan semua valid moves, di sinilah daya perhitungan yg penting sangat diperlukan.
Pada dasarnya ketika diberikan sebuah susunan posisi papan tertentu, komputer menghitung nilai posisi tersebut menggunakan fitur-fitur yg dijelaskan pada artikel Strategi bermain othello, seperti jumlah keping, penguasaan sudut/x-quare/c-square, jumlah keping stabil, mobility, jumlah keping tepi, parity, & pola sisi/sudut. Di setiap posisi papan yg sedang dipertimbangkan, mula-mula komputer menghitung nilai dari setiap fitur. Misalnya ketika dilakukan simulasi langkah 1, maka jumlah keping (discs) terdapat 30, sudut yg dikuasai (corners) terdapat 2, jumlah keping stabil (stables) terdapat 5, mobility terdapat 15, jumlah keping tepi (frontiers) terdapat 10, parity yg dimenangkan terdapat 3, & nilai pola sisi/sudut (pattern) merupakan 20.
Selanjutnya nilai dari masing-masing fitur ini digabungkan secara linier dengan bobot-bobot tertentu yg dianggap tepat. Misalnya nilai total dari posisi papan ini adalah:
score = w_d * discs + w_c * corners + w_s * stables + w_m * mobility + w_f * frontiers + w_p * parity + w_t * pattern
= -3 * 30 + 5 * 2 + 9 * 5 + 7 * 15 – 5 * 10 + 8 * 3 + 6 * 20
= 164
Dengan asumsi bahwa bobot-bobot untuk setiap fitur yg dianggap tepat adalah:
w_d = -3 (bobot untuk discs)
w_c = 5 (bobot untuk corners)
w_s = 9 (bobot untuk stables)
w_m = 7 (bobot untuk mobility)
w_f = -5 (bobot untuk frontiers)
w_p = 8 (bobot untuk parity)
w_t = 6 (bobot untuk pattern)
Ini merupakan nilai papan untuk simulasi langkah 1. Berikutnya dilakukan simulasi untuk langkah 2, dihitung lagi berapa nilainya, langkah 3 berapa nilainya.. dst. & ini baru berpikir sampai kedalaman satu, disebut juga 1-ply dalam istilah kecerdasan buatan untuk permainan komputer. Untuk berpikir sampai kedalaman 2, maka di setiap posisi papan (hasil simulasi kedalaman 1) belum dihitung dulu nilainya, tetapi harus dilakukan lagi simulasi kedalaman 2 untuk setiap langkah di posisi tersebut, baru kemudian dilakukan perhitungan di atas.
Jadi kalau di kedalaman 1 terdapat 3 valid moves, yg membawa ke 3 posisi papan berbeda, & di setiap posisi papan rata-rata terdapat 3 valid moves yg dimiliki lawan kita, maka untuk berpikir sampai kedalaman 2 user perlu memperhitungkan sebanyak 3 x 3 = 9 posisi papan. Tetapi rata-rata jumlah valid moves pada othello diperkirakan sekitar 8, sehingga ‘berpikir’ sampai kedalaman 2 perlu menghitung 8^2 = 64 posisi, kedalaman 3 perlu 8^3 = 512 posisi.. & kedalaman 10 perlu menghitung lebih dari 1 milyar posisi!
ALGORITMA MINIMAX
Untuk melakukan perhitungan simulasi permainan inilah, digunakan algoritma standar di dalam bidang kecerdasan buatan (artificial intelligence, AI) yg telah dikembangkan sejak lama, yaitu Game Theory, terutama algoritma yg disebut Minimax. Sesuai namanya, algoritma minimax merupakan aturan untuk permainan zero-sum 2 pemain, yg berusaha meminimalkan kemungkinan kalah sambil memaksimalkan kemungkinan menang untuk pemain yg akan melangkah.
Di kedalaman 1 (dan kedalaman ganjil lainya), posisi papan akan menentukan nilai untuk pemain yg akan melangkah saat ini (current player), sehingga di kedalaman ganjil ini algoritma minimax memilih langkah bernilai maksimal sebagai langkah terbaik. Sebaliknya di kedalaman 2 (dan kedalaman genap lainnya), posisi papan akan menentukan nilai untuk pemain lawan yg akan melangkah berikutnya (opponent player), sehingga di kedalaman genap ini algoritma minimax memilih langkah bernilai minimal sebagai langkah terbaik.
Sebagai ilustrasi sampai kedalaman dua bisa digambarkan dengan tabel berikut:
B memilih B1 | B memilih B2 | B memilih B3 | |
A memilih A1 | +3 | −2 | +2 |
A memilih A2 | −1 | 0 | +4 |
A memilih A3 | −4 | −3 | +1 |
Ketika A memilih langkah A1 dilanjutkan dengan B memilih langkah B1, posisi papan yg terbentuk bernilai +3. Demikian pula untuk A1 → B2 nilainya -2, A1 → B3 nilainya +2 dst. Sekarang mari user coba aplikasikan algoritma minimax untuk menghitung langkah terbaik bagi pemain A.
Terhadap langkah A1 (kedalaman 1) misalnya valid moves pemain B merupakan B1, B2 & B3 (kedalaman 2), & langkah terbaik menurut algoritma minimax didapat dengan mencari langkah bernilai minimal (karena di kedalaman 2), yaitu B2 (bernilai -2). Demikian pula terhadap langkah A2 yg terbaik bagi B merupakan B1 (bernilai -1), & terhadap A3 merupakan B1 juga (bernilai -4). Selanjutnya, nilai untuk langkah pemain A (kedalaman 1) merupakan nilai yg ‘dikembalikan’ dari pemain B di kedalaman 2, yaitu A1 merupakan -2, A2 merupakan -1, & A3 merupakan -4. Kemudian untuk kedalaman 1 ini algoritma minimax mencari nilai maksimal sebagai langkah terbaik, yaitu A2 (bernilai -1).
Untuk kedalaman lebih dari dua, cara ‘berpikir’ algoritma minimax bisa digambarkan sebagai pohon permainan (game tree) seperti pada gambar di atas. Di lokasi paling dalam (disebut lokasi node daun atau leaf node), dalam hal ini kedalaman 4, dilakukanlah perhitungan nilai posisi papan yg selanjutnya ‘dikembalikan’ ke node pada kedalaman di atasnya terus hingga sampai lokasi paling atas (di sebut akar atau root). Panah merah menunjukkan nilai yg dikembalikan dari langkah terbaik pilihan algoritma minimax ke kedalaman di atasnya. Demikianlah, user bisa melihat algoritma minimax bergantian memilih langkah dengan nilai minimal & maksimal sebagai langkah terbaik sesuai dengan kedalamannya. Dengan algoritma ini komputer bisa ‘berpikir’ sampai kedalaman tertentu untuk menentukan langkah terbaik untuk memenangkan permainan.
Tetapi pada prakteknya, algoritma minimax kini tidak pernah digunakan lagi, karena algoritma ini harus memperhitungkan semua valid moves, sehingga memerlukan waktu yg sangat lama. Sebagai gantinya telah dikembangkan beberapa improvisasi dari minimax seperti algoritma AlphaBeta, NegaScout dll. yg bisa melakukan pemangkasan game tree supaya tidak perlu memperhitungkan semua valid moves, sehingga bisa ‘berpikir’ dalam waktu jauh lebih cepat.
Contoh Kode Algoritma Negascout : Pseudo C Code
Contoh Kode Algoritma Negascout : Pseudo C
int NegaScout ( position p; int alpha, beta ){ /* compute minimax value of position p */ int a, b, t, i; if ( d == maxdepth ) return Evaluate(p); /* leaf node */ determine successors p_1,...,p_w of p; a = alpha; b = beta; for ( i = 1; i a) && (t 1) && (d = beta ) return a; /* cut-off */ b = a + 1; /* set new null window */ } return a;}
Alternatif Contoh Kode Negascout
int NegaScout ( position p; int alpha, beta ){ /* compute minimax value of position p */ int b, t, i; if ( d == maxdepth ) return quiesce(p, alpha, beta); /* leaf node */ determine successors p_1,...,p_w of p; b = beta; for ( i = 1; i a) && (t 1) ) t = -NegaScout ( p_i, -beta, -alpha ); /* re-search */ alpha = max( alpha, t ); if ( alpha >= beta ) return alpha; /* cut-off */ b = alpha + 1; /* set new null window */ } return alpha;}
Contoh Program Algoritma Negascout Dalam permainan Catur
// NegaScout.cpp: implementation of the CNegaScout class.////////////////////////////////////////////////////////////////////////
#include "stdafx.h"#include "chess.h"#include "NegaScout.h"
#ifdef _DEBUG#undef THIS_FILEstatic char THIS_FILE[]=__FILE__;#define new DEBUG_NEW#endif
//////////////////////////////////////////////////////////////////////// Construction/Destruction//////////////////////////////////////////////////////////////////////
CNegaScout::CNegaScout(){
}
CNegaScout::~CNegaScout(){
}
CNegaScout::SearchAGoodMove(BYTE position[10][9]){ memcpy(CurPosition, position, 90); m_nMaxDepth = m_nSearchDepth; CalculateInitHashKey(CurPosition); ResetHistoryTable();
NegaScout(m_nMaxDepth, -20000, 20000); MakeMove(&m_cmBestMove); memcpy(position, CurPosition, 90);}
int CNegaScout::NegaScout(int depth, int alpha, int beta){ int Count,i; BYTE type; int a,b,t; int side; int score;
i = IsGameOver(CurPosition, depth); if (i != 0) return i;
side = (m_nMaxDepth-depth)%2;
score = LookUpHashTable(alpha, beta, depth, side); if (score != 66666) return score;
if (depth Eveluate(CurPosition, side ); EnterHashTable(exact, score, depth, side ); return score; }
Count = m_pMG->CreatePossibleMove(C
... ... ... to be continued.
Download sourcecode lengkapnya disini
IMPLEMENTASI ALGORITMA NEGASCOUT
ActionScript AS3 ASP.NET AJAX C / C++ C# Clipper COBOL ColdFusion DataFlex Delphi Emacs Lisp Fortran FoxPro Java J2ME JavaScript JScript Lingo MATLAB Perl PHP PostScript Python SQL VBScript Visual Basic 6.0 Visual Basic .NET Flash MySQL Oracle Android
Rating: 100% based on 99998 ratings. 5 user reviews.
Ditulis Oleh hank2
{ 0 komentar... Views All / Send Comment! }
Posting Komentar