keskiviikko 11. toukokuuta 2016

MM-jääkiekon turnausformaatin mallinnusta

MM-kisojen pistelaskusysteemi antaa aina aivoilleni virikkeitä. Systeemi tuntuu omituiselta, mutta voin tietokoneohjelmalla osoittaa, että se toimii.

Pistelasku kausilla 2015 ja 2016

Turnaus alkaa alkusarjalla, joka kestää valtaosan turnauksesta. Joukkueet ovat valmiiksi jaettu kahteen erilliseen lohkoon A ja B. Lohkot on muodostettu aiempiin kisoihin perustuvan ranking-sijoituksen perusteella niin, että ne olisivat mahdollisimmat tasavahvoja.

Kummankin lohkon kaikki kahdeksan joukkuetta pelaavat toisiaan vastaan. Ottelut pelataan ratkaisuun asti. Jos ratkaisu tapahtuu varsinaisella peliajalla, pisteet jaetaan voittajan eduksi 3-0. Jatkoerässä tai rankkarikisassa (viralliselta nimeltä voittomaalikilpailussa) ratkaistussa ottelussa pisteet jaetaan tasaisemmin, 2-1.

Kumpikin lohko järjestestetään sen joukkueiden saamien pisteiden mukaisesti. Lohkon ykkönen on se, joka saa eniten pisteitä. Neljän vähiten pisteitä saaneen joukkueen pelit päättyvät. Niiden sijoitus turnauksessa selviää ensisijaisesti lohkosijoituksen mukaan. Jos ne ovat tasan, ratkaisee ensin pisteet, ja sen jälkeen muut tekijät.

Turnaus päättyy pudotuspeliin. Puolivälierässä lohkon A joukkueet pelaavan B-lohkon joukkueita vastaan käänteisessä järjestyksessä. A1 pelaa B4 vastaan, A2 pelaa B3 vastaan, jne. Välierissä ovat vastakkain 1A/4B – 2B/3A ja 1B/4A – 2A/3B. Voittajat jatkavat finaaliin ja hävinneet pronssiotteluun.

Tietokoneohjelmaa rakentamaan

Tietokoneohjelmaa tehdässä asioita kannattaa alussa yksinkertaistaa.

Joukkue on yhtäkuin sen vahvuustasoa kuvaava kokonaisluku. Perättäiset kokonaisluvut 0, 1, 2, ... luodaan komennolla.
joukkueet = range(16)
Alkulohkojen lohkojako määräytyy edellisten kisojen perusteella. Kokeilin kuitenkin muodostaa lohkot sattumanvarasesti sekoittaen listan, ja jakamalla se kahteen lohkoon.
random.shuffle(joukkueet)  
lohkoA = joukkueet[0:8]
lohkoB = joukkueet[8:18]
Sitten mallinnetaan alkusarja, jossa kaikki pelaa toisiaan vastaan. Koodin voisi rakentaa hätäisesti kahdesta silmukasta, mutta pythonissa on tätä varten ns. syntaktista sokeria. Tässäkin on yksinkertaistettu. Todellisuudessa pitäisi ottaa huomioon vielä otteluiden jakautuminen tasaisesti, sekä ajallisesti, että koti- ja vieraslogiikan suhteen.
for (id1, jo1), (id2, jo2) in itertools.combinations(enumerate(lohko), 2):

Voittaja saa ohjelmassani aina 3 pistettä. Jatkoaikaa tai rankkarikisaa ei ole mallinnettu.

Jatkopeleissä olen käyttänyt hyväksi järjestettyjä taulukoita: Sekä alkusarja-funktio että ottelufunktio palauttaa tulokset taulukkona, jonka solun järjestysnumero vastaa sijoitusta. Siten on helppoa osoittaa jatkopeliin valittua joukkuetta:

finaali = pelaa_ottelu_sort(valiera1[0], valiera2[0])
pronssiottelu = pelaa_ottelu_sort(valiera1[1], valiera2[1])
Lopuksi testataan vielä, onko tuloslista todenmukainen.

Ohjelman suorituksen perusteella neljä parasta joukkuetta menee aina täysin oikein, mikäli oletetaan, että parempi joukkue voittaa aina. Kisoissa pelataan 64 ottelua, ohjelmassani tehdään yhtä monta vertailua, ja tämä riittää neljän parhaan joukkueen löytämiseen. Koska millään joukkueella ei ole samaa taitotasoa, tasapelejä ei ilmene.
[15, 14, 13, 12]

Kiekko pomppii aina

Ongelmat alkavat, kun otetaan huomioon otteluiden tulosten sattumanvaraisuus. Turnausformaatin olisi siedettävä yksittäinen ottelukohtainen vaihtelu. Se ei saisi johtaa merkittävästi väärään lopputulokseen, ja joukkuetta tulisi arvioida pelattujen otteluiden keskiarvon mukaan.

