Implementasi Brute Force Pada Game Mahjong Titans

Implementasi Brute Forcepada Game Mahjong TitansYogi Adytia Marsal - 13508016Program Studi Teknik InformatikaSekolah Teknik Elektro dan InformatikaInstitut Teknologi Bandung, Jl. Ganesha 10 Bandung 40132, IndonesiaIF18016@itb.ac.idpenentuan susunan gambar sesuai yang di inginkanuser seperti gambar berikut ini.ABSTRAKGame Mahjong Titans merupakan salah satupermainan standar yang terdapat pada windows yangbertujuan menyamakan semua gambar yang samaataupun setipe. Gambar tersebut tertumpuk-tupuksehingga tidak semua gambar bisa kerjakan dalamwaktu bersamaan, Hanya ada beberapa gambar yangbisa dikerjakan. Selain itu tidak semua gambar bisadilihat pada waktu awal permainan tapi seiringberjalannya permainan gambar tersebut akanterlihat. Jika satu gambar di samakan, maka gambaritu akan di keluarkan dari tumpukan permainan danakan menambah ataupun mengurangi banyakgambar yang bisa diselesaikan. Hal ini dilakukanterus hingga semua gambar disamakan semua.Banyak algoritma yang bisa di gunakan untukmenyelesaikan permainan ini. Salah satunya adalahdengan menggunakan pohon dengan metodapencariannya solusi menggunakan algoritma "BruteForce”.Algoritma ini menggunakan matriks yang salahsatu ukuran 72x72. Hal ini karena jumlah semuamahjong yang tersusun adalah 144 buah dan tentupastinya ada dua gambar yang sama. Matriks inilahyang akan berisi data-data pohon dimana baris darimatriks tersebut merupakan kedalaman dari pohontersebut yaitu 72.Kata Kunci—Brute Force, Matriks,pohon, mahjongtitans.I. PENDAHULUANGambar 1. Pemilihan Susunan Mahjong TitansAda 6 macam susunan yang bisa di pilih, setiapsusunan memiliki tingkat kesulitan yang berbedabeda. 6 susunan tersebut adalah, Turtle, Dragon,Cat,Fortress,Crab dan Spider.Setelah memilih susunan tersebut barulahpermainan dimulai. Mulailah pemain untukmenyamakan gambar tersebut satu persatu. Tidaksemua gambar bisa disamakan karena masihtertutup oleh gambar lain. Gambar yang bisa diselesaikan adalah gambar yang teratas dan gambaryang terletak paling kiri atau kanan saja, walaupungambar yang dibawahnya sudah bisa terlihat tapikarena bukan gambar yang terluar(terkiri atauterkanan) tetap tidak bisa di kerjakan.kita mendengar kata mahjong, tentu kita akanteringat dengan permainan judi asal cina yangsangat terkenal yang di mainkan oleh empat orang,tapi pada kesempatan ini penulis tidak bermaksudmembahas Mahjong tersebut tapi Mahjong titansyang dimainkan oleh satu orang dan merupakanpermainan komputer versi mahjong solitaire yangdi kembangkan oleh Oberon Games yang terdapatdalam produk operating sistem microsoft.Permainan ini memiliki beberapa macamMakalah IF3051 Strategi Algoritma – Sem. I Tahun 2010/2011

