Yustian, Yustian (2019) Desain dan Analisa Algoritma Strategi Permainan Catur dengan Metode Divide and Conquer. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
05111540000058-Undergraduate_Theses.pdf Download (1MB) | Preview |
Abstract
Permasalahan yang dibahas pada Tugas Akhir ini terkait pada cara menentukan kondisi permainan dan jumlah langkah valid yang dapat dilakukan berdasarkan konfigurasi dari bidak catur pada papan catur yang diberikan, dengan jumlah bidak dan lebar papan yang jauh lebih banyak dan besar dibanding permainan catur pada umumnya. Karena kondisi yang tidak lazim ini perlu dilakukan pemecahan masalah menjadi sub-problem yaitu pencarian bidak terdekat yang dapat dilakukan dengan pencarian lower bound dan upper bound dari posisi sekarang. Untuk dapat mendukung pencarian bidak terdekat, informasi dari bidak disimpan dalam bentuk map-set yang dikelompokkan berdasarkan posisi x, posisi y, atau kombinasi dari x dan y. Tugas Akhir ini memberikan sebuah penyelesaian terhadap permasalahan yang dideskripsikan pada paragraf pertama dengan pendekatan divide and conquer yang digabungkan dengan strategi permainan catur. Solusi dari permasalahan dilakukan dengan pertama menentukan untuk tiap bidak raja apakah berada dalam kondisi sekak, kemudian mencari jumlah langkah valid yang dapat dilakukan, dari kedua hasil proses sebelumnya kondisi permainan dapat ditentukan. Solusi yang digunakan dalam menyelesaikan permasalahan ini memiliki kompleksitas O(p log q log q + 18q log q) dimana p adalah jumlah bidak dalam satu papan dan q adalah nilai minimal dari lebar papan dan jumlah bidak dalam papan.
================================================================================================
The problem imposed in this Final Project is how to determine the condition of chess game and the number of plausible move given a configuration of chess piece in a chess board with the number of chess piece and the length of board are far bigger than the one in the normal game of chess. Because of this abnormality there is a need to divide this problem to sub-problems which in this case is finding the closest chess pieces which can be achieved by finding the lower bound and upper bound of the current position. To be able to support the finding of closest chess pieces, the information of the chess piece should be saved in form of map-set where it is grouped based on their x position, y position, or the combination of both x and y. This Final Project gives a solution to the problem described in the previous paragraph with divide and conquer approach combined with chess game strategy. The solution is done by firstly determine for each king whether it is in check, after that find the plausible move, based on the result of previous two process the game condition can be determined. The solution used to solve this problem had O(p log q log q + 18q log q) where p is the number of chess piece on one board and q is the minimum of board length and number of piece.
| Item Type: | Thesis (Undergraduate) |
|---|---|
| Additional Information: | RSIf 511.8 Yus d-1 2019 |
| Uncontrolled Keywords: | Catur, Divide and Conquer, Lower Bound, Map, Set, Upper Bound. |
| Subjects: | Q Science > QA Mathematics > QA9.58 Algorithms |
| Divisions: | Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis |
| Depositing User: | Yustian Yustian |
| Date Deposited: | 26 Apr 2022 03:40 |
| Last Modified: | 26 Apr 2022 03:40 |
| URI: | http://repository.its.ac.id/id/eprint/60793 |
Actions (login required)
 |
View Item |