Tekmovalni dnevi Instituta Jožef Stefan
Srednješolsko tekmovanje ACM iz računalništva in informatike
Tarok — tekmovanje programov
- [novo] Objavili smo manjše popravke testnega okolja..
- Objavili smo testno okolje in ogrodja za razvoj vaših rešitev.
Letošnja naloga za tekmovanje programov je napisati program, ki igra tarok po malo poenostavljenih in prilagojenih pravilih.
Pravila
Igralci, pripomočki. Tarok je igra s kartami. Igrajo jo štirje igralci s 54 kartami:
- 22 tarokov, oštevilčenih od 1 do 22
- po 8 kart vsake barve (srce, kara, križ, pik): 7, 8, 9, 10, fant, kaval, kraljica, kralj.
Predpriprava. Strežnik naključno premeša karte. Šest jih zadrži (tem kartam pravimo talon), po 12 pa jih razdeli vsakemu igralcu. Strežnik določi tudi vrstni red, v katerem igralci „sedijo za (okroglo) mizo“.
Tipi igre. Vsako igro je eden od igralcev „glavni“. Ta igralec se odloči za enega od kraljev (srce, kara, pik, križ) in za enega od šestih tipov igre: 3, 2, 1, solo 3, solo 2 ali solo 1.
Glavnega igralca se določi tako, da vsak igralec pove, kakšen tip igre želi igrati, nato pa glavni igralec postane tisti, ki je predlagal navišje točkovan tip igre (glej Točkovanje). Če je takšnih igralcev več, glavni postane tisti, ki v sedežnem redu nastopa prej.
Če se odloči za igro „3“, se karte iz talona razdeli v dve skupini po 3 karte; glavni igralec pred začetkom igre vzame poljubno izmed teh dveh skupin v roke (jih doda svojim 12 kartam) ter poljubne 3 karte iz svoje roke (razen kraljev) pospravi na svoj kupček. (V tej fazi igre sicer še nobeden od igralcev nima svojega kupčka; na kupčku nabirajo karte, ki jih pridobijo med rednim delom igre.)
Igralci se nato organizirajo v dve skupini. Igralec, ki ima v roki kralja, ki si ga je izbral glavni igralec, igra v skupini z glavnim igralcem, preostala dva igralca pa tvorita drugo skupino. Če je bil izbrani kralj v talonu, igra glavni igralec sam, preostali trije igralci pa tvorijo drugo skupino.
Podobni sta igri „2“ in „1“, le da se talon razdeli na skupine s po dvema oz. po eno karto, zato glavni igralec dobi le dve oz. eno karto in zato tudi na kupček pospravi le dve oz. eno karto. V „solo“ različicah iger vsa pravila ostanejo enaka, le da glavni igralec ne izbere kralja, temveč igra sam proti vsem trem igralcem.
Redni del igre. Igra ima 12 krogov. Prvi krog začne prvi igralec po sedežnem redu. Preostale kroge začne tisti, ki je pobral karte v predhodnem krogu.
Igralec, ki začne krog, vrže poljubno karto. V vrstnem redu, določenim na začetku igre, vržejo po eno karto še preostali igralci. Če je prvi igralec vrgel netaroka, mora vsak od preostalih igralcev vreči karto enake barve; če takšne karte nima, mora vreči taroka; če pa nima niti taroka niti karte enake barve, lahko vrže poljubno karto. Če pa je prvi igralec vrgel taroka, mora tudi vsak od preostalih igralcev vreči taroka, če ga le ima, in poljubno karto sicer. Na koncu kroga vse štiri karte pobere in spravi na svoj kupček igralec, ki je vrgel najvišjo karto. Vsak tarok pobere vsakega netaroka. Netaroki, ki so enake barve kot prva v krogu vržena karta, poberejo netaroke drugih barv. Med kartami iste barve je kralj najvišja karta, 7 pa najnižja.
Točkovanje. Igralci znotraj vsake skupine združijo kupčke. Kupčka se ovrednotita tako, da se seštejejo vrednosti kart v kupčku. Naj bo A vrednost kupčka tiste skupine, v kateri je glavni igralec, B pa vrednost kupčka druge skupine. Potem vsi igralci skupine, v kateri igra glavni igralec, dobijo točke po formuli
|A − B|/2 + (vrednost tipa igre), če je A > B, v nasprotnem primeru (torej če je A ≤ B) pa takšno število točk izgubijo.
Vrednosti tipov iger: Tip igre Vrednost igre 3 30 2 60 1 90 solo 3 120 solo 2 150 solo 1 180 Vrednosti kart: Karta Vrednost kralj 13 kraljica 10 kaval 7 fant 4 taroki 1, 21 in 22 13 ostale karte 1
Razlike glede na klasični tarok
Zgornja pravila se v marsikateri podrobnosti razlikujejo od klasičnih. Odpadejo na primer posebne igre (berač, klop, valat, barvni valat), rdeči platlci so preštevilčeni, ni napovedi (kralj ultimo, pagat ultimo ipd), dovoljeno je založiti taroke, točkovanje je poenostavljeno (čeprav kljub nenavadnemu izgledu skoraj povsem ekvivalentno klasičnemu), ni posebnega točkovanja trule, kraljev, mondfanga, . . . , pagat ne pobere trule itd. Vseh razlik ne bomo posebej navajali. Veljajo le pravila, eksplicitno navedena zgoraj; ne privzemajte torej pravil, ki jih morda poznate od prej.
V primeru nejasnosti nam pišite.
Funkcije, ki jih morajo implementirati igralci
Vsak tekmovalec mora v izbranem programskem jeziku implementirati spodaj naštete funkcije. Funkcije so na tem mestu deklarirane v nekakšnem metaprogramskem jeziku, ki je, upamo, razumljiv vsem; deklaracije v tvojem programskem jeziku pa bodo verjetno videti nekoliko drugače. TipIgre in Karta sta posebna podatkovna tipa; definirana bosta v testnem okolju, ki ga bo v kratkem pripravila komisija.
zacniIgro(Karta[] karteZaVRoko) — sistem jo pokliče na začetku igre in ji sporoči, katere igre je igralec na začetku dobil v roko. Funkcija mora vrniti tip igre (3, 2, 1, solo 3, solo 2 ali solo 1), za katerega se je igralec odločil.
zalozi(Karta[] karte, Karta[][] talon) — sistem jo pokliče za funkcijo zacniIgro, vendar le pri glavnem igralcu. Parameter talon podaja vsebino talona (odvisno od tipa igre sta to dve skupini po 3 karte, tri skupine po 2 karti ali pa šest skupin po 1 karto). Parameter karte vsebuje karte, ki jih imaš trenutno v roki. Funkcija mora vrniti dve tabeli kart; prva pove, katere karte iz roke bi igralec založil, druga pa pove, katere karte iz talona bi vzel namesto njih.
zacniRedniDel(int idxIgralca, int glavniIgralec, TipIgre tipIgre, Karta[] ostanekTalona, Karta[] pobraneKarteTalona) — sistem jo bo poklical za zacniIgro in zalozi. Igralec iz parametrov izve svoj položaj v sedežnem redu (idxIgralca), položaj glavnega igralca (glavniIgralec), tip igre, za katerega se je odločil glavni igralec (tipIgre), pa tudi to, katere karte je glavni igralec vzel iz talona in kaj je od talona še ostalo. Ta funkcija ne vrača ničesar.
vrziKarto(Karta[] tvojeKarte, Karta[] karteNaMizi, int prviIgralec) — sistem jo v vsakem krogu igre pokliče po enkrat (torej enkrat pri vsakem igralcu in to v takšnem vrstnem redu, kot navajajo pravila igre). Prva dva parametra povesta, kaj ima igralec trenutno v roki in kaj vidi na mizi, tretji pa je številka igralca, ki je začel ta krog. Funkcija mora vrniti eno od kart iz tvojeKarte, ki jo bo igralec v tem krogu vrgel na mizo.
konecKroga(bool zmagal, int prviIgralecVKrogu, int zmagovalec, Karta[] karteNaMizi) — sistem jo pokliče na koncu vsakega kroga, v parametru karteNaMizi pa pove, katere karte so se pri tem krogu nabrale na mizi. Parametra prviIgralecVKrogu in zmagovalec povesta kateri igralec je začel krog in kateri je zmagal v tem krogu; parameter zmagal pa pove če si zmagovalec ti.
konecIgre(string razlog) — sistem jo pokliče na koncu igre, v parametru pa pove razlog za konec igre (to je neformalno sporočilo v ljudem prijaznem jeziku; namenjeno je zgolj debuggiranju).
Pravila tekmovanja
Vsak tekmovalec napiše svojo skupino podprogramov za igranje taroka. Za ocenjevanje bomo izvedli veliko število iger, po možnosti tako, da bodo prišle na vrsto vse možne kombinacije štirih igralcev in da bo bodo vsi igralci sodelovali v enakem številu iger. Po vsaki igri bomo izračunali točke (po zgoraj opisanih pravilih) in jih pripisali igralcem zmagovalne skupine. Na koncu bomo za vsakega tekmovalca sešteli točke, ki jih je njegov igralec taroka dobil v vseh igrah; zmagovalec je tisti z največ točkami. Če bomo dobili programe le od dveh ali treh tekmovalcev, bomo razliko do štirih zapolnili enim ali dvema preprostima igralcema, ki ju bo pripravila tekmovalna komisija.
Na to tekmovanje se ni treba posebej prijavljati. Tiste, ki vas sodelovanje v tem tekmovanju zanima, vabimo, da nam to sporočite po elektronski pošti (rtk-info@ijs.si). V sporočilu tudi navedite, v katerem programskem jeziku bi predvidoma napisali svoj program.
Programe sprejemamo do vključno 12. marca 2010, lahko pa nam jih pošljete tudi že prej. Izvorno kodo svojega programa nam pošljite po elektronski pošti na naslov rtk-info@ijs.si. Končni rezultati bodo objavljeni po zaključku 5. tekmovanja ACM in IJS v znanju računalništva (27. marca 2010).
Na tem tekmovanju programov lahko sodeluje kdorkoli, ne glede na starost, izobrazbo, itd. Objavili bomo rezultate vseh prejetih programov, najbolje uvrščeni dijak in najbolje uvrščeni študent pa bosta dobila tudi praktične nagrade.
Omejitve
Posamezni program lahko za posamezno igro porabi vsega skupaj največ 5 minut procesorjevega časa; v kateremkoli trenutku lahko uporablja največ 2 GB pomnilnika. (Igra bo potekala na računalniku z vsaj 2GHz AMDjevimi Opteroni.) Dovoljena je uporaba 64-bitnega naslavljanja in ostalih zmogljivosti teh procesorjev (npr. ukazi SIMD), če izbrani programski jezik to omogoča. Prepovedana je uporaba sistemskih klicev (npr. spreminjanje sistemskih nastavitev, časovnikov, …).
Razvojno okolje
Za razvoj boš potreboval testno okolje in zasnovo za tekmovalca. Testno okolje deluje kot strežnik, na katerega se poveže odjemalec, ki krmili tvojega tekmovalca. Poženi ga iz ukazne vrstice (tarok_eval_cli.exe), s parametri pa mu lahko poveš stevilo iger, ime datoteke, v katero naj shranjuje vmesne rezultate v CSV formatu, ipd. Program počaka, da se z njim povežejo štirje odjemalci, ki simulirajo tekmovalce, nato pa požene željeno število iger. Po vsaki igri izpiše statistike o odigrani igri; med igro pa lahko izpisuje tudi posamezne korake. Izvorno kodo testnega okolja (v pythonu) lahko pogledaš tu.
Stara različica testnega okolja je izpisovala vmesne rezultate v napačnem zaporedju. Poleg tega nova različica pravilno vodi točkovanje v primeru, ko igralec izbere solo igro, vendar istočasno izbere tudi veljavno barvo.
Zasnova za tekmovalca je trenutno na voljo v naslednjih jezikih:
- C++ (s projektom za Visual Studio 2008; če prevajate za Windows s čim drugim,
ne pozabite prilinkati zraven še knjižnice WinSock,
ws2_32.lib) - C# (s projektom za Visual Studio 2008)
- Java
- Python
Če bi želel pisati v jeziku, ki ga ni na zgornjem spisku, pošlji e-mail na blaz.novak@ijs.si.
Tu bodo objavljeni tudi morebitni popravki testnega okolja in zasnov za tekmovalce.
Vsaka zasnova že vsebuje:
- vse potrebno za komunikacijo z ocenjevalnim programom -- teh datotek ne spreminjaj
- razreda Karta in TipIgre ter nekaj uporabnih funkcij za izpis kart, izracun veljavnih potez, itn.
- datoteko z imenom Igralec.{cpp,h/java/cs/py}, ki v razredu Igralec vsebuje zgoraj opisane funkcije ZacniIgro, Zalozi, ZacniRedniDel, VrziKarto, KonecKroga, KonecIgre, ter spremenljivko Ime (ime tvojega igralca). Te datoteke lahko spreminjaš po želji, v razred Igralec lahko dodajaš nove spremenljivke, itd.
Za testiranje najprej zaženeš testno okolje, potem pa še štiri igralce.
Če imate v zvezi s tekmovanjem programov kakršna koli vprašanja, se obrnite na Blaža Novaka (blaz.novak@ijs.si), ali pa na forum.