Jurnal Teknik Informatika dan Sistem Informasi
Vol 4 No 1 (2018): JuTISI

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

Setiawan, Jerry (Unknown)
Famerdi, Farhan Agung (Unknown)
Udjulawa, Daniel (Unknown)
Yohannes, Yohannes (Unknown)



Article Info

Publish Date
20 Apr 2018

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.

Copyrights © 2018






Journal Info

Abbrev

jutisi

Publisher

Subject

Computer Science & IT

Description

Jurnal Teknik Informatika dan Sistem Informasi (JuTISI) adalah Jurnal Ilmiah yang dibangun oleh Fakultas Teknologi Informasi, Universitas Kristen Maranatha untuk memberikan sarana bagi para akademisi dan peneliti untuk mempublikasikan karya-karya ilmiah di khalayak luas. Jurnal ini merupakan ...