What's the content of this blog

Composition: Mathematics, my favourite lesson 90%. Mathematics Software 3%, My Life and Experience 3%, and Others 4%..
-- Here we can share knowledge --
-- Enjoy --

Sunday, June 7, 2009

Round-Robin Tournament

Pernahkah kalian memperhatikan sistem tournament yang digunakan dalam berbagai pertandingan olahraga, catur, ataupun tournament yang lain?

Ada banyak sekali sistem tournament yang ada. Sistem gugur / knockout / single elimination/ cup/ suddendeath adalah sistem yang sering kita jumpai di banyak pertandingan olahraga.. Sekali kalah, maka pemain tidak bisa lanjut ke bebak berikutnya. Di bawah ini diberikan contoh sistem gugur untuk 8 pemain, dari A hingga H.

Kelebihan sistem ini adalah dapat mengeliminasi jumlah pemain yang sangat banyak dan pertandingan yang dilangsungkan seminimal mungkin. Terlihat di atas bahwa jumlah pertandingan untuk menentukan 1 pemenang dari 8 pemain adalah 7 pertandingan. Jika kita ingin menentukan juara 2 dan juara 3, maka cukup diadakan satu pertandingan tambahan, sehingga total pertandingannya cukup 8 saja.

Ada kekurangan di dalam sistem ini, karena pemain-pemain yang unggul bisa saja kalah di babak-babak awal, atau mungkin di babak awal bertemu dengan pemain yang sangat kuat (tidak sebanding) sehingga digunakan sistem lain, yaitu sistem poin, atau biasa disebut dengan "Round-Robin Tournament" atau "All Play All Tournament". Untuk lebih jelasnya mengenai sistem ini, baca di bawah.

=========================================================================
ROUND-ROBIN TOURNAMENT

Round-Robin Tournament merupakan sistem tournament di mana setiap pemain akan bertanding melawan setiap pemain lainnya. Jika masing-masing melawan sekali, dinamakan "single round-robin", sedangkan jika melawannya dua kali, maka dinamakan "double round-robin". Sistem double sendiri jarang digunakan, karena memakan waktu.

Sistem round-robin dengan 4 pemain sering disebut juga "quad".
Istilah round-robin sendiri diturunkan dari bahasa Perancis "ruban", yang berarti "ribbon", namun entah mengapa istilah itu sekarang berubah menjadi Robin, yang sesungguhnya tidak ada sangkut pautnya dengan Robin Hood.

Di bawah diberikan contoh jadwal Single Round-robin dengan 8 team:
Round 1

Team 1 vs Team 7
Team 2 vs Team 6
Team 3 vs Team 5
Team 4 vs Team 8
Round 2
Team 1 vs Team 8
Team 2 vs Team 7
Team 3 vs Team 6
Team 4 vs Team 5
Round 3
Team 1 vs Team 2
Team 3 vs Team 7
Team 4 vs Team 6
Team 5 vs Team 8
Round 4
Team 1 vs Team 3
Team 2 vs Team 8
Team 4 vs Team 7
Team 5 vs Team 6
____
Round 5 Team 1 vs Team 4
Team 2 vs Team 3
Team 5 vs Team 7
Team 6 vs Team 8
Round 6 Team 1 vs Team 5
Team 2 vs Team 4
Team 3 vs Team 8
Team 6 vs Team 7
Round 7
Team 1 vs Team 6
Team 2 vs Team 5
Team 3 vs Team 4
Team 7 vs Team 8
Tabel Round-Robin dengan 8 team (tabel 1)

Sistem ini mengusahakan agar round yang digunakan adalah seminimum mungkin. Terlihat bahwa jika ada 8 team, maka round yang dibutuhkan cukup 7 round di mana setiap round-nya terdapat 4 pertandingan. Jadi, total pertandingannya adalah 28.

Jadwal pertandingan tidak harus seperti di atas. Ada banyak sekali kemungkinan untuk membuat jadwal round-robin. Pertanyaannya adalah bagaimanakah cara membuat jadwal round robin seperti di atas? Berikut dibahas di bawah.

=========================================================================
CARA MEMBUAT JADWAL ROUND-ROBIN TOURNAMENT

FORMAT TABEL YANG LEBIH SEDERHANA

Perhatikan contoh tabel 1 di atas. Jika tabel di atas terlihat lebih panjang, maka berikut akan diberikan tabel yang lebih sederhana dan singkat:

12345678
Round 1 7658
3214
Round 2 87654321
Round 3 21768
435
Round 4 38
176542
Round 5 432178
56
Round 6 548
2176
3
Round 7 65432187
Bentuk lain tabel 1 (tabel 2)

