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.

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:

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

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 (2.0 * Pi);
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).

Na vrh strani. | H kazalu.