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
1 susilo.yulius@yahoo.com
2 thel007@gmail.com
3 ratri.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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s