Tekmovalni dnevi Instituta Jožef Stefan

Štiri v vrsto — tekmovanje programov

• Rezultati.

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:

• Igralno polje 7 × 6 (7 stolpcev, največ 6 žetonov v vsakem stolpcu).
• Igralno polje 20 × 20.

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:

• Prvo (ZbudiSe) ocenjevalni program pokliče ob začetku igre, za parametre dobi velikost igralnega polja (sirina, visina) in spremenljivko zacne, ki pove, ali bo naš igralec prvi na potezi ali ne. Ta podprogram si lahko pripravi globalne spremenljivke in vse, kar igralec potrebuje za razmišljanje.

• Drugo funkcijo (KamGres) izvede ocenjevalni program enkrat na korak, od nje pa pričakuje odločitev o tvoji potezi.

  Kot parameter dobi ta funkcija stanje igralnega polja (kje so žetoni in kakšne barve so; ta parameter se prenaša po vrednosti, spremembe te spremenljivke ne bodo vplivale na potek igre) in parameter prejsnja_poteza, ki pove, kakšna je bila zadnja poteza drugega igralca. To je številka stolpca (0, ..., sirina − 1), v katerega je dodal svoj žeton. Če smo šele pri prvi potezi in drugi igralec še ni naredil nobene poteze, bo prejsnja_poteza = −1. V vsakem primeru je ta poteza že tudi upoštevana v stanju igralnega polja, ki ga dobi funkcija.

  Vsako mesto igralnega polja je ene izmed treh barv: bPrazna (na tem mestu še ni žetona), bJaz (na tem mestu je moj žeton) ali bNasprotnik (na tem mestu je že nasprotnikov žeton).

  Funkcija KamGres naj vrne številko stolpca (0, ..., sirina − 1), v katerega bi rad trenutni igralec dodal svoj žeton.

• Zadnja funkcija (KonecIgre) se pokliče ob koncu igre in dobi podatek o tem, zakaj se je igra končala (zmaga, poraz ali neodločen izid).

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:

• Testno okolje (napisano v pythonu; lahko si preneseš tudi različico, prevedeno v .exe za Windows). Ta program deluje kot strežnik, na katerega se povežeta dva odjemalca, ki krmilita vsak svojega igralca. Poženi ga iz ukazne vrstice in mu podaj tri parametre: število parov iger, širino igralne površine in višino igralne površine. Program počaka, da se z njim povežeta oba igralca, nato pa izvede želeno število parov iger. Razlika med dvema igrama v paru je ta, da je v eni igri prvi na potezi en tekmovalec, v drugi igri pa drugi tekmovalec. Po vsaki igri izpiše, koliko točk je doslej dosegel kateri od igralcev.

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

• C++ (z Visual Studio 2005 projektom; če prevajate za Windows s čim drugim, ne pozabite prilinkati zraven še knjižnice WinSock, ws2_32.lib; za Bloodshed Dev-C++ je v .zipu tudi datoteka .dev z nastavitvami; mogoče boste morali spremeniti pot do knjižnice libws2_32.a (v Project -> Options -> Parameters -> Linker); na ostalih sistemih (Linux, MacOS,...) uporabite stanardni C++ prevajalnik, npr g++)
• C# (z Visual Studio 2005 projektom, prevede se tudi z Monom; prevajajte z gmcs namesto mcs zaradi uporabe generikov)
• PHP
• Java (z Idea5 projektom, prevede se tudi s čim drugim)
• Python
• Delphi

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?