Desain Dan Analisis Algoritma Depth First Search Dan Metode Pruning Pada Permasalahan Spoj 32843 Adaqubic - Ada And Tictactoe.

Oktaviana, Sandra Agnes (2022) Desain Dan Analisis Algoritma Depth First Search Dan Metode Pruning Pada Permasalahan Spoj 32843 Adaqubic - Ada And Tictactoe. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 05111840000124-Undergraduate_thesis.pdf Restricted to Repository staff only Download (3MB)

Abstract

Permasalahan dalam tugas akhir ini adalah SPOJ 32843 ADAQUBIC – Ada and TicTacToe. Dalam permasalahan ini diminta mencari pemenang permainan 3D tictactoe dengan ukuran 3 × 3 × 3 yang ditinggalkan pemain dalam keadaan belum selesai. Tugas akhir ini mengulas penyelesaian permasalahan dengan menggunakan algoritma Depth First Search (DFS) dan metode pruning. Pencarian pemenang dilakukan dengan penelusuran menggunakan DFS dan metode pruning sebagai optimasi berdasarkan keadaan menang permainan (winning state), yang mana pada kasus ini memiliki 49 winning states. Keadaan papan permainan disimpan dalam bentuk Bitboards, yaitu stuktur data yang didesain untuk encoding sebuah papan permainan secara efisien dengan mengubah kondisi (state) permainan ke dalam bentuk bit. Penelusuran DFS dilakukan dengan membandingkan keadaan papan yang telah disimpan dalam bentuk Bitboards dan masing-masing winning state dengan menggunakan operasi Bitwise, sehingga didapatkan hasil pemenang apabila keadaan menang berhasil dicapai oleh salah satu pemain.
Berdasarkan hasil uji coba pada studi kasus yang diberikan, penyelesaian menggunakan algoritma Depth First Search dan metode pruning ini membutuhkan rata-rata waktu sebesar 0,127 detik dan memori 5,4 MB.
==============================================================================================================================
The problem in this thesis is SPOJ 32843 ADAQUBIC – Ada and TicTacToe. The problem asks to find the winner of 3D tictactoe game with a size of 3 × 3 × 3 that the player left unfinished. This thesis discusses the problem solving using Depth First Search (DFS) algorithm and pruning method. The search for winner is carried out by traversing using DFS and pruning methods as optimization based on the winning states, which in this case has 49 winning states. The state of the game board is stored in the form of Bitboards, which are data structure designed to encode an efficient game board by converting state of the game into bits. The DFS traverse is carried out by comparing the state of the board that has been stored in Bitboards and each winning state using Bitwise operations, so that the end game obtained if the winning state is successfully achieved by one of the players. Based on the trials from the given case study, the solution of this problem using Depth First Search algorithm and pruning method requires an average time of 0,127 seconds and memory of 5,4 MB.

Item Type:	Thesis (Other)
Additional Information:	RSIf 005.73 Okt d-1 2022
Uncontrolled Keywords:	Bitboards, Depth First Search, Pruning, 3D Tictactoe. Bitboards, Depth First Search, Pruning, 3D Tictactoe.
Subjects:	T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK5105.546 Computer algorithms
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Mr. Marsudiyana -
Date Deposited:	26 May 2026 03:32
Last Modified:	26 May 2026 03:32
URI:	http://repository.its.ac.id/id/eprint/133430

Actions (login required)

View Item