Tekmovalni dnevi Instituta Jožef Stefan

Štiri v vrsto — tekmovanje programov

Igra poteka na igralnem polju, ki je karirasta mreža velikosti w × h. Na začetku igre je polje prazno. Igro igrata dva igralca, ki izmenično delata vsak po eno potezo. Poteza je sestavljena iz tega, da igralec izbere enega od w stolpcev polja (razen tistih, ki že vsebujejo h žetonov) in vanj vrže svoj žeton. Žeton pristane nad ostalimi žetoni v tistem stolpcu.

Prvi igralec ima modre žetone, drugi pa rdeče. Če se nekoč med igro znajdejo skupaj štirje žetoni iste barve (v isti vrstici, stolpcu ali diagonali), zmaga igralec, ki mu ta barva pripada. Če pa se igralno polje (po w · h potezah) napolni, ne da bi kateri od igralcev dosegel štiri v vrsto, je izid neodločen.

Vsak tekmovalec napiše en podprogram za krmiljenje igralca (ta podprogram dobi na začetku podatke o velikosti igralnega polja, kasneje med igro pa podatke o tem, kje na polju so že žetoni, kakšnih barv so in kaj je bila zadnja nasprotnikova poteza). Na tekmovanju bomo med seboj primerjali podprogram vsakega tekmovalca s podprogrami vseh ostalih tekmovalcev. Za vsak par tekmovalcev bomo izvedli več iger (za primer, da si igralca pri odločanju o potezah pomagata z naključnimi števili). Po vsaki igri dobi zmagovalec eno točko, če se je igra končala z neodločenim izidom, pa dobi vsak igralec po pol točke. Zmagovalec bo tisti tekmovalec, čigar program bo zbral največje največje skupno število točk.

Tekmovanje bo potekalo v dveh kategorijah, ki se razlikujeta po velikosti igralnega polja:

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.

Rok za oddajo programov je 21. marec 2008. Izvorno kodo svojega programa nam pošljite po elektronski pošti na naslov rtk-info@ijs.si. Rezultati bodo objavljeni po zaključku tekmovanja iz znanja, 29. marca 2008.

Na tem tekmovanju programov lahko sodeluje kdorkoli, ne glede na starost, izobrazbo, itd. Objavili bomo rezultate vseh prejetih programov, za morebitne praktične nagrade pa pridejo v poštev le tisti tekmovalci oz. tekmovalke, ki v letu 2007/08 obiskujejo kakšno srednjo šolo.

Opis naloge

Igralno polje je pravokotna površina velikosti w × h; koordinate polj so cela števila od 0 do n − 1 (x-koordinata narašča od leve proti desni, y-koordinata narašča od spodaj navzgor). Tekmovalec napiše tri funkcije:

Cilj

Igralčev cilj je postavitev vzorca štirih sosednjih žetonov v vrsto, stolpec ali diagonalo, preden to uspe nasprotniku. Igre je konec, ko en od igralcev doseže cilj, ali pa je igralna površina zapolnjena.

Omejitve

Vsak igralec ima za eno igro skupno na voljo 120 sekund procesorskega časa pri igrah na polju 7 × 6 in 600 sekund za igre na polju 20 × 20. (Igra bo potekala na računalniku z vsaj 2GHz AMDjevimi Opteroni.) Posamezni igralec lahko uporablja največ 4 GB pomnilnika v kateremkoli trenutku. Dovoljena je uporaba 64 bitnega naslavljanja in ostalih zmogljivosti teh procesorjev (npr. SIMD ukazi), če izbran programski jezik to omogoča. Igralec, ki prekorači časovno ali prostorsko omejitev, ali pa naredi neveljavno potezo (npr. poskuša dodati žeton v stolpec, ki je že poln), igro takoj izgubi.

Prepovedana je uporaba sistemskih klicev (npr. spreminjanje sistemskih nastavitev, časovnikov, …) z izjemo branja datotek v trenutnem direktoriju (kjer imaš lahko npr. datoteke z že vnaprej pripravljenimi izračuni, ki jih pošlješ skupaj z rešitvijo; prostorska omejitev posamezne rešitve na disku je 50GB) in branja ure.

Razvojno okolje

Za razvoj boš potreboval:

in zasnovo za igralca. Ta je trenutno na voljo v naslednjih jezikih:

Tu bodo objavljeni tudi morebitni popravki in izboljšave razvojnega okolja in zasnov igralcev, pa tudi zasnove igralcev v novih jezikih. Če na zgornjem seznamu ni jezika, v katerem bi rad napisal svojo rešitev, nam pošlji e-mail.

Vsaka zasnova že vsebuje:

  • vse potrebno za komunikacijo z ocenjevalnim programom (datoteke SVVClient_*.*, ki jih ne spreminjaj),
  • datoteko z imenom Igralec.*, ki v razredu Igralec vsebuje funkcije ZbudiSe, KamGres (s preprostim primerom) in KonecIgre ter spremenljivko Ime (ime tvojega igralca; v Delphi različici je to funkcija getIme). Te datoteke lahko spreminjaš po želji, v razred Igralec lahko dodajaš nove spremenljivke in funkcije, itd.
  • razred podatkovnega tipa igralno polje (v datoteki Polje.*). Spremenljivko tega tipa dobi funkcija KamGreš kot vhodni parameter. S tem razredom si lahko pomagaš pri pisanju svoje rešitve, vendar ga ne spreminjaj — če potrebuješ dodatno funkcionalnost, iz njega izpelji nov razred. V datoteki je tudi komentar s kratkim opisom uporabe.

    Za testiranje najprej zaženeš testno okolje, potem pa še dva igralca (lahko tudi dvakrat enega in istega igralca).

    Č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.

    Na vrh strani. | H kazalu. | Imate vprašanje ali komentar?