Tugas
Konsep Board Game
Board game atau permainan papan, secara arti juga sudah dengan mudah untuk dimengerti, yaitu permainan yang dimainkan diatas papan atau diatas alas tertentu yang sudah dirancang sedemikian rupa sesuai dengan aturan permainannya. Board game biasanya ditujukan untuk permainan bersama keluarga dengan peraturan yang mudah sehingga mendapatkan kesan seru yang semakin mempererat tali kekeluargaan. Namun ada beberapa game yang membutuhkan keseriusan pada rancangan board game, seperti catur dan othello.
Algoritma Min Max
Algoritma minmax atau minimax adalah sebuah
algoritma yang digunakan pada permainan dengan dua
pemain dengan cara memprediksi keadaan masa depan,
dan kemudian mengambil langkah yang memaksimalkan
peluang kemenangan. Teori di balik minimax adalah
bahwa algoritma lawan akan mencoba untuk
meminimalkan nilai apapun yang algoritma pemain
berusaha maksimalkan. Dengan konsep seperti itu, maka
algoritma ini akan melakukan gerakan yang membuat
lawannya memiliki peluang lebih kecil untuk menang.
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
MAKALAH IF2251 STRATEGI ALGORITMIK TAHUN 2008
dalam tabel, maka nilai itu akan langsung digunakan,
bukan dilanjutkan dengan mencarinya. Store berfungsi
untuk menyimpan nilai yang ada. Dalam algoritma ini,
kita juga akan menyimpan nilai langkah terbaik kedalam
tabel transposisi.
Hashing
Hashing adalah transformasi aritmatik sebuah string dari karakter menjadi nilai yang merepresentasikan string aslinya. Menurut bahasanya, hashberarti memenggal dan kemudian menggabungkan. Hashing digunakan sebagai metode untuk menyimpan data dalam sebuah array agar penyimpanan data, pencarian data, penambahan data, dan penghapusan data dapat dilakukan dengan cepat. Ide dasarnya adalah menghitung posisi recordyang dicari dalam array, bukan membandingkan record dengan isi pada array. Fungsi yang mengembalikan nilai atau kunci disebut fungsi hash (hashfunction) dan array yang digunakan disebut tabel hash (hash table). Hash tablemenggunakan struktur data array asosiatif yang mengasosiasikan recorddengan sebuah field kunci unik berupa bilangan (hash) yang merupakan representasi dari record tersebut.
Zobrist Hashing
Zobrist hashing (juga disebut sebagai kunci Zobrist atau tanda tangan Zobrist [1]) adalah konstruksi fungsi hash yang digunakan dalam program komputer yang memainkan permainan papan abstrak, seperti catur dan Go, untuk menerapkan tabel transposisi, jenis khusus dari tabel hash yang diindeks oleh posisi papan dan digunakan untuk menghindari menganalisis posisi yang sama lebih dari satu kali.
Strategi Replacement
Metode replacement
digunakan untuk menghapus data yang ada pada cache yang penuh, untuk digantikan dengan data baru. Banyak
metode replacement yang diteliti sebelumnya. Faktor yg biasa diperhitungkan untuk proses replacement pada
cache:
- recency: waktu terakhir referensi ke objek
- frekuensi: jumlah request ke sebuah objek
- size: ukuran dari objek dalam cache
- cost of fetching the object: perhitungan pengambilan objek langsung dari server asli (seperti jarak
dalam jumlah hop)
- modification time: waktu dimodifikasi terakhir sebuah objek
- expiration time: waktu dimana objek sudah kadaluarsa dan bisa diganti langsung
Sumber :
http://repository.unpas.ac.id/15941/2/bab%202.pdf
http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2016-2017/Makalah2017/Makalah-IF2211-2017-043.pdf
http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2007-2008/Makalah2008/MakalahIF2251-2008-094.pdf
http://syazdiayhodian.blogspot.com/2011/06/hashing.html
https://en.wikipedia.org/wiki/Zobrist_hashing
file:///E:/Pengantar%20Game%20(Soft%20Skill)/Tugas%204/565-770-1-PB.pdf
