Analisis algoritma minimax optimasi alpha-beta pruning terhadap waktu komputasi pada game congklak

Congklak adalah salah satu permainan tradisional yang bisa dimainkan di komputer dengan single player. Banyak algoritma kecerdasan buatan di aplikasikan pada permainan dalam menentukan solusi atau langkah dan membuat komputer lebih cepat dalam menentukan solusi, seperti Algoritma Minimax dan Alpha-Beta Pruning. Penelitian sebelumnya hanya menggunakan algoritma Minimax, namun memiliki kelemahan karena waktu eksekusi yang dibutuhkan sebanding dengan jumlah leaf-nya.Alpha-Beta Pruning akan mengurangi jumlah node yang dievaluasi oleh pohon pencarian. Algoritma ini akan berhenti mengevaluasi langkah ketika terdapat minimal satu langkah yang lebih buruk dari pada langkah yang dievaluasi sebelumnya, sehingga langkah berikutnya tidak perlu dievaluasi. Analisis dilakukan dengan melihat kompleksitas waktu t(n) dan notasi asimptotik Big Oh(O), serta menggunakan pohon pencarian dengan menggunakan perhitungan heuristik.Dari hasil penelitian dapat disimpulkan bahwa Minimax optimasi Alpha-Beta Pruning terbukti lebih cepat dari pada Minimax tanpa optimasi, akan terlihat dari kompleksitas waktu t(n) yang berbeda dan penelusuran langkah serta waktu dari komputasi komputer dalam mengambil solusi, hal tersebut terbukti dari beberapa pengujian dan dari hasil kompleksitas waktu t(n).

Congklak is one of a traditional games are played on a computer with a single player. Many artificial intelligence algorithms applied in the game to determine a solution or a step and make a computer faster in determining the solution, such as minimax algorithm and alpha-beta pruning algorithm. Earlier research used a minimax algorithm, but it has a weakness because the execution time required is proportional to the number of its leaf.Alpha-beta pruning reduces the number of nodes evaluated by a search tree. This algorithm will stop evaluating measures when there is at least one-step worse than the measures has evaluated before, so the next step does not need to be evaluated. The analysis it has done by looking at the time complexity t (n) and the asymptotic big Oh or notation (O), as well as using the search tree using heuristic calculations.From the research it can be concluded that the optimization minimax alpha-beta pruning proved faster than the minimax without optimization, it will be visible from time complexity t(n) are different and the search step and the time of computation in retrieving computer solutions, it is evident from some of the testing and from the time complexity t(n).