Strategi Permainan Puzzle Yin-Yang Menggunakan Satisfiability Modulo Theories

'Arifah, Za'imatul (2023) Strategi Permainan Puzzle Yin-Yang Menggunakan Satisfiability Modulo Theories. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 06111940000066-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 October 2025. Download (8MB) | Request a copy

Abstract

Permainan merupakan sarana hiburan yang dapat dijangkau oleh berbagai kalangan.Terdapat berbagai jenis permainan seperti permainan fisik, permainan daring (game online), dan permainan logika. Salah satu permainan yang sampai saat ini masih dimainkan adalah permainan puzzle. Permainan puzzle Yin-Yang merupakan suatu puzzle dengan m × n grid, dengan setiap selnya terdiri dari lingkaran hitam, atau lingkaran putih, atau sel kosong. Terdapat beberapa metode yang dapat digunakan untuk menyelesaikan permainan puzzle Yin-Yang, diantaranya adalah Satisfiability Modulo Theories (SMT). SMT merupakan suatu permasalahan yang menguji apakah statement logika orde pertama (first order logic) memiliki penyelesaian. Banyak penelitian yang membahas penerapan SMT untuk menyelesaikan permainan, seperti pada permainan Slitherlink, Wordle, Sudoku, Sako, Hidato, dan masih banyak lagi. Akan tetapi, belum ada penelitian terkait penerapan SMT sebagai penyelesaian permainan puzzle Yin-Yang. Penelitian ini berfokus pada penerapan SMT sebagai strategi untuk memenangkan permainan puzzle Yin-Yang. Bahasa Python digunakan dalam uji kasus penyelesaian permainan puzzle Yin-Yang ini. Dalam penelitian ini, permainan puzzle Yin-Yang dan aturan-aturan yang terlibat dalam permainan ditransformasi menjadi permasalahan SMT kemudian dilakukan implementasi algoritma yang menggunakan SMT Solver untuk mencari solusi yang memenuhi permasalahan SMT tersebut. Berdasarkan hasil pengujian yang telah dilakukan, terbukti bahwa secara empiris SMT mampu menghasilkan solusi sesuai dengan aturan permainan.
=================================================================================================================================
A game is entertainment that can be enjoyed by various groups. There are various types of games, such as physical games, online games, and logic games. One of the games that still exists today is a puzzle game. Yin-Yang puzzle is a m×n grid of cells, with each cell consisting of a black circle, a white circle, or a blank cell. There are several methods that can be used to solve Yin-Yang puzzle, one of them is Satisfiability Modulo Theories (SMT). SMT is a problems that test whether statement from first order logic have a solution. Many studies discuss implementing SMT to finish the game, as in Slitherlink, Wordle, Sudoku, Sako, Hidato, and many more. However, there has been no related research on the application of the SMT method as a solution to the Yin-Yang puzzle game. This research will focus on implementing SMT as a strategy for winning Yin-Yang puzzle game. The Python language is used in the test cases for solving this one. In this research, we developed representation in SMT to represent the Yin-Yang puzzle grid and the rules involved in the game. The implementation of the algorithm using SMT Solver is looking for a solution that satisfies the SMT representation that has been made. Our experiments show that it is empirically proven that SMT method has been implemented produces a right solution based on game rules.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	Satisfiability Modulo Theories, Puzzle Yin-Yang, Z3, Yin-Yang Puzzle
Subjects:	Q Science > QA Mathematics > QA166 Graph theory
Divisions:	Faculty of Science and Data Analytics (SCIENTICS) > Mathematics > 44201-(S1) Undergraduate Thesis
Depositing User:	Za'imatul 'Arifah
Date Deposited:	05 Dec 2023 02:28
Last Modified:	05 Dec 2023 02:28
URI:	http://repository.its.ac.id/id/eprint/102580

Actions (login required)

View Item