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