kedalaman setegah dari jumlah mahjong yangdisusun yaitu 72, karena dalam permainan ini pastiada 2 gambar yang memiliki gambar yang samaatau setipe dan oleh karena itu total mahjongsebanyak 144 pasti akan menyamakan sebanyak 72kali.Dalam Permainan ini tidak semua gambar dapatdiselesaikan dalam waktu bersamaan karena masihada gambar yang tertutup dan pemain belum tahuapa gambar yang tertutup itu, hal inilah yangmembuat pemain akan terjebak kedalam jalanbuntu jika salah dalam menentukan gambar.Gambar 2. Contoh soal Mahjong Titans TurtlePada permainan ini ada 4 gambar yang memilikikesamaan sehingga ada kemungkinan jika salahdalam memilih jalan yang digunakan akanmembuat permainan ini tidak bisa diselesaikandikarenakan gambar sama tinggal 2 buah dangambar tersebut terdempet. Jika semua gambar bisadisamakan dengan kata lain game terselesaikanmaka pemain akan menang dan akan memperolehwaktu pengerjaan dan poin, semakin cepat pemainmenyelesaikan, semakin besar poin yang diperoleh.II.I Pemodelan PohonPada bagian ini merupakan pemodelan daripermainan Mahjong Titans agar bisa diselesaikandengan menggunakan algoritma Brute Force.Pemodelan memasukkan pola yang dapat diselesaikan dalam permainan ini kedalam bentukpohon. Untuk setiap gambar di beri penomoran dari1-36 karena satu gambar terdapat pada 4 buatmahjong sedangkan jumlah mahjong yangdigunakan adalah 144 buah.Untuk tahap awal kita masukkan semuapersoalan mahjong tersebut kedalam array tigadimensi yang berukuran sama. Jika di kotaktersebut tidak terdapat mahjongnya maka dalammatriks akan diisi dengan 0. Tetapi mahjong yangmasih tertutup diisi dengan 37. Untuk satu mahjongmengambil tempat 2 kolom 2 baris. Karena lebarnya ada 15 mahjong dan tingginya ada 8 mahjongbrarti ukuran matriksnya adalah 30x16.Gambar 3. Soal Mahjong Titans yang sudah terselesaikanPermasalahan pada permainan ini dapatdiselesaikan dengan salah satu algoritma pencariansolusi yaitu brute force. Algoritma ini akanmerepresentasikan permainan ini kedalam pohon,metode yang digunakan mirip dengan Breath FirstSearch(BFS). Cuman karena semua kemungkinandicoba menyebabkan algoritma ini lebih mengarahke algoritma brute force, tapi tetap saja pencariannya melebar seperti algorima BFS.Gambar 4. Soal Mahjong TitansII. PENERAPAN ALGORITMA BRUTEFORCEPenyelesaian “Mahjong Titans” dengan metodeBrute Force membutuhkan pohon denganGambar 5. Simulasi matriks teratas yang terdapat dalamarray tiga dimensiMakalah IF3051 Strategi Algoritma – Sem. I Tahun 2010/2011

Selanjutnya dalam pemimplementasian pohon initentunya terlebih dahulu perlu membutuhkan fungsiyang menentukan berapa banyak mahjong yangbisa disamakan. Tapi sebelumnya dibuat dulufungsi yang menghasilkan semua mahjong yangterletak dibagian yang bisa diselesaikan.Fungsi ini memasukkan semua mahjong yangbisa terletak paling atas dan paling luar(terkiri atauterkanan tapi bukan yang paling atas maupun yangpaling bawah) kedalam sebuat array yang nantinyaakan dimasukkan kedalam pohon yang dirancanguntuk menentukan yang mana saja yang bisadiselesaikan.Ada beberapa kemungkinan yang terjadi pada 1buah jenis mahjong ataupun 1 gambar mahjong,yaitu1. Hanya satu gambar yang sama dalamwaktu yang tertentu. Jika terjadi kasusini berarti gambar di abaikan karenatidak memiliki pasangan dengan katalain tidak di masukkan kedalam pohon.2. Ada dua gambar yang bisa disamakandalam waktu tertentu. Jika terjadi kasusini maka gambar ini langsungdimasukkan kedalam pohon karenatidak ada kemungkinan lain yang bisadisamakan lagi.3. Ada tiga gambar yang bisa disamakanpada waktu tertentu. Jika terjadi kasusini maka akan terjadi tiga kemungkinanjuga yaitu :a. Penyamaan gambar 1 dengangambar 2b. Penyamaan gambar 1 dengangambar 3c. Penyamaan gambar 2 dengangambar 3Ketiga kemungkinan diatas dimasukkansemuanyakedalam pohon sebagaisemua kemungkinan yang bisa terjadiuntuk disamakan. Karena jika terjadikemungkinan diatas ada kemungkinandari salah satu kasus tersebut yang akanmembuat permainan tidak dapatdiselesaikan, misalkan ada gambar yangsama dibawah salah satu gambartersebut.4. Ada empat gambar yang bisadisamakandalamwaktuyangbersamaan maka jadikan empat gambartersebut menjadi dua pasang gambaryang sama secara bebas lalu masukkanke dalam pohon karena bagaimana punkombinasinya gambar tersebut sudahpasti akan selesai.Header untuk pembentukan pohon tersebutsebagai berikut:Typedef MatSol: bapak: int,Tree : Matriks procedure TreeMaker(input/output Tree:matriks,inputsolusi: Matriks){procedure yang digunakan untukmembuat pohon denganmemanfaatkan procedure-procedurelain seperti Terluar danPencariPasangan}Procedure MahjongtoMartiks(output Mahjong: Array OfMatriks){procedure ini merupakanprocedure untuk membuat array ofmatriks yang mensimulasikansusunan mahjong kedalam Array ofMatriks}function Terluar(input Mahjong:array of Matriks, outputTerluar: Matriks){fungsi yang berguna membacaarray tiga dimensi yangdimasukkan dan menghasilkanMatriks yang berisi semuamahjong yang terluar}function PencariPasangan(inputTerluar: Matriks, output solusi: MatSol){fugsi ini berfungsi untukmenseleksi pasangan dari mahjongterluar, fungsi ini menghasilkanmatriks yang berisi semuakemungkinan pasangan gambarmahjong tersebut}Makalah IF3051 Strategi Algoritma – Sem. I Tahun 2010/2011

