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

Abstract

Tic-Tac-Toe is one of the board games that can hone the motor skills of the brain. This game uses 2 pawns, there are X and O. The game started with X’s pawn as the player who first turns, the game got win condition if the player or the enemy put the 3 pawns in a diagonal, vertical or horizontal line. While the game got draw if there is no player or enemy who put 3 pawns in a diagonal, vertical or horizontal line. The game’s problems are the player should think about the next best step to win and defend with put pawn to block enemy’s steps to win. To solve the problems, the game needs some algorithms, there are Minimax algorithm and Breadth First Search algorithm. Minimax algorithm explores node from deepest level and evaluates the scores using minimum or maximum value. Breadth First Search algorithm is an algorithm which explores node widely and compares evaluation scores to the deepest level. In this research, each algorithm is tested to response time and number of nodes needed on a 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 the 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.