Tekmovalni dnevi Instituta Jožef Stefan

Labirint — tekmovanje programov

• Rezultati.

Robot se premika po labirintu, ki je definiran kot karirasta mreža velikosti w × h. Vsako polje mreže je lahko prosto ali pa zazidano, na prostem polju pa lahko stoji tudi velika lahka kocka. Robot se lahko premika po labirintu ter pobira, prenaša in odlaga kocke, njegov cilj pa je najti izhod iz labirinta (torej neko prosto polje na zunanjem robu labirinta). Premikanje kock mu pride prav zato, da si pripravi prostor za gibanje (ker se na polje, na katerem stoji kocka, ne more premakniti).

Izziv pri tej nalogi je, da robot ne pozna celega labirinta vnaprej, pač pa v vsakem trenutku vidi le nek omejen del labirinta v okolici svojega trenutnega položaja. Tvoja naloga je napisati podprogram, ki vodi obnašanje robota — od nadzornega programa dobi podatke o tem, kaj robot vidi, in mora odločiti o robotovih nadaljnjih potezah.

Tipi polj

Polja so dveh vrst: prosta in zazidana. Polja na zunanjem robu mreže (torej v najbolj levem in najbolj desnem stolpcu ter v najbolj zgornji in najbolj spodnji vrstici) so malo drugačna od ostalih: prosto polje na zunanjem robu imenujemo tudi izhodno polje; zazidano polje na zunanjem robu pa imenujemo zunanji zid.

Na prostih poljih (in tudi na izhodnih poljih) lahko stojijo kocke, vendar največ ena kocka na vsakem takem polju. Začetno stanje labirinta bo vedno tako, da nobena kocka ne stoji na izhodnem polju.

Vidljivost

Robotovi senzorji mu vračajo le omejene podatke o njegovi okolici. Robot „vidi“ le v smeri 45 stopinj levo in desno od smeri, v katero je trenutno obrnjen. Vidi le polja, ki so največ v enot pred njim (število v dobi podano ob začetku igre). Če na nekem praznem ali izhodnem polju stoji kocka, je ta kocka za robotove senzorje nerazločljiva od (nezunanjega) zidu. Pač pa robotovi senzorji ločijo zunanje zidove od nezunanjih (ali od polj, na katerih stojijo kocke) in ločijo izhodna polja od navadnih prostih polj (kakršna stojijo v notranjosti labirinta).

Če na nekem polju stoji zid ali pa kocka, nam to polje zakriva pogled na polja, ki stojijo za njim. Če je neko polje v celoti zakrito s takšnimi zidovi in/ali kockami, ga robot ne vidi.

Primer: spodnja slika kaže primer labirinta; robot (predstavlja ga črni trikotnik) stoji na polju (2, 7) in je obrnjen proti desni. Zunanji zidovi so temno zeleni, notranji so temno sivi, izhodno polje je svetlo zeleno, kocke pa so rdeče.

Naslednja slika kaže območje, ki bi ga robot pri tem položaju teoretično lahko videl, če je vidljivost omejena na v = 5 enot:

Naslednja slika kaže, kako kocka na polju (5, 5) zakriva pogled na nekatere dele prostora, med drugim tudi na kocko na polju (5, 4). Polovica te slednje kocke leži zunaj robotovega vidnega polja (to smo videli na prejšnji sliki), drugo polovico pa zakriva kocka (5, 5), zato robot kocke (5, 4) sploh ne vidi — za polje (5, 4) ne ve, kaj je na njem.

Naslednja slika kaže, katera polja robot dejansko vidi; pogled na ostala polja mu zakrivata zid in kocka. Polja, ki jih vidi le delno, so narisana tako, kot da so vidna v celoti, saj robot lahko ve, da je posamezno polje nedeljivo (torej če je npr. tisti del polja, ki ga robot vidi, prost, je tudi preostanek tega polja prost).

Spodnja slika kaže, kakšno je torej vidno polje robota z njegovega vidika. Z modro barvo so označena polja, za katera robot ne dobi podatka o tem, kaj je na njih. Opozorimo tudi na to, da z vidom ne more ločiti med zidom in kocko (zato je tudi kocka narisana s sivo barvo).

Možne poteze robota

Robot lahko v vsakem koraku izvede eno od naslednjih potez:

• Premik za eno polje naprej (v tisti smeri, v katero je robot trenutno obrnjen). Ta poteza je možna le, če je polje pred robotom prosto (in na njem ne stoji kocka).

• Zasuk na mestu za 90 ali 180 stopinj levo ali desno.

