Algoritmi täyskierrosturnauksen paritukseen#

Ihanteellisessa yksinkertaisessa täyskierrosturnauksessa seuraavat ehdot toteutuvat:

• jokainen pelaa jokaista vastaan, mutta vain kerran
• jokainen pelaa yhtä monta tai melkein yhtä monta peliä mustilla ja valkeilla
• pelattu väri vaihtuu joka kierroksella
• jokainen pelaa joka kierroksella, ts. vapaakierroksia ei ole

Nämä kaikki eivät voi toteutua täydellisesti yhtä aikaa ei-triviaalissa tapauksessa. Todistus jää harjoitustehtäväksi ahkerille lukijoille.

Esitetään algoritmi parituksen muodostamiseen, joka takaa parituksen, joka on melkein yo. ehtojen mukainen.

Olkoon pelaajia parillinen määrä. Heihin viitataan jatkossa numeroilla 1,...,n, missä n on parillinen. Koska jokainen pelaa pelin kaikkia paitsi itseään vastaan, on tällöin turnauksessa vähintään n-1 kierrosta. Jos jokaiselle kierrokselle jokaiselle pelaajalle löytyy sopiva vastustaja, riittää n-1 kierrosta, eikä useampia tarvita.

Kuvataan kierrosta ja sen paritusta (n/2)x2-matriisilla, jonka alkioina ovat pelaajia vastaavat luvut. Samalla sarakkeella olevat pelaajat pelaavat pelin keskenään. Olkoon ensimmäisen kierroksen paritus seuraava:

Valitaan lisäksi peleissä värit siten, että ylärivissä parittomilla luvuilla pelaavilla on mustat ja parillisilla valkeat.

Kaikki muiden kierrosten k, k=2,3,...,n-1, saadaan induktiivisesti edellisen kierroksen parituksesta seuraavalla tavalla:

Matriisissa (1,1)-alkio, eli pelaaja 1, säilyy aina samana. Muita kierretään yksi askel myötäpäivään sillä tavalla, että ylärivillä jokainen alkio siirtyy yhden paikan oikealla, paitsi rivin viimeinen, joka siirtyy alemman rivin oikeanpuoleisimmaksi alkioksi. Alarivin alkioita siirretään yksi askel vasemmalla, paitsi vasemmanpuoleisinta alkiota, joka siirretään pelaajan 1 oikealle puolelle. Siis vain pelaajan 1 suhteellinen asema muihin pelaajin nähden muuttuu, koska hän on ainoa joka pysyy paikallaan.

Pelaaja 1 pelaa mustilla parittomilla kierroksilla ja valkeilla parillisilla kierroksilla. Muissa pareissa pelataan aina samoilla väreillä kuin samassa paikassa pelattiin ensimmäisellä kierroksella.

Menetelmä päättyy kun on paritettu n-1 kierrosta.

Jos pelaajia on pariton määrä, kutsutaan mukaan Byen veljeksistä vanhin, joka senioriteettinsä nojalla pelaa pelaajana yksi. Peli häntä vastaan tulkitaan vapaakierrokseksi.

Esimerkki. Olkoon paritettavana kuuden pelaajan täyskierrosturnaus. Esitetään seuraavassa matriisit kierroksille 1-5, missä lihavoidut numerot tarkoittavat mustalla pelaamista:

Kierros 1

Kierros 2

Kierros 3

Kierros 4

Kierros 5

Perustelu menetelmän toimivuudelle#

Selvästi jokaisella pelaajalla on vastus joka kierroksella. Todetaan siis, että yksikään pelaaja ei pelaa kahdesti samaa vastustajaa vastaan, sekä että värit jakautuvat niin, että kaikilla pelaajilla heidän mustilla ja valkeilla pelattujen peliensä erotuksen itseisarvo on 1. Tämä on parittomalla pelimäärällä parhain mahdollinen tulos.

Väite: Jokainen pelaaja pelaa jokaista vastaan kerran.

Todistus: Riittää osoittaa, että yksikään pelaaja ei pelaa kahdesti samaa pelaajaa vastaan. Tällöin väite seuraa kierrosten määrästä. Selvästi pelaaja 1 pelaa joka pelin eri vastustajaa vastaan.

Vastaoletus: eri pelaajat a ja b pelaavat kaksi peliä keskenään.

Jos näin tapahtuu, voidaan olettaa yleisesti, että ensimmäinen heidän keskeisistään peleistä tapahtuu niin, että pelaaja a on matriisin ylärivillä ja b vastaavalla sarakkeella alarivillä. Tällöin pelaajan a ja b välillä on parillinen määrä muita pelaajia, jotka on paritettu keskenään, kulkien matriisin yläriviä oikealla ja jatkaen alariviä vasemmalle oikeasta laidasta. Seuraavalla kierroksella a siirtyy oikealle matriisissa ja b vasemmalle, joten seuraavan kerran heidän kohdatessaan täytyy pelaajan b olla ylärivillä ja pelaajan a alarivillä. Nyt kuitenkin paritusten muodostussäännön nojalla pelaajien a ja b välillä (nyt matriisin vasemmalta puolelta lukien) ovat samat pelaajat, sekä vasemmalla oleva pelaaja 1. Koska tämä on pariton määrä, on mahdotonta, että pelaajat a ja b ovat samalla sarakkeella.

