Tekmovalni dnevi Instituta Jožef Stefan
Tekmovanje mačk in miši
Na igralno polje naključno postavimo mačko in miš. Igra poteka v korakih. V vsakem koraku se obe živali odločita o željenem premiku, ki ga opišeta s pospeškom in spremembo smeri. Obe živali imata enake omejitve pri spreminjanju hitrosti in smeri. Mačkin cilj je uloviti miš, naloga miši pa je uspešno bežati pred mačko. Obe živali se morata tudi izogibati temu, da bi se zaleteli v robove igralnega polja.
Vsak tekmovalec napiše en podprogram za krmiljenje mačke in/ali en podprogram za krmiljenje miši. Na tekmovanju bomo med seboj primerjali mačko enega tekmovalca z mišmi vseh ostalih tekmovalcev in obratno. Najboljša žival je tista, ki zmaga v največ tekmah (če jih bo več zmagalo v enakem številu tekem, bomo upoštevali tudi povprečno število korakov do konca igre — za mačko je bolje, če je igre konec čim prej, za miš pa, če čim kasneje). Podelili bomo po eno nagrado za najboljšo mačko in eno za najboljšo miš.
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 mačk in miši je 30. april 2006. 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, 6. maja 2006.
Opis naloge
Igralno polje je kvadratna površina velikosti 1.0 × 1.0, vse koordinate so opisane z realnimi števili (double precision floating point). Ob začetku igre sta obe živali postavljeni naključno: mačka nekje na območju 0.1 ≤ x ≤ 0.2, 0.1 ≤ y ≤ 0.9, miš pa na 0.8 ≤ x ≤ 0.9, 0.1 ≤ y ≤ 0.9. Tekmovalci za vsako žival napišejo tri funkcije.
Prva (
ZbudiSe
) se pokliče ob začetku igre, za parametra dobi začetni poziciji obeh živali, vrne pa naj želeno začetno smer. Istočasno lahko tudi pripravi globalne spremenljivke in vse, kar žival potrebuje za razmišljanje.Druga funkcija (
KamGres
) se izvede enkrat na korak. Kot parameter dobi poziciji, smeri in hitrosti obeh živali, vrne pa naj želeno spremembo hitrosti in smeri. Sprememba hitrosti je možna le v območju med
in-MAX_SPREMEMBA_HITROSTI
, sprememba smeri pa med+MAX_SPREMEMBA_HITROSTI
(desno) in-MAX_SPREMEMBA_SMERI
(levo).+MAX_SPREMEMBA_SMERI Zadnja funkcija (
KonecIgre
) se pokliče ob koncu igre, kot parameter pa dobi razlog za konec igre.
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
Če mačka uspe v v naprej določenem številu korakov (3000) ujeti miš, zmaga. Miš je ujeta, ko sta obe živali
na razdalji manjši od neke vrednosti (DOSEG_LOVCA
). V nasprotnem primeru se smatra, da je miš sposobna pobegniti
pred mačko (torej zmaga miš). Žival, ki se zaleti v "steno" (ima koordinate, ki niso z intervala [0,1]),
avtomatično izgubi. Če se v istem koraku v steno zaletita obe živali, je rezultat neodločen.
Vsaka žival ima na voljo 1000 sekund procesorskega časa (na 4-procesorskem AMD Opteronu, uporablja lahko vse 4 procesorje) za vseh 3000 korakov, uporablja pa lahko največ 4 GB pomnilnika. Ob prekoračitvi časovne ali prostorske omejitve žival avtomatično izgubi.
Razvojno okolje
Za razvoj živali boš potreboval:
- testno okolje (napisano v .NET; nova različica 2006-03-16b, popravljena nepravilnost v komunikaciji na slovenskih windowsih, izboljšana funkcionalnost) (pripadajoča izvorna koda v C#)
in zasnovo za žival. Ta je trenutno na voljo v naslednjih jezikih:
- Java
- Java (z IntelliJ IDEA projektom)
- C# (z Visual Studio 2005 projektom)
- VB.net (z Visual Studio 2003 projektom)
- Delphi
- Python
- PHP
- C++ (prevede se vsaj z Microsoft VS 2003/2005 in z gcc-jem pod linuxom)
Tu bodo objavljeni tudi morebitni popravki in izboljšave razvojnega okolja in zasnov živali, pa tudi zasnove živali v novih jezikih.
Vsaka zasnova že vsebuje vse potrebno za komunikacijo in pa datoteko z imenom zival.java
(oz. zival.cs
,
zival.cpp
, zival.pas
, ...), ki vsebuje
funkcije ZbudiSe
, KamGres
in KonecIgre
s preprostim primerom uporabe in spremenljivki Ime
(ime tvoje živali)
in Tip
(miš ali mačka). Za testiranje najprej zaženeš testno okolje, potem pa še po eno mačko in miš.
Za hitrejši razvoj sta na voljo tudi nekoliko pametnejši nasprotnici (brez izvorne kode) v Win32 in Linux različici. Naj le opozorimo, da se bodo nasprotnice na pravem tekmovanju verjetno obnašale popolnoma drugače, zato ti dve nista ustrezno merilo pri razvoju vaših.
Razni tehnični detajli
Potek koraka
Obe živali izvajata korak vzporedno, na podatkih prejšnjega koraka in zahtevanih popravkov.
Zival.Smer := (Zival.Smer + ZeljenaSpremembaSmeri) mod
Zival.Hitrost := Zival.Hitrost + ZeljenaSpremembaHitrosti;
if Zival.Hitrost < 0.0 then Zival.Hitrost := 0;
Zival.X := Zival.X + ( Zival.Hitrost * cos(Zival.Smer) );
Zival.Y := Zival.Y + ( Zival.Hitrost * sin(Zival.Smer) );
Matematične osnove
Vsi koti so v radianih (360° = 2.0*π radianov), kot 0 pa je prikazan na spodnji skici.
Razdalja = sqrt(Δx * Δx + Δy * Δy)
KotDoNasprotnika = atan2(Δy, Δx)
Δx = Razdalja * cos(KotDoNasprotnika)
Δy = Razdalja * sin(KotDoNasprotnika)
Za jezike, ki nimajo funkcije atan2(Δy, Δx) oz. arctan2(Δy, Δx):
function atan2(dy: double; dx: double): double;
begin
if dx > 0.0 then
atan2 := arctan(dy/dx);
else if dx < 0.0
atan2 := arctan(dy/dx) + Pi;
else
atan2 := (Pi/2.0) * sgn(dy)
end;
Če imate v zvezi s tekmovanjem mačk in miši kakršna koli vprašanja, se obrnite na Blaža Novaka (blaz.novak@ijs.si).