Untuk berikutnya, di bawah, kita akan menggunakan format tabel yang seperti di atas.

PENGENALAN TERHADAP KELOMPOK DUMMY
Sebelum melangkah lebih jauh, perlu kita ketahui bahwa jika jumlah pemainnya ganjil (misalnya 7 team) maka kita harus membuat sebuah kelompok dummy (misalnya kelompok ke-8). Jika ada kelompok yang bertemu dengan kelompok dummy tersebut, artinya team tersebut tidak bermain pada round tersebut..

Berikut diberikan contoh tabel Round-Robin untuk 7 pemain:

1234567
Round 1 765bye321
Round 2 bye765432
Round 3 2176bye43
Round 4 3bye17654
Round 5 43217bye5
Round 6 54bye2176
Round 7 654321bye
Tabel Round-robin dengan 7 pemain (tabel 3)

Perhatikan bahwa tabel dengan 7 pemain ini tidak berbeda jauh dengan tabel dengan 8 pemain. Bedanya, hanya kolom ke-8 yang dibuang, dan setiap pemain yang bertanding melawan kelompok 8 (sebagai dummy) diberi tanda "bye", yang artinya di round tersebut dia tidak bermain.. Misalnya, di round 4, team 2 diberi tanda "bye". Artinya, di round 4 ini, team 2 tidak bertanding.

Jadi, kita harus selalu membentuk kelompok dummy jika kita ingin menyusun jadwal dengan jumlah pemain ganjil. Misalkan, jika jumlah kelompoknya ada 5, kita tambahkan 1 kelompok dummy (yang dilabelkan dengan kelompok "6"), sehingga jumlahnya menjadi genap.

MENGGUNAKAN KONGRUENSI MODULO UNTUK MENYUSUN ROUND-ROBIN
Cara ini dikembangkan oleh Freund. Di sini, kita tidak akan membahas bukti, karena sesungguhnya buktinya hanyalah logika biasa. Jadi, kita akan langsung membahas algoritma Freund ini.
ALGORITMA FREUND:
Diketahui bahwa jumlah team yang ikut serta adalah sebanyak N, dimana N adalah genap. Pada Round ke-R, team i akan melawan team j, maka berlaku ketentuan sebagai berikut:

Ketentuan di atas selalu berlaku KECUALI jika i = j (karena tidak mungkin ada team yang melawan dirinya sendiri) atau jika ada j yang sudah dipakai di petak dengan i lebih kecil (sebelumnya) (agar tidak terjadi bentrok). Jika ketentuan ini dilanggar, kosongkan dulu nilai j.

Ketentuan yang lain: Jika ternyata terdapat 2 nilai j yang memenuhi, maka ambillah nilai j yang lebih kecil.

Kita akan langsung menggunakan contoh dimana jumlah pemain (N) = 8. Dengan menggunakan algoritma Freund, kita dapatkan tabel setengah jadi (abaikan warnanya) sebagai berikut:
R\ i
12345678
Round 1 765
321
Round 2 87654321
Round 3 2176
43
Round 4 3
17654
Round 5 43217
5
Round 6 54
2176
Round 7 65432187
Tabel setegah jadi dari Algoritma Freund (tabel 4)
Note: warna hanya sebagai pelengkap penjelasan di bawah.

Berikut penjelasan darimana angka-angka itu didapat (tapi hanya dibahas sebagian):
*) Lihat kotak dengan angka 7:
R = 1, dan i =1, maka (1+j) = 1 mod (7).
Nilai j yang memenuhi adalah 7.
*) Lihat kotak dengan angka 5:
R = 1, dan i =3, maka (3+j) = 1 mod (7).
Nilai j yang memenuhi adalah 5.
*) Lihat kotak kosong dengan background ungu:
R=1, dan i=4, maka (4+j) = 1 mod (7).
Nilai j yang memenuhi adalah 4.
Namun, karena i = j, maka kotak ini harus dikosongkan dahulu.
*) Lihat kotak kosong dengan background merah:
R=1, i =8, maka (8+j) = 1 mod (7).
Nilai j yang memenuhi adalah 7.
Namun, karena 7 sudah dipakai di petak sebelumnya (R=1, i=1), maka 7 tidak dapat digunakan lagi, maka kosongkan dulu petak ini.
*) Lihat kotak dengan angka 2:
R = 3, dan i =1, maka (1+j) = 3 mod (7).
Nilai j yang memenuhi adalah 2.
*) Lihat kotak dengan angka 1:
R = 3, dan i =2, maka (2+j) = 3 mod (7).
Nilai j yang memenuhi adalah 1 dan 8.
Pilih yang terkecil, yaitu 1.
*) Lihat kotak kosong dengan background kuning:
R=4, i =2, maka (2+j) = 4 mod (7).
Nilai j yang memenuhi adalah 2.
Namun, karena i = j, maka kosongkan dulu petak ini.
*) Lihat kotak kosong dengan background hijau:
R=4, i=8, maka (8+j) = 4 mod (7).
Nilai j yang memenuhi adalah 3.
Namun, karena 3 sudah dipakai sebelumnya (R=4, i=1), maka kosongkan dulu petak ini.

