3CP06 - Project 2 - Probablistic Eleusis

Reima Halmetoja
Olli Lyytinen
Ilari Nieminen
Teemu Saukonoja

1. Korttipakan jakauman estimoiminen

Tiedemiehemme ei (valitettavasti) käytä Bayesilaisia menetelmiä korttipakan jakauman selvittämiseksi. Sen sijaan käytämme seuraavanlaista ahnetta ja yksinkertaista frekvenssinoppimismekanismia:

Pidämme yllä 4x13 matriisia M korttien arvioiduista frekvensseistä. Aluksi M on 0-matriisi. Bayesiläisittäin sanoisimme, että käytämme tasaista prioria korttipakan jakaumalle.
Jokaisella vuorolla saamme datavektorin v=[arvattu maa, arvattu numero, maa oikein, numero oikein]. Kutakin tällaista vektoria kohden sirottelemme 1 yksikön verran frekvenssimassaa tasaisesti sellaisten korttien kesken, jotka ovat mahdollisia datavektorin perusteella. (Katso kuva alla). Tämä toimii käytännössä siten, että mitä enemmän informaatiota vektorissa on, sitä radikaalimmin jakauma muuttuu: Jos arvasimme molemmat oikein, yhden kortin frekvenssi kasvaa 1 yksikön, jos taas arvasimme molemmat väärin, 36 kortin frekvenssi kasvaa 1/36.

v=[ruutu, 8, true, true], delta(M)= v=[ruutu, 8, true, false], delta(M)=
v=[ruutu, 8, false, true], delta(M)= v=[ruutu, 8, false, false], delta(M)=

Kyseinen mallinnustapa on itse kehittämämme, emmekä osaa/jaksa esittää teoreettisia perusteluja sen toiminnalle tai suorituskyvylle. Intuitiivisesti malli on järkevä tapa estimoida korttipakan jakaumaa Eleusiksen palautteen perusteella ja testimme sekä kilpailun tulos osoittavat, että se toimii hyvin myös käytännössä. Mallinnustavalla on seuraavat mukavat ominaisuudet:

Mallinnus hyödyntää kaiken tarjolla olevan datan, ja hyödynnys tapahtuu siten, että informatiivisempi data vaikuttaa radikaalimmin. Hyödyntäminen ei kuitenkaan välttämättä ole optimaalista.
Mallinnus on tehokasta. O(1), pelkkiä yhteen-, kerto- ja jakolaskuja.
N:n kortin jälkeen mallissa on N yksikköä frekvenssimassaa. Niinpä uuden datan näkeminen vaikuttaa sitä vähemmän, mitä enemmän dataa on jo nähty, ja tämä vaikutuksen väheneminen tapahtuu oikeellisesti.
Mikäli tälle mallille haluaisi asettaa priorin (mitä emme tiedemiehessä tee), onnistuisi se helposti jakamalla N yksikköä frekvenssimassa haluttuun priorin muotoon. Samalla N on täsmälleen Equal Sampe Size tälle mallille.

2. Parhaan arvattavan kortin valitseminen

Tiedemiehemme valitsee kullakin kierroksella sen kortin, jonka odotusarvoinen harman kulutus on suurin mahdollinen. Tämä lasketaan mille tahansa kortille c seuraavasti.

Tästä lähinnä johtuu tiedemiehemme hitaahko suoriutuminen, sillä joudumme laskemaan joka vuorolla 52 odotusarvoa korttipakan estimoidun jakauman perusteella. Naiivimpi tapa valita kortti olisi ottaa sellainen kortti, jonka frekvenssi on pakan suurin. Tämä ei kuitenkaan ole paras tapa, sillä tiedemiehen tarkoitus on optimoida harmankulutusta. Seuraava yksinkertainen esimerkkipakka demonstroi, miksi suurin frekvenssi ei välttämättä ole paras arvaus:

P(pata 1) = 0.4 P(pata 2) = 0.3 P(ruutu 2) = 0.3

Tässä esimerkissä

Nyt lasketaan odotusarvot harman kulutukselle:

E(pata 1) = 3*0.4 - 2*0.3 = 0.6 E(pata 2) = 3*0.3 - 2*0.0 = 0.9

Vaikka kortin (pata,1) frekvenssi on suurin, kortilla (pata,2) on parempi odotusarvo harmankulutukselle, ja niinpä ilman muuta kannattaa arvata korttia (pata,2).

3. Lokaaliin maksimiin juuttumisen estäminen

Lokaaliin maksimiin juuttuminen Eleusiksen yhteydessä tarkoittaa sitä, että tiedemies pitää korttia c' parhaana harmankuluttajana, vaikka todellisuudessa pakassa on kortti c, c!=c' ja E(c) > E(c'). Tällöin tiedemies arvailee pelkästään korttia c', eikä saa enää riittävästi tietoa pakan muista korteista, jotta se voisi päätyä arvailemaan korttia c. Mikäli lokaaliin maksimiin juuttumista ei estä, tiedemies päätyy väistämättä 1000000 arvaukseen.

Eräs kokeilemamme ratkaisu tähän ongelmaan on satunnaistaa korttien arvailua simuloidun jäähdytyksen periaatteiden mukaisesti: mitä vähemmän tiedämme pakasta, sitä satunnaisempia ovat arvauksemme, ja sitä mukaa kun dataa kertyy, niin satunnaisuus arvauksissamme vähenee. Lopulta arvaukset konvergoivat globaaliin maksimiin. Tämä estää hyvin lokaaliin maksimiin juuttumisen, mutta seurauksena tiedemiehen suorituskyky heikkenee huomattavasti helpommilla jakaumilla.

TiedeUrpo ratkaisee ongelman jälleen hyvin yksinkertaisesti ja ahneesti siten, että seuraamme harman kehitystä, ja resetoimme koko koneiston, mikäli harmaa on kertynyt yli jonkun kiinteän kynnysarvon (Palautetussa versiossa 50). Koneiston resetointi tarkoittaa sitä, että nollaamme tiedemiehen muistin ja aloitamme uuden pelin tyhjältä pöydältä. Tämä on tehokasta, sillä useimmissa tapauksissa tiedemiehemme löytää globaalin maksimin ensimmäisellä yrityksellä.

4. TiedeUrpo pseudokoodina


harmanKehitys = 0;

resetointiKynnys = 50;

malli = alusta uusi malli. Tasainen priori.



while (true) {



    // Parhaan kortin arvaaminen

    Jakauma d = malli.laskeJakauma();

    Kortti c = jakauman d indeksi, jonka odotusarvoinen harmankulutus E(c) on suurin.

    

    // Mallin päivittäminen

    Eleusis.guess(c);

    v = Eleusis.reveal(); // palautevektori

    malli.train(v);



    // Lokaaliin maksimiin juuttumisen estäminen

    if (v.molemmatOikein)

	harmanKehitys -= 3;

    else if (v.molemmanVäärin)

	harmanKehitys += 2;

    if (harmanKehitys > resetointiKynnys) {

         malli = alusta uusi malli, tasainen priori.

         harmanKehitys = 0;

    }

}

`v=[ruutu, 8, true, true], delta(M)=`	`v=[ruutu, 8, true, false], delta(M)=`
`v=[ruutu, 8, false, true], delta(M)=`	`v=[ruutu, 8, false, false], delta(M)=`