Selasa, 13 November 2012

Ilmu Round-robin

Ada banyak sistem turnamen yang digunakan. Sistem gugur/knockout/single elimination/suddendeath adalah sistem yang cukup sering digunakan dalam banyak pertandingan olahraga. Seorang pemain yang telah kalah tidak dapat melanjutkan pertandingan ke babak berikutnya.

Berikut ini contoh diagram sistem gugur untuk 8 pemain.

Bila jumlah pemain sangat banyak sedangkan waktu pelaksanaan pertandingan sangat terbatas maka sistem ini bermanfaat untuk digunakan.
Pada diagram di atas tampak bahwa dari 8 pemain diperlukan 7 pertandingan untuk menentukan pemenang. Bila diperlukan juara 3 maka cukup diadakan satu pertandingan lagi sehingga banyak pertandingan seluruhnya hanya 8.

Ada kemungkinan pemain yang unggul kalah dalam babak awal, atau mungkin pada babak awal bertemu dua pemain yang tidak sebanding. Demikianlah di antara kurangan dalam sistem ini.

Untuk mengatasi hal tersebut dibentuklah sistem lain yang lebih mengacu pada poin yang diperoleh pemain, yaitu Round-robin Tournament atau biasa juga disebut All Play All Tournament.


Turnamen Round-robin
Turnamen Round-Robin adalah turnamen (pertandingan) di mana setiap pemain dipasangkan untuk melawan seluruh pemain lainnya pada tiap putarannya.

Jika tiap dua pemain bertanding satu kali maka disebut single round-robin, sedangkan jika bertanding dua kali maka disebut double round-robin. Sistem double jarang digunakan karena memerlukan waktu yang cukup lama. Sistem round-robin dengan 4 pemain kadang-kadang disebut quad.
Sebenarnya istilah round-robin berasal dari ruban (bahasa Perancis) yang berarti pita (ribbon), namun selama jangka waktu yang panjang istilah itu berubah bentuk menjadi robin.

Berikut ini contoh pemasangan (pairing) 8 pemain dalam single round-robin.
Round 1
Round 2
Round 3
Round 4
Round 5
Round 6
Round 7
1 – 7
2 – 6
3 – 5
4 – 8
1 – 8
2 – 7
3 – 6
4 – 5
1 – 2
3 – 7
4 – 6
5 – 8
1 – 3
2 – 8
4 – 7
5 – 6
1 – 4
2 – 3
5 – 7
6 – 8
1 – 5
2 – 4
3 – 8
6 – 7
1 – 6
2 – 5
3 – 4
7 – 8
Tabel 1. Round-robin dengan 8 pemain
Dalam sistem ini diupayakan agar babak (round) yang terjadi seminimum mungkin. Tampak bahwa untuk 8 pemain diperlukan hanya 7 babak dengan 4 pertandingan pada tiap babaknya. Jadi seluruhnya terdiri dari 28 pertandingan.


Pairing yang terbentuk tidak harus seperti di atas. Banyak kemungkinan untuk membuat pairing round-robin. Bagaimanakah cara membuat pairing round robin seperti di atas?


Cara Membuat Tabel pada Turnamen Round-robin

Bentuk tabel yang sederhana
Tabel 1 di atas yang terlihat panjang dapat disederhanakan sebagai berikut.
1
2
3
4
5
6
7
8
Round 1
7
6
5
8
3
2
1
4
Round 2
8
7
6
5
4
3
2
1
Round 3
2
1
7
6
8
4
3
5
Round 4
3
8
1
7
6
5
4
2
Round 5
4
3
2
1
7
8
5
6
Round 6
5
4
8
2
1
7
6
3
Round 7
6
5
4
3
2
1
8
7
Tabel 2. Bentuk lain Tabel 1


Pemain buatan/kosong (dummy)
Perlu diketahui bahwa jika banyak pemain berjumlah ganjil maka harus dibuat satu pemain dummy. Pemain yang dipasangkan dengan pemain dummy tidak bermain pada babak tersebut.
Berikut ini contoh tabel Round-robin untuk 7 pemain.
1
2
3
4
5
6
7
Round 1
7
6
5
bye
3
2
1
Round 2
bye
7
6
5
4
3
2
Round 3
2
1
7
6
bye
4
3
Round 4
3
bye
1
7
6
5
4
Round 5
4
3
2
1
7
bye
5
Round 6
5
4
bye
2
1
7
6
Round 7
6
5
4
3
2
1
bye
Tabel 3. Round-robin dengan 7 pemain
Tampak bahwa tabel untuk 7 pemain dibuat seperti tabel untuk 8 pemain dengan cara membuang kolom ke-8 dan setiap pemain yang akan bertanding melawan pemain dummy (nomor 8) diberi tanda "bye", sehingga pada babak tersebut dia tidak bermain. Misalnya, pada babak 4, pemain bernomor 2 tidak bermain.