Untuk petak -petak yang lain, caranya sama seperti contoh-contoh di atas....
Nah, setelah tabel setengah jadi di atas selesai, kita tinggal mengisi kotak-kotak yang masih kosong dengan nilai yang mungkin. Misalnya, karena di round 1, team 4 dan team 8 keduanya masih kosong, maka 4 akan melawan 8, dan 8 akan melawan 4. Cara yang sama juga kita lakukan untuk kotak kosong yang lain.

12345678
Round 1 7658
3214
Round 2 87654321
Round 3 21768
435
Round 4 38
176542
Round 5 432178
56
Round 6 548
2176
3
Round 7 65432187
Tabel hasil akhir algoritma Freund (tabel 5)
Hasil dari tabel ini sama persis seperti tabel 2.
Mudah sekali kan menyusun jadwal Round-Robin.. ^^

MENGGUNAKAN ROTASI UNTUK MENYUSUN ROUND-ROBIN
Selain cara Freund, ada cara lain yang digunakan untuk menyusun jadwal Round-Robin, yaitu dengan rotasi. Rotasi merupakan cara yang sangat mudah. Pertama-tama, kita buat dulu 1 round, dengan gamenya sesuka hati kita.. ^^.. Misalkan, ada 8 team dan Round 1 adalah sebagai berikut:
Round 1 Team 1 vs Team 5
Team 2 vs Team 6
Team 3 vs Team 7
Team 4 vs Team 8
Kemudian, dengan membuat Team 1 tak bergerak, kita rotasikan team yang lain untuk menciptakan round kedua. Berikut adalah gambaran cara merotasikannya:

Maka, kita dapatkan round 2 sebagai berikut:
Round 2 Team 1 vs Team 2
Team 3 vs Team 5
Team 4 vs Team 6
Team 8 vs Team 7
Dengan cara yang sama, round yang lain dapat dibentuk. Hasilnya seperti tabel di bawah.
Round 1

Team 1 vs Team 5
Team 2 vs Team 6
Team 3 vs Team 7
Team 4 vs Team 8
Round 2
Team 1 vs Team 2
Team 3 vs Team 5
Team 4 vs Team 6
Team 8 vs Team 7
Round 3
Team 1 vs Team 3
Team 4 vs Team 2
Team 8 vs Team 5
Team 7 vs Team 6
Round 4
Team 1 vs Team 4
Team 8 vs Team 3
Team 7 vs Team 2
Team 6 vs Team 5
____
Round 5 Team 1 vs Team 8
Team 7 vs Team 4
Team 6 vs Team 3
Team 5 vs Team 2
Round 6 Team 1 vs Team 7
Team 6 vs Team 8
Team 5 vs Team 4
Team 2 vs Team 3
Round 7
Team 1 vs Team 6
Team 5 vs Team 7
Team 2 vs Team 8
Team 3 vs Team 4
Tabel Round-Robin menggunakan rotasi (tabel 6)

Cara rotasi ini memiliki keuntungan lebih dibandingkan cara Freund, karena lebih fleksibel (tergantung inisialisasinya), juga lebih mudah dan lebih cepat dibuat.. ^^

PEMILIHAN HOME DAN AWAY
Ada sedikit kekurangan yang ada dalam penyusunan jadwal Round-Robin di atas, yaitu masalah Home dan Away.

Misalkan ada kata-kata: "Team 1 vs Team 8", maka di sini Team 1 adalah Home (karena terletak sebelum vs) dan Team 8 adalah Away (karena terletak setelah vs). Terlihat bahwa dalam tabel 1 di atas, Team 8 selalu mendapat Away, sedangkan team 1 selalu mendapat Home. Pastinya, dalam kehidupan nyata, hal ini harus dihindari agar Team 8-nya tidak protes.. Oleh karena itu, sebaiknya kita membuat suatu sistem jadwal sehingga setiap team mendapat jatah Home dan Away yang sama.

