Penyelesaian Impartial Game Menggunakan Metode Greedy: Studi Kasus SPOJ 13816 - PGAME

Ramadhan, Muhammad Zikri (2025) Penyelesaian Impartial Game Menggunakan Metode Greedy: Studi Kasus SPOJ 13816 - PGAME. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 5025211085-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only Download (3MB) | Request a copy

Abstract

Game theory adalah salah satu cabang ilmu matematika yang mempelajari tentang keputusan strategis. Salah satu jenis permainan ditinjau dari karakteristiknya adalah impartial game. Jenis permainan ini menjadi fokus tugas akhir. Studi kasus yang dibahas tugas akhir ini diambil dari laman Sphere Online Judge (SPOJ) dengan judul Pheversos Game dan kode PGAME. Permainan ini melibatkan dua pemain yang secara bergantian mengambil satu bilangan dari ujung kiri atau kanan suatu baris pada papan permainan. Persoalan ini meminta menentukan pemenang serta skor akhir jika kedua pemain bermain secara optimal. Permasalahan utama pada tugas akhir ini adalah jumlah kemungkinan skenario permainan yang sangat besar, serta bagaimana mereduksi kompleksitas solusi sehingga mampu menjawab persoalan dalam batas waktu dan alokasi memori yang ditentukan. Solusi yang dikembangkan menggunakan metode greedy untuk menentukan langkah optimal pemain pada tiap giliran. Pendekatan ini dipilih karena mampu mereduksi kompleksitas waktu. Untuk memastikan strategi greedy dapat diterapkan, tiap baris pada papan permainan disederhanakan melalui proses fusion dan fruitless move tanpa mengubah hasil akhir permainan. Struktur data stack digunakan dalam implementasi proses penyederhanaan ini. Solusi dirancang dengan kompleksitas waktu O(MN). Solusi kemudian diujikan pada laman SPOJ dan berhasil mendapatkan verdict: accepted. Solusi berjalan dengan waktu eksekusi rata-rata 0,076 detik dan alokasi memori rata-rata sebesar 5,22 MB dari 10 kali percobaan.
======================================================================================================================================
Game theory is a branch of mathematics that studies strategic decision-making. One type of the game based on its characteristic is the impartial game, which is the focus of this research. The case study discussed in this work is taken from the Sphere Online Judge (SPOJ) platform, specifically the Pheversos Game with the problem code PGAME. The game involves two players who take turns selecting a number from either the left or right end of a row on a game board. The goal is to determine the winner and the final scores, assuming both players play optimally. The challenge in this final project is the huge number of possible game scenarios, and how to reduce the solution’s complexity to satisfy the given time and memory constratints.The solution applies a greedy method to determine the optimal move at each turn. This approach is chosen because it helps reduce time complexity. To ensure the greedy strategy can be applied, each row of the game board is simplified through fusion and fruitless move processes without altering the final outcome of the game. A stack data structure is used to implement these simplification processes.
The solution was designed with a time complexity O(MN). This solution was tested on SPOJ with an accepted verdict. It achieved an average execution time of 0,076 seconds and an average memory usage of 5.22 MB over ten submissions.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	fruitless move, fusion, greedy, impartial game, fruitless move, fusion, greedy, impartial game
Subjects:	Q Science > QA Mathematics > QA269 Game theory Q Science > QA Mathematics > QA76.6 Computer programming. Q Science > QA Mathematics > QA9.58 Algorithms
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Muhammad Zikri Ramadhan
Date Deposited:	31 Jul 2025 01:39
Last Modified:	31 Jul 2025 01:39
URI:	http://repository.its.ac.id/id/eprint/123286

Actions (login required)

View Item