Perbandingan Performa Algoritma Minimax dan Breadth First Search Pada Permainan Tic-Tac-Toe

Jerry Setiawan, Farhan Agung Famerdi, Daniel Udjulawa, Yohannes Yohannes

Abstract


Tic-Tac-Toe is one of the board games that can hone the motor skills of the brain. This game used 2 pawn, there is X and O. Game started with X’s pawn as player who first turn, game got win condition if player or enemy put the 3 pawns in diagonal, vertical or horizontal. While game got draw if there is no player or enemy who put 3 pawns in diagonal, vertical or horizontal. The game’s problems are player should think about next best step for win and defend with put pawn to block enemy’s steps to win. To solve the problems, game needed a algorithms, there are Minimax algorithm and Breadth First Search algorithm. Minimax algorithm exploring node from depthest level and evaluate the scores using min or max value. Breadth First Search algorithm is algorithm which exploring node widenly and compare evaluation scores to depthest level. In this research, each algorithm is tested to response time and number of nodes needed on game board with 3×3, 5×5, 7×7, and 9×9 size as much as 16 scenarios. Based on the test results, Breadth First Search algorithm is superior to Minimax on 3×3 board size in terms of response time and number of nodes required. While the Minimax algorithm is superior to Breadth First Search on 5×5 and 9×9 board size in terms of response time and the number of nodes required. In the first turn, the algorithm will trace the number of nodes larger than the next step so that the placement of the algorithm for the first turn affects the final result of the node number parameter.


Full Text:

PDF


DOI: http://dx.doi.org/10.28932/jutisi.v4i1.757

Refbacks

  • There are currently no refbacks.


Copyright (c) 2018 Jurnal Teknik Informatika dan Sistem Informasi