Sebetulnya, kita dapat menggunakan cara manual, namun terlalu lama, maka kita gunakan cara di bawah:
Diketahui "Team i vs Team j".
Jika i+j ganjil, Home ditempati oleh i atau j yang lebih kecil.
Jika i+j genap, Home ditempati oleh i atau j yang lebih besar.
Sebagai contoh:
"Team 2 vs Team 8". Karena 2+8 genap, maka posisi Home ditempati oleh Team yang lebih besar, yaitu 8. Maka, sekarang berubah menjadi "Team 8 vs Team 2".
"Team 1 vs Team 5". Karena 1+5 adalah ganjil, maka Home ditempati oleh Team yang lebih kecil. Maka, tidak ada perubahan.

Jika kita memodifikasi tabel 1 dengan pemilihan Home dan Away ini, maka hasilnya menjadi seperti berikut:
Round 1

Team 7 vs Team 1
Team 6 vs Team 2
Team 5 vs Team 3
Team 8 vs Team 4
Round 2
Team 1 vs Team 8
Team 2 vs Team 7
Team 3 vs Team 6
Team 4 vs Team 5
Round 3
Team 1 vs Team 2
Team 7 vs Team 3
Team 6 vs Team 4
Team 5 vs Team 8
Round 4
Team 3 vs Team 1
Team 8 vs Team 2
Team 4 vs Team 7
Team 5 vs Team 6
____
Round 5 Team 1 vs Team 4
Team 2 vs Team 3
Team 7 vs Team 5
Team 8 vs Team 6
Round 6 Team 5 vs Team 1
Team 4 vs Team 2
Team 3 vs Team 8
Team 6 vs Team 7
Round 7
Team 1 vs Team 6
Team 2 vs Team 5
Team 3 vs Team 4
Team 7 vs Team 8
Tabel 1 yang dimodifikasi home dan away-nya (tabel 7)

Kita perlu waktu cukup lama untuk menentukan home dan away dari tabel 1, namun khusus untuk yang cara rotasi, kita tidak perlu menggunakan teori-teori seperti di atas. Perhatikan bahwa team yang berotasi akan menjadi home dan away secara bergilir. Artinya, yang perlu diperbaiki home dan away-nya hanyalah team yang tidak berotasi. Pada kasus tabel 6, artinya, kita cukup memperbaiki Home dan Away dari pertandingan Team 1.

Berikut hasil modifikasi home dan away terhadap tabel 6:
Round 1

Team 1 vs Team 5
Team 2 vs Team 6
Team 3 vs Team 7
Team 4 vs Team 8
Round 2
Team 1 vs Team 2
Team 3 vs Team 5
Team 4 vs Team 6
Team 8 vs Team 7
Round 3
Team 1 vs Team 3
Team 4 vs Team 2
Team 8 vs Team 5
Team 7 vs Team 6
Round 4
Team 1 vs Team 4
Team 8 vs Team 3
Team 7 vs Team 2
Team 6 vs Team 5
____
Round 5 Team 8 vs Team 1
Team 7 vs Team 4
Team 6 vs Team 3
Team 5 vs Team 2
Round 6 Team 7 vs Team 1
Team 6 vs Team 8
Team 5 vs Team 4
Team 2 vs Team 3
Round 7
Team 6 vs Team 1
Team 5 vs Team 7
Team 2 vs Team 8
Team 3 vs Team 4
Tabel 6 yang diperbaiki home dan away-nya (tabel 8)
Kita cukup memperhatikan bagian yang berwarna merah. Dari 7 round yang ada, kita cukup membalikkan 3 atau 4 buah. Itupun sesuka hati kita.. Di sini, cara rotasi benar-benar memberikan keuntungan yang luar biasa. ^^

=========================================================================
CLOSING
Round-Robin Tournament merupakan sistem yang sering digunakan dalam suatu pertandingan. Namun, seringkali sistem ini digabung dengan sistem gugur. Sebagai contoh, lomba atletik, badminton, sepakbola, ataupun catur semuanya menggunakan sistem Round-Robin Tournament di babak seleksi (yang dilakukan antar grup team atau wilayah). Setelah terkumpul sekitar 8 atau 16 team, barulah digunakan sistem gugur.

Sebetulnya, ada lagi 1 cara untuk menyusun jadwal Round Robin, bahkan sama sekali tidak perlu menghitung. Cara ini juga dilakukan dalam sekejap.!! Silakan gunakan free generator yang tersedia di http://www.teamopolis.com/tools/round-robin-generator.aspx. Weks.. Pasti kalian berpikir: "Aduuuu.. Saya udah belajar capek-capek, ternyata ada tool beginian"... Hahahaha.. Yang penting, kalian mau mencoba belajar dan tahu seluk-beluk Round-Robin, kemudian barulah menggunakannya.. Tul, gak? ^^

N, saya sarankan agar tabel di atas dibau sendiri agar kalian dapat berlatih. Melihat saja tidak akan cukup.

0 comments:

Post a Comment