Lisäksi menettely loppuu n-1:n kierroksen jälkeen, joten toista mahdollisuutta alkukierroksen parituksen syntymiseen ei ole. Näin ollen vastaoletus on väärä ja väite on tosi. MOT

Väite: jokainen pelaa melkein yhtä monta peliä valkeilla ja mustilla (erotuksen itseisarvo 1)

Todistus: Pelaaja 1 pelaa joka toisen pelin mustilla ja joka toisen valkeille. Hän aloittaa mustilla, joten selvästi hän tulee pelaaman yhden pelin enemmän mustilla kuin valkeilla. Muut pelaajat pelaavat kerran jokaisella paikalla paitsi (1,1)-alkion kohdalla. Muissa paikoissa kuin pelaajaa 1 vastaan pelaamisväri ei muutu eri kierroksilla, joten he pelaavat näissä paikoissa yhteensä yhtä monta peliä valkeilla ja mustilla. Pelaajaa yksi vastaan pelattu väri määrää kumpaa väriä he pelaavat yhden pelin enemmän. MOT

Menetelmää voidaan soveltaa yhden illan pikapeliturnauksissa ihan lennossa, jos jokainen vain muistaa edellisen kierroksen istumapaikkansa ja kierroksen numeron. Muuten menetelmän avulla voidaan määrätä paritus ja pelattava väri jokaiselle kierroksella ja sitten arpoa kuka osallistujista pelaa milläkin luvulla.

Kommentit ovat tervetulleita. Kirjoita alle nimesi jos kommentoit asiaa laajemmin. Sivun voisi linkittää muualtakin kun Oulun turnaussivulta, jos se ansaitsee pysyvän elämän wikissä.

(pikkuedittejä: luku vai numero? kuka sen tietää...)

Pekka Karjalainen, 24.10.2004

Varsin tuttu ja toimivaksi todettu algoritmi - myös GO-turnamenteissa ; tuota on käytetty mm. pikapeliturnausten "helppoon" paritukseen jo joskus 80 -luvulla. PS. aihe on aika-ajoin herättänyt keskustelua mm. webissä/newsseissä: esimerkkinä ( bonuksena havainnollistavia apletteja) : RoundRobin

Ari Karppinen , 24.10.2004

Kiitos osoitteesta. Sieltä löytyy myös "tables"-linkin takaa valmiita taulukoita, joista kiireisempi voi noutaa parituksen eri kokoisiin roundrobineihin. Värijakoa siellä ei ole ajateltu, tai en ainakaan huomannut äkkiä siitä mitään sanottavan. Se on toki mahdollista tehdä myös nigirillä jokaisen parin itse, riippuen ihan turnauksen järjestäjien päätöksestä.

--Pekka, 25.10.04

Shakissa on tietysti sama ongelma, ja värinvaihtelu jopa vielä tärkeämpää. Valmiita taulukoita, joissa tosin pelaajien numerointi noudattaa shakkiturnausten konventioita. Jos halutaan sama numerointi Pekan esittämällä ("kiertävällä") menetelmällä, alkutilanne on

ja pelaaja n pysyy paikallaan, muut kiertävät vastapäivään. (Toivottavasti meni oikein.) Värit menevät niin, että jos molemmat pelaajat ovat parillis- tai paritonnumeroisia, niin suurempinumeroisella on valkeat, muuten pienempinumeroisella (poikkeuksena pelaaja n, kun pelaajia on parillinen määrä). Taulukon muodostuminen ja värien määrääminen tulee havainnollisemmaksi, jos muodostaa n kertaa n -taulukon ja merkkaa, mitkä pelit pelataan milläkin kierroksella ja millä väreillä

-- Jyrki Kivinen 25.10.2004

Kirjoitin lyhyen ohjelman, jolla voi generoida tekstimuotoisia paritustaulukoita. Pitää harjoitella uutta kieltä harrastuksen vuoksi :-)

Pekka Karjalainen, 30.5.2005

Here's a short reminder on the most common formatting rules you have at your disposal. A complete list is available in TextFormattingRules.

(empty line)     Make a paragraph break.
----             Horizontal ruler
[link]           Create hyperlink to "link", where "link" can be either an internal 
                 WikiName or an external link (http://)
[text|link]      Create a hyperlink where the link text is different from the actual 
                 hyperlink link.
[text|wiki:link] Create a hyperlink where the link text is different from the 
                 actual hyperlink link, and the hyperlink points to a named Wiki. 
                 This supports interWiki linking.

*                Make a bulleted list (must be in first column). Use more (**) 
                 for deeper indentations.
#                Make a numbered list (must be in first column). Use more (##, ###) 
                 for deeper indentations.

!, !!, !!!       Start a line with an exclamation mark (!) to make a heading. 
                 More exclamation marks mean bigger headings.

__text__         Makes text bold.
''text''         Makes text in italics (notice that these are single quotes ('))
{{text}}         Makes text in monospaced font.
;term:def        Defines 'term' with 'def'.  Use this with empty 'term' to make short comments.
\\               Forced line break (please use sparingly).

|text|more text| Makes a table. Double bars for a table heading.

Don't try to use HTML, since it just won't work.

To embed images just put them available on the web using one of the approved formats, and they will get inlined automatically. To see the list of approved formats, go check SystemInfo.

To make a code block, use triple {'s to open, and triple }'s to close.

(Wondering where this text comes from? It's on a page called Edit Page Help, which you can edit too!)