14 August 2014

PENERAPAN ALGORITMA GENETIKA DAN GREEDY UNTUK MENENTUKAN LANGKAH TERBAIK MELALUI POHON PENCARIAN PADA PERMAINAN BACKGAMMON


PENERAPAN ALGORITMA GENETIKA DAN GREEDY UNTUK MENENTUKAN LANGKAH TERBAIK MELALUI POHON PENCARIAN PADA PERMAINAN BACKGAMMON
Yulius Susilo#1, The Houw Liong*2, Ken Ratri Retno Wardhani#3 #Faculty of Informatics Engineering, Institut Teknologi Harapan Bangsa Bandung, Indonesia 1susilo.yulius@yahoo.com 2thel007@gmail.com 3ratri.ken@gmail.com *Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung Bandung, Indonesia
Abstrak —Permainan backgammon merupakan salah satu permainan tertua yang menggunakan papan dan dimainkan oleh 2 orang. Permainan backgammon berguna untuk melatih taktik, strategi, berhitung, dan menghitung peluang yang terjadi dalam permainan. Algoritma genetika merupakan bentuk model dari matematika dengan cara melakukan suatu simulasi dengan membuat evolusi untuk menyelesaikan berbagai permasalahan optimasi dengan beragam variasi. Pada penelitian menggunakan algoritma genetika dan greedy untuk menentukan langkah terbaik yang dioptimasi dengan pohon pencarian .Algoritma greedy adalah algoritma yang memecahkan masalah langkah demi langkah.Pohon pencarian digunakan untuk menganalisis langkah – langkah lawan dan langkah selanjutnya yang menguntungkan. Berdasarkan penelitian terhadap algortima genetika, algoritma greedy, dan pohon pencarian menunjukkan bahwa tiga metode yang dikombinasikan dapat menghasilkan langkah yang terbaik untuk permainan backgammon dengan tingkat kecerdasan hingga mencapai 70% kemenangan.
Kata kunci —backgammon, algoritma genetika, algoritma greedy, pohon pencarian.
Abstract —Game of backgammon is one of the oldest game that uses a board and is played by 2 players. It is useful to train the backgammon tactics, strategy, counting, and calculating the odds that happens in the game. Genetic algorithm is a form of mathematical models that performs a simulation by making an evolution to solve the optimization problems with different variations. In studies using genetic and greedy algorithm to determine the best steps that are optimized to the search tree. Greedy algorithm is an algorithm that solves the problem step by step and make the best move. Tree is used to analyze the measures of the opponent and other profitable step. Based on the study of genetic algorithms, greedy algorithms, and trees shows that the combination of the three methods can produce the best step for backgammon game with a level of intelligence to achieve a 70% victory.
Keywords—backgammon, genetic algorithm, greedy algorithm, tree.