Pienet vaihtelut joukkueiden taitotasossa ovat todennäköisempiä kuin suuret, eikä ole odotettua, että kaikki asiat menisivät joukkueessa pieleen. Oletan, että joukkueiden tasovaihtelu noudattaa normaalijakaumaa eli gaussinkäyrää. (Juhani Tamminen on kylläkin puhunut jääkiekon momenttum-ilmiöstä, mutta en tässä ota siihen kantaa.) Pythonissa on satunnaislukugeneraattori, joka laskee gaussin jakaumalla. Tulos ottelusta saadaan yksinkertaisesti laskemalla taitotason erotus, ja lisäämällä siihen satunnaisuutta gauss-funktiolla.
tulos = joukkue1 - joukkue2 + random.gauss(0, varianssi)
 Varianssi vaikuttaa pistelaskun onnistumiseen melkoisesti.


Jatkopohdiskelua


Tulokset olisivat vähän parempia, jos noteerattaisiin jatkoaika alkusarjan pistetuloksista. Näin ottelun tulokset saadaan tarkemmin, ja joukkueiden järjestys sarjan jälkeen määräytyy todenmukaisemmin. Kokeilin alustavasti, ja parhaimmillaan saavutetaan 5% tarkempia tuloksia.

Alkulohkojen järjestäminen aikaisempien tulosten perusteella auttaa, mutta pääasiassa vain sijoituksilla 5-16.

Vielä kuriositeettina QuickSort-funktion käyttö turnauksessa. Kuvassa virallinen pistejärjestelmä sinisellä ja QuickSort punaisella.


Lähdekoodi

# -*- coding: utf-8 -*-

import random, itertools

#Suorittaa yksittäisen ottelun
#Palauttaa tuplen, jossa (voittaja, häviäjä)
def pelaa_ottelu_sorted(joukkue1, joukkue2):
  if(random.gauss(joukkue1 - joukkue2, 0.5) < 0):
    return (joukkue2, joukkue1)
  else:
    return (joukkue1, joukkue2)

#Suorittaa lohkolle alkusarjan pelit
#Palauttaa tuplen, jossa lohkon joukkueet järjestettynä pisteiden mukaisesti
def pelaa_alkusarja_sorted(lohko):
  pistetaulu = [0]*8
  for (id1, jo1), (id2, jo2) in itertools.combinations(enumerate(lohko), 2):
    if pelaa_ottelu_sorted(jo1, jo2)[0] == jo2:
      pistetaulu[id2]+=3
    else:
      pistetaulu[id1]+=3

  #Järjestetään pisteiden perusteella
  return [x for (y, x) in sorted(zip(pistetaulu, lohko), reverse=True)]

#Toteuttaa turnauksen
#palauttaa neljä parasta joukkuetta, järjestettynä sijoituksen mukaan voittajasta aloittaen
def turnaus_sorted(joukkueet):

  lohkoA = pelaa_alkusarja_sorted(joukkueet[0:8])
  lohkoB = pelaa_alkusarja_sorted(joukkueet[8:18])

  puolivaliera1 = pelaa_ottelu_sorted(lohkoA[0], lohkoB[3])
  puolivaliera2 = pelaa_ottelu_sorted(lohkoA[2], lohkoB[1])
  puolivaliera3 = pelaa_ottelu_sorted(lohkoB[0], lohkoA[3])
  puolivaliera4 = pelaa_ottelu_sorted(lohkoB[2], lohkoA[1])

  valiera1 = pelaa_ottelu_sorted(puolivaliera1[0], puolivaliera2[0])
  valiera2 = pelaa_ottelu_sorted(puolivaliera3[0], puolivaliera4[0])

  finaali = pelaa_ottelu_sorted(valiera1[0], valiera2[0])
  pronssiottelu = pelaa_ottelu_sorted(valiera1[1], valiera2[1])

  #jarjestetaan lopullinen ranking
  tuloslista = finaali + pronssiottelu

  return tuloslista


joukkueet = range(16)
random.shuffle(joukkueet)
print "Kaikki joukkeet:", joukkueet
print "Neljä parasta:  ", turnaus_sorted(joukkueet)

torstai 21. tammikuuta 2016

AAPUUVA! Kuvanpakkaus vie tikkaukset Jamesin taskuista

Vihdoinkin aihe, joka sopii blogin nimeen. Pureudumme tällä kertaa hyvänlaatuisen kuvan harhaan.