• Pobiranje kocke, ki stoji na polju pred robotom. Če je to polje prosto in na njem ne stoji kocka, se poskus pobiranja šteje za napako. Če robot že od prej nosi neko kocko, se poskus pobiranja tudi šteje za napako. Če je polje pred robotom v resnici zid, ne pa kocka na prostem polju, se poskus pobiranja ne šteje za napako, vendar pa robot zidu ne more pobrati — v naslednji potezi torej ostane praznih rok, pred njim pa je še vedno zid.

• Odlaganje kocke, ki jo robot nosi, na polje pred njim. Ta poteza je možna le, če robot trenutno nosi kocko in je polje pred robotom prosto in na njem še ne stoji kocka.

Medtem ko nosi kocko, se lahko robot obrača in premika pod enakimi pogoji kot sicer, vendar pa se te poteze takrat štejejo kot dražje (za več o ceni potez glej spodaj).

Robot na začetku igre dobi podatek o tem, kako velika je mreža, ne pa tudi o tem, kje v njej se nahaja in v katero smer je obrnjen. Pred vsako potezo dobi podatek o tem, ali trenutno nosi kocko in kaj trenutno vidi glede na svoj položaj in orientacijo. Polja, ki jih vidi, dobi našteta od leve proti desni.

Zagotovljeno je, da na začetku igre robot stoji na prostem polju, na katerem ni kocke, in da tudi sam ne nosi kocke. Labirinti pri tej nalogi so vsi sestavljeni tako, da za vsak možni začetni položaj robota obstaja vsaj eno tako izhodno polje, do katerega lahko robot pride z nekim zaporedjem zgoraj opisanih potez.

Vsaka poteza ima svojo ceno. Cena posamezne poteze je 1, razen v primeru, ko robot nosi kocko in se premakne naprej ali zasuka na mestu, tedaj pa ima poteza ceno 2. Skupna cena zaporedja več potez je definirana kot vsota cen vseh potez v zaporedju.

Pravila tekmovanja

Vsak tekmovalec napiše podprogram za krmiljenje robota (ta podprogram dobi na začetku podatke o velikosti labirinta, kasneje med igro pa podatke o tem, kaj robot trenutno vidi in ali trenutno prenaša kocko). Podprogram vsakega tekmovalca bomo pognali na več labirintih (na vsakem po enkrat). Točkovanje je pri vsakem labirintu relativno glede na najboljše prejeto zaporedje potez za ta labirint. Če tekmovalec pri nekem labirintu ni pripeljal robota do izhoda (npr. ker je naredil neveljavno potezo ali pa prekoračil časovno omejitev), ne dobi pri tem labirintu nobenih točk. Sicer pa, če je njegov robot opravil zaporedje potez s skupno ceno C, najboljše znano zaporedje potez pri tem labirintu pa ima skupno ceno C*, bo tekmovalec pri tem labirintu dobil C*/C točk. Nato točke tekmovalca seštejemo po vseh labirintih. Zmagovalec bo tisti tekmovalec, čigar program bo zbral največje skupno število točk.

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 6. marca 2009, lahko pa nam jih pošljete tudi že prej; programe bomo takoj po prejemu ocenili in rezultate objavili na tej spletni strani. Isti tekmovalec lahko pošlje tudi več različnih programov (vendar največ 10), pri čemer se bo na koncu upošteval najboljši izmed tako doseženih rezultatov. 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 4. tekmovanja IJS v znanju računalništva (28. marca 2009).

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

Labirinti, na katerih bomo preizkušali dobljene programe, bodo veliki največ 50 × 50 polj. Program lahko za vodenje robota po posameznem labirintu porabi največ 10000 sekund procesorskega časa, robot pa sme pri tem narediti največ 100000 potez. Večina testnih labirintov bo še manjših, velikosti največ 30 × 30 polj; pri njih sme program za posamezni labirint porabiti največ 1000 sekund procesorskega časa. (Igra bo potekala na računalniku z vsaj 2GHz AMDjevimi Opteroni.) Posamezni robot lahko uporablja največ 4 GB pomnilnika v kateremkoli trenutku. Dovoljena je uporaba 64-bitnega naslavljanja in ostalih zmogljivosti teh procesorjev (npr. ukazi SIMD), če izbrani programski jezik to omogoča. Robot, ki prekorači časovno ali prostorsko omejitev, ali pa naredi neveljavno potezo (npr. poskuša premakniti robota na polje, na katerem stoji zid), dobi pri tistem labirintu 0 točk.

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 C++, zraven je tudi prevedena različica za Windows). Ta program deluje kot strežnik, na katerega se poveže odjemalec, ki krmili robota. Poženi ga iz ukazne vrstice, s parametri pa mu lahko poveš ime datoteke z opisom labirinta, število iger, maksimalno število potez na igro ipd. Program počaka, da se z njim poveže odjemalec, ki bo upravljal robota, nato pa izvede želeno število iger. Po vsaki igri izpiše nekaj statistik o številu opravljenih potez.
   
  [novo] 6. januarja 2009: nova verzija, ker je stara v nekaterih primerih sporočala več polj, kot jih je robot dejansko videl. Testno okolje v C# (glej spodaj) te napake ni imelo.