Jadi banyak pemain harus berjumlah genap, sehingga jika ganjil maka harus ditambahkan pemain dummy pada saat menyusun pairing.

ALGORITMA FREUND(*)
Algoritma Freund berupa kekongruenan modulo yang dapat digunakan untuk menyusun pairing turnamen round-robin.

 Misalkan jumlah pemain sebanyak N dengan N genap. 
 Jika pada babak (round) ke-R, pemain bernomor i akan melawan pemain bernomor j maka 
 berlaku:
 i + j º R mod(N – 1)
 dengan syarat:
       1)      i ≠ j 
       2)     jika nilai j sudah digunakan pada petak dengan nilai i yang lebih kecil 
            maka kosongkan nilai j (agar tidak terjadi bentrok)
       3)    Jika terdapat 2 nilai j yang memenuhi maka pilihlah nilai j yang lebih kecil.
 (*) John E. Freund adalah anggota Mathematical Association of America (MAA) sejak 1949, penulis buku yang produktif, dan seorang pendidik yang bergairah. Dia meninggal dunia pada tanggal 14 Agustus 2004 dalam usia 83 tahun.
Berikut ini contoh penggunaan algoritma Freund untuk jumlah pemain N = 8 .
R \ i
1
2
3
4
5
6
7
8
Round 1
a

b
c



x
Round 2








Round 3
y
z






Round 4

m





n
Round 5








Round 6








Round 7








Tabel 4. Contoh penyusunan pairing dengan algoritma Freund
o   Untuk sel a diketahui R = 1 dan i = 1, maka 1 + j º 1 mod 7 sehingga yang memenuhi adalah j = 7.
o    Untuk sel b diketahui R = 1 dan i = 3, maka 3 + j º 1 mod 7 sehingga yang memenuhi adalah j = 5.
o    Untuk sel c diketahui R = 1 dan i = 4, maka 4 + j º 1 mod 7 sehingga yang memenuhi adalah j = 4.
Karena nilai i = j (berarti nomor pemain yang sama), maka kosongkan dulu sel c ini.
o    Untuk sel x diketahui R = 1 dan i = 8, maka 8 + j º 1 mod 7 sehingga yang memenuhi adalah j = 7.
Karena nilai j = 7 sudah digunakan pada sel a, maka kosongkan dulu sel x ini.
o    Untuk sel y diketahui R = 3 dan i = 1, maka 1 + j º 3 mod 7 sehingga yang memenuhi adalah j = 2.
o    Untuk sel z diketahui R = 3 dan i = 2, maka 2 + j º 3 mod 7 sehingga yang memenuhi adalah j = 1 dan j = 8. Dalam hal ini dipilih yang lebih kecil, yaitu j = 1.
o    Untuk sel m diketahui R = 4 dan i = 2, maka 2 + j º 4 mod 7 sehingga yang memenuhi adalah j = 2.
Karena nilai i = j (berarti nomor pemain yang sama), maka kosongkan dulu sel m ini.
o    Untuk sel n diketahui R = 4 dan i = 8, maka 8 + j º 4 mod 7 sehingga yang memenuhi adalah j = 3.
o   demikian seterusnya.
R \ i
1
2
3
4
5
6
7
8
Round 1
7

5





Round 2








Round 3
2
1






Round 4







3
Round 5








Round 6








Round 7








Tabel 5. Contoh penyusunan pairing dengan algoritma Freund