Tänäpäivänä videokuvaan kohdistuu tiettyjä voimakkaita vaatimuksia. Sen pitää sävähdyttää hienoilla efekteillä, mutta samanaikaisesti sen on mahduttava pieneen tilaan. Tämä johtaa aika erikoiseen lopputulokseen.

En nyt halua mennä teknisiin yksityiskohtiin (paitsi ehkä parissa viimeisessä kappaleessa), vaan haluan tarkastella tilannetta sellaisena kuin se on käytännössä esittäytyy. Aihe on niin monimutkainen, että kaikenkattavaa selostusta ei voi yhdessä postauksessa antaa. Seuraavassa kuitenkin jonkinlaisia esimerkkejä kuvan pakkaamisesta aiheutuvista ongelmista.

DVD vuodelta 2005, julkaissut EMI ja SubTV
 
Tavallinen digi-TV, n. 4000 kbs, MTV3 29.12.2015

Youtube, 720p, 1600 kbs, "julkaistu 24.2.2013"


DVD vuodelta 2005, julkaissut EMI ja SubTV


Tavallinen digi-tv, MTV3 29.12.2015

Youtube, 720p, "julkaistu 24.2.2013"


DVD-versiossa on selvästi kohinaa, joka on hävinnyt Youtuben versiosta. Youtube-kuva vaikuttaa ensinäkemältä jopa laadukkaammalta, ellei joukko yksityiskohtia olisi kadonnut. Tässä tapauksessa taskun kaksoistikkaus on pudonnut pois.

Tämä on tyypillinen esimerkki tiukasta MPEG-4-pakkauksesta, joka on yleistä Youtubessa. Minulle heräsi myös epäilys siitä, että televisiossa lähetetty versio olisi kokenut lievän MPEG-4-käsittelyn. Se on voinut tapahtua varastoidessa ohjelmaa, tai sitten lähettäessä se Digitalle lopullista MPEG-2 jakelua varten.

DVB-T-nauhoite TV2, 2015.

Sama TV-nauhoite pakattuna XviD-muotoon
Vertaisverkossa kiertävä Xvid-versio.
Tämän Kummeli-elokuvan pakkaamisessa retrotapetin rosoisuus on jäänyt pois. Tapetti on osa lavastetta, ja pelkkä tasainen seinä antaa studiomaisen vaikutelman. Ilman vertailukuvaa muutosta ei huomaa, ja kuva näyttää yhtä laadukkaalta.

TV1,dvb-t-lähetys
Areenan tallenne, "HD"



Tässä HD-tasoiseksi merkitty tallenne Yle Areenassa näyttää selvästi sumeammalta kuin TV:ssä esitetty.

Vasemmalla DVD ja oikealla MP4-tiedosto TV-kaistasta (n. 1500 kbs)
TVkaistan kuvanlaatun oli yllättävän hyvä, kun käytti korkeinta mahdollista bittivirtaa (nimellisesti 2000 kbs). Tässä terävöitetyssä kuvassa näkyy, kuinka videonpakkaus on suodattanut kohinat pois. Pitää silti muistaa, että kohinassakin on kuvainformaatiota, ja suodatuksella menetetään osa siitä.

TV2, tavallinen digi-tv

TV2, HD 1280x720, nettisteam (H.264)
Hiihtokisojen mainokset näkyvät HD-lähetyksessä selvästi paremmin, vaikka lähetysvirta on 25% alhaisempi. Toisaalta maisemasta ei voi yksiselitteisesti sanoa samaa. Kuusen yksittäiset oksat erottautuvat kyllä paremmin, mutta kokonaisuus on minusta hyvin erilainen. Oletan, että nettisteamista puuttuu jotain, mutta en osaa nimetä sitä vielä.
H.264-koodauksen purkaminen on tietysti myös raskaampaa tietokoneelle. Seuraavat mittaukset on molemmat tehty VLC-ohjelmalla äsken mainitun hiihtokilpailun aikana:


enkoodaus prosessorikäyttö prosessorin lämpötila
MPEG-2 10-12% +30
MPEG-4 H.264 22-26% +33

Yleinen uskomus on se, että koodekit kehittyvät huimaa vauhtia, ja yhä laadukkaampaa videota voidaan pakata yhä pienempään tilaan. MPEG-2 nähdään vanhentuneena teknologiana, ja suuria odotuksia asetetaan MPEG-4-koodekeille. Viimeksi mainittuja ovat H.263 (käytetty erityisesti vertaisverkoissa xvid-kääreessä), H.264 (käytetty laajasti blu-rayssa, HD-televisiossa ja nettistriimauksessa), ja vasta tulossa oleva H.265 (suunniteltu käytettäväksi 4k-televisioissa).

Muokattu 24.1.2016. Lisätty Jumalanpalvelus-kuvat ja taulukko.