procedure Update(){procedure yang berfungsi untukmeng-update kemungkinan yangbisa setelah salah satukemungkinan yang ada dieksekusi}procedure Open(input/outputmahjong: array of matriks, inputlayer : int , input posisi :point, input Yg terbuka:matriks){procedure yang berfungsi untukmeng-update data mahjong yangtelah terbuka}procedure FindPath(input solusi:MatSol, output path : Matriks,input possol:int){procedure ini merupakanprosedur untuk menemukan pathdari solusi dengan menelusuribapak dari possol(posisi solusi)hingga posisi yang tidak punyabapaknya lagi atau Parentutamanya}Pada permainan ini masih ada bagian yangtertutup. Dan hal ini tidak bisa di tebak mahjongapa yang tertutup tersebut secara sembarangankarena hanya ada 4 mahjong yang mungkin dalamsatu permainan. Jadi solusi yang di peroleh belumtentu sama juga. Untuk fungsi yang open tersebutakan meng-generate mahjong yang tertutuptersebut dari data mahjong yang telah terbuka.Dengan cara memilih secara random dari 32kemungkinan jenis mahjong yang mungkin munculdan membandingkan total mahjong yang telahterbuka(maksimal ada empat mahjong terbuka) .jika mahjong yang telah terbuka tersebut belummencapai empat buah dari hasil random tersebut,maka angka tersebut akan dimasukkan kedalamarray of matriks yang berisi data susunan mahjongtersebut. Agar tidak terjadi pengulangan data,misalkan tipe mahjong 1 sebenarnya sudahdiketahui telah terbuka 4 kali, tapi 2 telahdiselesaikan, maka dari hasil random, misalkan bisadi peroleh angka satu maka bisa saja tipe mahjong1 tersebut digunakan lagi, untuk mencegah itu perlujuga di bandingkan dengan mahjong yang telahterbuka. Dan yang tentunya harus diisi adalahbapak dari pilihan tersebut yaitu susunan yangsebelum memilih pilihan tersebut.Fungsi dan procedure yang ada tersebut di susunsedemikian rupa untuk bisa di looping hinggapersoalan berhasil ditemukan, hal ini akanmembentuk suatu pohon n-ner. Jika Pohon telahterbentuk maka kita bisa melanjutakan ketahapberikutnya yaitu tahap pencarian dengan metodabrute force.II.II Algoritma Brute ForceMetoda Brute Force, dari artinya kita sudah bisamengetahui metoda yang digunakan. Metoda inimemperoleh solusi dari suatu permasalahan dengancara mencoba semua kemungkinan yang akanterjadi setiap pengambilan keputusan dalampenyelesaian permasalahan tersebut. Akibatnya jikamendapatkan kasus terburuk akan memperolehwaktu eksekusi yang sangat lama.Sebelumnya kita telah membuat list yang berisibagian-bagian mana salah yang bisa di samakanatau diselesaikan. Setelah itu dijadikan menjadisebuah pohon. Pohon tersebut dibuat secararecursif dalam setiap pengulangan.Pada setiap pengulangan dimasukkan semuakemungkinan yang di update terus sehingga semuakemungkinan tersebut tidak terlewatkan. Prosedureupdate berfungsi agar pembuatan daerah yang bisadisamakan lebih efisien. Dengan cara hanyamemperhitungkan daerah yang berubah saja.Dengan demikian daerah yang terbentuk setiaplooping akan bisa di tentukan. Update ini jugamerupakan fungsi yang akan menerima gambarbaru dari mahjong yang sebelumnya tertutup olehmahjong lainnya. Sebelum melakukan updateseharusnya dilakukan dulu procedure open untukmengetahui meng-update susunan mahjong yangtelah terbuka.Selanjutnya akan dilooping terus sampaiditemukannya state dimana tidak array yangdihasilkan oleh procedure update tidak ada lagiatau hasilnya adalah array kosong. Tapi mahjongmasih belum terselesaikan, maka akan lanjutketahap berikutnya dan tahap yang sebelumnyaakan diabaikan.Pembuatan pohonnya yang terjadi karena terjadilooping ini di buat dari pohon induk trus anakpaling kirin sampai anak paling kanan. Laluselanjutnya pada kedalaman berikutnya, mulai darianak paling kiri hingga anak paling kanan hinggaditemukan solusi. Jika ada pengabaian, makaMakalah IF3051 Strategi Algoritma – Sem. I Tahun 2010/2011