Bila sel-sel telah diisi sesuai dengan persyaratan dalam algoritma Freund, maka sel-sel lainnya yang masih kosong diisi dengan cara mengatur nomor-nomor para pemain yang belum terpasangkan.
Misalnya, pada babak 1, pemain bernomor 4 dan 8 keduanya belum terpasangkan, maka dapat dibuat 4 melawan 8 dan 8 melawan 4. 
ROTASI
Cara lain yang digunakan untuk menyusun pairing turnamen Round-Robin adalah dengan pemutaran (rotasi) nomor pemain.
Langkah pertama, buatlah (sembarang) pairing untuk babak (round) 1.  
Sebagai contoh, untuk 8 pemain, babak 1 disusun sebagai berikut.
Round 1
1 – 5
2 – 6
3 – 7
4 – 8

Untuk babak 2, dengan menganggap pemain bernomor 1 sebagai titik pusat rotasi, rotasikan pemain lainnya sebagai berikut.
sehingga diperoleh:
Round 2
1 – 2
3 – 5
4 – 6
8 – 7


Penyusunan pairing untuk babak-babak selanjutnya dilakukan dengan cara seperti itu, hasilnya akan tampak seperti dalam tabel di bawah ini.
Round 1
1 – 5
2 – 6
3 – 7
4 – 8
Round 5
1 – 8
7 – 4
6 – 3
5 – 2
Round 2
1 – 2
3 – 5
4 – 6
8 – 7
Round 6
1 – 7
6 – 8
5 – 4
2 – 3
Round 3
1 – 3
4 – 2
8 – 5
7 – 6
Round 7
1 – 6
5 – 7
2 – 8
3 – 4
Round 4
1 – 4
8 – 3
7 – 2
6 – 5

Tabel 6. Contoh penyusunan pairing dengan rotasi
Silakan bandingkan cara rotasi dengan cara Freund, manakah yang lebih mudah dan lebih cepat?

Pengaturan “Putih“ dan “Hitam”
Pekerjaan menyusun pairing di atas belumlah selesai karena ada satu tahap lagi yang harus dilakukan, yaitu mengatur buah Putih dan Hitam yang akan dipegang para pemain agar terjadi proporsi yang seimbang. Warna buah yang dipegang pemain secara signifikan akan mempengaruhi perencanaan dan permainan yang terjadi.

Agar pengaturan warna buah ini tidak terlalu lama maka digunakan patokan berikut ini.
Untuk pemain bernomor i melawan pemain bernomor j berlaku:
o   Jika i + j ganjil maka pemain bernomor lebih kecil memegang buah Putih.
o   Jika i + j genap maka pemain bernomor lebih besar memegang buah Putih.

Sebagai contoh, perhatikan tabel 6 di atas.
Pada babak 1, tampak 2 – 6. Karena 2 + 6 genap maka haruslah pemain bernomor 6 memegang buah Putih, sehingga susunan itu harus diganti menjadi 6 – 2.
Pada babak 2, tampak 8 – 7. Karena 8 + 7 ganjil maka haruslah pemain bernomor 7 memegang buah Putih, sehingga susunan itu harus diganti menjadi 7 – 8.
Pada babak 6, tampak 2 – 3. Karena 2 + 3 ganjil maka haruslah pemain bernomor 2 memegang buah Putih, sehingga susunan itu sudah benar.

Dengan demikian hasil pairing berdasarkan table 6 adalah sebagai berikut.
Round 1
5 – 1
6 – 2
7 – 3
8 – 4
Round 5
1 – 8
4 – 7
3 – 6
2 – 5
Round 2
1 – 2
5 – 3
6 – 4
7 – 8
Round 6
7 – 1
8 – 6
4 – 5
2 – 3
Round 3
3 – 1
4 – 2
5 – 8
6 – 7
Round 7
1 – 6
7 – 5
8 – 2
3 – 4
Round 4
1 – 4
3 – 8
2 – 7
5 – 6



Penutup
Demikianlah sistem Round-robin yang sering digunakan dalam pertandingan dan kemudian seringkali digabungkan dengan sistem gugur menjelang babak-babak akhir pertandingan.

Bila kita ingin membuat pairing untuk turnamen Round-robin tanpa direpotkan dalam penyusunannya, maka kita dapat memilih layanan pada internet yang menyediakan perangkat untuk keperluan tersebut. Salah satunya (yang gratis) adalah dari teampolis.

Sumber:
Everything About Math 
MathematicalAssociation of America 
Wikipedia 
Teampolis 

-->
Posted by at
Labels: ,

2 komentar:

Langganan: Posting Komentar (Atom)
155733_AbeBooks Logo
Related Posts Plugin for WordPress, Blogger...