• Testno okolje z grafičnim uporabniškim vmesnikom (potrebuje .NET framework 2.0). V arhivu je tako prevedena različica kot izvorna koda (v C#).
   
  [novo] 14. novembra 2008: nova verzija, ki bolj temeljito reže CRLFje s konca vrstic. Potrebna je za delo z odjemalcem v C#.

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

• C++ (s projektom za Visual Studio 2005; če prevajate za Windows s čim drugim, ne pozabite prilinkati zraven še knjižnice WinSock, ws2_32.lib)
• C# (s projektom za Visual Studio 2005)
• Python
• Pascal (prevede se s FreePascalom s stikalom -S2, upajmo, da se bo prevedla tudi z Delphijem)

Za lažje testiranje smo pripravili tudi nekaj labirintov, podobnih tistim, na katerih bomo preizkušali prispele programe:

• lab1.txt
• lab2.txt
• lab3.txt

Struktura datotek z labirintom je takšna: v prvi vrstici so tri cela števila, h (višina labirinta), w (širina labirinta) in v (vidljivost: kako daleč pred sabo vidi robot). Sledi h vrstic, v vsaki mora biti w znakov, ki opisujejo labirint. Možni znaki so Z (zunanji zid), x (izhodno polje), # (notranji zid), O (kocka) in . (prazno polje). Začetni položaj in orientacija robota naj bo označena z enim od znakov <, >, ^ ali v.

Vsaka zasnova že vsebuje:

• vse potrebno za komunikacijo z ocenjevalnim programom (datoteke LabClient_*.*, ki jih ne spreminjaj),
• datoteko z imenom Robot.*, ki v razredu Robot vsebuje funkcije ZbudiSe, KamGres (s preprostim primerom) in KonecIgre ter spremenljivko Ime (ime tvojega igralca). Te datoteke lahko spreminjaš po želji, v razred Robot lahko dodajaš nove spremenljivke in funkcije, itd.

Za testiranje najprej zaženeš testno okolje, potem pa še program za upravljanje robota.

Nekaj podrobnosti

Robot od strežnika ne dobi točnega podatka o tem, kje v labirintu se nahaja. Podatki o tem, kaj robot trenutno vidi, so izraženi relativno glede na robotov trenutni položaj. Polja torej niso označena z običajnimi koordinatami (x, y), pač pa s pari (r, c), pri čemer r pove, koliko enot pred robotom je opazovano polje, c pa pove, koliko enot levo ali desno od njega je. Z drugimi besedami, os r kaže vedno v smeri, v katero gleda robot, os c pa kaže v smer, ki je za robota trenutno desno. Oglejmo si še enkrat primer z gornje slike:

V tem primeru bi torej robot od strežnika dobil podatke, da so polja (1, -1), (1, 0), (1, 1), (2, -2), (2, -1), (2, 0), (2, 1), (3, -1), (3, 0), (3, 1), (4, -2), (4, -1), (4, 1), (5, -2), (5, -1) in (5, 1) prosta; da je na poljih (3, -2) in (4, 0) zid in/ali kocka; da je (3, 2) prosto izhodno polje; in da so na poljih (2, 2), (4, 2) in (5, 2) zunanji zidovi.

V seznamu, ki ga vrne strežnik, so polja vedno urejena po kotu glede na robota (torej so urejena po razmerju c/r); tista z enakim kotom pa so med seboj urejena po oddaljenosti od robota.

Rezultati

Za preizkušanje prejetih rešitev smo uporabili nabor 31 labirintov; po zgoraj opisanih pravilih točkovanja lahko torej posamezna rešitev dobi od 0 do 31 točk.

Ime	Datum	Točke
Rok Kralj	29. 12. 2008	28,405
Matjaž Leonardis	27. 3. 2009	14,713
Gašper Medved	6. 3. 2009	4,430
Naključni robot		0,131

Glavni razlog, zakaj imajo nekateri tekmovalci manj točk kot drugi, ni to, da bi bili njihovi roboti toliko počasnejši, ampak to, da se pri nekaterih testnih primerih njihov program sesuje ali pa se robot zacikla ali pa naredi neveljavno potezo.

[„Naključni robot“ je tisti iz zgoraj objavljenih zasnov za robota: na vsakem koraku naključno izbere eno od možnih potez, pazi le na to, da ne bi delal neveljavnih potez (npr. se zaletel v zid ali pa poskusil pobrati še eno kocko, medtem ko eno že drži, ipd.).]

 

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