Newsgroups: sfnet.atk.ohjelmointi,sfnet.atk,sfnet.harrastus.pelit,sfnet.harrastus.pelit.strategia,tut.ot

PRISONER'S DILEMMA - Vankipeli

Vaihe 1:n säännöt

Tämä ohjelmointikilpailu on avoin kaikille, jotka eivät tunne ennestään peliteorian yhtä peruspeliä, Prisoner's Dilemmaa, josta käytän tästedes nimeä Vankipeli.

Vankipeli on yksinkertainen peli. Siinä on kaksi pelaajaa, joilla kummallakin on kaksi korttia: LUOTA ja HYLKÄÄ. Pelaajat eivät näe toisiaan eivätkä voi sopia yhteistyöstä. Kumpikin valitsee toisen korteistaan ja laittaa sen pöydälle alassuin. Kun molemmat kortit ovat pöydässä, ne käännetään näkyviin niin, että molemmat pelaajat näkevät myös pelikaverin valinnan.

Vankipelin pisteytys menee seuraavasti:

• Jos molemmat valitsette LUOTA, saatte 30 mk mieheen.
• Jos valitset LUOTA, mutta toinen pelaaja HYLKÄÄ, menetät 10 mk ja vastapelurisi tienaa 50 mk.
• Jos valitset HYLKÄÄ ja vastapelurisi LUOTA, saat 50 mk ja vastustajasi menettää 10 mk.
• Jos valitsette molemmat HYLKÄÄ, menetätte kumpikin markan.

Taulukkoa miettimällä näkee äkkiä, että jos pelataan vain yksi kierros, kannattaa aina valita HYLKÄÄ, koska riippumatta vastustajan vedosta saat aina silloin enemmän rahaa. Ongelma on tietenkin se, että jos kumpikin tekee saman, menetätte molemmat hieman rahaa, vaikka sopimalla olisitte kumpikin päässeet reilusti voitolle.

Jos pelataan useampia kierroksia, tilanne muuttuu. Nyt toinen tai molemmat voi alussa kokeilla luottamisen taktiikkaa, koska jos naapuri hylkää, voit itse halutessasi jatkaa samalla tavalla, eikä yksi tai pari kierrosta vaikuta niin paljoa menestykseesi.

Ohjelmointikilpailun tehtävä on toteuttaa C-kielellä mahdollisimman hyvä algoritmi. Se saa olla niin yksinkertainen tai monimutkainen kuin haluat, kunhan sen voi toteuttaa annetulla rajapinnalla. Aliohjelmallesi annetaan syötteeksi ensimmäillä kierroksella S_ALOITUS ja seuraavilla kierroksilla S_LUOTA tai S_HYLKÄÄ sen mukaan, mitä vastapuoli edellisellä kierroksella teki. Aliohjelmasi taas palauttaa omana siirtonaan joko V_LUOTA tai V_HYLKÄÄ.

Miettimisen aiheita:

• kannattaako tehdä "kiltti" vai "ilkeä" algoritmi vai sekoitus
  • kiltti algoritmi ei koskaan aloita HYLKÄÄ-korttien peluuta
  • ilkeä algoritmi saattaa aloittaa HYLKÄÄ-korttien peluun
• kuinka monimutkainen algoritmista kannattaa tehdä
• kannattaako vastustajaa joskus "kupata"
• kannattaako vastustajalle antaa joskus armoa
• tarvitaanko muistia ja jos, niin kuinka paljon

KILPAILUN EHDOT

Oma pelialgoritmi on kirjoitettava aliohjelmana, joka saa käyttää kaikki standardin ANSI-C:n suomia mahdollisuuksia, kuten muistin varausta, satunnaislukuja (ei kuitenkaan srand()) jne. Tämä aliohjelma alkukommentteineen (esimerkkiohjelman mukaisesti) lähetetään minulle.

Kilpailuaikaa on 15.12.1996 asti, jolloin kokoan kaikki sähköpostitse lähetetyt aliohjelmat pääohjelman runkoon ja laitan ne kilpailemaan keskenään. Jos vastauksia tuntuu tulevan tämän jälkeenkin, voin järjestää toisen "varjokierroksen".

Jokainen aliohjelma ottelee esimerkkiohjelman tapaan kaksi kertaa toisiaan vastaan. Pelikierrosten tarkkaa määrää en kerro etukäteen, jotta algoritmit eivät voisi ottaa sitä huomioon, mutta se tulee olemaan 100 ja 1000 kierroksen välissä. Yksi kilpailija saa lähettää vain yhden työn, jotta ei olisi mahdollisuutta tehdä keskenään pelisäännöistä sopivia algoritmeja.

Jos useampi kilpailija lähettää tarkalleen saman algoritmin, jälkimmäinen diskataan. Samoin käy, jos ohjelma ei ole riittävän puhdasta ANSI-C:tä tai jos sitä ei ole dokumentoitu esimerkkiohjelman tavoin.

Jos ehdin, aion tehdä ohjelmille myös evoluutiotestipenkin, jossa parhaiten menestyvät aliohjelmat saavat tehdä kopioita itsestään ja näin ollen alkavat lisääntyä populaatiossa. Tästä näemme sitten, mikä on (ainakin yksi) evolutionäärisesti stabiili tila (ESS) kilpailutöille.

Kilpailun tulokset samoin kuin käytetyt aliohjelmat tulevat näkyville seittisivulleni tulosten selvittyä. Lähetän myös tulokset newsseihin.

Pääpalkintona on rajattoman kunnian lisäksi sokerimunkki (vapaasti Hermitecin ruokala, Hervanta, Tampere).

HUOM!
Jos aliohjelmassasi on muistia, tee siitä esimerkin mukaisesti itsellesi kaksi kopiota. Muuten se toimii väärin pelatessaan itseään vastaan. Testatessa itse voit pitää ohjelmastasi vain yhden kopion, kunhan muistat tämän säännön.

Tätä kilpailukutsua saa levittää vapaasti.