JURNAL TEKNIK POMITS Vol. 1, No. 1, (2012) 1-6
1
Analisa Dan Implementasi Teorema Sprague-Grundy Pada Penyelesaian Variasi Game Nim Halimah Winajma, Yudhi Purwananto, S.Kom, M.Kom, dan Rully Soelaiman, S.Kom, M.Kom Jurusan Teknik Informatika, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember (ITS) Jl. Arief Rahman Hakim, Surabaya 60111 E-mail:
[email protected] Abstrak — Combinatorial game adalah permainan dua orang dengan informasi yang sempurna dimana winning position diperoleh apabila pergerakan lawan tidak dapat terjadi lagi (terminal position tercapai). Special Nim Game adalah salah satu contoh permainan combinatorial yang paling terkenal. Penyelesaian Special Nim Game menggunakan teorema SpragueGrundy yang diawali dengan penganalisisan mundur (backward induction). Selanjutnya dilakukan pencarian nilai SpragueGrundy untuk tiap-tiap nilai N dengan nilai Sprague-Grundy = 0 adalah winning position. Pada kasus ini diinginkan kemenangan untuk pemain kedua, sehingga nilai Sprague-Grundy yang dimiliki oleh N tertentu dapat dinyatakan kemenangan pemain kedua. Nilai Sprague-Grundy diperoleh dengan cara menghitung nilai integer non-negatif terkecil yang tidak ditemukan diantara nilai dari followers x, yang disebut dengan minimal excludant atau mex. Pada penganalisisan Special Nim Game menggunakan Sprague-Grundy untuk kemenangan pemain kedua diperoleh pada N=2, N=3, N=5, N=8, N=13, N=21, N=34, N=55, N=89, N=144, N=233, N=377, N=610, N=987, dan N=1597 dimana nilai Sprague-Grundy adalah 0 (nol). Kata Kunci— Combinatorial Game, Special Nim Game, Teorema Sprague-Grundy.
I. PENDAHULUAN OMBINATORIAL game adalah permainan dua orang dengan informasi yang sempurna dan tidak ada kesempatan untuk bergerak, dengan hasil menang atau kalah. Permainan ditentukan oleh satu set posisi, termasuk posisi awal, dan pemain yang bergantian untuk bergerak. Permainan bergerak dari satu posisi ke posisi lain, sampai posisi akhir (terminal position) tercapai. Terminal position adalah salah satu posisi yang mungkin tidak dapat bergerak. Maka salah satu pemain dinyatakan sebagai pemenang dan yang lainnya kalah. Teori ini dapat dibagi menjadi dua bagian, impartial games dimana set yang bergerak tersedia dari posisi tertentu adalah sama untuk kedua pemain, dan partizan games dimana masing-masing pemain memiliki set yang berbeda yang mungkin bergerak dari posisi tertentu. Combinatorial game yang paling terkenal adalah Nim Game. Cara bermain Nim Game adalah sebagai berikut, ada satu atau lebih tumpukan keping. Dua pemain bermain bergantaian. Setiap kali bermain, pemain mengambil satu keping atau lebih dalam satu tumpukan. Pemain tidak dapat memindahkan tumpukan lebih dari satu tumpukan pada satu giliran. Masing-masing pergerakan pemain tidak mempengaruhi pemain yang lain. Pemenangnya adalah pemain yang mengambil keping terakhir dalam tumpukan tersebut.
C
Dalam tugas akhir ini, ujicoba menitikberatkan pada Special Nim Game yang ada pada Sphere Online Judge problem set tutorial 1238, dimana jumlah keping yang diambil oleh pemain pertama yang mendapatkan giliran pertama adalah antara satu keping dan kurang dari sama dengan jumlah keping yang ada dalam tumpukan dikurangin satu (1 sampai N-1). Setelah langkah pertama, jumlah keping yang dapat diambil pemain berikutnya adalah antara satu dan maksimal kurang dari sama dengan dua kali jumlah keping yang diambil oleh pemain sebelumnya (1 sampai 2k, dimana k adalah jumlah keping yang diambil oleh pemain sebelumnya). Hal ini berlaku untuk semua pemain setelah langkah pertama dilakukan. Pemenangnya adalah pemain kedua. Jumlah keping yang ada dalam satu tumpukan adalah 2 sampai 2000 keping. II. ANALISIS DAN DESAIN Untuk menyelesaikan Special Nim Game, digunakan metode Sprague-Grundy. Pertama-tama akan dilakukan analisa permainan dari akhir dan kembali ke awal, yang disebut dengan metode induksi mundur (backward induction). Kemudian tentukan nilai Sprague-Grundy dari setiap N. Dan pada tahap akhir, menentukan jumlah N yang menyebabkan pemain kedua memenangkan permainan. A. Backward Induction Induksi mundur (backward induction) adalah proses penalaran mundur dalam waktu, dari akhir masalah atau situasi, untuk menentukan urutan tindakan yang optimal. Hasil dengan terlebih dahulu melihat posisi terakhir, keputusan mungkin dibuat dan memilih apa yang harus dilakukan dalam masalah atau situasi apa pun pada waktu itu. Menggunakan informasi ini, dapat ditentukan apa yang harus dilakukan pada saat-saat terakhir dari keputusan. Proses ini terus mundur sampai ditentukan tindakan yang terbaik untuk setiap masalah atau situasi yang mungkin pada setiap titik dalam waktu. Berikut analisis masing-masing nilai N, dengan pemetaan menggunakan parameter warna ungu untuk kemungkinan pertama, warna hijau untuk kemungkinan kedua, dan warna jingga untuk kemungkinan ketiga. Penjabaran proses pelaksanaan permainan ini untuk nilai N tertentu dijabarkan sebagai berikut: • N=2 Apabila N=2 dieksekusi pada permainan ini maka berdasarkan aturan Special Nim Game, pemain yang mendapatkan giliran pertama dapat mengambil keping antara 1 dan N-1, dimana N adalah jumlah keping. Dan pemain
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2012) 1-6 selanjutnya mengambil keping antara 1 dan 2k, dimana k adalah jumlah keping yang diambil pada pemain sebelumnnya. Karena N=2, maka pemain pertama hanya dapat mengambil 1 keping saja. Sehingga pemain kedua dapat memenangkan permainan dengan mengambil sisa keping (1 keping yang tersisa).
0
1
•
N=3 Apabila N=3 dieksekusi pada permainan ini maka berdasarkan aturan Special Nim Game, pemain yang mendapatkan giliran pertama dapat mengambil keping antara 1 dan N-1, dimana N adalah jumlah keping. Dan pemain selanjutnya mengambil keping antara 1 dan 2k, dimana k adalah jumlah keping yang diambil pada pemain sebelumnya. Karena N = 3, maka pemain pertama dapat mengambil 1 atau 2 keping. Apabila pemain pertama mengambil 1 keping, maka pemain kedua dapat mengambil 1 atau 2 keping sekaligus. Apabila pemain kedua mengambil 1 keping, maka pemain pertama dapat mengambil 1 keping yang tersisa dan memenangkan permainan. Tetapi apabila pemain kedua mengambil 2 keping sekaligus, maka pemain kedua memenangkan permainan. Apabila pada langkah pertama pemain pertama mengambil 2 keping sekaligus, maka pemain kedua juga dapat memenangkan permainan ini dengan mengambil 1 keping yang tersisa.
1
2
3
Gambar 2. Backward Induction N=3.
•
Apabila pada langkah awalnya pemain pertama mengambil 2 keping, maka pemain kedua dapat mengambil 1, 2, 3, atau 2 keping. Tetapi karena sisa N=2, maka maksimal pemain kedua dapat mengambil 2 keping. Apabila pemain kedua mengambil 1 keping, maka pemain pertama dapat memenangkan permainan dengan mengambil 1 keping yang tersisa. Tetapi apabila pada langkah sebelumnya pemain kedua mengambil 2 keping sekaligus, maka pemain kedua dapat memenangkan permainan.
2
Gambar 1. Backward Induction N=2.
0
2
N=4 Apabila N=4 dieksekusi pada permainan ini maka berdasarkan aturan Special Nim Game, pemain yang mendapatkan giliran pertama dapat mengambil keping antara 1 dan N-1, dimana N adalah jumlah keping. Dan pemain selanjutnya mengambil keping antara 1 dan 2k, dimana k adalah jumlah keping yang diambil pada pemain sebelumnya. Karena N=4, maka pemain pertama dapat mengambil 1, 2, atau 3 keping sekaligus. Apabila pada langkah awal pemain pertama hanya mengambil 1 keping, maka pemain kedua dapat mengambil 1 atau 2 keping dari tumpukan tersebut. Jika pemain kedua hanya mengambil 1 keping, maka pemain pertama dapat mengambil 1 atau 2 keping sekaligus dan memenangkan permainan. Tetapi apabila hanya mengambil 1 keping, maka pemain kedua memenangkan permainan dengan mengambil 1 keping yang tersisa. Tetapi apabila langkah sebelumnya pemain kedua pemain mengambil 2 keping, maka pemain pertama dapat memenangkan permainan.
Sedangkan apabila pada langkah awal pemain pertama mengambil 3 keping sekaligus, maka pemain kedua akan memenangkan permainan, karena pemain pertama hanya menyisakan 1 keping saja.
0
1
2
3
4
Gambar 3. Backward Induction N=4.
Apabila proses backward induction dilakukan secara manual, ketika jumlah keping semakin besar akan mengalami kesulitan. Untuk memudahkan penghitungan, digunakan algoritma sebagai berikut: 1 Tentukan jumlah keping yang akan dihitung. 2 Inisialisasi array untuk menyimpan langkah-langkah secara backward induction. 3 Tentukan jumlah keping yang bisa diambil oleh pemain dan disimpan dalam array. 4 Langkah 3 diulangi mulai dari sejumlah keping-1 sampai lebih besar sama dengan 0 (diulangi secara decrement). B. Fungsi Sprague-Grundy Sama seperti backward induction menggunakan graph, pada tahap ini juga akan dijelaskan bagaimana mengetahui kemungkinan langkah-langkah yang dapat dilakukan oleh setiap pemain. Fungsi Sprague-Grundy dari grafik (X, F) adalah fungsi g yang didefinisikan X dan mengambil nilai integer non-negatif, sehingga g(x) = min{n ≥ 0 : n ≠ g(y) untuk y∈ F(x)}. g(x) integer non-negatif terkecil yang tidak ditemukan diantara nilai dari followers x. Jika kita mendefinisikan minimal excludant atau mex dari satu set non-negatif integer sebagai bilangan bulat non-negatif terkecil, maka kita bisa menuliskan g(x) = mex {g(y) : y ∈ F(x)}. g(x) didefinisikan dalam g(y) untuk semua pengikut y dari x. Untuk simpul terminal, x didefinisikan menyiratkan bahwa g(x) = 0, karena F(x) adalah himpunan kosong untuk terminal x. Untuk non-terminal x, semua pengikut terminal g(x) = 1. Seperti penjelasan pada sub bab sebelumnya, menentukan langkah-langkah yang dapat dilakukan pada permainan ini, dalam tabel ini juga menggunakan backward induction dalam menentukan langkah-langkah permainan. Maka berdasarkan aturan Special Nim Game, pemain yang mendapatkan giliran pertama dapat mengambil keping antara 1 dan N-1, dimana N
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2012) 1-6 adalah jumlah keping. Dan pemain selanjutnya mengambil keping antara 1 dan 2k, dimana k adalah jumlah keping yang diambil pada pemain sebelumnya. Untuk menganalisis nilai Sprague-Grundy diperlukan tabel dengan ukuran N×N. Berikut analisis masing-masing nilai N, dengan pemetaan menggunakan parameter warna ungu untuk kemungkinan pertama, warna hijau untuk kemungkinan kedua, warna jingga untuk kemungkinan ketiga, warna hitam untuk kemungkinan keempat, dan warna biru untuk kemungkinan kelima. Berikut adalah tabulasi kemungkinan yang akan terjadi dengan nilai N tertentu, yaitu: • N=2 Pada permainan N=2, analisis dilakukan dengan didahului memetakan langkah-langkah yang mungkin terjadi bila nilai N=2. Berdasarkan peraturan permainan, pemain pertama hanya bisa mengambil 1 keping saja. Dan pemain kedua dapat memenangkan permainan dengan mengambil 1 keping yang tersisa. Tabel 1. Backward Induction N=2. ke dari 0 1 2
0
1
2
Dari langkah-langkah diatas, dapat lihat bahwa ketika tumpukan keping N=2 hanya ada satu kemungkinan langkah awal yang dapat dilakukan oleh pemain pertama, yaitu mengambil 1 keping. Sehingga pemain kedua dapat mengambil 1 keping yang tersisa dan memenangkan permainan karena batas pengambilan keping yang dapat dilakukan oleh pemain kedua adalah 1 keping sampai 2 keping. Jadi Sprague-Grundy value untuk 2 keping jika pemain pertama mengambil 1 keping adalah 1, dimana batas pengambilan adalah 2 keping. Dan selanjutnya pemain kedua mengambil 1 keping yang tersisa, sehingga Sprague-Grundy value untuk 2 keping adalah 0, yang artinya pemain pertama akan kalah, berapapun jumlah kepingan yang diambil. •
N=3 Pada permainan N=3, analisis dilakukan dengan didahului memetakan langkah-langkah yang mungkin terjadi bila nilai N=3. Berdasarkan peraturan permainan, pemain pertama dapat mengambil 1 keping atau 2 keping. Apabila pemain pertama hanya mengambil 1 keping (maka kolom yang ditandai adalah kolom (3,2)), maka pemain kedua dapat mengambil 1 keping atau 2 keping (kolom yang ditandai adalah kolom (2,1) dan (2,0)). Apabila pemain kedua mengambil 1 keping, maka pemain pertama dapat mengambil 1 keping yang tersisa (tandai kolom (1,0)). Apabila pemain pertama mengambil 2 keping sekaligus (kolom yang ditandai adalah kolom (3,1)), maka pemain kedua dapat mengambil 1 keping yang tersisa (kolom yang ditandai adalah kolom (1,0)).
3 Tabel 2. Backward Induction N=3. ke dari 0 1 2 3
0
1
2
3
Dari langkah-langkah diatas, dapat lihat bahwa ketika tumpukan keping N=3 ada dua kemungkinan langkah awal yang dapat dilakukan oleh pemain pertama, yaitu mengambil 1 keping atau 2 keping sekaligus. Pada saat pemain pertama mengambil 2 keping, maka pemain kedua dapat mengambil 1 keping yang tersisa dan memenangkan permainan karena batas pengambilan keping yang dapat dilakukan oleh pemain kedua adalah 1 keping sampai 4 keping. Pada saat pemain pertama mengambil 1 keping, maka pemain kedua dapat mengambil 2 keping yang tersisa dan memenangkan permainan karena batas pengambilan keping yang dapat dilakukan oleh pemain kedua adalah 1 keping sampai 2 keping. Jadi Sprague-Grundy value untuk 3 keping jika pemain pertama mengambil 1 keping adalah 0 (nol), dimana batas pengambilan adalah 2 keping. Sprague-Grundy value untuk 3 keping jika pemain pertama mengambil 2 keping adalah 0 (nol), dimana batas pengambilan adalah 4 keping. Sehingga Sprague-Grundy value untuk 3 keping adalah 0 (nol), yang artinya pemain pertama akan kalah, berapapun jumlah kepingan yang diambil. •
N=4 Pada permainan N=4, analisis dilakukan dengan didahului memetakan langkah-langkah yang mungkin terjadi bila nilai N=4. Berdasarkan peraturan permainan, pemain pertama dapat mengambil 1, 2, atau 3 keping sekaligus. Apabila pemain pertama hanya mengambil 1 keping maka yang ditandai adalah kolom (4,3), maka pemain kedua memiliki dua kemungkinan, yaitu mengambil 1 keping atau 2 keping. Apabila pemain kedua hanya mengambil 1 keping (yang ditandai kolom (3,2)), maka pemain pertama dapat mengambil 1 keping atau 2 keping sekaligus. Apabila pemain pertama mengambil 1 keping (yang ditandai kolom (2,1)), maka pemain kedua dapat mengambil 1 keping yang tersisa (yang ditandai kolom (1,0)). Apabila pemain pertama mengambil 2 keping sekaligus, maka yang ditandai adalah kolom (2,0). Apabila pada langkah sebelumnya pemain kedua mengambil 2 keping sekaligus (yang ditandai kolom (3,1)), maka pemain pertama dapat memenangkan permainan dengan mengambil 1 keping yang tersisa (yang ditandai kolom (1,0)). Apabila pada langkah awal pemain pertama mengambil 2 keping (yang ditandai kolom (4,2)), maka pemain kedua dapat mengambil 1 keping atau 2 keping sekaligus. Apabila pemain kedua mengambil 1 keping (yang ditandai kolom (2,1)), maka pemain pertama dapat mengambil 1 keping yang tersisa (tandai kolom (1,0)). Tetapi pemain kedua juda dapat mengambil 2 keping sekaligus (tandai kolom (2,0)). Apabila pada langkah awal pemain pertama mengambil 3 keping sekaligus (tandai kolom (4,1)), maka pemain kedua
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2012) 1-6 dapat mengambil keping yang tersisa, yaitu 1 keping (tandai kolom (1,0)). Tabel 3. Backward Induction N=4. ke dari 0 1 2 3 4
0
1
2
3
4
Dari langkah-langkah diatas, dapat lihat bahwa ketika tumpukan keping N=4 ada tiga kemungkinan langkah awal yang dapat dilakukan oleh pemain pertama, yaitu mengambil 1, 2, atau 3 keping sekaligus. Pada saat pemain pertama mengambil 3 keping, pemain kedua dapat mengambil 1 keping yang tersisa dan memenangkan permainan karena batas pengambilan keping yang dapat dilakukan oleh pemain kedua adalah 1 keping sampai 6 keping. Pada saat pemain pertama mengambil 2 keping, pemain kedua dapat mengambil 2 keping yang tersisa dan memenangkan permainan karena batas pengambilan keping yang dapat dilakukan oleh pemain kedua adalah 1 keping sampai 4 keping. Pada saat pemain pertama mengambil 1 keping maka 3 keping yang tersisa. Berdasarkan aturan permainan, maksimal pengambilan batu yang dapat diambil oleh pemain kedua adalah 2 keping. Sehingga pemain kedua bisa mengambil 1 atau 2 keping sekaligus. Jika pemain kedua mengambil 1 keping, maka pemain pertama dapat mengambil 2 keping yang tersisa dan memenangkan permainan. Dan jika pemain kedua mengambil 2 keping, maka pemain pertama dapat mengambil 1 keping yang tersisa dan memenangkan permainan. Jadi Sprague-Grundy value untuk 4 keping jika diambil 1 keping, batas pengambilan keping adalah 2 keping, maka Sprague-Grundy value adalah 0 (nol). Sprague-Grundy value untuk 4 keping jika diambil 2 keping, batas pengambilan 4 keping, maka Sprague-Grundy value adalah 2. SpragueGrundy value untuk 4 keping jika diambil 3 keping , batas pengambilan adalah 6 keping, maka Sprague-Grundy value adalah 1. Maka jumlah 4 keping harus diarahkan ke 3 keping agar pemain pertama dapat memenangkan pertandingan, sehingga Sprague-Grundy value untuk 4 keping dengan batas pengambilan 3 adalah 1. Apabila proses menentukan nilai Sprague-Grundy dilakukan secara manual, ketika jumlah keping semakin besar akan mengalami kesulitan. Untuk memudahkan penghitungan, digunakan algoritma sebagai berikut: 1. Tentukan jumlah keping dan jumlah maksimal keping yang bisa diambil oleh setiap pemain. 2. Tentukan langkah-langkah yang dapat dilakukan sesuai algoritma backward induction. 3. Tentukan jumlah batu yang dapat diambil oleh pemain pertama yang melangkah pertama kali dan jumlah batu yang dapat diambil oleh setiap pemain pada langkah selanjutnya. 4. Jika jumlah keping yang diambil lebih besar sama dengan dari jumlah keping, maka nilai SpragueGrundy sama dengan nilai follower pada saat langkah ke-i.
4 5.
Jika jumlah batu yang diambil lebih kecil sama dengan dari langkah ke-i, maka: a. Jika array yang menyimpan semua nilai Sprague-Grundy ada nilainya, maka langsung diisikan nilai ke-i tersebut. b. Jika array yang menyimpan semua nilai Sprague-Grundy belum ada nilainya, maka proses recursive akan dilakukan.
C. Menentukan Banyaknya KepingYang Menyebabkan Pemain Kedua Memenangkan Permainan. Dalam permainan Special Nim Game, yang diharapkan memenangkan permainan adalah pemain kedua, dimana memiliki nilai Sprague-Grundy 0 (nol). Mudah untuk menganalisis grafik fungsi Sprague-Grundy pada permainan. Posisi x untuk g(x) = 0 adalah posisi menang dan semua posisi lainnya adalah kalah. Prosedur yang menang adalah memilih langkah terakhir yang pindah ke titik dengan nilai SpragueGrundy 0 (nol). Adapun algoritmanya sebagai berikut: 1. Tentukan langkah-langkah yang bisa dilakukan sesuai algoritma backward induction. 2. Tentukan nilai Sprague-Grundy sesuai algoritma untuk mendapatkan nilai Sprague-Grundy. 3. Temukan jumlah N yang memiliki nilai SpragueGrundy nol (0). a. Jika pada langkah 1 dan 2 ditemukan jumlah keping yang memiliki nilai Sprague-Grundy 0, maka pemain pertama dapat memenangkan permainan dan pengecekan tumpukan keping tersebut tidak dilanjutkan. b. Jika pada langkah 1 dan 2 tidak ditemukan jumlah keping yang memiliki nilai SpragueGrundy 0, maka apapun yang pemain pertama lakukan, pemain kedua pasti tetap memenangkan permainan. III. IMPLEMENTASI Untuk menyelesaikan Special Nim Game, digunakan metode Sprague-Grundy. Dimana akan dilakukan analisa permainan dari akhir dan kembali ke awal, yang disebut dengan metode induksi mundur (backward induction). Kemudian tentukan nilai Sprague-Grundy dari setiap N. Dan pada tahap akhir, menentukan jumlah N yang pemain kedua memenangkan permainan.
Gambar 4. Diagram Alir Garis Besar Sistem.
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2012) 1-6 Pada proses backward induction ini dibutuhkan inputan jumlah keping dan jumlah keping - 1. Berikut adalah kode pemrograman untuk menentunkan langkah-langkah yang dapat ditempuh untuk setiap N. Table 4. Source Code Proses Backward Induction 1
int *generateState(int nInput,int maxValue)
2
{
5
24
mexValue[i]=getMexValue(state[i],nextTakenSton e);
25
arrValDataMex[state[i]][nextTakenStone]=mexVal ue[i];
26 27
}
38
if (mexValue[i]==0)
29
{
3
int *ret=new int[maxValue];
4
int ctr=1;
5
for (int i=maxValue-1;i>=0;i--)
30
6
{
31
7
ret[i]=nInput-ctr;
8
ctr++;
9
}
retValue=stone-state[i]; }
32
}
33
i++;
}
10
return ret;
11
}
Pada proses mencari Sprague-Grundy value dibutuhkan inputan jumlah keping dan jumlah maksimal keping yang dapat diambil oleh pemain. Berikut adalah kode pemrograman untuk mendapatkan Sprague-Grundy value. Table 5. Source Code Untuk Mendapatkan Nilai Sprague-Grundy. 1
int getMexValue(int stone,int maxTakenStone)
2
{
3
int *state=generateState(stone,maxTakenStone);
34
}
35
delete [] state;
36
delete [] mexValue;
37
return retValue;
38
}
Pada proses menentukan jumlah N yang menyebabkan pemain kedua memenangkan permainan dibutuhkan inputan jumlah keping awal dan jumlah keping akhir. Dari masingmasing tumpukan akan digenerate setiap langkah-langkah dan akan dicek apakah ada nilai Sprague-Grundy 0 (nol). Berikut adalah kode pemrograman untuk menentukan pemenang.
4
int *mexValue=new int[maxTakenStone];
5
int retValue=0;
6
int i=0;
1
//cDataMex
7
while (i<maxTakenStone && retValue==0)
2
for (int i=nAwal;i<=nAkhir;i++)
8
{
3
{
9 10 11
Table 6. Source Code Untuk Menentukan Jumlah N yang Menyebabkan Pemain Kedua Menang.
if (maxTakenStone<stone)
5
int *state=generateState(i,i-1);
{
8
int newStateLength=i-1;
9
bool foundZero=false;
int takenStone=stone-state[i];
12
int nextTakenStone=2*takenStone;
10
13
if (nextTakenStone>=state[i])
11
14
{
12
15 16 17
18 19
mexValue[i]=state[i]; }
13 14
else { if (arrValDataMex[state[i]][nextTakenStone] !=-1)
15
while (!foundZero && j
17
if (nextTakenStone<state[j])
18
{
{ 19
20
int j=0;
mexValue[i]=arrValDataMex[state[i]][nextTakenS tone]; 20
21
}
22
else
23
{
21
22
int mexValue=0; if (arrValDataMex[state[j]][nextTakenStone]!= -1) { mexValue=arrValDataMex[state[j]][nextTaken Stone];
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2012) 1-6
23
}
24
Else
25
{
26
mexValue=getMexValue(state[j],nextTakenSto ne);
28
arrValDataMex[state[j]][nextTakenStone]=me xValue;
29
}
30
if (mexValue==0)
31
{
32
33
foundZero=true; gfile<<"jumlah tumpukan batu :" << i << ", Sprague-Grundy valuenya adalah : " << (i-state[j])<<endl;
35
}
37
}
38
else {
40
}
41
j++;
42
}
43
if (!foundZero)
44
{
45
gfile<<"jumlah tumpukan batu :" << i << ", Sprague-Grundy valuenya adalah : 0"<<endl;
46
myfile<
6
Gambar 5. Hasil Nilai Sprague-Grundy N=2 sampai N=25.
V. KESIMPULAN Dari hasil analisa program dapat diambil beberapa kesimpulan: 1. Sistem yang dibuat memungkinkan manusia untuk bermain Nim Game dengan menggunakan komputer dan dapat menentukan langkah-langkah yang optimal agar dapat memenangkan permainan dengan menggunakan metode backward induction. 2. Nilai Sprague-Grundy dapat ditemukan dengan menggunakan teorema Sprague-Grundy, dimana nilai Sprague-Grundy adalah 0 (nol). Pencarian nilai Sprague-Grundy dilakukan secara rekursif sampai batas yang paling bawah atau pada saat jumlah maksimal keping yang dapat diambil lebih besar daripada jumlah keping. 3. Jumlah N keberapa yang pemain kedua memenangkan permainan dapat ditemukan dengan cara digenerate setiap langkah. Dan untuk masing-masing langkah akan dicek apakah nilai Sprague-Grundynya adalah 0 (nol). Dari tumpukan 2 keping sampai 2000 keping, ditemukan 15 nilai N yang dimenangkan oleh pemain kedua.
47
}
48
ofstream myfile2;
49
myfile2.open ("debug.txt");
50
myfile2<
51
myfile2.close();
UCAPAN TERIMA KASIH
52
delete [] state;
53
cout<<"process :"<
Penulis mengucapkan terima kasih kepada Bapak dan Ibu yang selalu memberikan do’a restu, Bapak Yudhi Purwananto, S.Kom, M.Kom. dan Bapak Rully Soelaiman, S.Kom., M.Kom. atas bimbingan yang diberikan selama penyusunan Tugas Akhir.
54
}
IV. UJI COBA Data uji coba pada studi kasus Special Nim Game yang yang ada pada Sphere Online Judge problem set tutorial 1238 ini hanya jumlah tumpukan, yaitu 2 keping sampai 2000 keping. Setelah dilakukan analisa backward induction, nilai Sprague-Grundy, dan menentukan nilai N dimana pemain kedua yang memenangkan permainan, hasil Sprague-Grundy value masing-masing N ditampilkan dalam bentuk SpragueGrundyValue.txt. Sedangkan untuk hasil N keberapa yang memenangkan permainan dimana Sprague-Grundy value adalah 0 (nol) ditampilkan dalam bentuk result.txt. Nilai Sprague-Grundy adalah 0 akan diperoleh pada 15 jumlah keping N yang pemain kedua memenangkan permainan. Berikut adalah hasil yang diperoleh pada percobaan terhadap beberapa nilai, yaitu N=2 sampai N=25.
DAFTAR PUSTAKA [1]
Thomas S. Ferguson. Game Theory. Class note for Math 167, Fall 2000.
[2]
Game Theory and Algorithms, Lecture 19: Nim & Impartial Combinatorial Games. May 17, 2011.
