IMPLEMENTASI MULTITHREADING PADA ALGORITMA MINIMAX

Abstract

BAHASA

Algoritma minimax merupakan salah satu dari algoritma pencarian yang mencari cabang dengan nilai tertinggi pada suatu pohon pencarian, dimana pohon pencarian adalah pohon yang terbuat dari kemungkinan – kemungkinan yang dapat terjadi. Kekurangan dari algoritma ini adalah semakin besarnya pohon pencarian maka waktu eksekusi yang dibutuhkan dalam melakukan pencarianpun meningkat. Teknik multithreading merupakan suatu teknik yang membagi sebuah tugas besar menjadi beberapa tugas kecil dan dikerjakan secara bersamaan. Teknik multithreading akan diimplementasikan pada algoritma minimax untuk mengurangi waktu eksekusi pencarian cabang dengan nilai tertinggi. Penelitian ini menggunakan bahasa pemrograman java dengan NetBeans IDE 8.0.2. dan komputer personal. Hasil penelitian menunjukkan algoritma minimax dengan implementasi multithreading lebih efisien dibandingkan dengan algoritma minimax dengan Speed Up yang dihasilkan pada multithreading dengan 2 thread adalah 1.31 pada kedalaman maksimal 4, 1.41 pada kedalaman maksimal 5, dan 1.52 pada kedalaman maksimal 6. Sedangkan Speed Up yang dihasilkan pada multithreading dengan 3 thread adalah 1.35 pada kedalaman maksimal 4, 1.42 pada kedalaman maksimal 5, dan 1.55 pada kedalaman maksimal 6. Gradien Speed Up yang dihasilkan dari 2 thread pada kedalaman 4 dan 5 adalah 0.1 dan pada kedalaman 5 dan 6 adalah 0.11. Sedangkan Gradien Speed Up yang dihasilkan dari 3 thread pada kedalaman 4 dan 5 adalah 0.07 dan pada kedalaman 5 dan 6 adalah 0.13.

ENGLISH

Minimax algorithm is one of the searching algorithm that search a branch with the highest value on a searching tree, a searching tree is a tree that made of any possibility that might happen. The lack of this algorithm is that the bigger the tree than the time it consume to search is bigger too. Multithreading technique is a technique that divide a big job into a few small jobs, the few small job will be done at the same time. Multithreading technique will be implemented on minimax algorithm to reduce the execution time to search the branch with the highest value. This research use java programming language with NetBeans IDE 8.0.2. and personal computer. The result of this research is that the minimax algorithm with multithreading implementation is more efficient than minimax algorithm with the resulting Speed Up in multithreading with 2 thread are 1.31 with 4 as the maximum depth, 1.41 with 5 as the maximum depth, and 1.52 with 6 as the maximum depth. Gradien Speed Up for 3 thread toward 2 thread with the maximum depth of 4 and 5 is 0.7, meanwhile with the maximum depth of 5 and 6 is 1.2. On the depth of 4 and 5 the rise of the Speed Up on 2 thread is bigger than 3 thread, meanwhile on the depth of 5 and 6 the rise of the Speed Up on 3 thread is bigger than 2 thread. This thing can be seen by looking at the resulting Gradien Speed Up from 2 thread on the depth of 4 and 5 which is 0.1 and on the depth of 5 and 6 which is 0.11. Meanwhile the resulting Gradien Speed Up from 3 thread on the depth of 4 and 5 is 0.07 and on the depth of 5 and 6 is 0.13.