Tekmovalni dnevi Instituta Jožef Stefan
Lov na zaklade — tekmovanje programov
Igra poteka na karirasti mreži velikosti n × n. Na začetku igre se na k različnih (naključno izbranih) poljih nahajajo zakladi.
Po mreži se premikata dva igralca (njun začetni položaj je izbran naključno). Igralec se lahko v enem koraku premakne s svojega trenutnega polja na eno od osmih sosednjih polj. Če pri tem stopi na polje z zakladom, dobi eno točko, zaklad pa izgine.
Oba igralca hkrati naredita vsak svojo potezo; če pri tem oba igralca hkrati stopita na isto polje z zakladom, dobita vsak po pol točke, zaklad pa izgine.
Primer na mreži velikosti 25 × 25:
Igre je konec po 10000 korakih (ali že prej, če so pobrani vsi zakladi). Zmagovalec je tisti, ki ima največ točk.
Vsak tekmovalec napiše en podprogram za krmiljenje igralca (ta podprogram dobi že na začetku tudi podatke o položaju vseh zakladov, kasneje med igro pa podatke o tem, kateri zakladi še niso bili pobrani). Na tekmovanju bomo med seboj primerjali podprogram vsakega tekmovalca s podprogrami vseh ostalih tekmovalcev. Za vsak par tekmovalcev bomo izvedli več iger z različnimi začetnimi položaji igralcev in zakladov. Zmagovalec bo tisti tekmovalec, ki bo zbral največje skupno število točk.
Tekmovanje bo potekalo v dveh kategorijah, ki se razlikujeta po velikosti igralnega polja in številu zakladov.
- Igralno polje 20 × 20, 10 zakladov.
- Igralno polje 100 × 100, 100 zakladov.
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 23. marec 2007. 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, 31. marca 2007.
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 2006/07 obiskujejo kakšno srednjo šolo.
Opis naloge
Igralno polje je kvadratna površina velikosti n × n; koordinate polj so cela števila od 0 do n − 1 (x-koordinata narašča od leve proti desni, y-koordinata narašča od zgoraj navzdol). Tekmovalec napiše tri funkcije:
Prva (
ZbudiSe) se pokliče ob začetku igre, za parametre dobi velikost igralnega polja, število zakladov na njem ter začetna položaja obeh igralcev in vseh zakladov na igralnem polju. Ta podprogram si lahko pripravi globalne spremenljivke in vse, kar igralec potrebuje za razmišljanje. Začetno stanje igre je tako, da noben igralec ne stoji na polju z zakladom.Druga funkcija (
KamGres) se izvede enkrat na korak. Kot parameter dobi položaj obeh igralcev in seznam tistih zakladov, ki doslej še niso bili pobrani. Vrne naj želeni premik (x-koordinata se lahko spremeni za −1, 0 ali +1, ravno tako pa tudi y-koordinata). Če bi želeni premik premaknil igralca čez rob igralnega polja, bo igralec ostal na dosedanjem položaju. Želja po premiku za več kot +1 se obravnava kot +1, želja po premiku za manj kot −1 pa se obravnava kot −1.Zadnja funkcija (
KonecIgre) se pokliče ob koncu igre in ne dobi nobenih posebnih parametrov.
Prepovedana je uporaba sistemskih klicev (npr. spreminjanje sistemskih nastavitev, časovnikov, …) z izjemo branja in pisanja datotek v trenutnem direktoriju (kjer imaš lahko vnaprej pripravljene izračune).
Cilj
Cilj vsakega od igralcev je pobrati čim več zakladov. Igre je konec, ko so pobrani vsi zakladi ali pa je poteklo 10000 korakov.
Vsak igralec ima na voljo 100 sekund procesorskega časa (na 4-procesorskem AMD Opteronu, uporablja lahko vse 4 procesorje) za vseh 10000 korakov, uporablja pa lahko največ 4 GB pomnilnika. Igralec, ki prekorači časovno ali prostorsko omejitev, se do konca trenutne igre ne more več premakniti.
Razvojno okolje
Za razvoj boš potreboval:
-
Testno okolje (napisano v pythonu). 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 iger, velikost igralne površine (n) in začetno število zakladov. Program počaka, da se z njim povežeta oba igralca, nato pa izvede želeno število iger, vsako z drugim naključnim začetnim razporedom zakladov. Po vsaki igri izpiše, koliko točk je dosegel kateri od igralcev.
-
[novo] Testno okolje z grafičnim uporabniškim vmesnikom (potrebuje .NET framework 1.1). Zraven je tudi izvorna koda (v C#) in projekt za Visual Studio 2003.
in zasnovo za igralca. Ta je trenutno na voljo v naslednjih jezikih:
- C++ (z Visual Studio 2005 projektom, prevede se tudi pod linuxom)
- C# (z Visual Studio 2005 projektom)
- VB.net (z Visual Studio 2005 projektom)
- 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.
Vsaka zasnova že vsebuje vse potrebno za komunikacijo in pa datoteko z imenom Lovec.java (oz. Lovec.cs,
Lovec.cpp, ...), ki vsebuje
funkcije ZbudiSe, KamGres in KonecIgre s preprostim primerom uporabe in spremenljivko Ime (ime tvojega igralca).
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).