Pengambilan keputusan pada board game

Posted by : tessarishak Senin, 25 Juni 2018

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